基于碼分多址防碰撞的射頻識別認證協(xié)議

王云峰 張 斌 劉 洋 費曉飛

?

基于碼分多址防碰撞的射頻識別認證協(xié)議

王云峰*張 斌 劉 洋 費曉飛

(解放軍信息工程大學(xué) 鄭州 450001)

該文針對射頻識別(RFID)領(lǐng)域中的安全認證協(xié)議和多標簽防碰撞算法兩個研究熱點，設(shè)計了一種基于碼分多址防碰撞算法的RFID安全認證協(xié)議。協(xié)議支持密鑰的動態(tài)更新并引入標志位機制選擇備用密鑰來抵御數(shù)據(jù)庫同步攻擊，同時結(jié)合碼分多址技術(shù)，應(yīng)用重傳隨機數(shù)進行擴頻碼的選擇，實現(xiàn)一次重傳解決多標簽識別中因數(shù)據(jù)碰撞造成的標簽不識別的問題。首先，描述協(xié)議的流程及防碰撞原理；其次，應(yīng)用SVO邏輯對認證協(xié)議的正確性進行證明；最后，對應(yīng)用該認證協(xié)議的系統(tǒng)吞吐效率進行數(shù)值分析，分析表明其吞吐效率高于傳統(tǒng)防碰撞算法。

射頻識別；碼分多址；認證協(xié)議；防碰撞

1 引言

射頻識別RFID(Radio Frequency Identify)技術(shù)是通過無線射頻方式對目標進行自動識別的非接觸雙向數(shù)據(jù)通信技術(shù)。其特有的非接觸式自動識別性能，使其被廣泛應(yīng)用到交通、物流供應(yīng)鏈管理和零售行業(yè)等領(lǐng)域[1]。

RFID系統(tǒng)中，由于無線信道的開放特性，導(dǎo)致標簽與閱讀器之間的信息傳輸易遭到竊聽、干擾、欺騙和篡改。為解決RFID系統(tǒng)存在的安全問題，目前已提出多種認證協(xié)議，一般可分為兩類：一類是靜態(tài)機制認證協(xié)議，主要包括分布式RFID詢問-響應(yīng)協(xié)議[2]、輕量級同步認證協(xié)議[3]和基于DES加密的認證協(xié)議[4]等。該類協(xié)議能夠抵御竊聽、跟蹤、重放和欺騙等常見攻擊，但不能對密鑰進行更新，使用該類協(xié)議的系統(tǒng)存在標簽密鑰泄露，進而導(dǎo)致系統(tǒng)內(nèi)所有標簽標識ID被攻擊者竊取的安全隱患，同時計算復(fù)雜、成本較高。另一類是動態(tài)機制認證協(xié)議，包括Hash鏈協(xié)議[5]、基于雜湊ID變化協(xié)議[6]和基于流密碼的協(xié)議[7]等，此類協(xié)議考慮對ID的保護，每次認證后都更新ID，但存在標簽與閱讀器之間數(shù)據(jù)不同步的隱患。因此，設(shè)計支持不斷更新密鑰并能消除數(shù)據(jù)不同步隱患的認證協(xié)議已成為研究熱點。

設(shè)計高效的防碰撞算法是多標簽識別問題的另一熱點。常用的防碰撞算法一般可分為兩類：一類是基于時隙隨機分配的ALOHA算法，包括幀時隙ALOHA算法[8]、分群時隙ALOHA算法[9]和分組動態(tài)幀時隙算法[10]等。此類算法簡單、便于實現(xiàn)、成本低，但系統(tǒng)吞吐量小，且存在標簽無法被識別的情況。另一類是基于二進制樹搜索的算法，主要包括自適應(yīng)四叉樹搜索算法[11]、自適應(yīng)多叉樹算法[12]和基于識別碼分組的算法[13]等。該類算法能夠識別讀寫器有效通信范圍內(nèi)所有標簽，但計算復(fù)雜、延時較長。

文獻[14]提出了一種基于碼分多址技術(shù)的RFID防碰撞算法，算法可以同時識別系統(tǒng)中的多個標簽，但未明確指出多標簽碰撞情況下擴頻碼的選擇方法，無法避免數(shù)據(jù)再次碰撞。結(jié)合文獻[14]的設(shè)計思路，針對數(shù)據(jù)碰撞問題，本文提出一種基于碼分多址防碰撞的RFID認證協(xié)議。該協(xié)議將靜態(tài)和動態(tài)機制的優(yōu)點相結(jié)合，支持密鑰的動態(tài)更新并引入標志位機制選擇備用密鑰來抵御數(shù)據(jù)庫同步攻擊。同時，協(xié)議結(jié)合碼分多址技術(shù)，應(yīng)用重傳隨機數(shù)進行擴頻碼的選擇，實現(xiàn)一次重傳解決多標簽識別中因數(shù)據(jù)碰撞造成的標簽不識別的問題。

2 基于碼分多址防碰撞RFID認證協(xié)議

基于碼分多址防碰撞的RFID協(xié)議認證流程如圖1所示，文中符號見表1。

表1符號描述

符號描述 ID標簽身份標識 K,K'標簽密鑰K和備用密鑰K' PRNG隨機數(shù)發(fā)生器 RT標簽產(chǎn)生的隨機數(shù) RR閱讀器產(chǎn)生的隨機數(shù) 重傳機制中閱讀器產(chǎn)生的新隨機數(shù) Flag1 bit防數(shù)據(jù)同步攻擊標志位 N系統(tǒng)內(nèi)置擴頻碼數(shù)量 M擴頻碼 擴頻運算 密鑰為K的Hash運算值的左半部 密鑰為K'的Hash運算值的右半部

協(xié)議中閱讀器存儲著ID和，標簽存儲著IDR和Flag。

認證和密鑰更新流程如下：

(1)閱讀器向標簽發(fā)送認證請求和R；

(2)標簽收到請求和R，生成范圍在1至之間的隨機數(shù)R并將其儲存，同時計算(R+R) mod的值，標簽選擇內(nèi)置對應(yīng)的第個Gold序列作為擴頻碼；

圖1 基于碼分多址防碰撞的協(xié)議認證流程

(4)閱讀器收到擴頻信息后，依次使用內(nèi)置擴頻碼進行解擴。若在同一時刻或數(shù)據(jù)處理過程中，存在兩個或以上數(shù)據(jù)應(yīng)用同一擴頻碼進行解擴，則發(fā)生碰撞，轉(zhuǎn)向流程(7)；否則繼續(xù)執(zhí)行；

若以上兩種信息對都不存在，則認證失敗，結(jié)束；

3 安全性能分析

3.1 SVO邏輯分析證明

協(xié)議的分析證明采用形式化驗證邏輯SVO[15]，通過認證協(xié)議運行過程中消息的接收和發(fā)送，從初始假設(shè)逐漸推導(dǎo)出協(xié)議的目標。證明過程中，R代表閱讀器，T代表標簽，公理A1, A2, A3, A4參見參考文獻[15]中SVO邏輯推理規(guī)則。

RFID雙向認證協(xié)議流程分析如下：

(1)初始假設(shè)

(3)消息接收

(4)主體對接收到消息的理解 由于閱讀器在接收到消息前不知道標簽對應(yīng)的密鑰和ID，因此不知道接收的內(nèi)容，故

(5)接收者對消息的解釋

(6)使用SVO邏輯推導(dǎo)

由P2, P9，推論a和A1可得：

由推論d和消息發(fā)送公理A4:

由P7, P10, A1可得：

由P2, P11，推論a和A1可得：

由P1, A2, A1和NEC規(guī)則可得：

由推論b，推論c, A3, A1和NEC規(guī)則可得：

3.2 抗攻擊分析

(1)防竊聽和跟蹤攻擊：單向Hash函數(shù)的加密，使攻擊者無法還原標簽與閱讀器間信息明文，因此協(xié)議可抵御竊聽攻擊。同時，標簽在每次通信中傳遞的信息不固定，所以不能實現(xiàn)對標簽的跟蹤。

(2)防重放和欺騙攻擊：由于閱讀器每次通信時都產(chǎn)生隨機數(shù)，攻擊者無法預(yù)知和控制，所以記錄并重放泄漏的消息，偽裝成合法用戶的方法對系統(tǒng)無效，數(shù)據(jù)庫不會給予認證。

(3)防數(shù)據(jù)庫同步攻擊：為解決數(shù)據(jù)庫和標簽的數(shù)據(jù)同步問題，協(xié)議提出了一種基于標志位Flag選擇密鑰或備用密鑰的認證機制。協(xié)議初始，標簽檢查Flag標志位。若Flag=1，表明前一輪協(xié)議認證中閱讀器與標簽之間實現(xiàn)了合法認證；若Flag=0，說明系統(tǒng)受到攻擊導(dǎo)致數(shù)據(jù)不同步，系統(tǒng)將自動采用備用密鑰進行加密。這樣，協(xié)議不僅實現(xiàn)了對標識ID的保護，同時解決了不斷更新加密密鑰帶來的數(shù)據(jù)庫不同步的安全問題。

(4)防內(nèi)部篡改：內(nèi)部篡改是指合法標簽有意地篡改自身ID值，偽裝成其它合法標簽，騙取閱讀器的認證。但由于每個標簽的認證密鑰獨立且不斷更新，偽裝的標簽無法產(chǎn)生與閱讀器對應(yīng)的合法信息，不能通過認證。同時，即使攻擊者獲得加密算法的硬件結(jié)構(gòu)和標簽數(shù)據(jù)信息，可無法掌握密鑰的更新，同樣無法通過閱讀器的認證。

(5)ID的保護與相互認證：不固定的密文傳輸及密鑰的實時更新等諸多保護措施，實現(xiàn)了對標簽ID的保護。同時，閱讀器和標簽之間的雙向認證使得系統(tǒng)安全性更加可靠。

協(xié)議安全性對比如表2(其中，×代表無法防御，○代表有效防御)。

表2協(xié)議安全性對比

協(xié)議名稱竊聽跟蹤重放欺騙ID保護數(shù)據(jù)同步內(nèi)部篡改認證方式 Hash-lock×××××○×單向 隨機Hash-lock×○×××○×單向 基于Hash的ID變化○○○×○××雙向 LCAP○○○○○××雙向 分布詢問應(yīng)答○○○○○○×雙向 本文協(xié)議○○○○○○○雙向

協(xié)議計算量對比如表3(其中，N表示Hash函數(shù)次數(shù)，N表示產(chǎn)生隨機數(shù)次數(shù)，表示系統(tǒng)中標簽的數(shù)量)。

與其它協(xié)議相比，標簽和閱讀器的計算量沒有增加，且查找過程是在計算能力強的數(shù)據(jù)庫進行，因此協(xié)議在保證安全性的同時，未給系統(tǒng)帶來多余計算負荷。

表3協(xié)議計算量對比

協(xié)議標簽閱讀器數(shù)據(jù)庫 NH NR NH NRNH NR Hash-lock1 0 0 0 0 0 隨機Hash-lock1 1(n+1)/2 0 1 0 基于Hash的ID變化3 0 0 0 3 1 LCAP2 0 0 1 1 0 分布詢問應(yīng)答2 1 0 1(n+3)/2 0 本文協(xié)議1 1 0 1(n+1)/2 0

4 防碰撞性能分析

4.1 認證協(xié)議防碰撞原理

本文認證協(xié)議基于碼分多址技術(shù)，在待識別的標簽數(shù)量較多時，有效地增加系統(tǒng)吞吐量，減少識別時間，提高搜索效率，其原理如圖2所示。某時刻有個標簽同時向閱讀器發(fā)送數(shù)據(jù)，系統(tǒng)隨機分配個擴頻碼(1~M)供碰撞數(shù)據(jù)使用，閱讀器端采用同樣的擴頻碼對信息解擴，以恢復(fù)標簽數(shù)據(jù)。當(dāng)有兩個或以上標簽選擇的擴頻碼相同時，標簽數(shù)據(jù)發(fā)生碰撞，此時啟動重傳機制，標簽重新選擇擴頻碼實現(xiàn)其數(shù)據(jù)的識別。協(xié)議中重傳機制的數(shù)據(jù)幀與確認幀發(fā)送時間關(guān)系如圖3所示，其中閱讀器和標簽封裝的幀格式如圖4，圖5所示。

反向鏈路，即標簽響應(yīng)閱讀器的命令并向其發(fā)送數(shù)據(jù)的鏈路。t是標簽數(shù)據(jù)幀的發(fā)送時間，由圖4可知其幀長=112 bit，在中高頻系統(tǒng)中，上行速率通常為=40 kbit/s[16]，因此數(shù)據(jù)幀發(fā)送時間t=/=0.0028 s，同理t=0.0028 s。數(shù)據(jù)幀沿反向鏈路傳到閱讀器還要經(jīng)歷物理鏈路造成的傳播時延t，同時閱讀器收到數(shù)據(jù)幀要經(jīng)歷處理時間t。閱讀器接著發(fā)送前向鏈路的確認幀，其發(fā)送時間為t，傳播時延為t，標簽收到確認幀需要時間t進行處理，再重新發(fā)送數(shù)據(jù)幀。為方便問題研究，設(shè)標簽與閱讀器的處理時間t遠小于數(shù)據(jù)幀發(fā)送時間，且由于標簽與閱讀器間作用距離短，傳播時延t為0，因此一次重傳時間可視為t+t+t

圖2 協(xié)議的多標簽識別原理

圖3 協(xié)議中數(shù)據(jù)幀與確認幀發(fā)送時間關(guān)系

圖4 標簽數(shù)據(jù)幀格式(前向鏈路)

圖5 閱讀器確認幀格式(反向鏈路)

定義系統(tǒng)的吞吐量為時間內(nèi)能成功解擴的標簽數(shù)據(jù)幀的均值，則其可以表示為

4.2 認證協(xié)議吞吐量分析

由吞吐量公式可知，由于發(fā)送時間≠0，因此吞吐效率函數(shù)在=處并不連續(xù)，當(dāng)<時，=，吞吐效率為直線=1；當(dāng)>時，吞吐效率為下降曲線，取幀發(fā)送時間=t=0.0028 s，系統(tǒng)吞吐量與負載和擴頻碼數(shù)量的關(guān)系如圖6所示。

由圖6可知，當(dāng)擴頻碼數(shù)量一定時，系統(tǒng)吞吐量會隨著負載的增加而先增大達到峰值再逐漸減小。同時負載一定時，吞吐量會隨著擴頻碼數(shù)量的增加而逐漸增大；圖7吞吐效率隨著的增加而逐漸減小，隨著的增加而逐漸增大，且，因此系統(tǒng)吞吐效率高于時隙ALOHA吞吐效率。協(xié)議算法與傳統(tǒng)算法吞吐效率對比如圖8所示，其中=100,=0.0028 s。由圖可知，本文算法吞吐效率曲線并不連續(xù)，當(dāng)<100時，吞吐效率=1.0，明顯高于傳統(tǒng)算法；>100時，吞吐效率為下降曲線，但仍高于傳統(tǒng)算法。

圖6 系統(tǒng)吞吐量與負載和擴頻碼數(shù)量的關(guān)系

圖7 吞吐效率與負載和擴頻碼數(shù)量的關(guān)系

圖8 本文協(xié)議算法與傳統(tǒng)算法吞吐效率對比圖

5 結(jié)束語

本文針對RFID領(lǐng)域中的安全認證協(xié)議和多標簽防碰撞算法兩個研究熱點，設(shè)計了一種基于碼分多址防碰撞算法帶有重傳機制的RFID安全認證協(xié)議。文中利用SVO邏輯對該協(xié)議進行形式化分析，在理論上證明其正確性與安全性，并在此基礎(chǔ)上分析了協(xié)議對各種攻擊的有效抵御。在防碰撞算法的分析中，分析了防碰撞算法中擴頻碼數(shù)量和標簽數(shù)量對吞吐量的影響，并應(yīng)用Matlab實現(xiàn)算法仿真。仿真結(jié)果證實了算法的正確性，其吞吐量高于傳統(tǒng)防碰撞算法。

[1] 謝磊, 殷亞鳳, 陳曦. RFID數(shù)據(jù)管理: 算法、協(xié)議與性能評測[J]. 計算機學(xué)報, 2013, 36(3): 457-470.

Xie Lei, Yin Ya-feng, and Chen Xi. RFID data management: algorithms, protocols and performance evaluation[J]., 2013, 36(3): 457-470.

[2] Rhee K, Kwak J, Kim S,.. Challenge-response based RFID authentication protocol for distributed database environment[C]. Proceedings of International Conference on Security in Pervasive Computing, Boppard, Germany, 2005(3450): 70-84.

[3] Ha J C, Ha J H, Moon S J,.. LRMAP: lightweight and re-synchronous mutual authentication protocol for RFID system[C]. Proceedings of the International Conference on Ubiquitous Convergence Technology, Berlin, Germany, 2007: 80-89.

[4] Wang Z, Xin W, Xu Z,.. A secure RFID communication protocol based on simplified DES[C]. Proceedings of the 2012 International Conference on Information Technology and Software Engineering, Berlin, Germany, 2013: 351-357.

[5] Miyako Ohkubo, Koutarou Suzuki, and Shingo Kinoshita. Hash-chain based forward-secure privacy protection scheme for low cost RFID[C]. Proceedings of the 2004 Symposium on Cryptography and Information Security (SCIS 2004), Sendai, Japan, 2004: 719-724.

[6] Henrici D and Muller P. Hash-based enhancement of location privacy for radio-frequency identification devices using varying identifiers[C]. Proceedings of the 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops, Washington, USA, 2004: 149-153.

[7] 龔潔中, 陳恭亮, 李林森, 等. 基于流密碼的RFID 安全認證協(xié)議[J]. 計算機工程, 2013, 38(13): 126-129.

Gong Jie-zhong, Chen Gong-liang, Li Lin-sen,.. RFID secure authentication protocol based on stream cipher[J]., 2013, 38(13): 126-129.

[8] Finkenzeller K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification[M].New York: John Wiley & Sons, 2003: 151-158.

[9] Hwang Tae-wook, Lee Byong-gyo, and Kim Young-Soo. Improved anti-collision scheme for high speed identification in RFID system[C]. First International Conference on Innovative Computing, Information and Control, Beijing, China, 2006, 2: 449-452.

[10] 龐宇, 彭琦, 林金朝, 等. 基于分組動態(tài)幀時隙的射頻識別防碰撞算法[J]. 物理學(xué)報, 2013, 62(14):148401-1-148401-8.

Pang Yu, Peng Qi, Lin Jin-chao,.. Reducing tag collision in radio frequency identification systems by using a grouped dynamic frame slotted ALOHA algorithm[J]., 2013, 62(14): 148401-1-148401-8.

[11] Shih B Y, Lo T W, Chen C Y. The research of quadtree search algorithms for anti-collision in radio frequency identification systems[J]., 2011, 6(25): 5342-5350.

[12] 張學(xué)軍, 蔡文琦, 王鎖萍. 改進型自適應(yīng)多叉樹防碰撞算法研究[J]. 電子學(xué)報, 2012, 40(1): 193-198.

Zhang Xue-jun, Cai Wen-qi, and Wang Suo-ping. One anti-collision algorithm based on improved adaptive multi-tree search[J]., 2012, 40(1): 193-198.

[13] 張學(xué)軍, 王娟, 王鎖萍. 基于標簽識別碼分組的連續(xù)識別防碰撞算法研究[J]. 電子與信息學(xué)報, 2011, 33(5): 1159-1165.

Zhang Xue-jun, Wang Juan, and Wang Suo-ping. An uninterrupted anti-collision algorithm with ID-based grouping for RFID system[J].&, 2011, 33(5): 1159-1165.

[14] 梁彪, 胡愛群, 秦中元. 一種新的RFID防碰撞算法設(shè)計[J]. 電子與信息學(xué)報, 2007, 29(9): 2158-2160.

Liang Biao, Hu Ai-qun, and Qin Zhong-yuan. A novel design for RFID anti-collision technique[J].&, 2007, 29(9): 2158-2160.

[15] Syverson P F, and Cervesato I. The logic of authentication protocols[J]., 2001, 2171: 63-137.

[16] 周曉光, 王曉華. 射頻識別(RFID)技術(shù)原理與應(yīng)用實例[M]. 北京: 人民郵電出版社, 2006: 113-114.

Zhou Xiao-guang and Wang Xiao-hua. Radio Frequency Identification (RFID) Technology Theory and Practical Examples[M]. Beijing: Posts & Telecommunications Press, 2006: 113-114.

王云峰： 男，1990年生，碩士生，研究方向為安全認證協(xié)議.

張 斌： 男，1969年生，教授，碩士生導(dǎo)師，研究方向為網(wǎng)絡(luò)信息安全.

劉 洋： 男，1980年生，博士生，研究方向為SOA安全、無線通信安全.

Radio Frequency Identification Authentication Protocol Based on CDMA Anti-collision Algorithm

Wang Yun-feng Zhang Bin Liu Yang Fei Xiao-fei

(,450001)

For addressing the two focus issues under research , security authentication protocol and the multi-tag anti-collision algorithm in the field of Radio Frequency IDentification (RFID), a Code Division Multiple Access (CDMA)-based anti-collision algorithm of the RFID authentication protocol is presented in this paper. The authentication protocol supports dynamic updates of the key and resists database synchronization attacks by using flag mechanism to select spare key. Meanwhile, by combining with CDMA and by retransmitting random number to select spreading code, the authentication protocol solves recognition of tags due to data collisions during the multi-tag identification by one-time retransmission. Firstly, the process of the authentication protocol and an anti-collision theory is described. Secondly, the SVO logic is used to prove correctness of the protocol in theory. Finally, numerical analysis of the system throughput applying the protocol shows that its throughput efficiency is higher than the traditional one.

Radio Frequency Identification (RFID); Code Division Multiple Access (CDMA); Authentication protocol; Anti-collision

TN91

A

1009-5896(2014)06-1472-06

10.3724/SP.J.1146.2013.01337

王云峰 wangyunfengieu@126.com

2013-09-04收到，2013-12-24改回