基于非線性譯碼問題的 RFID安全協(xié)議

陳民, 鄒傳云

(西南科技大學(xué) 信息工程學(xué)院,四川 綿陽 621010)

0 引言

RFID技術(shù)是眾多自動識別技術(shù)中一種,它是無線電技術(shù)和雷達(dá)技術(shù)的結(jié)合?；镜?RFID系統(tǒng)由標(biāo)簽(Tag)、閱讀器(Reader)以及計算機(jī)網(wǎng)絡(luò)組成[1]。一個安全的RFID系統(tǒng)應(yīng)該能解決以下兩個基本問題：認(rèn)證性和保密性[2]。

鑒于低成本的RFID系統(tǒng),2001年,Hopper和Blum基于LPN問題的困難性提出了HB協(xié)議[3]。HB協(xié)議雖然使電路結(jié)構(gòu)簡單化,但不能抵御主動攻擊,攻擊者可偽裝成閱讀器并將一個修改過的 a發(fā)給標(biāo)簽n次,利用高斯消元法可獲得密鑰 s。為此,Juels和 Weis提出了 HB+協(xié)議[4]。在 HB+協(xié)議中,標(biāo)簽和閱讀器共享兩個密鑰s1,s2∈{0,1}k,同時協(xié)議是從標(biāo)簽開始認(rèn)證。對于主動攻擊,HB+協(xié)議被證明是安全的,但Gilbert證明了其對來自一個偽裝成有效標(biāo)簽和閱讀器的中間人攻擊是不安全的[5]。針對 HB+協(xié)議的不足之處,本文提出了 NLHB+協(xié)議。

1 RFID安全協(xié)議的設(shè)計

1.1 非線性布爾函數(shù)和非線性譯碼問題

假設(shè) D和p都是正整數(shù)(d=n-p,n表示 HB協(xié)議執(zhí)行的次數(shù)),構(gòu)造一個非線性布爾函數(shù) y=f(x)[6](y∈{0,1}D,x∈{0,1}n);對于函數(shù) y=f(x)輸出的每一位 yi都能夠滿足：yi=xi+g(xi+1,xi+2,…,xi+p),其中 g(x)也是非線性布爾函數(shù)。當(dāng)取 p=3時,非線性布爾函數(shù) f以 x∈{0,1}n為輸入,y∈ {0,1}D為響應(yīng),即 yi=xi+xi+1xi+2+xi+2xi+3+xi+3xi+1,1≤i≤D;此時,僅需要 3個與門和 3個異或門就可得到 yi,計算量小而且工程上又易實現(xiàn),可應(yīng)用于多種安全協(xié)議的設(shè)計。當(dāng)然,肯定也可在RFID標(biāo)簽上實現(xiàn)。

在文獻(xiàn)[7]中,LPN問題被詳細(xì)地闡述,指出它是噪聲存在情況下的奇偶性問題;在不同的環(huán)境中有不同的描述,MDP問題、Syndrome譯碼問題以及非線性譯碼問題等都是LPN問題的變型。下面以矩陣運算定義非線性譯碼問題。

定義：A是一個隨機(jī)的 k×n二元矩陣,噪聲參數(shù) ε∈(0,1/2),s是一個隨機(jī)的k比特矢量,v是一個隨機(jī)的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),可證明非線性譯碼問題的困難性;依據(jù)其困難性的性質(zhì),本文提出了 NLHB+協(xié)議。

1.2 NLHB+協(xié)議的設(shè)計

相對于 HB+協(xié)議,以非線性譯碼問題為基礎(chǔ),借鑒它的“挑戰(zhàn) -響應(yīng)”認(rèn)證模式[2],提出了 NLHB+協(xié)議,其并行形式的流程如圖 1所示。

圖 1 并行的 NLHB+協(xié)議

在系統(tǒng)運行前,標(biāo)簽和閱讀器預(yù)共享密鑰s1,s2;以并行的形式,協(xié)議認(rèn)證過程如下：

①標(biāo)簽向閱讀器發(fā)送一個隨機(jī)矩陣 B∈{0,}k×n;

②閱讀器生成一個隨機(jī)的挑戰(zhàn)矩陣 A∈{0,1}k×n,并發(fā)送給標(biāo)簽;

③標(biāo)簽使用當(dāng)前的共享密鑰 s1和 s2,計算 z=f(s1B)⊕f(s2A)⊕v,隨后將計算值 z發(fā)送給閱讀器;

④閱讀器收到 z值后,驗證 d′=d(z,f(s1B)⊕f(s2A))≤ε′D是否成立,如果成立,認(rèn)證通過,反之,認(rèn)證失敗。

NLHB+協(xié)議執(zhí)行過程簡單,硬件上利用與門和異或門就可實現(xiàn),標(biāo)簽接收到挑戰(zhàn)矩陣 A后不用緩存可以直接計算,節(jié)省了存儲空間,另外噪聲矢量也易產(chǎn)生[3]?；诜蔷€性譯碼問題的困難性,NLHB+協(xié)議能抵御被動攻擊的,在“DET”模型中,現(xiàn)將證明它能有效抵御主動攻擊。

2 協(xié)議性能分析

以“DET”模型為平臺,這里證明了 NLHB+協(xié)議抵御主動攻擊的安全性。下面是一些相關(guān)概念的定義：

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+主動攻擊者,該算法分為兩個階段。詢問階段：以一個隨機(jī)的矩陣 B∈{0,1}k×n作為輸入,然后以挑戰(zhàn)矩陣A為響應(yīng),合法的 NLHB+標(biāo)簽利用矩陣 A和 B計算 z=f(s1B)⊕f(s2A)⊕v并發(fā)送給Z+;挑戰(zhàn)階段：首先向 NLHB+閱讀器發(fā)送一個盲矩陣 B?;其次接收到閱讀器發(fā)送的挑戰(zhàn)矩陣 A?后,生成響應(yīng) z?(這個?z能使閱讀器以一定的概率生成“Yes”并發(fā)送給 Z+)。

圖 2 詢問階段

圖 3 挑戰(zhàn)階段

3 結(jié)語

依據(jù)非線性譯碼問題的困難性,借鑒 HB+協(xié)議的認(rèn)證模式,提出了 NLHB+協(xié)議。在“DET”模型中證明了 NLHB+協(xié)議可以抵御各類攻擊,尤其是主動攻擊。另外實現(xiàn) NLHB+協(xié)議功能的硬件電路較簡單,僅需要適度的邏輯門即可。在同等的安全性前提下,和現(xiàn)有的 RFID認(rèn)證協(xié)議相比,NLHB+協(xié)議計算量低些,故更適合于資源受限并低成本的 RFID系統(tǒng)。由于作者能力有限,所述的噪聲矢量是協(xié)議自定義的,并且協(xié)議并未涉及中間人攻擊,因此,NLHB+協(xié)議的優(yōu)勢需要進(jìn)一步地研究。

[1]王睿,趙龑.RFID技術(shù)及其應(yīng)用系統(tǒng)構(gòu)架的研究[J].通信技術(shù),2009,42(05)：116-118.

[2]劉慶華,霍騰飛,鄧依群,等.基于Hash函數(shù)的隨機(jī)RFID認(rèn)證協(xié)議[J].通信技術(shù),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]常祖領(lǐng),柯品惠,張劼,等.高非線性度多輸出布爾函數(shù)的構(gòu)造[J].電子學(xué)報,2008,36(01)：141-145.

[7]唐靜,姬東耀.基于 LPN問題的 RFID安全協(xié)議設(shè)計與分析[J].電子與信息學(xué)報,2009,31(02)：439-443.