位替换运算的超轻量级移动RFID认证协议

梅松青，邓小茹

广州医科大学，广州510006

1 引言

射频识别技术出现于二十世纪三四十年代，大面积推广在二十世纪九十年代。因当时技术受限，及人们需求不大等众多因素，射频识别技术在应用中的RFID系统中读写器与服务器之间基于有线连接链路进行信息交换，该交换方式一般认定为安全可靠，并将该系统称之为传统的RFID系统[1-2]。

进入二十一世纪，伴随着科技的快速发展，以及人类需求的增长，传统的RFID系统早已无法满足人们的需求，于是导致移动式RFID系统的产生[3]。移动式RFID系统区别于传统的RFID系统最大的不同之处在于：移动式RFID系统中读写器与服务器之间的通信不在基于有线连接链路，而是采用无线连接线路进行信息传送。无线链路因其自身固有的属性，使得该传输方式存在一定的安全隐患[4-5]。适用于传统RFID系统的双向认证协议不再适用于移动式RFID系统中，因此需要设计适用于移动式的RFID系统的新双向认证协议。

在分析近些年提出的适用于移动式RFID系统协议的基础之上，文中给出一种基于位替换运算的超轻量级的适用于移动式的RFID系统的双向认证协议。为达到降低通信实体计算量的目标，设计的协议采用位运算进行信息的加密；同时对协议进行基于GNY逻辑形式化分析和安全性分析。

2 相关工作

文献[6]中提出单向认证的移动认证协议，分析发现该协议无法抵抗中间人攻击及重放攻击。文献[7]中提出了一种基于椭圆曲线的移动认证协议，但分析发现，该方案不能确保读写器端隐私的安全，同时标签端的计算量也较大。

文献[8]中给出一个轻量级的移动双向认证协议，协议对信息的加密主要基于PUF函数（物理不可克隆函数）。对协议进行分析：协议无法抵抗异步攻击。攻击者通过监听可获取完整的通信消息，在阻塞通信实体会话过程时，攻击者通过将监听获取的信息进行重放多次，即可使得标签一端与后端服务器之间的共享加密密钥失去一致性，使得攻击者发起的异步攻击成功。

文献[9]中设计出一个超轻量级的移动认证协议，该协议基于按位操作实现对信息的加密。对协议研究：攻击者可以通过一定的物理手段获取隐私信息，从而使得攻击者可以假冒成标签或其他通信实体进一步进行攻击，以便于获取更多的隐私信息，使得攻击者发起的假冒攻击成功。

文献[10]中提出的基于Edwards曲线的移动协议，分析可得知该协议在认证过程中并未实现读写器对标签的认证，使得攻击者可以假冒标签发送信息，从而使得协议无法抵抗标签假冒攻击。

文献[11]提出一个移动双向认证协议，该协议具备一定的安全性。对协议分析：协议未提供标签一端对读写器的认证，使得攻击者可以假冒成读写器给标签发送信息，以便于攻击者通过标签的验证，获取标签反馈的信息，对消息进行分析，使得攻击者发起的假冒攻击有效。

鉴于篇幅有限，更多移动式RFID系统双向认证协议可以参见文献[12-16]。

鉴于上述移动式双向认证协议存在的计算量大、通信复杂或存在安全缺陷等不足，文中设计出一种能够满足较高安全需求的认证协议MSB。MSB协议采用位替换运算对所要传送的信息进行加密，尽可能降低通信实体的计算量；为能够增大攻击者的破解难度，所有信息加密过程中混入随机数。对协议进行安全性分析和性能分析，表明协议具备较高的安全性，且协议能够适用于移动式的无源标签系统中。

3 MSB设计

3.1 符号说明及协议初始化

为便于文中描述，用符号Bro(X,Y)表示位替换运算（Bit Replacement Operation，Bro）。位替换运算按如下定义进行计算：X和Y属于二进制序列，长度均为L位；对X和Y均从左向右依次遍历，当X上的数为0时，将Y上相对应的数替换（0替换为1，1替换为0），X上的数为1时，Y不做任何操作，从而形成一个新的二进制序列Z，即Z=Bro(X,Y)。

为便于对位替换运算的理解，文中给出如下例子进行解释：取L=8位，X=01100101，Y=00001100，则根据上述有关位替换运算的定义可得Z=Bro(X,Y)=10010110。具体示意图见图1所示。

图1 位替换运算示意图

对协议中出现的符号进行如表1说明。

表1 符号说明

认证协议开始之前，对协议中的所有通信实体进行初始化操作，初始化完成之后，各通信实体存放信息如下：标签端存放(KL,KR,IDTag)；移动读写器端存放(KL,KR,IDReader)；服务器端存放(KL,KR,IDTag,IDReader)。

3.2 MSB认证流程

双向认证协议MSB认证过程描述可参见图2所示。

图2 MSB认证示意图

对图2中双向认证协议出现的符号进行如表2中的公式说明。

表2 公式说明

结合图2双向认证协议MSB具体过程描述如下：

步骤1读写器产生随机数rReader，然后计算A和B，最后将＜Query,A,B＞一并传送给标签。

其中A和B计算过程详细见表2所示。

步骤2标签比对A⊕KR与B⊕KL是否相等。若A⊕KR=B⊕KL，则读写器通过验证，然后标签产生随机数rTag，接着计算C、D、E、F，最后将＜C,D,E,F＞一并传送给读写器，以表示标签对读写器的响应。若A⊕KR≠B⊕KL，表明读写器是伪造的，协议停止。

其中C、D、E、F计算过程详细见表2所示。

步骤3读写器通过计算(rReader&KR)⊕C得到随机数rTag；然后将计算所得随机数rTag，结合rReader、KL进行计算得到F′，比对F′与F是否相等。

若F′=F，表明读写器计算所得随机数rTag与标签产生的随机数rTag是相同的，且标签通过验证，然后读写器再计算G和H，最后将＜D,E,G,H＞一并传送给服务器。

若F′≠F，说明标签是伪造的，协议停止。

其中F′=Bro(rReader&KL,(rReader&KR)⊕C)；G、H计算过程详细见表2所示。

步骤4服务器分两步进行，先对读写器进行验证，当且仅当读写器验证通过，再对标签进行验证。

（1）对读写器的验证

服务器通过计算G⊕IDReader得到随机数rReader；然后将计算所得随机数rReader，结合IDReader、KL进行计算得到H′，比对H′与H是否相等。

若H′=H，表明服务器计算所得随机数rReader与读写器产生的随机数rReader是相同的，且读写器通过验证，然后服务器开始对标签的验证。

若H′=H，服务器将用Kold替换Knew再次进行计算H″。将再次比对H″与H是否相等。如果H″=H，表明读写器通过验证，然后服务器开始对标签的验证。如果仍然H″=H，说明读写器是伪造的，协议停止。

其中H′=Bro((G⊕IDReader)⊕(IDReader&KL),(G⊕IDReader)&IDReader)、H″=Bro((G⊕IDReader)⊕(IDReader&G⊕IDReader)&IDReader)。

（2）对标签的验证

服务器通过计算(IDTag&KL)⊕D得到随机数rTag；然后将计算所得随机数rTag，结合KR进行计算得到E′，比对E′与E是否相等。

若E′=E，表明服务器计算所得随机数rTag与标签产生的随机数rTag是相同的，且标签通过验证，然后服务器进行步骤（1）。

若E′≠E，服务器将用Kold替换Knew再次进行计算E″。将再次比对E″与E是否相等。如果E″=E，表明标签通过验证，然后服务器进行步骤（1）。如果仍然E″≠E，说明标签是伪造的，协议停止。

其中E′=Bro((IDTag&KL)⊕D,((IDTag&KL)⊕D)⊕KR)、E″=Bro((IDTag&)⊕D,((IDTag&⊕D)⊕

步骤（1）：服务器产生随机数rDataBase，然后计算I、J、M、N；接着服务器开始进行信息更新Kold=K、K=Knew；最后将＜I,J,M,N＞一并传送给读写器，以表示服务器对读写器的响应。

其中Knew=Bro(rDataBase⊕rTag⊕rReader,K)；J、M、N计算过程详细见表2所示。

步骤5读写器通过计算I⊕(rReader&IDReader)得到随机数rDataBase，然后将计算所得随机数rDataBase，结合IDReader、rReader进行计算得到M′，比对M′与M是否相等。

若M′=M，表明读写器计算所得随机数rDataBase与服务器产生的随机数rDataBase是相同的，且服务器通过验证；然后读写器计算Q；接着读写器开始进行信息更新K=Bro(rDataBase⊕rTag⊕rReader,K)；最后将＜J,N,Q＞一并传送给标签。

若M′≠M，说明服务器是伪造的，协议停止。

其中M′=Bro(rReader,(I⊕(rReader&IDReader))&IDReader)；Q计算过程详细见表2所示。

步骤6标签需要完成对读写器和服务器的验证。

（1）对服务器的验证

标签通过计算J⊕(rTag&IDTag)得到随机数rDataBase，然后将计算所得随机数rDataBase，结合rTag、IDTag计算得到N′，比对N′与N是否相等。

若N′=N，表明标签计算所得随机数rDataBase与服务器产生的随机数rDataBase是相同的，且服务器通过验证，然后标签开始对读写器进行验证。

若N′≠N，说明服务器是伪造的，协议停止。

其中N′=Bro(rTag,(J⊕(rTag&IDTag))&IDTag)。

（2）对读写器的验证

标签通过上述（1）中计算得到的随机数rDataBase，结合rTag、rReader计算得到Q′，比对Q′与Q是否相等。

若Q′=Q，表明读写器通过验证，接着标签开始更新信息K=Bro(rDataBase⊕rTag⊕rReader,K)；待信息更新完成，通信实体之间的认证结束。

若Q′≠Q，说明读写器是伪造的，协议停止。

其中Q′=rReader&(J⊕(rTag&IDTag))&rTag。

4 协议全性分析

（1）重放攻击

攻击者想要发起重放攻击需先进行窃听以获取上一轮通信消息，通过将窃听所获取再次发送给通信系统中的一方，以企图验证通过，从而获取相对应的隐私信息。文中协议为抵抗攻击者发动的重放攻击，在所有通信消息加密过程中全部混入随机数，使得前后两轮通信中消息并不一致。因随机数随机产生，且具备不重复性，使得混入随机数加密的通信消息前后不同，且无法预测。因此，当攻击者重放监听获取上一轮消息时，当前正在进行的通信中用到的消息值早已发生变化，故攻击者发动的重放攻击失败，协议能够抵抗重放攻击。

（2）异步攻击

攻击者通过某种手段使得通信系统中，其中一方通信实体加密用到的共享密钥进行更新，而另一方通信实体加密用到的共享密钥未进行更新或更新过程中用到的参数值不同，从而使得两个通信实体之间共享密钥失去一致性。文中协议为抵抗异步攻击，在服务器端特地存放当前一轮通信过程中的共享密钥值，且同时保存上一轮通信中用到的共享密钥值。当服务器用当前密钥无法验证读写器或标签之时，将会调用上一轮密钥再次发起对标签或读写器的验证，以此方法来抵抗攻击者发起的异步攻击。基于上述，协议能够抵抗异步攻击。

（3）中间人攻击

攻击者通过窃听一个会话过程，以此获取通信消息，对获取的消息进行删除或篡改等操作，以发起中间人攻击，达到通过通信实体验证通过的目的。文中协议为抵抗该种攻击方式，信息加密过程中引入随机数，对于攻击者来说并不知道每轮加密过程中用到的随机数；且因随机数随机产生，具备无法预测性，因此攻击者再不知道随机数的前提下，想要发起中间人攻击，就只能随机选择一个数作为随机数进行消息的修改或篡改。当系统中任何一个通信实体接收到消息后，通过简单的计算就可以识别出消息发送源是伪造的，协议立刻停止。基于上述，因此协议能够抵抗中间人攻击。

（4）前向安全

前向安全是指攻击者通过某种手段获取的当前通信中的消息，对该消息进行各种方式的分析，也无法预测出下一轮通信过程中用到的消息的值，以保证隐私信息的安全性。文中协议为确保能够提供前向安全需求，标签一端通过随机数rTag来保证消息的新鲜性；读写器一端通过随机数rReader来保证消息的新鲜性；服务器一端通过随机数rDataBase来保证消息的新鲜性。随机数每轮都是随机产生，且具备无法预测性和不重复性，使得攻击者根本无法预测下轮通信中加密用到的随机数，自然使得攻击者无法通过当前获取的消息分析出任何有用的隐私信息。基于上述，协议能够提供前向安全。

（5）假冒攻击

假冒攻击是指攻击者伪装成通信实体中的一方向另外的通信实体发送消息，以通过验证，并获取相关隐私信息。文中协议中通信实体有三个：标签、读写器、服务器。对于攻击者来说，可以伪装成任何其中的一方发起重放攻击，鉴于篇幅有限，此处仅选择攻击者伪装成标签发起假冒攻击。

当攻击者伪装成标签之时，向读写器发送消息。攻击者要想向读写器发送的消息通过读写器的验证，则攻击者需要计算出正确的＜C、D、E、F＞值。但对于攻击者来说，是不可能做到正确计算上述四个通信消息的值，原因如下：攻击者不知晓共享密钥K的情况，是不可能通过消息A和B计算得到正确的随机数rReader的值；没有正确的随机数rReader的值，就不可能进行正确的＜C、D、E、F＞的计算。当攻击者无法获取随机数rReader的值之时，攻击者只能随便选择一个数充当该随机数进行计算，由此可推测出，攻击者计算得到的＜C、D、E、F＞的值肯定都是错误。当读写器收到消息后，进行简单的计算，即可辨别出消息发送源是伪造的，协议停止，攻击者未获取任何有用的信息。因此，协议能够抵抗假冒攻击。

（6）双向认证

双向认证是一个认证协议应具备的最基本的安全要求。协议中的双向认证包含三部分：读写器与标签之间的双向认证、读写器与服务器之间的双向认证、标签与服务器之间的双向认证。该三部分双向认证分析过程相类似，鉴于篇幅有限，此处选择读写器与标签之间的双向认证为例子进行阐述。

根据上述有关于MSB协议的描述可得知：在步骤2中标签通过A和B第一次对读写器进行认证；在步骤6中标签通过Q将再一次对读写器进行认证。而读写器对标签的认证是在步骤3中通过C和F完成的。有关于两者之间具体的双向认证是如何实现的，可以详见前文中有关MSB协议的步骤阐述。基于上述，协议能够提供通信实体之间的双向认证。

本文协议与其他此类协议进行安全性比对，比对结果见表3所示。

5 基于GNY逻辑形式化分析

（1）协议形式化描述

双向认证协议采用GNY逻辑形式化描述如下：

表3 协议安全性比较

消息1 T＜*[A,B,Query]；

消息2 R＜*[C,D,E,F]；

消息3 DB＜*[D,E,G,H]；

消息4 R＜*[I,J,M,N]；

消息5 T＜*[J,N,Q]。

其中，T表示标签，R表示读写器，DB表示服务器。

（2）协议初始化假设

假设1 TЭ(K，rTag，IDTag)；表示标签拥有共享密钥K、标签标识符IDTag、标签产生随机数rTag。

假设2 RЭ(K,IDReader,rReader）；表示读写器拥有共享密钥K、读写器标识符IDReader、读写器产生随机数

假设3 DBЭ(K,IDReader,rReader,rTag,rDataBase,IDTag)；表示服务器拥有共享密钥K、读写器标识符IDReader、标签标识符IDTag、读写器产生随机数rReader、服务器产生随机数rDataBase、标签产生随机数rTag。

假设4 R|≡#(rReader,rDataBase,rTag）；表示读写器相信随机数rReader,rDataBase,rTag新鲜性。

假设5 T|≡#(rReader,rDataBase,rTag）；表示标签相信随机数rReader,rDataBase,rTag新鲜性。

假设6 DB|≡#(rReader,rDataBase,rTag）；表示服务器相信随机数rReader,rDataBase,rTag新鲜性。

假设7 T|≡DB；表示标签相信标签、读写器、服务器三者之间共享密钥K。

假设8 R|≡TDB；表示读写器相信标签、读写器、服务器三者之间共享密钥K。

假设9 DB|≡TDB；表示服务器相信标签、读写器、服务器三者之间共享密钥K。

假设10 T|≡D；表示标签相信标签、服务器之间共享的信息IDTag。

假设11 DB|≡DB；表示服务器相信标签、服务器之间共享的信息IDTag。

假设12 R|≡DB；表示读写器相信读写器、服务器之间共享的信息IDReader。

假设13 DB|≡DB；表示服务器相信读写器、服务器之间共享的信息IDReader。

（3）协议证明目标

双向认证协议需要证明的目标有五个，如下：

目标1 T|≡R|～#(A,B)；

目标2 R|≡T|～#(C,D,E,F)；

目标3 DB|≡R|～#(D,E,G,H)；

目标4 R|≡DB|～#(I,J,M,N)；

目标5 T|≡R|～#(J,N,Q)。

（4）协议证明过程

GNY逻辑包含多种运算法则，此处用T表示逻辑推理规则；用P表示告知规则；用F表示新鲜规则；用I表示拥有规则[17-18]。

上述五个证明目标的证明过程相类似，此处选择目标Goal1为例子进行证明。鉴于篇幅有限，其他证明目标的详细证明过程不再阐述。

∴TЭ{A,B}

∴T=#{A,B}

∴TЭ{A,B}

∴T|≡#{A,B}

∵规则I3又∵假设7：T|≡R↔KT↔KDB、假设8：R|≡T↔KR↔KDB以及消息1：T＜*【A,B,Query】

∴T|=R～{A,B}

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

∴目标1：T|≡R|～#(A,B)得证明。

6 性能分析

在移动式的RFID系统中一共有三个通信实体：标签、读写器、服务器。读写器与服务器两者均有较大的存储空间和较强的计算能力，而标签并不具备上述优点，因此在性能分析时，一般选择标签为研究对象，从标签一端的计算量和存储量两个角度进行性能分析。本文协议与其他类型协议进行性能分析结果见表4所示。

表4 协议性能比较

对表4中出现的符号进行下面的解释说明：pa表示哈希函数的计算量；pb表示标量乘运算的计算量；pc表示伪随机数函数的计算量；pd表示模运算的计算量；pe表示物理不可克隆函数的计算量；pf表示交叉运算的计算量；pg表示产生随机数的计算量；ph表示位替换运算的计算量；pi表示位运算的计算量（此处的位运算是指包含与运算、异或运算等）。

在上述运算的计算量中，pa、pb、pc、pd、pe、pg属于轻量级的计算；pf、ph、pi属于超轻量级的计算。专家学者一般认定为一次轻量级的计算量相当于几十次甚至上百次超轻量级的计算量；因此协议运行过程中，相对于轻量级的计算而言，超轻量级的计算次数多几次，甚至多十几次，对于整个系统的总体计算量影响是很小的，几乎可忽略不计。文中协议涉及的运算包含三种：产生随机数的计算、位替换运算，位运算；其中产生随机数的计算有且只有一次，即轻量级的运算次数只有一次，其他运算均属于超轻量级的计算。文中协议与其他此类协议进行计算量角度的比较：文中协议在标签一端的计算量方面具备一定的优势，计算总量明显少于其他协议计算总量。

标签一端主要用于存放标签标识符IDTag、通信实体之间的共享密钥K两个参数。约定IDTag、K的长度均为l位，因此文中协议标签一端的存储量为2l。

7 结束语

介绍传统RFID系统无法满足人们需求，使得移动式RFID系统的产生，但适用于传统RFID系统的协议无法满足移动式RFID系统，文中为解决该问题，提出一种能够运用在移动式RFID系统的认证协议。所提协议基于位替换运算实现对传输信息的加密，位替换运算可采用按位运算实现，一定程度上降低了通信实体的计算量；为保证通信消息的安全性，所有信息先加密再传输，同时所有信息加密过程中混入随机数，增大攻击者的破解难度。从不同的攻击类型角度出发对协议进行安全性，表明协议具备较高的安全性；以标签为对象对协议进行性能分析，表明协议能够适用于无源标签系统中；同时基于GNY逻辑对协议进行形式化推理证明。下一步的研究方向为将设计的协议运用在具体的移动RFID系统中，对协议运行的具体时间等参数进行统计研究分析。