基于物理不可克隆函數(shù)的高性能RFID網(wǎng)絡(luò)隱私保護(hù)算法

周恩輝，劉雅娜

(1.河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050024；2.石家莊學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050035)

基于物理不可克隆函數(shù)的高性能RFID網(wǎng)絡(luò)隱私保護(hù)算法

周恩輝1，劉雅娜2

(1.河北師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050024；2.石家莊學(xué)院 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 石家莊 050035)

RFID網(wǎng)絡(luò)是物聯(lián)網(wǎng)中物體身份識(shí)別的重要方案，RFID系統(tǒng)的安全性直接影響物聯(lián)網(wǎng)的安全性。已有的RFID隱私保護(hù)算法均需要線性地搜索后端的數(shù)據(jù)庫(kù)從而識(shí)別某個(gè)標(biāo)簽，因此后端數(shù)據(jù)庫(kù)的計(jì)算復(fù)雜度與延遲較高。對(duì)此基于物理不可克隆函數(shù)(PUF)提出一種無需數(shù)據(jù)庫(kù)搜索操作的低計(jì)算復(fù)雜度隱私保護(hù)算法。首先，采用PUF安全地保存標(biāo)簽的秘密信息以抵御妥協(xié)攻擊；然后，數(shù)據(jù)庫(kù)端僅需要3個(gè)哈希運(yùn)算與兩個(gè)異或運(yùn)算，計(jì)算復(fù)雜度為O(1)。最終，基于Vaudenay的RFID隱私安全模型分析本算法的性能，結(jié)果顯示其具有最高的隱私等級(jí)，同時(shí)計(jì)算復(fù)雜度最低。

RFID網(wǎng)絡(luò)；物聯(lián)網(wǎng)；隱私保護(hù)；物理不可克隆函數(shù)

0 引言

由于人們無法感知射頻信號(hào)的非法讀取，導(dǎo)致RFID技術(shù)存在特有的安全與隱私問題。在RFID系統(tǒng)的標(biāo)簽與閱讀器之間主要存在以下7種攻擊：假冒標(biāo)簽攻擊、假冒讀寫器攻擊、跟蹤標(biāo)簽攻擊、竊聽攻擊、中間件攻擊、重放攻擊、去同步攻擊。其中假冒讀寫攻擊、跟蹤標(biāo)簽攻擊、竊聽攻擊與中間件攻擊破壞標(biāo)簽的隱私性。因此保證RFID系統(tǒng)的隱私，需要滿足保密性、不可跟蹤性、前向安全與驗(yàn)證讀寫器 4種隱私保護(hù)需求[1]。一些研究使用樹結(jié)構(gòu)來保存秘鑰，以此降低搜索復(fù)雜度(O(n)-＞O(log n))，而此類方案易受妥協(xié)攻擊，因此，基于樹狀協(xié)議的隱私等級(jí)較低。

文獻(xiàn)[2]基于物理實(shí)體的內(nèi)在物理構(gòu)造來唯一地標(biāo)識(shí)單個(gè)物理實(shí)體實(shí)現(xiàn)有效認(rèn)證的思路，提出了 PUF(物理不可克隆函數(shù))，PUF具有魯棒性、不可克隆性以及不可預(yù)測(cè)性特點(diǎn)，目前廣泛應(yīng)用于RFID系統(tǒng)的認(rèn)證領(lǐng)域。文獻(xiàn)[3，4]均采用PUF(物理不可克隆函數(shù))來提高RFID的安全性，然而此類算法均為narrow-destructive隱私性[5]，其搜索復(fù)雜度最低為O(logN)。

本文提出一種基于PUF的RFID驗(yàn)證協(xié)議，本協(xié)議最大的優(yōu)勢(shì)是無需搜索數(shù)據(jù)庫(kù)(識(shí)別標(biāo)簽)，其搜索復(fù)雜度僅為O(1)，因此本協(xié)議可應(yīng)用于大規(guī)模 RFID網(wǎng)絡(luò)。本協(xié)議在標(biāo)簽與閱讀器端不需要多余的計(jì)算與通信開銷，并且本算法可抵御旁道攻擊。

1 背景知識(shí)介紹

假設(shè)標(biāo)簽為T，其 ID唯一，閱讀器為 R。RFID系統(tǒng)包含若干的閱讀器R、發(fā)送器以及一個(gè)后端數(shù)據(jù)庫(kù)，發(fā)送器與數(shù)據(jù)庫(kù)間有一個(gè)信道。

1.1 系統(tǒng)模型

RFID功能可表示為如下的函數(shù)形式：

(1)SetupReader(1S)→(KS，KP)：生成一個(gè)公共參數(shù) KP、一個(gè)隱私參數(shù)KS與一個(gè)閱讀器的安全參數(shù)s，同時(shí)生成一個(gè)數(shù)據(jù)庫(kù)(其中保存標(biāo)簽的ID)。

(2)SetupTagKP(ID)→(K，S)：生成一個(gè)標(biāo)簽(ID唯一)、一個(gè)秘鑰K與一個(gè)內(nèi)存狀態(tài)S。如果該標(biāo)簽合法，則將ID與K保存于數(shù)據(jù)庫(kù)中。

(3)IdentTag→out：該函數(shù)表示標(biāo)簽T與閱讀器R之間的一次交互。如果閱讀器最終識(shí)別出該標(biāo)簽，則輸出標(biāo)簽的ID，否則輸出“?”。

1.2 攻擊模型

假設(shè)攻擊者A具備以下性質(zhì)：首先，攻擊者C執(zhí)行SetupReader(1S)程序，生成 1S、KS與 KP3個(gè)參數(shù)，并將1S、KP傳至 A；然后 A使用 CreateTagb(ID)生成標(biāo)簽，本模型按標(biāo)簽是否在攻擊者的閱讀范圍內(nèi)將標(biāo)簽分類：如果在閱讀范圍內(nèi)分類，則為危險(xiǎn)標(biāo)簽(DanTag)，否則為安全標(biāo)簽(SecTag)。

為攻擊者定義以下10個(gè)行為或攻擊能力：

(1)CreateTagb(ID)：創(chuàng)建一個(gè) SecTag并為其分配一個(gè)ID。該函數(shù)使用 SetupTagKP(ID)創(chuàng)建標(biāo)簽，如果該標(biāo)簽合法(b=1)，則將其加入數(shù)據(jù)庫(kù)中。

(2)DanTag(distr，n)→(vtag0，b0，…，vtagn-1，bn-1)：從SecTag標(biāo)簽集中隨機(jī)地選擇n個(gè)標(biāo)簽，并將標(biāo)簽狀態(tài)從 SecTag變?yōu)镈antag。為選擇的標(biāo)簽分配一個(gè)新的 ID并輸出虛擬標(biāo)簽(vtag0，…，vtagn-1)，如果該標(biāo)簽已經(jīng)為 Dantag或已不存在，則輸出“？”。

(3)Free(vtag)：將標(biāo)簽狀態(tài)從DanTag變?yōu)镾ecTag。

(4)Launch()→π：觸發(fā)閱讀器開始新的協(xié)議循環(huán)，輸出為該輪協(xié)議的IDπ(為每輪協(xié)議設(shè)置一個(gè)標(biāo)識(shí)ID)。

(5)SendReader(m，π)→m′：發(fā)送一個(gè)消息m至閱讀器R(在協(xié)議循環(huán)π中)，閱讀器的回復(fù)消息為m′。

(6)SendTag(m,vtag)→m′：發(fā)送一個(gè)消息 m至標(biāo)簽，其虛擬ID為vtag。閱讀器的回復(fù)消息為m′。

(7)Execute(vtag)→(π，transcript)：在標(biāo)簽(該標(biāo)簽虛擬ID為vtag)與閱讀器之間執(zhí)行完整的協(xié)議。該協(xié)議由Lauch()開始，然后是SendReader與 SendTag，輸出協(xié)議循環(huán) π的成功消息列表。

(8)Result(π)→x：如果閱讀器成功識(shí)別一個(gè)合法的標(biāo)簽，則返回 1；否則返回 0。

(9)Time(π)→δ：返回閱讀器的總計(jì)算時(shí)間δ。

(10)Corrupt(vtag)→S：獲得標(biāo)簽(虛擬ID為 vtag)的當(dāng)前狀態(tài)S。

1.3 隱私分類

攻擊者分為強(qiáng)(strong)、破壞性(destructive)、前向(forward)、弱(weak)攻擊者，此外與這 4類攻擊者正交的還有wide與narrow兩個(gè)攻擊者的概念，wide攻擊者可通過閱讀器訪問認(rèn)證結(jié)果，但 narrow攻擊不行。圖1描述了6種攻擊概念之間的關(guān)系[5]。

圖1 6種隱私概念之間的關(guān)系

1.4 安全性級(jí)別

定義1正確性：如果在IdentTag程序之后 R返回標(biāo)簽ID的成功率極高，則認(rèn)為該協(xié)議符合正確性。

定義2強(qiáng)正確性：如果在R與合法標(biāo)簽T交互之后返回標(biāo)簽ID的成功率極高，則認(rèn)為符合強(qiáng)正確性。

定義3穩(wěn)固性[5]：如果對(duì)合法標(biāo)簽 T假冒攻擊的成功率極低，則認(rèn)為符合穩(wěn)固性。

1.5 隱私性

定義4盲攻擊：假設(shè)B表示一個(gè)算法，仿真了Lauch()、SendReader(m，π)、SendTag(m，vtag)與 Result(π)4個(gè)程序的串行組合(對(duì)于攻擊者A)，并且不知道任何的秘密信息。一個(gè)盲攻擊者(AB)不使用Lauch()、SendReader(m，π)、SendTag(m，vtag)與Result(π)程序，如果存在B，則攻擊者A威脅極小，即|Pr[Awins]-Pr[ABwins]|可忽略不計(jì)。

2 本文大規(guī)模RFID網(wǎng)絡(luò)安全協(xié)議

定義 5 Hash函數(shù)：假設(shè) l∈N是一個(gè)安全參數(shù)，γ，K∈N是 l中的項(xiàng)，則 hash函數(shù) H可定義為{0，1}γ→{0，1}K，其條件為：

(1)對(duì)于一個(gè)給定的輸出 yi，無法反向計(jì)算出滿足H(xi)=yi的 xi。

(2)計(jì)算出滿足條件 xi≠xj&&H(xi)=H(xj)的參數(shù)組合(xi，xj)難度極高。

定義 6物理不可克隆函數(shù)(PUF)[6]：假設(shè) l∈N是安全參數(shù)，γ，K∈N是l的項(xiàng)。理想的PUF(設(shè)為P)定義為{0，1}γ→{0，1}K，其條件如下：

(1)對(duì)于參數(shù)對(duì)(ci，cj)∈{0，1}γ，P(ci)=ri，P(cj)=rj。如果 ci=cj，則概率Pr[ri=rj]=1。

(2)攻擊者無法在有限次數(shù)內(nèi)計(jì)算出P的輸出。

表1所示是本文預(yù)設(shè)參數(shù)及其意義。

本文協(xié)議主要有兩個(gè)階段：初始化與驗(yàn)證階段，圖2所示是本文RFID隱私保護(hù)協(xié)議的主要流程。

2.1 初始化階段

為數(shù)據(jù)庫(kù)隨機(jī)生成秘鑰S，為每個(gè)標(biāo)簽生成兩個(gè)隨機(jī)且唯一的秘鑰a與b。然后，為每個(gè)標(biāo)簽計(jì)算其秘鑰c=S⊕P(a)⊕P(b)，其中P(·)是各標(biāo)簽的嵌入 PUF。數(shù)據(jù)庫(kù)保存每個(gè)標(biāo)簽的基本信息{ID，a，b，DATA}。

2.2 驗(yàn)證階段

(1)每個(gè)閱讀器生成一個(gè)隨機(jī)數(shù) r1∈{0，1}l并廣播該隨機(jī)數(shù)。

(2)標(biāo)簽Ti生成一個(gè)隨機(jī)數(shù)r2∈{0，1}l，計(jì)算M1←H(r1，r2，ai)，M2←H(r1，r2，ai)⊕IDi，h←H(r2，1，2)。然后，將Pi(ai)與 r2做異或運(yùn)算，計(jì)算出消息 k。使用 k⊕Pi(bi)⊕ci代替消息k，從內(nèi)存中刪除 Pi(bi)。標(biāo)簽將 M1、M2、k發(fā)送至閱讀器。

(3)閱讀器生成一個(gè)隨機(jī)數(shù) r3∈{0，1}l。計(jì)算←S⊕k與←M2⊕H(，r1，1)。閱讀器通過計(jì)算 H(r1，，ai)驗(yàn)證M1以實(shí)現(xiàn)標(biāo)簽Ti的驗(yàn)證。如果成功驗(yàn)證標(biāo)簽Ti，閱讀器則計(jì)算 M3=H(H(，1，2)，r3，bi)，然后將 r3與 M3發(fā)送回標(biāo)簽Ti。

(4)標(biāo)簽 Ti通過計(jì)算 H(h，r3，bi)驗(yàn)證 M3。如果驗(yàn)證成功，則Ti成功驗(yàn)證閱讀器。

表1 本文的參數(shù)定義

圖2 本文協(xié)議主要流程

3 本文協(xié)議的性能分析

3.1 安全性分析

本文協(xié)議理論上可抵御假冒攻擊，下文將證明本方法對(duì)假冒攻擊具有安全性。因?yàn)楸疚膮f(xié)議是無狀態(tài)協(xié)議，并且標(biāo)簽無需與數(shù)據(jù)庫(kù)保持同步，因此，去同步攻擊對(duì)本協(xié)議也無效。

引理1：假設(shè)A是一個(gè)destructive級(jí)別的攻擊者。A的特點(diǎn)是在不執(zhí)行Corrupt程序的情況下，獲得共享秘鑰的成功率極低。

證明：假設(shè)有一個(gè)攻擊者A可學(xué)習(xí)共享秘鑰(不執(zhí)行Corrupt程序)。每個(gè)標(biāo)簽響應(yīng)閱讀器的查詢語(yǔ)句(M1，M2，k)，其中k=S⊕r2，r2是標(biāo)簽產(chǎn)生的隨機(jī)值。為了獲得共享秘鑰S，A需要知道隨機(jī)數(shù)r2，然而，r2并沒有隨密文發(fā)送，A必須從消息M1、M2與M3中破解出 r2。此外，將標(biāo)簽ID IDi以密文形式H(r2，r1，1)⊕IDi發(fā)送至閱讀器，在不知道隨機(jī)值的情況下A無法破解出IDi。

3.2 計(jì)算效率與隱私性實(shí)驗(yàn)與分析

在此分析標(biāo)簽端與數(shù)據(jù)庫(kù)端的性能。本協(xié)議中，一個(gè)標(biāo)簽共需完成4個(gè)hash運(yùn)算、兩個(gè)PUF運(yùn)算與4個(gè)XOR運(yùn)算，數(shù)據(jù)庫(kù)端則需要完成一個(gè)標(biāo)簽驗(yàn)證程序，該驗(yàn)證需要3個(gè)hash運(yùn)算與兩個(gè)XOR運(yùn)算，其復(fù)雜度為O(1)。本協(xié)議在標(biāo)簽端與數(shù)據(jù)庫(kù)端均無需秘鑰更新機(jī)制。

表2所示是本文方法與其他RFID隱私保護(hù)算法的計(jì)算效率與隱私性比較，其中，成本 1：共 2128個(gè)標(biāo)簽的RFID網(wǎng)絡(luò)；成本 2：共 216個(gè)標(biāo)簽的 RFID網(wǎng)絡(luò)；成本 3：共N個(gè)標(biāo)簽的RFID網(wǎng)絡(luò)；nonce：生成隨機(jī)數(shù)操作；hash：哈希運(yùn)算；PUF：PUF運(yùn)算。從中可看出，本方法具有最高的隱私等級(jí)，并且其數(shù)據(jù)庫(kù)端的計(jì)算復(fù)雜度較低。

表2 各協(xié)議性能比較

4 結(jié)論

PUF具有魯棒性、不可克隆性以及不可預(yù)測(cè)性特點(diǎn)，本文提出一種基于 PUF的RFID驗(yàn)證協(xié)議，本協(xié)議最大的優(yōu)勢(shì)是無需搜索數(shù)據(jù)庫(kù)(識(shí)別標(biāo)簽)，其搜索復(fù)雜度僅為O(1)，因此本協(xié)議可應(yīng)用于大規(guī)模 RFID網(wǎng)絡(luò)。與其他RFID隱私保護(hù)算法的比較結(jié)果顯示，本方法具有最高的隱私等級(jí)，并且其數(shù)據(jù)庫(kù)端的計(jì)算復(fù)雜度較低。參考文獻(xiàn)

[1]王良民，茅冬梅，梁軍.基于RFID系統(tǒng)的隱私保護(hù)技術(shù)[J].江蘇大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，33(6)：690-695.

[2]PAPPU R.Physical one-way functions[J].Science，2002，297 (5589)：2026-2030.

[3]AKGUN M，CAGLAYAN M U.PUF based scalable private RFID authentication[C].Availability，Reliability and Security (ARES)，2011 Sixth International Conference on.IEEE，2011：473-478.

[4]KARDAS S，KIRAZ M S，BING?L M A，et al.A novel RFID distance bounding protocol based on physically unclonable functions[C].Lecture Notes in Computer Science，2011：78-93.

[5]VAUDENAY S.On privacy models for RFID[M].Advances in Cryptology-ASIACRYPT 2007.Springer Berlin Heidelberg，2007：68-87.

[6]SADEGHI A R，VISCONTI I，WACHSMANN C.Pufenhanced rfid security and privacy[J].2nd Workshop on Secure Component and System Identification(SECSI′10)，2010，24(3)：381-394.

[7]MOLNAR D，WAGNER D.Privacy and security in library RFID：issues，practices，and architectures[C].Acm Conference on Computer&Communications Security，2004：210-219.

[8]BRINGER J，CHABANNE H，ICART T.Improved privacy of the tree-based hash protocols using physically unclonable function[J].Lecture Notes in Computer Science，2007：77-91.

[9]AVOINE G，DYSLI E，OECHSLIN P.Reducing time complexity in RFID systems[C].Lecture Notes in Computer Science，2005，3897：291-306.

[10]ALOMAIR B，CLARK A，CUELLAR J，et al.Scalable RFID systems：a privacy-preserving protocol with constant-time identification[J].Parallel&Distributed Systems IEEE Transactions on，2011，23(8)：1536-1550.

[11]AKGUN M，CAGLAYAN M U.PUF based scalable private RFID authentication[C].Availability，Reliability and Security (ARES)，2011 Sixth International Conference on.IEEE，2011：473-478.

[13]ASADPOUR M，DASHTI M T.Scalable，privacy preserving radio-frequency identification protocol for the internet of things[J].Concurrency and Computation：Practice and Experience，2013，27(8)：1932-1950.

Physically unclonable function based high performance privacy protection algorithm of RFID network

Zhou Enhui1，Liu Yana2
(1.College of Mathematics and Information Science，Hebei Normal University，Shijiazhuang 050024，China；2.College of Mathematics and Information Science，Shijiazhuang University，Shijiazhuang 050035，China)

RFID network is an important solution for the identification of Internet of Things,the security of RFID system impacts the security of the Internet of Things directly.The existing RFID privacy protection algorithms need to search the backend database to validate a tag,so that the database has a high computational complexity and delay.Thus a physical unclonable function based low computational complexity privacy protection algorithm which does not need searching the database is proposed.Firstly,PUF is used to store the secret information of the tags securely to resist the compromising attack.Then,three hash function and two XOR computation are needed for database and it′s computational complexity is O(1).Lastly,the proposed algorithm is analyzed based on the RFID privacy and security model proposed by Vaudenay.The results show that the proposal realize the best privacy level and the lowest computational complexity.

RFID network；Internet of Things；privacy protection；physical unclonable function

TP29

A

10.16157/j.issn.0258-7998.2016.03.028

周恩輝，劉雅娜.基于物理不可克隆函數(shù)的高性能 RFID網(wǎng)絡(luò)隱私保護(hù)算法[J].電子技術(shù)應(yīng)用，2016，42 (3)：98-101.

英文引用格式：Zhou Enhui，Liu Yana.Physically unclonable function based high performance privacy protection algorithm of RFID network[J].Application of Electronic Technique，2016，42(3)：98-101.

2015-11-18)

周恩輝（1973-），男，碩士，實(shí)驗(yàn)師，主要研究方向：計(jì)算機(jī)圖形圖像處理，多媒體技術(shù)，計(jì)算機(jī)網(wǎng)絡(luò)等。

劉雅娜（1973-），通信作者，女，碩士，講師，主要研究方向：技術(shù)經(jīng)濟(jì)，運(yùn)籌學(xué)，E-mail：liuya_na@163.com。