低成本RFID搜索協議的設計與安全性證明

周清雷，周 靜

(鄭州大學信息工程學院，河南鄭州450001)

0 引言

RFID技術在日常生活中最常見的應用是讀寫器和標簽間的交互，RFID安全協議是實現這種交互的重要保證。其中RFID搜索協議是RFID認證協議［1-6］的延伸，在大批量貨物中快速搜索目標貨物、高效管理大型圖書館等多個應用領域中具有重要的意義，但目前對其單獨的研究還比較少。Tan［7］較早的提出了搜索協議，但由于在整個協議中使用的是hash函數，導致標簽成本較高;Kulseng［8］針對此問題在提出的新協議中用LFSR(linear feedback shift register)和PUF(physically unclonable function)構造的隨機序列函數代替了hash函數，但引進函數種類較多;Ahamed［9］、曹錚［10］、趙斌［11］等分別在協議中引用了偽隨機函數，但部分計算過程仍使用了hash函數，不能從根本上降低標簽成本而且在提出的協議中采用信息更新機制來防止攻擊者重放，但卻會導致協議遭受新的重放攻擊。本文針對以上提出的問題，設計了一個簡單的所需標簽成本較低和安全性較高的RFID搜索協議，且利用UC模型對其安全性進行了形式化證明，并將其與前人工作在相關特性和安全性方面進行了對比，顯示了新協議的優勢。

1 協議設計

本文所設計的新協議是無需后端數據庫的，在其運行的整個過程中使用共享的偽隨機函數，利用了該函數所具有的偽隨機性，強單向性等性質，但同時又考慮了其相對于hash函數較弱的抗碰撞性問題，從降低標簽成本和提高安全性角度進行了設計。

協議設計的前提:已知注冊機構CA是可信任的，任何一個讀寫器在CA處注冊成功后才是合法的，而且所有的標簽必須由CA分發。讀寫器一旦注冊成功，CA會對其授權一批標簽，即該讀寫器能夠識別該批標簽中的任何一個，而每個標簽只能被這一個讀寫器識別。以讀寫器Ri和標簽Tj為例，若Ri有權訪問Tj，其中Ri中存儲了一個參數列表Li(ki1:id1，ki2:id2，…kij:idj，…)，Tj存儲的參數為 idj和 kij。必要參數說明如下:

idj:Tj的身份標識符，是唯一可區分的。

kij:Ri和Tj間的共享秘密，初始值由CA進行分配，是唯一可區分的。

t:Ri產生的隨機數。

f():偽隨機函數。

||:連接運算符。

⊕:異或運算符。

*:對標簽泛指的下標標記。

Tdesired:目標標簽。

Tnotdesired:非目標標簽。

kidesired:Ri和Tdesired間的共享秘密。

p:非目標標簽產生響應的概率。

1.1 搜索協議1

根據設計的基本思想，協議1如下:

Ri→T*:f(t||kidesired)，t

T*:用自身的秘密信息與t進行連接，經過偽隨機函數運算，驗證所得結果與收到的函數值是否相等，若相等，則

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired為f(kidesired)

否則

Ri←Tnotdesired:以概率p向Ri發送一個隨機數

Ri:對收到的響應進行一一驗證，若是確認搜索到了目標標簽，則將kidesired更新為f(kidesired)。

在協議1中，Ri將f(t||kidesired)和t一同廣播出去，收到該消息的標簽做相應的驗證后，若認為搜索的是其自身，則發送f(t⊕k*)給讀寫器，同時用f(k*)來更新k*;否則，以事先設定好的概率p發送同樣位數的隨機值給Ri，Ri若收到了目標響應，則進行相應的秘密值更新。

協議1的優勢有兩個:用偽隨機函數代替了以前多數搜索協議中采用的hash函數，降低了標簽成本;考慮了偽隨機函數的碰撞性問題，通過在廣播消息的偽隨機函數中采用連接運算，而在目標響應消息的偽隨機函數中采用異或運算，減小了碰撞發生的可能性，提高了搜索的準確度。

但協議1存在的不足是:Tdesired和Ri成功認證后將更新kidesired，由于各個k*不同才能保證協議的正確運行，但更新后的kidesired是否能夠保持與沒有更新的標簽的秘密信息不同，該協議無法保證。如果相同，再次尋找該標簽時，可能導致其它標簽產生Ri期待的目標響應，造成誤判。

1.2 搜索協議2

針對協議1中的不足，協議2如下:

Ri→ T*:f(t||kidesired)，t⊕ iddesired

T*:用自身的秘密信息與t進行連接，經過偽隨機函數運算，驗證所得結果與收到的函數值是否相等，若相等，則

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired為f(kidesired)

否則

Ri←Tnotdesired:以概率p向Ri發送一個隨機數

Ri:對收到的響應進行一一驗證，若是確認搜索到了目標標簽，則將kidesired更新為f(kidesired)。

協議2沒有直接廣播t，而是將(t⊕iddesired)進行廣播。即使兩個不同標簽的秘密值相同，但標簽的身份標識是唯一的，用身份標識與收到的(t⊕iddesired)進行異或運算，不同的標簽就會得到不同的t值，只有目標標簽才能得到原本的t值，從而有效地避免了協議2中提到的問題。

然而以上兩個協議仍存在著一個共同的問題:即標簽和讀寫器的共享秘密信息更新可能不同步。原因有兩個:①偽隨機函數相對于hash函數較弱的抗碰撞性，導致非目標標簽可能會誤認為讀寫器搜索的是其自身，之后將秘密信息進行了更新，而讀寫器卻不會進行相應的更新。那么當讀寫器真正搜索該標簽時，即使它存在，也無法搜索到。②通過更新kidesired來避免以追蹤為目的的重放攻擊，但其有效性卻是以該標簽存在為前提的。這有可能導致另外一種目的的重放:若Ri在搜索Tdesired時，Tdesired由于某種原因沒有收到廣播消息，那么Ri和Tdesired中的kidesired都不會更新。此時攻擊者雖然對Ri搜索的目標以及搜索結果都一無所知，但它能在竊聽到Ri廣播出的消息后，將此消息有選擇的在一定范圍內重放，若Tdesired在該范圍內且收到的是重放消息，那么該標簽就會認為是Ri在搜索自己，于是會更新kidesired，而Ri中的kidesired并沒有被更新，這樣也會導致Ri以后無法搜索到該標簽。

1.3 搜索協議3

針對2.2節最后提到的問題，本節對Ri的參數列表進行如下修改:在列表中增加一個搜索標識位，以標簽Tj為例，該標識位為sij，初始化時，sij=1。下面給出以下定義:①當sij=1時，表明Ri沒有搜索到Tj;②當sij=2時，表明Ri搜索到了Tj。協議3如下:

Ri→ T*:f(t||kidesired)，t⊕ iddesired

T*:用自身的秘密信息與t進行連接，經過偽隨機函數運算，驗證所得結果與收到的函數值是否相等，若相等，則

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired為f(kidesired)

否則

Ri←Tnotdesired:以概率p向Ri發送一個隨機數

Ri:對收到的響應進行一一驗證。⑴若搜索到了Tdesired，則將kidesired更新為f(kidesired)且將sij置為2;⑵若沒有搜索到Tdesired時，檢查sidesired的值:①若sidesired=1，那么Ri就用f(kidesired)代替消息中的kidesired，再次進行廣播，若能收到Tdesired的響應，則將kidesired的值更新為f(f(kidesired))且將sidesired的值置為2，否則sidesired和Tdesired的值不變;②若sidesired=2，則將sidesired的值置為1。

協議3增加了搜索標識位處理機制，當Ri此次沒有收到Tdesired的響應時，則要檢查sidesired:若sidesired=2，則說明上次搜索該標簽時搜索到了，可以肯定該標簽此次不存在，將sidesired置為1;若sidesired=1，則有3種可能:①該標簽確實不存在;②該標簽存在，Ri以前從未搜索過它，但該標簽曾經誤認為被Ri搜索過，標簽的kidesired已經被更新;③該標簽存在，但已經受到了重放攻擊，它的kidesired已經被更新。所以當檢查出sidesired=1時，Ri將用f(kidesired)代替原消息中的kidesired發起新一輪的搜索，從而來防止標簽假丟失情況的發生。

2 基于UC模型對最終協議的安全性證明

通過安全性分析，協議3滿足機密性、匿名性、不可追蹤性、防竊聽、防重放和并發安全。本章將對此給出UC模型下的形式化證明。首先簡要介紹UC模型如下:

2001年Canneti提出了UC(UniversallyComposable)模型，并定義了框架。該框架采用模塊化的思想，通過外界環境不能區分真實協議和理想協議的方法來證明協議是安全的。其中包括以下幾個要素:環境機Z，真實協議參與者P1，P2…Pn以及攻擊者A，理想協議虛擬參與者p'1，p'2…p'n，理想函數F以及理想攻擊者S。其中Z用來模擬協議運行的整個外部環境。在該模型下，若對于任何攻擊者A和環境機Z，至少有一個理想攻擊者S，使Z不能夠區分出自身是在與理想協議交互，還是在與真實協議交互，那么就說真實協議πUC實現了理想函數F，即π是安全的。其中理想函數的設計是該證明方法的關鍵。

2.1 理想函數Fsearch的設計與安全性證明

本節設計的理想函數Fsearch為每一次會話分配一個會話號，且只和具有相同會話號的實體進行通信，假設讀寫器是不可攻破的，攻擊者只能攻陷合法標簽。Fsearch的具體內容如下:

(1)收到R'i發來的消息broadcast()，則獨立隨機選擇一會話號ssid，記錄broadcast(ssid，R'i)，向攻擊者S發送消息broadcast(ssid，Anonymous(R'i))。

(2)收到某標簽發來的消息response()，則對每一個標簽，獨立隨機選擇一會話號ssid'，調用目標驗證函數g(ssid'，R'i，T'*)，驗證是否等于ssid:①若相等，假設該標簽為T'j:則將T'j的目標標識位設為1，表明它為目標標簽，記 錄 response(ssid'，T'j)， 向 攻 擊 者 S 發 送response(ssid'，Anonymous(T'j));②否則，以概率 p向攻擊者S發送response(ssid'，Anonymous(T'j))。

(3)收到攻擊者S發來的消息authenticate(ssid'，ssid，Anonymous(R'i)，Anonymous(T'j))，則查看有沒有記錄broadcast(ssid，R'i)和response(ssid'，T'j):①若有，則刪除這兩條記錄，記錄 link(ssid'，ssid，R'i，T'j)且向 T'j發送消息authenticate(R'i);②否則，忽略該消息。

(4)當收到攻擊者 S發來的消息 search(ssid，ssid'，Anonymous(T'j)，Anonymous(R'i))，則查看T'j的攻陷標志位是否為1:①若為1，表明T'j已經被攻陷，則刪除當前會話中關于T'j的所有信息，然后向R'i發送search(T'j);②否則，檢查有沒有記錄 link(ssid'，ssid，R'i，T'j):若有，則將其刪除，并向 R'i發送 search(T'j);否則，忽略這條消息。

(5)當Fsearch收到攻擊者S發來的消息corrupt(ssid')，則將T'j的攻陷標識位置為1。

(6)當 Fsearch收到攻擊者 S發來的消息impersonate(ssid＇)，則 檢 查 記 錄 broadcast(ssid，R'i) 或link(ssid'，ssid，R'i，T'j)是否存在:①若存在，則向 R'i發送search(T'j);②否則，忽略該消息。

下面證明Fsearch滿足本章開頭所提到的安全特性:

機密性:每次的會話號都是獨立隨機選擇的，只有理想函數能判斷出標簽是否為目標標簽，因此攻擊者不能得到協議參與方的任何秘密信息。

匿名性:每次在傳送給 S的消息中用Anonymous(R'i)，Anonymous(T'j)，因此攻擊者只知道協議參與方的類型，不知道參與方的真實身份。

不可追蹤性:非目標標簽總是以概率p向S發送消息，因此S無法識別出目標標簽響應，即對目標標簽的存在性不能做出判斷，從而無法對其追蹤。

防竊聽:由于對通信方的身份實行了匿名制，即使攻擊者獲取了通信方之間的所有通信消息，也不能從中獲得有用的信息，尤其是秘密信息。

防重放:每一次的會話號都是獨立隨機選擇的，而且在本次會話結束后，函數會刪除標簽和讀寫器的會話記錄，即使攻擊者在新會話中重放以前的消息，理想函數也會對其忽略。

并發安全:只有當前子會話結束后，理想函數才會對新會話進行響應和處理，有效解決多個標簽同時訪問理想函數出現沖突的情況。

所以，Fsearch實現了機密性、匿名性、不可追蹤性、防竊聽、防重放和并發安全等安全特性。

2.2 對真實協議的安全性證明

為了證明的方便，將協議3稱為πsearch，下面來證明πsearch是UC安全的。

命題 假設真實協議中的偽隨機函數是安全的，則對于任何一個攻擊者，πsearchUC實現了理想函數Fsearch的功能。

證明:對于任何攻擊者A、環境機Z，若至少有一個理想攻擊者S，使Z無法區分出自身是在與虛擬參與者R'i，T'*和S的交互，還是在與實際參與者Ri，T*和A的交互，從而認為πsearch安全地實現了Fsearch的功能。下面來構造攻擊者S:

首先，模擬S與Z的交互，Z產生所有的輸入，S把從Z傳來的輸入寫到A的輸入帶，同樣，A把輸出帶的內容拷貝到S的輸出帶上，被Z讀。其次，模擬S與A和Fsearch的交互，其過程如下:

(1)當 S收到 Fsearch發來的消息 broadcast(ssid，Anonymous(R'i))，則生成一個新的會話號newssid，記錄broadcast(newssid，reader)，接著發送消息broadcast(newssid，reader)給真實協議攻擊者A。

(2)當 S收到 Fsearch發來的消息 response(ssid'，Anonymous(T'j))，則生成一個新的會話號newssid'，記錄response(newssid'，tag)，發 送 消 息 response(newssid'，tag)給真實協議攻擊者A。

(3)當 S收到 A發來的消息 authenticate(newssid'，newssid，reader，tag)，則 查 看 記 錄 broadcast(newssid，reader)和response(newssid'，tag)是否存在:

若存在，則將其刪除，記錄 link(newssid，newssid'，reader，tag) 且 向 Fsearch發 送 authenticate(ssid'，ssid，Anonymous(R'i)，Anonymous(T'j));

(4)當S收到A發來的消息 search(newssid，newssid'，reader，tag)，則:①若該tag的攻陷標識位為1，則刪除S中關于它的所有信息直接向 Fsearch發送 search(ssid，ssid'，Anonymous(R'i)，Anonymous(T'j));②否則，查看記錄link(newssid，newssid'，reader，tag)是否存在:若存在，刪除該記錄，且向 Fsearch發送 search(ssid，ssid'，Anonymous(R'i)，Anonymous(T'j));否則，忽略該消息。

(5)當S收到A發來的消息corrupt(newssid')，則將S中的tag的攻陷標識位設為1。

(6)當S收到A發來的消息impersonate(newssid'，Tj)，則 若 記 錄 broadcast(newssid，reader)或 者 link(newssid，newssid'，reader，tag)存在，則直接發送 impersonate(ssid＇)給Fsearch，這與理想協議中的操作是一樣的。

下面分情況來證明真實協議與理想協議對于任意的環境機Z都是不可區分的:

(1)當標簽Tj被攻陷時

很顯然，這種情況下理想協議和真實協議是不可區分的。

(2)當標簽Tj沒有被攻陷時

下面利用可證明安全方法的思想來證明之。若對于任何攻擊者A、環境機Z，至少有一個理想攻擊者S，使Z能夠區分出自身是在與真實協議交互還是在與理想協議交互，則:在理想協議中，虛擬參與者與Fsearch間建立會話時的會話號，是Fsearch隨機獨立選擇的。而在真實協議中，每次A都會激發參與者產生一個偽隨機函數值，而標簽和讀寫器自身的內部行為及交互，對Z來說是不可見的。已知算法D是由Z構造的，具有以下功能:在每次仿真交互時執行Z的若干副本中的一個，且針對Z，模擬攻擊者A和實體Ri、T*并與其交互。當實體即將重新產生一個隨機數時，讓函數l生成一個偽隨機數。若Z在實體T*未輸出結果時已攻陷了T*，則D終止運行且輸出一個隨機值;不然，D繼續運行且其輸出為Z的輸出。若D沒有終止，且l是偽隨機函數，那么Z的輸出為它和πsearch交互時的輸出;若l是隨機函數，那么Z的輸出為它和Fsearch交互的輸出。所以，若Z能以不可忽略的概率區分出πsearch和Fsearch，那么D就能夠利用向一個隨機預言機發出詢問的方式，以同樣的概率區分出偽隨機函數和隨機函數。因為偽隨機函數是安全的，從而得出矛盾。由以上可得，對于任何攻擊者A和環境機Z，至少有一個理想攻擊者S，使得Z不能區分出自身是在與R'i，T*和S交互，還是在與Ri，T*和A交互，從而πsearch安全地實現了理想函數Fsearch的功能。綜合 (1)(2)，可以得出結論:πsearch是UC安全的，實現了機密性、匿名性、不可追蹤性、防竊聽、防重放、并發安全等安全特性。

3 分析與比較

下面就本文的最終協議與Tan、Ahamed、曹錚、趙斌分別在對應文獻［7，9-11］提出的協議在相關特性與安全性方面進行分析對比見表1。

表1 協議相關特性對比表

表1結果顯示，新協議相對其他幾個協議降低了標簽成本，且解決了以往協議中存在的通信雙方信息更新不同步問題。

表2 協議安全性對比表

表2結果顯示，新協議比其他幾個協議更安全，具有較高的安全性。

4 結束語

本文首先對前人的工作進行了分析和總結，針對出現的標簽成本較高以及容易遭受攻擊等問題，通過3個協議來逐層展示協議設計的過程，在這三個協議中，后一個協議總是對前一個協議的改進和完善，形成了最終的搜索協議3，且利用UC模型對其安全性進行了形式化證明，得出該協議是UC安全的，最后對新協議與前人協議在相關特性及安全性方面進行了對比，其結果達到了協議設計的初衷。

本文在協議的設計過程中有3個創新點:①協議中完全采用了偽隨機函數，真正減少了標簽邏輯門的數量，降低了標簽成本，適合于低成本的RFID系統。②考慮了偽隨機函數可能引發的碰撞性問題，提高了搜索的準確度。③通過在讀寫器存儲列表中增加搜索標識位避免了以通信雙方秘密信息更新不同步為目的的重放攻擊，提高了安全性，這同時也解決了非重放原因造成的更新不同步問題。但新協議也有不足:當讀寫器沒有搜索到目標標簽時，有可能要發起新一輪的搜索，這種情況將會導致搜索效率的下降。所以新協議比較適合于實時性要求不高，安全性要求相對較高的應用。因此，如何在降低標簽成本和保證安全性的基礎上，設計出更加高效的RFID搜索協議，是下一步需要做的工作。

［1］TAN C C，SHENG B，LI Q.Secure and serverless RFID authentication and search protocols［J］.IEEE Transactions on Wireless Communications，2008，7(4):1400-1407.

［2］QI Yong，YAO Qingsong，CHEN Ying，et al.Study on RFID authentication protocol theory ［J］.China Communications，2011，8(1):65-71.

［3］LI Jian，SONG Danjie，GUO Xiaojing，et al.ID updating-based RFID mutual authentication protocol for low-cost tags［J］.China Communications，2011，8(7):122-127.

［4］WEI C H，HWANG M S，Chin A Y.A mutualauthentication protocol for RFID ［J］.IT Professional，2011，13(2):20-24.

［5］DING Zhenhua，LI Jintao，FENG Bo.The research of secure authentication protocol based on hash function for RFID ［J］.Journal of Computer Research and Development，2009，4(4):483-592(in Chinese).［丁振華，李錦濤，馮波.基于Hash函數的RFID安全認證協議的研究［J］.計算機研究與發展，2009，4(4):483-592.］

［6］Seo K J，Jeon J C，Yoo K Y.A reinforced authentication protocol for anti-counterfeiting and privacy protection［C］//6th International Conference on Information Technology:New Gergerations.Las Vegas:IEEE Press，2009:1610-1611.

［7］TAN C C，SHENG B，LI Q.Serverless search and authentication protocols for RFID ［C］//5th International Conference on Pervasive Computing and Communication.New York:IEEE Press，2007:24-29.

［8］Kulseng L，YU Z，WEI Y.Light weight secure search protocols for low-cost RFID systems［C］//29th International Conference on Distributed Computing Systems.Washington:IEEE Press，2009:40-48.

［9］Ahamed S，Rahman F，Hoque E，et al.S3PR:Secure serverless search protocols for RFID ［C］//International Conference on Information Security and Asurance.Hawaii:IEEE Press， 2008:187-192.

［10］CAO Zheng，DENG Miaolei.A univerally composable RFID search protocol［J］.Journal of Huazhong University of Science and Technology，2011，39(4):56-59(in Chinese).［曹錚，鄧淼磊.通用可組合的RFID協議［J］.華中科技大學學報，2011，39(4):56-59.］

［11］ZHAO Bin.The research on RFID security authentication and search protocols without back-end database［D］.Xian:Xian University of Electronic Science and Technology，2011(in Chinese).［趙斌.無后端數據庫的RFID安全認證和搜索協議研究 ［D］.西安:西安電子科技大學，2011.］