基于码分多址防碰撞的射频识别认证协议

王云峰 张 斌 刘 洋 费晓飞



基于码分多址防碰撞的射频识别认证协议

王云峰*张 斌 刘 洋 费晓飞

(解放军信息工程大学 郑州 450001)

该文针对射频识别(RFID)领域中的安全认证协议和多标签防碰撞算法两个研究热点，设计了一种基于码分多址防碰撞算法的RFID安全认证协议。协议支持密钥的动态更新并引入标志位机制选择备用密钥来抵御数据库同步攻击，同时结合码分多址技术，应用重传随机数进行扩频码的选择，实现一次重传解决多标签识别中因数据碰撞造成的标签不识别的问题。首先，描述协议的流程及防碰撞原理；其次，应用SVO逻辑对认证协议的正确性进行证明；最后，对应用该认证协议的系统吞吐效率进行数值分析，分析表明其吞吐效率高于传统防碰撞算法。

射频识别；码分多址；认证协议；防碰撞

1 引言

射频识别RFID(Radio Frequency Identify)技术是通过无线射频方式对目标进行自动识别的非接触双向数据通信技术。其特有的非接触式自动识别性能，使其被广泛应用到交通、物流供应链管理和零售行业等领域[1]。

RFID系统中，由于无线信道的开放特性，导致标签与阅读器之间的信息传输易遭到窃听、干扰、欺骗和篡改。为解决RFID系统存在的安全问题，目前已提出多种认证协议，一般可分为两类：一类是静态机制认证协议，主要包括分布式RFID询问-响应协议[2]、轻量级同步认证协议[3]和基于DES加密的认证协议[4]等。该类协议能够抵御窃听、跟踪、重放和欺骗等常见攻击，但不能对密钥进行更新，使用该类协议的系统存在标签密钥泄露，进而导致系统内所有标签标识ID被攻击者窃取的安全隐患，同时计算复杂、成本较高。另一类是动态机制认证协议，包括Hash链协议[5]、基于杂凑ID变化协议[6]和基于流密码的协议[7]等，此类协议考虑对ID的保护，每次认证后都更新ID，但存在标签与阅读器之间数据不同步的隐患。因此，设计支持不断更新密钥并能消除数据不同步隐患的认证协议已成为研究热点。

设计高效的防碰撞算法是多标签识别问题的另一热点。常用的防碰撞算法一般可分为两类：一类是基于时隙随机分配的ALOHA算法，包括帧时隙ALOHA算法[8]、分群时隙ALOHA算法[9]和分组动态帧时隙算法[10]等。此类算法简单、便于实现、成本低，但系统吞吐量小，且存在标签无法被识别的情况。另一类是基于二进制树搜索的算法，主要包括自适应四叉树搜索算法[11]、自适应多叉树算法[12]和基于识别码分组的算法[13]等。该类算法能够识别读写器有效通信范围内所有标签，但计算复杂、延时较长。

文献[14]提出了一种基于码分多址技术的RFID防碰撞算法，算法可以同时识别系统中的多个标签，但未明确指出多标签碰撞情况下扩频码的选择方法，无法避免数据再次碰撞。结合文献[14]的设计思路，针对数据碰撞问题，本文提出一种基于码分多址防碰撞的RFID认证协议。该协议将静态和动态机制的优点相结合，支持密钥的动态更新并引入标志位机制选择备用密钥来抵御数据库同步攻击。同时，协议结合码分多址技术，应用重传随机数进行扩频码的选择，实现一次重传解决多标签识别中因数据碰撞造成的标签不识别的问题。

2 基于码分多址防碰撞RFID认证协议

基于码分多址防碰撞的RFID协议认证流程如图1所示，文中符号见表1。

表1符号描述

符号描述 ID标签身份标识 K,K'标签密钥K和备用密钥K' PRNG随机数发生器 RT标签产生的随机数 RR阅读器产生的随机数 重传机制中阅读器产生的新随机数 Flag1 bit防数据同步攻击标志位 N系统内置扩频码数量 M扩频码 扩频运算 密钥为K的Hash运算值的左半部 密钥为K'的Hash运算值的右半部

协议中阅读器存储着ID和，标签存储着IDR和Flag。

认证和密钥更新流程如下：

(1)阅读器向标签发送认证请求和R；

(2)标签收到请求和R，生成范围在1至之间的随机数R并将其储存，同时计算(R+R) mod的值，标签选择内置对应的第个Gold序列作为扩频码；

图1 基于码分多址防碰撞的协议认证流程

(4)阅读器收到扩频信息后，依次使用内置扩频码进行解扩。若在同一时刻或数据处理过程中，存在两个或以上数据应用同一扩频码进行解扩，则发生碰撞，转向流程(7)；否则继续执行；

若以上两种信息对都不存在，则认证失败，结束；

3 安全性能分析

3.1 SVO逻辑分析证明

协议的分析证明采用形式化验证逻辑SVO[15]，通过认证协议运行过程中消息的接收和发送，从初始假设逐渐推导出协议的目标。证明过程中，R代表阅读器，T代表标签，公理A1, A2, A3, A4参见参考文献[15]中SVO逻辑推理规则。

RFID双向认证协议流程分析如下：

(1)初始假设

(3)消息接收

(4)主体对接收到消息的理解 由于阅读器在接收到消息前不知道标签对应的密钥和ID，因此不知道接收的内容，故

(5)接收者对消息的解释

(6)使用SVO逻辑推导

由P2, P9，推论a和A1可得：

由推论d和消息发送公理A4:

由P7, P10, A1可得：

由P2, P11，推论a和A1可得：

由P1, A2, A1和NEC规则可得：

由推论b，推论c, A3, A1和NEC规则可得：

3.2 抗攻击分析

(1)防窃听和跟踪攻击：单向Hash函数的加密，使攻击者无法还原标签与阅读器间信息明文，因此协议可抵御窃听攻击。同时，标签在每次通信中传递的信息不固定，所以不能实现对标签的跟踪。

(2)防重放和欺骗攻击：由于阅读器每次通信时都产生随机数，攻击者无法预知和控制，所以记录并重放泄漏的消息，伪装成合法用户的方法对系统无效，数据库不会给予认证。

(3)防数据库同步攻击：为解决数据库和标签的数据同步问题，协议提出了一种基于标志位Flag选择密钥或备用密钥的认证机制。协议初始，标签检查Flag标志位。若Flag=1，表明前一轮协议认证中阅读器与标签之间实现了合法认证；若Flag=0，说明系统受到攻击导致数据不同步，系统将自动采用备用密钥进行加密。这样，协议不仅实现了对标识ID的保护，同时解决了不断更新加密密钥带来的数据库不同步的安全问题。

(4)防内部篡改：内部篡改是指合法标签有意地篡改自身ID值，伪装成其它合法标签，骗取阅读器的认证。但由于每个标签的认证密钥独立且不断更新，伪装的标签无法产生与阅读器对应的合法信息，不能通过认证。同时，即使攻击者获得加密算法的硬件结构和标签数据信息，可无法掌握密钥的更新，同样无法通过阅读器的认证。

(5)ID的保护与相互认证：不固定的密文传输及密钥的实时更新等诸多保护措施，实现了对标签ID的保护。同时，阅读器和标签之间的双向认证使得系统安全性更加可靠。

协议安全性对比如表2(其中，×代表无法防御，○代表有效防御)。

表2协议安全性对比

协议名称窃听跟踪重放欺骗ID保护数据同步内部篡改认证方式 Hash-lock×××××○×单向 随机Hash-lock×○×××○×单向 基于Hash的ID变化○○○×○××双向 LCAP○○○○○××双向 分布询问应答○○○○○○×双向 本文协议○○○○○○○双向

协议计算量对比如表3(其中，N表示Hash函数次数，N表示产生随机数次数，表示系统中标签的数量)。

与其它协议相比，标签和阅读器的计算量没有增加，且查找过程是在计算能力强的数据库进行，因此协议在保证安全性的同时，未给系统带来多余计算负荷。

表3协议计算量对比

协议标签阅读器数据库 NH NR NH NRNH NR Hash-lock1 0 0 0 0 0 随机Hash-lock1 1(n+1)/2 0 1 0 基于Hash的ID变化3 0 0 0 3 1 LCAP2 0 0 1 1 0 分布询问应答2 1 0 1(n+3)/2 0 本文协议1 1 0 1(n+1)/2 0

4 防碰撞性能分析

4.1 认证协议防碰撞原理

本文认证协议基于码分多址技术，在待识别的标签数量较多时，有效地增加系统吞吐量，减少识别时间，提高搜索效率，其原理如图2所示。某时刻有个标签同时向阅读器发送数据，系统随机分配个扩频码(1~M)供碰撞数据使用，阅读器端采用同样的扩频码对信息解扩，以恢复标签数据。当有两个或以上标签选择的扩频码相同时，标签数据发生碰撞，此时启动重传机制，标签重新选择扩频码实现其数据的识别。协议中重传机制的数据帧与确认帧发送时间关系如图3所示，其中阅读器和标签封装的帧格式如图4，图5所示。

反向链路，即标签响应阅读器的命令并向其发送数据的链路。t是标签数据帧的发送时间，由图4可知其帧长=112 bit，在中高频系统中，上行速率通常为=40 kbit/s[16]，因此数据帧发送时间t=/=0.0028 s，同理t=0.0028 s。数据帧沿反向链路传到阅读器还要经历物理链路造成的传播时延t，同时阅读器收到数据帧要经历处理时间t。阅读器接着发送前向链路的确认帧，其发送时间为t，传播时延为t，标签收到确认帧需要时间t进行处理，再重新发送数据帧。为方便问题研究，设标签与阅读器的处理时间t远小于数据帧发送时间，且由于标签与阅读器间作用距离短，传播时延t为0，因此一次重传时间可视为t+t+t

图2 协议的多标签识别原理

图3 协议中数据帧与确认帧发送时间关系

图4 标签数据帧格式(前向链路)

图5 阅读器确认帧格式(反向链路)

定义系统的吞吐量为时间内能成功解扩的标签数据帧的均值，则其可以表示为

4.2 认证协议吞吐量分析

由吞吐量公式可知，由于发送时间≠0，因此吞吐效率函数在=处并不连续，当<时，=，吞吐效率为直线=1；当>时，吞吐效率为下降曲线，取帧发送时间=t=0.0028 s，系统吞吐量与负载和扩频码数量的关系如图6所示。

由图6可知，当扩频码数量一定时，系统吞吐量会随着负载的增加而先增大达到峰值再逐渐减小。同时负载一定时，吞吐量会随着扩频码数量的增加而逐渐增大；图7吞吐效率随着的增加而逐渐减小，随着的增加而逐渐增大，且，因此系统吞吐效率高于时隙ALOHA吞吐效率。协议算法与传统算法吞吐效率对比如图8所示，其中=100,=0.0028 s。由图可知，本文算法吞吐效率曲线并不连续，当<100时，吞吐效率=1.0，明显高于传统算法；>100时，吞吐效率为下降曲线，但仍高于传统算法。

图6 系统吞吐量与负载和扩频码数量的关系

图7 吞吐效率与负载和扩频码数量的关系

图8 本文协议算法与传统算法吞吐效率对比图

5 结束语

本文针对RFID领域中的安全认证协议和多标签防碰撞算法两个研究热点，设计了一种基于码分多址防碰撞算法带有重传机制的RFID安全认证协议。文中利用SVO逻辑对该协议进行形式化分析，在理论上证明其正确性与安全性，并在此基础上分析了协议对各种攻击的有效抵御。在防碰撞算法的分析中，分析了防碰撞算法中扩频码数量和标签数量对吞吐量的影响，并应用Matlab实现算法仿真。仿真结果证实了算法的正确性，其吞吐量高于传统防碰撞算法。

[1] 谢磊, 殷亚凤, 陈曦. RFID数据管理: 算法、协议与性能评测[J]. 计算机学报, 2013, 36(3): 457-470.

Xie Lei, Yin Ya-feng, and Chen Xi. RFID data management: algorithms, protocols and performance evaluation[J]., 2013, 36(3): 457-470.

[2] Rhee K, Kwak J, Kim S,.. Challenge-response based RFID authentication protocol for distributed database environment[C]. Proceedings of International Conference on Security in Pervasive Computing, Boppard, Germany, 2005(3450): 70-84.

[3] Ha J C, Ha J H, Moon S J,.. LRMAP: lightweight and re-synchronous mutual authentication protocol for RFID system[C]. Proceedings of the International Conference on Ubiquitous Convergence Technology, Berlin, Germany, 2007: 80-89.

[4] Wang Z, Xin W, Xu Z,.. A secure RFID communication protocol based on simplified DES[C]. Proceedings of the 2012 International Conference on Information Technology and Software Engineering, Berlin, Germany, 2013: 351-357.

[5] Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita. Hash-chain based forward-secure privacy protection scheme for low cost RFID[C]. Proceedings of the 2004 Symposium on Cryptography and Information Security (SCIS 2004), Sendai, Japan, 2004: 719-724.

[6] Henrici D and Muller P. Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers[C]. Proceedings of the 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops, Washington, USA, 2004: 149-153.

[7] 龚洁中, 陈恭亮, 李林森, 等. 基于流密码的RFID 安全认证协议[J]. 计算机工程, 2013, 38(13): 126-129.

Gong Jie-zhong, Chen Gong-liang, Li Lin-sen,.. RFID secure authentication protocol based on stream cipher[J]., 2013, 38(13): 126-129.

[8] Finkenzeller K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification[M].New York: John Wiley & Sons, 2003: 151-158.

[9] Hwang Tae-wook, Lee Byong-gyo, and Kim Young-Soo. Improved anti-collision scheme for high speed identification in RFID system[C]. First International Conference on Innovative Computing, Information and Control, Beijing, China, 2006, 2: 449-452.

[10] 庞宇, 彭琦, 林金朝, 等. 基于分组动态帧时隙的射频识别防碰撞算法[J]. 物理学报, 2013, 62(14):148401-1-148401-8.

Pang Yu, Peng Qi, Lin Jin-chao,.. Reducing tag collision in radio frequency identification systems by using a grouped dynamic frame slotted ALOHA algorithm[J]., 2013, 62(14): 148401-1-148401-8.

[11] Shih B Y, Lo T W, Chen C Y. The research of quadtree search algorithms for anti-collision in radio frequency identification systems[J]., 2011, 6(25): 5342-5350.

[12] 张学军, 蔡文琦, 王锁萍. 改进型自适应多叉树防碰撞算法研究[J]. 电子学报, 2012, 40(1): 193-198.

Zhang Xue-jun, Cai Wen-qi, and Wang Suo-ping. One anti-collision algorithm based on improved adaptive multi-tree search[J]., 2012, 40(1): 193-198.

[13] 张学军, 王娟, 王锁萍. 基于标签识别码分组的连续识别防碰撞算法研究[J]. 电子与信息学报, 2011, 33(5): 1159-1165.

Zhang Xue-jun, Wang Juan, and Wang Suo-ping. An uninterrupted anti-collision algorithm with ID-based grouping for RFID system[J].&, 2011, 33(5): 1159-1165.

[14] 梁彪, 胡爱群, 秦中元. 一种新的RFID防碰撞算法设计[J]. 电子与信息学报, 2007, 29(9): 2158-2160.

Liang Biao, Hu Ai-qun, and Qin Zhong-yuan. A novel design for RFID anti-collision technique[J].&, 2007, 29(9): 2158-2160.

[15] Syverson P F, and Cervesato I. The logic of authentication protocols[J]., 2001, 2171: 63-137.

[16] 周晓光, 王晓华. 射频识别(RFID)技术原理与应用实例[M]. 北京: 人民邮电出版社, 2006: 113-114.

Zhou Xiao-guang and Wang Xiao-hua. Radio Frequency Identification (RFID) Technology Theory and Practical Examples[M]. Beijing: Posts & Telecommunications Press, 2006: 113-114.

王云峰： 男，1990年生，硕士生，研究方向为安全认证协议.

张 斌： 男，1969年生，教授，硕士生导师，研究方向为网络信息安全.

刘 洋： 男，1980年生，博士生，研究方向为SOA安全、无线通信安全.

Radio Frequency Identification Authentication Protocol Based on CDMA Anti-collision Algorithm

Wang Yun-feng Zhang Bin Liu Yang Fei Xiao-fei

(,450001)

For addressing the two focus issues under research , security authentication protocol and the multi-tag anti-collision algorithm in the field of Radio Frequency IDentification (RFID), a Code Division Multiple Access (CDMA)-based anti-collision algorithm of the RFID authentication protocol is presented in this paper. The authentication protocol supports dynamic updates of the key and resists database synchronization attacks by using flag mechanism to select spare key. Meanwhile, by combining with CDMA and by retransmitting random number to select spreading code, the authentication protocol solves recognition of tags due to data collisions during the multi-tag identification by one-time retransmission. Firstly, the process of the authentication protocol and an anti-collision theory is described. Secondly, the SVO logic is used to prove correctness of the protocol in theory. Finally, numerical analysis of the system throughput applying the protocol shows that its throughput efficiency is higher than the traditional one.

Radio Frequency Identification (RFID); Code Division Multiple Access (CDMA); Authentication protocol; Anti-collision

TN91

A

1009-5896(2014)06-1472-06

10.3724/SP.J.1146.2013.01337

王云峰 wangyunfengieu@126.com

2013-09-04收到，2013-12-24改回