2. 中国建设银行股份有限公司信息技术管理部, 北京 100033
为了实现对低成本标签的认证和隐私保护，提出了轻量级无线射频识别(RFID)双向认证协议.利用HB#协议通信量和存储量较小的特性，结合物理不可克隆函数防止标签被克隆，认证结束后进行密钥更新防范位置追踪.分析结果表明，该协议实现了标签与阅读器间的双向认证，不仅具有HB#协议的安全特性，还具有抵抗克隆攻击、内存读取攻击、保护隐私安全等特性，同时可以减轻阅读器搜索密钥的负担.
2. Department of Information Technology Management, China Construction Bank, Beijing 100033, China
In order to authenticate low-cost tag and protect its privacy, a lightweight radio frequency identification mutual-authentication protocol is proposed. The proposed protocol takes advantage of HB# protocol with small amount of transmission and storage, combines with physically unclonable function to protect the tag from cloning, and updates the keys to prevent location tracking. Analysis shows that it realizes mutual-authentication between the reader and the tag, and not only inherits the security properties of HB# protocol, but also can resist clone attack, read memory attack and protect privacy. At the same time, the proposed protocol can also substantially reduce the reader's burden on searching keys.
在无线射频识别(RFID, radio frequency identification)系统中，标签的成本一般很低，拥有的硬件资源有限，计算能力和存储能力都较弱，而且容易受到窃听、篡改和追踪等攻击.目前，很多学者对RFID安全进行了研究，邓淼磊等[1]在不可追踪性方面作了研究；在轻量级认证协议方面，HB族和物理不可克隆函数(PUF, physically unclonable function)这2类认证协议受到较多关注. PUF由一组微型延迟电路组成，可利用制造过程中不可避免产生的差异，使PUF具有唯一性，从而抵抗标签克隆攻击. HB族协议主要包括HB[2]、HB+[3]和HB#[4]等，这些协议均基于噪声环境下的学习校验(LPN, learning parity with noise)难题. HB#协议在HB族协议中性能优异，计算量、通信量和存储量都较小.但该协议不能抵御中间人攻击，也没有提供阅读器搜索标签密钥的方法. RFID认证协议不仅需要实现阅读器与标签的双向认证，还应该保障标签身份信息的隐私安全.因此，笔者结合HB#和PUF，提出了双向认证协议PUF-HB#.
1 LPN难题和HB#协议HB协议族都基于LPN难题，LPN是为数不多的“矢量子求和”困难问题. LPN已被证明是非确定性多项式难度(NP-Hard, non-deterministic polynomial hard)[5]，破解算法的时间复杂度都不低于2O(k/lbk). Hopper和Blum[2]首先提出HB协议，HB协议在抵抗被动攻击的安全性可以规约到LPN难题上，但是不能抵抗主动攻击[3].改进后的HB+协议可以抵抗针对HB协议的攻击. Gilbert等[4]发现对HB+协议的攻击方法(GRS-MIM攻击)，并且提出了能抵抗GRS-MIM攻击的HB#协议.在HB#协议中标签与阅读器共享密钥为kx和ky，首先，标签发送随机矢量b给阅读器，然后阅读器回复随机矢量a，标签根据密钥kx和ky生成Toeplitz矩阵X和Y，产生噪声系数为η的随机噪声，计算z = a ·X ⊕ b ·Y ⊕v，并发送给z阅读器，阅读器也根据kx和ky产生X和Y，计算a ·X ⊕ b ·Y ⊕ z的汉明重量，若小于阀值t则认证通过；否则失败. HB#协议过程如图 1所示.
|
图 1 HB#认证协议 |
HB#协议性能比较优异，错误拒绝率和错误接受率都非常低，通信量和存储量也仅有约1 kbit，但是该协议不能抵抗中间人攻击[6].此外，HB和HB#协议都没有密钥查询的功能，阅读器需要按顺序对密钥进行运算，直到查到匹配的密钥为止，其运算量非常大，而且有可能以其他密钥通过了标签的认证.如果标签直接发送身份标识码(ID, identity)，则泄露了标签的隐私信息.为了解决阅读器搜索密钥的问题，Ouafi等[7]提出了基于树查找密钥的Tree-based HB协议，但Avoine等[8]指出该协议并不能保证隐私安全，并提出了新的方案，而新方案在系统初始化时很难实现.因此，笔者提出了新协议可解决HB#协议存在的问题.
2 PUF简介Gassend等[9]指出PUF利用物体的物理特征把一组挑战值映射到一组应答值，它包含2个特征：第一，易于计算，收到挑战值后在多项式时间内能得到响应值；第二，难以模拟，攻击者在有限的时间和计算资源内不能实现完全一样的PUF功能.此外，在采用标准互补金属氧化物制造工艺的集成电路中容易构建PUF，即PUF可以用于低成本标签的认证.
标签在制造过程中生成PUF，挑战应答对由所处的环境决定.由于标签在制造过程中都不可避免地存在一些差异，所以生成的PUF都不相同.在认证时，对同一挑战值，每个标签都会产生不同的应答值，阅读器可以根据系统部署时存储的挑战应答对来确定哪个标签是合法的.由于攻击者不能产生相同的挑战应答对，所以攻击者很难实现克隆攻击.攻击者如果试图窃取标签内存中存储的秘密信息，必然会在读取过程中破坏标签的物理结构，影响PUF，使得PUF的挑战应答对发生很大的变化，从而使标签失效，所以内存读取攻击也是无法实现的.
由于PUF具有抵抗物理克隆攻击的特性，可以利用PUF产生随机数和密钥，也可用来设计认证协议.本研究结合LPN难题和PUF抵御克隆攻击的特性，提出了HB#协议的改进协议PUF-HB#.
3 PUF-HB#：轻量级RFID认证协议PUF-HB#协议的主要参数如下.
ID：标签的唯一标识，96 bit，在标签和阅读器中分别存放；
ki：标签存储的根密钥，用于产生kp；
kp：用于验证标签的PUF输出，存储于阅读器，kp=PUF(ki)；
kx和ky：这2个密钥分别用于产生Toeplitz矩阵X和Y，存储于阅读器和标签；
kt：在传输IDnew(更新的标签ID)时保护IDnew，存储于阅读器和标签；
v：随机噪声；
η：噪声系数；
t：ID的比特数，即96 bit；
m：Toeplitz矩阵X和Y的列数；
a，b，c：随机矢量；
u：判断认证通过的系数.
参考文献[4]，设m为441，kx长度为520 bit，ky长度为952 bit，η为0.125，v长度为441 bit，a和c长度为80 bit，b长度为512 bit，um为113 bit. ki长度为96 bit，kp长度与v相同为441 bit，kt与ID长度相同，均为96 bit.
在系统初始化阶段，系统先产生根密钥ki，标签计算kp=PUF(ki)，1次输出不够441 bit，可以以上次输出作为输入，重复多次，将这些PUF输出级联取前441 bit作为kp，并将ki存储在标签中，而kp存储在阅读器数据库中.认证过程见图 2，描述如下
|
图 2 PUF-HB#协议认证过程 |
1) 当有标签进入阅读器的扫描范围时，阅读器产生80 bit的随机矢量a，发送a给标签.
2) 标签首先查看是否存储了随机矢量a，若有则与阅读器发送过来的随机矢量a比较，若相同，则认为是重放攻击，认证结束；否则继续.根据kx和ky生成Toeplitz矩阵X和Y，计算kp′=PUF(ki).将a补齐0至t bit，然后以a⊕ID作为PUF输入产生随机矢量b，如果1次PUF输出不够512 bit，可将前1次的PUF输出作为下次的输入，将这些输出级联直至长度大于512 bit，取前512 bit作为b.同理以最后1次输出作为输入，产生441 bit的v3、v4和v5，v3和v4进行与运算得到结果v6，v6再和v5相与得到噪声系数为0.125的随机噪声v1.计算z1= a ·X ⊕ b ·X ⊕kp′⊕v1.取vt为v1的前t bit，计算PUF(ID⊕vt)，取前t bit作为IDnew.取kp′前t bit即kp′ t，计算T=IDnew⊕kt⊕kp′ t⊕vt.然后给阅读器发送ID‖ b ‖z1‖T.
3) 阅读器根据ID查找密钥，如果当前ID组没有该ID，则在IDold组中查找，如果仍未找到则认为该系统不存在该ID的标签，认证结束.找到密钥之后根据kx和ky生成Toeplitz矩阵X和Y，判断Hwt(a ·X ⊕ b ·Y ⊕kp⊕z1)≤um是否成立，若不成立，则认为认证不通过，认证结束；否则认为认证通过.计算s= a ·X ⊕ b ·Y ⊕z1，st为s的前t bit，计算IDnew=T⊕kt⊕st，更新数据库中的ID数据，即IDold=ID(当前ID)，ID=IDnew.产生随机矢量c，同时产生噪声系统为0.125的噪声v2，计算z2= c ·X ⊕ b ·Y ⊕v2.发送c‖z2给标签.
4) 标签判断Hwt(c ·X ⊕ b ·Y ⊕z2)≤um是否成立，如果不成立，则认为标签认证阅读器失败，并且存储本次认证过程中阅读器发送的a以防止重放攻击；如果成立，则认为认证成功，更新ID为IDnew，并且清除存储的随机矢量a，认证结束.
4 协议分析 4.1 安全性分析从以下几方面分析本方案的安全性.
1) 双向认证.首先阅读器对标签进行了认证，然后标签又对阅读器进行了认证.由于传输了标签的ID，阅读器可直接查询ID所对应的密钥，解决了HB#协议查询密钥复杂的问题.在ID更新过程中，传输的是T=IDnew⊕kt⊕vt⊕kp′ t，既没有泄露IDnew，也没有泄露vt和kp′ t，即使下次认证时攻击者知道了IDnew，由于kt的存在，也无法得到vt和kp′ t.标签认证阅读器的过程和HB#协议的认证过程相同，因此该过程的安全性和HB#协议相同.阅读器认证标签过程中，判断认证是否通过的式子由HB#协议中的Hwt(a ·X ⊕ b ·Y ⊕z)≤um变为Hwt(a ·X ⊕ b ·Y ⊕kp⊕z1)≤um，由于z1相对z多异或了kp′，而kp′⊕kp为0，这样判定式子和HB#协议相同.根据文献[10]，对于同一个PUF，相同的输入产生不同的输出概率仅为0.7%，可见，p′有可能与kp不同，但不同的概率很小，最大为0.7%，在本方案中，多次计算kp′可以进一步减少与kp不同的位数，而u远大于0.7%，因此kp′⊕kp的汉明重量远小于um，于是该认证过程的安全性能和HB#协议相同.此外，本协议在传输过程中传输了ID和T，按前面的分析，并不会泄露vt和kp′ t，攻击者就无法得到v和kp，因此传输ID和T并不会影响协议的安全性.由于本协议中双向认证的每次认证都可以认为是1次HB#认证，所以本协议具有HB#协议的安全性能，在抵御被动攻击方面可规约到LPN问题，并且可以抵抗基于检测(DET, detection-based)模型和GRS-MIM模型的攻击[4].
2) 位置追踪.如果标签的ID一直不更新，攻击者可以利用第2条通信消息中的ID来达到跟踪标签的目的.在本方案中，认证成功之后，双方会更新标签的标识ID，而IDnew又无法从通信消息中获得，所以攻击者不能追踪标签，保证了标签的位置隐私安全.
3) 去同步攻击.攻击者可能想通过截断或篡改某条消息，使得阅读器和标签中的一方更新ID，而另一方未能更新.然而在本方案中，阅读器在认证标签成功后就更新ID，并保存当前ID和IDnew，标签在认证成功阅读器后才更新ID.所以由第3条通信数据被篡改的原因导致标签认证阅读器失败，标签不更新ID，而下次认证时阅读器可以从IDold组中查找标签发送的ID.
4) 重放攻击.在重放攻击中，攻击者通常截获合法标签的成功认证消息，然后用这些消息发起认证请求.在本方案中，攻击者可能希望假冒阅读器重新发送随机矢量a和认证请求，得到标签发送过来的ID而达到跟踪的目的，但本方案中当标签认证阅读器失败时，会保存阅读器发送的随机矢量a，当下次认证时，如果阅读器仍是发送相同的随机矢量则认为是重放攻击，结束认证.如果标签认证阅读器成功，即使攻击者重放随机矢量a，标签的ID已更新也达不到跟踪的目的.由于本方案实现了双向认证，并且认证双方都产生了随机矢量，攻击者利用重放攻击来通过认证更不可能.
5) 克隆攻击.由于本协议在认证向量中异或PUF输出kp′，攻击者模拟PUF功能非常困难，攻击者不能复制出一个合法的标签，所以本协议可以抵御克隆攻击.
6) 内存读取攻击.标签采用了PUF模块，当攻击者试图读取标签存储的密钥信息时，会破坏标签的物理特性，改变PUF，使得标签失效，而即使攻击者获得了也无法得到PUF(ki)，所以即使攻击者拥有kx、ky和ki，也无法认证通过.
7) 中间人攻击.根据文献[7]中的攻击方法，攻击者需要构造一些参数使认证通过，经过多次攻击后能得到kx和ky，HB#协议只有阅读器认证标签，本协议实现了双向认证，攻击者构造的参数很难使双向认证都通过，攻击复杂度呈指数级增长.在参数kx为80，ky为512，m为1 164，η为0.25，t为405的HB#协议中，中间人攻击的复杂度为225，那么同参数的PUF-HB#协议的中间人攻击复杂度为250.本协议中认证成功之后标签的ID会更新，攻击者不容易确定它所攻击的标签，并且攻击者还很难跟踪标签，而中间人攻击需要多次认证通过才能得到密钥kx和ky，因此更新ID加大了中间人攻击的难度.即使攻击者得到了kx和ky，但是由于PUF-HB#协议中z1的计算还需要异或PUF(ki)，攻击者无法获得ki，并且本协议可以抵抗克隆攻击，攻击者无法克隆出相同的标签.因此，本协议可以解决中间人攻击的问题.
4.2 性能分析下面分析本方案的错误拒绝率PFR、错误接受率PFA、通信量、标签的存储量和标签的计算量.
对于阅读器错误接受非法标签的概率PFA，本协议和HB#协议相同，即
|
(1) |
标签认证阅读器的方式就是1个HB#协议过程，所以标签错误接受非法阅读器的概率P′ FA与PFA相等.
阅读器错误拒绝合法标签的条件为|kp⊕PUF(ki)⊕v1|大于um，设PUF输出错误的概率为PFW，则连续执行n(假设为奇数)次PUF，对于每1位取0和1出现次数较多的作为该位实际值，那么最终对于PUF输出的每1位错误的概率PFF为
|
(2) |
对于a ·X ⊕ b ·Y ⊕kp⊕z1的1位为1的概率P1为
|
(3) |
而阅读器错误拒绝合法标签的概率PFR为
|
(4) |
由于PFF很小，P1近似等于η，所以PFR和原HB#协议相差不多.标签认证阅读器的方式就是1个HB#协议过程，所以标签错误接受非法阅读器的概率P′ FR和HB#协议计算阅读器拒绝合法标签的式子是相同的，即
|
(5) |
在通信开销上，由于进行了双向认证和ID查询及更新，整个认证过程共需传输1 746 bit数据，不到原HB#协议的2倍.标签的存储开销上，需要多存储80 bit的随机矢量a，96 bit的ID，96 bit的kt和ki，所以存储开销相对HB#协议增加得不多.在计算量上执行了2次HB#运算和数次PUF计算，所以标签计算量比较轻量级.但是由于标签发送ID给阅读器，可以很大程度上减小阅读器查询密钥的开销，这是本方案的又一优点.在硬件开销上，标签需要部署PUF模块，但是不再需要部署随机数发生器，所以硬件消耗不比HB#协议大.
4.3 与HB#协议的对比分析协议中参数的取值为：a的长度为80 bit，b的长度为512 bit，m为441 bit，η为0.125，um为113 bit，则可以得到HB#和PUF-HB#协议的多项性能值，如表 1所示.
|
表 1 HB#协议和PUF-HB#协议的比较 |
从表 1可以看出PUF-HB#实现了双向认证，并且能抵抗内存读取攻击、克隆攻击和中间人攻击.通信量和存储量都没有达到HB#协议的2倍，存储量只增长了300多比特，仍适用于低成本标签；通信量增加了0.5倍左右，对认证协议无本质影响；硬件消耗与HB#协议差不多，计算量稍有增加，但可以很大程度上减轻阅读器搜索密钥的负担.因此PUF-HB#是安全性很高的轻量级双向认证协议.
5 结束语在分析HB#协议和PUF特性的基础上，提出了轻量级RFID双向认证协议PUF-HB#，巧妙地将这两类协议结合在一起，不仅实现了标签与阅读器的双向认证功能，还保留了HB#协议的优点，即错误拒绝率和错误接受率很小，计算量和通信量也较小；特别地，通过采用PUF，该协议能够抵抗克隆攻击、重放攻击、去同步攻击和内存读取攻击，而且保障了标签的位置隐私安全.
| [1] |
邓淼磊, 朱昭, 石金娥, 等. RFID标签的不可追踪性[J]. 北京邮电大学学报, 2010, 33(2): 44–47.
Deng Miaolei, Zhu Zhao, Shi Jin'e, et al. Untrace-ability of RFID tags[J]. Journal of Beijing University of Posts and Telecommunications, 2010, 33(2): 44–47. |
| [2] | Hopper N J, Blum M. Secure human identification protocols[J]. Lecture Notes in Computer Science, 2001(2248): 52–66. |
| [3] | Juels A, Weis S. Authenticating pervasive devices with human protocols[J]. Lecture Notes in Computer Science, 2005(3126): 293–308. |
| [4] | Gilbert H，Robshaw M，Sibert H. HB#: increasing the security and efficiency of HB+[C]//Advances in Cryptology-EUROCRYPT 2008. Istanbul: Springer Press，2009: 361-378. |
| [5] | Berlekamp E R, Mceliece R J, Tilborg H C. On the inherent intractability of certain coding problems[J]. IEEE Transactions on Information Theory, 1978, 24(3): 384–386. doi: 10.1109/TIT.1978.1055873 |
| [6] | Halevi T，Saxena N，Halevi S. Using HB family of protocols for privacy-preserving authentication of RFID tags in a population[C]//RFIDsec 2009. Leuven: arXiv Press，2009: 1-15. https://www.researchgate.net/publication/220593580_Lightweight_RFID_authentication_with_forward_and_backward_security |
| [7] | Ouafi K, Overbeck R, Vaudenay S. On the security of HB# against a man-in-the-middle attack[J]. Lecture Notes in Computer Science, 2008(5350): 108–124. |
| [8] | Avoine G, Martin B, Martin T. Tree-based RFID authentication protocols are definitively not privacy friendly[J]. Lecture Notes in Computer Science, 2010(6370): 103–122. |
| [9] | Gassend B，Clarke D，Dijk M V，et al. Silicon physical random functions[C]//Proceedings of the 9th ACM Conference on Computer and Communications Security (2002). Washington，DC: ACM Press，2002: 148-160. |
| [10] | Lee J W，Lim D，Gassend B，et al. A technique to build a secret key in integrated circuits with identification and authentication applications[C]//VLSI Circuits (2004). Honolulu: IEEE Press，2004: 176-179. https://link.springer.com/article/10.1007/s13389-016-0119-4 |