周清雷，周 静

(郑州大学信息工程学院，河南郑州450001)

0 引言

RFID技术在日常生活中最常见的应用是读写器和标签间的交互，RFID安全协议是实现这种交互的重要保证。其中RFID搜索协议是RFID认证协议［1-6］的延伸，在大批量货物中快速搜索目标货物、高效管理大型图书馆等多个应用领域中具有重要的意义，但目前对其单独的研究还比较少。Tan［7］较早的提出了搜索协议，但由于在整个协议中使用的是hash函数，导致标签成本较高;Kulseng［8］针对此问题在提出的新协议中用LFSR(linear feedback shift register)和PUF(physically unclonable function)构造的随机序列函数代替了hash函数，但引进函数种类较多;Ahamed［9］、曹铮［10］、赵斌［11］等分别在协议中引用了伪随机函数，但部分计算过程仍使用了hash函数，不能从根本上降低标签成本而且在提出的协议中采用信息更新机制来防止攻击者重放，但却会导致协议遭受新的重放攻击。本文针对以上提出的问题，设计了一个简单的所需标签成本较低和安全性较高的RFID搜索协议，且利用UC模型对其安全性进行了形式化证明，并将其与前人工作在相关特性和安全性方面进行了对比，显示了新协议的优势。

1 协议设计

本文所设计的新协议是无需后端数据库的，在其运行的整个过程中使用共享的伪随机函数，利用了该函数所具有的伪随机性，强单向性等性质，但同时又考虑了其相对于hash函数较弱的抗碰撞性问题，从降低标签成本和提高安全性角度进行了设计。

协议设计的前提:已知注册机构CA是可信任的，任何一个读写器在CA处注册成功后才是合法的，而且所有的标签必须由CA分发。读写器一旦注册成功，CA会对其授权一批标签，即该读写器能够识别该批标签中的任何一个，而每个标签只能被这一个读写器识别。以读写器Ri和标签Tj为例，若Ri有权访问Tj，其中Ri中存储了一个参数列表Li(ki1:id1，ki2:id2，…kij:idj，…)，Tj存储的参数为 idj和 kij。必要参数说明如下:

idj:Tj的身份标识符，是唯一可区分的。

kij:Ri和Tj间的共享秘密，初始值由CA进行分配，是唯一可区分的。

t:Ri产生的随机数。

f():伪随机函数。

||:连接运算符。

⊕:异或运算符。

*:对标签泛指的下标标记。

Tdesired:目标标签。

Tnotdesired:非目标标签。

kidesired:Ri和Tdesired间的共享秘密。

p:非目标标签产生响应的概率。

1.1 搜索协议1

根据设计的基本思想，协议1如下:

Ri→T*:f(t||kidesired)，t

T*:用自身的秘密信息与t进行连接，经过伪随机函数运算，验证所得结果与收到的函数值是否相等，若相等，则

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired为f(kidesired)

否则

Ri←Tnotdesired:以概率p向Ri发送一个随机数

Ri:对收到的响应进行一一验证，若是确认搜索到了目标标签，则将kidesired更新为f(kidesired)。

在协议1中，Ri将f(t||kidesired)和t一同广播出去，收到该消息的标签做相应的验证后，若认为搜索的是其自身，则发送f(t⊕k*)给读写器，同时用f(k*)来更新k*;否则，以事先设定好的概率p发送同样位数的随机值给Ri，Ri若收到了目标响应，则进行相应的秘密值更新。

协议1的优势有两个:用伪随机函数代替了以前多数搜索协议中采用的hash函数，降低了标签成本;考虑了伪随机函数的碰撞性问题，通过在广播消息的伪随机函数中采用连接运算，而在目标响应消息的伪随机函数中采用异或运算，减小了碰撞发生的可能性，提高了搜索的准确度。

但协议1存在的不足是:Tdesired和Ri成功认证后将更新kidesired，由于各个k*不同才能保证协议的正确运行，但更新后的kidesired是否能够保持与没有更新的标签的秘密信息不同，该协议无法保证。如果相同，再次寻找该标签时，可能导致其它标签产生Ri期待的目标响应，造成误判。

1.2 搜索协议2

针对协议1中的不足，协议2如下:

Ri→ T*:f(t||kidesired)，t⊕ iddesired

T*:用自身的秘密信息与t进行连接，经过伪随机函数运算，验证所得结果与收到的函数值是否相等，若相等，则

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired为f(kidesired)

否则

Ri←Tnotdesired:以概率p向Ri发送一个随机数

Ri:对收到的响应进行一一验证，若是确认搜索到了目标标签，则将kidesired更新为f(kidesired)。

协议2没有直接广播t，而是将(t⊕iddesired)进行广播。即使两个不同标签的秘密值相同，但标签的身份标识是唯一的，用身份标识与收到的(t⊕iddesired)进行异或运算，不同的标签就会得到不同的t值，只有目标标签才能得到原本的t值，从而有效地避免了协议2中提到的问题。

然而以上两个协议仍存在着一个共同的问题:即标签和读写器的共享秘密信息更新可能不同步。原因有两个:①伪随机函数相对于hash函数较弱的抗碰撞性，导致非目标标签可能会误认为读写器搜索的是其自身，之后将秘密信息进行了更新，而读写器却不会进行相应的更新。那么当读写器真正搜索该标签时，即使它存在，也无法搜索到。②通过更新kidesired来避免以追踪为目的的重放攻击，但其有效性却是以该标签存在为前提的。这有可能导致另外一种目的的重放:若Ri在搜索Tdesired时，Tdesired由于某种原因没有收到广播消息，那么Ri和Tdesired中的kidesired都不会更新。此时攻击者虽然对Ri搜索的目标以及搜索结果都一无所知，但它能在窃听到Ri广播出的消息后，将此消息有选择的在一定范围内重放，若Tdesired在该范围内且收到的是重放消息，那么该标签就会认为是Ri在搜索自己，于是会更新kidesired，而Ri中的kidesired并没有被更新，这样也会导致Ri以后无法搜索到该标签。

1.3 搜索协议3

针对2.2节最后提到的问题，本节对Ri的参数列表进行如下修改:在列表中增加一个搜索标识位，以标签Tj为例，该标识位为sij，初始化时，sij=1。下面给出以下定义:①当sij=1时，表明Ri没有搜索到Tj;②当sij=2时，表明Ri搜索到了Tj。协议3如下:

Ri→ T*:f(t||kidesired)，t⊕ iddesired

T*:用自身的秘密信息与t进行连接，经过伪随机函数运算，验证所得结果与收到的函数值是否相等，若相等，则

Ri←Tdesired:f(t⊕kidesired)

Tdesired:更新kidesired为f(kidesired)

否则

Ri←Tnotdesired:以概率p向Ri发送一个随机数

Ri:对收到的响应进行一一验证。⑴若搜索到了Tdesired，则将kidesired更新为f(kidesired)且将sij置为2;⑵若没有搜索到Tdesired时，检查sidesired的值:①若sidesired=1，那么Ri就用f(kidesired)代替消息中的kidesired，再次进行广播，若能收到Tdesired的响应，则将kidesired的值更新为f(f(kidesired))且将sidesired的值置为2，否则sidesired和Tdesired的值不变;②若sidesired=2，则将sidesired的值置为1。

协议3增加了搜索标识位处理机制，当Ri此次没有收到Tdesired的响应时，则要检查sidesired:若sidesired=2，则说明上次搜索该标签时搜索到了，可以肯定该标签此次不存在，将sidesired置为1;若sidesired=1，则有3种可能:①该标签确实不存在;②该标签存在，Ri以前从未搜索过它，但该标签曾经误认为被Ri搜索过，标签的kidesired已经被更新;③该标签存在，但已经受到了重放攻击，它的kidesired已经被更新。所以当检查出sidesired=1时，Ri将用f(kidesired)代替原消息中的kidesired发起新一轮的搜索，从而来防止标签假丢失情况的发生。

2 基于UC模型对最终协议的安全性证明

通过安全性分析，协议3满足机密性、匿名性、不可追踪性、防窃听、防重放和并发安全。本章将对此给出UC模型下的形式化证明。首先简要介绍UC模型如下:

2001年Canneti提出了UC(UniversallyComposable)模型，并定义了框架。该框架采用模块化的思想，通过外界环境不能区分真实协议和理想协议的方法来证明协议是安全的。其中包括以下几个要素:环境机Z，真实协议参与者P1，P2…Pn以及攻击者A，理想协议虚拟参与者p'1，p'2…p'n，理想函数F以及理想攻击者S。其中Z用来模拟协议运行的整个外部环境。在该模型下，若对于任何攻击者A和环境机Z，至少有一个理想攻击者S，使Z不能够区分出自身是在与理想协议交互，还是在与真实协议交互，那么就说真实协议πUC实现了理想函数F，即π是安全的。其中理想函数的设计是该证明方法的关键。

2.1 理想函数Fsearch的设计与安全性证明

本节设计的理想函数Fsearch为每一次会话分配一个会话号，且只和具有相同会话号的实体进行通信，假设读写器是不可攻破的，攻击者只能攻陷合法标签。Fsearch的具体内容如下:

(1)收到R'i发来的消息broadcast()，则独立随机选择一会话号ssid，记录broadcast(ssid，R'i)，向攻击者S发送消息broadcast(ssid，Anonymous(R'i))。

(2)收到某标签发来的消息response()，则对每一个标签，独立随机选择一会话号ssid'，调用目标验证函数g(ssid'，R'i，T'*)，验证是否等于ssid:①若相等，假设该标签为T'j:则将T'j的目标标识位设为1，表明它为目标标签，记 录 response(ssid'，T'j)， 向 攻 击 者 S 发 送response(ssid'，Anonymous(T'j));②否则，以概率 p向攻击者S发送response(ssid'，Anonymous(T'j))。

(3)收到攻击者S发来的消息authenticate(ssid'，ssid，Anonymous(R'i)，Anonymous(T'j))，则查看有没有记录broadcast(ssid，R'i)和response(ssid'，T'j):①若有，则删除这两条记录，记录 link(ssid'，ssid，R'i，T'j)且向 T'j发送消息authenticate(R'i);②否则，忽略该消息。

(4)当收到攻击者 S发来的消息 search(ssid，ssid'，Anonymous(T'j)，Anonymous(R'i))，则查看T'j的攻陷标志位是否为1:①若为1，表明T'j已经被攻陷，则删除当前会话中关于T'j的所有信息，然后向R'i发送search(T'j);②否则，检查有没有记录 link(ssid'，ssid，R'i，T'j):若有，则将其删除，并向 R'i发送 search(T'j);否则，忽略这条消息。

(5)当Fsearch收到攻击者S发来的消息corrupt(ssid')，则将T'j的攻陷标识位置为1。

(6)当 Fsearch收到攻击者 S发来的消息impersonate(ssid＇)，则 检 查 记 录 broadcast(ssid，R'i) 或link(ssid'，ssid，R'i，T'j)是否存在:①若存在，则向 R'i发送search(T'j);②否则，忽略该消息。

下面证明Fsearch满足本章开头所提到的安全特性:

机密性:每次的会话号都是独立随机选择的，只有理想函数能判断出标签是否为目标标签，因此攻击者不能得到协议参与方的任何秘密信息。

匿名性:每次在传送给 S的消息中用Anonymous(R'i)，Anonymous(T'j)，因此攻击者只知道协议参与方的类型，不知道参与方的真实身份。

不可追踪性:非目标标签总是以概率p向S发送消息，因此S无法识别出目标标签响应，即对目标标签的存在性不能做出判断，从而无法对其追踪。

防窃听:由于对通信方的身份实行了匿名制，即使攻击者获取了通信方之间的所有通信消息，也不能从中获得有用的信息，尤其是秘密信息。

防重放:每一次的会话号都是独立随机选择的，而且在本次会话结束后，函数会删除标签和读写器的会话记录，即使攻击者在新会话中重放以前的消息，理想函数也会对其忽略。

并发安全:只有当前子会话结束后，理想函数才会对新会话进行响应和处理，有效解决多个标签同时访问理想函数出现冲突的情况。

所以，Fsearch实现了机密性、匿名性、不可追踪性、防窃听、防重放和并发安全等安全特性。

2.2 对真实协议的安全性证明

为了证明的方便，将协议3称为πsearch，下面来证明πsearch是UC安全的。

命题 假设真实协议中的伪随机函数是安全的，则对于任何一个攻击者，πsearchUC实现了理想函数Fsearch的功能。

证明:对于任何攻击者A、环境机Z，若至少有一个理想攻击者S，使Z无法区分出自身是在与虚拟参与者R'i，T'*和S的交互，还是在与实际参与者Ri，T*和A的交互，从而认为πsearch安全地实现了Fsearch的功能。下面来构造攻击者S:

首先，模拟S与Z的交互，Z产生所有的输入，S把从Z传来的输入写到A的输入带，同样，A把输出带的内容拷贝到S的输出带上，被Z读。其次，模拟S与A和Fsearch的交互，其过程如下:

(1)当 S收到 Fsearch发来的消息 broadcast(ssid，Anonymous(R'i))，则生成一个新的会话号newssid，记录broadcast(newssid，reader)，接着发送消息broadcast(newssid，reader)给真实协议攻击者A。

(2)当 S收到 Fsearch发来的消息 response(ssid'，Anonymous(T'j))，则生成一个新的会话号newssid'，记录response(newssid'，tag)，发 送 消 息 response(newssid'，tag)给真实协议攻击者A。

(3)当 S收到 A发来的消息 authenticate(newssid'，newssid，reader，tag)，则 查 看 记 录 broadcast(newssid，reader)和response(newssid'，tag)是否存在:

若存在，则将其删除，记录 link(newssid，newssid'，reader，tag) 且 向 Fsearch发 送 authenticate(ssid'，ssid，Anonymous(R'i)，Anonymous(T'j));

(4)当S收到A发来的消息 search(newssid，newssid'，reader，tag)，则:①若该tag的攻陷标识位为1，则删除S中关于它的所有信息直接向 Fsearch发送 search(ssid，ssid'，Anonymous(R'i)，Anonymous(T'j));②否则，查看记录link(newssid，newssid'，reader，tag)是否存在:若存在，删除该记录，且向 Fsearch发送 search(ssid，ssid'，Anonymous(R'i)，Anonymous(T'j));否则，忽略该消息。

(5)当S收到A发来的消息corrupt(newssid')，则将S中的tag的攻陷标识位设为1。

(6)当S收到A发来的消息impersonate(newssid'，Tj)，则 若 记 录 broadcast(newssid，reader)或 者 link(newssid，newssid'，reader，tag)存在，则直接发送 impersonate(ssid＇)给Fsearch，这与理想协议中的操作是一样的。

下面分情况来证明真实协议与理想协议对于任意的环境机Z都是不可区分的:

(1)当标签Tj被攻陷时

很显然，这种情况下理想协议和真实协议是不可区分的。

(2)当标签Tj没有被攻陷时

下面利用可证明安全方法的思想来证明之。若对于任何攻击者A、环境机Z，至少有一个理想攻击者S，使Z能够区分出自身是在与真实协议交互还是在与理想协议交互，则:在理想协议中，虚拟参与者与Fsearch间建立会话时的会话号，是Fsearch随机独立选择的。而在真实协议中，每次A都会激发参与者产生一个伪随机函数值，而标签和读写器自身的内部行为及交互，对Z来说是不可见的。已知算法D是由Z构造的，具有以下功能:在每次仿真交互时执行Z的若干副本中的一个，且针对Z，模拟攻击者A和实体Ri、T*并与其交互。当实体即将重新产生一个随机数时，让函数l生成一个伪随机数。若Z在实体T*未输出结果时已攻陷了T*，则D终止运行且输出一个随机值;不然，D继续运行且其输出为Z的输出。若D没有终止，且l是伪随机函数，那么Z的输出为它和πsearch交互时的输出;若l是随机函数，那么Z的输出为它和Fsearch交互的输出。所以，若Z能以不可忽略的概率区分出πsearch和Fsearch，那么D就能够利用向一个随机预言机发出询问的方式，以同样的概率区分出伪随机函数和随机函数。因为伪随机函数是安全的，从而得出矛盾。由以上可得，对于任何攻击者A和环境机Z，至少有一个理想攻击者S，使得Z不能区分出自身是在与R'i，T*和S交互，还是在与Ri，T*和A交互，从而πsearch安全地实现了理想函数Fsearch的功能。综合 (1)(2)，可以得出结论:πsearch是UC安全的，实现了机密性、匿名性、不可追踪性、防窃听、防重放、并发安全等安全特性。

3 分析与比较

下面就本文的最终协议与Tan、Ahamed、曹铮、赵斌分别在对应文献［7，9-11］提出的协议在相关特性与安全性方面进行分析对比见表1。

表1 协议相关特性对比表

表1结果显示，新协议相对其他几个协议降低了标签成本，且解决了以往协议中存在的通信双方信息更新不同步问题。

表2 协议安全性对比表

表2结果显示，新协议比其他几个协议更安全，具有较高的安全性。

4 结束语

本文首先对前人的工作进行了分析和总结，针对出现的标签成本较高以及容易遭受攻击等问题，通过3个协议来逐层展示协议设计的过程，在这三个协议中，后一个协议总是对前一个协议的改进和完善，形成了最终的搜索协议3，且利用UC模型对其安全性进行了形式化证明，得出该协议是UC安全的，最后对新协议与前人协议在相关特性及安全性方面进行了对比，其结果达到了协议设计的初衷。

本文在协议的设计过程中有3个创新点:①协议中完全采用了伪随机函数，真正减少了标签逻辑门的数量，降低了标签成本，适合于低成本的RFID系统。②考虑了伪随机函数可能引发的碰撞性问题，提高了搜索的准确度。③通过在读写器存储列表中增加搜索标识位避免了以通信双方秘密信息更新不同步为目的的重放攻击，提高了安全性，这同时也解决了非重放原因造成的更新不同步问题。但新协议也有不足:当读写器没有搜索到目标标签时，有可能要发起新一轮的搜索，这种情况将会导致搜索效率的下降。所以新协议比较适合于实时性要求不高，安全性要求相对较高的应用。因此，如何在降低标签成本和保证安全性的基础上，设计出更加高效的RFID搜索协议，是下一步需要做的工作。

［1］TAN C C，SHENG B，LI Q.Secure and serverless RFID authentication and search protocols［J］.IEEE Transactions on Wireless Communications，2008，7(4):1400-1407.

［2］QI Yong，YAO Qingsong，CHEN Ying，et al.Study on RFID authentication protocol theory ［J］.China Communications，2011，8(1):65-71.

［3］LI Jian，SONG Danjie，GUO Xiaojing，et al.ID updating-based RFID mutual authentication protocol for low-cost tags［J］.China Communications，2011，8(7):122-127.

［4］WEI C H，HWANG M S，Chin A Y.A mutualauthentication protocol for RFID ［J］.IT Professional，2011，13(2):20-24.

［5］DING Zhenhua，LI Jintao，FENG Bo.The research of secure authentication protocol based on hash function for RFID ［J］.Journal of Computer Research and Development，2009，4(4):483-592(in Chinese).［丁振华，李锦涛，冯波.基于Hash函数的RFID安全认证协议的研究［J］.计算机研究与发展，2009，4(4):483-592.］

［6］Seo K J，Jeon J C，Yoo K Y.A reinforced authentication protocol for anti-counterfeiting and privacy protection［C］//6th International Conference on Information Technology:New Gergerations.Las Vegas:IEEE Press，2009:1610-1611.

［7］TAN C C，SHENG B，LI Q.Serverless search and authentication protocols for RFID ［C］//5th International Conference on Pervasive Computing and Communication.New York:IEEE Press，2007:24-29.

［8］Kulseng L，YU Z，WEI Y.Light weight secure search protocols for low-cost RFID systems［C］//29th International Conference on Distributed Computing Systems.Washington:IEEE Press，2009:40-48.

［9］Ahamed S，Rahman F，Hoque E，et al.S3PR:Secure serverless search protocols for RFID ［C］//International Conference on Information Security and Asurance.Hawaii:IEEE Press， 2008:187-192.

［10］CAO Zheng，DENG Miaolei.A univerally composable RFID search protocol［J］.Journal of Huazhong University of Science and Technology，2011，39(4):56-59(in Chinese).［曹铮，邓淼磊.通用可组合的RFID协议［J］.华中科技大学学报，2011，39(4):56-59.］

［11］ZHAO Bin.The research on RFID security authentication and search protocols without back-end database［D］.Xian:Xian University of Electronic Science and Technology，2011(in Chinese).［赵斌.无后端数据库的RFID安全认证和搜索协议研究 ［D］.西安:西安电子科技大学，2011.］