基于PPUF的高效RFID隐私认证协议

向学哲，马昌社

(华南师范大学计算机学院，广东广州510631)

RFID(Radio Frequency IDentification)技术［1］是物联网的底层关键支撑技术之一，对物联网的发展起着举足轻重的作用.如今，安全和成本问题已成为制约物联网发展的2个主要因素. 能否以较低的代价来获取较高的隐私安全性是大规模物联网应用的前提条件，对于RFID 技术更是如此，因此，工业界和学术界进行了相关研究，主要集中在使用轻量级的密码技术来实现RFID 隐私保护.文献［2］论证了保证RFID 隐私性的必要条件是标签能够计算伪随机函数，而具有密码学意义上安全的伪随机函数的计算开销巨大，不适合RFID 这种资源受限环境.因此，从某种意义上来说，纯粹从密码技术出发难以设计出具有可证明安全的RFID 隐私保护技术. 幸运的是，微电子技术的发展为RFID 隐私保护技术的设计提供了崭新的设计工具:物理不可克隆函数(PUF:Physically Unclonable Function)［3］可以用来以几乎零成本的方式获得RFID 隐私认证协议. 简单地说，PUF 是一种基于消息挑战应答模式的物理装置，它是物理系统的物理指纹.PUF 依据物理系统的内在属性和物理系统自身体系结构而设计，所以其生产成本非常低，它的物理不可克隆性被用来设计防止边信道攻击的安全方案.

一个RFID 应用系统一般由标签、阅读器和后端数据库组成:每一个标签具有全球唯一的电子编码，并附着在物体上以标识该物体;阅读器负责激活被动式标签并利用后端数据库结合标签的应答信息完成对标签的识别或认证.尽管PUF 函数可以减轻RFID 标签端的复杂性，但是其不可克隆性却增加了阅读器端对其进行识别的复杂性.目前PUF 有2 种应用方法:其一是直接用标签内置的PUF 的应答来对标签进行认证;其二是在标签端把PUF 当作一个密钥存储器使用，再加上一个密码认证函数来实现对标签的认证.在前一种方法中，阅读器端为了实现对标签的认证，需要事先存储多个挑战应答对，每次认证标签时，选择一个挑战消息发送给标签，然后把标签的应答消息和存储的应答消息进行比对后做出对标签的认证.显然，为了保证隐私性，阅读器端需要对每一个标签存储足够的挑战应答对，因此严重地增加了阅读器的存储负担，而且不能保证隐私性，因为标签对同一个挑战消息的应答是一样的. 后一种方法仅仅增加了标签中秘密信息的存储安全，其认证性和隐私性完全依赖于标签中的密码认证函数，因此没有体现出PUF 的优越性，不会有解决标签低成本问题.

PPUF(Public Physically Unclonable Function)［4］是一种特殊的PUF，在知道其描述的条件下，可以模拟其输出.本文从PPUF 出发，围绕PPUF 的优越性，设计了一个高效且低成本的RFID 认证协议RPAP(RFID Privacy－preserving Authentication Protocol).在效率方面，协议RPAP 中的标签只需要配置一个PPUF 而不需要其他的计算能力，同时阅读器端可以在常数时间内完成对标签的识别. 由于PPUF 可以依据标签内部的存储电路来实现，因此，RPAP 协议简单、高效且标签生产成本低. 在隐私安全性方面，协议RPAP 可以抵抗破解攻击等各种强隐私攻击，本文证明了其具有SInd－privacy 隐私安全性.总之，RPAP 协议充分利用PUF 的优点，做到了低成本和隐私安全的结合，为RFID 技术大规模应用提供了技术支撑.

1 RFID 隐私认证技术相关研究

目前，业界提出了若干RFID 隐私安全解决方案和协议，但是都存在问题:要么不具有安全性，要么生成成本高.

在轻量级RFID 协议设计方面，采用简单操作(比如:比特异或、比特内积、16 比特的随机数发生器等)，文献［5］和文献［6］分别设计了简单的RFID双向认证协议.然而，这2个协议都容易遭到隐私攻击［7］.采用对称密码技术，文献［8］首次提出了一个基于树的RFID 认证系统，不能抵抗主动攻击.实际上，在基于树的RFID 系统中，所有标签之间需要或多或少的共享某些秘密信息，读取某一标签的内部状态后，可以利用它攻击其他标签的隐私性.因此基于树的RFID 系统都不能抵抗主动跟踪攻击.

基于哈希函数，文献［9］设计了一个简单安全的RFID 系统(简称OSK 协议)，该系统的可扩展性很差，因为阅读器端识别标签所需要的计算量与RFID 系统中标签的数目成线性关系.这制约了OSK不能用于标签数目比较大的应用场合. 后来的研究者们采用状态同步并结合哈希链提出了各种各样的RFID 协议［10］，这些协议中大部分仍不具有安全性［10］.因此，设计低成本且隐私安全的RFID 协议仍是研究者们主要工作所在.

2 预备知识

定义1 称函数ε:{0，1}n→R 是可以忽略不计的，如果它满足:对任意一个多项式p(n)，当n 充分大时有:ε(n)＜1/p(n).

2.1 RFID 系统

假设RFID 系统［11］中共有n个标签，它们是T={T1，…，Tn}，只有一个阅读器R 和一个后端数据库系统DB.每一个标签由一个唯一的ID 所标识，阅读器有一个或者多个射频收发器，后端数据库系统DB维护认证标签所需要的所有数据，比如标签的密钥、ID、状态信息等.这里假设阅读器和后端数据库之间的通信是安全的，并且后端数据库属于安全数据库.

图1 RFID 认证协议Figure 1 RFID authentication protocol

由于现有大部分RFID 协议只有2 轮或者3 轮通信，因此本文仅考虑不超过三轮通信的RFID 协议(图1).这里sT是标签中存储的状态信息(包含标签的密钥)，l1、l2和l3分别表示协议第1 轮、第2轮和第3 轮消息的比特长度. 当标签收到协议的挑战消息m1{0，1}l1之后，它返回1个应答消息m2{0，1}l2，然后阅读器返回协议第3 轮消息m3给标签.此外，一个RFID 系统RS ={T，R，DB}还包含协议π(R，Ti):调用R 和Ti执行一次完整的认证协议(图1)，返回协议消息(m1，m2，m3).

2.2 PPUF 及其属性

由于生产制造过程中各种因素之间的差异性导致了实现同一功能的2个物理系统在内部物理结构上存在差异性，这就是物理系统的指纹，而PUF 恰是这一指纹的表现.比如:在大规模集成电路的生成过程中，由于硅精格的多样性以及化工机械打磨过程中的非均匀性，导致了每一个电路门具有不同的物理特性，即使在45 纳米技术中，同一个门在不同的集成电路中的时延是不一样的，利用这种时延的不一致性，就可以构造一个PUF 函数. 而制造过程中工艺的复杂性和偏差的随机性使得这样的PUF 具有一种良好的属性也就是物理不可克隆性.简单地说，PUF 就是一种基于物理结构的挑战应答系统.假设F 是一个PUF 函数，c 是一个挑战消息，那么F(c)就是PUF 函数的应答消息.

PPUF 是一种特殊的PUF，可以被模拟:假设D是PPUF 函数的描述，那么在已知D 的前提条件下，存在一个算法S 可以完全模拟PF 的输出，也就是说，对任意的挑战消息，均有S(D，c)= PF(c). 当然，在不知道D 的情况下，模拟PF 的输出仍是一个非常困难的问题.PPUF 函数的属性如下:

定义2(不可克隆性) 对任意一个多项式时间算法A 和一个随机挑战消息c，概率Pr［A(c)=F(c)］是可以忽略不计的.

定义3(不可预测性) 假设算法A 是一个多项式时间算法，算法A 首先以自适应的方式查询PF:选择挑战消息c1，…，cn，并获得它们对应的应答消息r1，…，rn;然后算法A 以自适应的方式选择t个挑战信息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函数F 具有不可预测性如果算法A 成功的优势是可以忽略不计的.

3 RFID 隐私安全定义

本节将定义一种强RFID 隐私安全模型，称之为SInd－privacy(Strong Indistinguishability based privacy)，具体定义如下:由于低成本的RFID 标签不具有任何防篡改的能力，因此攻击者可以很容易地通过破解标签来获得标签的内部状态，并利用获得的内部状态信息来攻击标签在被破解之前的通信隐私性(比如:跟踪标签、获取标签身份信息等). 因此，在本文的隐私安全模型中，允许攻击者可以破解任意一个标签，这给予攻击者最强的攻击能力.SInd－privacy 隐私由下面的隐私游戏(图2)来定义:首先利用隐私游戏模拟现实的RFID 攻击环境;然后利用对2个标签行为的不可区分性定义隐私安全.隐私游包含一个攻击者和一个RFID 系统.

图2 隐私安全游戏Figure 2 Privacy game

攻击者:这里假设任何一个攻击者都是一个概率多项式时间算法，它可以完全控制阅读器和标签之间的通信.此外，攻击者A 还可以和协议参与方之间进行交互，这些交互用以下预言机来刻画.

Launch(R):触发阅读器产生一个新的协议会话，输出会话标识sid 和协议的第1 轮消息m1，它模拟搭线窃听获取协议第1 轮消息;

SendTag(sid，m1，Ti):模拟篡改协议消息和搭线窃听协议的第2 轮消息m2;

SendReader(sid，m2):模拟篡改协议消息和搭线窃听协议的第3 轮消息m3;

Reveal(Ti):模拟对标签的破解攻击，输出标签Ti的内部状态包括其密钥和状态信息.

假设O1、O2、O3和O4分别表示以上4个预言机，本文假设攻击者对这4个预言机的查询次数总共不超过q 次.

SInd－privacy:通俗地讲，在RFID 系统中尽管攻击者可以对RFID 协议进行窃听、篡改、阻断，甚至可以破解标签获得其内部状态，但攻击者仍不能对2个标签的行为加以区分，这就是SInd－privacy.实际上，RFID 隐私安全由隐私游戏(图2)所定义，在该游戏中，攻击者A 由算法A1和算法A2组成，攻击者A 对RFID 系统的隐私攻击分两阶段实施.在第一阶段(也就是学习阶段)，攻击者A 初始化一个RFID 系统RS，并可以随意调用预言机O1、O2、O3和O4，在这一阶段末，算法A1输出2个标签T0、T1和状态信息st，并把T0和T1递交给游戏作为自己的候选挑战标签. 在第二阶段(也就是挑战阶段)，游戏首先对T0和T1分别执行一次完整的协议π，然后选择一个随机比特β，把Tβ交给攻击者作为挑战标签，接下来攻击者实施第二阶段的攻击.在这一阶段，算法A2仍然可以对Tβ随意调用预言机O1、O2、O3和O4进行查询.

最后，要求攻击者A 猜测游戏选择的随机抛币β，假设A 的输出是β'.如果β=β'则称A 攻击RFID系统的SInd－privacy 隐私安全性成功.

定义5(SInd－privacy) SInd－privacy 隐私安全性是指在以上的隐私游戏中不存在一个多项式时间攻击者，其优势至少是ε(不可忽略不计)，且攻击时间不超过t.或者称RFID 系统RS 是(ε，t)－SInd－privacy 隐私安全的.

4 RPAP 协议

假设s 是一个比特串，L(s)表示s 的左半部分，R(s)表示s 的右半部分，PF 是一个PPUF 函数，其描述为D，S 为PF 的模拟算法，也就是说对任意的挑战消息c 均有PF(c)=S(D，c)，w 是一个阀值，它表示任何一个标签与阅读器不同步的次数不能超过w 次. 在协议RPAP 中，系统为每一个标签Ti配置一个PPUF 函数PFi和一个索引信息Ⅰi.阅读器R为标签Ti保存数据(Ⅰ'i，Ⅰi，Di，ⅠDi)在安全数据库中，这里Ⅰ'i=R(S(Di，Ⅰi‖Ⅰi))，Di是关于PFi的描述，ⅠDi是标签的身份信息. 协议RPAP 的详细描述见图3.

图3 RPAP 协议Figure 3 RPAP protocol

第一轮:阅读器发送随机挑战消息c 给标签Ti.

第二轮:标签收到挑战消息c 之后，计算x =PFi(Ⅰi‖Ⅰi)和r1=PFi(c‖Ⅰi)并更新Ⅰi=L(x)，然后返回r=(r1，r2)给阅读器，这里r2=R(x).

最后，当阅读器收到消息r =(r1，r2)后，利用r2作为索引，在数据库中检索(Ⅰ'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 依次对数据库中的每一个数据(Ⅰ'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))，如果都不成立，则拒绝该标签.

注:该二轮协议可以很方便地扩充为三轮协议从而实现对阅读器的认证.在第三轮中，阅读器发送f=S(Di，c‖L(r1))给标签，标签可以通过验证f =PFi(c‖L(r1))是否成立来做出对阅读器的认证.

5 隐私安全分析

本节讨论协议RPAP 的隐私安全性，它由下面的定理所保证.

定理1 假设PPUF 函数具有不可克隆性和不可预测性且q ＜w，那么协议RPAP 具有SInd－privacy 隐私安全性.

证明 假设存在一个多项式时间攻击者A 能够以不可忽略不计的概率攻击了协议RPAP 的SIind－privacy，那么我们就可以将攻击者A 转化为另一个攻击算法B，它能以不可忽略不计的概率攻击PPUF 函数的不可预测性.算法B 的构造如下:

假设算法B 要攻击的PPUF 函数为PF'，它首先随机抛一个币b，然后设置标签的内置PPUF 函数为PF'，设置Tb的初始状态信息为Ⅰb，它再按照RPAP 协议的初始化方法设置另外一个标签T1－b，然后它把Tb和T1－b交给攻击者A 进行SInd－privacy 游戏.算法B 按如下方式回答攻击者A 的查询:

1)对于预言机O1的查询，直接选择一个随机的挑战消息c 给攻击者A;

2)对于预言机O2的查询，假设输入参数为c，算法B 先以c‖Ⅰb查询PPUF 函数PF'获得~，再以Ⅰb‖Ⅰb查询PPUF 函数PF'获得，然后返回r =)给攻击者A 并更新Ⅰb=L);

3)对于预言机O4的查询，直接把Ⅰb返回给攻击者A.

由于协议RPAP 只有2 轮消息，所以攻击者没有关于预言机O3的查询.对于和标签T1－b有关的查询算法B 可以按RPAP 协议直接回答.

当攻击者A 结束其第一阶段的攻击后，它把Tb和T1－b递交给算法B，算法B 先结束对PF'的不可预测性的第一阶段的攻击，然后，发送测试消息Ⅰb‖Ⅰb给PPUF 的不可预测性游戏，用收到的应答消息r'1左半部分更新Ⅰb;最后把Tb交给攻击者. 接下来攻击者进行第二阶段的攻击，算法B 按以下方式回答攻击者A 的查询:对于预言机O2的每一次查询(输入参数为c)，算法B 发送测试消息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 模拟的攻击环境和攻击者A的真实攻击环境是不可区分的.且算法B 成功的优势至少是攻击者A 成功的优势的一半.

6 结束语

低成本和隐私安全问题是阻碍RFID 技术大规模应用的2个主要因素，本文充分利用PPUF 函数的优点，设计了超轻量级的RFID 认证协议PRAP，并证明了该协议具有SInd－privacy 隐私安全性.由于PPUF 函数可以由标签内部电路直接构造，因此造价低.所以，协议PRAP 实现了低成本和高隐私安全的有机结合，为构造隐私安全的RFID 认证协议提供了新方法.

［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 认证协议［J］. 计算机学报，2011，34(8):1387－1398.