无线射频识别(RFID，radio frequency identification)技术近年来发展迅速，但其安全问题也日趋显现，RFID安全认证协议成为保护标签隐私数据的主要研究方向之一^[1]. 不难发现，现有协议大多数基于对称密钥方式^[2]，使得每次认证时，都需要读写器进行遍历计算. 为了解决这个问题，国内外学者提出了基于预计算^[3]和基于二次剩余困难问题假设^[4]等多种方案. 这些方案虽然提高了认证效率，但协议本身的安全性却无法保证^[5].

笔者在Chou^[6]的研究基础上，基于直线斜率计算方法和伪随机数生成器(PRNG，pseudo random number generator)算法，提出了一个新的轻量级RFID双向认证协议. 该协议在硬件和存储空间方面需求较低，一次认证运算能够在常数时间内完成，且可抵抗重放、身份假冒、标签位置追踪等多种攻击，实现了协议的安全性和认证效率的较好平衡.

1 RFID双向认证协议 1.1 平面直线斜率理论

采用平面上直线来代表标签，并将该直线斜率作为标签的密钥值.

如图 1所示，随机选择点(a,b)作为读写器的秘密值，不失一般性，当所有直线通过原点时，有a=b=0. 一条直线L_j，斜率为k_j，且通过点(a,b)，它代表标签T_j . 这样直线L_j上的任何一个点(x_j,y_j)，都可以存储在读写器中，作为标签T_j的一个身份证明. 同时，在大规模多标签环境中，读写器只需要存储一个点(a,b)，然后它就可以和每个标签之间共享一个互不相同的密钥值k_j.

1.2 符号描述

表 1对文中需要用到的一些符号进行了描述.

1.3 协议初始化阶段

在初始化阶段，标签T_j被写入一个唯一动态身份D_ID^j、唯一密钥k_j和当前时间戳C_old. 读写器R_i存储平面上一个点坐标(a,b)、它的身份值R_IDⁱ、关于标签的信息列表，这里只给出标签T_j的信息内容：{D_IDold^j,D_IDnew^j,(x_j,y_j)}.

1.4 双向认证阶段

假设读写器R_i与标签T_j之间相互认证，认证过程如下.

1) R_i生成一个时间戳C_new，并根据R_IDⁱ计算R_request=PRNG(R_IDⁱ⊕C_new).

2) R_i广播C_new,_Rrequest.

3) 收到认证请求之后，标签T_j首先验证C_new是否大于C_old，且R_request是否等于R′_request=PRNG(R_IDⁱ⊕C_new). 如果成立，它生成一个随机数t，利用自己的密钥k_j计算T=PRNG(t⊕D_ID^j⊕k_j⊕C_new).

4) T_j回复消息t,_DID^j,T给R_i .

5) R_i根据D_ID^j查询到坐标(x_j,y_j)，计算T′=PRNG(t⊕D_ID^j⊕C_new⊕(x_j－a)/(y_j－b)). 若T′=T，继续进行计算：D_IDold^j←D_ID^j、 D_IDnew^j←PRNG(C_new⊕D_ID^j⊕(x_j－a)/(y_j－b))、R=PRNG(t⊕C_new⊕D_IDnew^j).

6) R_i发送R给标签T_j .

7) 收到R之后，T_j根据C_new,D_ID^j,_kj计算获得 D′_IDnewID^j和R′. 如果R′=R，T_j更新时间戳和身份值：D^j←PRNG(C_new⊕D_ID^j⊕k_j)，C_old←C_new.

2 基于GNY逻辑的形式化证明

本节利用GNY(Gong,Needham,Yahalom)逻辑规则^[7]，对协议的安全性进行分析. 为了简化文章结构，证明过程中出现的逻辑规则，仅仅给出规则代号，具体规则内容可参见文献^[7].

2.1 协议初始形式化

根据1.4节双向认证协议交互流程，分别针对标签、读写器和协议目标的逻辑语言形式化表达如下.

1) 关于标签T_j的假设：T_j拥有身份值D_ID^j，伪随机生成函数PRNG(·)，知道读写器的身份值R_IDⁱ；验证双方拥有相同的密钥值k_j，所以T_j相信它与R_i共享k_j；T_j生成t，所以它相信t是新鲜的.

标签的假设形式化表达：T_j∈D_ID^j，T_j∈R_IDⁱ，T_j∈PRNG(·)，T_j∈k_j，T_j∈t，T_j|≡${{T}_{j}}\overset{{{k}_{j}}}{\longleftrightarrow}{{R}_{i}}$，T_j|≡#(t).

2) 关于读写器R_i的假设：R_i拥有身份值R_IDⁱ，伪随机生成函数PRNG(·)，知晓读写器的身份值R_IDⁱ；验证双方拥有相同的密钥值k_j，所以R_i相信它与T_j共享k_j；R_i相信C_new是新鲜的.

读写器的假设形式化表达：R_i∈R_IDⁱ，R_i∈PRNG(·)，R_i|≡${{R}_{j}}\overset{{{k}_{j}}}{\longleftrightarrow}{{T}_{i}}$，R_i|≡φ(C_new)，R_i|≡#(C_new).

3) 协议的目标：经过协议的安全运行，读写器R_i相信回复信息T是来自于目标标签T_j并且以前未被使用，也就是新鲜的；同样协议运行后，目标标签T_j相信认证信息R是来自于合法的读写器R_i并且以前未被使用，也就是新鲜的.

协议目标形式化表达为：

① R_i|≡T_j|~#(PRNG(t⊕D_ID^j⊕C_new⊕k_j))；

② T_j|≡R_i|~#(PRNG(t⊕C_new⊕D′_IDnew^j)).

2.2 协议目标形式化证明

1.4节中的4)等价于：R_i收到t,D_ID^j,T语句，可GNY逻辑形式化为

${{R}_{i}}\triangleleft *(t,{{D}^{j}}_{ID},PRNG(t\oplus {{D}^{j}}_{ID}\oplus {{k}_{j}}\oplus {{C}_{new}}))$

也即

${{R}_{i}}\triangleleft *(t,{{D}^{j}}_{ID}){{R}_{i}}\triangleleft *PRNG(t\oplus {{D}^{j}}_{ID}\oplus {{k}_{j}}\oplus {{C}_{new}})$

(1)

由读写器前提假设可知： R_i∈(a,b)，R_i∈(x_j,y_j).

根据GNY拥有规则P2可知：

${{R}_{i}}\in {{k}_{j}}=({{x}_{j}}-a)/(\text{ }{{y}_{j}}-b)$

(2)

根据读写器的假设可知：

${{R}_{i}}|\equiv {{R}_{j}}\overset{{{k}_{j}}}{\longleftrightarrow}{{T}_{i}}$

(3)

根据式(1)、接收原则TI、拥有原则P1可知：

${{R}_{i}}\in t,{{R}_{i}}\in {{D}^{j}}_{ID}={{D}^{j}}_{IDold}$

(4)

由拥有原则P2可知：

${{R}_{i}}\in (t\oplus {{D}^{j}}_{ID}\oplus {{k}_{j}}\oplus {{C}_{new}})$

(5)

由读写器假设R_i|≡φ(C_new)和GNY可识别规则R1、R5可知：

${{R}_{i}}|\equiv \varphi (PRNG(t\oplus {{D}^{j}}_{ID}\oplus {{k}_{j}}\oplus {{C}_{new}}))$

(6)

由读写器假设R_i|≡#(C_new)和GNY新鲜性规则F1可知：

${{R}_{i}}|\equiv \#(PRNG(t\oplus {{D}^{j}}_{ID}\oplus {{k}_{j}}\oplus {{C}_{new}}))$

(7)

由式(1)、式(2)、式(3)、式(5)、式(6)和消息解析规则I1可知：

${{R}_{i}}|\equiv {{T}_{j}}|\tilde{\ }\varphi (PRNG(t\oplus D{{\prime }_{ID}}\oplus {{C}_{new}}\oplus {{k}_{j}}))$

(8)

由式(7)和式(8)可知：

${{R}_{i}}|\equiv {{T}_{j}}|\tilde{\ }\#(PRNG(\oplus D{{\prime }_{ID}}\oplus {{C}_{new}}\oplus {{k}_{j}}))$

(9)

至此目标①得证.

类似于目标①的证明过程，应用GNY逻辑规则I1可以证明：

T_j|≡R_i|~φ(PRNG(t⊕C_new⊕D′_IDnew^j))

根据前提假设R_j|≡#(t)，应用GNY逻辑规则F1可以证明T_j|≡#(PRNG(t⊕C_new⊕D′_IDnew^j)).

所以目标② T_j|≡R_i|~#(PRNG(t⊕C_new⊕D′ _IDnewID^j))成立. 其中D′_IDnew^j=PRNG(C_new⊕D^j⊕k_j).

3 协议安全和效率分析 3.1 协议安全性分析

为了进一步证明协议的安全性，本节从窃听、冒充欺骗、重放、追踪和同步化攻击5个方面来进行分析，具体内容如下.

1) 抗窃听攻击：由于无线信道的不安全，对于所提协议，攻击者A可以通过窃听获取本次会话全部传输消息：C_new,R_request,t,D_ID^j,T,R. 其中C_new是随机值，D_ID^j代表标签的身份，如果本次认证成功，下次标签将更新身份值；如果认证失败，在A不知道读写器身份值R_IDⁱ的情况下，标签是不会响应的. PRNG(·)是安全单向函数，A通过R_request,T,R不能获得比随机数更多的信息. 所以，对于攻击者A来说，通过公开信道获取的信息，对发起攻击没有任何帮助.

2) 抗冒充攻击：所提出协议的目的是实现双向认证，其中所依赖的是读写器与标签之前共享密钥值k_j的机密性，以及伪随机生成器PRNG(·)的强安全性. 如果相信对方身份的合法性，需要C_new,R_request,T,R能通过验证. 本协议中，公开发送消息之间逻辑关系紧密，任何改动将会导致验证失败. 所以，本协议可以抵抗冒充攻击.

3) 抗重放攻击：为了抵抗重放攻击，本协议采用时间戳C_new的方式. 由于每次时间信息的不同，重放之前的信息，将会无法通过时间戳和消息完整性的验证. 所以，本协议可以抵抗重放攻击.

4) 抗标签追踪攻击：追踪攻击的目的是获取某个标签的特征信息，确定不同的认证消息是来源于同一个标签. 在本协议中，攻击者希望可以依据某些特征信息将T_j从众多标签中识别出来. 有两种攻击途径可用来获取特征信息：①窃听R_i和T_j之间的所有通信；②利用窃听到的信息，对T_j实施重放攻击. 对于前者，由于标签引入了随机值，使得每次回复值也不同，同样每次认证成功之后D_ID^j值会更新，利用公开值获取标签特征是不可能的. 后者也即是重放攻击，本节第3)部分已经证明协议可以抵抗重放攻击. 所以，本协议可以抵抗标签追踪攻击.

5) 抗同步化攻击：攻击者A可以通过篡改、阻断等方式发动同步化攻击，使得协议不能完整运行，对于需要秘密值更新的协议机制而言，会导致认证双方分享值的不对称，引起后续所有认证的失败. 在本协议运行中，消息C_new,R_request和消息t,D_ID^j,T识别失败，认证双方都未对D_ID^j值进行更新；消息R认证失败，只有读写器方进行了D_ID^j值更新，但其存储了(D_IDold^j,D_IDnew^j)值，可确保双方共享信息的同步性. 所以，本协议可以抵抗同步化攻击.

3.2 协议硬件需求分析

本节采用与现有协议相比较的方式，对新提出协议的硬件需求进行分析. 由于读写器的硬件配置较高，不依赖于算法的复杂度，所以本节只对标签的硬件需求进行分析.

如表 2所示，文献^[3]基于Hash算法的安全性，文献^[4]和文献^[5]采用Hash算法和二次剩余算法组合的方式，它们至少需要8K门电路来实现协议运算. 然而，低成本的RFID标签只能够提供不超过3K门电路来用于安全保障，所以文献^[3-5]提出的协议不适用于低成本标签环境中. 笔者提出的协议基于PRNG算法，只需要最多2K门电路即可满足其运算要求^[8].

3.3 标签存储需求分析

所提出的协议中，每个标签需要存储D_ID^j,C_old和256 bit的PRNG. 另外，标签还要存储每个被授权接入它的读写器信息，如k_j,R_IDⁱ. 根据标签的记忆能力，可以选择恰当的密钥长度以达到理想的安全水平. 建议每个ID为128 bit(D_ID^j=128 bit,R_IDⁱ=128 bit)、密钥值为1 024 bit(k_j=1 024 bit)、时间戳为256 bit，结果本协议标签的存储要求是(128+256+256)=640/8=80 B. 另外，需要存储一个授权读写器的空间是(1 024+128)=1 152/8=144 B.

轻量级被动式RFID标签的记忆空间是1 kbit～1 KB. 可见所提出的协议适用于轻量级RFID系统. 对于记忆空间达到8 KB的标签，最多可以存储56((8 192－80)/144≈56.3)个读写器信息. 所以，所提出的协议在确保安全的前提下，更加适用于低成本移动RFID环境中.

3.4 协议仿真分析

所提出的协议在Intel 双核CPU、3.16 GHz、4 GB内存的PC上，采用NS-2模拟环境进行仿真. 由于所提出协议与文献^{[3, 5]}都是固定时间认证，认证时间与标签的个数无关，且不需要服务器进行辅助运算，所以仿真对象只包括1个读写器和1个标签，统计完成一次认证协议运行的时间消耗. 为了统计的准确性，结果取100次仿真的平均值.

表 3总结文献^{[3, 5]}和所提出协议的运算效率，其中E_H、E_S、E_P和E_R分别为一次Hash运算、二次剩余求解运算、PRNG运算和一次随机数生成运算的计算花费. 其中Hash函数采用长度为512 bit的SHA-1算法.

通过比较分析发现，文献^[3]协议需要进行5轮交互、7次Hash运算，协议效率最低. 与其相比，所提出的协议在协议运算时间方面降低了近9%，具有更好的认证效率.

4 结束语

安全和效率之间的平衡一直是低成本RFID系统身份识别机制需要解决的问题. 笔者基于PRNG，综合运用直线斜率计算方法、时间戳和身份值更新等手段，提出了一个新的双向认证协议，通过安全证明和效率分析发现，新协议认证时间复杂度为O(1)，且可以满足RFID系统几乎所有必要的安全需求.

在实际应用中，标签-读写器间的认证效率除了受计算量、交互轮数等因素的影响之外，还受软硬件环境的限制. 所以下一步研究的重点在于，将提出协议应用于不同环境中进行验证，如航空器材管理、危险品运输等.