按位运算的RFID系统密钥无线生成算法

曹朝阳 吴庆涛

1(河南省市场监督管理局 河南 郑州 450008)2(郑州航空工业管理学院 河南 郑州 450015)

0 引 言

无线射频识别(Radio Frequency Identification，RFID)是一种非接触式、自动识别和采集信息的综合性技术[1-3]。RFID系统具备成本低、易携带、寿命长等优点，已经运用在身份识别等各个领域中[4-6]。

为推动RFID系统更进一步发展及应用，研究人员提出许多方法来解决安全问题，其中标签与读写器之间的双向认证尤为突出。两个通信实体在双向认证过程中，涉及共享密钥重要参量[7-9]。

现有的双向认证协议中用到的共享密钥大多都是在标签出厂之前设定好的，这种做法有一定的好处，但也存在一定的缺陷：(1) 会带来密钥托管问题，负责托管的人员可能会因托管不当而导致密钥泄露；(2) 密钥始终只能由厂商设定，无法由用户自己设定，在一定程度上无法满足用户自定义密钥的需求。基于以上缺陷，专家及学者提出在标签与读写器之间动态地生成共享密钥，既可以避免因托管人员管理不当而造成的密钥泄露问题，也可以满足用户自定义密钥的需求。

1 相关工作

文献[10]创新地利用RFID系统信道的前后非对称性特征，设计出一种动态生成共享密钥的算法。该算法能够弥补提前设定密钥的不足，但仍存在一定缺陷：协议基于后向信道的不可窃听性，在标签传送给读写器信息时，采用明文直接传送。但在实际应用中，后向信道仍存在被攻击者窃听的可能性，具有一定的局限性。

文献[11]在文献[10]的基础之上提出一种动态生成共享密钥的算法，遵行前向信道与后向信道均能被攻击者窃听的原则，弥补了文献[10]算法的不足，但其在设计过程中未全面考虑，导致攻击者在阻塞读写器到标签的最后一个消息情况下，读写器生成密钥的同时，标签不能生成密钥，标签与读写器两端失去一致性，因此算法无法抵抗去同步化攻击。

文献[12]算法采用动态生成密钥的思想，仍遵行前后向信道均可被攻击者窃听原则。算法设计过程中，采用对部分ID加密的机制进行信息的传输，能够增大攻击者的破解难度，但算法无法抵抗攻击者发起的重放攻击。攻击者在窃听到上一轮信息后，对消息进行重放，并阻塞标签与读写器之间的通信，破解出相关隐私信息。

文献[13]基于假名设计出一种密钥无线生成算法，该算法虽能够弥补文献[10]算法的不足，但无法抵抗去同步化攻击。攻击者可以截获通信实体之间传送的消息C，从而导致合法标签无法验证消息C，使得标签一端无法生成共享密钥，但读写器一端却已生成共享密钥，最终导致标签与读写器之间的共享密钥失去一致性。

综上，本文设计出一种采用位运算的低计算量的共享密钥无线生成算法。利用标签的假名标识符ID_S进行传输信息的加密计算，减少其他变量的引入，有助于降低存储空间；假名标识符的使用，在一定程度上可避免标签唯一标识符ID的泄露；采用计算量较低的位运算进行加密，可有效减少系统整体计算量；采用标签一端不生成随机数机制，降低标签端的门电路总量，有助于成本的降低。

2 密钥无线生成算法

2.1 符号说明

标签、读写器、后台数据库三部分组成一个完整的RFID系统。系统在通信过程中，读写器与后台数据库之间采用安全的有限信道进行通信，故可将两者看成一个整体；标签与读写器之间的通信采用不安全的无线信道[14-15]。有关符号的含义如表1所示，其中L取值为偶数值。

表1 符号说明

2.2 密钥生成

共享密钥动态生成开始之前，Tag存有(id,ids)；Reader存有(id_i,ids_i)。参考文献[10]可以得知：密钥生成算法需要分三种情况讨论，具体如下：

1) 单标签密钥生成算法。算法流程如图1所示。

图1 单标签密钥生成算法流程

算法过程简述如下：

(1) 读写器向标签发出通信请求命令。

(2) 标签计算消息A；将A传给读写器。其中A=id_r⊕ids_l。

(3) 读写器查找存放的(id_i,ids_i)中是否有满足A的计算结果。如未找到，算法停止。如找到，生成随机数r；计算消息B和C、共享密钥k；将B、C传给标签。其中B=r⊕ids_r，C=r⊕id_l。

说明：r长度为L位，ids_r、id_l长度为L/2位，在计算过程中将ids_r、id_l的高位部分补L/2个0，从而使得ids_r、id_l、r长度均为L位，便于计算。后面涉及长度不同的地方进行计算时，按照此计算法则进行。

(4) 标签对B、C进行验证(B⊕ids_r是否等于C⊕id_l)。如不相等，算法停止；如相等，计算共享密钥k。其中k= (r⊕id)⊕(r⊕ids)。

2) 多标签密钥生成算法。多标签密钥生成算法过程与单标签密钥生成算法过程主要不同之处在于：每个不同的标签在接收到读写器发送来的消息且通过验证之后，共享密钥k的生成过程中需要根据每个标签的自身信息(id_i,ids_i)来生成属于自身的个体密钥。其他思想一样，故不再阐述。

3) 群组标签密钥生成算法。算法流程如图2所示。

图2 群组标签密钥生成算法流程

算法流程如下：

(1) 读写器向标签组广播通信请求命令。

(2) 标签Tagi计算消息Qi；将Qi传给读写器。i=1,2,…,n。其中Qi=id_i_r⊕ids_i_l。

(3) 后台数据库中查找已存放的信息并计算是否与Qi信息完全一致。如不完全一致，说明有标签未响应，第二次发送请求命令。如一致，生成随机数r；计算唯一的共享密钥k；同时为标签Tagi生成唯一的密钥因子ki；将ki发给所有标签。其中k=ids_1_r⊕ids_2_r⊕…⊕ids_i_r⊕r，ki=k⊕ids_i_r。

(4) 标签Tagi将自身的标号与ki中的i值作对比。如不相等，不做任何操作；如相等，计算唯一共享密钥k。其中k=ki⊕ids_i_r。

3 安全性分析

算法的安全性分析一般从两个角度进行阐述：(1) 对算法进行抽象，进而采用逻辑化形式进行分析，文中采用基于BAN的逻辑形式化证明对算法进行逻辑形式化分析，来说明算法的安全性。(2) 从具体的攻击方式对算法的安全性进行分析。具体的攻击方式主要分为两大类：主动攻击及被动攻击。最常见的被动攻击方式为监听。而主动攻击的方式较多，比较常见的有：异步攻击、重放攻击、追踪攻击等。

据了解，本次技能大赛分为初赛、决赛两部分，60%的参赛人员通过初赛考核，可进入决赛环节。在决赛之前，青岛市家庭服务业生态圈统一组织入围参赛者接受为期1个月的培训。通过决赛阶段综合笔试和实操两项成绩，最终评选出“首席家庭服务员”8人、“首席婴幼儿营养烹饪师”“首席母婴护理师”各10名，共28位首席技师，优胜奖50名，由青岛市家庭服务产业生态圈颁发荣誉证书并授予称号，举行优胜获奖者与客户供需见面会，为岛城家庭服务市场输送优质服务人员。

攻击者通过监听、跟踪等方式获取通信实体之间的通信消息，该种攻击方式称之为被动攻击。对于通信实体而言，当被动攻击发生之时，通信实体绝大多数情况下是不知晓的。因此，为确保传输信息的安全性，算法必须能够抵抗攻击者发起的被动攻击，即：在通信实体不知被监听的情况下，攻击者获取通信信息，亦无法破解出有用的隐私信息。与被动攻击有所不同的是，攻击者在发起主动攻击之时，通信实体通过实体之间的双向认证是可以识别出真伪的。较为常见的主动攻击方式有重放攻击、追踪攻击等。

单标签密钥生成算法与多标签密钥生成算法大体一致，可将两种算法放在一块进行分析讨论。采用监听的方式可以获取一个通话中所有的消息，但攻击者仍无法得到所想要的信息。原因如下：(1) 攻击者不知晓id、ids，因此无法从A、B或C中逆推出共享密钥；(2)A、B、C在计算过程中，对于攻击者来说，都至少有两个变量是不知晓的，因此无法穷举；(3) 计算过程中，混入随机数r，使得前后两次数值并不一样，增大破解难度；(4)A、B、C加密过程中涉及的参量值，在通信过程中都没有明文出现过。基于上述分析，攻击者无法破解出有用的信息。

对群组标签密钥生成算法进行被动攻击及主动攻击分析。攻击者通过监听一个完整的通信过程，可获取如下信息：Qi、ki。攻击者通过这些消息仍无法破解出有用的隐私信息，原因如下：(1)Qi加密过程中，有两个变量，对于攻击者来说，是事前不知晓的，因此攻击者无法穷举；(2)ki仅仅只是计算共享密钥k的一个密钥因子，攻击者即便是可以获取，但仍无任何用处，因为由ki计算出k需要每个标签相对应的假名，但攻击者无法获取该变量；(3)k在计算过程中，因随机数r的加入，使得k前后两次的数值并不一致；(4)k的计算，需要群组标签里的每个标签的假名变量，对于攻击者来说，这些信息是无法获取的。基于上述原因，攻击者通过监听获取的信息，不足以破解出有用的隐私信息。

本文算法与其他此类密钥动态生成算法进行安全性分析比较，结果如表2所示。表中，×表示不能抵抗；√表示能够抵抗。

4 BAN逻辑形式化证明

采用基于BAN逻辑[16]对算法进行形式化分析：R表示读写器与后台数据库的整体；T表示标签。选取单标签密钥生成算法为例进行证明，其他两种场合的算法证明分析过程类似。

1) 理想化模型：

消息① R→T：Request；

消息② T→R：A；

消息③ R→T：B，C。

2) 初始假设：

P7：R|≡T|⟹A；P8：T|≡R|⟹B；P9：T|≡R|⟹C。

3) 安全目标：

G1：T|≡B；G2：T|≡C；G3：R|≡A。

4) 分析推理：

G2、G3同理。

5 性能分析

性能分析部分选取单标签密钥生成算法为例。其他两种算法可参考表3的分析过程及方法。

表3 性能分析

表3中，符号XOR表示“异或”运算的计算量，符号AND表示“与”运算的计算量，符号R表示移位运算。id、ids长度一致，用L表示。

综合性能分析的三个方面来看，本文算法的计算量明显多于文献[10]算法的计算量，但文献[10]算法存在应用局限性等缺陷，本文算法能够弥补该缺陷。与其他算法相比，本文算法在计算量或通信量或存储空间方面有提升，且能够解决其他算法中存在的一些安全缺陷问题。

6 结 语

本文研究了RFID系统中标签与读写器双向认证过程用到的共享密钥设定问题，提出按位运算的RFID系统密钥无线生成算法。采用动态无线生成的机制产生共享密钥，能够解决密钥托管问题，且能够满足用户进行自定义共享密钥的需求。使用按位运算对所要生成的共享密钥信息进行加密，使算法整体计算量减少。为确保信息传输的安全性，信息加密过程中，混入随机数，使得前后两轮信息不同，增大攻击者破解难度。为拓展算法的运用范围，设计出三种不同场合的共享密钥生成算法。安全性以及性能分析表明，本文算法能够适用于当前的RFID系统中。