基于物理不可克隆函数的高性能RFID网络隐私保护算法

　　0 引言

　　由于人们无法感知射频信号的非法读取，导致RFID技术存在特有的安全与隐私问题。在RFID系统的标签与阅读器之间主要存在以下7种攻击：假冒标签攻击、假冒读写器攻击、跟踪标签攻击、窃听攻击、中间件攻击、重放攻击、去同步攻击。其中假冒读写攻击、跟踪标签攻击、窃听攻击与中间件攻击破坏标签的隐私性。因此保证RFID系统的隐私，需要满足保密性、不可跟踪性、前向安全与验证读写器4种隐私保护需求[1]。一些研究使用树结构来保存秘钥，以此降低搜索复杂度(O(n)->O(log n))，而此类方案易受妥协攻击，因此，基于树状协议的隐私等级较低。

　　文献[2]基于物理实体的内在物理构造来唯一地标识单个物理实体实现有效认证的思路，提出了PUF(物理不可克隆函数)，PUF具有鲁棒性、不可克隆性以及不可预测性特点，目前广泛应用于RFID系统的认证领域。文献[3，4]均采用PUF(物理不可克隆函数)来提高RFID的安全性，然而此类算法均为narrow-destructive隐私性[5]，其搜索复杂度最低为O(logN)。

　　本文提出一种基于PUF的RFID验证协议，本协议最大的优势是无需搜索数据库(识别标签)，其搜索复杂度仅为O(1)，因此本协议可应用于大规模RFID网络。本协议在标签与阅读器端不需要多余的计算与通信开销，并且本算法可抵御旁道攻击。

　　1 背景知识介绍

　　假设标签为T，其ID唯一，阅读器为R。RFID系统包含若干的阅读器R、发送器以及一个后端数据库，发送器与数据库间有一个信道。

　　1.1 系统模型

　　RFID功能可表示为如下的函数形式：

　　(1)SetupReader(1S)→(KS，KP)：生成一个公共参数KP、一个隐私参数KS与一个阅读器的安全参数s，同时生成一个数据库(其中保存标签的ID)。

(2)

生成一个标签(ID唯一)、一个秘钥K与一个内存状态S。如果该标签合法，则将ID与K保存于数据库中。

　　(3)IdentTag→out：该函数表示标签T与阅读器R之间的一次交互。如果阅读器最终识别出该标签，则输出标签的ID，否则输出“?”。

　　1.2 攻击模型

　　假设攻击者A具备以下性质：首先，攻击者C执行SetupReader(1S)程序，生成1S、KS与KP 3个参数，并将1S、KP传至A;然后A使用CreateTagb(ID)生成标签，本模型按标签是否在攻击者的阅读范围内将标签分类：如果在阅读范围内分类，则为危险标签(DanTag)，否则为安全标签(SecTag)。

　　为攻击者定义以下10个行为或攻击能力：

　　(1)CreateTagb(ID)：创建一个SecTag并为其分配一个ID。该函数使用创建标签，如果该标签合法(b=1)，则将其加入数据库中。

　　(2)DanTag(distr，n)→(vtag0，b0，…，vtagn-1，bn-1)：从SecTag标签集中随机地选择n个标签，并将标签状态从SecTag变为Dantag。为选择的标签分配一个新的ID并输出虚拟标签(vtag0，…，vtagn-1)，如果该标签已经为Dantag或已不存在，则输出“?”。

　　(3)Free(vtag)：将标签状态从DanTag变为SecTag。

　　(4)Launch()→π：触发阅读器开始新的协议循环，输出为该轮协议的IDπ(为每轮协议设置一个标识ID)。

　　(5)SendReader(m，π)→m′：发送一个消息m至阅读器R(在协议循环π中)，阅读器的回复消息为m′。

　　(6)SendTag(m, vtag)→m′：发送一个消息m至标签，其虚拟ID为vtag。阅读器的回复消息为m′。

　　(7)Execute(vtag)→(π，transcript)：在标签(该标签虚拟ID为vtag)与阅读器之间执行完整的协议。该协议由Lauch()开始，然后是SendReader与SendTag，输出协议循环π的成功消息列表。

　　(8)Result(π)→x：如果阅读器成功识别一个合法的标签，则返回1;否则返回0。

　　(9)Time(π)→δ：返回阅读器的总计算时间δ。

　　(10)Corrupt(vtag)→S：获得标签(虚拟ID为vtag)的当前状态S。

　　1.3 隐私分类

　　攻击者分为强(strong)、破坏性(destructive)、前向(forward)、弱(weak)攻击者，此外与这4类攻击者正交的还有wide与narrow两个攻击者的概念，wide攻击者可通过阅读器访问认证结果，但narrow攻击不行。图1描述了6种攻击概念之间的关系[5]。

　　1.4 安全性级别

　　定义1 正确性：如果在IdentTag程序之后R返回标签ID的成功率极高，则认为该协议符合正确性。

　　定义2 强正确性：如果在R与合法标签T交互之后返回标签ID的成功率极高，则认为符合强正确性。

　　定义3 稳固性[5]：如果对合法标签T假冒攻击的成功率极低，则认为符合稳固性。

　　1.5 隐私性

　　定义4 盲攻击：假设B表示一个算法，仿真了Lauch()、SendReader(m，π)、SendTag(m，vtag)与Result(π)4个程序的串行组合(对于攻击者A)，并且不知道任何的秘密信息。一个盲攻击者(AB)不使用Lauch()、SendReader(m，π)、SendTag(m，vtag)与Result(π)程序，如果存在B，则攻击者A威胁极小，即|Pr[Awins]-Pr[AB wins]|可忽略不计。

　　2 本文大规模RFID网络安全协议

　　定义5 Hash函数：假设l∈N是一个安全参数，γ，K∈N是l中的项，则hash函数H可定义为{0，1}γ→{0，1}K，其条件为：

　　(1)对于一个给定的输出yi，无法反向计算出满足H(xi)=yi的xi。

　　(2)计算出满足条件xi≠xj && H(xi)=H(xj)的参数组合(xi，xj)难度极高。

　　定义6 物理不可克隆函数(PUF)[6]：假设l∈N是安全参数，γ，K∈N是l的项。理想的PUF(设为P)定义为{0，1}γ→{0，1}K，其条件如下：

　　(1)对于参数对(ci，cj)∈{0，1}γ，P(ci)=ri，P(cj)=rj。如果ci=cj，则概率Pr[ri=rj]=1。

　　(2)攻击者无法在有限次数内计算出P的输出。

　　表1所示是本文预设参数及其意义。

　　本文协议主要有两个阶段：初始化与验证阶段，图2所示是本文RFID隐私保护协议的主要流程。

　　2.1 初始化阶段

　　为数据库随机生成秘钥S，为每个标签生成两个随机且唯一的秘钥a与b。然后，为每个标签计算其秘钥c=SP(a)P(b)，其中P(·)是各标签的嵌入PUF。数据库保存每个标签的基本信息{ID，a，b，DATA}。

　　2.2 验证阶段

　　(1)每个阅读器生成一个随机数r1∈{0，1}l并广播该随机数。

　　(2)标签Ti生成一个随机数r2∈{0，1}l，计算M1←H(r1，r2，ai)，M2←H(r1，r2，ai)IDi，h←H(r2，1，2)。然后，将Pi(ai)与r2做异或运算，计算出消息k。使用kPi(bi)ci代替消息k，从内存中删除Pi(bi)。标签将M1、M2、k发送至阅读器。 (3)阅读器生成一个随机数r3∈{0，1}l。计算阅读器通过计算验证M1以实现标签Ti的验证。如果成功验证标签Ti，阅读器则计算然后将r3与M3发送回标签Ti。

　　(4)标签Ti通过计算H(h，r3，bi)验证M3。如果验证成功，则Ti成功验证阅读器。

　　3 本文协议的性能分析

　　3.1 安全性分析

　　本文协议理论上可抵御假冒攻击，下文将证明本方法对假冒攻击具有安全性。因为本文协议是无状态协议，并且标签无需与数据库保持同步，因此，去同步攻击对本协议也无效。

　　引理1：假设A是一个destructive级别的攻击者。A的特点是在不执行Corrupt程序的情况下，获得共享秘钥的成功率极低。

　　证明：假设有一个攻击者A可学习共享秘钥(不执行Corrupt程序)。每个标签响应阅读器的查询语句(M1，M2，k)，其中k=Sr2，r2是标签产生的随机值。为了获得共享秘钥S，A需要知道随机数r2，然而，r2并没有随密文发送，A必须从消息M1、M2与M3中破解出r2。此外，将标签ID IDi以密文形式H(r2，r1，1)IDi发送至阅读器，在不知道随机值的情况下A无法破解出IDi。

　　3.2 计算效率与隐私性实验与分析

　　在此分析标签端与数据库端的性能。本协议中，一个标签共需完成4个hash运算、两个PUF运算与4个XOR运算，数据库端则需要完成一个标签验证程序，该验证需要3个hash运算与两个XOR运算，其复杂度为O(1)。本协议在标签端与数据库端均无需秘钥更新机制。

　　表2所示是本文方法与其他RFID隐私保护算法的计算效率与隐私性比较，其中，成本1：共2128个标签的RFID网络;成本2：共216个标签的RFID网络;成本3：共N个标签的RFID网络;nonce：生成随机数操作;hash：哈希运算;PUF：PUF运算。从中可看出，本方法具有最高的隐私等级，并且其数据库端的计算复杂度较低。

　　4 结论

　　PUF具有鲁棒性、不可克隆性以及不可预测性特点，本文提出一种基于PUF的RFID验证协议，本协议最大的优势是无需搜索数据库(识别标签)，其搜索复杂度仅为O(1)，因此本协议可应用于大规模RFID网络。与其他RFID隐私保护算法的比较结果显示，本方法具有最高的隐私等级，并且其数据库端的计算复杂度较低。