Security challenges for RFID systems: From protocol design to hardware implementation

RFID (Radio Frequency Identification) systems are becoming a very prominent communication technology. They are expanding from common applications such as supply chains, access control and tracking systems to health care applications and intelligent transport systems. RFID technologies are part of everyday life. Unfortunately, their usage raises important security and privacy issues. Current standards from ISO, IEC and EPCglobal provide either no protection at all or simple password-based access control. This can cause serious security and privacy risks since eavesdropped messages can compromise or track a tag.;In order to achieve stronger security and privacy, many non-standard proposals are presented. The non-standard solutions can be classified depending on whether a public-key algorithm is used or not. Only a public-key algorithm can resolve all the generally desired properties, which include system scalability and security against cloning attacks, replay attacks, tracking attacks and Denial of Service (DoS) attacks. However, since a public-key algorithm requires much more hardware resources in a tag so far, most cryptographic protocols are designed using hash algorithms or private-key algorithms. Therefore, some of the desired properties must be surrendered.;We present two different approaches to achieve RFID security and privacy; each includes authentication protocol designs and hardware implementations. The first is a hash algorithm; this is effective for low power consumption and small gate area compared to a public-key algorithm. As privacy is a primary concern, the number of tags in a system would be limited by the computing power of a server since its workload increases linearly with the number of tags. Therefore, throughput optimization in architecture design is an important factor in an RFID server or reader. However, in previous work, designers used their intuition for better throughput and there was no proof or claim whether their designs are optimal. In this thesis, we develop a design methodology applicable to any of the MD4-class hash algorithms (which are the most popular class of hash algorithms). We show how to analyze the iteration bound, which defines a theoretical upper limit of throughput at the micro-architecture level, and how to design a hardware architecture that is achieving this theoretical limit. By applying this methodology, it is possible to design throughput-optimum architecture of SHA1 for the first time as noted in the literature.;The second approach is to use a public-key algorithm. Since most of the conventional public-key based authentication protocols are not secure against tracking attacks, we design new protocols. In this case, the workload in a server can be fixed as a constant independent of the number of tags. However, due to the complexity of a public-key algorithm, an efficient implementation in a tag is essential to lower the required hardware resources such as the power consumption and the circuit area. The power consumption should be low enough to be operable with a passive tag and the circuit area is directly related with the price of a tag. To achieve this, we perform optimizations at multiple levels: protocol level, algorithm level, micro-architecture level and arithmetic level. As a result, we show a public-key is feasible for a passive tag.;In short, the presented approaches can be used for different RFID applications with different security and/or operation properties. If a low implementation cost of tags is a primary concern, a hash algorithm can be used for security solutions, which requires to surrender either the system scalability or the security against tracking attacks. A solution that mitigates tracking attacks while keeping the system scalability is presented in this thesis as well. On the other hand, if privacy and the system scalability are required in an RFID system, a public-key algorithm can be used, whose implementation complexity and power consumption are optimized for tags using various techniques.