基于非线性译码问题的 RFID安全协议
2010-09-13陈民邹传云
陈民, 邹传云
(西南科技大学 信息工程学院,四川 绵阳 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问题的变型。下面以矩阵运算定义非线性译码问题。……
