基于PPUF的高效RFID隱私認證協(xié)議

向學哲，馬昌社

(華南師范大學計算機學院，廣東廣州510631)

RFID(Radio Frequency IDentification)技術［1］是物聯(lián)網(wǎng)的底層關鍵支撐技術之一，對物聯(lián)網(wǎng)的發(fā)展起著舉足輕重的作用.如今，安全和成本問題已成為制約物聯(lián)網(wǎng)發(fā)展的2個主要因素. 能否以較低的代價來獲取較高的隱私安全性是大規(guī)模物聯(lián)網(wǎng)應用的前提條件，對于RFID 技術更是如此，因此，工業(yè)界和學術界進行了相關研究，主要集中在使用輕量級的密碼技術來實現(xiàn)RFID 隱私保護.文獻［2］論證了保證RFID 隱私性的必要條件是標簽能夠計算偽隨機函數(shù)，而具有密碼學意義上安全的偽隨機函數(shù)的計算開銷巨大，不適合RFID 這種資源受限環(huán)境.因此，從某種意義上來說，純粹從密碼技術出發(fā)難以設計出具有可證明安全的RFID 隱私保護技術. 幸運的是，微電子技術的發(fā)展為RFID 隱私保護技術的設計提供了嶄新的設計工具:物理不可克隆函數(shù)(PUF:Physically Unclonable Function)［3］可以用來以幾乎零成本的方式獲得RFID 隱私認證協(xié)議. 簡單地說，PUF 是一種基于消息挑戰(zhàn)應答模式的物理裝置，它是物理系統(tǒng)的物理指紋.PUF 依據(jù)物理系統(tǒng)的內在屬性和物理系統(tǒng)自身體系結構而設計，所以其生產(chǎn)成本非常低，它的物理不可克隆性被用來設計防止邊信道攻擊的安全方案.

一個RFID 應用系統(tǒng)一般由標簽、閱讀器和后端數(shù)據(jù)庫組成:每一個標簽具有全球唯一的電子編碼，并附著在物體上以標識該物體;閱讀器負責激活被動式標簽并利用后端數(shù)據(jù)庫結合標簽的應答信息完成對標簽的識別或認證.盡管PUF 函數(shù)可以減輕RFID 標簽端的復雜性，但是其不可克隆性卻增加了閱讀器端對其進行識別的復雜性.目前PUF 有2 種應用方法:其一是直接用標簽內置的PUF 的應答來對標簽進行認證;其二是在標簽端把PUF 當作一個密鑰存儲器使用，再加上一個密碼認證函數(shù)來實現(xiàn)對標簽的認證.在前一種方法中，閱讀器端為了實現(xiàn)對標簽的認證，需要事先存儲多個挑戰(zhàn)應答對，每次認證標簽時，選擇一個挑戰(zhàn)消息發(fā)送給標簽，然后把標簽的應答消息和存儲的應答消息進行比對后做出對標簽的認證.顯然，為了保證隱私性，閱讀器端需要對每一個標簽存儲足夠的挑戰(zhàn)應答對，因此嚴重地增加了閱讀器的存儲負擔，而且不能保證隱私性，因為標簽對同一個挑戰(zhàn)消息的應答是一樣的. 后一種方法僅僅增加了標簽中秘密信息的存儲安全，其認證性和隱私性完全依賴于標簽中的密碼認證函數(shù)，因此沒有體現(xiàn)出PUF 的優(yōu)越性，不會有解決標簽低成本問題.

PPUF(Public Physically Unclonable Function)［4］是一種特殊的PUF，在知道其描述的條件下，可以模擬其輸出.本文從PPUF 出發(fā)，圍繞PPUF 的優(yōu)越性，設計了一個高效且低成本的RFID 認證協(xié)議RPAP(RFID Privacy－preserving Authentication Protocol).在效率方面，協(xié)議RPAP 中的標簽只需要配置一個PPUF 而不需要其他的計算能力，同時閱讀器端可以在常數(shù)時間內完成對標簽的識別. 由于PPUF 可以依據(jù)標簽內部的存儲電路來實現(xiàn)，因此，RPAP 協(xié)議簡單、高效且標簽生產(chǎn)成本低. 在隱私安全性方面，協(xié)議RPAP 可以抵抗破解攻擊等各種強隱私攻擊，本文證明了其具有SInd－privacy 隱私安全性.總之，RPAP 協(xié)議充分利用PUF 的優(yōu)點，做到了低成本和隱私安全的結合，為RFID 技術大規(guī)模應用提供了技術支撐.

1 RFID 隱私認證技術相關研究

目前，業(yè)界提出了若干RFID 隱私安全解決方案和協(xié)議，但是都存在問題:要么不具有安全性，要么生成成本高.

在輕量級RFID 協(xié)議設計方面，采用簡單操作(比如:比特異或、比特內積、16 比特的隨機數(shù)發(fā)生器等)，文獻［5］和文獻［6］分別設計了簡單的RFID雙向認證協(xié)議.然而，這2個協(xié)議都容易遭到隱私攻擊［7］.采用對稱密碼技術，文獻［8］首次提出了一個基于樹的RFID 認證系統(tǒng)，不能抵抗主動攻擊.實際上，在基于樹的RFID 系統(tǒng)中，所有標簽之間需要或多或少的共享某些秘密信息，讀取某一標簽的內部狀態(tài)后，可以利用它攻擊其他標簽的隱私性.因此基于樹的RFID 系統(tǒng)都不能抵抗主動跟蹤攻擊.

基于哈希函數(shù)，文獻［9］設計了一個簡單安全的RFID 系統(tǒng)(簡稱OSK 協(xié)議)，該系統(tǒng)的可擴展性很差，因為閱讀器端識別標簽所需要的計算量與RFID 系統(tǒng)中標簽的數(shù)目成線性關系.這制約了OSK不能用于標簽數(shù)目比較大的應用場合. 后來的研究者們采用狀態(tài)同步并結合哈希鏈提出了各種各樣的RFID 協(xié)議［10］，這些協(xié)議中大部分仍不具有安全性［10］.因此，設計低成本且隱私安全的RFID 協(xié)議仍是研究者們主要工作所在.

2 預備知識

定義1 稱函數(shù)ε:{0，1}n→R 是可以忽略不計的，如果它滿足:對任意一個多項式p(n)，當n 充分大時有:ε(n)＜1/p(n).

2.1 RFID 系統(tǒng)

假設RFID 系統(tǒng)［11］中共有n個標簽，它們是T={T1，…，Tn}，只有一個閱讀器R 和一個后端數(shù)據(jù)庫系統(tǒng)DB.每一個標簽由一個唯一的ID 所標識，閱讀器有一個或者多個射頻收發(fā)器，后端數(shù)據(jù)庫系統(tǒng)DB維護認證標簽所需要的所有數(shù)據(jù)，比如標簽的密鑰、ID、狀態(tài)信息等.這里假設閱讀器和后端數(shù)據(jù)庫之間的通信是安全的，并且后端數(shù)據(jù)庫屬于安全數(shù)據(jù)庫.

圖1 RFID 認證協(xié)議Figure 1 RFID authentication protocol

由于現(xiàn)有大部分RFID 協(xié)議只有2 輪或者3 輪通信，因此本文僅考慮不超過三輪通信的RFID 協(xié)議(圖1).這里sT是標簽中存儲的狀態(tài)信息(包含標簽的密鑰)，l1、l2和l3分別表示協(xié)議第1 輪、第2輪和第3 輪消息的比特長度. 當標簽收到協(xié)議的挑戰(zhàn)消息m1{0，1}l1之后，它返回1個應答消息m2{0，1}l2，然后閱讀器返回協(xié)議第3 輪消息m3給標簽.此外，一個RFID 系統(tǒng)RS ={T，R，DB}還包含協(xié)議π(R，Ti):調用R 和Ti執(zhí)行一次完整的認證協(xié)議(圖1)，返回協(xié)議消息(m1，m2，m3).

2.2 PPUF 及其屬性

由于生產(chǎn)制造過程中各種因素之間的差異性導致了實現(xiàn)同一功能的2個物理系統(tǒng)在內部物理結構上存在差異性，這就是物理系統(tǒng)的指紋，而PUF 恰是這一指紋的表現(xiàn).比如:在大規(guī)模集成電路的生成過程中，由于硅精格的多樣性以及化工機械打磨過程中的非均勻性，導致了每一個電路門具有不同的物理特性，即使在45 納米技術中，同一個門在不同的集成電路中的時延是不一樣的，利用這種時延的不一致性，就可以構造一個PUF 函數(shù). 而制造過程中工藝的復雜性和偏差的隨機性使得這樣的PUF 具有一種良好的屬性也就是物理不可克隆性.簡單地說，PUF 就是一種基于物理結構的挑戰(zhàn)應答系統(tǒng).假設F 是一個PUF 函數(shù)，c 是一個挑戰(zhàn)消息，那么F(c)就是PUF 函數(shù)的應答消息.

PPUF 是一種特殊的PUF，可以被模擬:假設D是PPUF 函數(shù)的描述，那么在已知D 的前提條件下，存在一個算法S 可以完全模擬PF 的輸出，也就是說，對任意的挑戰(zhàn)消息，均有S(D，c)= PF(c). 當然，在不知道D 的情況下，模擬PF 的輸出仍是一個非常困難的問題.PPUF 函數(shù)的屬性如下:

定義2(不可克隆性) 對任意一個多項式時間算法A 和一個隨機挑戰(zhàn)消息c，概率Pr［A(c)=F(c)］是可以忽略不計的.

定義3(不可預測性) 假設算法A 是一個多項式時間算法，算法A 首先以自適應的方式查詢PF:選擇挑戰(zhàn)消息c1，…，cn，并獲得它們對應的應答消息r1，…，rn;然后算法A 以自適應的方式選擇t個挑戰(zhàn)信息c'1，…，c't，接下來，隨機拋一個幣b，如果b=0 就選擇t個隨機的應答消息r'1，…，r't，如果b=1 則設置r'i=F(c'i)(i=1，…，t)，然后把r'1，…，r't交給算法A，最后算法A 輸出一個比特b'，稱PUF函數(shù)F 具有不可預測性如果算法A 成功的優(yōu)勢是可以忽略不計的.

3 RFID 隱私安全定義

本節(jié)將定義一種強RFID 隱私安全模型，稱之為SInd－privacy(Strong Indistinguishability based privacy)，具體定義如下:由于低成本的RFID 標簽不具有任何防篡改的能力，因此攻擊者可以很容易地通過破解標簽來獲得標簽的內部狀態(tài)，并利用獲得的內部狀態(tài)信息來攻擊標簽在被破解之前的通信隱私性(比如:跟蹤標簽、獲取標簽身份信息等). 因此，在本文的隱私安全模型中，允許攻擊者可以破解任意一個標簽，這給予攻擊者最強的攻擊能力.SInd－privacy 隱私由下面的隱私游戲(圖2)來定義:首先利用隱私游戲模擬現(xiàn)實的RFID 攻擊環(huán)境;然后利用對2個標簽行為的不可區(qū)分性定義隱私安全.隱私游包含一個攻擊者和一個RFID 系統(tǒng).

圖2 隱私安全游戲Figure 2 Privacy game

攻擊者:這里假設任何一個攻擊者都是一個概率多項式時間算法，它可以完全控制閱讀器和標簽之間的通信.此外，攻擊者A 還可以和協(xié)議參與方之間進行交互，這些交互用以下預言機來刻畫.

Launch(R):觸發(fā)閱讀器產(chǎn)生一個新的協(xié)議會話，輸出會話標識sid 和協(xié)議的第1 輪消息m1，它模擬搭線竊聽獲取協(xié)議第1 輪消息;

SendTag(sid，m1，Ti):模擬篡改協(xié)議消息和搭線竊聽協(xié)議的第2 輪消息m2;

SendReader(sid，m2):模擬篡改協(xié)議消息和搭線竊聽協(xié)議的第3 輪消息m3;

Reveal(Ti):模擬對標簽的破解攻擊，輸出標簽Ti的內部狀態(tài)包括其密鑰和狀態(tài)信息.

假設O1、O2、O3和O4分別表示以上4個預言機，本文假設攻擊者對這4個預言機的查詢次數(shù)總共不超過q 次.

SInd－privacy:通俗地講，在RFID 系統(tǒng)中盡管攻擊者可以對RFID 協(xié)議進行竊聽、篡改、阻斷，甚至可以破解標簽獲得其內部狀態(tài)，但攻擊者仍不能對2個標簽的行為加以區(qū)分，這就是SInd－privacy.實際上，RFID 隱私安全由隱私游戲(圖2)所定義，在該游戲中，攻擊者A 由算法A1和算法A2組成，攻擊者A 對RFID 系統(tǒng)的隱私攻擊分兩階段實施.在第一階段(也就是學習階段)，攻擊者A 初始化一個RFID 系統(tǒng)RS，并可以隨意調用預言機O1、O2、O3和O4，在這一階段末，算法A1輸出2個標簽T0、T1和狀態(tài)信息st，并把T0和T1遞交給游戲作為自己的候選挑戰(zhàn)標簽. 在第二階段(也就是挑戰(zhàn)階段)，游戲首先對T0和T1分別執(zhí)行一次完整的協(xié)議π，然后選擇一個隨機比特β，把Tβ交給攻擊者作為挑戰(zhàn)標簽，接下來攻擊者實施第二階段的攻擊.在這一階段，算法A2仍然可以對Tβ隨意調用預言機O1、O2、O3和O4進行查詢.

最后，要求攻擊者A 猜測游戲選擇的隨機拋幣β，假設A 的輸出是β'.如果β=β'則稱A 攻擊RFID系統(tǒng)的SInd－privacy 隱私安全性成功.

定義5(SInd－privacy) SInd－privacy 隱私安全性是指在以上的隱私游戲中不存在一個多項式時間攻擊者，其優(yōu)勢至少是ε(不可忽略不計)，且攻擊時間不超過t.或者稱RFID 系統(tǒng)RS 是(ε，t)－SInd－privacy 隱私安全的.

4 RPAP 協(xié)議

假設s 是一個比特串，L(s)表示s 的左半部分，R(s)表示s 的右半部分，PF 是一個PPUF 函數(shù)，其描述為D，S 為PF 的模擬算法，也就是說對任意的挑戰(zhàn)消息c 均有PF(c)=S(D，c)，w 是一個閥值，它表示任何一個標簽與閱讀器不同步的次數(shù)不能超過w 次. 在協(xié)議RPAP 中，系統(tǒng)為每一個標簽Ti配置一個PPUF 函數(shù)PFi和一個索引信息Ⅰi.閱讀器R為標簽Ti保存數(shù)據(jù)(Ⅰ'i，Ⅰi，Di，ⅠDi)在安全數(shù)據(jù)庫中，這里Ⅰ'i=R(S(Di，Ⅰi‖Ⅰi))，Di是關于PFi的描述，ⅠDi是標簽的身份信息. 協(xié)議RPAP 的詳細描述見圖3.

圖3 RPAP 協(xié)議Figure 3 RPAP protocol

第一輪:閱讀器發(fā)送隨機挑戰(zhàn)消息c 給標簽Ti.

第二輪:標簽收到挑戰(zhàn)消息c 之后，計算x =PFi(Ⅰi‖Ⅰi)和r1=PFi(c‖Ⅰi)并更新Ⅰi=L(x)，然后返回r=(r1，r2)給閱讀器，這里r2=R(x).

最后，當閱讀器收到消息r =(r1，r2)后，利用r2作為索引，在數(shù)據(jù)庫中檢索(Ⅰ'i，Di，ⅠDi)滿足r2=Ⅰ'i.如果找到，則判斷r1=S(Di，c‖Ⅰi)是否成立，如果成立就接受標簽Ti并更新Ⅰi=L(S(Di，Ⅰi‖Ⅰi))和Ⅰ'i=R(S(Di，Ⅰi‖Ⅰi))，如果不成立就拒絕標簽Ti;如果沒有找到，那么從1 到w 依次對數(shù)據(jù)庫中的每一個數(shù)據(jù)(Ⅰ'i，Ⅰi，Di，ⅠDi)先計算Ⅰi=L(S(Di，Ⅰi‖Ⅰi))，然后判斷r1=S(Di，c‖Ⅰi)是否成立，如果成立則接受標簽Ti并更新Ⅰi= L(S(Di，Ⅰi‖Ⅰi))和Ⅰ'i=R(S(Di，Ⅰi‖Ⅰi))，如果都不成立，則拒絕該標簽.

注:該二輪協(xié)議可以很方便地擴充為三輪協(xié)議從而實現(xiàn)對閱讀器的認證.在第三輪中，閱讀器發(fā)送f=S(Di，c‖L(r1))給標簽，標簽可以通過驗證f =PFi(c‖L(r1))是否成立來做出對閱讀器的認證.

5 隱私安全分析

本節(jié)討論協(xié)議RPAP 的隱私安全性，它由下面的定理所保證.

定理1 假設PPUF 函數(shù)具有不可克隆性和不可預測性且q ＜w，那么協(xié)議RPAP 具有SInd－privacy 隱私安全性.

證明 假設存在一個多項式時間攻擊者A 能夠以不可忽略不計的概率攻擊了協(xié)議RPAP 的SIind－privacy，那么我們就可以將攻擊者A 轉化為另一個攻擊算法B，它能以不可忽略不計的概率攻擊PPUF 函數(shù)的不可預測性.算法B 的構造如下:

假設算法B 要攻擊的PPUF 函數(shù)為PF'，它首先隨機拋一個幣b，然后設置標簽的內置PPUF 函數(shù)為PF'，設置Tb的初始狀態(tài)信息為Ⅰb，它再按照RPAP 協(xié)議的初始化方法設置另外一個標簽T1－b，然后它把Tb和T1－b交給攻擊者A 進行SInd－privacy 游戲.算法B 按如下方式回答攻擊者A 的查詢:

1)對于預言機O1的查詢，直接選擇一個隨機的挑戰(zhàn)消息c 給攻擊者A;

2)對于預言機O2的查詢，假設輸入?yún)?shù)為c，算法B 先以c‖Ⅰb查詢PPUF 函數(shù)PF'獲得~，再以Ⅰb‖Ⅰb查詢PPUF 函數(shù)PF'獲得，然后返回r =)給攻擊者A 并更新Ⅰb=L);

3)對于預言機O4的查詢，直接把Ⅰb返回給攻擊者A.

由于協(xié)議RPAP 只有2 輪消息，所以攻擊者沒有關于預言機O3的查詢.對于和標簽T1－b有關的查詢算法B 可以按RPAP 協(xié)議直接回答.

當攻擊者A 結束其第一階段的攻擊后，它把Tb和T1－b遞交給算法B，算法B 先結束對PF'的不可預測性的第一階段的攻擊，然后，發(fā)送測試消息Ⅰb‖Ⅰb給PPUF 的不可預測性游戲，用收到的應答消息r'1左半部分更新Ⅰb;最后把Tb交給攻擊者. 接下來攻擊者進行第二階段的攻擊，算法B 按以下方式回答攻擊者A 的查詢:對于預言機O2的每一次查詢(輸入?yún)?shù)為c)，算法B 發(fā)送測試消息c‖Ⅰb和Ⅰb‖Ⅰb給PPUF 的不可預測性游戲，假設其接收到的應答消息分別為r'i和r'i+1，算法B 返回(r'i，R(r'i+1))給攻擊者A，并更新Ⅰb=L(r'i+1);對于預言機O1和O4的查詢，算法B 按上面的方式進行回答.

最后，如果攻擊者A 輸出的比特是b'，算法B也輸出b'.

顯然，上面算法B 模擬的攻擊環(huán)境和攻擊者A的真實攻擊環(huán)境是不可區(qū)分的.且算法B 成功的優(yōu)勢至少是攻擊者A 成功的優(yōu)勢的一半.

6 結束語

低成本和隱私安全問題是阻礙RFID 技術大規(guī)模應用的2個主要因素，本文充分利用PPUF 函數(shù)的優(yōu)點，設計了超輕量級的RFID 認證協(xié)議PRAP，并證明了該協(xié)議具有SInd－privacy 隱私安全性.由于PPUF 函數(shù)可以由標簽內部電路直接構造，因此造價低.所以，協(xié)議PRAP 實現(xiàn)了低成本和高隱私安全的有機結合，為構造隱私安全的RFID 認證協(xié)議提供了新方法.

［1］JUELS A. RFID security and privacy:a research survey［J］. IEEE Journal on Selected Areas in Communications，2006，24(2):381－394.

［2］MA C，LI Y，DENG R，et al. RFID privacy:relation between two notions，minimal condition，and efficient construction［C］∥16th ACM Conference on Computer and Communications Security－ACM CCS’09.New York:ACM，2009:54－65.

［3］PAPPU R，RECHT B，TAYLOR J，et al. Physical oneway functions［J］. Science，2002，297(5589):2026－2030.

［4］BECKMANN N，POTKONJAK M. Hardware－ based public－ key cryptography with public physically unclonable functions［C］∥11th Conference on Information Hiding. Berlin:Springer－Verlag，2009:206－220.

［5］CHIEN H－Y，CHEN C－H. Mutual authentication protocol for RFID conforming to EPC Class 1 Generation 2 standards［J］. Computer Standars and Interfaces，Elsevier Science Publishers，2007，29(2):254－259.

［6］KONIDALA D，KIM Z，KIM K. A simple and cost－effective RFID tag－ reader mutual authentication scheme［C］∥RFID Security. Berlin:Springer－ Verlag，2007:141－152.

［7］PIETRO R D，MOLVA R. Information confinement，privacy，and security in RFID systems［C］∥12th European Symposium on Research in Computer Security－ ESORICS. Berlin:Springer－Verlag，2007:187－202.

［8］MOLNAR D，WAGNER D. Privacy and security in library RFID:issues，practices，and architectures［C］∥Computer and Communications Security－ACM CCS’04.New York:ACM，2004:210－219.

［9］OHKUBO M，SUZUKI K，KINOSHITA S. Cryptographic Approach to“Privacy－Friendly”Tags［C］∥RFID Privacy Workshop. IEEE，2003:624－654.

［10］DEURSEN T V，RADOMIROVI＇C S. Security of RFID protocols－ A case study［C］∥Proc 4th International Workshop on Security and Trust Management (STM'08). Trondheim，Norway，Elsevier，the Netherlands，2009:41－52.

［11］馬昌社. 前向隱私安全的低成本RFID 認證協(xié)議［J］. 計算機學報，2011，34(8):1387－1398.