無后臺服務器的射頻識別標簽安全查詢協議

周景賢 李 昊 周亞建 李國友 張 淼

①(北京郵電大學信息安全中心 北京 100876)

②(災備技術國家工程實驗室 北京 100876)

③(電子信息控制重點實驗室 成都 610036)

1 引言

RFID應答器(transponders)、讀取器、軟體與服務市場在2011年增長了9億美元，根據研究機構ABI Research預測，該市場未來5年可取得年平均20%的增長率，到2017年可實現營收額705億美元，那時RFID裝置將無處不在。但是，由于存儲和計算能力受限等先天缺陷，使得用戶在享受RFID帶來便捷的同時，也面臨種種安全和隱私問題。例如，2007年2月在RSA安全大會上，一家名為IOActive的公司展示了一款RFID克隆器，它可以復制信用卡去竊取密碼。目前，學術界和工業界對RFID系統及其應用的安全問題已經進行了深入的研究，并取得了許多令人鼓舞的成果。不可否認，仍然有不少需要改進的地方。本文集中于對RFID標簽查詢安全協議的研究。

安全查詢協議是一個RFID密碼協議，按照協議交互，驗證者(讀寫器)可以準確地判斷某一特定標簽是否存在于多個標簽中，并且協議的攻擊者得不到任何有用信息。例如，在RFID標簽化圖書的圖書館環境中，可以使用此類協議去查詢一本可能丟失的圖書是否還在。

2008年，Tan等人[1]首次討論了RFID查詢機制，并給出了一系列標簽查詢協議。他們協議都采用挑戰-響應機制，讀寫器首先廣播一個請求消息，根據這個請求，如果目標標簽存在，它將回復被加密的身份信息，區域內的其他標簽以一定概率回復一個隨機值。隨后，一些研究成果相繼被提出[2-10]。Kulseng等人[2]基于線性反饋移位寄存器(LFSR)和物理不可克隆函數(PUF)，提出了幾個輕量級安全查詢協議，適用于低成本標簽。Chao等人[3]對這幾個協議分析后發現，它們均不能抵抗標簽追蹤攻擊。Kim等人[4]提出了一個基于標簽群身份的查詢協議。他們將標簽劃分為多個群，每個標簽只屬于一個群，每個群有一個統一的群身份。在閱讀器發布請求信息后，除了目標標簽回復外，目標標簽所在的群中每個標簽都需要回復。然后由讀寫器驗證所有的回復，以確定目標標簽是否存在。類似于文獻[1]使用的概率性回復一樣，它的缺點是：為了查詢一個標簽，讀寫器需要進行大量的計算。文獻[5]基于Hash函數給出了一個輕量級標簽查詢協議，作者們聲稱該協議計算代價小、且安全性高。然而，Lee等人[6]分析指出，文獻[1,5]提出的查詢協議不能抵抗標簽假冒攻擊。在文獻[6]中一個改進協議也被提出，但它沿用概率性回復策略去抵抗追蹤攻擊，這限制了該協議的擴展性。文獻[7,8]的作者們分別提出了基于密鑰更新的安全增強查詢協議，但讀寫器和目標標簽密鑰更新不同步問題卻沒有得到有效解決。直接導致的后果就是：一次查詢失敗，之后所有的查詢均不成功。文獻[9]基于比特記錄提出了一個前向安全的標簽查詢協議，然而協議的安全分析顯示，它不能抵抗標簽追蹤攻擊。文獻[10]的突出貢獻是：首先研究了標簽查詢協議的匿名安全性，但該文提出協議的安全完全依賴于第三方的誠實度，讀寫器變成僅僅轉發信息的中繼器，該協議的使用范圍受到限制。

本文利用時間戳和Hash函數，提出一個新的標簽查詢協議，它不需要后臺服務器的參與，適用于移動RFID環境。主要貢獻包括：(1)形式化安全證明。用GNY邏輯證明新協議的正確性；(2)效率高。查詢協議計算復雜度為：O(1);(3)適用于低成本標簽。協議僅采用Hash函數來保證數據傳輸的安全。

2 RFID系統模型

傳統的RFID系統由3個主體構成：標簽(Tag)、讀寫器(Reader)和后臺服務器。后臺服務器往往是一個固定站，存儲所有標簽的信息，具有強大的計算能力，讀寫器通過有線的方式和服務器相連。該系統廣泛地應用于超市購物、物流倉儲管理等環境中。然而在現實中，后臺服務器在給RFID系統帶來便捷的同時也引入了一些新的問題，如：它與讀寫器之間的安全、可靠、持續的連接如何保證，易引起災難性后果的服務器失效如何防止等。

本文研究的標簽查詢協議應用于無后臺服務器的移動RFID系統，它是由閱讀器R和一個標簽集合組成。閱讀器R是一個手持式移動裝置，如：掌上電腦(PDA)等，它利用無線射頻信號與標簽進行通信，具有較強的計算和存儲能力，可以獨立對標簽進行認證和查詢。標簽一般分為兩類：有源(主動)標簽和無源(被動)標簽。我們主要考慮最為常用的被動標簽，每個標簽每次和一個閱讀器進行通信。該系統適用于無法將服務器與讀寫器連接的遠距離操作環境中；或標簽分布范圍較廣，需要讀寫器頻繁移動的環境中。

與傳統RFID系統一樣，在無后臺服務器的RFID系統中，閱讀器與標簽之間是無線通信，容易遭受許多惡意攻擊。我們假設攻擊者可以截獲標簽和閱讀器之間所有的通信信息，并且攻擊者還可以對這些消息內容進行修改。特別地，在標簽查詢過程中，針對標簽安全和隱私的攻擊主要包括：竊聽、冒充、重放、標簽追蹤和拒絕服務等。在第5節將對查詢協議的安全性進行分析，這里不再贅述。

3 RFID標簽查詢協議

在本節，我們提出一個使用在無后臺服務器的RFID系統中的標簽查詢協議。協議參與主體有：讀寫器Ri和一個標簽集合，其中假設Tj為目標查詢標簽。查詢協議包括兩個階段：參數初始化階段和標簽查詢階段。圖1給出了具體查詢協議交互流程。

3.1 符號說明

文中需要用到的一些符號被列出在表1中。

表1 符號描述

3.2 初始化階段

在初始化階段，標簽Ti被寫入一個l長的唯一身份idi和一個與S共享的密鑰ki。讀寫器Ri有一個唯一的身份ri和包含標簽秘密信息的訪問列表Li。ri和Li是Ri向S成功認證自己后，從S處獲取。其中，訪問列表Li≡{(id1,h(ri,k1)),(id2,h(ri,k2)),…,(idn,h(ri,kn))}。

圖1 本文提出的協議交互流程

3.3 標簽查詢階段

假設Ri想查詢標簽Tj是否存在，Ri執行下列步驟去查詢該標簽：

(1)Ri首先生成一個新的時間戳 timenew，并且計算值r；

(2)Ri廣播r,ri, timenew給可達范圍內的所有標簽；

(3)收到查詢請求之后，所有標簽T*首先驗證timenew是否大于 timeold。如果大于，它們利用自己的密鑰kj計算f(h(ri,kj),timenew)的值，然后檢查f(h(ri,kj),timenew)⊕r是否等于它的身份值idj。如果相等，那么它就是本次要尋找的標簽。然后Tj計算值t，并且替換 timeold為 timenew；

(4)Tj回復消息t給Ri；

(5)Ri利用 timenew驗證消息t的有效性。

4 協議的GNY邏輯分析

形式化方法的價值在于：能夠發現安全協議中以前不為所知的漏洞。GNY邏輯是一種形式化分析工具，在1990年由Gong等人[11]提出。GNY邏輯是由BAN邏輯發展而來的，與BAN邏輯相比，它具有更強的表現能力和適應性。目前，它被認為是影響最大的一種BAN類邏輯之一。

為了驗證協議的安全性，我們利用 GNY邏輯對協議的目標，假設和消息傳遞進行形式化分析，證明從協議的假設出發，經過協議的運行可以達到預先設定的目標。證明過程中使用的邏輯規則都來自于文獻[11]。為了簡化證明過程，我們直接給出邏輯規則代碼。希望進一步研究的讀者，可以參見文獻[11]。

4.1 協議的假設、目標及其形式化

(1)關于標簽Tj的假設：Tj擁有身份信息idj，兩個單向 Hash 函數h(·),f(·)；擁有秘密信息kj；協議雙方驗證的依據是擁有共同秘密值h(ri,kj)，所以Tj相信它與Ri共享h(ri,kj);Tj相信 timenew是新鮮的，否則協議不能成功運行。

(2)關于讀寫器Ri的假設：Ri擁有身份信息ri，單向函數f(·);Ri擁有關于Tj的秘密消息h(ri,kj)，并且在協議運行中發送自己的身份ri給Tj，所以Ri相信它和Tj共享信息h(ri,kj);Ri相信 timenew是新鮮的。

(3)協議的目標：作為一種自動查詢技術，經過安全協議的運行，目標標簽Tj能夠相信挑戰信息是來自于合法的讀寫器Ri，并且以前未被使用，也就是新鮮的；同樣協議運行后，讀寫器Ri也能夠確認收到的回復信息來自于目標標簽Tj，并且是新鮮的。

協議目標可以形式化為

4.2 形式化分析

在明確了協議的假設、目標后，我們可以利用GNY邏輯中的相關推理規則，證明協議能夠從假設出發，經協議運行后達到預先設定的目標。

圖1中的(2)可GNY邏輯形式化為

圖1中的(4)可GNY邏輯形式化為

可見，通過協議的運行，該協議可以在前提假設的基礎上實現預定的設計目標。

5 協議的安全性及效率分析

與許多形式化邏輯一樣，GNY邏輯也有其不足之處。比如：無詳細的時間概念，無否定形式等。所以，某些潛在攻擊僅僅依靠 GNY邏輯無法被發現(比如：竊聽攻擊，追蹤攻擊等)。本節將從安全性能和實施效率兩方面來對提出的標簽查詢協議進行分析。

5.1 協議安全性分析

本文主要從：標簽追蹤、竊聽、拒絕服務、冒充欺騙和重放攻擊5個方面來分析新協議的安全。

(1)竊聽攻擊：攻擊者A可以通過竊聽Ri和Tj之間的不安全信道，收集到消息：r,ri, timenew,t。顯然對于攻擊者A來說這些值沒有任何意義。t im enew是隨機值；ri是代表讀寫器的身份，攻擊者可以通過它來知道是哪個讀寫器，但對于追蹤目標標簽沒有任何幫助。f(·)是單向函數，所以A通過r也不能獲得比隨機數更多的信息。

注：ri的明文傳輸，確實泄漏了讀寫器Ri的身份，但本文討論的追蹤攻擊對象是查詢目標標簽。同時要想實現身份信息的秘密傳輸，只有加密算法可以做到。為保證所提協議的輕量級，我們并不考慮加密算法的使用。

(2)冒充攻擊：由于h(ri,kj)和kj的機密性，同時根據第 4節的形式化證明可以知道，如果r,ri, timenew和t能通過驗證，就可以說明對方是合法的。也就是說，在提出的協議中，公開傳輸值有任何改動導致不匹配，就會引起協議失敗，冒充攻擊是不可能成功的。

(3)重放攻擊：本文提出的協議中，采用時間戳timenew來抵抗重放攻擊。重放以前的消息必然導致時間戳驗證不能通過，引起協議的失敗。所以，重放攻擊對本協議不構成威脅。

注：由于標簽的低成本和計算能力的限制，放置同步時鐘是不可能的。所以我們采用在標簽內存儲時間戳的方式，比較條件為 timenew＞timeold，認證成功則實施 timenew→timeold操作；否則不變。

(4)拒絕服務攻擊：拒絕服務攻擊一般是指攻擊者試圖實施中間人攻擊，為了引起Ri和Tj之間秘密值不同步，導致以后協議交互的失敗。但是，在我們提出的協議中，Ri和Tj在每次會話中，不需要進行密鑰更新。因此，本文協議能安全抵抗拒絕服務攻擊。

(5)標簽追蹤攻擊：追蹤就是攻擊者能將Tj與其它標簽區分開來。攻擊者有兩種方式來實現對目標標簽Tj的追蹤。(a)竊聽Ri和Tj之間的所有通信；(b)利用竊聽到的信息，對Tj實施重放攻擊。對于第 1種攻擊，我們的協議是安全的，因為攻擊者不可能每次都能預測到時間戳 timenew和Tj的回復值t。因此，攻擊者不能將Tj與其它標簽進行區分；在另一種攻擊中，攻擊者可能竊聽到了Ri和Tj之間一次通信的查詢挑戰和響應，然后攻擊者重復廣播查詢挑戰。由于時間戳的使用，使得Tj不會對攻擊者的挑戰做出回應。

從以上討論的關于安全的5個方面，我們將提出的協議與文獻[1]，文獻[7]，文獻[6]的協議進行比較(表2)。通過比較可以發現，我們的協議具有最好的安全性質，是唯一滿足了所有安全需求的協議。

表2 協議安全性比較

5.2 協議效率分析

標簽查詢系統中有兩類實體：標簽和讀寫器，所以在效率方面我們主要考慮：查詢協議的交互輪數、單個標簽的計算量和讀寫器的計算量3部分。文獻[1]和文獻[6]使用概率性回復來抵抗標簽追蹤攻擊，使得讀寫器的計算量與標簽數成正比，查詢效率較低。文獻[7]采用加密算法和密鑰更新的方法，來實現協議的安全。對標簽的計算能力和硬件都提出了很高的要求。我們提出的協議采用簡單的2輪交互認證，對于每次查詢讀寫器只需要 2次 Hash運算。

表3總結了我們提出協議的效率，其中，CH為一次Hash運算的計算花費；CE為一次加密運算的計算花費；N為標簽總個數；λ為標簽回復概率值。通過比較可以發現，在4個標簽查詢協議中，我們的協議是計算代價要求最低的。

表3 協議效率比較

6 結束語

本文首先對標簽查詢問題的研究現狀進行了分析，然后提出了一個無后臺服務器的RFID標簽查詢協議。GNY邏輯分析表明，從該協議的假設出發經協議運行可以達到預先設定的協議目標。分析顯示，本文提出的協議在滿足各種安全需求的同時，具有很高的運行效率。同時，由于標簽僅需要一個Hash函數電路來實現隱私保護，成本較低，更適用于資源緊張的無源標簽。協議應用場合可以是在圖書館進行圖書查詢，也可以是在奢侈品零售店進行商品查詢。

然而，目前所提出的標簽查詢協議，基本上都是以標簽的身份作為查詢依據，使得這些協議只能用于一對一的環境中。如果一個讀寫器想一次查詢滿足某一條件的所有標簽是否存在，那么目前的協議無法直接使用。所以，下一步研究內容是一對多的標簽查詢協議機制和基于某些特征的標簽查詢機制。

[1]Tan C C, Sheng B, and Li Q. Secure and serverless RFID authentication and search protocols[J].IEEE Transactions on WirelessCommunications, 2008, 7(4): 1400-1407.

[2]Kulseng L, Yu Z, Wei Y,et al.. Lightweight secure search protocols for low-cost RFID systems[C]. Proceedings of the 29th IEEE International Conference on Distributed Computing Systems, IEEE Computer Society, Washington,DC, USA, 2009: 40-48.

[3]Chao L, Li H, Ma J F,et al.. Vulnerability analysis of lightweight secure search protocols for low-cost RFID systems[J].International Journal of Radio Frequency Identification Technology and Applications, 2012, 1(4): 3-12.

[4]Kim Z, Kim J, Kim K,et al.. Untraceable and serverless RFID authentication and search protocols[C].2011 Ninth IEEE International Symposium on Busan, Parallel and Distributed Processing with Applications Workshops(ISPAW), Montreal, Canada, 2011: 278-283.

[5]Lin I C, Tsaur S C, and Chang K P. Lightweight and serverless RFID authentication and search protocol [C].Proceedings of the 2009 Second International Conference on Computer and Electrical Engineering, IEEE, New York, 2009,2: 95-99.

[6]Lee C F, Chien H Y, and Laih C S. Server-less RFID authentication and searching protocol with enhanced security[J].International Journal of Communication System, 2012,25(3): 376-385.

[7]Zuo Y J. Secure and private search protocols for RFID systems[J].Information System Front, 2010, 12(5): 507-519.

[8]曹崢, 鄧淼磊. 通用可組合的RFID搜索協議[J]. 華中科技大學學報(自然科學版), 2011, 39(4): 56-59.

Cao Z and Deng M L. Universally composable search protocol for RFID[J].Journal of Huazhong University of Science and Technology(Natural Science Edition), 2011, 39(4): 56-59.

[9]Hoque M E, Rahman F, and Ahamed S L. S-search: finding RFID tags using scalable and secure search protocol[C].Proceedings of the 2010 ACM Symposium on Applied Computing(SAC), Sierre, Switzerland, 2010: 439-443.

[10]Yoon H S and Youm H Y. An anonymous search protocol for RFID systems[J].Journal of Convergence Information Technology, 2011, 8(6): 44-50.

[11]Gong L, Needham R, and Yahalom R. Reasoning about belief in cryptographic protocols[C]. Proceedings of the 1990 IEEE Symposium on Research in Security and Privacy, Oakland,California, 1990: 234-248.