无后端数据库的RFID安全认证协议的改进方案*

王 萍，周治平，李 静

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

1 引言

随着物联网的快速发展，作为物联网感知层的关键技术，射频识别（radio frequency identification，RFID）以其非接触式自动识别[1]的优势被广泛应用于医疗[2]等领域。为保证RFID系统的安全和隐私，实现双向认证是关键[3]。传统RFID系统的基本结构由标签、读写器和后端数据库组成。读写器将接收到的标签信息转发到后端数据库，由后端数据库进行验证。大部分情况下，读写器须通过有线的方式与后端数据库相连，无法适用于移动RFID环境，因此无后端数据库的RFID认证协议相继被研究者提出。文献[4]首先提出无后端数据库的RFID认证和搜索协议，通过安全性分析发现，该协议只满足单向身份验证，易遭受读写器假冒等攻击。文献[5]在文献[4]基础上提出无后端数据库的标签搜索协议，与认证协议类似，该类协议在实现阅读器和标签相互认证的同时还可达到搜索标签的目的。文献[5]指出所提协议在满足EPCC1G2标准的同时，还可抵抗去同步化、重放、假冒等攻击。但随后文献[6]指出文献[5]由于盲因子构造不合理，导致协议无法抵抗重放、去同步化攻击，且标签密钥更新操作采用固定种子，导致位置隐私无法保证。文献[7]提出增强隐私保护的无后端数据库的RFID安全认证协议。但是文献[8]指出文献[7]所提的方案存在去同步化攻击，并在此基础上进行改进以解决去同步化攻击。经分析，文献[8]未能解决去同步化攻击问题，且文献[7-8]均无法保证位置隐私。文献[9]提出基于Hash函数的无后端数据库RFID安全认证协议，该方案具有较强的安全属性。通过分析可知，以上方案读写器均采用遍历方式搜索标签，其时间复杂度为O(N)，不适用于大规模环境[10]。为了降低搜索标签复杂度，基于树的认证协议[11]被提出，其搜索时间复杂度为O(logαN)，其中α表示分支数，N表示标签总数。树型结构虽然降低了搜索时间复杂度，但是标签一旦被攻击者腐化获得内部信息，就会导致其他标签的密钥信息被暴露。文献[12]采用标签共享主密钥的方式来提高协议的搜索效率，这种方式可保证常数时间的认证，即搜索复杂度为O(1)[13]，另外该方案采用物理不可克隆函数来保证安全性。但经分析可知，一旦标签主密钥被攻击者破解，文献[12]所提安全性将无法保证，且物理不可克隆函数的输出结果会随着操作环境的变化而发生波动，因此大规模采用物理不可克隆函数仍是不现实的[5]。文献[14]提出在大规模RFID系统中采用组认证方式以验证合法标签，该方案有效保证了标签匿名性且降低了搜索复杂度。文献[15]采用分组匿名认证的方式在降低搜索复杂度的同时保证标签的不可链接性，但协议由于缺少密钥更新操作，导致位置隐私无法保证。

通过分析发现，无后端数据库的RFID安全认证协议主要存在以下几点问题：（1）搜索时间复杂度高，为保护隐私安全，标签需将密钥加密后发送给读写器，读写器则通过将所有标签的密钥与消息进行匹配以验证标签合法性。因此，验证标签的时间代价与标签数量呈线性关系，严重影响RFID系统的效率。（2）位置隐私难以保证，攻击者通过腐化标签获得标签的密钥信息后重新将标签放入流通，通过腐化的密钥信息跟踪标签。（3）无法抵制常见的攻击，如去同步化攻击、重放攻击等。基于此，本文将采用组身份标识共享技术来提高文献[8]的搜索效率，另外改进文献[8]中读写器更新密钥的方式，并在密钥更新操作中引入随机数，以解决去同步化攻击并保证位置隐私。

2 相关工作

2.1 安全模型

2.1.1 隐私模型

Ouafi和Phan在文献[16]中提出了一个形式化的隐私模型，本文将采用该隐私模型对协议进行安全性分析。攻击者A可以访问以下几个预言机。

（1）Execute query(R,T,i)预言机：该预言机模拟攻击者侦听通信消息的能力。预言机将返回标签T和阅读器R在第i轮认证过程中的所有交互消息。

（2）Send query(U,V,m,i)预言机：该预言机模拟攻击者假冒合法阅读器或标签进行交互的能力。即攻击者A在第i轮认证过程中假冒标签U∈T向阅读器V∈R发送消息m，并收到阅读器的响应m′。

（3）Corrupt query(T,k)预言机：该预言机模拟攻击者访问标签T内部存储数据，预言机将返回标签的密钥和状态信息。

（4）Test query(T0,T1,i)预言机：该预言机执行第i轮认证实例后，挑战者随机输出一个比特位b∈{0,1}，并令Tb∈{T0,T1}，传递给攻击者。若攻击者能够正确猜出随机位b值，则攻击者获胜。

定义1（位置隐私）假设敌手通过调用预言机Corrupt query(T,k)腐化得到目标标签第l次的密钥和内部状态，再对第l+1次会话进行分析，无法推知目标标签第l+1次的密钥和输出信息。

2.1.2 攻击者模型及安全假设

本文假设阅读器与标签之间的信道为不安全信道。攻击者可窃听、篡改、拦截标签与阅读器之间的通信消息，并且可以主动向标签和阅读器发起会话。对于位置隐私，攻击者可调用以上所有预言机。而对于去同步化攻击、重放攻击，攻击者无调用Corrupt query(T,k)和Test query(T0,T1,i)预言机的能力，即攻击者无法获取标签内部信息。最后本文假设敌手无法获取阅读器内部信息（密钥等）。

2.2 Deng等人方案的隐患分析

本文通过分析发现Deng等人[8]所提的方案在两次通信交互后存在去同步化攻击问题，并且该方案无法保证位置隐私。此外，文献[8]中读写器搜索时间复杂度为O(N)，不适用于大规模的RFID环境。具体分析如下。

（1）去同步化攻击

初始化阶段，读写器Ri在数据库中存储标签Tj的数据目录(SeedTj,SeedPTj,idTj)，其中SeedTj为标签Tj当前的密钥种子，SeedPTj为标签Tj的前一轮的密钥种子，idTj为标签Tj的身份标识符，且初始时刻SeedTj=SeedPTj。为方便简述，令SeedTj=SeedPTj=a。

假设读写器Ri和标签Tj成功执行一次交互后，读写器Ri更新标签Tj的密钥种子为SeedTj=b，且标签Tj也更新自身的密钥种子，即Seed=b。在第二轮交互时，读写器Ri成功更新密钥种子SeedTj=c，且将加密消息反馈给标签Tj，这时攻击者拦截消息使标签Tj不更新自身的密钥种子，从而使读写器存储的标签Tj两轮密钥种子与标签Tj存储的密钥种子不一致，达到去同步化攻击目的。

（2）位置隐私

学习阶段：在第l轮交互过程中，攻击者A调用预言机Corrupt query(T0,k)获得标签T0内部信息攻击者A可以根据获得的密钥信息计算T0在第l+1轮的密钥

挑战阶段：攻击者随机挑选两个新鲜的标签T0和T1作为测试对象，并调用预言机Test query(T0,T1,l+1)。攻击者 A随机选择一个比特位b∈{0,1}，并令Tb∈{T0,T1}。攻击者 A调用预言机 Execute query(R,Tb,l+1)获得实体间的通信消息

猜测阶段：攻击者A停止游戏G，并输出一比特位b′∈{0,1}作为对比特位b的猜测，即：

显而易见，可以得出：

证明若Tb=T0，则：

Deng等人[8]方案的密钥更新方式为仅对初始密钥进行哈希运算，即 Seed=M(M(Seed))，其中 M(⋅)表示单向散列Hash函数。一旦标签Tj被攻击者腐化获得内部信息Seed，则攻击者获得此后每轮密钥种子的概率为1，且攻击者A通过侦听读写器与标签间交互的随机数可计算出表示伪随机函数，因此攻击者 A会时刻跟踪目标标签，协议的位置隐私无法保证。□

（3）搜索时间复杂度

读写器接收到标签的应答消息后，采用伪随机函数遍历匹配的方式验证标签的合法性，其搜索时间复杂度为O(N)，其中N表示标签的总数。因此，随着存储标签数量的增加，读写器搜索时间也随之线性上升。

2.3 改进协议描述

与Deng等人[8]所提方案类似，改进协议包含两个阶段：初始化阶段和认证阶段。

初始化阶段：读写器和标签存储认证过程中所需的相关信息。与Deng等人[8]所提方案不同之处在于：改进协议将N个标签分为τ组，每组包含n=N/τ个子标签。标签存储所在组的身份标识IDGi以及自身密钥SeedTj，读写器存储自身标识IDi，τ个不同的组身份标识IDGi以及各标签前后两轮密钥SeedTj。

认证阶段：改进协议认证过程如图1所示，具体过程如下。

（1）Ri→Tj：读写器 Ri生成随机数 randi，并向标签Tj发送查询命令request以及randi。

（2）Tj→Ri：Tj接收到 Ri的消息后生成随机数randj，计 算 aj=P(IDGi⊕(randj||randi))，nj=P(SeedTj⊕(randi||randj))，将 ＜aj,nj,randj＞ 作为响应消息发送给 Ri。

（3）Ri→Tj：Ri接收到Tj的消息后，首先在数据目录中寻找IDGi使得 aq=P(IDGq⊕(randj||randi))，其中q∈{1,2,…,τ}。若 aq=aj，则表示特定标签 Tj属于第q组标签。Ri继续在第q组标签的数据目录中寻找SeedTj

，计算 nm=P(SeedTm⊕(randi||randj))，其中 m∈{1,2,…,n}。当nm==nj时，则标签通过认证，读写器更新密钥：SeedPTj=SeedTj,SeedTj=M(SeedTj⊕(randj||randi))。Ri更新完密钥后计算s=M(SeedTj⊕randj),ni=P(s)；若nm≠nj，Ri在第q组标签的数据目录中寻找SeedPTm，计算 nm=P(SeedPTm⊕(randi||randj))，其中 m ∈ {1,2,…,n}。当nm==nj时，则标签通过认证，读写器更新密钥：SeedTj=M(SeedPTj⊕(randj||randi))。 Ri更新完密钥后计算 s=M(SeedPTj⊕randj),ni=P(s)。最后 Ri将消息ni发送给Tj。

Fig.1 Authentication process of improved protocol图1 改进协议的认证过程

（4）Tj：Tj接收到 Ri的消息后计算 k=M(SeedTj)，b=P(k)。若b==ni，则读写器通过认证，标签更新自身密钥：SeedTj=M(SeedTj⊕(randj||randi))；否则，终止协议且不更新密钥。

3 安全性分析

3.1 GNY逻辑分析

此处用T表示标签，R表示读写器。在证明之前需要先将协议消息进行形式化，并确定要证明的目标，同时对已知的信息进行初始假设。具体证明过程如下。

（1）协议形式化

（2）协议目标

①读写器对标签的认证

②标签对读写器的认证

（3）假设条件

（4）GNY逻辑证明

证明①：R|≡ T～#P(IDGi⊕(randj||randi))，R|≡ T～#P(SeedTj⊕(randj||randi))

由M1:R⊲randj和规则P1：可得：

证明②：T|≡ R|～#P(s)

由规则F1和假设条件A5:T|≡#randj可得：

由规则P2和假设条件A1:T∍IDGi,SeedTj可得：

再由规则F10和式（9）、（10）可得：

继而再由规则F10，令s=M(SeedTj⊕randj)可得：

3.2 理论分析

此处采用第2章介绍的安全模型对改进协议安全性进行分析。

（1）抵制重放攻击

改进方案中读写器和标签端产生不同的随机数且采用伪随机数函数进行加密，保证通信消息的新鲜性。假设攻击者重放消息＜aj,nj,randj＞给读写器，由于每轮交互过程的通信消息aj=P(IDGi⊕(randj||randi))，nj=P(SeedTj⊕(randi||randj))中含有随机数randi、randj，故重放消息将无法通过读写器的认证。同理，攻击者重放消息ni无法通过标签的认证。

（2）双向认证

对读写器而言，读写器首先验证特定标签属于哪一组标签，即验证aq=?P(IDGi⊕(randj||randi))。若相等，则读写器认为特定标签属于该组，且继续验证nm=?P(SeedTj⊕(randi||randj))。若相等，则读写器视特定标签为合法标签，并更新该标签的密钥。对标签而言，标签收到读写器的消息后验证ni=?P(M(SeedTj))。若相等，则标签视其为合法读写器，并更新密钥。这种方式实现了标签和读写器之间的双向认证，不仅有效防止攻击者假冒合法标签的行为，而且又能避免攻击者假冒授权读写器对合法标签进行恶意跟踪。

（3）位置隐私

学习阶段：攻击者A调用预言机Corrupt query(T0,k)获得标签T0第l轮的内部信息

挑战阶段：攻击者随机挑选两个新鲜的标签T0和T1作为测试对象，并调用预言机Test query(T0,T1,l+1)。攻击者A随机选择一个比特位b∈{0,1}，并令Tb∈{T0,T1}。攻击者A调用预言机Execute query(R,Tb,l+1)获得实体间的通信消息

猜测阶段：攻击者A停止游戏G，并输出一比特位b′∈{0,1}作为对比特位b的猜测，即：

由此可得出，攻击者获取标签位置隐私的优势为：

证明在学习阶段,攻击者通过调用Corrupt query(T0,k)预言机获取标签T0第l轮的内部信息由于同组标签的组标识相同，攻击者无法通过对比消息来跟踪标签。攻击者若要成功跟踪目标标签T0，则必须计算出与原协议不同，本文在密钥更新操作中引入读写器和标签的随机数randi、randj与初始密钥异或后再进行哈希加密，从而保证更新密钥的随机性和新鲜性，即使攻击者获取密钥，仍无法得到，也就无法通过对比和确定b值，攻击者成功猜测b值的概率为，即改进协议能够保护位置隐私。 □

（4）抵制去同步化攻击

改进方案中，读写器存储上一轮和当前的密钥信息，并且判断接收到的标签消息由哪一轮的密钥计算获得。若由上一轮的密钥通过加密操作获得，则只更新并存储当前的密钥，即SeedTj=M(SeedPTj⊕(randj||randi))；若由当前的密钥通过加密操作获得，则更新并存储两轮的密钥，即SeedPTj=SeedTj，SeedTj=M(SeedTj⊕(randj||randi))，即使攻击者通过拦截消息使标签密钥未更新，阅读器仍能完成对标签的认证。另外，攻击者不能通过改变randi、randj值的方式导致读写器和标签更新密钥值不同，从而达到去同步化目的，一旦randi和randj的值被篡改，则将导致认证不成功，协议终止，密钥将不会更新。综上所述，改进协议可抵抗去同步化攻击。

改进协议与现有典型协议[5,7-8,12,15]的安全性比较如表1所示。其中×表示不安全；√表示安全。由表1可知，仅文献[12]和改进协议满足所有安全属性，但文献[12]由于物理不可克隆函数的输出随着操作环境变化而波动的性质，导致该方案实用性较差，且该方案的安全性完全取决于主密钥，一旦标签主密钥某时刻被攻击者破解，该方案的安全性将难以保证。

Table 1 Security comparison of protocols表1 协议的安全性对比

4 仿真结果分析

4.1 搜索时间对比

此部分主要对现有协议[5,7-9,12,14]和改进方案在搜索时间上进行对比。本文仿真环境为Intel Core i3-2.10 GHz，RAM-6 GB；由于每次运行时间有细微差异，故测试30次取平均值，伪随机函数（PRNG）耗时约为0.021 ms，哈希函数（Hash）耗时0.25 ms。为便于分析，本节对比最坏情况下读写器搜索特定标签所需的时间。另外将文献[14]与改进方案中N个标签分为τ=2组标签，每组有N τ个标签，考虑最坏情况下特定标签处于第2组最后位置的情况。如图2所示，文献[5,7-9,14]与改进方案中读写器搜索耗时均随着标签数量的增加而上升，但是改进方案的读写器搜索耗时的上升趋势较文献[5,7-9,14]方案更为平缓，因此改进方案通过采用组标识共享技术实现了更高的搜索效率；采用哈希遍历匹配[9]方式的搜索耗时增长最快；而采用共享主密钥[12]方式的搜索耗时为常数且最低，但在大规模环境下应用物理不可克隆函数仍是一个亟待解决的问题，且该方案在主密钥被破解情况下，其所有安全性将无法得到保证；文献[5,7-8]均采用伪随机函数遍历匹配，故搜索耗时相同；文献[14]与改进方案虽然都采用分组的思想，但是文献[14]采用单向Hash函数匹配标签传输的消息，故搜索时间较改进方案高。

Fig.2 Comparison of reader search time-consuming图2 读写器搜索耗时对比

4.2 分组对搜索时间的影响

改进方案中，当标签数量N一定时，分组数的变化会导致读写器搜索特定标签的时间随之变化。如图3所示，当N=10 000，N=100 000，N=200 000时，其搜索时间曲线的变化趋势都是先下降，达到最小值之后再上升，这是由于读写器搜索标签耗时与τ+N/τ相关联。当N=10 000，τ=100时，读写器搜索时间最少，为4.2 ms；当N=100 000，τ=316时，读写器搜索耗时最少，为13.281 6 ms；当N=200 000，τ=447时，读写器搜索耗时最少，为18.783 ms。为了使读写器搜索耗时最少，则且1≤τ≤N，分析可得，当τ=N时，t取最小值。但是分组数τ为整数，因此τ=ceil(N)时，读写器搜索耗时最少。由图3可得，当τ一定时，读写器搜索特定标签所需耗时随着标签数量的增长而增加，当N一定时，读写器搜索特定标签耗时随着分组数的增加首先呈下降趋势，达到最小值后又呈上升趋势。因此，在改进协议中，需根据标签的总数确定分组数，从而使读写器在最坏情况下搜索特定标签的耗时最少，以达到最高的搜索效率。

Fig.3 Effect of the number of packets on reader search time图3 分组数对读写器搜索时间的影响

4.3 通信时间对比

为了更加充分地说明本文采用的组标识共享技术在RFID系统效率上比原方案[8]的遍历匹配方式有大幅的提升，此处将改进方案与哈希计算遍历匹配[9]及伪随机函数遍历匹配[8]进行通信时间的对比。本文通过调用Java中的socket接口模拟读写器与标签间的通信，利用System.nanoTime()函数计算一轮成功交互所需的时间。读写器的数据库中存储1×104个标签，其中改进方案中将1×104个标签分成100组，每组含有100个标签。分别将目标标签存储于数据库链表的第1个、第500个、第501个、第1 000个、第1 001个、第5 000个、第5 001个、第10 000个位置，测试一轮成功交互通信所需的时间。由于每次运行时间有细微差异，故测试10次取平均值，如表2所示。文献[8-9]的通信时间随着目标标签所在数据库位置的增长而呈线性上升趋势，这是由于读写器需要遍历搜索数据库存储链表以检索目标标签，且文献[9]由于采用哈希计算遍历匹配，故通信耗时比文献[8]的伪随机函数遍历匹配高。而改进方案将一群标签分组，通过组身份标识降低读写器搜索范围，因此改进方案的通信效率与哈希及伪随机函数遍历匹配相比都有大幅提升。由于第500和501个分别处于第5组的最后位置和第6组的首位，故标签处于数据库第501个位置的通信时间较第500个位置低，其他同理。与原方案相比,改进方案通信时间更低，实用性更佳。

Table 2 Comparison of protocol communication time表2 协议通信时间对比

5 结束语

本文首先分析了Deng等人所提协议存在的去同步化攻击、位置隐私无法保证以及阅读器搜索时间复杂度高的问题，然后在此基础上提出了一种改进的无后端服务器的RFID认证协议。改进方案完善了原协议在阅读器成功验证标签后更新共享密钥的方式，并将阅读器和标签产生的随机数种子作为哈希函数的输入参数更新密钥。通过安全性分析可知，改进方案能够保证读写器和标签共享密钥的同步更新，且保证了标签的位置隐私。另外，改进方案采用组身份标识共享技术有效提高了读写器搜索效率。通过实验仿真可知,随着数据库存储标签数量的增加，本文方案的读写器搜索耗时和通信耗时的增长趋势较其他协议更为平缓，具有良好的可扩展性和实用性。另外，本文还通过实验模拟了分组数对读写器搜索时间的影响，以便实现更低的搜索耗时。