基于M序列的轻量级RFID认证协议

徐鹏翱 滕济凯 马鸿洋

(青岛理工大学理学院 山东青岛 266033) (xupa123@163.com)

RFID技术即射频识别技术是近几年来业界非常关注的热点.正是因为RFID标签的体积小、寿命长、容量大而且可以重复使用等优点， 目前RFID技术已被广泛应用于各种领域[1-2].RFID由2个主要模块构成：标签和读写器.RFID读写器能够直接扫描目标对象，这带来了很高的效率，但同时也带来了很大的安全隐患，主要是因为电子标签的内容容易被泄露，另外，标签也很容易被追踪、定位，这给人们带来了很多隐私威胁问题.尽管有许多安全手段，但是也没有完全解决安全和隐私问题[3].如果这里的安全和隐私问题不能解决，人们就不会很放心地使用RFID系统，这就会极大地阻碍RFID的发展.因此，RFID应用中的安全隐私保护问题受到人们的重视，提出了许多RFID隐私保护协议，有Sarma等人[4]提出的一种基于Hash函数的Hash-Lock协议和随机化Hash-Lock协议[5]，其中随机化Hash-Lock协议是Hash-Lock协议的一个扩展，它解决了标签定位隐私问题，解决的方法是主动干扰无线电信号，标签用户可以通过一个设备主动广播无线电信号阻止或破坏附近的RFID阅读器的操作.Juels等人[6]提出了基于Hash链的认证协议，该认证协议在认证过程中通过阻止阅读器读取标签来确保消费者隐私，另外标签还通过刷新认证所用的ID来实现前向安全性.陈瑞鑫等人[7]提出了一种基于Hash函数的双向RFID认证协议，为了避免信息泄露和被追踪，使用metaID代替真实的标签ID.但是这些协议需要大量运算和通信，所需要的计算资源和通信资源都非常多，只适用于小规模应用.Zhou等人[8]提出了轻量级协议来提高协议的可行性，但该协议被发现不能抵抗拒绝服务攻击.Duc等人[9]提出了一种抵抗拒绝服务攻击的认证协议，但是该协议在最坏情况下计算复杂度为O(m×n)，可行性仍然不好，而且不具有前向安全性.为了提高协议的可行性，有些研究人员提出了采用轻量级分组密码的认证协议[10-11].Chien等人[12]和Fernàndez-Mir等人[13]试图通过标签和服务器共享的索引伪标识符来提高协议的可扩展性，但由于系统数据同步性失败所导致的位置跟踪问题，张顺和陈海进[14]提出了双向认证协议，该协议可扩展性好，而且能抵抗拒绝服务攻击.在上述协议[3-14]中，服务器的搜索量都和标签的个数有关.

本文基于M序列提出了一种安全高效的轻量级RFID认证协议.在该协议中，服务器的搜索量和标签个数无关.标签和服务器只需做少量计算就可以完成协议的运行.协议具有抗重放、抗分析、防伪造、防跟踪等安全属性.

1 基础知识介绍

在描述协议之前，先介绍和协议相关的n级移位寄存器、M序列以及联结多项式.

n级移位寄存器：n级移位寄存器由n个寄存器和1个开关电路组成，寄存器从左至右依次称为第1级，第2级，…，第n级.每个寄存器中的内容为有限域Fq中的一个元素，每一级的内容移给下一级，最后一级的内容输出，为了保持连续工作，将移位寄存器的某些内容进行运算后反馈到第1级.不断加脉冲即移位寄存器不断移动，上述n级移位寄存器的输出就构成一个无限序列a0，a1，…，an，…这个寄存器称为线性移位反馈寄存器.

M序列：上述序列a0，a1，…，an，…必为周期序列，序列a0，a1，…，an，…的周期最大值可达到2n-1，称周期达到最大值的线性移位寄存器序列为M序列.

联结多项式:如果有一个序列适合递归关系式ak=-c1ak-1-c2ak-2-…-cnak-n(k≥n)，则称多项式f(x)=1+c1x+c2x2+…+cnxn为这个线性移位反馈寄存器序列的联结多项式.

2 协议介绍

在以往大多数认证协议中，标签和读写器有较高的计算量和通信量，服务器的搜索量和标签个数有关.本文基于M序列提出了一种轻量级RFID认证协议，该协议可以使标签和读写器具有较低的计算量和通信量，而且服务器的搜索量为常数级，该协议也具有较强的安全属性.

2.1 协议描述

协议初始化：

首先，为系统选择一个合适的Hash函数H:{0,1}*→Fq，然后为每个标签Ti分配1个联结多项式fi，联结多项式fi为该标签和服务器共享，fi在服务器中的存储位置被标识为ui.

该协议运行过程如下：

1) 阅读器向标签Ti发送1个认证请求，生成

1个随机数mi∈2n-1，然后将请求和mi发送给标签Ti.

2) 标签Ti收到后，选择随机数ti∈2n-1，以fi为联结多项式，以H(IDi)为初态，移动mi步，将得到的状态ni和ti发送给阅读器，阅读器转发给服务器.

3) 服务器收到后，以fui为联结多项式，以ni为初态，移动2n-1-mi步，得到H(IDi)，并检查与数据中保存的身份信息的Hash值是否一致，如果一致，接受标签Ti，服务器将fui转发给读写器；否则标签认证失败，服务器停止响应.

4) 阅读器fui联结多项式，以H(R)为初态，其中R为读写器的身份信息，移动ti步，将得到的状态vi发送给标签Ti.

5) 标签以fi为联结多项式，以vi为初态，移动2n-1-ti步，得到H(R)，并检查计算的H(R)是否正确，如果正确则接受读写器，否则意味着受到了1次攻击.

因为序列的周期为2n-1，所以序列移动mi步后，再移动2n-1-mi步可以得到初态H(IDi).同理，移动ti步后，再移动2n-1-ti步可以得到初态H(R)，因此，协议正确.

2.2 协议的分析

2.2.1安全性分析

1) 抗重放攻击和哄骗攻击，抗数据分析

因为M序列和伪随机序列的不可区分性，对敌手来说，每次发送的消息都具有随机性.另外因为M序列的周期非常大，所以攻击者无法记录下每一次的通信数据.

2) 防伪造

在2次认证中，尽管参数明文传输，但是联结多项式是保密的，而且M序列和伪随机序列是不可区分的，因此只有正确参数的持有者才能通过对方的验证，攻击者无法通过对方的验证.

不可跟踪性也就是如果攻击者不能从一个协议通信报文集中区分出2个具有不同密钥的标签，则称这个RFID协议具有不可跟踪性.在本协议中，因为M序列和伪随机序列的不可区分性，攻击者即使获取了大量的通信数据，也无法判别出数据属于哪个标签，所以本协议具有不可跟踪性.

2.2.2复杂性分析

为了便于协议的分析和比较，将使用如下记号.

H:表示 Hash运算；

XOR:表示异或运算；

PRNG:表示1次伪随机数产生的运算；

l:表示元素长度.

n:表示数据库中标签的个数.

协议的复杂度比较如表1所示:

表1 复杂度比较

由表1可以看出，本文提出的协议在存储量、计算量、通信量和搜索量上优于其他协议，特别是在服务器的搜索量上，本文的协议是常数，和标签的个数无关，而其他协议都和标签的个数有关，因此，本文提出的协议其效率要高于其他协议的效率.

3 结 论

本文采用M序列提出了一种轻量级RFID认证协议，该协议在存储量、计算量、通信量方面均优于目前大多数协议，特别是在服务器的搜索量上，该协议的搜索量和标签的个数无关.在安全性上，本文的协议实现了抗重放、抗分析、防伪造、防跟踪等安全属性.

[1]Rhee K, Kwak J, Kim S, et al. Challenge-response based RFID authentication protocol for distributed database environment[G]LNCS 3450: Proc of the Int Conf on Security in Pervasive Computing. Berlin: Springer, 2005: 70-84

[2]周永彬, 冯登国. RFID安全协议的设计与分析[J]. 计算机学报, 2006, 29(4): 581-589

[3]Burmester M, Medeiros B, Motta R, et al. Anonymous RFID authentication with constant key-lookup[C]Proc of the 2008 ACM Symp on Information, Computer and Communications Security. New York: ACM, 2008: 283-291

[4]Sarma S E, Weis S A, Engels D W. RFID systems and security and privacy implications[C]Proc of Int Workshop on Cryptographic Hardware and Embedded Systems.Berlin: Springer, 2003: 454-469

[5]Sarma S E, Weis S A, Engels D W. Radiofrequency identification: Secure risks and challenges[J]. RSA Laboratories Cryptophytes, 2003, 6(1): 2-9

[6]Juels A, Rivest R L, Szydlo M. The blocker tag: Selective blocking of RFID tags for consumer privacy[C]Proc of the 10th ACM Conf on Computer and Communication Security. New York: ACM, 2003: 103-111

[7]陈瑞鑫, 邹传云, 黄景武. 一种基于双向Hash认证的RFID安全协议[J]. 微计算信息, 2010, 26(11): 149-151

[8]Zhou S J, Zhang Z, Luo Z, et al. A lightweight anti-desynchronization RFID authentication protocol[J]. Information Systems Frontiers, 2010, 12(5): 521-52

[9]Duc D N, Kim K. Defending RFID authentication protocols against DoS attacks[J]. Computer Communi-cations, 2011, 34(3): 384-390

[10]Ohkubo M, Suzuki K, Kinoshita S. Efficient hash-chain based RFID privacy protection scheme[C]Proc of Int Conf on Ubiquitous Computing Ubicomp, Workshop. 2004 [2018-05-29]. https:ci.nii.ac.jpnaid10030538475#cit

[11]Tsudik G. YA-TRAP: Yet another trivial RFID authenti-cation protocol[C]Proc of the 4th Annual IEEE Int Conf

on Pervasive Computing and Communications Workshops. Piscataway, NJ: IEEE, 2006: 640-643

[12]Chien H Y, Huang C W. A lightweight authentication protocol for low-cost RFID[J]. Journal of Signal Processing Systems, 2010, 59(1): 95-102

[13]Fernàndez-Mir A, Castellà-Roca J, Viejo A. Secure and scalable RFID authentication protocol[G]LNCS 6514: Proc of the 5th Int Workshop on Data Privacy Management. Berlin: Springer, 2011: 231-243

[14]张顺, 陈海进. 轻量级的无线射频识别安全认证协议[J]. 计算机应用, 2012, 32(7): 2010-2014