一種RFID系統密鑰無線生成算法

左 文 濤

(廣州工商學院計算機科學與工程系 廣東 廣州 510006)

0 引 言

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

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

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

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

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

鑒于此，本文設計一種設定后向信道可竊聽的動態無線方式生成共享密鑰的算法。為推進算法的運用范圍，對共享密鑰的運用環境進行分析，設計了能夠適用于三種不同環境下的共享密鑰生成算法。為使算法能夠適用于現有的RFID系統中，即不增加RFID系統中通信實體的計算量，算法在加密過程中選擇計算量較小的按位運算，對所要傳輸的信息進行加密。最大程度上降低通信實體的存儲空間，將標簽的標識符以及標簽的假名作為參數進行運算，一定程度上可以降低存儲空間。

1 共享密鑰生成算法

由標簽、讀寫器、后臺數據庫三部分可以組成一個RFID系統。讀寫器與后臺數據庫采用有線方式交換信息，一般鏈路安全，故可以將兩者看成一個整體；標簽與讀寫器之間通過無線方式進行通信，一般認定為不安全鏈路[11]。算法中涉及到的符號如表1所示。

表1 算法符號說明

續表1

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

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

1.1 單標簽密鑰生成算法

單標簽密鑰生成算法如圖1所示。

圖1 單標簽密鑰生成協議

公式符號說明見表2。

表2 單標簽密鑰生成算法公式符號說明

結合圖1，算法描述如下：

步驟一讀寫器向標簽發出密鑰生成請求Request命令。

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

有關M1的具體計算方法參照表2所示。

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

如果沒有查找到，說明標簽是偽造的，算法即刻停止。如果查找到，說明標簽通過讀寫器的驗證，并進行如下步驟：

(1) 讀寫器生成一個隨機數，記作x。

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

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

步驟四標簽接收信息后，進行如下操作：

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

(2) 利用接收到的M3、自身存放的標識符ID進行計算M3⊕ID。

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

(4) 利用自身存放的標識符ID、計算得到的隨機數x；自身存放的假名標識符ID_S計算得到共享密鑰KEY。

1.2 多標簽密鑰生成算法

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

多標簽密鑰生成算法如圖2所示。

圖2 多標簽密鑰生成協議

公式符號說明見表3。

表3 多標簽密鑰生成算法公式符號說明

1.3 群組標簽密鑰生成算法

群組標簽密鑰生成算法如圖3所示。

圖3 群組標簽密鑰生成協議

公式符號說明見表4。

表4 群組標簽密鑰生成算法公式符號說明

結合圖3，具體算法過程如下：

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

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

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

(1) 讀寫器生成一個隨機數，記作x。

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

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

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

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

其中標簽一端計算共享密鑰KEY的過程如下：KEY=KEY_i⊕ID_i_S_L。

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

2 安全性分析

本節采用基于BAN邏輯對算法進行形式化證明[12]，選取單標簽密鑰生成算法為例進行證明。

1) 算法的理想化模型：

消息①R→T：Request；

消息②T→R：M1；

消息③R→T：M2，M3。

2) 算法的初始假設：

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

P6：T|≡#(x)，標簽相信隨機數x的新鮮性。

P7：R|≡T|?M1，讀寫器相信標簽對消息M1的管轄權。

P8：T|≡R|?M2，標簽相信讀寫器對消息M2的管轄權。

P9：T|≡R|?M3，標簽相信讀寫器對消息M3的管轄權。

3) 算法的安全目標:

G1：T|≡M2，標簽相信消息M2。

G2：T|≡M3，標簽相信消息M3。

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

4) 算法的分析推理:

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

3 性能分析

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

對單標簽密鑰生成算法進行性能分析，結果如表5所示。

表5 單標簽密鑰生成算法性能分析

表5中，按位異或運算的計算量用符號ph來表示，按位與運算的計算量用符號pm來表示。設定標簽的標識符ID、假名標識符ID_S長度一致，且用pn表示長度。

單標簽密鑰生成算法中，標簽一端在計算M1的過程中，第一次進行“異或運算”。在步驟四中，計算M2⊕ID_S_L與M3⊕ID時，會進行第二次及第三次“異或運算”。同時計算共享密鑰KEY時，涉及到2次的“與運算”。基于上述，標簽端的計算量包含以下：3次“異或運算”、2次“與運算”，即3ph+2pm。

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

標簽一端需要存放如下信息：標簽的標識符ID、標簽的假名標識符ID_S，因此標簽一端的存儲空間為2pn。

通過上面的分析可以得出：算法采用位運算進行加密，使得標簽一端的計算量較低，能夠滿足標簽低計算量的要求。產生隨機數的操作放在讀寫器一端進行，使得標簽一端不再產生隨機數，從而可以減少實現功能的總的門電路數量，達到降低標簽成本的目標。因此，本文算法具有低計算量、低成本的優勢，且滿足系統所需的安全需求。

4 結 語

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