一种改进的高效RFID加密安全协议

刘 念1，殷 业1，叶 龙2，肖 龙1，严 实1

(1.上海师范大学信息与机电工程学院，上海 200234；2.上海商学院信息与计算机学院，上海 201400)

1 概述

无线射频识别(Radio Frequency Identification,RFID)是利用射频信号来自动识别目标对象，并获取其相关信息的一种非接触式无线通信自动识别技术[1]。RFID在无线通信中有着广泛应用的同时，在其无线信道中的标签信息安全问题也存在很大的隐患[2]。针对RFID无线通信中的安全问题，国内外开展了很多的安全保密研究[3]，如Hash-Lock协议、Hash-Chain协议、树形协议等，但这些加密安全协议在一定程度上都存在一些缺陷，本文针对这些协议的不足之处，结合密集环境下的目标识别问题，提出一个新的RFID加密安全协议，旨在提高低成本标签的安全性，以及系统识别标签的效率。

2 RFID中的安全问题

在实际应用环境中，RFID系统的阅读器与后台信息系统之间通过互联网或局域网相连接，标签与阅读器之间则通过无线信道进行通信。一般认为阅读器和后台信息系统之间的信道为安全信道，阅读器与标签之间的信道为不安全信道，即其间发送的数据是易被攻击者窃听或篡改的。没有可靠的信息安全机制，就无法有效地保护射频标签中的数据信息[4]。

RFID系统面临的安全问题主要是数据的隐匿性、完整性、真实性和用户隐私泄露问题，另一方面，标签的成本会直接影响RFID的安全性能，要有可靠的信息安全机制，才能够实现对低成本标签安全威胁的高效防护[5]。一个好的安全协议要能够实现在重放攻击、跟踪攻击、假冒复制攻击、信息篡改攻击、插入攻击等中有足够的抗攻击能力，能够保证信息的认证性、秘密性以及完整性，并且在信息处理复杂度上做到最优[6]。

3 常见的安全协议

3.1 Hash-Lock协议

文献[7]提出了Hash-Lock协议，利用Hash(ID)加密来代替真实的标签ID以避免信息泄露和被跟踪。Hash-Lock协议如图1所示。

图1 Hash-Lock协议

在该协议中，标签T将自身信息ID进行Hash函数加密，将H(ID)信息发送给阅读器R，后台信息管理系统DB顺次搜索到与该H(ID)匹配的（H（IDi）,K eyi,IDi）信息，从而完成验证。Hash-Lock协议可以有效地进行标签隐私保护，攻击者无法根据在通信过程中劫取的H(ID)信息破译出标签中的ID信息[8]。但标签的H(ID)信息保持不变，信息易被跟踪定位，攻击者可以很容易复制相同的标签对阅读器进行重放攻击，造成后台信息系统的运算量加大，造成信道拥堵[9]。

3.2 Hash-Chain协议

相对于Hash-Lock协议的缺陷，Hash-Chain协议是基于共享秘密的询问-应答协议[10]，保证了前向通道的安全。Hash-Chain协议如图2所示。

图2 Hash-Chain协议

在Hash-Chain协议中，标签利用2个Hash函数H和G，一方面对标签的ID信息进行 G（St,j）加密，另一方面对密值St,j更新为H（St,j）。该协议延续了Hash-Lock协议中的单向通道安全性，同时通过对St,j的随机更新，使得即使攻击者截获标签信息，也不能够进行位置跟踪和重放攻击[11]。但该协议同时运用2个Hash函数，当标签数量较大时，会加大后台信息系统的运算量和执行效率[12]。

3.3 SPA协议

文献[13]提出依靠树结构来减少安全协议中认证的复杂度。所有的标签分布在一棵度为k的平衡树的叶子节点上，树的深度为logkN，树的每条边的值为一个随机值ki,j，其中，i是目标在树中的层数；j是分支数。支节点路径可以唯一确定一个标签，这组值是标签的ID组值。k度树结构如图3所示。

图3 k度树结构

在该协议中，标签将树路径上的所有序列值经过加密后发送，后台信息系统接收到信息后，根据信息从根节点到支节点一层层进行验证，以确定标签在哪个分枝中。采用这种方法，在树中的第i层，系统只需要在k个秘密值中查找是否有一个与标签的秘密组中的第i个密码值相同的密值，时间复杂度降低为O（lo g n），可以很大程度上提高后台信息系统的运行速率。然而，又因为树结构的分支特性，攻击者可以容易地跟踪其他与这个标签共享部分密值的标签[14]。

4 改进的高效RFID安全协议

在上文介绍的RFID安全协议中，利用Hash函数的特性，对原有明文数据的任何篡改或替换都会得到一个不同的结果，是采用基于共享密钥的询问-应答的方式来增加RFID系统的安全，虽然这些协议能保证安全需求，但是使得RFID系统时间复杂度太大，不适合在大规模的RFID系统中应用。基于树的RFID安全协议通过构造一颗树结构的密码树来提高在大规模RFID系统中后台信息系统搜索的效率，但由于任何2个标签间至少共享了一个密码值，使得这类协议有明显的安全漏洞，很容易因为一个标签的信息泄漏而使其他标签被跟踪。

基于以上安全协议所面临的问题，本文在散列Hash函数安全协议的基础上，对其进行改进，融合二分搜索法和循环冗余校验(Cyclic Redundancy Check,CRC)法，实现了RFID安全通信的同时，降低协议执行的时间复杂度，使得在安全性质、抗攻击能力、低成本、执行速率等方面获得更大的综合优势。

4.1 数学原理

假定n≥1个有序整数存储在数组list中，list[0]≤list[1]≤list[2]≤…≤list[n–1]。查找searchnum是否出现在这个表中，若存在，则返回searchnum=list[i]，否则返回–1。

对于有序查找法，将searchnum与list[i]依次从前往后进行比较，直到找到使得searchnum=list[i]的i值为止。while语句每次循环耗时 O（1），利用这种方法，后台数据库的运算时间复杂度为O（n）。

利用二分搜索法，令left，right分别表示表中待查范围的左右两端点，标签数为n，初值left=0，right=n–1。令middle=(left+right)/2，每次搜索时，将searchnum与list[middle]进行对比，每次对比，将数组长度减为原来的一半，再进行依次循环，直到找到使searchnum=list[middle]的middle值，并返回。利用二分搜索法，while语句每循环一次，待查的表长度会减少一半，这种情况下算法的时间复杂度降低为O（lo g n），会大大减少后台信息系统的运算量，降低工作量，提高搜寻效率。

可以看出，二分搜索法可以有效降低系统的运算量，实现快速识别，同时，结合Hash函数的安全特性，可以防止标签的跟踪攻击。

4.2 循环冗余校验法

循环冗余校验码是一种从数据本身出发，依靠数学上约定的形式来对通信数据进行检验的一种校验方法。CRC校验码可以检测到接收的数据是否发生错误，当发生错误时，接收方会通知发送方重新发送一遍数据。

发送方发送m位信息数据T(x)，接收方接收到D(x)，若T(x)=D(x)，则传输过程中没有出现错误。CRC码通过在信息数据T(x)后附加一个k位的二进制校验信息段R(x)来对信息数据进行校验。R(x)、生成多项式g(x)以及信息数据T(x)有着特定的关系，如果数据在传输中的某一位或某些位发生错误，这种特定的关系就会被破坏，因此通过检查这种特定关系就可以实现对数据正确性的检验。

在国际标准中，CRC-8校验码的生成多项式为g（x）=x8+ x5+ x4+1。通过将原信息码T(x)左移k位，然后与生成多项式g(x)作异或运算处理，得到的余数就是校验码R(x)。在接受方，则将收到的信息数据D(x)用同样的方法作逆运算，如果最终运算结果有余数存在，则说明数据T(x)在传送通道中被篡改，否则即可证明信息传送的正确性。

4.3 改进的RFID安全协议

后台管理信息系统首先利用CRC-8校验法对阅读器发送回的信息进行校验，如果存在攻击者在无线通信路径中对标签信息进行了非法篡改，CRC-8可以首先检验出错误标签，对错误标签直接返回不予处理，从而后台信息系统可以避免对错误标签的搜索，防止篡改标签的攻击，大大减少工作量。

当CRC-8校验证明标签传送正确时，后端信息系统再进行定位搜索工作。对于一般的基于Hash函数安全协议，直接从所有的标签中搜索得到目标标签，算法复杂度为O（n）。结合二分搜索法，比较searchnum与list[middle]，可以在很大程度上减少目标标签的搜索次数，迅速地找到目标标签，时间复杂度为O（lo g n），大大减少后台信息系统的工作量。当标签数量N很大时，二分搜索法的执行速度和效率更高。

融合CRC-8校验法和二分搜索法，可以有效防止信息篡改攻击，避免错误标签对后台信息系统资源的占用，降低系统搜索的时间复杂度。同时，相对于树协议搜索法，可避免标签信息之间的联接，有效防止标签位置跟踪攻击。改进的高效RFID加密安全协议的执行过程如图4所示。

图4 改进的高效RFID加密安全协议

认证过程：

(1)当数据库需要搜索某个标签时，由后台信息系统DB产生一个随机数R，发送随机数R给阅读器。

(2)阅读器随即将询问信息Query和R发送给识别范围内的标签T。

(3)T将接收到的随机数R和自身密值S1做异或运算后，再计算其Hash函数值：MetaID=H（S1⊕R）。

(4)T将MetaID传送给阅读器；阅读器将MetaID发送给DB。

(5)DB利用CRC-8校验法验证MetaID，若最终逆运算结果有余数，则CRC校验错误，说明T发送出的消息在无线通道中被攻击者篡改，否则认证通过。

(6)若步骤(5)认证通过，再利用二分搜索法，在DB（H（Si⊕R）,IDi）中查找到使得 H（S1⊕R）=H（Si⊕R）的Si值。

(7)更新密值 Si'=H（Si）。

(8)计算 MetaID '=H（Si'⊕ R），DB将 MetaID'发送给阅读器，阅读器将 MetaID '发送回T。

(9)验证 MetaID '=H（S1'⊕ R）是否成立，若成立，则认证成功，更新T密值 S1'=H（S1）。

5 安全分析和性能评估

本文提出的加密安全协议结合了Hash函数单向性加密和二分搜索法。Hash函数的单向安全性可以有效保证标签信息的安全，实现标签防窃听攻击、防信息泄漏和数据隐匿性等问题，结合密钥更新，避免了标签被复制重放攻击和位置跟踪的问题。同时，利用Hash函数可以有效地减少标签的设计复杂度，保证标签的低成本设计，在实际生产中的应用价值较大。利用CRC-8校验法，防止信息在无线通道中被恶意篡改，有效避免了错误标签对后台信息处理的数据占用，减少系统验证非法标签的时间。最后，采用二分搜索法，对标签二进制信息采用折半查找，大大提高了后台信息系统搜索标签的时间复杂度，提高了后台数据库的执行效率。本文协议使得RFID标签识别在安全性、低成本、执行效率方面具有较好性能。

5.1 协议安全分析

本文提出的协议可以有效提高系统的工作效率，在大量标签聚集环境下，实现高效的目标定位功能，同时，能够保证通信过程中的安全性。

(1)降低成本。将随机数产生器放在后台信息系统，降低了标签和阅读器的设计复杂度。

(2)防非法读取。只有经过认证的阅读器才能够获取标签的信息。本文协议利用散列Hash函数的单向安全性，即使攻击者截获到通道中传送的信息，也不能够反向获得标签的信息。

(3)数据完整性。本文协议利用散列Hash函数的强碰撞特性，对原有明文数据的任何篡改或替换都会得到一个不同的结果，可以有效保证消息的完整性。

(4)防重发。后台信息系统每次访问时产生一个随机数R，使得每次认证过程中标签的输出 MetaID=H（S ⊕R）都不同。攻击者即使窃听到某一次的标签输出，也不能够在下一次认证中推测或伪装该标签造成信息重发。

(5)防信息篡改。DB利用CRC-8校验法验证MetaID，可以保证信息在传送路径中的正确性。即使攻击者在通信信道中对标签信息进行干扰，后台信息系统也可以很快地验证出该消息已被篡改，从而可以有效减少系统验证非法标签的时间，在一定程度上提高验证效率。

(6)后台信息系统的时间复杂度降低，效率提高。在每次询问过程中，信息系统中存储的标签个数为N，基于Hash函数的安全协议算法复杂度为O（n）。本文协议中采取二分搜索法，很大程度上减少目标标签的搜索次数，迅速地找到目标标签，算法复杂度为O（lo g n），减少后台数据库的工作量和资源消耗。当N很大时，本文协议的执行速度将更快和效率更高。

(7)双向认证安全性。本文协议利用MetaID来实现标签的认证，在DB搜索到目标标签后，通过 MetaID=H（S1⊕R）计算比较，实现阅读器对标签的前向通道安全认证；在反向过程中，通过 MetaID '=H（S1'⊕ R）的计算比较，实现标签对阅读器的后向通道安全认证。

(8)防位置跟踪。更新密值和随机数，攻击者即使截获多个标签密值，无法根据标签的信息来找到相关规律，也无法标签相关的历史活动信息，防止攻击者根据特定的输出进行位置跟踪。

5.2 协议运行性能评估

本文协议结合了Hash函数的单向安全性与二分搜索法的高效性，有效保证了RFID安全系统中的重传攻击、假冒复制攻击、信息篡改攻击、插入攻击、拒绝服务攻击、前向安全、标签伪造、位置跟踪等。

综合对比Hash-Lock协议、Hash-Chain协议、SPA协议和本文协议，在安全性、复杂度、通话量等各方面的性能如表1所示，N表示协议对这种信息攻击没有抗攻击能力，Y表示协议对这种信息攻击有抗攻击能力。

表1 各安全协议的安全性和时间复杂度对比

比较Hash-Lock协议和Hash-Chain协议中的直接搜索法、SPA协议的树形搜索法和本文协议中的二分搜索法，三者在时间复杂度上有明显区别。

采用直接搜索法，数据库中有N个标签，对于目标标签searchnum，最少需要1次搜索，最多需要N次搜索，所以，直接搜索法最差情形的整体复杂度为O（n）。采用树形搜索法，度为δ、树的深度为logδN，每个标签内部存储一组从根节点到叶子节点的路径密码组 ［S1,S2,…,SL］，在树的第i层，只需进行δ/2次搜索比较，即认证一个标签需要δ·L/2次搜索。可以看到，后台信息系统搜索每个标签的过程就是在树的支节点中通过分支来进行查找，使得时间复杂度降低到 O（lo g n）。本文采用二分搜索法，比较searchnum与中间值list[middle]的大小，每次查找后，待查找的表长会减少一半，最佳情况的复杂度为O（1），最差情况的循环比较次数为O（lo g n）。利用Matlab仿真，比较各算法的时间复杂度，如图5所示。

图5 不同搜索算法的时间复杂度对比

通过图5可以看出，Hash协议中直接搜索算法的时间复杂度 O（n）要远大于本文协议中二分搜索算法的时间复杂度 O（log n）。当标签数量N增大时，复杂度对比更明显，二分搜索算法会大大地减少后台信息系统的运算量，提高系统的执行效率。

6 结束语

在实现大型场地中的目标定位时，由于阅读器阅读范围内的目标标签数目过多，极易出现目标混杂和攻击者入侵的现象。在某些重要场合中，要能够准确迅速地定位到目标标签，就需要在保证信息系统执行效率的前提下，使得标签能够抵抗重放、假冒复制、位置跟踪等攻击。

由于现在常见的安全协议均不能在位置跟踪、重放攻击、信息篡改、算法复杂度等方面同时做到最优，对比这些常见的典型RFID安全协议的特性，本文提出了改进的RFID安全加密协议，结合不同安全加密协议的优势，在保证信息通道安全的情况下，可以有效地保证标签信息的动态安全性，减少信息系统识别错误标签的时间，同时降低系统搜索标签算法的时间复杂度。最后通过对协议的安全性分析以及Matlab时间复杂度的仿真，结果证明本文协议具有安全性、低成本、复杂度等方面的综合优势，解决了Hash函数安全协议的时间复杂度问题，同时解决了树结构安全协议的安全隐匿问题，是一种较实用的安全协议，在低成本密集型标签环境中具有较高的实用价值。

[1]Jeremy L.The History of RFID[J].IEEE Potentials,2005,24(4):8-11.

[2]胡国胜,龙 雄.RFID系统安全分析[J].网络安全技术与应用,2013,(2):40-44.

[3]李 磊,陈 静.物联网感知层中RFID系统安全解决方案[J].网络安全技术与应用,2011,(6):34-36.

[4]李宏年.基于Hash协议的射频识别系统安全对策[J].信息通信技术,2009,(6):16-19.

[5]Sun D Z,Zhong J D.A Hash-based RFID Security Protocol forStrong Privacy Protection[J].IEEE Transactions on Consumer Electronics,2012,58(4):1246-1252.

[6]Liu Leian,Chen Zhiqiang,Yang Ling.Research on the Security Issues of RFID-based Supply Chain[C]//Proceedings of International Conference on E-Business and E-Government.Guangzhou,China:[s.n.],2010:3267-3270.

[7]Rieback M R,Crispo B,Tanenbaum A S.The Evolution of RFID Security[J].IEEE Pervasive Computing,2006,5(1):62-69.

[8]陈瑞鑫,邹传云,黄景武.一种基于双向Hash认证的RFID安全协议[J].微计算机信息,2010,(11):149-151.

[9]Kim Dong-Seong,Shin Taek-Hyun,Park Jong-Sou.A Security Framework in RFID Multi-domain System[C]//Proceedings of the 2nd International Conference on Availability,Reliability and Security.Vienna,Austria:IEEE Press,2007:1227-1234.

[10]Pateriya R K.The Evolution of RFID Security and Privacy:A Research Survey[C]//Proceedings of 2011 International Conference on Communication Systems and Network Technologies.[S.l.]:IEEE Press,2011:115-119.

[11]Yang Yuanyuan,Lu Zhen.Security Analysis of a Mutual Authentication Protocol for RFID Systems[C]//Proceedings of IMCCC’12.[S.l.]:IEEE Press,2012:252-255.

[12]Yan Fang,Liu Bingwu,Huo Lingyu.Research and Design of a Security Framework for RFID System[C]//Proceedings of 2010 International Forum on Information Technology and Applications.[S.l.]:IEEE Press,2010:443-445.

[13]Tzipora H,Nitesh S,Shai H.Tree-based HB Protocols for Privacy-preserving Authentication of RFID Tags[J].Journal of Computer Security,2011,19(2):343-363.

[14]Bashir A K,Chauhdary S H.Mobile RFID and Its Design Security Issues[J].IEEE Potentials,2011,30(4):34-38.