基于非线性译码问题的 RFID安全协议

陈民, 邹传云

(西南科技大学 信息工程学院,四川 绵阳 621010)

0 引言

RFID技术是众多自动识别技术中一种,它是无线电技术和雷达技术的结合。基本的 RFID系统由标签(Tag)、阅读器(Reader)以及计算机网络组成[1]。一个安全的RFID系统应该能解决以下两个基本问题：认证性和保密性[2]。

鉴于低成本的RFID系统,2001年,Hopper和Blum基于LPN问题的困难性提出了HB协议[3]。HB协议虽然使电路结构简单化,但不能抵御主动攻击,攻击者可伪装成阅读器并将一个修改过的 a发给标签n次,利用高斯消元法可获得密钥 s。为此,Juels和 Weis提出了 HB+协议[4]。在 HB+协议中,标签和阅读器共享两个密钥s1,s2∈{0,1}k,同时协议是从标签开始认证。对于主动攻击,HB+协议被证明是安全的,但Gilbert证明了其对来自一个伪装成有效标签和阅读器的中间人攻击是不安全的[5]。针对 HB+协议的不足之处,本文提出了 NLHB+协议。

1 RFID安全协议的设计

1.1 非线性布尔函数和非线性译码问题

假设 D和p都是正整数(d=n-p,n表示 HB协议执行的次数),构造一个非线性布尔函数 y=f(x)[6](y∈{0,1}D,x∈{0,1}n);对于函数 y=f(x)输出的每一位 yi都能够满足：yi=xi+g(xi+1,xi+2,…,xi+p),其中 g(x)也是非线性布尔函数。当取 p=3时,非线性布尔函数 f以 x∈{0,1}n为输入,y∈ {0,1}D为响应,即 yi=xi+xi+1xi+2+xi+2xi+3+xi+3xi+1,1≤i≤D;此时,仅需要 3个与门和 3个异或门就可得到 yi,计算量小而且工程上又易实现,可应用于多种安全协议的设计。当然,肯定也可在RFID标签上实现。

在文献[7]中,LPN问题被详细地阐述,指出它是噪声存在情况下的奇偶性问题;在不同的环境中有不同的描述,MDP问题、Syndrome译码问题以及非线性译码问题等都是LPN问题的变型。下面以矩阵运算定义非线性译码问题。

定义：A是一个随机的 k×n二元矩阵,噪声参数 ε∈(0,1/2),s是一个随机的k比特矢量,v是一个随机的D比特矢量,vi∈ {0,1|p(vi=1)=ε),i∈ {1,2,…,D},其汉明重量 wt(v)≤εD;已知 A,ε以及 z=f(sA)⊕v,总能找到一个 k比特矢量 s′,满足 d(z,f(s′A))≤εD(d(,)表示汉明距离)。

因此,以一个LPN问题为例(LPN问题已被证明是NPHard),可证明非线性译码问题的困难性;依据其困难性的性质,本文提出了 NLHB+协议。

1.2 NLHB+协议的设计

相对于 HB+协议,以非线性译码问题为基础,借鉴它的“挑战 -响应”认证模式[2],提出了 NLHB+协议,其并行形式的流程如图 1所示。

图 1 并行的 NLHB+协议

在系统运行前,标签和阅读器预共享密钥s1,s2;以并行的形式,协议认证过程如下：

①标签向阅读器发送一个随机矩阵 B∈{0,}k×n;

②阅读器生成一个随机的挑战矩阵 A∈{0,1}k×n,并发送给标签;

③标签使用当前的共享密钥 s1和 s2,计算 z=f(s1B)⊕f(s2A)⊕v,随后将计算值 z发送给阅读器;

④阅读器收到 z值后,验证 d′=d(z,f(s1B)⊕f(s2A))≤ε′D是否成立,如果成立,认证通过,反之,认证失败。

NLHB+协议执行过程简单,硬件上利用与门和异或门就可实现,标签接收到挑战矩阵 A后不用缓存可以直接计算,节省了存储空间,另外噪声矢量也易产生[3]。基于非线性译码问题的困难性,NLHB+协议能抵御被动攻击的,在“DET”模型中,现将证明它能有效抵御主动攻击。

2 协议性能分析

以“DET”模型为平台,这里证明了 NLHB+协议抵御主动攻击的安全性。下面是一些相关概念的定义：

Asef：一个遵循 ＜A,z=f(sA)⊕v的分布,A∈ {0,1}k×n,v为服从伯努利分布的 D比特噪声矢量。

Ukn+D：表示一个(kn+D))比特的均匀分布位串,换言之,一个位串 s∈Ukn+D,满足 Pr(S=g)=2-(kn+D),∀g∈{0,1}kn+D。

Z+：表示一个多项式时间的 NLHB+主动攻击者,该算法分为两个阶段。询问阶段：以一个随机的矩阵 B∈{0,1}k×n作为输入,然后以挑战矩阵A为响应,合法的 NLHB+标签利用矩阵 A和 B计算 z=f(s1B)⊕f(s2A)⊕v并发送给Z+;挑战阶段：首先向 NLHB+阅读器发送一个盲矩阵 Bˆ;其次接收到阅读器发送的挑战矩阵 Aˆ后,生成响应 zˆ(这个ˆz能使阅读器以一定的概率生成“Yes”并发送给 Z+)。

图 2 询问阶段

图 3 挑战阶段

3 结语

依据非线性译码问题的困难性,借鉴 HB+协议的认证模式,提出了 NLHB+协议。在“DET”模型中证明了 NLHB+协议可以抵御各类攻击,尤其是主动攻击。另外实现 NLHB+协议功能的硬件电路较简单,仅需要适度的逻辑门即可。在同等的安全性前提下,和现有的 RFID认证协议相比,NLHB+协议计算量低些,故更适合于资源受限并低成本的 RFID系统。由于作者能力有限,所述的噪声矢量是协议自定义的,并且协议并未涉及中间人攻击,因此,NLHB+协议的优势需要进一步地研究。

[1]王睿,赵龑.RFID技术及其应用系统构架的研究[J].通信技术,2009,42(05)：116-118.

[2]刘庆华,霍腾飞,邓依群,等.基于Hash函数的随机RFID认证协议[J].通信技术,2009,42(08)：59-61.

[3]HOPPER N J,M Blum.Secure Human Identificationprotocols[C].Germany：Springer-Verlag,2001：52-66.

[4]JUELS A,WEIS S.Authenticating Pervasive Devices with Human Protocols[C].Germany：Springer Verlag,2005：293-308.

[5]Gilbert H,Robshaw M,Sibert H.An Active Attack Against HB+-a Provably Secure Lightweight Protocol[J].Electronic Letters,2005,41(21)：1169-1170.

[6]常祖领,柯品惠,张劼,等.高非线性度多输出布尔函数的构造[J].电子学报,2008,36(01)：141-145.

[7]唐静,姬东耀.基于 LPN问题的 RFID安全协议设计与分析[J].电子与信息学报,2009,31(02)：439-443.