一種改進的高效RFID加密安全協(xié)議

劉 念1，殷 業(yè)1，葉 龍2，肖 龍1，嚴 實1

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

1 概述

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

2 RFID中的安全問題

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

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

3 常見的安全協(xié)議

3.1 Hash-Lock協(xié)議

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

圖1 Hash-Lock協(xié)議

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

3.2 Hash-Chain協(xié)議

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

圖2 Hash-Chain協(xié)議

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

3.3 SPA協(xié)議

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

圖3 k度樹結(jié)構(gòu)

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

4 改進的高效RFID安全協(xié)議

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

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

4.1 數(shù)學(xué)原理

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

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

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

可以看出，二分搜索法可以有效降低系統(tǒng)的運算量，實現(xiàn)快速識別，同時，結(jié)合Hash函數(shù)的安全特性，可以防止標簽的跟蹤攻擊。

4.2 循環(huán)冗余校驗法

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

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

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

4.3 改進的RFID安全協(xié)議

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

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

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

圖4 改進的高效RFID加密安全協(xié)議

認證過程：

(1)當數(shù)據(jù)庫需要搜索某個標簽時，由后臺信息系統(tǒng)DB產(chǎn)生一個隨機數(shù)R，發(fā)送隨機數(shù)R給閱讀器。

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

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

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

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

(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'發(fā)送給閱讀器，閱讀器將 MetaID '發(fā)送回T。

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

5 安全分析和性能評估

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

5.1 協(xié)議安全分析

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

(1)降低成本。將隨機數(shù)產(chǎn)生器放在后臺信息系統(tǒng)，降低了標簽和閱讀器的設(shè)計復(fù)雜度。

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

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

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

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

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

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

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

5.2 協(xié)議運行性能評估

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

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

表1 各安全協(xié)議的安全性和時間復(fù)雜度對比

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

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

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

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

6 結(jié)束語

在實現(xiàn)大型場地中的目標定位時，由于閱讀器閱讀范圍內(nèi)的目標標簽數(shù)目過多，極易出現(xiàn)目標混雜和攻擊者入侵的現(xiàn)象。在某些重要場合中，要能夠準確迅速地定位到目標標簽，就需要在保證信息系統(tǒng)執(zhí)行效率的前提下，使得標簽?zāi)軌虻挚怪胤拧⒓倜皬?fù)制、位置跟蹤等攻擊。

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

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

[2]胡國勝,龍 雄.RFID系統(tǒng)安全分析[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2013,(2):40-44.

[3]李 磊,陳 靜.物聯(lián)網(wǎng)感知層中RFID系統(tǒng)安全解決方案[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2011,(6):34-36.

[4]李宏年.基于Hash協(xié)議的射頻識別系統(tǒng)安全對策[J].信息通信技術(shù),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安全協(xié)議[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.