【作者】 田芸；

【导师】 陈恭亮；

【作者基本信息】 上海交通大学 ， 计算机科学与技术， 2013， 博士

【摘要】 物联网已成为当前世界新一轮经济和科技发展的战略制高点之一，射频识别（RadioFrequency Identification, RFID）技术是物联网中的关键技术，通过无线射频方式传输和获取相关数据，并对物体加以识别。RFID系统主要由电子标签、阅读器和后端服务器三部分组成。被动电子标签通常被贴附在物品上或嵌入物品中，对该物品或者持有者进行标识。标签作为信息的载体，在RFID系统中具有非常重要的地位，阅读器通过对标签进行身份识别，即可以知道该物品的相关特征或者持有者的个人信息。在被动电子标签的身份识别中存在一些问题，包括碰撞问题、安全问题以及搜索问题等，这些问题从一定程度上制约了电子标签的大规模应用。本课题通过对这些问题的研究，从理论上给出计算证明和相关数据，并结合被动电子标签的实际硬件和RFID标准要求，使这些理论成果可以直接在实际应用中发挥作用，解决被动电子标签在身份识别中存在的问题，促进RFID技术的应用和物联网的发展。本文针对被动电子标签身份识别中的问题进行了比较深入的研究，并取得了一系列的成果，主要研究内容和成果如下：1．对被动电子标签身份识别中涉及到的碰撞问题、安全问题以及搜索问题进行统一的描述，其中，搜索问题可以看作碰撞问题和安全问题的结合。这些问题的描述包括问题存在的场景、所要达到的目标、存在的阻碍和达到目标应该满足的要求等；2．在对电子标签防碰撞算法的研究现状进行详细的回顾及分析的基础上，提出基于临时ID的查询树电子标签防碰撞算法，从标签ID中选取字符串作为临时ID，当多个标签由于具有相同的临时ID而不可区分时，将重新选取字符串作为临时ID，给出仿真实验结果，表明该算法比查询树及其变型算法在标签平均传输比特数方面具有优势，从而提高标签识别的效率。提出带堆栈的双时隙二进制树电子标签防碰撞算法，该算法采用曼彻斯特编码，利用双时隙机制为标签预留响应时隙，减少标签发送的比特数和碰撞次数，采用堆栈的方法记录碰撞发生的位置，减少阅读器的查询次数和无用信息的重复查询，并分别从数学推导和实验结果证明所提出的算法比原始的二进制树算法在时间复杂度和通信复杂度方面都有所降低，提供了更高的标签识别性能；3．研究分析轻量级序列密码Trivium的设计，定义Trivium型移位寄存器并将其推广到k轮，证明k轮的Trivium型移位寄存器的特征多项式形如(1+x)kf(x)，定义k阶本原多项式，并给出Trivium型密码的设计准则，要求其每轮的特征多项式都为k阶本原多项式。根据该准则对Trivium算法进行改进，提出面向电子标签的轻量级序列密码Quavium，Quavium的设计基于4轮的Trivium型移位寄存器结构和k阶本原多项式，由于每轮都保持特征多项式的本原性，因此可以根据不同的应用需求采用不同寄存器长度的密码算法，实验结果表明，Quavium在硬件和软件上的性能几乎和Trivium相当，3轮甚至更少轮数的Quavium具有更佳的性能，更适用于被动电子标签的通信保密；4．分别对简单级、轻量级和超轻量级RFID身份认证协议进行研究。在简单级的RFID认证协议方面，分析典型的匿名RFID认证协议ARAP协议，对该协议进行假冒攻击，针对简单级协议对计算复杂度的要求，提出置换操作及相应的改进措施，使其可以在原协议的基础上抵抗假冒攻击；在轻量级的RFID认证协议方面，给出一个广义的3轮轻量级RFID双向认证协议框架，证明如果该框架无法抵抗假冒攻击，那么还可以对该框架进行非同步攻击，根据此定理实现对两个符合EPC C1G2标准的轻量级双向认证协议的非同步攻击，并提出相应的修正方法，改变标签响应信息的计算；在超轻量级的RFID认证协议方面，对带置换的超轻量级RFID身份认证协议RAPP协议进行分析，给出与置换运算和循环左移运算相关的性质，指出超轻量级协议中存在的漏洞，原因是标签不具有产生伪随机数的能力，因此，引入初始值机制，设计增强型带置换的超轻量级协议，并分析协议的安全性和性能；5．提出轻量级电子标签搜索协议的设计准则，并根据该准则设计了一个无需服务器的符合EPC C1G2标准的轻量级电子标签搜索协议，与其他搜索协议相比，该协议需要更少的操作类型和更低的计算复杂度，适用于被动电子标签，安全分析表明，该搜索协议满足数据完整性、实体认证性、实体匿名性和不可跟踪性。更多还原

【Abstract】 The Internet of Things has become one of the strategic commanding heights in theeconomy and technology development of the current world. Radio frequency identification isa key technology in IOT. It transmits and obtains information via radio to identify objects. AnRFID system mainly consists of RFID tags, RFID readers and a back-end server. PassiveRFID tags are usually attached to or embedded in objects so that the object or the carrier canbe identified. Being the carrier of information, tags play a very important role in RFIDsystems. By identifying the tag, the reader can obtain the features of the object or theinformation of the owner.There are several problems in the identification of the passive RFID tags, includingcollision problems, security problems and search problems. These problems restrict thelarge-scale use of RFID tags. So we study these problems in this dissertation, presentcomputation, proof and data in theory, make these theoretical results directly work in thepractical use by integrating the actual RFID tag hardware and RFID standards, and solve theproblems in the identification of passive RFID tags to promote the application of RFIDtechnology and the development of IOT.This dissertation makes a relatively thorough research on the identification of passiveRFID tags and obtains several achievements. The main research content and results in thisdissertation are as follows:1. Make unified description of the problems in the identification of passive RFID tags, i.e. collision problems, security problems and search problems. Search problems can beregarded as the combination of collision problems and security problems. The descriptionincludes the situation of the problem, the objective to be achieved, the existing obstacles andthe requirements to be satisfied to reach the goal.2. Make a detailed review and analysis of the state of the art of RFID tag anti-collision algorithms. Propose a temporary ID based query tree RFID tag anti-collision algorithm. Eachtag in this algorithm selects a sequence from its ID as its temporary ID. When several tags areundistinguishable because of the same temporary ID, they will select other sequences in ID.The simulation results show that the algorithm has advantage over the query tree algorithmand its variants in terms of average number of transmitted bits for one tag identification. Sothe algorithm improves the identification efficiency. Propose a bi-slotted binary tree RFID taganti-collision algorithm with stack. Manchester code is used in this algorithm. Bi-slottedmechanism is adopted to reserve slots for the tag responses so that the average number oftransmitted bits by the tag and the number of collisions will be reduced. The reader maintainsa stack to record the position of collisions so that the number of queries sent by the reader isreduced and the useless repeated queries are dimished. Mathematical derivation andsimulation results both prove that the proposed algorithm outperforms the original binary treealgorithm in terms of time complexity and communication complexity and provide betterperformance on tag identification.3. Analyze the design of a lightweight stream cipher named Trivium, destruct it toTrivium-model shift registers and generalize the structure to k rounds. Prove that thecharacteristic polynomial of a k-round Trivium-model shift register has the format of (1+x)kf(x) and define k-order primitive polynomials. Give the design criteria of Trivium-modelstream ciphers, requiring the characteristic polynomials of each round to be k-order primitivepolynomials. Based on the criteria, an improved version of Trivium is presented. Moreover, anew RFID tag oriented lightweight stream cipher, Quavium, is proposed. Quavium iscomposed of4-round Trivium-model shift registers and each round satisfies the k-orderprimitive polynomial so that the stream cipher can be used in a shorter version or in thecomplete version according to different application requirements. Experimental results showthat Quavium performs nearly the same as Trivium in both hardware and software. Quaviumof fewer rounds have better performance and is more suitable for the communication securityof passive RFID tags.4. Study the simple RFID authentication protocols, the lightweight RFID authenticationprotocols and the ultralightweight RFID authentication protocols respectively. In the simpleRFID authentication protocols aspect, a typical anonymous RFID authentication protocolARAP is analyzed and impersonation attack is launched against this protocol. According tothe computation complexity requirements of simple protocols, a new operation named permutation is introduced and corresponding remedies are presented to improve the originalversion and resist impersonation attacks. In the lightweight RFID authentication protocolsaspect, a generalized3-round lightweight RFID mutual authentication protocol framework ispresented. It is proved that if the protocol framework is vulnerable to impersonation attacks,desynchronization attacks can also be launched against it. Based on this theorem,desynchronization attacks are launched against two lightweight RFID mutual authenticationprotocols in conformity with EPC C1G2standards. In addition, corresponding suggestions areproposed to change the computation of the messages sent by tags so as to resistdesynchronization attacks. In the ultralightweight RFID authentication protocols aspect, anultralightweight RFID authentication protocol with permutation is analyzed. Some theoremsrelated to the permutation and left rotation operations are proposed. It is pointed out thatultralightweight protocols have vulnerabilities due to the fact that tags cannot generaterandom numbers. Therefore, initial value mechanism is introduced to provide freshness in thetag end. An enhanced ultralightweight RFID authentication protocol is proposed and securityanalysis and performance evaluation are given.5. Propose the design criteria for lightweight RFID search protocols and design aserverless lightweight RFID tag search protocol conforming to EPC C1G2standards.Compared with other search protocols, the proposed protocol requires fewer operation typesand less computation complexity. So it is more suitable for passive RFID tag search. Securityanalysis shows that the protocol achieves data integrity, entity authentication, entityanonymity and untraceability.更多还原