Abstract
Using RFID tags can simplify many applications and provide many benefits, but the privacy of the customers should be taken into account. A potential threat for the privacy of a user is that anonymous readers can obtain information about the tags in the system. In order to address the security issues of RFID systems, various schemes have been proposed. Among the various solutions, lightweight protocols have attracted much attention as they are more appropriate for the limited architecture of RFID tags. In this paper, we perform the security analysis of five lightweight protocols proposed in [1-4] and discuss their advantages and security issues. The computational complexity of these lightweight protocols are also compared in this work.
Introduction
Radio frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. For pervasive deployment of RFID systems, one issue which causes public’s concern is privacy. Many research activities have been devoted in the area of RFID security and privacy recently. Various attacks on the current algorithms, protocols and implementations showed that the privacy of RFID systems should be taken into account more seriously. Some customers are concerned about being tracked by other readers when they are carrying items (such as clothes, medicine or currency) embedded with RFID tags. In addition to tracking people, RFID tags may also be used to extract personal information such as the type of clothes somebody wears, the specific brand that an individual is interested in, or some medical information about the patient carrying an RFID-embedded container of medicine [5]. RFID tags may also be used by some malicious organizations or dealers that sell fake RFID embedded items and forge them as valuable items [5]. Denial of service (DoS) is another type of problem which can be caused by attackers whose aim is to disrupt an RFID system [6]. Moreover, some specific RFID applications demand specific considerations.
In order to cope with security issues of RFID systems, various schemes have been proposed. These solutions can be divided into two general groups. The first group uses blocking, jamming and physical solutions [7]. The other group uses cryptographic concepts and privacy preserving protocols. Cryptographic solutions for RFID security issues can be divided into two main groups, lightweight and complex cryptographic solutions. Some researchers believe that it is possible to
Fig. 1. The RFID protocol proposed by Henrici and Muller [1] use complex cryptographic protocols in future RFID tags. Most RFID researchers, however, believe that the industry needs simple and low cost RFID tags (below 5 cents per item) with limited number of logical gates [5],[8]. For this case, many approaches that are based on the lightweight cryptographic solutions and protocols have been suggested [1-4]. Lightweight protocols have the advantage of keeping the computational demand and the price of RFID tags very low. In this work, we perform a security analysis of five lightweight protocols proposed in [1-4], and show that they are vulnerable to some simple security attacks.
Henrici-Miiller RFID Protocol
In this Section, we explain the protocol proposed by Henrici and Muller [1]. In this protocol, each tag contains its current identifier id, the current session number i, and the last successful session number i*. Similarly, the database contains a list of all identifiers, session numbers and the last successful session numbers for all the tags in the system. Both the reader and the tags are aware of the hash function h, and o is a "simple XOR function" [1]. The communication process is performed as shown in Fig. 1. It should be noted that in this protocol, an entry is not deleted from the database after the third step, but a copy of the previous id and i* is kept until the next successful session.
Although this protocol is simple, efficient and can solve many security issues of RFID systems, it is vulnerable to some simple attacks as explained below:
1. In this protocol, the tag increases the value of i by one, even if the session finally fails, while i* is updated only if the session is successful and the reader is confirmed. Based on the above, an attacker can interrogate a tag several times to abnormally increase i and Ai. Therefore, an attacker is able to recognize its target by identifying and "tracking" the tag that sends abnormally large values of Ai.
2. After step (2) and before the legitimate reader sends r and h(r o i o id) to the tag, the attacker can use a null element like r’ = 0 and sends back the r’ and h(r’ o i o id) to the tag. As a result, the original r and h(r o i o id) will not be accepted from the legitimate reader and it will be "desynchronized" from the tag.
Fig. 1. The RFID protocol proposed by Henrici and Muller
Fig. 2. The challenge-response trigger protocol proposed by Lim et al.
3. As mentioned before, a copy of the previous id is kept in the database to make it possible for the reader to communicate with a tag whose id has not been updated for any reason. Using this fact, an attacker can simply save and then "replay"
to the legitimate reader to "impersonate" itself as the real tag.
4. In Henrici-Muller protocol, when a legitimate reader interrogates a tag, an attacker can interrogate this tag before the reader carries out the third step. After receiving the request message from the attacker, the tag increases i by one. Thus, the hash value sent by the legitimate reader to the tag is conceived as an incorrect response and will not be accepted (desynchronization).
5. An attacker can repeatedly send the request message to the nearby tags and looks for the h(id) in the received replies. As a result, the attacker can "track" a specific tag using its h(id).
Lim et al. RFID Protocols
In this Section, we explain two RFID protocols proposed by Lim et al. [2]. The first protocol is named the "challenge-response trigger" and uses a challenge-response mechanism to provide the required security. In this scheme, each tag contains its current id, and a copy of all the tag ids is kept in the database. The communication process is shown in Fig. 2. Here, R and R’ are random challenges, o shows the XOR function, and g is a one-way hash function [2]. In the challenge-response trigger protocol, an entry is not deleted from the database after the third step. The challenge-response trigger protocol is vulnerable to some simple attacks as discussed below:
1. For most RFID applications, it is a reasonable assumption that a tag may be captured and analyzed by an attacker. The attacker can interrogate the captured tag for different values of R, and make a dictionary of some probable challenges and related responses from the tag. The attacker can use this dictionary later to impersonate itself as the real tag to the legitimate reader.
Fig. 3. The forward rolling trigger protocol proposed by Lim et al.
2. As another attack, the above mentioned dictionary can be used to track a specific tag. The attacker would repeatedly send the request message and R to all tags and look for the g(id, R) response known from the dictionary.
3. After the legitimate reader sends a request message to the tag in step (1) and before step (3), an attacker can repeat step (1) and send a request message to force the tag to reset the random challenge R’. Since the new random challenge is different from the previous one, the h(ido R’) message which the reader sends will not be accepted by the tag.
After the challenge-response trigger protocol, another scheme named the "forward rolling trigger" was proposed in [2]. This scheme takes advantage of Lamport’s one-time password authentication scheme [9]. In the "forward rolling trigger" protocol, the tag only responds to a valid challenge from the reader or sends back some random values otherwise [2]. In this protocol, the reader stores a chain of hash functions like
where h is a secure one-way hash function, w is a secret random seed, and max is the length of the chain. The reader uses a hash value from this chain to authenticate itself to the tag over time. For each tag in the system, the last successful session (communication with the reader) is stored as i* and the current session is shown by i. The reader uses
to authenticate itself to the tag. The communication process is shown in Fig. 3. As in the challenge-response trigger protocol, an entry is not deleted from the database after the third step, but a copy of the previous id is kept until the next successful session. The forward rolling trigger protocol has some security drawbacks, as stated below:
1. The total number of session requests which can be issued by the reader is limited to max for each tag, which makes the protocol vulnerable to DoS attacks.
2. The attacker may know the set of acceptable {i, Li] (or at least a large pair of this set) from another RFID system or by tampering. The attacker can send i = max and Lmax to a tag and waste its set of acceptable {i, Li].
3. The (i — i*) > 0 condition makes the protocol vulnerable to DoS attack. Moreover, the reader needs to be aware of the tag which is going to be interrogated next, and this is not a plausible assumption for many applications. On the other hand, if we remove the (i — i*) > 0 condition, the protocol becomes vulnerable to another attack. The attacker may listen to the communications between the tags and the reader in another RFID system, eavesdrop and save a valid (i, Li) pair, and use it for an RFID system somewhere else to ruin the synchronization between the tag and the reader.
4. If we remove the (i — i*) > 0 condition from the protocol, an attacker can eavesdrop on the previous communication between the tag and the reader and use one of the previously used valid (i, Li) pairs to interrogate the tag again. The tag replies with extid = g(id, i) and the attacker can track the tag by sending the request message repeatedly.
5. An attacker may find a valid (i, Li) pair from another RFID system as explained above. Then, it can send the valid pair along with the request message to a captured tag and obtain the {R’, extid = g(id, i)} information in the second step. Using the {R’, extid = g(id, i)} information, the attacker is now able to impersonate itself as the actual tag to the legitimate reader.
Tan et al. RFID Protocol
In this Section, we explain the lightweight protocol proposed by Tan et al. [3]. This scheme uses a server-less authentication protocol that aims to provide the same level of security as the previous protocols, without needing a central database system. In this scheme, each reader has a unique identifier ri where the index i is used to distinguish between different readers. Each tag has a unique identifier id and a unique secret tj where the index j is used to distinguish between different tags. The secret tj is only known by the tag itself and a central database. A one-way hash function h is known by both the tags and the readers and f (a,b) = h(a||b) in which || is the concatenation operation. It should be noted that the reader does not have access to the secret tj of the tags, but it knows the value of f (ri,tj) for each tag [3]. Details of the the server-less protocol is shown in Fig. 4. Here, © shows the XOR operation. This protocol can resist the DoS, cloning, replay and physical attacks [3]. However, it still has some security issues as explained below:
1. A malicious user can send a request message to the tag after step (3) and force it to generate a new challenge nj. At this point, the reader waits for 
while the tag is expecting a new n’i and ri as the third step.
Fig. 4. The server-less protocol proposed by Tan et al.
2. In step (4) of this scheme,
is sent by the tag. This is a static form of data which can be used by malicious users to track the tag.
3. It is possible that an attacker captures a tag, repeatedly sends the request message along with fixed values of ri and ni, and then stores the 
responses received for different values of nj. This way, the attacker can make a table of responses and use this table in a fake tag to impersonate it as a real one.
Sun et al. Gen2+ RFID Protocol
In order to solve the security issues of the EPCglobal Class-1 Generation-2 (Gen2) protocol, Sun et al. propose an improved version of Gen2 called the Gen2+ protocol [4]. A typical Gen2 tag contains a pseudorandom number generator (PRNG) and takes advantage of a cyclic redundancy code (CRC-16) to protect the message integrity [4]. The Gen2+ protocol uses the same PRNG and CRC-16 tools for privacy preserving. Sun et al. assume that each tag shares an /-word-long random string, called "keypool", with the back-end database. This string is randomly generated by the back-end database and is written into the tag before deployment [4]. A threshold t is also set in each tag to tolerate error bits in the received values and to boost the reading speed. Sun et al. assume that it is possible to design and add an extra Hamming distance calculator to each Gen2 tag [4]. The Gen2+ protocol is depicted in Fig. 5. Although the Gen2+ protocol is easy to implement and inexpensive, it has some security problems as follow:
1. To obtain the EPC data, an attacker needs to be able to provide an acceptable ck’ for each RN16 and check it receives in step (2). It was proven in [4] that if an attacker records approximately 16,384 failed sessions between a reader and a tag and analyzes them, it may be able to track the tag using the additional information provided by the check bits. Moreover, a passive attacker can listen to the communication between the legitimate readers and the tags, and notice the presence of a specific tag, as the EPC data is sent in plaintext in the Gen2+ protocol.
Fig. 5. The Gen2+ protocol proposed by Sun et al.
Table 1. Security comparison of the RFID protocols explained in Sections 2-5
|
Protocol\Attack |
Tracking |
Desynchronization |
Replay |
DoS |
Impersonating a real tag |
|
Henrici-Miiller [1] |
No |
No |
No |
Yes |
No |
|
Challenge-Response Trigger [2] |
No |
No |
Yes |
Yes |
No |
|
Forward Rolling Trigger [2] |
No |
No |
Yes |
No |
No |
|
Server-less Method [3] |
No |
No |
Yes |
Yes |
No |
|
Gen 2+ [4] |
No |
No |
No |
Yes |
No |
Table 2. Complexity comparison of the RFID protocols explained in Sections 2-5
|
Protocol |
Complexity |
|
Henrici-Muller [1] |
 |
|
Challenge-Response Trigger [2] |
 |
|
Forward Rolling Trigger [2] |
 |
|
Server-less Method [3] |
 |
|
Gen2+ [4] |
 |
2. An attacker can eavesdrop on the communication between a legitimate reader and a tag, and extract its EPC data, RN16 and check. The attacker can save this information on a fake tag. The fake tag then accepts any ck’ it receives from the reader and sends its EPC data in step (4) to impersonate itself.
3. An attacker can wait until a tag is interrogated by a legitimate reader and sends its RN 16 and check in step (2). At this point and before the legitimate reader calculates ck’ and sends it to the tag, another request message can be sent to the tag by the attacker. As a result, the tag replies with another RN16 and does not accept the ck’ which was sent by the legitimate reader.
Comparison and Conclusion
In this Section, we compare the five discussed protocols [1-4] from the security point of view. We also compare them from the complexity and computational costs aspect. Table 1 compares the robustness of discussed protocols against tracking, desynchronization, replay, DoS, and impersonation attacks. For each attack, the word "Yes" implies the considered protocol is robust against that attack while "No" means the protocol is vulnerable to that attack. Table 2 compares the computational costs (per successful session) imposed on the tags, for each of the discussed protocols. In this table, we only consider the complexity of implementing each protocol on RFID tags, and neglect the computational cost on the database side. In order to make a fair comparison of the complexity and computational costs, we denote the computational cost of each hash function by a, each random generation by [, each addition, subtraction or comparison by y, each conjugation or concatenation function by A, and each Hamming distance calculation by 0. Finally, interested readers are encouraged to refer to [10] for more details and the complete version of this paper.
