采用PUF保护位置隐私的轻量级RFID移动认证协议*

孙子文，李 松

1.江南大学 物联网工程学院，江苏 无锡 214122

2.江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 214122

1 引言

无线射频识别技术（radio frequency identification，RFID）凭借快速识别和非接触射频通信的特性，成为供应链系统实现商品的自动化管理和信息追溯的重要技术手段。供应链系统普遍采用EPC C1G2（electronic product code class 1 generation 2）标准的低成本射频标签（以下简称标签）具有远距离识别和抗干扰性强的优势，与此同时，标签受限于成本限制，无法应用成熟的加密机制实现标签的安全和隐私保护。供应链系统中将标签附着在商品上以完成对商品的识别和追溯，由于标签会对任意读写器的请求做出响应，攻击者发动恶意攻击获得标签中的商品信息，并通过追踪不同时刻的标签位置，将直接泄露商品在流通过程以及使用过程中商品所有者的位置隐私[1]。

为防止攻击者对标签的位置追踪，文献[2]采用密钥更新式和列表式协议实现了标签的匿名性和位置的不可追踪性，但协议采用的RSA非对称加密算法需要38K门电路，协议不适用于EPC C1G2标准，无法满足供应链系统对标签成本的限制[3]；文献[4]抛弃了运算成本高的哈希算法，标签只进行交叉、异或等简单的位运算，符合EPC C1G2标准，但攻击者可通过物理入侵获得标签和读写器密钥，从而通过对标签和读写器反向克隆的方式发起假冒攻击；文献[5]采用物理不可克隆函数（physical unclonable function，PUF）[6]作为密钥生成机制，标签只在认证过程由PUF电路产生相应的会话密钥，避免传统加密机制将密钥存储在非易失性存储器易被攻击者窃取的弊端，可有效抵御假冒攻击[7]；文献[8]考虑了服务器与读写器之间的信道安全问题，引入服务器对读写器身份的安全认证，适用于移动读写器的认证环境；文献[2,5]中服务器对标签的识别需要遍历整个服务器，识别效率低不适用于供应链中大规模RFID系统的使用。

针对EPC C1G2标准的低成本标签运算能力低、易遭受假冒攻击、标签和读写器位置容易被追踪等问题，本文设计了一种采用PUF保护位置隐私的轻量级RFID移动认证协议（PUF based lightweight authentication protocol for location privacy in mobile RFID system,PLLM）。PLLM协议采用PUF函数生成密钥，64位输出的PUF电路仅需要500～700门电路[9]，标签的模平方运算仅需几百门电路，128位伪随机数生成需要1 500门电路，标签的安全电路整体仅需3 000门电路[8]，且协议不使用哈希函数等运算量大的加密算法，符合EPC C1G2的应用标准，解决标签运算能力不足的问题；标签密钥由两步PUF电路生成，攻击者对标签的入侵将直接导致PUF电路失活而无法获得完整密钥，使得攻击者无法克隆标签，以解决攻击者对标签的非法入侵和假冒攻击的问题，搭载PUF电路的标签使得商品同样具备不可伪造性，实现供应链中商品的防伪保护；协议通过不断更新的共享密钥，实现前向和后向不可追踪性，以解决供应链系统中攻击者对标签和读写器的位置追踪问题；服务器通过中国剩余定理可快速检索标签和读写器的合法身份，识别速率不随数据库中标签数目的增长而线性加长，满足供应链对RFID系统中标签规模可拓展的应用要求；Alagheband等人[10]改进了Vaudenay模型[11]的预假设，使其适用于前向隐私和后向隐私的分析。本文采用改进的Vaudenay模型证明PLLM协议的安全和隐私性。

2 安全隐私模型

Vaudenay提出的安全隐私模型对安全和隐私进行了严格定义，是目前为止用于协议分析最全面的安全隐私模型[12]。Vaudenay模型中，通过预言机描述了攻击者与RFID系统交互的过程，其中预言机的功能介绍如表1所示。

根据攻击者查询Corrupt预言机的权限，划分4类能力递进的攻击者，其中最弱的Weak攻击者无法查询Corrupt预言机，而Forward攻击者可查询Corrupt预言机，Destructive攻击者查询Corrupt后无法访问任何预言机，能力最强的Strong攻击者可以没有限制地进行Corrupt预言机查询。同时根据攻击者查询Result预言机权限划分Narrow和Wide的两类攻击者（Narrow攻击者无法查询Result，而Wide攻击者可以查询），最终根据以上两种不同的分类划分为8类攻击者。

Vaudenay模型的预假设及其应用中的不足：

（1）假设读写器与服务器之间的信道是安全的，未考虑读写器遭受假冒攻击的问题，不适用于移动读写器的认证环境。

（2）假设攻击者错过了标签密钥的更新过程，不符合位置追踪的实际攻击环境。

（3）假设标签仅在i次会话遭受攻击，未考虑攻击者对第i+1和i-1次会话中标签位置的追踪问题，不适用于前向和后向不可追踪性的协议分析。

基于以上三点不足，修改Vaudenay模型的预假设条件使其适用于位置隐私分析。将读写器与服务器之间的信道安全纳入协议的安全考量，考虑读写器遭受攻击者非法入侵和假冒攻击的问题，使其符合移动读写器的认证环境；假设敌人为Narrow-Strong的攻击者，没有错过密钥更新过程，可以对协议进行持续的监听；分析第i+1和i-1次会话协议的安全性，并依照Alagheband等人[10]提出的前向和后向不可追踪性，定义协议的位置隐私。

定义1（前向不可追踪性[10]）攻击者窃听标签第i次会话记录并通过入侵标签得到第i次会话的标签内部信息，攻击者分析第i+1次会话记录，无法推断出第i+1次标签内部信息和输出信息，因此攻击者无法对标签第i+1次状态进行追踪。

定义2（后向不可追踪性[10]）攻击者窃听标签第i次会话记录并通过入侵标签得到第i次会话的标签内部信息，攻击者分析第i-1次会话记录，无法推断出第i-1次标签内部信息和输出信息，因此攻击者无法对标签第i-1次状态进行追踪。

3 PLLM认证协议描述

PLLM协议使用的符号和注释如表2所示，PLLM协议由初始化和双向认证两个阶段组成。

Table 1 Function introduction of each oracle表1 预言机功能介绍

3.1 初始化阶段

密钥生成及共享机制。由服务器生成4个大素数p、q、g、h作为服务器解密标签和读写器会话信息的私钥，并将n=p⋅q,m=g⋅h分别作为标签和读写器加密会话信息的公钥。

Table 2 Annotation of each notation in this protocol表2 协议使用的符号及其注释

共享密钥S1由服务器生成并发送给标签和读写器，标签使用共享密钥S1和自身参数a、b，经内部PUF电路计算P(a)、P(b),用以生成参数c：

读写器使用S1和自身参数d、e，经内部PUF电路计算P(d)、P(e),用以生成参数f：

共享密钥S2由服务器生成并在每次认证成功后更新，初始状态S2=S-12,服务器计算系统中每个合法标签的索引值：

3.2 双向认证阶段

双向认证协议由读写器发起，协议流程如图1所示，具体认证步骤如下：

（1）由读写器生成随机数r1，并将r1以广播的形式发送给通信范围内的所有标签。

（2）标签接收到读写器广播信息r1后，生成随机数r2，并完成以下计算：

根据式（5）得到的x的值采用二次剩余定理计算：

根据式（6），服务器在后期的认证中采用中国剩余定理解密x′得到4个模平方根(x1,x2,x3,x4),服务器需执行4次匹配工作。为提高服务器的后台搜索效率，在式（7）中使用x2取代式（6）的x，服务器将求得唯一的模平方根x值[13]，从而解决了式（6）存在的非唯一解的问题。

标签的会话密钥kT由两步PUF生成。第一步由标签的PUF电路计算P(a)，并将P(a)异或随机数r2得到标签的会话密钥：

随即将P(a)和r2从标签内存中删除。

第二步运行标签PUF电路计算P(b)，使用P(b)和c更新标签会话密钥：

随即删除内存中的P(b)。

通过两步生成会话密钥，使得攻击者在任意时刻入侵标签都无法获得完整密钥，从而抵御攻击者的假冒攻击。

标签通过kT保护标签随机数r2，并通过x″保护标签标识符H(TID)，实现了标签匿名性和不可追踪性，达到保护标签位置隐私的目的。最后标签将[x″,kT]作为交互信息通过射频天线发送给读写器。

（3）读写器接收到来自标签的响应[x″,kT]后，生成随机数r3，并完成以下计算：

读写器的PUF电路生成P(d)后计算读写器的会话密钥：

随即将内存中的P(d)和r3删除。

Fig.1 Proposed authentication protocol图1 协议认证流程

运行读写器PUF电路生成P(e)，并更新会话密钥：

随即删除内存中的P(e)。

读写器通过kR保护读写器随机数r3，并通过y″保护读写器标识符H(RID)，实现了读写器匿名性和不可追踪性，达到保护读写器位置隐私的目的。最后读写器将[x″,kT,r1,y″,kR]发送给后台服务器。

（4）服务器接收到认证请求[x″,kT,r1,y″,kR]后，通过共享密钥S1与读写器的会话密钥kR异或求得：

采用中国剩余定理从式（12）中计算得到唯一的y：

服务器可快速验证：

Ify⊕r1⊕r3′=H(RID)then读写器身份认证成功；

Else读写器是非法身份，服务器停止认证。

随之共享密钥S1与标签的会话密钥kT异或求得：

采用中国剩余定理从式（7）中计算x：

服务器可快速验证：

Ifx⊕r1⊕r2′=RTIDorR-1TIDthen标签身份认证成功；

Else标签是非法身份，服务器停止认证。

读写器和标签皆认证合法后，更新服务器与标签之间的共享密钥S2：

服务器计算确认字符：

ACK′包含服务器的认证信息，以便读写器和标签验证服务器的合法身份，实现更安全的双向认证。最终服务器将ACK′发送给读写器。

（5）读写器接收到ACK′后，验证：

Ifr3=[ACK′⊕H(（y)l]l为伪随机数r3的位长）then认证服务器为合法身份；

Else服务器是非法身份，停止认证。

服务器身份认证成功，读写器继续计算：

并将ACK发送给标签。

（6）标签接收到ACK后，验证：

then认证服务器为合法身份；

Else服务器是非法身份，停止认证。

服务器身份认证成功，进而更新标签的共享密钥：

协议中标签仅使用伪随机数、异或、取余和PUF等轻量级运算，符合EPC C1G2的应用标准。

4 协议的安全隐私性证明和性能分析

4.1 安全和隐私性分析

基于Vaudenay模型建立协议运行环境和具备不同能力攻击者的安全模型，证明PLLM协议的安全性和隐私性。使用定理1和定理2证明PLLM协议满足前向不可追踪性和后向不可追踪性，保护标签的位置隐私。使用定理3、定理4和定理5证明协议可抵御攻击者的假冒攻击和去同步化攻击。

定理1在Narrow-Strong的攻击者能力模型下，PLLM协议满足前向不可追踪性。

证明Narrow-Strong的攻击者通过入侵和监听标签的第i次会话，得到标签第i次会话的内部信息和会话记录，攻击者持续监听标签的第i+1次会话记录，攻击者无法依此推断出第i+1次标签的内部信息和输出信息。由满足前向不可追踪性的算法流程图2所示，从以下四方面考虑攻击者实现前向追踪的可能性。

（1）标签的输出信息和密钥更新都需要计算x值，攻击者求解第i+1次会话中标签的xi+1值：

Fig.2 Proof flow of forward untraceable图2 满足前向不可追踪性的证明流程图

由式（25）可知，攻击者查询Corrupt预言机获得第i次会话标签内部信息[H(TID),Si2,n,a,b,c]，并通过监听第i+1次标签会话获得r1i+1。由于皆为128位随机数，且在第i次认证后通过伪随机函数更新，使得。因此攻击者成功模拟求得xi+1值的概率为：

（2）攻击者利用监听到的第i+1次标签输出信息(x″)i+1反向求解xi+1的值：

由式（27）可知，攻击者入侵第i次会话标签获得内部信息n，协议的安全性取决于基于大整数n的素数分解问题[14]。攻击者在缺少p、q私钥的情况下无法分解n，因此攻击者无法求解(x′)i+1和xi+1。

（3）攻击者监听标签会话记录，求解第i+1次确认字符ACKi+1：

由式（28）可知，攻击者入侵标签获得内部信息H(TID)并监听得到第i+1次会话记录ri+11。攻击者求解ACKi+1需要计算PRNG(xi+1⊕(x′)i+1)，由式（27）可知攻击者无法求解xi+1和(x′)i+1，因此攻击者无法追踪标签的确认字符ACKi+1。

（4）攻击者求解第i+1次标签的会话密钥：

攻击者在第i次会话入侵标签获得标签参数a、b、c，协议中标签的会话密钥Ki+1T通过两步PUF函数生成，且在每步PUF计算后删除内存中的运行参数。攻击者求解Ki+1T需要两次物理入侵标签，分别获得PUF函数输出值P(a)和P(b)。由于PUF函数的防篡改性，攻击者的物理入侵将破坏PUF的结构从而无法再次生成PUF[6]，攻击者仅能获得P(a)或P(b)。攻击者通过数学模拟PUF电路输出和ri+12值从而成功计算标签输出Ki+1T的概率为：

定理2在Narrow-Strong的攻击者能力模型下，PLLM协议满足后向不可追踪性。

证明Narrow-Strong的攻击者在标签的第i次会话入侵标签，得到标签内部信息和会话记录。由后向不可追踪性的证明流程图3可知，攻击者无法推断第i-1次标签密钥xi-1和输出信息[(x″)i-1,Ki-1T,ACKi-1],因此无法对后向会话中的特定标签进行区分，攻击者后向追踪的优势AdvABackward-untra＜＜ε,协议满足后向不可追踪性。

Fig.3 Proof flow of backward untraceable图3 满足后向不可追踪性的证明流程图

综上，攻击者无法求解标签第i+1次会话的xi+1,

定理3Narrow-Destructive的攻击者能力模型下，PLLM协议可抵御攻击者对标签的假冒攻击。

证明Narrow-Destructive的攻击者假冒标签的响应[x″,kT]，服务器不会将攻击者识别为合法标签，从而抵御攻击者对标签的假冒攻击。

由定理1可知，攻击者无法正向计算x值，进而无法计算x″。按照以下两方面分析攻击者成功计算kT的可能性。

（1）攻击者入侵标签，获得标签内部信息。

由式（32）可知，攻击者计算kT需要模拟P(a)和P(b)且需要得到r2。PUF函数依据电路在制造过程中工艺偏差，每块PUF电路产生的响应序列具有唯一性和不可复制性，攻击者无法通过数学运算模拟P(a)和P(b)。且攻击者对标签的物理入侵将对标签的PUF电路造成不可逆的损坏，导致PUF电路失活，使得PUF(x)′≠PUF(x)[15]。因此攻击者对标签的入侵无法获得kT的全部参数，攻击者无法成功计算kT。

（2）攻击者监听无线信道的会话记录以假冒标签。

攻击者查询标签和读写器之间的会话记录，并利用标签的真实响应来假冒合法标签与服务器交互。由于标签在每次身份认证完毕都会更新标签密钥S2，使得。因此，攻击者无法利用标签的历史响应完成身份认证。综上，PLLM协议可以抵御Narrow-Destructive的攻击者对标签的假冒攻击。

定理4在Narrow-Destructive的攻击者能力模型下，PLLM协议可以抵御攻击者对读写器的假冒攻击。

证明Narrow-Destructive的攻击者假冒读写器的响应[x″,kT,r1,y″,kR]，服务器不会将攻击者识别为合法读写器，从而抵御攻击者对读写器的假冒攻击。

读写器与服务器之间的会话信息不在无线射频信道上传输，攻击者无法窃听读写器的响应，只能通过入侵读写器的方式假冒读写器。攻击者入侵读写器可以获得读写器信息[H(RID),m,d,e,f]。攻击者为了假冒读写器需要计算读写器会话密钥kR：

由定理3可知，攻击者无法通过数学运算模拟PUF输出P(d)和P(e)，从而无法计算kR。PLLM协议可以抵御Narrow-Destructive的攻击者对读写器的假冒攻击。

定理5在Narrow-Destructive的攻击者能力模型下，PLLM协议可以抵御攻击者的去同步攻击。

证明攻击者无法通过阻塞信道或伪造确认字符ACK的方式，导致服务器与标签之间的共享秘钥S2不同步。从以下两方面考虑攻击者的去同步攻击：

（1）攻击者阻塞读写器与标签之间的信道。

由于标签接收不到读写器发送的确认字符ACK，导致标签更新共享秘钥S2失败。标签在下次认证过程中依旧使用先前未更新密钥S-12。但PLLM协议中，服务器同时存储S2和S-12，依旧可以实现对合法标签的身份认证。

（2）攻击者伪造确认字符ACK并发送给标签。

攻击者通过伪造ACK的方式，使得标签更新共享密钥S2，从而导致服务器永久性地拒绝标签的认证请求。由定理1可知，攻击者无法求解伪造ACK所需的x和x′，因此标签计算ACK=H(TID)⊕r1⊕PRNG(x⊕x′)无法验证通过，从而标签不会更新密钥S2。综上，PLLM协议可以抵御攻击者的去同步攻击。

4.2 性能分析

PLLM协议与现有文献[2,4-5,8]的安全性能对比如表3所示。

Table 3 Security performance comparison of protocols表3 协议安全性能对比

文献[2]采用RSA的非对称加密算法实现标签的前向和后向不可追踪性，但加密算法运算压力大不适用低成本标签。文献[4]的标签端仅使用伪随机数、交叉、异或等轻量级运算，攻击者通过窃听无线信道上的会话记录获得NR和TID⊕NR，攻击者利用计算得到的标识符TID假冒标签，并可对前向和后向会话中标签状态进行追踪。文献[8]采用二次剩余定律保护标签输出信息，避免攻击者的追踪，但攻击者可以通过物理入侵的方式获得标签和读写器密钥而发起假冒攻击。文献[5]通过物理不可克隆函数生成标签密钥，可有效地抵御攻击者对标签的物理入侵，但协议中标签涉及大量哈希运算，且未考虑读写器与服务器之间的信道安全问题，缺少服务器对读写器身份的合法性认证，不适用于移动RFID认证环境。PLLM协议通过两步PUF运算保护标签密钥的随机数，解决了标签密钥更新过程中的随机数易被攻击者窃取的问题，可成功地抵御攻击者的假冒攻击，协议满足前向和后向不可追踪性，标签仅使用伪随机数、异或、取余和PUF等轻量级运算，适用于EPC C1G2标准。

Table 4 Computation costs of protocols表4 协议开销对比

Fig.4 Search time comparison of indexing target tag图4 搜索特定位置标签的耗时对比

计算开销部分只对比运算成本较大的随机数、伪随机数、求余运算、哈希、PUF运算和交叉运算，PLLM协议与现有文献[2,4-5,8]在计算开销和后台搜索开销的对比如表4所示。文献[2,5]的标签需进行哈希运算，不适用于低成本标签。文献[4,8]中标签仅使用伪随机数、求余和交叉等轻量级运算。PLLM协议相较文献[8]标签端的运算量略有提升，标签需生成3次伪随机数、2次求余运算和2次PUF运算，但PUF函数保护了标签密钥，有效地抵御假冒攻击，协议实现了更高的安全性。

协议的各项性能指标中，服务器的搜索开销决定协议是否适用于大规模RFID系统。对服务器搜索特定标签消耗的时间进行仿真实验。实验通过PC机（CPU：Intel-2520M 2.5 GHz×2，RAM：8 GB）来模拟后台服务器，仿真环境使用Matlab。在数据库中设定6×103个标签，分别对第1×103个、2×103个、3×103个、6×103个特定标签进行搜索耗时的仿真实验，来测试不同协议中服务器从接收到特定标签的认证请求到识别成功的时间[16]。由于计算机的每次运行存在细小差异，故采用测试10次求取均值的方法作为比较结果。协议搜索耗时对比如图4所示。

文献[2,4-5]中服务器对标签身份的认证需要遍历整个服务器，对数据库中特定位置的标签的搜索耗时呈线性增长，第6×103个标签的搜索耗时分别为1.274 4 s、0.786 7 s和1.912 5 s，无法满足大规模RFID系统对标签快速认证的应用要求。文献[8]中服务器根据中国剩余定理解得随机数u的模平方根(u1,u2,u3,u4)和随机数t的模平方根(t1,t2,t3,t4),故最坏情况下，服务器需要匹配16次才可成功认证读写器和标签身份。PLLM协议中，服务器通过标签会话密钥与共享密钥的异或运算得到随机数，从而直接计算读写器和标签的标识符，实现身份的快速认证，服务器的搜索压力最低。

在RFID系统的实际应用中，服务器对伪造标签的快速识别能力是决定RFID系统性能的另一个重要指标。攻击者伪造标签标识符参与认证过程，现有协议中服务器对伪造标签的识别通常需要遍历整个后台数据库，这将造成服务器巨大的资源浪费并一定程度延迟合法标签的认证时间，且大量伪造标签对服务器发起认证请求将导致RFID系统无法正常工作。采用与上述实验相同的仿真参数，数据库中设定6×103标签，测试不同协议中服务器对伪造标签的识别耗时，如图5所示。PLLM协议相较文献[2,4-5,8]的搜索耗时分别减少99.09%、90.6%、99.4%和91.3%，PLLM协议拒绝伪标签的性能优势明显。

5 结束语

Fig.5 Search time comparison of indexing counterfeit tag图5 识别伪标签的搜索耗时对比

本文设计了适用于供应链商品管理的RFID移动认证协议，PLLM协议使用伪随机数、求余、PUF等轻量级运算，符合EPC C1G2的应用标准。协议采用PUF作为密钥生成机制，在有效抵御攻击者假冒攻击的同时可实现商品的防伪保护。基于Vaudenay模型，理论证明PLLM协议满足前向和后向不可追踪性，能够有效保护移动RFID认证环境下标签的位置隐私，防止攻击者对供应链中商品的位置跟踪。相较现有文献[2,4-5,8]，PLLM协议具有最高的安全性、最快的后台服务器搜索效率和更快的拒绝伪标签的效率。同时，由于PUF函数的输出极易遭受环境变量的影响，导致认证结果不稳定。在低成本标签有限的安全电路基础上设计高效且可靠的模糊提取器，以提高PUF输出的鲁棒性是今后的研究重点。