共享密钥与位运算的移动RFID认证协议

梅松青 邓小茹

(广州医科大学 广东 广州 510006)

0 引 言

RFID是一种使用非物理性接触实现对象识别和数据交换的技术，兴起于20世纪，并在20世纪90年代末得到大规模的应用[1-2]。

现有的RFID系统一般由标签、读写器、后台数据库三部分构成。在传统的RFID系统中，读写器一般是固定式，因此读写器与后台数据库之间的通信基于有线信道完成，同时被认为该信道安全可靠[3-4]。伴随着移动智能终端的快速发展，将读写器嵌入移动智能终端中从而形成移动RFID系统。在移动RFID系统中，读写器不再是固定式，而是可移动的，因此读写器与后台数据库之间的信息传输亦只能通过无线方式完成；无线信道易被攻击者窃听，使得两者之间的信息传输不再安全可靠[5-6]。

基于上述描述，显然传统的RFID认证协议并不适用于移动RFID系统。为此，提出一种基于共享密钥及按位运算的移动无线射频识别系统双向认证协议MAP。

1 相关工作

文献[7]提出一个移动双向认证协议，且考虑了后台服务器与移动读写器之间的信道安全问题，引入后台服务器对移动读写器身份认证步骤，适用于移动读写器的认证场景。但对协议进行深入分析发现：协议没有提供标签与移动读写器两者之间的认证，从而导致协议并不能抵抗攻击者发起的假冒攻击。

文献[8]提出一种移动认证协议，该协议未采用计算量较大的哈希函数，而是采用位运算进行信息的加密。对协议进行研究发现：攻击者通过物理入侵的方式获取密钥，从而假冒标签或移动读写器发起假冒攻击。

文献[9]提出了一种超轻量级的移动认证协议，分析发现该协议不能抵抗标签端的重放攻击。文献[10]中提出一种基于Hash函数的移动认证协议，分析发现协议无法防范标签伪造且存在中间人攻击及重放攻击。文献[11]提出三方认证的移动协议，但分析得知，协议使得后台数据库一直处于大负荷工作状态，且该协议无法抵抗拒绝服务攻击。

文献[12]基于物理不可克隆设计出一种适用于轻量级的移动RFID双向认证协议，协议主要基于物理不可克隆特征进行信息加密。对协议进一步研究分析：协议无法抵抗攻击者发起的去同步化攻击，攻击者截获信息后，重放该消息，经过几轮重放之后，标签一端的密钥会与后台服务器之间的密钥失去同步性。文献[13]提出了基于共享密钥的移动认证协议，分析发现该协议在整个认证过程中并未实现标签对读写器的认证，使得协议存在假冒攻击威胁。

鉴于现有众多方案的缺陷，本文针对移动无线射频识别系统提出了一种基于共享密钥与按位运算的移动RFID系统双向认证协议MAP。MAP在整个认证过程中，先验证消息源的真伪，再进行后续操作，从而可以抵抗攻击者的蓄意破坏；采用按位运算对信息进行加密，使得MAP可以达到超轻量级别，能够有效减少RFID系统的计算量；从安全性及性能角度分析表明，MAP适用于低成本的移动RFID系统中。

2 MAP设计

2.1 初始条件及符号说明

位替换运算定义：为了便于用符号描述，约定用符号Sub(X，Y)表示位替换运算符号。位替换运算Sub(X，Y)定义如下：设X、Y是两个长度均为L位的二进制数，X=x1x2…xL，Y=y1y2…yL。获取二进制数Y中为1的位，二进制数X中与之对应的位元素取反将其替换，则二进制数X中共有n=wt(Y)个元素被替换，其中wt(Y)为Y的汉明重量。

位替换运算在标签中实现时，采用文献[14]中所提出的指针形式，从而使得它比直接采用逻辑门效率更高。引入两个指针，一个记为PX，另一个记为PY，其中PX指向二进制数X，PY指向二进制数Y。当PX从二进制数X最高位开始遍历的时候，PY同时从二进制数Y最高位开始遍历。当PY指向二进制数Y中元素为0时，PX所指二进制数X中元素不变；当PY指向二进制数Y中元素为1时，PX所指二进制数X位上元素用取反(0的反为1)替换。最后Sub(X，Y)即为被替换后的二进制数X。比如：L=8，X=00001100，Y=01100101，则Sub(X,Y)=01101001，具体过程如图1所示。

图1 位替换运算流程图

本文提出的MAP移动认证协议主要基于以下假设前提：

1) 低成本标签的计算能力及存储空间是受限制的；移动读写器及后台数据库具备较强的计算能力及存储空间。

2) 标签与移动读写器之间无线信道通信，被认为不安全；移动读写器与后台数据库之间无线信道通信，同样被认为不安全。

3) 协议中采用的位替换运算是安全的。

4) 标签、读写器、后台数据库初始化时存放的信息是安全可靠的。

在MAP执行之前，移动RFID系统中所有实体需初始化内存单元。初始化结果如下：

标签端存放Key_L、Key_R、IDT，即形成一个三元组(Key_L，Key_R，IDT)。移动读写器端存放Key_L、Key_R、IDR，即形成一个三元组(Key_L，Key_R，IDR)。后台数据库端存放Key_L、Key_R、IDT、IDR，即形成一个四元组(Key_L，Key_R，IDT，IDR)。

MAP所使用的符号定义及说明如表1所示。

表1 符号说明

2.2 MAP认证流程

MAP认证流程如图2所示。图2中M0至M12公式具体含义说明如表2所示。

图2 MAP认证流程图

符号含义M0rR⊕Key_RM1rR⊕Key_LM2rR⊕rT

续表2

MAP认证流程详细步骤描述如下:

步骤1首先移动读写器生成一个随机数rR，然后读写器计算M0和M1的值，最后将M0、M1及认证请求命令Query发送给标签。

步骤2标签接收到信息后，首先计算M0⊕Key_R、M1⊕Key_L的值，然后比对M0⊕Key_R与M1⊕Key_L两者值是否相等。若相等，则标签验证移动读写器通过，进行步骤3；否则，说明移动读写器是伪造的，MAP立刻终止。

步骤3标签通过计算得到随机数rR，然后标签生成一个随机数rT，接着标签计算M2、M3、M4、M5的值，最后将(M2、M3、M4、M5)传送给移动读写器。

步骤4移动读写器接收到信息后，首先计算M2⊕rR的值，然后计算M5′的值，最后比较M5′与M5的值是否相等。若相等，则移动读写器验证标签通过，进行步骤5；否则，说明标签是伪造的，MAP立刻终止。其中：M5′=Sub(((M2⊕rR)&rR),((M2⊕rR)& Key_L))。

步骤5移动读写器通过计算得到随机数rT，然后读写器计算M6、M7的值，最后将(M3、M4、M6、M7)传送给后台数据库。

步骤6后台数据库对移动读写器的认证。

(1) 数据库接收到信息后，首先计算M6⊕IDR的值，然后计算M7′的值，最后比对M7′与M7的值是否相等。若相等，则数据库验证移动读写器通过，进行步骤(3)；否则，进行步骤(2)。其中：M7′=Sub((M6⊕IDR)&IDR& Key_L,(M6⊕IDR)&IDR& Key_R)。

(2) 数据库用Key_old代替Key_new进行步骤(1)中的计算。若相等，则数据库验证读写器通过，进行步骤(3)；否则，说明移动读写器是伪造的，MAP立刻终止。

(3) 数据库通过计算得到随机数rR，然后进行步骤7。

步骤7后台数据库对标签的认证。

(1) 数据库验证移动读写器通过后，然后计算M3⊕IDT的值，再计算M4′的值，最后比对M4′与M4的值是否相等。若相等，则数据库验证标签通过，进行步骤(3)；否则，进行步骤(2)。其中：M4′=Sub((M3⊕IDT)& Key_L,(M3⊕IDT)⊕Key_R)。

(2)数据库用Key_old代替Key_new进行步骤(1)中的计算。若相等，则数据库验证标签通过，进行步骤(3)；否则，说明标签是伪造的，MAP立刻终止。

(3)数据库通过计算得到随机数rT，然后进行步骤8。

步骤8数据库生成一个随机数rDB，然后计算M8、M9、M10、M11的值，接着开始更新共享密钥信息Key_old=Key、Key=Key_new，最后将(M8，M9，M10，M11)传送给移动读写器。其中：Key_new=Sub((rDB⊕rT⊕rR),(rDB&rT&rR))。

步骤9移动读写器接收到信息后，首先计算M8⊕rR⊕IDR的值，然后计算M10′的值，最后比对M10′与M10的值是否相等。若相等，则移动读写器验证后台数据库通过，进行步骤10；否则，说明后台数据库是伪造的，MAP立刻终止。其中:M10′=Sub(rR,(M8⊕rR⊕IDR))。

步骤10移动读写器计算M12的值；然后更新共享密钥信息，即Key_old=Key、Key=Key_new；最后将(M9,M11,M12)传送给标签。其中:Key_new=Sub((rDB⊕rT⊕rR),(rDB&rT&rR))。

步骤11标签对移动读写器的验证。

(1) 标签接收到信息后，标签首先计算M9⊕rT⊕IDT的值，然后计算M12′的值，最后比对M12′与M12的值是否相等。若相等，则标签验证移动读写器通过，进行步骤(2)；否则，说明移动读写器是伪造的，MAP立刻终止。其中:M12′=rR&(M9⊕rT⊕IDT)。

(2) 标签对后台数据库的验证：标签计算M11′的值，比对M11′与M11的值是否相等。若相等，则标签验证后台数据库通过，进行步骤(3)；否则，说明后台数据库是伪造的，MAP立刻终止。其中:M11′=Sub(rT,(M9⊕rT⊕IDT))。

(3) 标签开始更新共享密钥信息，即Key=Sub((rDB⊕rT⊕rR),(rDB&rT&rR))。到此标签、移动读写器、后台数据库三方之间的认证结束。

3 安全性分析

(1) 重放攻击。在每次认证过程中，标签都会产生随机数rT。认证消息(M2，M3，M4，M5)计算过程中都有包含rT。若攻击者采用旧的上述消息，则标签在验证(M9，M11，M12)时会使用新产生的随机数rT。这样使得标签在验证移动读写器及后台数据库时就会失败，MAP立刻终止，阻止了攻击者完成后续认证过程，故MAP可以抵抗重放攻击。

(2) 异步攻击。异步攻击是指移动读写器(或后台数据库)与标签在认证过程中，由于攻击者的蓄意破坏，使得两者之间的共享密钥不同步，异步攻击也称为去同步化攻击。为了能够抵抗异步攻击，MAP存放了上一轮认证过程中用到的共享密钥Key_old用来现实与标签恢复同步。后台数据库通过(M3，M4，M6，M7)对标签及移动读写器进行认证时，首先调用Key_new进行计算，若验证无法通过，再调用Key_old进行计算，从而抵抗攻击者的去同步化攻击。故Key_new及Key_old的存在使得MAP能够抵抗异步攻击。

(3) 中间人攻击。该种攻击方式比较常见的攻击方法是替换消息、篡改消息等。根据协议应用的场景，攻击者可以获取标签、移动读写器、后台数据库三者之间所有的通信信息集合MS={M0,M1,M2,M3,M4,M5,M6,M7,M8,M9,M10,M11,M12}。上述消息都是加密之后的信息，因此即便是攻击者获取上述消息，并不能推导出有用信息。攻击者虽然可以对其中某个消息进行修改或篡改，但MAP在每个步骤中都将会对其进行验证，简单的验证便会发现消息已被篡改。同时上述消息计算过程中与随机数rR、rT、rDB有关联，且随机数是秘密产生的，并具备无法预测性，使得攻击者修改消息难度进一步增大。故MAP可以抵抗中间人攻击。

(4) 前向安全。因后台数据库存放有上一轮的认证共享密钥，所以这里仅仅讨论标签端的前向安全性。若攻击者想要获取标签的当前共享密钥值，则攻击者需要从获得的上次消息来解密出以前的认证消息。但攻击者无法成功，原因如下：攻击者无法破解采用按位操作加密的消息，因为密文中至少有两个量对于攻击者来说是未知的；MAP在认证结束后，会立刻更新共享密钥值，前后共享密钥值之间并无关联，同时共享密钥值的计算与rR、rT、rDB三个随机数都有关联，攻击者是不可能获取这三个随机数的。故MAP能够确保标签的前向安全。

(5) 假冒攻击。若攻击者假冒标签，发送消息给移动读写器。由于攻击者假冒的标签并不知晓当前共享密钥值Key_R、Key_L，因此攻击者无法计算出正确的随机数rR的值，从而攻击者传送给移动读写器(M2、M5)信息也会被移动读写器识别为错误，认证立刻终止。攻击者假冒标签失败。

若攻击者假冒移动读写器，则发送消息给标签。由于攻击者假冒的移动读写器并不知晓当前共享密钥值Key_R、Key_L，因此攻击者计算出来的(M0、M1)必定是错误的，传送给标签后，标签进行简单计算即可识别出攻击者假冒移动读写器。

若攻击者假冒移动读写器，则发送消息给后台数据库。由于攻击者假冒的移动读写器并不知晓移动读写器标识符IDR，因此攻击者计算出来的(M6、M7)必定是错误的。消息传送给后台数据库之后，验证移动读写器失败，攻击者被发现。

若攻击者假冒后台数据库，发送消息给移动读写器。由于攻击者假冒的后台数据库并不知晓移动读写器标识符IDR、标签标识符IDT，因此攻击者根本无法解密出正确的随机数rR、rT，攻击者计算得到的(M8、M9、M10、M11)亦是错误的，移动读写器验证后台数据库无法通过，攻击者假冒失败。综上描述，MAP能够抵抗攻击者的各种假冒攻击。

(6) 双向认证。因在移动RFID系统中，标签与读写器之间、读写器与后台数据库之间都是通过无线信道进行通信的，均不安全，因此每次信息传输都需要先对其进行认证。

• 标签对读写器的认证。读写器第一次传送消息给标签，标签通过步骤2完成对读写器的第一次验证；读写器在步骤10中第二次传送消息给标签，标签在步骤11中完成对读写器的第二次认证。

• 读写器对标签的认证。标签在步骤3中发送消息给读写器，读写器在步骤4中完成对标签的真伪鉴定。

• 读写器对后台数据库的认证。后台数据库在步骤8中向读写器传送消息，读写器在步骤9中完成对后台数据库真伪的鉴定。

• 后台数据库对读写器、标签的认证。为了能够抵抗去同步攻击，后台数据库同时存放Key_new、Key_old的值。在步骤5中读写器向后台数据库传送消息后，后台数据库在步骤6中实现对读写器的认证，在步骤7中实现对标签的认证。

通过上述描述，标签、读写器、后台数据库之间可以实现任意两者之间的相互认证，故MAP能够实现双向认证。

表3为本文MAP与其他移动RFID认证协议之间的安全性比较。

表3 认证协议安全性比较

注：×表示不能抵抗；√表示能够抵抗。

4 GNY逻辑形式化证明

(1) 协议形式化描述。为使MAP协议便于用GNY形式逻辑语言描述，现作如下约定：R表示移动读写器，T表示标签，DB表示后台数据库。MAP协议流程如下：

用GNY形式逻辑语言规范以上协议，可以描述如下：

Msg1：T<*{M0,M1,Query}。

Msg2：R<*{M2,M3,M4,M5}。

Msg3：DB<*{M3,M4,M6,M7}。

Msg4：R<*{M8,M9,M10,M11}。

Msg5：T<*{M9,M11,M12}。

(2) 协议初始化假设。MAP协议假设如下：R、DB、T表示主体，即R表示移动读写器，T表示标签，DB表示后台数据库。

Sup1：T(Key_R,Key_L,IDT,rT)；表示标签T拥有共享密钥值Key_R、Key_L，拥有自身标识符IDT及自身产生的随机数rT。

Sup2：R(Key_R,Key_L,IDR,rR)；表示移动读写器R拥有共享密钥值Key_R、Key_L，拥有自身标识符IDR及自身产生的随机数rR。

Sup3：DB(Key_R,Key_L,IDR,IDT,rDB)；表示后台数据库DB拥有共享密钥值Key_R、Key_L，拥有移动读写器R的标识符IDR及标签T的标识符IDT，拥有自身产生的随机数rDB。

Sup4：R|≡#(rR，rT，rDB)；表示移动读写器R相信随机数rR、rT、rDB是新鲜的。

Sup5：T|≡#(rR，rT，rDB)；表示标签T相信随机数rR、rT、rDB是新鲜的。

Sup6：DB|≡#(rR，rT，rDB)；表示后台数据库DB相信随机数rR、rT、rDB是新鲜的。

(3) 协议证明目标。MAP协议的证明目标主要有5个，即标签、移动读写器、后台数据库之间对彼此交互信息新鲜性的信任。目标的证明公式如下：

Goal1：T|≡R|～#(M0,M1)；

Goal2：R|≡T|～#(M2,M3,M4,M5)；

Goal3：DB|≡R|～#(M3,M4,M6,M7)；

Goal4：R|≡DB|～#(M8,M9,M10,M11)；

Goal5：T|≡R|～#(M9,M11,M12)。

(4) 协议证明过程。MAP协议的证明是在初始化假设的基础之上进行的，证明过程遵循文献[15]中的逻辑推理规则、告知规则、新鲜规则、拥有规则，消息解释规则遵循文献[15]中GNY逻辑推理规则的书写形式，分别用T、P、F及I表示。

因协议证明目标Goal2、Goal3、Goal4、Goal5的证明过程与协议证明目标Goal1的证明过程相似，故本节以协议证明目标Goal1为例，证明过程如下描述：

∴ T=#{M0,M1}

∴ T|≡#{M0,M1}

∴ T|=R～{M0,M1}

∵ 新鲜性定义以及推导出来的T=#{M0,M1}、T|=R～{M0,M1}

∴ Goal1：T|≡R|～#(M0,M1)得证明。

5 性能分析

移动RFID系统中包含标签、移动读写器、后台数据库，因后两者具备较强的计算能力及较大的存储量，对协议的性能影响不大，所以这里只针对标签一端的计算量及存储量进行分析。RFID认证协议的性能分析主要从以下4个方面进行：标签端的计算量、标签端的存储量、会话次数、协议的通信量。表4为本文MAP与其他认证协议之间的性能比较结果。

表4 认证协议性能比较

表4中：H表示哈希函数运算；M表示标量乘运算；S表示随机数运算；Sub表示位替换运算；N表示求余运算；PR表示伪随机数运算；P表示物理不可克隆函数运算；C表示交叉运算。由上文叙述可得，H、M、S、N、PR、P属于轻量级运算，而Sub、C属于超轻量级运算，即前者的运算量要比后者运算量大很多。考虑到按位“异或”运算、按位与运算的计算开销很小，因此在进行性能分析时予以忽略。设定共享密钥Key、标识符ID、各运算结果(各运算是指H、M、S、N、PR、P、Sub、C)的长度均为l。

(1) 标签的存储量及计算量。本文MAP中标签端只需要存放共享密钥Key、标签的标识符IDT两个量，根据前面的约定可知，标签端存储量为2l。相对于文献[7，10，12]来说，本文协议标签端的存储量已有所降低；相对于文献[8，11，13]来说，本文协议标签端的存储量与其相当。

在标签端的计算量方面，针对按位“异或”运算及按位与运算因计算开销小，不予考虑，故本文协议在标签端的计算量要远少于其他文献。本文协议标签端并未使用计算量较大的哈希函数或标量乘运算对信息进行加密，而是采用超轻量级的按位操作对信息进行加密，从而减少标签的计算量。综上描述，在标签的存储量及计算量方面，本文协议相比其他协议均有所改进。

(2) 通信量及会话次数。本文协议在通信量方面相对文献[7，10-11，13]而言，略大于上述文献中的通信量，但上述文献中均存在一些安全隐患，而本文协议弥补了上述文献中协议存在的缺陷问题。本文协议在通信量方面与文献[8，12]相当，同时解决了它们中存在的安全问题。

会话次数方面，众多协议大多是5次通信，本文协议在会话次数方面并无优势。综上所述，本文协议在整个通信量及会话次数两方面改进不大，相对其他协议并无优势，但解决了其他协议中存在的安全缺陷问题，故本文协议仍具备一定的实用价值。

6 结 语

本文描述传统RFID系统与移动RFID系统的不同点，指出传统RFID系统认证协议无法适用于移动RFID系统的特点，从而提出一种适用于移动RFID系统的认证协议MAP。阐述当前一些适用于移动RFID系统的认证协议中存在的缺陷及不足，然后提出改进的认证方案。所提MAP协议摒弃哈希函数加密的方法，采用按位操作对信息进行加密，使得协议可以达到超轻量级的级别；位替换运算的使用，增加了攻击者破解协议的难度；通过安全性及性能分析，表明了协议的安全性及优势之处所在；GNY逻辑形式化证明了MAP的正确性。MAP不仅适用于移动RFID系统，传统RFID系统也同样适用。下一步的研究方向：对MAP协议进行优化，合理降低整个通信的通信量；将采用MAP的移动RFID系统原型实现出来，搞清楚实现所需门电路总个数、一个完整通信时间等问题，做到理论与实际相结合。