ScalabilityUniqueness of MetaIDsResources required for authenticationCloning ProblemTracking ProblemForward SecrecyDenial of Service AttackSecure and Low-cost RFID Authentication Protocols 1 1,2Yong Ki Lee and Ingrid Verbauwhede1 University of California, Los Angeles 2 Katholieke Universiteit Leuven {jfirst, ingrid} @ ee.ucla.edu Abstract In this paper we propose two RFID (Radio Frequency Identification) authentication protocols for secure and low-cost RFID systems. The first protocol SRAC (Semi-Randomized Access Control) is designed using only a hash function as security primitives in tags. In spite of very restricted functionality, SRAC resolves not only security properties, such as the tracking problem, the forward secrecy and the denial of service attack, but also operational properties such as the scalability and the uniqueness of MetaIDs. The second protocol A-SRAC (Advanced SRAC) resolves the replay attack in the cost of a random number generator in tags. Moreover, our schemes have significantly reduced the amount of tag transmissions which is the most energy consuming task. 1 Introduction The RFID technology has been one of the hottest issues in the wireless communication area. One of the reasons many developers are researching this topic is that the RFID is supposed to replace the bar code systems. This expectation has been accelerated since the adoption of EPCglobal Gen2 [8]. However, the application area is not restricted to product supply chains but covers livestock tracking, airline baggage, road toll management, hotel room access and so on. In order to be popular in commercial markets, the RFID system should overcome the restriction of cheap RFID tags. The limited price means limited functionalities and resources in tags. Because of the limitation, using asymmetric or symmetric key encryption algorithm or making memory secure in tags is improper [1]. To solve security problems related with low-cost RFID systems, many authentication protocols were proposed. However, those protocols could not satisfy the RFID security requirements and/or operational requirements. According to the best of our knowledge, there is no published authentication protocol that deals effectively on security and operational requirements. In this paper we review and classify previously proposed protocols and their drawbacks, and propose new protocols which satisfy not only several major security properties such as the tracking problem, the forward secrecy, the denial of service attack and the replay attack, but also operational properties such as the scalability and the uniqueness of MetaIDs. The remainder of this paper is organized as follows. Section 2 explains the desired properties in RFID systems. Section 3 introduces related works and points out the problems they have. In section 4 and 5, we propose new RFID authentication protocols and analyze several operational and security properties, and conclude this paper in section 6. 2 Desired Properties in RFID System Even though the resources allowed in RFID tags are very restricted, RFID systems are supposed to satisfy some operational and security requirements. The following sub-sections explain those requirements. 2.1 Operational requirement Considering that most applications of RFID systems require a lot of tags to be used, the scalability is a required property. For example, in order to apply RFID systems to a large library, more than 1 million RFID tags should be applicable. Another operational requirement is the uniqueness of MetaIDs. Many published protocols [2, 3, 4, 6] make MetaIDs using a hash function. One problem is that we cannot assure the uniqueness of hash outputs. In order to avoid the conflictions of hash outputs, we need to have enough length of hash outputs. Otherwise the confliction of MetaIDs can cause serious problems in the system. In another word, if we can make sure the uniqueness of MetaIDs, we can reduce the size of MetaIDs, which means the reduction of transmission and memory. 2.2 Security requirement The most important security problems are the cloning and tracking problems. However, there are more security properties which are useful in RFID systems. We consider 1the other properties when we analyze our proposing protocols. Without sharing the common secret information among all the readers and the tags, making the response pseudo-random causes some drawbacks. [2, 6] described protocols which resolve tracking problems, but the systems are not scalable since the server needs to perform hashes for all the tags’ ID every time of authentication protocols. One approach to resolve the un-scalability of randomized access control is proposed in [4]. This scheme used a cryptanalytic method. However, this method also causes some other problems. Since this protocol uses time-memory trade-off method [5], in order to reduce the searching time they have to increase the amount of memory in the server. Another problem is that the searching algorithm is probabilistic, i.e. there is some probability to fail in searching for a tag’s ID. Even though they are saying the failure probability is small, it can cause a crucial problem in certain applications. First of all, to prevent the cloning problem in low cost tags, it is indispensable to store some secret information in tags which cannot be made arbitrarily by attackers. And the secret information should be used in authentication between a tag and a reader. There are two ways to store secret information in tags. The first way is to store common secret information among all the readers and the tags. In this way, as long as the information is secure, this method makes the systems very secure and efficient. However, if a single tag is compromised, attackers may clone other tags or may control all the tags using the secret information. The other way is to store secret information which is pertinent to only a specific tag. In this case, even if some secret information is compromised, the information will be irrelevant to the other tags so that they still remain secure. Protocols proposed in [3, 7] resolve the tracking problem by sharing the common secret information among all the readers and the tags. Even though these schemes are scalable and resolve the tracking problem, they have a crucial problem. By capturing and compromising only one tag, attackers can reveal the secret information. Once the secret information is revealed, the tags which share the secret