一種RFID系統(tǒng)密鑰無線生成算法

左 文 濤

(廣州工商學(xué)院計(jì)算機(jī)科學(xué)與工程系 廣東 廣州 510006)

0 引 言

無線射頻識(shí)別(RFID)是一種不需要接觸，就可以自動(dòng)進(jìn)行識(shí)別的技術(shù)[1]。RFID系統(tǒng)因具備眾多優(yōu)點(diǎn)，比如：易攜帶、成本低、壽命長等，已廣泛在生活中運(yùn)用，比如：門禁系統(tǒng)、公交卡系統(tǒng)等[2-3]。

現(xiàn)有的RFID系統(tǒng)基本上都是由三部分組成，即：標(biāo)簽、讀寫器、后臺(tái)數(shù)據(jù)庫。常見的系統(tǒng)中，標(biāo)簽與讀寫器之間傳輸信息信道不安全，容易被攻擊者監(jiān)聽；讀寫器與后臺(tái)數(shù)據(jù)庫之間采用安全的鏈路傳輸信息，因此在讀寫器與標(biāo)簽之間在進(jìn)行信息傳遞之前，需要進(jìn)行安全的雙向認(rèn)證[4]。雙向認(rèn)證過程中涉及到共享密鑰，現(xiàn)有的系統(tǒng)中，共享密鑰絕大多數(shù)都是在標(biāo)簽出廠的時(shí)候都已經(jīng)設(shè)定好。

標(biāo)簽出廠之時(shí)設(shè)定好共享密鑰存在缺陷，比如：大量的標(biāo)簽中設(shè)定好的共享密鑰，需要額外的空間來進(jìn)行存放，且還需要人進(jìn)行看管，從而產(chǎn)生密鑰托管問題；共享密鑰在標(biāo)簽出廠的時(shí)候設(shè)定好，在標(biāo)簽后續(xù)的使用過程中，用戶根本沒有辦法按照自己的意愿來自定義共享密鑰的值[5-7]。為了解決上面的問題，一些創(chuàng)新型的算法被設(shè)計(jì)出來[8-10]。

文獻(xiàn)[8]中首次提出動(dòng)態(tài)生成共享密鑰的算法。算法的主要思想是基于傳輸信道的前后非對(duì)稱性，即后向信道不可竊聽。但分析發(fā)現(xiàn)，實(shí)際運(yùn)用中，后向信道并不是完全不可竊聽，因此文獻(xiàn)中提及的算法存在一定的運(yùn)用局限性。雖文獻(xiàn)中的算法存在不足之處，但文獻(xiàn)中算法的思想給予其他研究人員較好的啟發(fā)。

在上述文獻(xiàn)的算法思想啟發(fā)之下，文獻(xiàn)[9]在彌補(bǔ)后向信道不可竊聽的局限之下設(shè)計(jì)出一種動(dòng)態(tài)生成共享密鑰的算法，同時(shí)彌補(bǔ)了原文獻(xiàn)算法的不足，但設(shè)計(jì)出的算法未能抵抗攻擊者發(fā)起的去同步化攻擊。文獻(xiàn)[10]設(shè)計(jì)了一種動(dòng)態(tài)生成共享密鑰的算法，采用對(duì)部分ID加密的機(jī)制進(jìn)行信息的傳輸，但算法無法抵抗攻擊者發(fā)起的重放攻擊。攻擊者在竊聽到上一輪信息后，對(duì)消息進(jìn)行重放，再加上攻擊者阻塞標(biāo)簽與讀寫器之間的通信，可以破解出相關(guān)隱私信息。

鑒于此，本文設(shè)計(jì)一種設(shè)定后向信道可竊聽的動(dòng)態(tài)無線方式生成共享密鑰的算法。為推進(jìn)算法的運(yùn)用范圍，對(duì)共享密鑰的運(yùn)用環(huán)境進(jìn)行分析，設(shè)計(jì)了能夠適用于三種不同環(huán)境下的共享密鑰生成算法。為使算法能夠適用于現(xiàn)有的RFID系統(tǒng)中，即不增加RFID系統(tǒng)中通信實(shí)體的計(jì)算量，算法在加密過程中選擇計(jì)算量較小的按位運(yùn)算，對(duì)所要傳輸?shù)男畔⑦M(jìn)行加密。最大程度上降低通信實(shí)體的存儲(chǔ)空間，將標(biāo)簽的標(biāo)識(shí)符以及標(biāo)簽的假名作為參數(shù)進(jìn)行運(yùn)算，一定程度上可以降低存儲(chǔ)空間。

1 共享密鑰生成算法

由標(biāo)簽、讀寫器、后臺(tái)數(shù)據(jù)庫三部分可以組成一個(gè)RFID系統(tǒng)。讀寫器與后臺(tái)數(shù)據(jù)庫采用有線方式交換信息，一般鏈路安全，故可以將兩者看成一個(gè)整體；標(biāo)簽與讀寫器之間通過無線方式進(jìn)行通信，一般認(rèn)定為不安全鏈路[11]。算法中涉及到的符號(hào)如表1所示。

表1 算法符號(hào)說明

續(xù)表1

算法在進(jìn)行之前，標(biāo)簽一端保存有如下信息：(ID,ID_S)；讀寫器一端保存有如下信息：(ID_i,ID_i_S)。

RFID系統(tǒng)在應(yīng)用中，一般情況下，是單個(gè)讀寫器與單個(gè)標(biāo)簽的通信，或單個(gè)讀寫器與多個(gè)標(biāo)簽的通信。基于上述的情況，標(biāo)簽與讀寫器之間的密鑰動(dòng)態(tài)生成情況可以分成下面三種情況：(1) 一個(gè)讀寫器，一個(gè)標(biāo)簽，兩者之間生成共享密鑰；(2) 一個(gè)讀寫器，多個(gè)標(biāo)簽，讀寫器與每個(gè)標(biāo)簽之間均生成一個(gè)共享密鑰，且每個(gè)共享密鑰都不相同；(3) 一個(gè)讀寫器，多個(gè)標(biāo)簽，讀寫器與多個(gè)標(biāo)簽之間生成的共享密鑰是一樣的，即多個(gè)標(biāo)簽共同享用一個(gè)相同的共享密鑰。

1.1 單標(biāo)簽密鑰生成算法

單標(biāo)簽密鑰生成算法如圖1所示。

圖1 單標(biāo)簽密鑰生成協(xié)議

公式符號(hào)說明見表2。

表2 單標(biāo)簽密鑰生成算法公式符號(hào)說明

結(jié)合圖1，算法描述如下：

步驟一讀寫器向標(biāo)簽發(fā)出密鑰生成請(qǐng)求Request命令。

步驟二標(biāo)簽收到消息后，利用自身存放的標(biāo)識(shí)符ID、自身存放的假名標(biāo)識(shí)符ID_S的右半部分ID_S_R計(jì)算得到M1；然后將M1傳送給讀寫器。

有關(guān)M1的具體計(jì)算方法參照表2所示。

步驟三讀寫器收到信息后，查找存放的(ID_i,ID_i_S)中是否有滿足M1的計(jì)算結(jié)果。

如果沒有查找到，說明標(biāo)簽是偽造的，算法即刻停止。如果查找到，說明標(biāo)簽通過讀寫器的驗(yàn)證，并進(jìn)行如下步驟：

(1) 讀寫器生成一個(gè)隨機(jī)數(shù)，記作x。

(2) 利用找到的假名標(biāo)識(shí)符ID_S的左半部分ID_S_L、自身生成的隨機(jī)數(shù)x計(jì)算得到M2；利用找到的標(biāo)識(shí)符ID、自身生成的隨機(jī)數(shù)x計(jì)算得到M3；利用找到的假名標(biāo)識(shí)符ID_S、找到的標(biāo)識(shí)符ID、自身生成的隨機(jī)數(shù)x計(jì)算得到共享密鑰KEY。

(3) 將一并傳送給標(biāo)簽。

步驟四標(biāo)簽接收信息后，進(jìn)行如下操作：

(1) 利用接收到的M2、自身存放的假名標(biāo)識(shí)符ID_S的左半部分ID_S_L進(jìn)行計(jì)算M2⊕ID_S_L。

(2) 利用接收到的M3、自身存放的標(biāo)識(shí)符ID進(jìn)行計(jì)算M3⊕ID。

(3) 比對(duì)M2⊕ID_S_L與M3⊕ID是否相等。不等，說明讀寫器存在問題，算法即刻停止；反之，通過上述計(jì)算可得到讀寫器生成的隨機(jī)數(shù)x。

(4) 利用自身存放的標(biāo)識(shí)符ID、計(jì)算得到的隨機(jī)數(shù)x；自身存放的假名標(biāo)識(shí)符ID_S計(jì)算得到共享密鑰KEY。

1.2 多標(biāo)簽密鑰生成算法

多標(biāo)簽密鑰生成算法過程與單標(biāo)簽密鑰生成算法過程大致一樣，其中算法主要不同之處在于：每個(gè)不同的標(biāo)簽在接收到讀寫器發(fā)送來的消息且通過驗(yàn)證之后，共享密鑰KEY的生成過程中需要根據(jù)每個(gè)標(biāo)簽的自身信息(ID_i,ID_i_S)來生成屬于自身的個(gè)體密鑰。算法其他地方一樣，故不再詳細(xì)闡述。

多標(biāo)簽密鑰生成算法如圖2所示。

圖2 多標(biāo)簽密鑰生成協(xié)議

公式符號(hào)說明見表3。

表3 多標(biāo)簽密鑰生成算法公式符號(hào)說明

1.3 群組標(biāo)簽密鑰生成算法

群組標(biāo)簽密鑰生成算法如圖3所示。

圖3 群組標(biāo)簽密鑰生成協(xié)議

公式符號(hào)說明見表4。

表4 群組標(biāo)簽密鑰生成算法公式符號(hào)說明

結(jié)合圖3，具體算法過程如下：

步驟一讀寫器向{T1，T2,…,Ti}廣播發(fā)送Request命令。

步驟二標(biāo)簽組里的標(biāo)簽在接收信息后，每個(gè)標(biāo)簽根據(jù)ID、ID_S_R進(jìn)行計(jì)算，依次可得到Q1，Q2，…，Qi；最后將一并傳送給讀寫器。

步驟三讀寫器接收信息后，在數(shù)據(jù)庫中查找已存放的信息(ID_i,ID_i_S)并計(jì)算是否與接收到的信息完全一致。存在不一致，表明有標(biāo)簽沒有應(yīng)答，讀寫器會(huì)再次向標(biāo)簽組發(fā)送Request命令。反之，說明每個(gè)標(biāo)簽都已經(jīng)應(yīng)答，并進(jìn)行如下操作：

(1) 讀寫器生成一個(gè)隨機(jī)數(shù)，記作x。

(2) 讀寫器利用自身生成的隨機(jī)數(shù)x、自身存放的假名標(biāo)識(shí)符ID_S的左半部分ID_S_L進(jìn)行計(jì)算，可得到一個(gè)唯一的共享密鑰KEY。

(3) 接著讀寫器為每一個(gè)標(biāo)簽Ti生成一個(gè)唯一的密鑰因子KEY_i。

(4) 最后讀寫器將KEY_i廣播發(fā)送給標(biāo)簽組里的所有標(biāo)簽。

步驟四標(biāo)簽組里的標(biāo)簽接收信息后，比對(duì)自身的標(biāo)號(hào)是否與接收到的KEY_i中的i值相等。不等，直接舍掉，不做任何操作；反之，標(biāo)簽用自身存放的假名標(biāo)識(shí)符ID_S的左半部分ID_S_L、接收到的KEY_i進(jìn)行計(jì)算，可得到群組標(biāo)簽的唯一共享密鑰KEY。

其中標(biāo)簽一端計(jì)算共享密鑰KEY的過程如下：KEY=KEY_i⊕ID_i_S_L。

綜上闡述，本文提出的算法具備如下優(yōu)勢(shì)：(1) 針對(duì)不同的情況設(shè)計(jì)出三種密鑰動(dòng)態(tài)生成的算法，能夠使得算法具備廣泛的適用范圍；(2) 算法在設(shè)計(jì)之時(shí)，遵行的前后向信道均可被攻擊者竊聽的原則，使得算法沒有局限性；(3) 算法對(duì)信息加密過程中僅用到“異或運(yùn)算”以及“與運(yùn)算”，兩者均屬于按位運(yùn)算，能夠減少通信實(shí)體的計(jì)算量。

2 安全性分析

本節(jié)采用基于BAN邏輯對(duì)算法進(jìn)行形式化證明[12]，選取單標(biāo)簽密鑰生成算法為例進(jìn)行證明。

1) 算法的理想化模型：

消息①R→T：Request；

消息②T→R：M1；

消息③R→T：M2，M3。

2) 算法的初始假設(shè)：

P5：R|≡#(x)，讀寫器相信隨機(jī)數(shù)x的新鮮性。

P6：T|≡#(x)，標(biāo)簽相信隨機(jī)數(shù)x的新鮮性。

P7：R|≡T|?M1，讀寫器相信標(biāo)簽對(duì)消息M1的管轄權(quán)。

P8：T|≡R|?M2，標(biāo)簽相信讀寫器對(duì)消息M2的管轄權(quán)。

P9：T|≡R|?M3，標(biāo)簽相信讀寫器對(duì)消息M3的管轄權(quán)。

3) 算法的安全目標(biāo):

G1：T|≡M2，標(biāo)簽相信消息M2。

G2：T|≡M3，標(biāo)簽相信消息M3。

G3：R|≡M1，讀寫器相信消息M1。

4) 算法的分析推理:

G2、G3的證明方法和上面一樣，因此不再闡述。

3 性能分析

本節(jié)將從性能角度對(duì)算法進(jìn)行詳細(xì)分析，性能分析選取的分析對(duì)象為標(biāo)簽通信實(shí)體，同時(shí)選取以下參數(shù)作為分析的目標(biāo)：算法的通信量、標(biāo)簽一端的存儲(chǔ)空間、標(biāo)簽一端的計(jì)算量。對(duì)單標(biāo)簽密鑰生成算法、多標(biāo)簽密鑰生成算法、群組標(biāo)簽密鑰生成算法進(jìn)行性能分析。三種情況性能分析相差不大，因此只選取單標(biāo)簽密鑰生成算法為例進(jìn)行性能分析。

對(duì)單標(biāo)簽密鑰生成算法進(jìn)行性能分析，結(jié)果如表5所示。

表5 單標(biāo)簽密鑰生成算法性能分析

表5中，按位異或運(yùn)算的計(jì)算量用符號(hào)ph來表示，按位與運(yùn)算的計(jì)算量用符號(hào)pm來表示。設(shè)定標(biāo)簽的標(biāo)識(shí)符ID、假名標(biāo)識(shí)符ID_S長度一致，且用pn表示長度。

單標(biāo)簽密鑰生成算法中，標(biāo)簽一端在計(jì)算M1的過程中，第一次進(jìn)行“異或運(yùn)算”。在步驟四中，計(jì)算M2⊕ID_S_L與M3⊕ID時(shí)，會(huì)進(jìn)行第二次及第三次“異或運(yùn)算”。同時(shí)計(jì)算共享密鑰KEY時(shí)，涉及到2次的“與運(yùn)算”?；谏鲜?，標(biāo)簽端的計(jì)算量包含以下：3次“異或運(yùn)算”、2次“與運(yùn)算”，即3ph+2pm。

整個(gè)通信過程中，涉及到的傳輸消息有M1、M2、M3，因此算法的通信量為3pn。

標(biāo)簽一端需要存放如下信息：標(biāo)簽的標(biāo)識(shí)符ID、標(biāo)簽的假名標(biāo)識(shí)符ID_S，因此標(biāo)簽一端的存儲(chǔ)空間為2pn。

通過上面的分析可以得出：算法采用位運(yùn)算進(jìn)行加密，使得標(biāo)簽一端的計(jì)算量較低，能夠滿足標(biāo)簽低計(jì)算量的要求。產(chǎn)生隨機(jī)數(shù)的操作放在讀寫器一端進(jìn)行，使得標(biāo)簽一端不再產(chǎn)生隨機(jī)數(shù)，從而可以減少實(shí)現(xiàn)功能的總的門電路數(shù)量，達(dá)到降低標(biāo)簽成本的目標(biāo)。因此，本文算法具有低計(jì)算量、低成本的優(yōu)勢(shì)，且滿足系統(tǒng)所需的安全需求。

4 結(jié) 語

為解決通信實(shí)體之間認(rèn)證所需的共享密鑰不再事前設(shè)定好問題，本文給出一種通過無線方式動(dòng)態(tài)生成共享密鑰的算法。結(jié)合實(shí)際應(yīng)用環(huán)境，給出適用于三種不同環(huán)境下的算法，使得所提算法具備廣泛的應(yīng)用范圍。算法采用簡(jiǎn)單的“異或運(yùn)算”、“與運(yùn)算”對(duì)傳輸信息進(jìn)行加密，一來可以不用明文直接傳輸，攻擊者難以攻擊；二來標(biāo)簽端的計(jì)算量較小，使算法適用于受限的低成本標(biāo)簽中。分析了算法安全性，表明其能夠抵抗攻擊者發(fā)起的常見的攻擊方式，滿足系統(tǒng)所需的安全要求。分析了算法性能，表明其對(duì)標(biāo)簽的計(jì)算量、標(biāo)簽的存儲(chǔ)空間要求并不高，適用于低成本的受限制的標(biāo)簽中。結(jié)合基于BAN邏輯對(duì)算法進(jìn)行形式化證明，分析了算法的正確性及可行性。