無后端數據庫的RFID安全認證協(xié)議的改進方案*

王 萍，周治平，李 靜

江南大學 物聯(lián)網技術應用教育部工程研究中心，江蘇 無錫 214122

1 引言

隨著物聯(lián)網的快速發(fā)展，作為物聯(lián)網感知層的關鍵技術，射頻識別（radio frequency identification，RFID）以其非接觸式自動識別[1]的優(yōu)勢被廣泛應用于醫(yī)療[2]等領域。為保證RFID系統(tǒng)的安全和隱私，實現(xiàn)雙向認證是關鍵[3]。傳統(tǒng)RFID系統(tǒng)的基本結構由標簽、讀寫器和后端數據庫組成。讀寫器將接收到的標簽信息轉發(fā)到后端數據庫，由后端數據庫進行驗證。大部分情況下，讀寫器須通過有線的方式與后端數據庫相連，無法適用于移動RFID環(huán)境，因此無后端數據庫的RFID認證協(xié)議相繼被研究者提出。文獻[4]首先提出無后端數據庫的RFID認證和搜索協(xié)議，通過安全性分析發(fā)現(xiàn)，該協(xié)議只滿足單向身份驗證，易遭受讀寫器假冒等攻擊。文獻[5]在文獻[4]基礎上提出無后端數據庫的標簽搜索協(xié)議，與認證協(xié)議類似，該類協(xié)議在實現(xiàn)閱讀器和標簽相互認證的同時還可達到搜索標簽的目的。文獻[5]指出所提協(xié)議在滿足EPCC1G2標準的同時，還可抵抗去同步化、重放、假冒等攻擊。但隨后文獻[6]指出文獻[5]由于盲因子構造不合理，導致協(xié)議無法抵抗重放、去同步化攻擊，且標簽密鑰更新操作采用固定種子，導致位置隱私無法保證。文獻[7]提出增強隱私保護的無后端數據庫的RFID安全認證協(xié)議。但是文獻[8]指出文獻[7]所提的方案存在去同步化攻擊，并在此基礎上進行改進以解決去同步化攻擊。經分析，文獻[8]未能解決去同步化攻擊問題，且文獻[7-8]均無法保證位置隱私。文獻[9]提出基于Hash函數的無后端數據庫RFID安全認證協(xié)議，該方案具有較強的安全屬性。通過分析可知，以上方案讀寫器均采用遍歷方式搜索標簽，其時間復雜度為O(N)，不適用于大規(guī)模環(huán)境[10]。為了降低搜索標簽復雜度，基于樹的認證協(xié)議[11]被提出，其搜索時間復雜度為O(logαN)，其中α表示分支數，N表示標簽總數。樹型結構雖然降低了搜索時間復雜度，但是標簽一旦被攻擊者腐化獲得內部信息，就會導致其他標簽的密鑰信息被暴露。文獻[12]采用標簽共享主密鑰的方式來提高協(xié)議的搜索效率，這種方式可保證常數時間的認證，即搜索復雜度為O(1)[13]，另外該方案采用物理不可克隆函數來保證安全性。但經分析可知，一旦標簽主密鑰被攻擊者破解，文獻[12]所提安全性將無法保證，且物理不可克隆函數的輸出結果會隨著操作環(huán)境的變化而發(fā)生波動，因此大規(guī)模采用物理不可克隆函數仍是不現(xiàn)實的[5]。文獻[14]提出在大規(guī)模RFID系統(tǒng)中采用組認證方式以驗證合法標簽，該方案有效保證了標簽匿名性且降低了搜索復雜度。文獻[15]采用分組匿名認證的方式在降低搜索復雜度的同時保證標簽的不可鏈接性，但協(xié)議由于缺少密鑰更新操作，導致位置隱私無法保證。

通過分析發(fā)現(xiàn)，無后端數據庫的RFID安全認證協(xié)議主要存在以下幾點問題：（1）搜索時間復雜度高，為保護隱私安全，標簽需將密鑰加密后發(fā)送給讀寫器，讀寫器則通過將所有標簽的密鑰與消息進行匹配以驗證標簽合法性。因此，驗證標簽的時間代價與標簽數量呈線性關系，嚴重影響RFID系統(tǒng)的效率。（2）位置隱私難以保證，攻擊者通過腐化標簽獲得標簽的密鑰信息后重新將標簽放入流通，通過腐化的密鑰信息跟蹤標簽。（3）無法抵制常見的攻擊，如去同步化攻擊、重放攻擊等?；诖?，本文將采用組身份標識共享技術來提高文獻[8]的搜索效率，另外改進文獻[8]中讀寫器更新密鑰的方式，并在密鑰更新操作中引入隨機數，以解決去同步化攻擊并保證位置隱私。

2 相關工作

2.1 安全模型

2.1.1 隱私模型

Ouafi和Phan在文獻[16]中提出了一個形式化的隱私模型，本文將采用該隱私模型對協(xié)議進行安全性分析。攻擊者A可以訪問以下幾個預言機。

（1）Execute query(R,T,i)預言機：該預言機模擬攻擊者偵聽通信消息的能力。預言機將返回標簽T和閱讀器R在第i輪認證過程中的所有交互消息。

（2）Send query(U,V,m,i)預言機：該預言機模擬攻擊者假冒合法閱讀器或標簽進行交互的能力。即攻擊者A在第i輪認證過程中假冒標簽U∈T向閱讀器V∈R發(fā)送消息m，并收到閱讀器的響應m′。

（3）Corrupt query(T,k)預言機：該預言機模擬攻擊者訪問標簽T內部存儲數據，預言機將返回標簽的密鑰和狀態(tài)信息。

（4）Test query(T0,T1,i)預言機：該預言機執(zhí)行第i輪認證實例后，挑戰(zhàn)者隨機輸出一個比特位b∈{0,1}，并令Tb∈{T0,T1}，傳遞給攻擊者。若攻擊者能夠正確猜出隨機位b值，則攻擊者獲勝。

定義1（位置隱私）假設敵手通過調用預言機Corrupt query(T,k)腐化得到目標標簽第l次的密鑰和內部狀態(tài)，再對第l+1次會話進行分析，無法推知目標標簽第l+1次的密鑰和輸出信息。

2.1.2 攻擊者模型及安全假設

本文假設閱讀器與標簽之間的信道為不安全信道。攻擊者可竊聽、篡改、攔截標簽與閱讀器之間的通信消息，并且可以主動向標簽和閱讀器發(fā)起會話。對于位置隱私，攻擊者可調用以上所有預言機。而對于去同步化攻擊、重放攻擊，攻擊者無調用Corrupt query(T,k)和Test query(T0,T1,i)預言機的能力，即攻擊者無法獲取標簽內部信息。最后本文假設敵手無法獲取閱讀器內部信息（密鑰等）。

2.2 Deng等人方案的隱患分析

本文通過分析發(fā)現(xiàn)Deng等人[8]所提的方案在兩次通信交互后存在去同步化攻擊問題，并且該方案無法保證位置隱私。此外，文獻[8]中讀寫器搜索時間復雜度為O(N)，不適用于大規(guī)模的RFID環(huán)境。具體分析如下。

（1）去同步化攻擊

初始化階段，讀寫器Ri在數據庫中存儲標簽Tj的數據目錄(SeedTj,SeedPTj,idTj)，其中SeedTj為標簽Tj當前的密鑰種子，SeedPTj為標簽Tj的前一輪的密鑰種子，idTj為標簽Tj的身份標識符，且初始時刻SeedTj=SeedPTj。為方便簡述，令SeedTj=SeedPTj=a。

假設讀寫器Ri和標簽Tj成功執(zhí)行一次交互后，讀寫器Ri更新標簽Tj的密鑰種子為SeedTj=b，且標簽Tj也更新自身的密鑰種子，即Seed=b。在第二輪交互時，讀寫器Ri成功更新密鑰種子SeedTj=c，且將加密消息反饋給標簽Tj，這時攻擊者攔截消息使標簽Tj不更新自身的密鑰種子，從而使讀寫器存儲的標簽Tj兩輪密鑰種子與標簽Tj存儲的密鑰種子不一致，達到去同步化攻擊目的。

（2）位置隱私

學習階段：在第l輪交互過程中，攻擊者A調用預言機Corrupt query(T0,k)獲得標簽T0內部信息攻擊者A可以根據獲得的密鑰信息計算T0在第l+1輪的密鑰

挑戰(zhàn)階段：攻擊者隨機挑選兩個新鮮的標簽T0和T1作為測試對象，并調用預言機Test query(T0,T1,l+1)。攻擊者 A隨機選擇一個比特位b∈{0,1}，并令Tb∈{T0,T1}。攻擊者 A調用預言機 Execute query(R,Tb,l+1)獲得實體間的通信消息

猜測階段：攻擊者A停止游戲G，并輸出一比特位b′∈{0,1}作為對比特位b的猜測，即：

顯而易見，可以得出：

證明若Tb=T0，則：

Deng等人[8]方案的密鑰更新方式為僅對初始密鑰進行哈希運算，即 Seed=M(M(Seed))，其中 M(?)表示單向散列Hash函數。一旦標簽Tj被攻擊者腐化獲得內部信息Seed，則攻擊者獲得此后每輪密鑰種子的概率為1，且攻擊者A通過偵聽讀寫器與標簽間交互的隨機數可計算出表示偽隨機函數，因此攻擊者 A會時刻跟蹤目標標簽，協(xié)議的位置隱私無法保證?！?/p>

（3）搜索時間復雜度

讀寫器接收到標簽的應答消息后，采用偽隨機函數遍歷匹配的方式驗證標簽的合法性，其搜索時間復雜度為O(N)，其中N表示標簽的總數。因此，隨著存儲標簽數量的增加，讀寫器搜索時間也隨之線性上升。

2.3 改進協(xié)議描述

與Deng等人[8]所提方案類似，改進協(xié)議包含兩個階段：初始化階段和認證階段。

初始化階段：讀寫器和標簽存儲認證過程中所需的相關信息。與Deng等人[8]所提方案不同之處在于：改進協(xié)議將N個標簽分為τ組，每組包含n=N/τ個子標簽。標簽存儲所在組的身份標識IDGi以及自身密鑰SeedTj，讀寫器存儲自身標識IDi，τ個不同的組身份標識IDGi以及各標簽前后兩輪密鑰SeedTj。

認證階段：改進協(xié)議認證過程如圖1所示，具體過程如下。

（1）Ri→Tj：讀寫器 Ri生成隨機數 randi，并向標簽Tj發(fā)送查詢命令request以及randi。

（2）Tj→Ri：Tj接收到 Ri的消息后生成隨機數randj，計 算 aj=P(IDGi⊕(randj||randi))，nj=P(SeedTj⊕(randi||randj))，將 ＜aj,nj,randj＞ 作為響應消息發(fā)送給 Ri。

（3）Ri→Tj：Ri接收到Tj的消息后，首先在數據目錄中尋找IDGi使得 aq=P(IDGq⊕(randj||randi))，其中q∈{1,2,…,τ}。若 aq=aj，則表示特定標簽 Tj屬于第q組標簽。Ri繼續(xù)在第q組標簽的數據目錄中尋找SeedTj

，計算 nm=P(SeedTm⊕(randi||randj))，其中 m∈{1,2,…,n}。當nm==nj時，則標簽通過認證，讀寫器更新密鑰：SeedPTj=SeedTj,SeedTj=M(SeedTj⊕(randj||randi))。Ri更新完密鑰后計算s=M(SeedTj⊕randj),ni=P(s)；若nm≠nj，Ri在第q組標簽的數據目錄中尋找SeedPTm，計算 nm=P(SeedPTm⊕(randi||randj))，其中 m ∈ {1,2,…,n}。當nm==nj時，則標簽通過認證，讀寫器更新密鑰：SeedTj=M(SeedPTj⊕(randj||randi))。 Ri更新完密鑰后計算 s=M(SeedPTj⊕randj),ni=P(s)。最后 Ri將消息ni發(fā)送給Tj。

Fig.1 Authentication process of improved protocol圖1 改進協(xié)議的認證過程

（4）Tj：Tj接收到 Ri的消息后計算 k=M(SeedTj)，b=P(k)。若b==ni，則讀寫器通過認證，標簽更新自身密鑰：SeedTj=M(SeedTj⊕(randj||randi))；否則，終止協(xié)議且不更新密鑰。

3 安全性分析

3.1 GNY邏輯分析

此處用T表示標簽，R表示讀寫器。在證明之前需要先將協(xié)議消息進行形式化，并確定要證明的目標，同時對已知的信息進行初始假設。具體證明過程如下。

（1）協(xié)議形式化

（2）協(xié)議目標

①讀寫器對標簽的認證

②標簽對讀寫器的認證

（3）假設條件

（4）GNY邏輯證明

證明①：R|≡ T～#P(IDGi⊕(randj||randi))，R|≡ T～#P(SeedTj⊕(randj||randi))

由M1:R?randj和規(guī)則P1：可得：

證明②：T|≡ R|～#P(s)

由規(guī)則F1和假設條件A5:T|≡#randj可得：

由規(guī)則P2和假設條件A1:T?IDGi,SeedTj可得：

再由規(guī)則F10和式（9）、（10）可得：

繼而再由規(guī)則F10，令s=M(SeedTj⊕randj)可得：

3.2 理論分析

此處采用第2章介紹的安全模型對改進協(xié)議安全性進行分析。

（1）抵制重放攻擊

改進方案中讀寫器和標簽端產生不同的隨機數且采用偽隨機數函數進行加密，保證通信消息的新鮮性。假設攻擊者重放消息＜aj,nj,randj＞給讀寫器，由于每輪交互過程的通信消息aj=P(IDGi⊕(randj||randi))，nj=P(SeedTj⊕(randi||randj))中含有隨機數randi、randj，故重放消息將無法通過讀寫器的認證。同理，攻擊者重放消息ni無法通過標簽的認證。

（2）雙向認證

對讀寫器而言，讀寫器首先驗證特定標簽屬于哪一組標簽，即驗證aq=?P(IDGi⊕(randj||randi))。若相等，則讀寫器認為特定標簽屬于該組，且繼續(xù)驗證nm=?P(SeedTj⊕(randi||randj))。若相等，則讀寫器視特定標簽為合法標簽，并更新該標簽的密鑰。對標簽而言，標簽收到讀寫器的消息后驗證ni=?P(M(SeedTj))。若相等，則標簽視其為合法讀寫器，并更新密鑰。這種方式實現(xiàn)了標簽和讀寫器之間的雙向認證，不僅有效防止攻擊者假冒合法標簽的行為，而且又能避免攻擊者假冒授權讀寫器對合法標簽進行惡意跟蹤。

（3）位置隱私

學習階段：攻擊者A調用預言機Corrupt query(T0,k)獲得標簽T0第l輪的內部信息

挑戰(zhàn)階段：攻擊者隨機挑選兩個新鮮的標簽T0和T1作為測試對象，并調用預言機Test query(T0,T1,l+1)。攻擊者A隨機選擇一個比特位b∈{0,1}，并令Tb∈{T0,T1}。攻擊者A調用預言機Execute query(R,Tb,l+1)獲得實體間的通信消息

猜測階段：攻擊者A停止游戲G，并輸出一比特位b′∈{0,1}作為對比特位b的猜測，即：

由此可得出，攻擊者獲取標簽位置隱私的優(yōu)勢為：

證明在學習階段,攻擊者通過調用Corrupt query(T0,k)預言機獲取標簽T0第l輪的內部信息由于同組標簽的組標識相同，攻擊者無法通過對比消息來跟蹤標簽。攻擊者若要成功跟蹤目標標簽T0，則必須計算出與原協(xié)議不同，本文在密鑰更新操作中引入讀寫器和標簽的隨機數randi、randj與初始密鑰異或后再進行哈希加密，從而保證更新密鑰的隨機性和新鮮性，即使攻擊者獲取密鑰，仍無法得到，也就無法通過對比和確定b值，攻擊者成功猜測b值的概率為，即改進協(xié)議能夠保護位置隱私。 □

（4）抵制去同步化攻擊

改進方案中，讀寫器存儲上一輪和當前的密鑰信息，并且判斷接收到的標簽消息由哪一輪的密鑰計算獲得。若由上一輪的密鑰通過加密操作獲得，則只更新并存儲當前的密鑰，即SeedTj=M(SeedPTj⊕(randj||randi))；若由當前的密鑰通過加密操作獲得，則更新并存儲兩輪的密鑰，即SeedPTj=SeedTj，SeedTj=M(SeedTj⊕(randj||randi))，即使攻擊者通過攔截消息使標簽密鑰未更新，閱讀器仍能完成對標簽的認證。另外，攻擊者不能通過改變randi、randj值的方式導致讀寫器和標簽更新密鑰值不同，從而達到去同步化目的，一旦randi和randj的值被篡改，則將導致認證不成功，協(xié)議終止，密鑰將不會更新。綜上所述，改進協(xié)議可抵抗去同步化攻擊。

改進協(xié)議與現(xiàn)有典型協(xié)議[5,7-8,12,15]的安全性比較如表1所示。其中×表示不安全；√表示安全。由表1可知，僅文獻[12]和改進協(xié)議滿足所有安全屬性，但文獻[12]由于物理不可克隆函數的輸出隨著操作環(huán)境變化而波動的性質，導致該方案實用性較差，且該方案的安全性完全取決于主密鑰，一旦標簽主密鑰某時刻被攻擊者破解，該方案的安全性將難以保證。

Table 1 Security comparison of protocols表1 協(xié)議的安全性對比

4 仿真結果分析

4.1 搜索時間對比

此部分主要對現(xiàn)有協(xié)議[5,7-9,12,14]和改進方案在搜索時間上進行對比。本文仿真環(huán)境為Intel Core i3-2.10 GHz，RAM-6 GB；由于每次運行時間有細微差異，故測試30次取平均值，偽隨機函數（PRNG）耗時約為0.021 ms，哈希函數（Hash）耗時0.25 ms。為便于分析，本節(jié)對比最壞情況下讀寫器搜索特定標簽所需的時間。另外將文獻[14]與改進方案中N個標簽分為τ=2組標簽，每組有N τ個標簽，考慮最壞情況下特定標簽處于第2組最后位置的情況。如圖2所示，文獻[5,7-9,14]與改進方案中讀寫器搜索耗時均隨著標簽數量的增加而上升，但是改進方案的讀寫器搜索耗時的上升趨勢較文獻[5,7-9,14]方案更為平緩，因此改進方案通過采用組標識共享技術實現(xiàn)了更高的搜索效率；采用哈希遍歷匹配[9]方式的搜索耗時增長最快；而采用共享主密鑰[12]方式的搜索耗時為常數且最低，但在大規(guī)模環(huán)境下應用物理不可克隆函數仍是一個亟待解決的問題，且該方案在主密鑰被破解情況下，其所有安全性將無法得到保證；文獻[5,7-8]均采用偽隨機函數遍歷匹配，故搜索耗時相同；文獻[14]與改進方案雖然都采用分組的思想，但是文獻[14]采用單向Hash函數匹配標簽傳輸的消息，故搜索時間較改進方案高。

Fig.2 Comparison of reader search time-consuming圖2 讀寫器搜索耗時對比

4.2 分組對搜索時間的影響

改進方案中，當標簽數量N一定時，分組數的變化會導致讀寫器搜索特定標簽的時間隨之變化。如圖3所示，當N=10 000，N=100 000，N=200 000時，其搜索時間曲線的變化趨勢都是先下降，達到最小值之后再上升，這是由于讀寫器搜索標簽耗時與τ+N/τ相關聯(lián)。當N=10 000，τ=100時，讀寫器搜索時間最少，為4.2 ms；當N=100 000，τ=316時，讀寫器搜索耗時最少，為13.281 6 ms；當N=200 000，τ=447時，讀寫器搜索耗時最少，為18.783 ms。為了使讀寫器搜索耗時最少，則且1≤τ≤N，分析可得，當τ=N時，t取最小值。但是分組數τ為整數，因此τ=ceil(N)時，讀寫器搜索耗時最少。由圖3可得，當τ一定時，讀寫器搜索特定標簽所需耗時隨著標簽數量的增長而增加，當N一定時，讀寫器搜索特定標簽耗時隨著分組數的增加首先呈下降趨勢，達到最小值后又呈上升趨勢。因此，在改進協(xié)議中，需根據標簽的總數確定分組數，從而使讀寫器在最壞情況下搜索特定標簽的耗時最少，以達到最高的搜索效率。

Fig.3 Effect of the number of packets on reader search time圖3 分組數對讀寫器搜索時間的影響

4.3 通信時間對比

為了更加充分地說明本文采用的組標識共享技術在RFID系統(tǒng)效率上比原方案[8]的遍歷匹配方式有大幅的提升，此處將改進方案與哈希計算遍歷匹配[9]及偽隨機函數遍歷匹配[8]進行通信時間的對比。本文通過調用Java中的socket接口模擬讀寫器與標簽間的通信，利用System.nanoTime()函數計算一輪成功交互所需的時間。讀寫器的數據庫中存儲1×104個標簽，其中改進方案中將1×104個標簽分成100組，每組含有100個標簽。分別將目標標簽存儲于數據庫鏈表的第1個、第500個、第501個、第1 000個、第1 001個、第5 000個、第5 001個、第10 000個位置，測試一輪成功交互通信所需的時間。由于每次運行時間有細微差異，故測試10次取平均值，如表2所示。文獻[8-9]的通信時間隨著目標標簽所在數據庫位置的增長而呈線性上升趨勢，這是由于讀寫器需要遍歷搜索數據庫存儲鏈表以檢索目標標簽，且文獻[9]由于采用哈希計算遍歷匹配，故通信耗時比文獻[8]的偽隨機函數遍歷匹配高。而改進方案將一群標簽分組，通過組身份標識降低讀寫器搜索范圍，因此改進方案的通信效率與哈希及偽隨機函數遍歷匹配相比都有大幅提升。由于第500和501個分別處于第5組的最后位置和第6組的首位，故標簽處于數據庫第501個位置的通信時間較第500個位置低，其他同理。與原方案相比,改進方案通信時間更低，實用性更佳。

Table 2 Comparison of protocol communication time表2 協(xié)議通信時間對比

5 結束語

本文首先分析了Deng等人所提協(xié)議存在的去同步化攻擊、位置隱私無法保證以及閱讀器搜索時間復雜度高的問題，然后在此基礎上提出了一種改進的無后端服務器的RFID認證協(xié)議。改進方案完善了原協(xié)議在閱讀器成功驗證標簽后更新共享密鑰的方式，并將閱讀器和標簽產生的隨機數種子作為哈希函數的輸入參數更新密鑰。通過安全性分析可知，改進方案能夠保證讀寫器和標簽共享密鑰的同步更新，且保證了標簽的位置隱私。另外，改進方案采用組身份標識共享技術有效提高了讀寫器搜索效率。通過實驗仿真可知,隨著數據庫存儲標簽數量的增加，本文方案的讀寫器搜索耗時和通信耗時的增長趨勢較其他協(xié)議更為平緩，具有良好的可擴展性和實用性。另外，本文還通過實驗模擬了分組數對讀寫器搜索時間的影響，以便實現(xiàn)更低的搜索耗時。