采用PUF保護位置隱私的輕量級RFID移動認證協議*

孫子文，李 松

1.江南大學 物聯網工程學院，江蘇 無錫 214122

2.江南大學 物聯網技術應用教育部工程研究中心，江蘇 無錫 214122

1 引言

無線射頻識別技術（radio frequency identification，RFID）憑借快速識別和非接觸射頻通信的特性，成為供應鏈系統實現商品的自動化管理和信息追溯的重要技術手段。供應鏈系統普遍采用EPC C1G2（electronic product code class 1 generation 2）標準的低成本射頻標簽（以下簡稱標簽）具有遠距離識別和抗干擾性強的優勢，與此同時，標簽受限于成本限制，無法應用成熟的加密機制實現標簽的安全和隱私保護。供應鏈系統中將標簽附著在商品上以完成對商品的識別和追溯，由于標簽會對任意讀寫器的請求做出響應，攻擊者發動惡意攻擊獲得標簽中的商品信息，并通過追蹤不同時刻的標簽位置，將直接泄露商品在流通過程以及使用過程中商品所有者的位置隱私[1]。

為防止攻擊者對標簽的位置追蹤，文獻[2]采用密鑰更新式和列表式協議實現了標簽的匿名性和位置的不可追蹤性，但協議采用的RSA非對稱加密算法需要38K門電路，協議不適用于EPC C1G2標準，無法滿足供應鏈系統對標簽成本的限制[3]；文獻[4]拋棄了運算成本高的哈希算法，標簽只進行交叉、異或等簡單的位運算，符合EPC C1G2標準，但攻擊者可通過物理入侵獲得標簽和讀寫器密鑰，從而通過對標簽和讀寫器反向克隆的方式發起假冒攻擊；文獻[5]采用物理不可克隆函數（physical unclonable function，PUF）[6]作為密鑰生成機制，標簽只在認證過程由PUF電路產生相應的會話密鑰，避免傳統加密機制將密鑰存儲在非易失性存儲器易被攻擊者竊取的弊端，可有效抵御假冒攻擊[7]；文獻[8]考慮了服務器與讀寫器之間的信道安全問題，引入服務器對讀寫器身份的安全認證，適用于移動讀寫器的認證環境；文獻[2,5]中服務器對標簽的識別需要遍歷整個服務器，識別效率低不適用于供應鏈中大規模RFID系統的使用。

針對EPC C1G2標準的低成本標簽運算能力低、易遭受假冒攻擊、標簽和讀寫器位置容易被追蹤等問題，本文設計了一種采用PUF保護位置隱私的輕量級RFID移動認證協議（PUF based lightweight authentication protocol for location privacy in mobile RFID system,PLLM）。PLLM協議采用PUF函數生成密鑰，64位輸出的PUF電路僅需要500～700門電路[9]，標簽的模平方運算僅需幾百門電路，128位偽隨機數生成需要1 500門電路，標簽的安全電路整體僅需3 000門電路[8]，且協議不使用哈希函數等運算量大的加密算法，符合EPC C1G2的應用標準，解決標簽運算能力不足的問題；標簽密鑰由兩步PUF電路生成，攻擊者對標簽的入侵將直接導致PUF電路失活而無法獲得完整密鑰，使得攻擊者無法克隆標簽，以解決攻擊者對標簽的非法入侵和假冒攻擊的問題，搭載PUF電路的標簽使得商品同樣具備不可偽造性，實現供應鏈中商品的防偽保護；協議通過不斷更新的共享密鑰，實現前向和后向不可追蹤性，以解決供應鏈系統中攻擊者對標簽和讀寫器的位置追蹤問題；服務器通過中國剩余定理可快速檢索標簽和讀寫器的合法身份，識別速率不隨數據庫中標簽數目的增長而線性加長，滿足供應鏈對RFID系統中標簽規?？赏卣沟膽靡?；Alagheband等人[10]改進了Vaudenay模型[11]的預假設，使其適用于前向隱私和后向隱私的分析。本文采用改進的Vaudenay模型證明PLLM協議的安全和隱私性。

2 安全隱私模型

Vaudenay提出的安全隱私模型對安全和隱私進行了嚴格定義，是目前為止用于協議分析最全面的安全隱私模型[12]。Vaudenay模型中，通過預言機描述了攻擊者與RFID系統交互的過程，其中預言機的功能介紹如表1所示。

根據攻擊者查詢Corrupt預言機的權限，劃分4類能力遞進的攻擊者，其中最弱的Weak攻擊者無法查詢Corrupt預言機，而Forward攻擊者可查詢Corrupt預言機，Destructive攻擊者查詢Corrupt后無法訪問任何預言機，能力最強的Strong攻擊者可以沒有限制地進行Corrupt預言機查詢。同時根據攻擊者查詢Result預言機權限劃分Narrow和Wide的兩類攻擊者（Narrow攻擊者無法查詢Result，而Wide攻擊者可以查詢），最終根據以上兩種不同的分類劃分為8類攻擊者。

Vaudenay模型的預假設及其應用中的不足：

（1）假設讀寫器與服務器之間的信道是安全的，未考慮讀寫器遭受假冒攻擊的問題，不適用于移動讀寫器的認證環境。

（2）假設攻擊者錯過了標簽密鑰的更新過程，不符合位置追蹤的實際攻擊環境。

（3）假設標簽僅在i次會話遭受攻擊，未考慮攻擊者對第i+1和i-1次會話中標簽位置的追蹤問題，不適用于前向和后向不可追蹤性的協議分析。

基于以上三點不足，修改Vaudenay模型的預假設條件使其適用于位置隱私分析。將讀寫器與服務器之間的信道安全納入協議的安全考量，考慮讀寫器遭受攻擊者非法入侵和假冒攻擊的問題，使其符合移動讀寫器的認證環境；假設敵人為Narrow-Strong的攻擊者，沒有錯過密鑰更新過程，可以對協議進行持續的監聽；分析第i+1和i-1次會話協議的安全性，并依照Alagheband等人[10]提出的前向和后向不可追蹤性，定義協議的位置隱私。

定義1（前向不可追蹤性[10]）攻擊者竊聽標簽第i次會話記錄并通過入侵標簽得到第i次會話的標簽內部信息，攻擊者分析第i+1次會話記錄，無法推斷出第i+1次標簽內部信息和輸出信息，因此攻擊者無法對標簽第i+1次狀態進行追蹤。

定義2（后向不可追蹤性[10]）攻擊者竊聽標簽第i次會話記錄并通過入侵標簽得到第i次會話的標簽內部信息，攻擊者分析第i-1次會話記錄，無法推斷出第i-1次標簽內部信息和輸出信息，因此攻擊者無法對標簽第i-1次狀態進行追蹤。

3 PLLM認證協議描述

PLLM協議使用的符號和注釋如表2所示，PLLM協議由初始化和雙向認證兩個階段組成。

Table 1 Function introduction of each oracle表1 預言機功能介紹

3.1 初始化階段

密鑰生成及共享機制。由服務器生成4個大素數p、q、g、h作為服務器解密標簽和讀寫器會話信息的私鑰，并將n=p?q,m=g?h分別作為標簽和讀寫器加密會話信息的公鑰。

Table 2 Annotation of each notation in this protocol表2 協議使用的符號及其注釋

共享密鑰S1由服務器生成并發送給標簽和讀寫器，標簽使用共享密鑰S1和自身參數a、b，經內部PUF電路計算P(a)、P(b),用以生成參數c：

讀寫器使用S1和自身參數d、e，經內部PUF電路計算P(d)、P(e),用以生成參數f：

共享密鑰S2由服務器生成并在每次認證成功后更新，初始狀態S2=S-12,服務器計算系統中每個合法標簽的索引值：

3.2 雙向認證階段

雙向認證協議由讀寫器發起，協議流程如圖1所示，具體認證步驟如下：

（1）由讀寫器生成隨機數r1，并將r1以廣播的形式發送給通信范圍內的所有標簽。

（2）標簽接收到讀寫器廣播信息r1后，生成隨機數r2，并完成以下計算：

根據式（5）得到的x的值采用二次剩余定理計算：

根據式（6），服務器在后期的認證中采用中國剩余定理解密x′得到4個模平方根(x1,x2,x3,x4),服務器需執行4次匹配工作。為提高服務器的后臺搜索效率，在式（7）中使用x2取代式（6）的x，服務器將求得唯一的模平方根x值[13]，從而解決了式（6）存在的非唯一解的問題。

標簽的會話密鑰kT由兩步PUF生成。第一步由標簽的PUF電路計算P(a)，并將P(a)異或隨機數r2得到標簽的會話密鑰：

隨即將P(a)和r2從標簽內存中刪除。

第二步運行標簽PUF電路計算P(b)，使用P(b)和c更新標簽會話密鑰：

隨即刪除內存中的P(b)。

通過兩步生成會話密鑰，使得攻擊者在任意時刻入侵標簽都無法獲得完整密鑰，從而抵御攻擊者的假冒攻擊。

標簽通過kT保護標簽隨機數r2，并通過x″保護標簽標識符H(TID)，實現了標簽匿名性和不可追蹤性，達到保護標簽位置隱私的目的。最后標簽將[x″,kT]作為交互信息通過射頻天線發送給讀寫器。

（3）讀寫器接收到來自標簽的響應[x″,kT]后，生成隨機數r3，并完成以下計算：

讀寫器的PUF電路生成P(d)后計算讀寫器的會話密鑰：

隨即將內存中的P(d)和r3刪除。

Fig.1 Proposed authentication protocol圖1 協議認證流程

運行讀寫器PUF電路生成P(e)，并更新會話密鑰：

隨即刪除內存中的P(e)。

讀寫器通過kR保護讀寫器隨機數r3，并通過y″保護讀寫器標識符H(RID)，實現了讀寫器匿名性和不可追蹤性，達到保護讀寫器位置隱私的目的。最后讀寫器將[x″,kT,r1,y″,kR]發送給后臺服務器。

（4）服務器接收到認證請求[x″,kT,r1,y″,kR]后，通過共享密鑰S1與讀寫器的會話密鑰kR異或求得：

采用中國剩余定理從式（12）中計算得到唯一的y：

服務器可快速驗證：

Ify⊕r1⊕r3′=H(RID)then讀寫器身份認證成功；

Else讀寫器是非法身份，服務器停止認證。

隨之共享密鑰S1與標簽的會話密鑰kT異或求得：

采用中國剩余定理從式（7）中計算x：

服務器可快速驗證：

Ifx⊕r1⊕r2′=RTIDorR-1TIDthen標簽身份認證成功；

Else標簽是非法身份，服務器停止認證。

讀寫器和標簽皆認證合法后，更新服務器與標簽之間的共享密鑰S2：

服務器計算確認字符：

ACK′包含服務器的認證信息，以便讀寫器和標簽驗證服務器的合法身份，實現更安全的雙向認證。最終服務器將ACK′發送給讀寫器。

（5）讀寫器接收到ACK′后，驗證：

Ifr3=[ACK′⊕H(（y)l]l為偽隨機數r3的位長）then認證服務器為合法身份；

Else服務器是非法身份，停止認證。

服務器身份認證成功，讀寫器繼續計算：

并將ACK發送給標簽。

（6）標簽接收到ACK后，驗證：

then認證服務器為合法身份；

Else服務器是非法身份，停止認證。

服務器身份認證成功，進而更新標簽的共享密鑰：

協議中標簽僅使用偽隨機數、異或、取余和PUF等輕量級運算，符合EPC C1G2的應用標準。

4 協議的安全隱私性證明和性能分析

4.1 安全和隱私性分析

基于Vaudenay模型建立協議運行環境和具備不同能力攻擊者的安全模型，證明PLLM協議的安全性和隱私性。使用定理1和定理2證明PLLM協議滿足前向不可追蹤性和后向不可追蹤性，保護標簽的位置隱私。使用定理3、定理4和定理5證明協議可抵御攻擊者的假冒攻擊和去同步化攻擊。

定理1在Narrow-Strong的攻擊者能力模型下，PLLM協議滿足前向不可追蹤性。

證明Narrow-Strong的攻擊者通過入侵和監聽標簽的第i次會話，得到標簽第i次會話的內部信息和會話記錄，攻擊者持續監聽標簽的第i+1次會話記錄，攻擊者無法依此推斷出第i+1次標簽的內部信息和輸出信息。由滿足前向不可追蹤性的算法流程圖2所示，從以下四方面考慮攻擊者實現前向追蹤的可能性。

（1）標簽的輸出信息和密鑰更新都需要計算x值，攻擊者求解第i+1次會話中標簽的xi+1值：

Fig.2 Proof flow of forward untraceable圖2 滿足前向不可追蹤性的證明流程圖

由式（25）可知，攻擊者查詢Corrupt預言機獲得第i次會話標簽內部信息[H(TID),Si2,n,a,b,c]，并通過監聽第i+1次標簽會話獲得r1i+1。由于皆為128位隨機數，且在第i次認證后通過偽隨機函數更新，使得。因此攻擊者成功模擬求得xi+1值的概率為：

（2）攻擊者利用監聽到的第i+1次標簽輸出信息(x″)i+1反向求解xi+1的值：

由式（27）可知，攻擊者入侵第i次會話標簽獲得內部信息n，協議的安全性取決于基于大整數n的素數分解問題[14]。攻擊者在缺少p、q私鑰的情況下無法分解n，因此攻擊者無法求解(x′)i+1和xi+1。

（3）攻擊者監聽標簽會話記錄，求解第i+1次確認字符ACKi+1：

由式（28）可知，攻擊者入侵標簽獲得內部信息H(TID)并監聽得到第i+1次會話記錄ri+11。攻擊者求解ACKi+1需要計算PRNG(xi+1⊕(x′)i+1)，由式（27）可知攻擊者無法求解xi+1和(x′)i+1，因此攻擊者無法追蹤標簽的確認字符ACKi+1。

（4）攻擊者求解第i+1次標簽的會話密鑰：

攻擊者在第i次會話入侵標簽獲得標簽參數a、b、c，協議中標簽的會話密鑰Ki+1T通過兩步PUF函數生成，且在每步PUF計算后刪除內存中的運行參數。攻擊者求解Ki+1T需要兩次物理入侵標簽，分別獲得PUF函數輸出值P(a)和P(b)。由于PUF函數的防篡改性，攻擊者的物理入侵將破壞PUF的結構從而無法再次生成PUF[6]，攻擊者僅能獲得P(a)或P(b)。攻擊者通過數學模擬PUF電路輸出和ri+12值從而成功計算標簽輸出Ki+1T的概率為：

定理2在Narrow-Strong的攻擊者能力模型下，PLLM協議滿足后向不可追蹤性。

證明Narrow-Strong的攻擊者在標簽的第i次會話入侵標簽，得到標簽內部信息和會話記錄。由后向不可追蹤性的證明流程圖3可知，攻擊者無法推斷第i-1次標簽密鑰xi-1和輸出信息[(x″)i-1,Ki-1T,ACKi-1],因此無法對后向會話中的特定標簽進行區分，攻擊者后向追蹤的優勢AdvABackward-untra＜＜ε,協議滿足后向不可追蹤性。

Fig.3 Proof flow of backward untraceable圖3 滿足后向不可追蹤性的證明流程圖

綜上，攻擊者無法求解標簽第i+1次會話的xi+1,

定理3Narrow-Destructive的攻擊者能力模型下，PLLM協議可抵御攻擊者對標簽的假冒攻擊。

證明Narrow-Destructive的攻擊者假冒標簽的響應[x″,kT]，服務器不會將攻擊者識別為合法標簽，從而抵御攻擊者對標簽的假冒攻擊。

由定理1可知，攻擊者無法正向計算x值，進而無法計算x″。按照以下兩方面分析攻擊者成功計算kT的可能性。

（1）攻擊者入侵標簽，獲得標簽內部信息。

由式（32）可知，攻擊者計算kT需要模擬P(a)和P(b)且需要得到r2。PUF函數依據電路在制造過程中工藝偏差，每塊PUF電路產生的響應序列具有唯一性和不可復制性，攻擊者無法通過數學運算模擬P(a)和P(b)。且攻擊者對標簽的物理入侵將對標簽的PUF電路造成不可逆的損壞，導致PUF電路失活，使得PUF(x)′≠PUF(x)[15]。因此攻擊者對標簽的入侵無法獲得kT的全部參數，攻擊者無法成功計算kT。

（2）攻擊者監聽無線信道的會話記錄以假冒標簽。

攻擊者查詢標簽和讀寫器之間的會話記錄，并利用標簽的真實響應來假冒合法標簽與服務器交互。由于標簽在每次身份認證完畢都會更新標簽密鑰S2，使得。因此，攻擊者無法利用標簽的歷史響應完成身份認證。綜上，PLLM協議可以抵御Narrow-Destructive的攻擊者對標簽的假冒攻擊。

定理4在Narrow-Destructive的攻擊者能力模型下，PLLM協議可以抵御攻擊者對讀寫器的假冒攻擊。

證明Narrow-Destructive的攻擊者假冒讀寫器的響應[x″,kT,r1,y″,kR]，服務器不會將攻擊者識別為合法讀寫器，從而抵御攻擊者對讀寫器的假冒攻擊。

讀寫器與服務器之間的會話信息不在無線射頻信道上傳輸，攻擊者無法竊聽讀寫器的響應，只能通過入侵讀寫器的方式假冒讀寫器。攻擊者入侵讀寫器可以獲得讀寫器信息[H(RID),m,d,e,f]。攻擊者為了假冒讀寫器需要計算讀寫器會話密鑰kR：

由定理3可知，攻擊者無法通過數學運算模擬PUF輸出P(d)和P(e)，從而無法計算kR。PLLM協議可以抵御Narrow-Destructive的攻擊者對讀寫器的假冒攻擊。

定理5在Narrow-Destructive的攻擊者能力模型下，PLLM協議可以抵御攻擊者的去同步攻擊。

證明攻擊者無法通過阻塞信道或偽造確認字符ACK的方式，導致服務器與標簽之間的共享秘鑰S2不同步。從以下兩方面考慮攻擊者的去同步攻擊：

（1）攻擊者阻塞讀寫器與標簽之間的信道。

由于標簽接收不到讀寫器發送的確認字符ACK，導致標簽更新共享秘鑰S2失敗。標簽在下次認證過程中依舊使用先前未更新密鑰S-12。但PLLM協議中，服務器同時存儲S2和S-12，依舊可以實現對合法標簽的身份認證。

（2）攻擊者偽造確認字符ACK并發送給標簽。

攻擊者通過偽造ACK的方式，使得標簽更新共享密鑰S2，從而導致服務器永久性地拒絕標簽的認證請求。由定理1可知，攻擊者無法求解偽造ACK所需的x和x′，因此標簽計算ACK=H(TID)⊕r1⊕PRNG(x⊕x′)無法驗證通過，從而標簽不會更新密鑰S2。綜上，PLLM協議可以抵御攻擊者的去同步攻擊。

4.2 性能分析

PLLM協議與現有文獻[2,4-5,8]的安全性能對比如表3所示。

Table 3 Security performance comparison of protocols表3 協議安全性能對比

文獻[2]采用RSA的非對稱加密算法實現標簽的前向和后向不可追蹤性，但加密算法運算壓力大不適用低成本標簽。文獻[4]的標簽端僅使用偽隨機數、交叉、異或等輕量級運算，攻擊者通過竊聽無線信道上的會話記錄獲得NR和TID⊕NR，攻擊者利用計算得到的標識符TID假冒標簽，并可對前向和后向會話中標簽狀態進行追蹤。文獻[8]采用二次剩余定律保護標簽輸出信息，避免攻擊者的追蹤，但攻擊者可以通過物理入侵的方式獲得標簽和讀寫器密鑰而發起假冒攻擊。文獻[5]通過物理不可克隆函數生成標簽密鑰，可有效地抵御攻擊者對標簽的物理入侵，但協議中標簽涉及大量哈希運算，且未考慮讀寫器與服務器之間的信道安全問題，缺少服務器對讀寫器身份的合法性認證，不適用于移動RFID認證環境。PLLM協議通過兩步PUF運算保護標簽密鑰的隨機數，解決了標簽密鑰更新過程中的隨機數易被攻擊者竊取的問題，可成功地抵御攻擊者的假冒攻擊，協議滿足前向和后向不可追蹤性，標簽僅使用偽隨機數、異或、取余和PUF等輕量級運算，適用于EPC C1G2標準。

Table 4 Computation costs of protocols表4 協議開銷對比

Fig.4 Search time comparison of indexing target tag圖4 搜索特定位置標簽的耗時對比

計算開銷部分只對比運算成本較大的隨機數、偽隨機數、求余運算、哈希、PUF運算和交叉運算，PLLM協議與現有文獻[2,4-5,8]在計算開銷和后臺搜索開銷的對比如表4所示。文獻[2,5]的標簽需進行哈希運算，不適用于低成本標簽。文獻[4,8]中標簽僅使用偽隨機數、求余和交叉等輕量級運算。PLLM協議相較文獻[8]標簽端的運算量略有提升，標簽需生成3次偽隨機數、2次求余運算和2次PUF運算，但PUF函數保護了標簽密鑰，有效地抵御假冒攻擊，協議實現了更高的安全性。

協議的各項性能指標中，服務器的搜索開銷決定協議是否適用于大規模RFID系統。對服務器搜索特定標簽消耗的時間進行仿真實驗。實驗通過PC機（CPU：Intel-2520M 2.5 GHz×2，RAM：8 GB）來模擬后臺服務器，仿真環境使用Matlab。在數據庫中設定6×103個標簽，分別對第1×103個、2×103個、3×103個、6×103個特定標簽進行搜索耗時的仿真實驗，來測試不同協議中服務器從接收到特定標簽的認證請求到識別成功的時間[16]。由于計算機的每次運行存在細小差異，故采用測試10次求取均值的方法作為比較結果。協議搜索耗時對比如圖4所示。

文獻[2,4-5]中服務器對標簽身份的認證需要遍歷整個服務器，對數據庫中特定位置的標簽的搜索耗時呈線性增長，第6×103個標簽的搜索耗時分別為1.274 4 s、0.786 7 s和1.912 5 s，無法滿足大規模RFID系統對標簽快速認證的應用要求。文獻[8]中服務器根據中國剩余定理解得隨機數u的模平方根(u1,u2,u3,u4)和隨機數t的模平方根(t1,t2,t3,t4),故最壞情況下，服務器需要匹配16次才可成功認證讀寫器和標簽身份。PLLM協議中，服務器通過標簽會話密鑰與共享密鑰的異或運算得到隨機數，從而直接計算讀寫器和標簽的標識符，實現身份的快速認證，服務器的搜索壓力最低。

在RFID系統的實際應用中，服務器對偽造標簽的快速識別能力是決定RFID系統性能的另一個重要指標。攻擊者偽造標簽標識符參與認證過程，現有協議中服務器對偽造標簽的識別通常需要遍歷整個后臺數據庫，這將造成服務器巨大的資源浪費并一定程度延遲合法標簽的認證時間，且大量偽造標簽對服務器發起認證請求將導致RFID系統無法正常工作。采用與上述實驗相同的仿真參數，數據庫中設定6×103標簽，測試不同協議中服務器對偽造標簽的識別耗時，如圖5所示。PLLM協議相較文獻[2,4-5,8]的搜索耗時分別減少99.09%、90.6%、99.4%和91.3%，PLLM協議拒絕偽標簽的性能優勢明顯。

5 結束語

Fig.5 Search time comparison of indexing counterfeit tag圖5 識別偽標簽的搜索耗時對比

本文設計了適用于供應鏈商品管理的RFID移動認證協議，PLLM協議使用偽隨機數、求余、PUF等輕量級運算，符合EPC C1G2的應用標準。協議采用PUF作為密鑰生成機制，在有效抵御攻擊者假冒攻擊的同時可實現商品的防偽保護?；赩audenay模型，理論證明PLLM協議滿足前向和后向不可追蹤性，能夠有效保護移動RFID認證環境下標簽的位置隱私，防止攻擊者對供應鏈中商品的位置跟蹤。相較現有文獻[2,4-5,8]，PLLM協議具有最高的安全性、最快的后臺服務器搜索效率和更快的拒絕偽標簽的效率。同時，由于PUF函數的輸出極易遭受環境變量的影響，導致認證結果不穩定。在低成本標簽有限的安全電路基礎上設計高效且可靠的模糊提取器，以提高PUF輸出的魯棒性是今后的研究重點。