基于物理不可克隆函数的高性能RFID网络隐私保护算法

周恩辉，刘雅娜

(1.河北师范大学 数学与信息科学学院，河北 石家庄 050024；2.石家庄学院 数学与信息科学学院，河北 石家庄 050035)

基于物理不可克隆函数的高性能RFID网络隐私保护算法

周恩辉1，刘雅娜2

(1.河北师范大学 数学与信息科学学院，河北 石家庄 050024；2.石家庄学院 数学与信息科学学院，河北 石家庄 050035)

RFID网络是物联网中物体身份识别的重要方案，RFID系统的安全性直接影响物联网的安全性。已有的RFID隐私保护算法均需要线性地搜索后端的数据库从而识别某个标签，因此后端数据库的计算复杂度与延迟较高。对此基于物理不可克隆函数(PUF)提出一种无需数据库搜索操作的低计算复杂度隐私保护算法。首先，采用PUF安全地保存标签的秘密信息以抵御妥协攻击；然后，数据库端仅需要3个哈希运算与两个异或运算，计算复杂度为O(1)。最终，基于Vaudenay的RFID隐私安全模型分析本算法的性能，结果显示其具有最高的隐私等级，同时计算复杂度最低。

RFID网络；物联网；隐私保护；物理不可克隆函数

0 引言

由于人们无法感知射频信号的非法读取，导致RFID技术存在特有的安全与隐私问题。在RFID系统的标签与阅读器之间主要存在以下7种攻击：假冒标签攻击、假冒读写器攻击、跟踪标签攻击、窃听攻击、中间件攻击、重放攻击、去同步攻击。其中假冒读写攻击、跟踪标签攻击、窃听攻击与中间件攻击破坏标签的隐私性。因此保证RFID系统的隐私，需要满足保密性、不可跟踪性、前向安全与验证读写器 4种隐私保护需求[1]。一些研究使用树结构来保存秘钥，以此降低搜索复杂度(O(n)-＞O(log n))，而此类方案易受妥协攻击，因此，基于树状协议的隐私等级较低。

文献[2]基于物理实体的内在物理构造来唯一地标识单个物理实体实现有效认证的思路，提出了 PUF(物理不可克隆函数)，PUF具有鲁棒性、不可克隆性以及不可预测性特点，目前广泛应用于RFID系统的认证领域。文献[3，4]均采用PUF(物理不可克隆函数)来提高RFID的安全性，然而此类算法均为narrow-destructive隐私性[5]，其搜索复杂度最低为O(logN)。

本文提出一种基于PUF的RFID验证协议，本协议最大的优势是无需搜索数据库(识别标签)，其搜索复杂度仅为O(1)，因此本协议可应用于大规模 RFID网络。本协议在标签与阅读器端不需要多余的计算与通信开销，并且本算法可抵御旁道攻击。

1 背景知识介绍

假设标签为T，其 ID唯一，阅读器为 R。RFID系统包含若干的阅读器R、发送器以及一个后端数据库，发送器与数据库间有一个信道。

1.1 系统模型

RFID功能可表示为如下的函数形式：

(1)SetupReader(1S)→(KS，KP)：生成一个公共参数 KP、一个隐私参数KS与一个阅读器的安全参数s，同时生成一个数据库(其中保存标签的ID)。

(2)SetupTagKP(ID)→(K，S)：生成一个标签(ID唯一)、一个秘钥K与一个内存状态S。如果该标签合法，则将ID与K保存于数据库中。

(3)IdentTag→out：该函数表示标签T与阅读器R之间的一次交互。如果阅读器最终识别出该标签，则输出标签的ID，否则输出“?”。

1.2 攻击模型

假设攻击者A具备以下性质：首先，攻击者C执行SetupReader(1S)程序，生成 1S、KS与 KP3个参数，并将1S、KP传至 A；然后 A使用 CreateTagb(ID)生成标签，本模型按标签是否在攻击者的阅读范围内将标签分类：如果在阅读范围内分类，则为危险标签(DanTag)，否则为安全标签(SecTag)。

为攻击者定义以下10个行为或攻击能力：

(1)CreateTagb(ID)：创建一个 SecTag并为其分配一个ID。该函数使用 SetupTagKP(ID)创建标签，如果该标签合法(b=1)，则将其加入数据库中。

(2)DanTag(distr，n)→(vtag0，b0，…，vtagn-1，bn-1)：从SecTag标签集中随机地选择n个标签，并将标签状态从 SecTag变为Dantag。为选择的标签分配一个新的 ID并输出虚拟标签(vtag0，…，vtagn-1)，如果该标签已经为 Dantag或已不存在，则输出“？”。

(3)Free(vtag)：将标签状态从DanTag变为SecTag。

(4)Launch()→π：触发阅读器开始新的协议循环，输出为该轮协议的IDπ(为每轮协议设置一个标识ID)。

(5)SendReader(m，π)→m′：发送一个消息m至阅读器R(在协议循环π中)，阅读器的回复消息为m′。

(6)SendTag(m,vtag)→m′：发送一个消息 m至标签，其虚拟ID为vtag。阅读器的回复消息为m′。

(7)Execute(vtag)→(π，transcript)：在标签(该标签虚拟ID为vtag)与阅读器之间执行完整的协议。该协议由Lauch()开始，然后是SendReader与 SendTag，输出协议循环 π的成功消息列表。

(8)Result(π)→x：如果阅读器成功识别一个合法的标签，则返回 1；否则返回 0。

(9)Time(π)→δ：返回阅读器的总计算时间δ。

(10)Corrupt(vtag)→S：获得标签(虚拟ID为 vtag)的当前状态S。

1.3 隐私分类

攻击者分为强(strong)、破坏性(destructive)、前向(forward)、弱(weak)攻击者，此外与这 4类攻击者正交的还有wide与narrow两个攻击者的概念，wide攻击者可通过阅读器访问认证结果，但 narrow攻击不行。图1描述了6种攻击概念之间的关系[5]。

图1 6种隐私概念之间的关系

1.4 安全性级别

定义1正确性：如果在IdentTag程序之后 R返回标签ID的成功率极高，则认为该协议符合正确性。

定义2强正确性：如果在R与合法标签T交互之后返回标签ID的成功率极高，则认为符合强正确性。

定义3稳固性[5]：如果对合法标签 T假冒攻击的成功率极低，则认为符合稳固性。

1.5 隐私性

定义4盲攻击：假设B表示一个算法，仿真了Lauch()、SendReader(m，π)、SendTag(m，vtag)与 Result(π)4个程序的串行组合(对于攻击者A)，并且不知道任何的秘密信息。一个盲攻击者(AB)不使用Lauch()、SendReader(m，π)、SendTag(m，vtag)与Result(π)程序，如果存在B，则攻击者A威胁极小，即|Pr[Awins]-Pr[ABwins]|可忽略不计。

2 本文大规模RFID网络安全协议

定义 5 Hash函数：假设 l∈N是一个安全参数，γ，K∈N是 l中的项，则 hash函数 H可定义为{0，1}γ→{0，1}K，其条件为：

(1)对于一个给定的输出 yi，无法反向计算出满足H(xi)=yi的 xi。

(2)计算出满足条件 xi≠xj&&H(xi)=H(xj)的参数组合(xi，xj)难度极高。

定义 6物理不可克隆函数(PUF)[6]：假设 l∈N是安全参数，γ，K∈N是l的项。理想的PUF(设为P)定义为{0，1}γ→{0，1}K，其条件如下：

(1)对于参数对(ci，cj)∈{0，1}γ，P(ci)=ri，P(cj)=rj。如果 ci=cj，则概率Pr[ri=rj]=1。

(2)攻击者无法在有限次数内计算出P的输出。

表1所示是本文预设参数及其意义。

本文协议主要有两个阶段：初始化与验证阶段，图2所示是本文RFID隐私保护协议的主要流程。

2.1 初始化阶段

为数据库随机生成秘钥S，为每个标签生成两个随机且唯一的秘钥a与b。然后，为每个标签计算其秘钥c=S⊕P(a)⊕P(b)，其中P(·)是各标签的嵌入 PUF。数据库保存每个标签的基本信息{ID，a，b，DATA}。

2.2 验证阶段

(1)每个阅读器生成一个随机数 r1∈{0，1}l并广播该随机数。

(2)标签Ti生成一个随机数r2∈{0，1}l，计算M1←H(r1，r2，ai)，M2←H(r1，r2，ai)⊕IDi，h←H(r2，1，2)。然后，将Pi(ai)与 r2做异或运算，计算出消息 k。使用 k⊕Pi(bi)⊕ci代替消息k，从内存中删除 Pi(bi)。标签将 M1、M2、k发送至阅读器。

(3)阅读器生成一个随机数 r3∈{0，1}l。计算←S⊕k与←M2⊕H(，r1，1)。阅读器通过计算 H(r1，，ai)验证M1以实现标签Ti的验证。如果成功验证标签Ti，阅读器则计算 M3=H(H(，1，2)，r3，bi)，然后将 r3与 M3发送回标签Ti。

(4)标签 Ti通过计算 H(h，r3，bi)验证 M3。如果验证成功，则Ti成功验证阅读器。

表1 本文的参数定义

图2 本文协议主要流程

3 本文协议的性能分析

3.1 安全性分析

本文协议理论上可抵御假冒攻击，下文将证明本方法对假冒攻击具有安全性。因为本文协议是无状态协议，并且标签无需与数据库保持同步，因此，去同步攻击对本协议也无效。

引理1：假设A是一个destructive级别的攻击者。A的特点是在不执行Corrupt程序的情况下，获得共享秘钥的成功率极低。

证明：假设有一个攻击者A可学习共享秘钥(不执行Corrupt程序)。每个标签响应阅读器的查询语句(M1，M2，k)，其中k=S⊕r2，r2是标签产生的随机值。为了获得共享秘钥S，A需要知道随机数r2，然而，r2并没有随密文发送，A必须从消息M1、M2与M3中破解出 r2。此外，将标签ID IDi以密文形式H(r2，r1，1)⊕IDi发送至阅读器，在不知道随机值的情况下A无法破解出IDi。

3.2 计算效率与隐私性实验与分析

在此分析标签端与数据库端的性能。本协议中，一个标签共需完成4个hash运算、两个PUF运算与4个XOR运算，数据库端则需要完成一个标签验证程序，该验证需要3个hash运算与两个XOR运算，其复杂度为O(1)。本协议在标签端与数据库端均无需秘钥更新机制。

表2所示是本文方法与其他RFID隐私保护算法的计算效率与隐私性比较，其中，成本 1：共 2128个标签的RFID网络；成本 2：共 216个标签的 RFID网络；成本 3：共N个标签的RFID网络；nonce：生成随机数操作；hash：哈希运算；PUF：PUF运算。从中可看出，本方法具有最高的隐私等级，并且其数据库端的计算复杂度较低。

表2 各协议性能比较

4 结论

PUF具有鲁棒性、不可克隆性以及不可预测性特点，本文提出一种基于 PUF的RFID验证协议，本协议最大的优势是无需搜索数据库(识别标签)，其搜索复杂度仅为O(1)，因此本协议可应用于大规模 RFID网络。与其他RFID隐私保护算法的比较结果显示，本方法具有最高的隐私等级，并且其数据库端的计算复杂度较低。参考文献

[1]王良民，茅冬梅，梁军.基于RFID系统的隐私保护技术[J].江苏大学学报：自然科学版，2012，33(6)：690-695.

[2]PAPPU R.Physical one-way functions[J].Science，2002，297 (5589)：2026-2030.

[3]AKGUN M，CAGLAYAN M U.PUF based scalable private RFID authentication[C].Availability，Reliability and Security (ARES)，2011 Sixth International Conference on.IEEE，2011：473-478.

[4]KARDAS S，KIRAZ M S，BINGÖL M A，et al.A novel RFID distance bounding protocol based on physically unclonable functions[C].Lecture Notes in Computer Science，2011：78-93.

[5]VAUDENAY S.On privacy models for RFID[M].Advances in Cryptology-ASIACRYPT 2007.Springer Berlin Heidelberg，2007：68-87.

[6]SADEGHI A R，VISCONTI I，WACHSMANN C.Pufenhanced rfid security and privacy[J].2nd Workshop on Secure Component and System Identification(SECSI′10)，2010，24(3)：381-394.

[7]MOLNAR D，WAGNER D.Privacy and security in library RFID：issues，practices，and architectures[C].Acm Conference on Computer&Communications Security，2004：210-219.

[8]BRINGER J，CHABANNE H，ICART T.Improved privacy of the tree-based hash protocols using physically unclonable function[J].Lecture Notes in Computer Science，2007：77-91.

[9]AVOINE G，DYSLI E，OECHSLIN P.Reducing time complexity in RFID systems[C].Lecture Notes in Computer Science，2005，3897：291-306.

[10]ALOMAIR B，CLARK A，CUELLAR J，et al.Scalable RFID systems：a privacy-preserving protocol with constant-time identification[J].Parallel&Distributed Systems IEEE Transactions on，2011，23(8)：1536-1550.

[11]AKGUN M，CAGLAYAN M U.PUF based scalable private RFID authentication[C].Availability，Reliability and Security (ARES)，2011 Sixth International Conference on.IEEE，2011：473-478.

[13]ASADPOUR M，DASHTI M T.Scalable，privacy preserving radio-frequency identification protocol for the internet of things[J].Concurrency and Computation：Practice and Experience，2013，27(8)：1932-1950.

Physically unclonable function based high performance privacy protection algorithm of RFID network

Zhou Enhui1，Liu Yana2
(1.College of Mathematics and Information Science，Hebei Normal University，Shijiazhuang 050024，China；2.College of Mathematics and Information Science，Shijiazhuang University，Shijiazhuang 050035，China)

RFID network is an important solution for the identification of Internet of Things,the security of RFID system impacts the security of the Internet of Things directly.The existing RFID privacy protection algorithms need to search the backend database to validate a tag,so that the database has a high computational complexity and delay.Thus a physical unclonable function based low computational complexity privacy protection algorithm which does not need searching the database is proposed.Firstly,PUF is used to store the secret information of the tags securely to resist the compromising attack.Then,three hash function and two XOR computation are needed for database and it′s computational complexity is O(1).Lastly,the proposed algorithm is analyzed based on the RFID privacy and security model proposed by Vaudenay.The results show that the proposal realize the best privacy level and the lowest computational complexity.

RFID network；Internet of Things；privacy protection；physical unclonable function

TP29

A

10.16157/j.issn.0258-7998.2016.03.028

周恩辉，刘雅娜.基于物理不可克隆函数的高性能 RFID网络隐私保护算法[J].电子技术应用，2016，42 (3)：98-101.

英文引用格式：Zhou Enhui，Liu Yana.Physically unclonable function based high performance privacy protection algorithm of RFID network[J].Application of Electronic Technique，2016，42(3)：98-101.

2015-11-18)

周恩辉（1973-），男，硕士，实验师，主要研究方向：计算机图形图像处理，多媒体技术，计算机网络等。

刘雅娜（1973-），通信作者，女，硕士，讲师，主要研究方向：技术经济，运筹学，E-mail：liuya_na@163.com。