增强型匿名RFID双向认证协议eARAP的设计与分析

丁　洁,吴汉炜,林志阳,王泽众

(1.海南大学信息科学技术学院, 海南海口570228； 2.华南理工大学电子与信息学院， 广东广州510640)



增强型匿名RFID双向认证协议eARAP的设计与分析

丁洁1,吴汉炜1,林志阳1,王泽众2

(1.海南大学信息科学技术学院, 海南海口570228； 2.华南理工大学电子与信息学院， 广东广州510640)

摘要：对匿名RFID身份认证协议(ARAP)进行了深入分析，指出其存在无法抵抗假冒攻击、多标签冲突和阅读器功能受限等三方面的缺陷，提出相应的改进协议eARAP，并对eARAP协议进行了严格的形式化分析和安全性能分析。结果表明：eARAP协议能够达到预期的认证目标，能够抵抗假冒、拒绝服务等诸多攻击，安全性能有所增强，且协议执行的计算量明显减少，具有较高的可行性。

关键词：无线射频识别；ARAP协议；身份认证；形式化分析

0引言

随着电子信息技术的发展，无线射频识别(radio frequency identification，RFID)的应用日趋广泛。RFID是一种非接触式的自动识别技术，具有使用时间长、读取精度高、操作便捷等优点，然而其安全与隐私问题也日益突出，比如伪造标签、非法访问和信息泄露等。身份认证是保证信息安全的关键技术之一，现有基于哈希函数的RFID身份认证协议中比较典型的有哈希锁协议[1]、随机哈希锁协议[2]、哈希链协议[3]等，这几个协议都存在着无法保障用户隐私、标签容易追踪等安全隐患。对此，Shen等[4]提出了一种基于匿名机制的RFID身份认证协议ARAP(anonymous RFID authentication protocol)，该协议实现了标签和阅读器的双向认证，并通过使用假名来保护用户的隐私，防止标签被攻击者跟踪。但ARAP协议也存在由于异或不当而被攻击者假冒的安全隐患[5-6]。笔者对ARAP协议进行深入的分析，指出其存在三个方面的缺陷，在给出相应改进方案的基础上，提出增强版的协议eARAP(enhanced anonymous RFID authentication protocol)，并对其进行严格的形式化分析和安全性能分析。

1ARAP协议及其改进方案eARAP

1.1　ARAP协议简介

ARAP协议通过使用假名来为标签提供隐私性保护。假名P表示标签T的身份，且协议每成功执行一次，标签T就更换假名，以防止攻击者对标签进行跟踪攻击。每个标签T都与后端数据库DB共享一个初始秘密xT,DB能够根据T的假名P遍历出初始共享的秘密xT，实现对T的身份认证。ARAP协议的具体认证过程如图1所示，阅读器R和标签T都拥有一个伪随机数发生器，标签可执行Hash计算和异或操作：

①R→T：R向T发送认证请求Query和随机数rR；

②T→R：T计算S=h(P⊕xT)和M=h(rT⊕rA⊕P)⊕S，并向R发送消息{rT，P，M}作为应答，其中xT是T与R互相共享的秘密；

③R→DB：R向DB发送消息{rT，rR，P，M}；

④DB→R：DB收到消息后，计算S′=h(P⊕xT)和M′=h(rT⊕rA⊕P)⊕S′，验证M′与M是否相等。若相等，则通过认证，DB计算N′=h(M′⊕S′)发送给R。否则，认证失败，协议终止。

⑤R→T：R收到N′后转发给T，T计算N=h(M⊕S)，验证N′与N是否相等，若等，则R通过认证，T更新假名P，否则认证失败，协议终止。

图1　ARAP协议认证过程

1.2　ARAP协议的缺陷分析及解决方案

缺陷1：无法抵抗假冒攻击。

在ARAP协议的第2步中，标签T计算了S=h(P⊕xT)和M=h(rT⊕rA⊕P)⊕S，其中P为标签的匿名，xT为共享秘密，rA和rT分别为攻击者与标签生成的伪随机数。若攻击者截取了消息M，rA，rT，P，利用异或运算的性质(a⊕a=0，a⊕0=a)，则可直接计算M⊕h(rT⊕rA⊕P)=h(rT⊕rA⊕P)⊕S⊕h(rT⊕rA⊕P) =S，从而获取S，就相当于获得了阅读器向标签进行认证的钥匙N′=h(M⊕S)，攻击者可假冒阅读器向标签发送N′，从而获取标签的信任，成功进行假冒攻击。

对此，参考分布式RFID询问—应答协议的认证过程[7]，对部分异或运算和验证操作进行修改，将标签用户的秘密隐藏入哈希函数中，使攻击者无法通过异或运算来假冒阅读器实施假冒攻击。

缺陷2：多标签冲突。

在ARAP协议的执行过程中，若每次只读取一个标签，则运行良好。但当多个标签同时进入RFID阅读器的读取频段时，阅读器便无法判断与哪个标签进行通信，进而导致访问冲突。

由于标签受硬件资源限制，存储和计算能力有限，诸多传统的网络防冲突算法并不适用于RFID标签之间的冲突检测。从系统的复杂性以及成本方面考虑，基于时分多址(TDMA)的时隙ALOHA防冲突算法[8]可用于检测RFID标签之间的冲突。该算法将时间分为若干个离散时隙，每个时隙长度大于或等于标签标识符发送的时间长度，每个标签只能在时隙开始时刻发送标识符。当发生冲突时，阅读器发送命令让标签停止发送，随机等待一段时间后再重新发送以减少冲突。

缺陷3：忽略了阅读器的计算和存储能力。

在ARAP协议的执行过程中，阅读器只起到了在标签和后端数据库之间进行数据传递的作用，没有执行任何计算。事实上，相对于标签T，阅读器R具有相对强大的计算和存储能力。对此，可以结合连续会话[9]的操作模式，将前次会话的信息缓存在阅读器中，让阅读器通过对比两次会话的内容是否相同，对消息进行第一次过滤，以减少后端数据的计算量以及对后端数据库的重放攻击。

1.3　eARAP协议

eARAP协议中使用的符号及其含义见表1。

表1　eARAP符号及含义

eARAP协议认证过程如图2所示。

图2　eARAP协议认证过程

Step 1： 阅读器R生成一个伪随机数rR，向标签T发送Query认证请求，认证请求中包含伪随机数rR。此时可能会有3种情况发生：① 无标签应答；② 恰好一个标签应答；③ 多个标签发生应答冲突。当多个标签冲突时，会执行一次时隙Aloha算法，选定一个T和R进行接下来的认证步骤。

Step 2：T收到Query后生成一个伪随机数rT，计算S=h(P⊕xT)和M=h(rR‖rT‖P‖S)，其中xT是T和DB共享的秘密，P是标签的假名。T将消息{rT，P，M}发送给R。

Step 3:R收到T的消息{rT，P，M}后，先根据上一次缓存的M*来判断M*与M是否相等，若M*=M，则过滤掉该标签以避免攻击者对后端服务器的重放攻击，降低后端服务器的计算负载。若M*≠M，则R将{rR，rT，P，M}发送给DB。

Step 4: DB收到R的消息后，先查找事先与标签匿名P所对应的共享秘密xT，若无记录，则认证失败。若有记录，DB计算S′=h(P⊕xT)，M′=h(rR‖rT‖P‖S′)，如果M=M′，则DB信任T的合法性，认证成功，DB计算N′=h(M′‖S′)，并将N′发送给R；若M≠M′，则T不是合法标签，认证失败。

Step 5：R将消息N′发送给T，T计算N=h(M‖S)，并验证N和N′是否相等，如果N=N′，则T信任R的合法性，并更新假名P，如果N≠N′，认证失败，协议终止。

2eARAP协议的形式化分析

身份认证方案的核心是安全协议，其目的是认证参加协议的主体身份。安全协议的设计极易出错，以往对安全协议的验证手段主要有两类，一类是用常规方法，对协议进行实际攻击;另一类是从表面上进行直观检测。前者必须在系统己经建立之后才能检测出错误，后者由于检测手段不够严密，难免有疏漏之处。安全协议的形式化分析，就是运用某种形式化语言，为安全协议建立模型，并按照规定的假设、分析和验证规则，对协议的正确性和安全性进行推理验证，使得研究者可以在安全协议付诸实施之前，用一种严谨可靠的方法检查协议是否可以达到其设计目标。目前广泛使用的安全协议形式化分析方法是基于知识和信念的形式逻辑分析法，其中最有影响力的是BAN逻辑[10]。BAN逻辑是一种基于信念的模态逻辑，其目标是认证参与协议的主体身份，分析协议能否达到预定的目标。

2.1　BAN逻辑

BAN逻辑的基本语句及其含义如表2所示。

表2　BAN逻辑的基本语义

BAN逻辑的主要推理规则如下：

②随机数验证规则R2：{P|≡#(X)，P|≡Q|~X}/(P|≡Q|≡X)，表示若P相信消息X是新鲜的，且P相信Q曾发送过X，那么P就相信Q是相信X的。

③信仰规则R3：{P|≡Q|≡(X,Y)}/(P|≡Q|≡X)，表示若P相信Q相信消息(X,Y)，则P相信Q相信X。

④管辖规则R4：(P|≡Q|=>X,P|≡Q|≡X)/(P|≡X)，如果P相信Q对X具有管辖权，而且P相信Q相信X，那么P就相信X。

⑤新鲜性规则R5：{P|≡#(X)}/{P|≡#(X,Y)}，表示若P相信消息X是新鲜的，则P相信消息(X,Y)也是新鲜的。

2.2　eARAP协议的形式化分析

2.2.1eARAP协议的形式化

在eARAP协议中，R、T之间的认证主要通过传送包含共享秘密xT的消息{rR,rT,P}进行：

Message 1：RΔxT;Message 2：TΔxT。

2.2.2初始化假设

R、T相信随机数rT和rR的新鲜性：P3：R|≡#(rT)；P4：T|≡#(rR)；

R、T相信彼此对匿名P具有控制权：P5：R|≡T|=>P；P6：T|≡R|=>P。

2.2.3协议的安全目标

本协议的最终目标是实现阅读器和标签之间的相互认证，即：

G1：R|≡P：R相信匿名P的合法性；

G2：T|≡P：T相信R传回的匿名P的合法性。

2.2.4协议分析

①当RΔxT时，根据初始假设P1和消息含义规则R1：

(1)

即R相信T曾发送过消息{rR,rT,P}。

②根据初始假设P3与消息新鲜性规则R5：

{R|≡#(rR,rT)}/{R|≡#(rR,rT,P)}，可得：R|≡#(rR,rT,P)，

(2)

即R相信消息{rR,rT,P}的新鲜性。

③由式(1),式(2)和临时值验证规则R2：

{R|≡#(rR,rT,P),R|≡T|~(rR,rT,P)}/{R|≡T|≡(rR,rT,P)}，得：R|≡T|≡(rR,rT,P)，

(3)

即R相信T相信消息{rR,rT,P}的真实性。

④由式(3)和信仰规则R3：

{R|≡T|≡(rR,rT,P)}/(R|≡T|≡P)，可得：R|≡T|≡P,

(4)

即R相信T相信匿名P的合法性。

⑤由式(4)、初始假设P5和管辖规则R4：(R|≡T|=>P,R|≡T|≡P)/(R|≡P)，可得：R|≡P，表示阅读器R相信标签T所传的匿名P是合法的，安全目标G1得证，阅读器对标签认证成功。

同理，可推导出T|≡P。

至此，eARAP协议的形式化分析结果表明，阅读器R和标签T可以实现相互之间的双向认证，达到预期的认证目标。

3eARAP协议的安全和性能分析

3.1　eARAP协议的安全性分析

在安全性分析时，依据三个基本假设[11]：攻击者都可以窃听并操作公共信道上的信息；攻击者若通过某种手段获得用户的智能卡，则可以得到其中存储的秘密信息；用户所采用的密码是可记忆的，其信息熵不高。现选取四种较常见的攻击对eARAP协议进行安全性分析：

①抗重放攻击

重放攻击是指攻击者截取以前成功认证的消息，重新发送给目标，企图绕过认证，包括阅读器的重放攻击和标签的重放攻击。

若攻击者伪装成合法阅读器，向标签发送先前监听到的协议流程中的信息N′=h(M′‖P‖xT)和N′⊕P′。由于在协议的每次执行中所使用的随机数rR、rT和匿名P都会更新，所以标签此时不会响应，攻击者无法通过重放攻击来伪装成阅读器。

若攻击者伪装成一个合法标签，发送前次通信监听到的标签认证信息{rT，P，M}给阅读器，其中M=h(rR‖rT‖P‖xT)。阅读器对从标签收到的信息进行判断，若发现本次收到的消息M与上次相同，则直接过滤掉该标签。因此攻击者无法通过重放攻击来伪装成合法标签。

②抗假冒攻击

在eARAP协议中，标签和后端数据库事先拥有配对参数，只有拥有共享秘密xT才能通过相互验证。且xT通过异或运算并隐藏入Hash函数中，攻击者无法获取，故能够有效防止假冒攻击。

③抗位置跟踪攻击

eARAP协议保留了原协议匿名性的特点，每个标签都有大量的假名，且对应于协议的每一次成功执行，标签会更换假名。即使攻击者获取大量的通信数据来跟踪标签，也无法确定标签的真实身份，因此可抵抗位置跟踪攻击。

④抗拒绝服务攻击

原ARAP协议在一些特殊情况下易遭受拒绝服务攻击。比如，后端数据库链接断开、阅读器断电等，将使得后端数据库无法及时更新数据，造成认证失败；攻击者通过截取某些通信数据等手段，刻意使标签和阅读器不同时更新共享的数据，造成下一次通信时双方共享的数据不相同，致使合法的标签认证失败。在eARAP协议中，后端数据库存有和标签对应的所有假名，只有标签需要更新假名，因而不存在需要双方同时更新的要求，能够全面抵抗拒绝服务攻击。

表3　ARAP协议及3种改进方案的安全性比较

由表3可见，eARAP协议能够较好地抵抗针对RFID系统的各种攻击。与原ARAP协议相似，文献[6]的方案也无法抵抗特殊情况下的拒绝服务攻击，而本文提出的eARAP协议则有效地解决该问题。文献[5]所提的改进方案虽然也能抵抗针对RFID系统的各种攻击，但其计算量比eARAP协议要大，下文将对此作详细分析。

3.2　eARAP协议的性能分析

在RFID系统中，标签的存储空间和计算能力有限，认证协议在解决安全性问题的同时，也要尽可能减少标签的计算量和存储容量，以降低标签的成本。eARAP协议主要用到哈希运算、异或运算、随机数运算，是一种中量级的身份认证协议。在此对ARAP协议及其3种改进方案进行对比，比较各协议中标签、阅读器和后端数据库的计算量，结果如表4所示。其中，“H”表示Hash运算的次数，“X”表示异或运算的次数，“R”表示产生随机数的次数，“N”表示数据库存储的标签数量，“j”表示Hash链的长度。

表4　ARAP协议及3种改进方案的性能比较

由表4可见，在文献[5]的改进方案与本文的eARAP协议相比，标签和后端数据库的计算量较大。文献[6]的改进方案与eARAP协议相比，后端数据库少了一次哈希计算，而通常后端数据库的计算能力很强，所以影响不大。其标签端也少1次哈希运算和1次异或运算，但其在安全性方面有所欠缺。

综合表3和表4，可对ARAP协议的一些相关研究进行比较。文献[5]发现其无法抵抗假冒伪造攻击，并通过提出一种新的“置换操作”对其进行改进，其协议运行的代价高于本文提出的eARAP协议。文献[6]则通过直接计算M=h(rR‖rT‖P‖xT)来对匿名P和秘密xT进行加密，若攻击者截取了M,rT,rR,P，便可遍历出秘密xT，该方案无法抵抗弱碰撞攻击[12]，且无法抵抗特殊情况下的拒绝服务攻击。本文提出的eARAP协议与原协议相比，在安全性能进一步增强的同时，协议执行过程中的异或次数和哈希函数的使用次数都明显减少，降低了原有协议的计算量，具有较高的可行性。

在协议的执行过程中，若有多个标签同时响应阅读器的查询命令，将导致标签不能被正确识别，这便是多标签冲突或称碰撞，将严重影响标签识别效率，甚至造成通信故障。现有的RFID安全协议一般只注重其安全性能[13-14]，往往忽略协议在执行过程中可能遇到的这一问题。本文所提eARAP 协议通过调用时隙Aloha算法来克服上述缺陷，进一步保证了协议的顺利执行。

4结语

本文对ARAP协议进行了深入的分析，指出其存在的缺陷，提出了相应的改进方案eARAP协议，并对其进行了严格的形式化分析和安全性能分析。结果表明eARAP协议能够达到预期的认证目标，能够抵抗假冒、拒绝服务等诸多攻击，在安全性能有所增强的同时，协议执行的计算量明显减少，具有较高的可行性。eARAP协议的仿真和实验测试工作将在后继的研究工作中展开。

参考文献:

[1]SARMA S E, WEIS S A,ENGELS D W.RFID systems and security and privacy implications[C]//Proceedings of the 4thInternational Workshop on Cryptographic Hardware and Embedded Systems. New York: Springer-Verlag, 2002: 454-469.

[2]WEIS S A, SARMA S E, RIVEST R L, et al.Security and privacy aspects of low-cost radio frequency identification systems[J]. Security in Pervasive Computing, 2004, 28(2):201-212.

[3]OHKUBO M, SUZUKI K, KINOSHITA S. Hash-chain based forward-secure privacy protection scheme for low-cost RFID[C]//Proceedings of the 2004 Symposium on Cryptography and Information Security(SCIS 2004). Berlin: Springec Verlag, 2004:719-724.

[4]SHEN J, CHOI D, MOH S, et al.A novel anonymous RFID authentication protocol providing strong privacy and security[C]//Proceedings 2010 International Conference on Multimedia Information Networking and Security. Nanjing: Acn Press, 2010: 584-588.

[5]田芸,陈恭亮,李建华.针对RFID身份认证协议-ARAP协议的攻击及改进[J]. 中国电子科学研究院学报, 2011,6(6): 556-560.

[6]李景峰,郭卫锋.对ARAP认证协议的攻击及改进[J]. 武汉大学学报:理学版, 2012, 58(6): 526-530.

[7]RHEE K, KWAK J, KIM S, et al.Challenge-response based RFID authentication protocol for distributed database environment[C]//Proceedings of the 2nd International Conference on Security in Pervasive Computing(SPC 2005).Lectures Notes in Computer Science 3450.Berlin:Springer-Verlag, 2005:70-84.

[8]陆桑璐,谢磊.射频识别技术:原理、协议及系统设计 [M]. 北京:科学出版社,2014.

[9]丁振华,李锦涛,冯波.基于Hash函数的RFID安全认证协议研究 [J]. 计算机研究与发展,2009,46(4):583-592.

[10]BURRROWS M, ABADI M, NEEDHAM R.A logic of authentication[J]. ACM Transactions on Computer Systems, 1990,8(1):18-36.

[11]WANG D, MA C G, GU D L, et al.Cryptanalysis of two dynamic ID-Based remote user authentication schemes for multi-server architecture [J]. Lecture Notes in Computer Science, 2012,7645:462-475.

[12]王张宜,李波,张焕国.Hash函数的安全性研究 [J]. 计算机工程与应用, 2005, 41(12): 18-19.

[13]龚晶,石会,邓元庆,等.基于Hash函数的RFID安全认证协议研究[J]. 微电子与计算机,2014,31(9):135-137.

[14]张捍东,丁磊,岑豫皖.基于Hash函数的RFID安全协议研究[J]. 计算机工程与设计, 2013, 34(11): 3766-3769.

(责任编辑梁碧芬)

Design and analysis of an enhanced anonymous mutual RFID authentication protocol eARAP

DINH Jie1, WU Han-wei1, LIN Zhi-yang1, WANG Ze-zhong2

(1.College of Information Science and Technology，Hainan University，Haikou 570228, China;

2.College of Electronics and Information Engineering, South China

University of Technology, Guangzhou 510640, China)

Abstract:The analysis of anonymous RFID authentication protocol (ARAP) is given, which shows that there are three kinds of defect including failure on resistance to counterfeiting attack, multi label conflict and reader function limitation. An improved protocol named eARAP is proposed. The formal analysis based on BAN logic and the analysis of security and performance are given. The results show that eARAP protocol achieves the expected authentication target. It can resist theattacks such as counterfeiting and denial of service with enhanced security, and the calculation in the execution process decreases significantly.

Key words:RFID; ARAP protocol; identity authentication; formal analysis

中图分类号：TP393

文献标识码：A

文章编号：1001-7445(2015)06-1494-07

doi:10.13624/j.cnki.issn.1001-7445.2015.1494

通讯作者：吴汉炜(1976—)，男，广东汕头人，海南大学副教授; E-mail：Hanwei761314@163.com。

基金项目：国家自然科学基金资助项目(61562018)；国际科技合作专项项目(2015DFR10510)；海南省自然科学基金资助项目(20156250;614231)

收稿日期：2015-09-22；

修订日期：2015-10-17