基于位替换运算的RFID双向认证协议

杜宗印，章国安，袁红林

(南通大学 电子信息学院，江苏 南通226019)

责任编辑:薛 京

射频识别(Radio Frequency Identification，RFID)是一种非接触式自动识别技术，现已广泛应用于身份认证、物品识别、门禁系统、高速公路自动收费甚至动物跟踪等领域。RFID系统主要包含标签、阅读器及后端数据库3部分，在其通信协议设计时，通常认为，后端数据库与阅读器之间的传输信道是安全的，可将它们共同视为协议一方，本文统称为阅读器;而标签与阅读器之间的传输信道存在多种潜在攻击[1]，可将标签单独视为协议另一方。同时，由于RFID系统硬件资源受到计算能力、存储空间等因素的限制，因而，设计出安全性较好、成本较低的RFID认证协议是至关重要的。

目前，研究者们已提出多种认证协议，如HB系列协议、Hash-Lock协议、LMAP等，文献[2]中将它们划分为全面、简单、轻量级及超轻量级4类认证协议。全面认证协议需要密码算法的支持，如对称密码算法、公开密码算法等;简单认证协议需要在标签中建立伪随机数发生器和单向哈希函数;轻量级认证协议需要在标签中建立伪随机数发生器和循环冗余检验编码;超轻量级认证协议只需在标签中提供简单的位运算，如异或(⊕)、或(∨)、与(∧)及模二加(+)等。其中，超轻量级认证协议较前3类，可大大降低标签的存储空间和计算需求。因而，它是近期的研究热点。

超轻量级认证协议LMAP[3]由Peris-Lopez等人率先提出，并且进一步提出了EMAP[4]和M2AP[5]，这些协议只需⊕、∨、∧和+运算，在认证通信中非常有效，引起了人们一时的关注。但文献[6]指出它们存在主动与被动攻击;文献[2]中Chien在协议中引入左循环移位运算Rot(X，Y)——将X循环左移wt(Y)位，wt(Y)是Y的汉明重量，并提出了非常典型的SASI协议，其认证性和数据完整性更强，但文献[7]分析发现它存在跟踪及拒绝服务(DoS)攻击;超轻量级Gossamer协议[8]，首次引入MIXBITS函数，该函数采用右移及加法操作实现，具有很高的效率，但由于该协议的初始状态与SASI协议相同，故它仍存在DoS攻击。

为解决现有RFID认证协议所存在的问题，本文根据AES加密算法[9]设计了位替换运算Sub(X，Y)，并协同按位异或及Rot(X，Y)运算提出一种新的基于位替换的RFID双向认证协议(SRMAP)。

1 所提协议SRMAP

1.1 位替换运算

SRMAP中，异或和左循环移位[2，7]已详细描述，位替换运算Sub(X，Y)设计如下:

设X、Y是两个具有L位的二进制数组，获取Y中为1的位，X中与之对应的位元素取反将其替换，则二进制数组X中共有n=wt(Y)个元素被替换，其中wt(Y)为Y的汉明重。

位替换运算在标签中实现时，采用文献[10]提出的指针形式，它比直接采用逻辑门效率更高。设指针rX、rY分别指向数组X、Y，rX、rY同时从X、Y最高位遍历，当rY指向Y中元素为0时，rX所指X中元素不变;当rY指向Y中元素为1时，rX所指X位上元素用其反(0的反为1)替换，最后Sub(X，Y)即是被替换后的二进制串X。与文献[10]中各指针需遍历数组2次相比，Sub(X，Y)运算只需遍历1次，效率提高。

例如，给定L=8，取X=10011001，Y=01101011，则Sub(X，Y)=11111010，运算过程如图1所示。

图1 Sub(X，Y)运算实例

1.2 SRMAP通信流程

协议SRMAP运行时，标签内需存储其真正ID、当前标签假名IDS、当前认证密钥K1和K2，阅读器中需含有伪随机数发生器及存储各标签真正ID、当前信息}及前一次会话信息}。该协议包括标签识别、双向认证、假名和密钥更新3个阶段。各个阶段进行详细描述如下，具体通信流程如图2所示。

图2 所提协议SRMAP通信流程

标签识别:阅读器向标签发送请求信号“Query”，标签收到请求信号后，向阅读器返回假名IDS，阅读器在后端数据库中搜索相同的IDS，若搜到，则进入双向认证阶段;若未搜到，阅读器再次向标签发送请求。

双向认证:阅读器查找与IDS匹配的密钥，然后生成随机数N1、N2，计算A=Sub(K1，K2)⊕N1，B=Sub(K1，Rot(N1，N1))⊕Rot(Sub(K2，K1)，N1)，并发送至标签。

标签接收到A||B后，提取随机数N1，N1=A⊕Sub(K1，K2)，并采用与B相同的算法计算B'，如果B'=B，则认证阅读器成功;如果B'≠B，认证失败，协议终止。标签成功认证阅读器后，计算C=Sub(Rot(N1，K1)，K2)⊕Sub(N1⊕K2，K1)并返回给阅读器，阅读器采用与C相同的算法，利用自身存储的数据计算C'，若C'=C，则成功认证标签，进入下一阶段;若C'≠C，认证失败，协议终止。

假名和密钥更新:阅读器成功认证标签后，阅读器立即进行标签假名和密钥更新，算法为

而原来使用的{IDS，K1，K2}则变为

若此时的IDSnew与后端数据库中其他某个IDS相同，则必须重新生成N2再计算IDSnew，直到IDSnew与数据库中原存储的各IDS不同为止，以确保标签的IDSnew与其ID是一一对应的。然后计算D=Sub(K1⊕K2，N1)⊕N2和E=Sub(N1，N2)⊕Rot(N1，N2)并发送至标签。

标签收到D||E后，提取随机数N2=D⊕Sub(K1⊕K2，N1)，并用与E相同的算法计算E'，若E'=E，则同阅读器更新算法进行标签内数据更新，并丢弃原来使用的数据{IDS，K1，K2}，如果E'≠E，标签内不更新数据。

2 安全与性能分析

2.1 安全分析

1)双向认证和数据完整性:SRMAP能够确保标签与阅读器得到相互认证，因为只有合法的阅读器拥有预共享密钥K1、K2，能计算传输消息A||B，也只有合法的标签才能够根据消息A获取正确的随机数N1，计算消息C;该协议始终运用位替换Sub(X，Y)与异或运算共同对随机数加密传输，且阅读器和标签各自产生了认证消息B、C，用于与接收到的消息进行比较，保证了数据的完整性。

2)标签匿名性和不可跟踪性:该协议中标签对所有攻击者具有匿名性，因为协议运行时，标签始终未透漏其真正ID，而一直使用的是其假名IDS，而且协议结束时，标签都会更新其假名和密钥;攻击者若截获标签响应，对其认真分析，跟踪该标签，但每一次会话都生成新的随机数N1、N2参与运算，对以前消息分析是毫无意义的，故攻击者不可能成功跟踪标签。

3)抵抗假冒攻击:攻击者可以假冒合法阅读器向标签发送请求消息，获得标签响应，但由于攻击者本身并不含有真正的密钥K1、K2，不能得出正确的认证消息A||B，协议失败。同样，如果攻击者假冒标签截获阅读器发出的消息A||B，但由于其本身并不含有密钥K1、K2而不能正确计算B'，即使攻击者假装认证阅读器成功，它也不能计算出一致的消息C，协议运行失败。所以，该协议能够抵抗假冒攻击。

4)抵抗重传攻击:即使攻击者多次收集阅读器与标签的交互信息，在以后的会话中进行重放，也不能使协议成功运行。攻击者如果重放前次会话中的消息A、B和C，由于在每次会话中都有新的伪随机数N1、N2，且每次会话后密钥也要更新，保证了数据的新鲜性，重传失效。

5)抵抗DoS攻击:在更新阶段，如果攻击者截获最后的传输消息D||E，标签无法验证E'是否等于E，则不进行更新，而后端数据库中存有标签的两组消息，当协议再次运行时，标签返回的是IDSold阅读器仍然能够搜索到相应的信息，协议能够正常运行。因而，该协议可以抵抗DoS攻击[7]。

6)前向安全性:该协议能够提供前向安全性，是因为每次会话都有新的随机数参与运算，其对攻击者是不可预知的，即使最后攻击者破解了标签的当前信息}，该协议也能够保证标签之前任何信息的秘密性。

2.2 性能分析

由于阅读器不受硬件资源的限制，主要从标签内部的计算需求、存储空间和通信量这3个方面来分析所提协议SRMAP。

计算需求:SRMAP在计算上只需要XOR、Rot(X，Y)及位替换Sub(X，Y)三种简单的位运算。其中，XOR与Rot(X，Y)只需少量简单逻辑门即可硬件实现，而本文设计的Sub(X，Y)运算在标签中运用指针也可有效实现。

再者，本文协议有效避开了按位与或的存储空间:协议运行结束时，标签需丢弃前一次会话使用的数据，标签中只存储一组信息{ID，IDSnew，K1new，K2new};当认证协议运行中断时，标签不更新会话信息，只存储{ID，IDSold，K1old，K2old}。设标签身份识别和密钥的长度都为L位，则标签内存空间共需4L位。

通信量:协议运行共需传输的消息是“Query”，IDS及A～F，设“Query”需5 byte，其他消息均为L位，则总通信量即是5×8+L×6=6L+40位，而标签传输的消息只有IDS和C，即标签上的通信量为2L位。

将所提超轻量级认证协议SRMAP与其他几种超轻量级认证协议对比，如表1所示。

表1 超轻量级认证协议性能对比

3 协议的形式化分析

BAN逻辑[11]是在多种安全协议形式化分析方法中应用最为广泛的，它于1989年由Burrows、Abadi和Needham提出。本文即采用BAN逻辑形式化证明协议的安全性。

3.1 BAN逻辑语法及推导准则

由于BAN逻辑知识较为复杂，本文只介绍证明过程中所用到的相关语法及推导规则如下，详细见文献[11]。

1)语法

{X}K:用密钥K加密后X的密文;

P←→KQ:主体P和Q之间共享密钥;

P believes X:主体P相信消息X是真的;

P sees X:主体P接收到包含X的消息;

P said X:主体P曾发送过消息X;

P controls X:主体P对消息X有管辖权;

fresh(X):X是新鲜的。

2)推导规则

R1消息含义规则

式(3)表示:如果P相信K是P和Q的共享密钥，并且P曾经接收到用K加密的消息{X}K，则P相信Q发送过消息X。

R2随机数验证规则

式(4)表示:如果主体P相信消息X是新鲜的，并且P相信Q发送过消息X，则P相信主体Q相信消息X。

式(5)表示:如果主体P收到了消息(X，Y)，则P收到了消息X。

R4管辖规则

式(6)表示:如果主体相信P相信主体Q对消息X具有管辖权，并且P相信Q相信X，则P相信消息X。

R5消息新鲜性规则

式(7)表示:如果主体P相信消息X是新鲜的，则P相信消息(X，Y)是新鲜的。

3.2 形式化证明过程

BAN逻辑形式化证明可简化为:建立协议理想化模型、给出协议的初始假设、给出协议预期达成的安全目标及分析推理4个步骤。SRMAP的证明过程如下:

1)协议理想化模型

在理想化模型中，需去除原来协议所有的明文传输

其中，A、B、C为用密钥Ki加密后的密文。

2)初始假设

3)预期安全目标)

4)分析推理

由Msg3、初始假设P2及消息含义规则R1、接收准则R3得

由初始假设P4及消息新鲜性规则R5得

又由随机数验证规则R2及以上推出的式(11)、(12)得

最后由初始假设P5、管辖规则R4及式(13)推出T believes B，目标G1得证。

同样，由Msg4、假设P1及规则R1得R believes T said C;由初始假设P3及规则R得R believes #(C);又因为准则R2得R believes T believes C;最后由假设P6及规则R4得到R believes C，目标G2得证。

综上，该协议可以达到预期的安全目标，故它是安全的、可行的。

4 小结

本文运用新设计的位替换运算以及异或、左循环移位运算，提出了一种新的超轻量级认证协议SRMAP，并通过BAN逻辑形式化分析方法证明了该协议的安全性与可行性。安全与性能分析结果表明:该协议可抵抗DoS等多种攻击，安全性较好;采用该协议的标签实现效率高，且所需存储空间和通信量较少。

[1]游相柏，刘毅敏.RFID安全认证协议研究[J].电视技术，2012，36(15):104-107.

[2]CHIEN H Y.SASI:a new ultra-lightweight RFID authentication protocol providing strong authentication and strong integrity[J].IEEE Trans.Dependable and Secure Computing，2007，4(4):337-340.

[3]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.LMAP:A real lightweight mutual authentication protocol for low-cost RFID tags[C]//Proc.2nd Workshop on RFID Security.New Jersey，USA:IEEE Press，2006:137-148.

[4]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.EMAP:an efficient mutual authentication protocol for low-cost RFID tags[C]//Proc.IS’06.Berlin:Springer Press，2006:352-361.

[5]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，TAPIADOR J M，et al.M2AP:a minimalist mutual authentication protocol for low-cost RFID tags[C]//Proc.UIC’06.Berlin:Springer Press，2006:912-923.

[6]王少辉，王高丽.RFID认证协议ULAP的被动攻击分析[J].计算机工程，2010，36(22):17-19.

[7]SUN H M，TING W C，WANG K H.On the security of Chien's ultralightweight RFID authentication[J].IEEE Trans.Dependable and Secure Computing，2011，8(2):315-319.

[8]PERIS-LOPEZ P，HERNANDEZ-CASTRO J C，ESTEVEZ-TAPIADOR J M，et al.Advances in ultra-lightweight cryptography for low-cost RFID tags:Gossamer protocol[C]//Proc.9th International Workshop，WISA 2008.Berlin:Springer Press，2009:56-68.

[9]王沁，梁静，齐悦.一种有效缩减AES算法S盒面积的组合逻辑优化设计[J].电子学报，2010，38(4):939-942.

[10]TIAN Yun，CHEN Gongliang，LI Jianhua.A new ultra-lightweight RFID authentication protocol with permutation[J].IEEE Communications Letters，2012，16(5):702-705.

[11]王聪，刘军，王孝国，等.安全协议原理与验证[M].北京:北京邮电大学出版社，2011.