一種改進的高效RFID加密安全協議

劉 念1，殷 業1，葉 龍2，肖 龍1，嚴 實1

(1.上海師范大學信息與機電工程學院，上海 200234；2.上海商學院信息與計算機學院，上海 201400)

1 概述

無線射頻識別(Radio Frequency Identification,RFID)是利用射頻信號來自動識別目標對象，并獲取其相關信息的一種非接觸式無線通信自動識別技術[1]。RFID在無線通信中有著廣泛應用的同時，在其無線信道中的標簽信息安全問題也存在很大的隱患[2]。針對RFID無線通信中的安全問題，國內外開展了很多的安全保密研究[3]，如Hash-Lock協議、Hash-Chain協議、樹形協議等，但這些加密安全協議在一定程度上都存在一些缺陷，本文針對這些協議的不足之處，結合密集環境下的目標識別問題，提出一個新的RFID加密安全協議，旨在提高低成本標簽的安全性，以及系統識別標簽的效率。

2 RFID中的安全問題

在實際應用環境中，RFID系統的閱讀器與后臺信息系統之間通過互聯網或局域網相連接，標簽與閱讀器之間則通過無線信道進行通信。一般認為閱讀器和后臺信息系統之間的信道為安全信道，閱讀器與標簽之間的信道為不安全信道，即其間發送的數據是易被攻擊者竊聽或篡改的。沒有可靠的信息安全機制，就無法有效地保護射頻標簽中的數據信息[4]。

RFID系統面臨的安全問題主要是數據的隱匿性、完整性、真實性和用戶隱私泄露問題，另一方面，標簽的成本會直接影響RFID的安全性能，要有可靠的信息安全機制，才能夠實現對低成本標簽安全威脅的高效防護[5]。一個好的安全協議要能夠實現在重放攻擊、跟蹤攻擊、假冒復制攻擊、信息篡改攻擊、插入攻擊等中有足夠的抗攻擊能力，能夠保證信息的認證性、秘密性以及完整性，并且在信息處理復雜度上做到最優[6]。

3 常見的安全協議

3.1 Hash-Lock協議

文獻[7]提出了Hash-Lock協議，利用Hash(ID)加密來代替真實的標簽ID以避免信息泄露和被跟蹤。Hash-Lock協議如圖1所示。

圖1 Hash-Lock協議

在該協議中，標簽T將自身信息ID進行Hash函數加密，將H(ID)信息發送給閱讀器R，后臺信息管理系統DB順次搜索到與該H(ID)匹配的（H（IDi）,K eyi,IDi）信息，從而完成驗證。Hash-Lock協議可以有效地進行標簽隱私保護，攻擊者無法根據在通信過程中劫取的H(ID)信息破譯出標簽中的ID信息[8]。但標簽的H(ID)信息保持不變，信息易被跟蹤定位，攻擊者可以很容易復制相同的標簽對閱讀器進行重放攻擊，造成后臺信息系統的運算量加大，造成信道擁堵[9]。

3.2 Hash-Chain協議

相對于Hash-Lock協議的缺陷，Hash-Chain協議是基于共享秘密的詢問-應答協議[10]，保證了前向通道的安全。Hash-Chain協議如圖2所示。

圖2 Hash-Chain協議

在Hash-Chain協議中，標簽利用2個Hash函數H和G，一方面對標簽的ID信息進行 G（St,j）加密，另一方面對密值St,j更新為H（St,j）。該協議延續了Hash-Lock協議中的單向通道安全性，同時通過對St,j的隨機更新，使得即使攻擊者截獲標簽信息，也不能夠進行位置跟蹤和重放攻擊[11]。但該協議同時運用2個Hash函數，當標簽數量較大時，會加大后臺信息系統的運算量和執行效率[12]。

3.3 SPA協議

文獻[13]提出依靠樹結構來減少安全協議中認證的復雜度。所有的標簽分布在一棵度為k的平衡樹的葉子節點上，樹的深度為logkN，樹的每條邊的值為一個隨機值ki,j，其中，i是目標在樹中的層數；j是分支數。支節點路徑可以唯一確定一個標簽，這組值是標簽的ID組值。k度樹結構如圖3所示。

圖3 k度樹結構

在該協議中，標簽將樹路徑上的所有序列值經過加密后發送，后臺信息系統接收到信息后，根據信息從根節點到支節點一層層進行驗證，以確定標簽在哪個分枝中。采用這種方法，在樹中的第i層，系統只需要在k個秘密值中查找是否有一個與標簽的秘密組中的第i個密碼值相同的密值，時間復雜度降低為O（lo g n），可以很大程度上提高后臺信息系統的運行速率。然而，又因為樹結構的分支特性，攻擊者可以容易地跟蹤其他與這個標簽共享部分密值的標簽[14]。

4 改進的高效RFID安全協議

在上文介紹的RFID安全協議中，利用Hash函數的特性，對原有明文數據的任何篡改或替換都會得到一個不同的結果，是采用基于共享密鑰的詢問-應答的方式來增加RFID系統的安全，雖然這些協議能保證安全需求，但是使得RFID系統時間復雜度太大，不適合在大規模的RFID系統中應用。基于樹的RFID安全協議通過構造一顆樹結構的密碼樹來提高在大規模RFID系統中后臺信息系統搜索的效率，但由于任何2個標簽間至少共享了一個密碼值，使得這類協議有明顯的安全漏洞，很容易因為一個標簽的信息泄漏而使其他標簽被跟蹤。

基于以上安全協議所面臨的問題，本文在散列Hash函數安全協議的基礎上，對其進行改進，融合二分搜索法和循環冗余校驗(Cyclic Redundancy Check,CRC)法，實現了RFID安全通信的同時，降低協議執行的時間復雜度，使得在安全性質、抗攻擊能力、低成本、執行速率等方面獲得更大的綜合優勢。

4.1 數學原理

假定n≥1個有序整數存儲在數組list中，list[0]≤list[1]≤list[2]≤…≤list[n–1]。查找searchnum是否出現在這個表中，若存在，則返回searchnum=list[i]，否則返回–1。

對于有序查找法，將searchnum與list[i]依次從前往后進行比較，直到找到使得searchnum=list[i]的i值為止。while語句每次循環耗時 O（1），利用這種方法，后臺數據庫的運算時間復雜度為O（n）。

利用二分搜索法，令left，right分別表示表中待查范圍的左右兩端點，標簽數為n，初值left=0，right=n–1。令middle=(left+right)/2，每次搜索時，將searchnum與list[middle]進行對比，每次對比，將數組長度減為原來的一半，再進行依次循環，直到找到使searchnum=list[middle]的middle值，并返回。利用二分搜索法，while語句每循環一次，待查的表長度會減少一半，這種情況下算法的時間復雜度降低為O（lo g n），會大大減少后臺信息系統的運算量，降低工作量，提高搜尋效率。

可以看出，二分搜索法可以有效降低系統的運算量，實現快速識別，同時，結合Hash函數的安全特性，可以防止標簽的跟蹤攻擊。

4.2 循環冗余校驗法

循環冗余校驗碼是一種從數據本身出發，依靠數學上約定的形式來對通信數據進行檢驗的一種校驗方法。CRC校驗碼可以檢測到接收的數據是否發生錯誤，當發生錯誤時，接收方會通知發送方重新發送一遍數據。

發送方發送m位信息數據T(x)，接收方接收到D(x)，若T(x)=D(x)，則傳輸過程中沒有出現錯誤。CRC碼通過在信息數據T(x)后附加一個k位的二進制校驗信息段R(x)來對信息數據進行校驗。R(x)、生成多項式g(x)以及信息數據T(x)有著特定的關系，如果數據在傳輸中的某一位或某些位發生錯誤，這種特定的關系就會被破壞，因此通過檢查這種特定關系就可以實現對數據正確性的檢驗。

在國際標準中，CRC-8校驗碼的生成多項式為g（x）=x8+ x5+ x4+1。通過將原信息碼T(x)左移k位，然后與生成多項式g(x)作異或運算處理，得到的余數就是校驗碼R(x)。在接受方，則將收到的信息數據D(x)用同樣的方法作逆運算，如果最終運算結果有余數存在，則說明數據T(x)在傳送通道中被篡改，否則即可證明信息傳送的正確性。

4.3 改進的RFID安全協議

后臺管理信息系統首先利用CRC-8校驗法對閱讀器發送回的信息進行校驗，如果存在攻擊者在無線通信路徑中對標簽信息進行了非法篡改，CRC-8可以首先檢驗出錯誤標簽，對錯誤標簽直接返回不予處理，從而后臺信息系統可以避免對錯誤標簽的搜索，防止篡改標簽的攻擊，大大減少工作量。

當CRC-8校驗證明標簽傳送正確時，后端信息系統再進行定位搜索工作。對于一般的基于Hash函數安全協議，直接從所有的標簽中搜索得到目標標簽，算法復雜度為O（n）。結合二分搜索法，比較searchnum與list[middle]，可以在很大程度上減少目標標簽的搜索次數，迅速地找到目標標簽，時間復雜度為O（lo g n），大大減少后臺信息系統的工作量。當標簽數量N很大時，二分搜索法的執行速度和效率更高。

融合CRC-8校驗法和二分搜索法，可以有效防止信息篡改攻擊，避免錯誤標簽對后臺信息系統資源的占用，降低系統搜索的時間復雜度。同時，相對于樹協議搜索法，可避免標簽信息之間的聯接，有效防止標簽位置跟蹤攻擊。改進的高效RFID加密安全協議的執行過程如圖4所示。

圖4 改進的高效RFID加密安全協議

認證過程：

(1)當數據庫需要搜索某個標簽時，由后臺信息系統DB產生一個隨機數R，發送隨機數R給閱讀器。

(2)閱讀器隨即將詢問信息Query和R發送給識別范圍內的標簽T。

(3)T將接收到的隨機數R和自身密值S1做異或運算后，再計算其Hash函數值：MetaID=H（S1⊕R）。

(4)T將MetaID傳送給閱讀器；閱讀器將MetaID發送給DB。

(5)DB利用CRC-8校驗法驗證MetaID，若最終逆運算結果有余數，則CRC校驗錯誤，說明T發送出的消息在無線通道中被攻擊者篡改，否則認證通過。

(6)若步驟(5)認證通過，再利用二分搜索法，在DB（H（Si⊕R）,IDi）中查找到使得 H（S1⊕R）=H（Si⊕R）的Si值。

(7)更新密值 Si'=H（Si）。

(8)計算 MetaID '=H（Si'⊕ R），DB將 MetaID'發送給閱讀器，閱讀器將 MetaID '發送回T。

(9)驗證 MetaID '=H（S1'⊕ R）是否成立，若成立，則認證成功，更新T密值 S1'=H（S1）。

5 安全分析和性能評估

本文提出的加密安全協議結合了Hash函數單向性加密和二分搜索法。Hash函數的單向安全性可以有效保證標簽信息的安全，實現標簽防竊聽攻擊、防信息泄漏和數據隱匿性等問題，結合密鑰更新，避免了標簽被復制重放攻擊和位置跟蹤的問題。同時，利用Hash函數可以有效地減少標簽的設計復雜度，保證標簽的低成本設計，在實際生產中的應用價值較大。利用CRC-8校驗法，防止信息在無線通道中被惡意篡改，有效避免了錯誤標簽對后臺信息處理的數據占用，減少系統驗證非法標簽的時間。最后，采用二分搜索法，對標簽二進制信息采用折半查找，大大提高了后臺信息系統搜索標簽的時間復雜度，提高了后臺數據庫的執行效率。本文協議使得RFID標簽識別在安全性、低成本、執行效率方面具有較好性能。

5.1 協議安全分析

本文提出的協議可以有效提高系統的工作效率，在大量標簽聚集環境下，實現高效的目標定位功能，同時，能夠保證通信過程中的安全性。

(1)降低成本。將隨機數產生器放在后臺信息系統，降低了標簽和閱讀器的設計復雜度。

(2)防非法讀取。只有經過認證的閱讀器才能夠獲取標簽的信息。本文協議利用散列Hash函數的單向安全性，即使攻擊者截獲到通道中傳送的信息，也不能夠反向獲得標簽的信息。

(3)數據完整性。本文協議利用散列Hash函數的強碰撞特性，對原有明文數據的任何篡改或替換都會得到一個不同的結果，可以有效保證消息的完整性。

(4)防重發。后臺信息系統每次訪問時產生一個隨機數R，使得每次認證過程中標簽的輸出 MetaID=H（S ⊕R）都不同。攻擊者即使竊聽到某一次的標簽輸出，也不能夠在下一次認證中推測或偽裝該標簽造成信息重發。

(5)防信息篡改。DB利用CRC-8校驗法驗證MetaID，可以保證信息在傳送路徑中的正確性。即使攻擊者在通信信道中對標簽信息進行干擾，后臺信息系統也可以很快地驗證出該消息已被篡改，從而可以有效減少系統驗證非法標簽的時間，在一定程度上提高驗證效率。

(6)后臺信息系統的時間復雜度降低，效率提高。在每次詢問過程中，信息系統中存儲的標簽個數為N，基于Hash函數的安全協議算法復雜度為O（n）。本文協議中采取二分搜索法，很大程度上減少目標標簽的搜索次數，迅速地找到目標標簽，算法復雜度為O（lo g n），減少后臺數據庫的工作量和資源消耗。當N很大時，本文協議的執行速度將更快和效率更高。

(7)雙向認證安全性。本文協議利用MetaID來實現標簽的認證，在DB搜索到目標標簽后，通過 MetaID=H（S1⊕R）計算比較，實現閱讀器對標簽的前向通道安全認證；在反向過程中，通過 MetaID '=H（S1'⊕ R）的計算比較，實現標簽對閱讀器的后向通道安全認證。

(8)防位置跟蹤。更新密值和隨機數，攻擊者即使截獲多個標簽密值，無法根據標簽的信息來找到相關規律，也無法標簽相關的歷史活動信息，防止攻擊者根據特定的輸出進行位置跟蹤。

5.2 協議運行性能評估

本文協議結合了Hash函數的單向安全性與二分搜索法的高效性，有效保證了RFID安全系統中的重傳攻擊、假冒復制攻擊、信息篡改攻擊、插入攻擊、拒絕服務攻擊、前向安全、標簽偽造、位置跟蹤等。

綜合對比Hash-Lock協議、Hash-Chain協議、SPA協議和本文協議，在安全性、復雜度、通話量等各方面的性能如表1所示，N表示協議對這種信息攻擊沒有抗攻擊能力，Y表示協議對這種信息攻擊有抗攻擊能力。

表1 各安全協議的安全性和時間復雜度對比

比較Hash-Lock協議和Hash-Chain協議中的直接搜索法、SPA協議的樹形搜索法和本文協議中的二分搜索法，三者在時間復雜度上有明顯區別。

采用直接搜索法，數據庫中有N個標簽，對于目標標簽searchnum，最少需要1次搜索，最多需要N次搜索，所以，直接搜索法最差情形的整體復雜度為O（n）。采用樹形搜索法，度為δ、樹的深度為logδN，每個標簽內部存儲一組從根節點到葉子節點的路徑密碼組 ［S1,S2,…,SL］，在樹的第i層，只需進行δ/2次搜索比較，即認證一個標簽需要δ·L/2次搜索。可以看到，后臺信息系統搜索每個標簽的過程就是在樹的支節點中通過分支來進行查找，使得時間復雜度降低到 O（lo g n）。本文采用二分搜索法，比較searchnum與中間值list[middle]的大小，每次查找后，待查找的表長會減少一半，最佳情況的復雜度為O（1），最差情況的循環比較次數為O（lo g n）。利用Matlab仿真，比較各算法的時間復雜度，如圖5所示。

圖5 不同搜索算法的時間復雜度對比

通過圖5可以看出，Hash協議中直接搜索算法的時間復雜度 O（n）要遠大于本文協議中二分搜索算法的時間復雜度 O（log n）。當標簽數量N增大時，復雜度對比更明顯，二分搜索算法會大大地減少后臺信息系統的運算量，提高系統的執行效率。

6 結束語

在實現大型場地中的目標定位時，由于閱讀器閱讀范圍內的目標標簽數目過多，極易出現目標混雜和攻擊者入侵的現象。在某些重要場合中，要能夠準確迅速地定位到目標標簽，就需要在保證信息系統執行效率的前提下，使得標簽能夠抵抗重放、假冒復制、位置跟蹤等攻擊。

由于現在常見的安全協議均不能在位置跟蹤、重放攻擊、信息篡改、算法復雜度等方面同時做到最優，對比這些常見的典型RFID安全協議的特性，本文提出了改進的RFID安全加密協議，結合不同安全加密協議的優勢，在保證信息通道安全的情況下，可以有效地保證標簽信息的動態安全性，減少信息系統識別錯誤標簽的時間，同時降低系統搜索標簽算法的時間復雜度。最后通過對協議的安全性分析以及Matlab時間復雜度的仿真，結果證明本文協議具有安全性、低成本、復雜度等方面的綜合優勢，解決了Hash函數安全協議的時間復雜度問題，同時解決了樹結構安全協議的安全隱匿問題，是一種較實用的安全協議，在低成本密集型標簽環境中具有較高的實用價值。

[1]Jeremy L.The History of RFID[J].IEEE Potentials,2005,24(4):8-11.

[2]胡國勝,龍 雄.RFID系統安全分析[J].網絡安全技術與應用,2013,(2):40-44.

[3]李 磊,陳 靜.物聯網感知層中RFID系統安全解決方案[J].網絡安全技術與應用,2011,(6):34-36.

[4]李宏年.基于Hash協議的射頻識別系統安全對策[J].信息通信技術,2009,(6):16-19.

[5]Sun D Z,Zhong J D.A Hash-based RFID Security Protocol forStrong Privacy Protection[J].IEEE Transactions on Consumer Electronics,2012,58(4):1246-1252.

[6]Liu Leian,Chen Zhiqiang,Yang Ling.Research on the Security Issues of RFID-based Supply Chain[C]//Proceedings of International Conference on E-Business and E-Government.Guangzhou,China:[s.n.],2010:3267-3270.

[7]Rieback M R,Crispo B,Tanenbaum A S.The Evolution of RFID Security[J].IEEE Pervasive Computing,2006,5(1):62-69.

[8]陳瑞鑫,鄒傳云,黃景武.一種基于雙向Hash認證的RFID安全協議[J].微計算機信息,2010,(11):149-151.

[9]Kim Dong-Seong,Shin Taek-Hyun,Park Jong-Sou.A Security Framework in RFID Multi-domain System[C]//Proceedings of the 2nd International Conference on Availability,Reliability and Security.Vienna,Austria:IEEE Press,2007:1227-1234.

[10]Pateriya R K.The Evolution of RFID Security and Privacy:A Research Survey[C]//Proceedings of 2011 International Conference on Communication Systems and Network Technologies.[S.l.]:IEEE Press,2011:115-119.

[11]Yang Yuanyuan,Lu Zhen.Security Analysis of a Mutual Authentication Protocol for RFID Systems[C]//Proceedings of IMCCC’12.[S.l.]:IEEE Press,2012:252-255.

[12]Yan Fang,Liu Bingwu,Huo Lingyu.Research and Design of a Security Framework for RFID System[C]//Proceedings of 2010 International Forum on Information Technology and Applications.[S.l.]:IEEE Press,2010:443-445.

[13]Tzipora H,Nitesh S,Shai H.Tree-based HB Protocols for Privacy-preserving Authentication of RFID Tags[J].Journal of Computer Security,2011,19(2):343-363.

[14]Bashir A K,Chauhdary S H.Mobile RFID and Its Design Security Issues[J].IEEE Potentials,2011,30(4):34-38.