基于伪随机数发生器的移动RFID双向认证算法

郝伟伟，吕 磊

(1.河南省市场监督管理局 信息中心，河南 郑州 450008；2.河南工业大学 信息科学与工程学院，河南 郑州 450008)

0 引 言

射频识别技术是一种不需要与特定商品相接触就可以识别内部存放信息的技术，该技术最早出现于20世纪，受限于20世纪科技等各方面制约，未能得到较大范围推广使用[1-2]。进入新世纪之后，伴随着云计算、大数据、物联网、区块链等新技术的不断产生，以及全球经济持续快速发展，使得射频识别技术再次得到发展机遇[3-4]。

一个经典的RFID系统至少包含有电子标签、读写器、后台服务器三者，受限于当时科技或人类需求等因素，电子标签与读写器间以无线方式交互数据，读写器与后台服务器间以有线方式交互数据。一般认为无线方式交互数据易被第三方人员窃听，存在一定安全风险，认为不安全、不可靠，而有线方式交互数据不易被第三方人员窃听，一般认为安全可靠[5-7]。但随着科技进步、人类需求越来越多，且越来越复杂，经典的RFID系统早已无法满足，出现了移动式RFID系统。该系统主要不同之处在于：读写器与后台服务器间也采用无线方式交互数据[8-9]。

为能够确保每个无线方式交互数据的安全性，需要设计新的可适用于移动式RFID系统的双向认证算法。文献[10]中提出的算法仅适合于在传统的RFID系统中使用，无法在移动式系统中使用，使用范围受到制约。文献[11]中设计的算法可在移动式RFID系统中使用，但算法采用传统的加密算法对消息进行加密，使得电子标签一端无法使用，该算法仅能在一些特定场合使用。文献[12]中提出的算法具有一定的安全性，但算法未考虑物理克隆的可能性，导致算法无法抵抗假冒攻击。文献[13]中的算法可使用在移动式系统中，但算法使用到不同类型的哈希函数对信息进行加密，使得电子标签一端无法推广使用。文献[14]中基于按位运算给出一种超轻量级的可在移动式系统使用的算法，但根据现有的研究表明，基于按位运算的算法本身安全性还有待商榷，因此该算法的安全性也有待商榷。限于篇幅，更多有关RFID双向认证可以参见文献[15-20]。

鉴于现有绝大多数算法无法适用于移动式RFID系统或计算量大或存在安全缺陷等不足，文中提出一种轻量级的可适用于移动式RFID系统的双向认证算法。

1 算法设计

本章节将从下面两个方面展开，首先对算法中出现的符号给予详细的含义描述，接着对算法具体实现步骤展开描述。

(1)算法符号说明及初始化。

DB表示后台服务器；

R表示读写器；

T表示电子标签；

K表示DB、R、T三者之间共享密钥；

IDR表示R的身份标志；

IDT表示T的身份标志；

x表示T生成的随机数；

y表示DB生成的随机数；

PR()表示伪随机发生器运算；

&表示按位与运算；

⊕表示按位异或运算。

(2)算法具体实现。

DB与R间以无线方式交换数据，R与T间以无线方式交换数据，都认定为不安全[21]。算法启动之前，即T离开工厂之前，经过初始化操作后，T、R、DB三者均存放有共享密钥K值，同时DB一端还存放有IDR、IDT。文中轻量级的移动RFID双向认证算法如图1所示。

图1 轻量级双向认证算法

文中算法具体步骤如下描述：

(1)读写器向电子标签发送一个Hello消息，用于告知电子标签开始双向认证算法。

(2)电子标签在收到读写器发送来的消息之后，电子标签首先产生一个随机数，可以标记为x；接着电子标签用产生的随机数x、自身存放的共享密钥K计算得到消息A=x⊕K、B=PR(x，K)，用产生的随机数x、自身存放的共享密钥K、自身存放的电子标签的标识符IDT计算得到消息C=PR(x⊕IDT，K)；最后将计算得到的消息A、B、C发送给读写器。

(3)读写器在收到电子标签发送来的消息之后，首先对消息A进行变形处理，可以得到随机数x'=A⊕K；接着读写器用变形处理得到的随机数x'、自身存放的共享密钥K计算得到一个消息B'=PR(x'，K)，并对比计算得到的消息B'与接收到的消息B值是否相等。

如果两者值不相等，说明电子标签无法通过读写器的验证，算法停止。

如果两者值相等，说明读写器验证电子标签成功。接着读写器用变形处理得到的随机数x、自身存放的读写器标识符IDR、接收到的消息C计算得到消息D=PR(C⊕x，IDR)；最后将消息A、D发送给后台服务器。

(4)后台服务器在收到读写器发送来的消息之后，首先对消息A进行变形处理可以得到随机数x''=A⊕K；然后利用计算得到的随机数x''、自身存放的共享密钥K、自身存放的电子标签的标识符IDT计算得到一个消息C'=PR(x''⊕IDT，K)，紧接着再用计算得到的消息C'、变形处理得到的随机数x''、自身存放的读写器的标识符IDR计算得到一个消息D'=PR(C'⊕x''，IDR)。并对比计算得到的消息D'与接收到的消息D值是否相等。

如果两者值不相等，表明读写器或电子标签中至少有一方是伪造的，算法停止。

如果两者值相等，可以说明电子标签和读写器同时通过后台服务器的验证。接着后台服务器生成一个随机数，可以标记为y，后台服务器利用生成的随机数y、计算得到的随机数x计算得到消息E=y⊕x；用生成的随机数y、自身存放的读写器的标识符IDR、自身存放的共享密钥K计算得到消息F=PR(y⊕IDR, K)；利用计算得到的随机数x、自身存放的电子标签的标识符IDT、自身存放的共享密钥K计算得到消息G=PR(x& IDT,K)。最后后台服务器将消息E、F、G发送给读写器。

(5)读写器在收到后台服务器发送的消息之后，先对消息E进行变形处理得到随机数y'=E⊕x；然后利用变形处理得到的y'、自身存放的共享密钥K、自身存放的读写器的标识符IDR计算得到一个消息F'=PR(y'⊕IDR，K)，并对比计算得到的消息F'与接收到的消息F值是否相等。

如果两者值不相等，说明后台服务器无法通过读写器验证，算法停止。

如果两者值相等，表明读写器对后台服务器的验证成功。读写器接着利用接收到的消息G、变形处理得到的随机数y'、自身存放的共享密钥K计算得到消息H=PR(G &y,K)。最后读写器将消息E、H发送给电子标签。

(6)电子标签在收到读写器发送来的消息之后，首先对消息E进行变形处理得到一个随机数y''=E⊕x；接着电子标签利用自身生成的随机数x、自身存放的电子标签的标识符IDT、自身存放的共享密钥K计算得到一个消息G'=PR(x& IDT, K)，利用变形处理得到的随机数y''、自身存放的共享密钥K、计算得到的消息G'计算得到一个消息H'=PR(G'&y'',K)，并对比计算得到的消息H'与接收到的消息H值是否相等。

如果两者值不相等，表明电子标签对读写器的验证失败，算法停止。

如果两者值相等，表明读写器通过电子标签的验证，且也可以说明后台服务器同时通过电子标签的验证，截止到此，双向认证算法顺利结束。

2 算法安全性分析

本章节将主要从双向认证、重放攻击等角度展开分析文中算法安全性。

(1)双向认证。

算法实现双向认证是一个最基本也是必须的要求，文中算法可以保证实现。

通过上一章节算法具体步骤描述可以看出，文中算法每会话实体在接收到消息之后，并不是马上回复消息来源方，而是先对消息来源方进行验证，只有在消息来源方通过接收方验证之后，消息接收方才会开始进行其他操作。一旦消息来源方无法通过接收方验证，则算法即刻停止。基于上述，可得知文中算法可以实现双向认证安全需求。

(2)重放攻击。

因移动式RFID系统中，任何两个会话实体之间的数据交换方式都是无线链路，无线链路固有的开放式，使得交互数据易被第三方人员窃听获取，并在下一轮会话中第三方人员重放窃听获取的之前的消息，以企图通过合法实体一方验证。

(3)假冒攻击。

从理论上来讲，第三方人员可以假冒成任何一个会话实体与其他会话实体进行通信，具体的：第三方人员可假冒成电子标签、可以假冒成读写器、可以假冒成后台服务器。鉴于篇幅有限等因素，此处仅选择第三方人员假冒成读写器与合法电子标签进行通信进行分析。

当第三方人员假冒成读写器时，第三方人员会给合法电子标签发送一个hello指令，合法电子标签收到消息后，经过一系列操作，最终会响应第三方人员，并给第三方人员返回一些合法消息，但该消息都是加密之后的密文。第三方人员接收到之后，需要先对部分消息解密以获取合法电子标签产生的随机数，从而才可以继续后面的破解操作。但因为第三方人员缺少DB、R、T三者间共享密钥，使得第三方人员无法正确破解出合法电子标签生成的随机数，第三方人员无法获取正确随机数值，就无法进行后面破解。第三方人员只能随机选择一些数据作为无法获取的正确值参与运算，并将运算结果发送给后台服务器。后台服务器收到消息后，只需要进行简单的验证，即可识别出消息来源方是假冒的，算法停止。第三方人员假冒失败，未能获取任何有用隐私信息。基于上述，可得知文中算法可以实现抵抗假冒攻击。

(4)追踪攻击。

第三方人员想要追踪电子标签的具体位置，则需要持续监听通信，以获取电子标签发出的消息，并对获取的消息进行分析，以确定电子标签位置。但文中算法对于第三方来说则无法完成消息分析，因消息加密过程中使用到电子标签生成的随机数x，将会使得电子标签每轮计算得到消息值发生变更，展现给第三方人员的将是电子标签不断处于变动状态，第三方根本无法追踪定位电子标签的具体位置。基于上述，可得知文中算法可以实现抵抗追踪攻击。

(5)前向安全性。

第三方人员想通过对监听获取的消息进行破解，以便可以分析出之前通信过程中涉及到用户的重要隐私信息，从而构成前向安全性。但文中算法，第三方人员无法破解分析出之前任何一轮通信中有关用户隐私信息，原因主要如下：每个消息加密过程中都参加入随机数，或加入随机数x或加入随机数y或同时加入随机数x、y，将使得每轮每个消息值都是处于变化状态中，当第三方人员对第i次通信消息进行分析，第i-1次消息值已变更，且前后两次消息值间无任何关联性。基于上述，可得知文中算法可以实现前向安全性。

(6)后向安全性。

所谓的后向安全性是说攻击者通过窃听可获取第i轮会话的所有消息，通过对第i轮消息的分析，企图预测出第i+1轮会话实体之间的通信消息，攻击者假冒成其中一方进行通信，破解出标签中更多的隐私信息，从而造成用户存放在标签中的隐私信息泄露。文中主要通过混入随机数的方式来解决上述问题，具体的分析过程如下：文中每个消息在加密的时候都至少加入一个随机数，或加入标签产生的随机数，或加入后台数据库产生的随机数，或同时加入标签和后台数据库产生的随机数，并且随机数每轮由随机数产生器随机产生，将会使得每轮用到的随机数的数值都是不相同的，且时时刻刻处于变动状态；再加上前后两轮随机数间并无关联性，将导致攻击者根本无法从当前通信的消息中分析出任何有帮助预测下轮会话的消息信息。从而使得攻击者按照自己计算的下轮会话消息进行假冒其中一方进行通信时，消息接收方仅只是需要进行简单的计算，即可识别出消息来源方并非真实可靠的会话实体，算法立刻结束，截至此时，攻击者并未获取或分析出有用的隐私信息。基于上述，文中算法能够抵抗后向安全性。

各算法之间的安全性对比见表1。

表1 各算法间安全性对比

3 算法性能分析

在移动式RFID系统中，虽包含电子标签、读写器、服务器三个实体，但只有电子标签在计算能力和存储方面受到严重制约，因此这里仅选择电子标签作为性能对比分析对象，具体见表2。

表2 不同算法间性能对比

对于表2里面部分符号给出下面的解释：约定所有算法中消息长度都为L。T1表示按位运算(比如异或运算、与运算、连接运算等)的计算时间，T2表示伪随机发生器运算的计算时间，T3表示哈希函数运算的计算时间(不同形式的哈希函数计算时间可能存在差别，这里统一看成相同的计算时间)，T4表示可基于按位运算实现的超轻量级的运算计算时间，T5表示物理不可克隆函数的计算时间，T6表示模运算的计算时间。

在上述涉及到的运算中，T1和T4的计算时间最短，可称之为超轻量级的计算；T3、T5、T6的计算时间最长；T2的计算时间介于上述两者之间。各运算的运算时间可大致按照如下方式由小到大进行排序：T1

存储量的由来：电子标签一端存放的数据有IDT、K，根据上述约定，可得知存储量为2L。

通信量的由来：一个DB、R、T三者间完整通信包含的消息有，A消息2次、B消息1次、C消息1次、D消息1次、E消息2次、F消息1次、G消息1次、H消息1次、Hello指令1次，其中Hello指令消息仅需要1 bit来存放即可，故一个完整会话过程中的通信量为10L+1 bit。

电子标签一端计算量的由来：在计算消息A时第一次用到按位异或运算，在计算消息B、C、G'、H'时分别依次第一次、第二次、第三次、第四次用到伪随机数发生器运算，在计算随机数y''时第二次用到按位异或运算。因此，电子标签一端总的计算时间为2T1+4T2。

通过表2综合分析可得知，在通信量和存储量方面文中算法与其他算法大致相当；在计算量方面，文中算法比文献[14]中算法计算量要大，比其他文献中算法计算量都要小。但文献[14]中算法存在一定的安全缺陷，文中算法可以弥补其算法不足。综合安全性和性能两方面分析，文中算法在计算量角度存在一定的优势，同时安全方面可弥补其他算法存在的安全隐患问题，使得文中算法具有推广使用价值。

4 逻辑化形式证明

(1)形式化模型。

Msg1：R→T:Hello

Msg2：T→R:A,B,C

Msg3：R→DB:A,D

Msg4：DB→R:E,F,G

Msg5：R→T:E,H

(2)初始化假设。

读卡器R所拥有的：

电子标签T所拥有的：

A3：TK

后台服务器DB所拥有的：

读写器R对拥有信息新鲜性的相信：

A8：R|≡#(x)

A9：R|≡#(y)

电子标签T对拥有信息新鲜性的相信：

A10：T|≡#(x)

A11：T|≡#(y)

后台服务器DB对拥有信息新鲜性的相信：

A12：DB|≡#(x)

A13：DB|≡#(y)

后台服务器DB与电子标签T间彼此相信共享信息：

电子标签T与后台服务器DB间彼此相信共享信息：

读写器R与后台服务器DB间彼此相信共享信息：

后台服务器DB与读写器R间彼此相信共享信息：

电子标签T与读写器R间彼此相信共享信息：

读写器R与电子标签T间彼此相信共享信息：

(3)证明目标。

G1：T|≡R|～#(E)

G2：T|≡R|～#(H)

G3：R|≡T|～#(A)

G4：R|≡T|～#(B)

G5：R|≡T|～#(C)

G6：DB|≡R|～#(A)

G7：DB|≡R|～#(D)

G8：R|≡DB|～#(E)

G9：R|≡DB|～#(F)

G10：R|≡DB|～#(G)

(4)推理证明。

因为上面十个需要证明的目标证明过程大致相同，同时加上篇幅有限等因素，文中这里仅选择证明目标G1为例进行推导证明，具体证明推导过程如下：

在Msg5中，R◁*x，即Rx，同时结合初始化假设A3、A4和规则P2可得知：T(x,IDT)。

接着，由已推导出的T|≡#(x,IDT)、T(x,IDT)，再根据新鲜性规则可得知：T|≡#(E)。

由新鲜性的定义可推导出证明目标G1：T|≡R|～#(E)。

5 结束语

文中介绍了经典的RFID系统的优缺点，提出一个适用于移动RFID系统的双向认证算法。该算法不仅可使用在经典的RFID系统中，同时也可适用于移动RFID系统中，具备更为广泛的使用推广范围；算法采用伪随机数发生器对发送隐私信息进行加密，能够确保信息安全性，同时随机数数发生器的使用，可在一定程度上减少系统整体计算量。从不同类型攻击方式对算法进行安全性分析，表明算法能够提供抵抗常见类型攻击方式安全需求；同时从计算量、通信量角度对算法进行性能分析，表明算法具有较低的计算开销。