基于非線性譯碼問題的 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.