I. Introduction

Due to the properties of low cost, reading without physical contact and writable storage, Radio Frequency Identification (RFID) tags, have many practical applications in our daily life, and further, several new potential applications are under development [27], However, the potential wide deployment of RFIDs also incurs many security concerns, such as privacy, access control, identity protection, un-traceability, etc [3, 29]. It is interesting that anonymity and un-traceability are desirable or even necessary security requirements in many RFID applications, because identifying or tracing specific tags would reveal the identity, the location and the movement of the tagged object and even the person who carries the object.

From the security point of view, we do not discriminate the term server and the term reader when we describe the protocols in the following sections, since the server and the reader are usually resource-abundant devices on which conventional well-studied security protocols can be effectively implemented. Here, we only concentrate on those RFID authentication protocols that considered or claimed to achieve the requirements of anonymity and un-traceability. Those protoc시s like [4, 10, 12, 20, 26, 29, 30] that did not consider or did not well protect the properties of anonymity and untraceability are excluded from the following discussion.

In this paper, we first classify the previous RFID authentication protocols based on their rationales, and then discuss their performance properties. After that, we examine the security weaknesses inherent in some previous protocols based on varying-pseudonym (VP), and finally propose our improvements. The proposed improvements not only enforce the security weakness but also have excellent performance.

The rest of this paper is organized as follows. In Section 2, we classify the previous RFID authentication schemes according to their rationales. In Section 3, we give brief review of some VP-based RFID authentication protocols, and point out their vulnerability against the Denial-of-Service (DOS) attacks. Our countermeasures to the DOS attacks are given in Section 4. In Section 5, we analyze the security and evaluate the performance of the proposed solutions. Finally, conclusion is given in Section 6.

Ⅱ. Classification of RFID authentication protocols Tables

Based on the rationale used by an RFID authentication protocol to identify a tag while protecting the anonymity, we may classify such protocols into the following categories, as depicted in Fig. 1. Note that we only fbcus on the techniques to identify tags while preserving the anonymity, without covering the details of the protocols.

Simple challenge-response approach. In this approach, each tag shares a distinct key kj with the server or the reader. When a reader R probes a tag Ti by sending a random value Nr as a challenge, the tag 7} responds with 力(&, 心), where hQ denotes a secure one-way function that can output commitment on its inputs while protecting the undisclosed input . Upon receiving the response , the server verifies 方(勺, 心)for each potential tag Tj in its database to check whether there is a matched one. This approach allows the server to identify a tag without disclosing the identity to eavesdroppers. Each tag just keeps one secret key, but the server needs to perform the computation for each potential tag to identify the tag. So, the tag's storage space is 0(1) but the computational cost for identifying a tag is O(〃), where n the number of possible tags. The previous protocols proposed in [7, 9, 13, 14, 19, 22, 28, 31, 32] adopt this approach.

Tree-walk approach. In this approach, the tags are organized as a tree, where each leaf node in the tree denotes one tag and each edge in the tree is associated with a key. Fig. 1(b) shows a simple example. In the example, the tag T; holds the key KI and K3, and the tag T2 holds the keys K\ and K4. When a reader probes the tag T2 by sending a challenge Nr , the tag T2 responds with (方(K], Nr ), h(K4, Nr )} on which the server can perform the so- called depth-first-search to identify the tag. This approach requires 0( log n ) key space on each tag and 0( log n) computational cost for identifying a tag. However, the required key space is a serious burden on low-cost tags. One more serious problem of this approach is that once a tag is compromised, other tags that share the same keys on the same key path could be partially traced. The more the number of keys one tag 7} shares with the compromised tag Tj , the more probability the tag could be identified and traced. The protocols proposed in [1, 19] adopt this approach.

Figure 1. Different approaches to protect RFID tag identity

Hash chains approach. One well-known work of this approach is Ohkubo et al's protocol [21]. In this approach, the server and each tag Tx share a distinct hash seed 月 x initially. For each query request, the tag Tx updates x = h(sj x) for i > 1 and responds with x = g(sj x), where hQ and g0 are two different hash functions. This approach achieves the forward secrecy property. That is, if a tag is compromised some day in the futxire, then the past communications from the same tag can not be traced. However, Ohkubo et al.'s original version cannot resist the replay attack [1] and has the problem of poor scalability [2, 3]. In Ohkubo et al/s protocol, the computational cost for identifying a tag is O(nm), where n is the number of potential tags and m is the maximum length of the hash chain. Lately, Avoine et al. [1, 2] proposed an improvement to overcome the replay attack inherent in the Ohkubo et al/s original version. However, their improvement reduces the time complexity at the cost of extra memory required. Varying Pseudonym (VP) approach. In this approach, each tag synchronizes its varying identifier and its internal state with the server. The varying identifier is called pseudonym in [5, 8, 17, 18, 23, 24, 25] and is called metalD in [11, 15, 16]. Here, we all refer to them the pseudonyms. Upon receiving a challenge request, a tag responds with the current pseudonym and the commitment on the challenge and the secret internal state. The server verifies the tag based on the commitment. During the authentication stage, the tag and the server respectively update their pseudonyms and their internal state. In this approach, the pseudonym not only protects the anonymity of the tag but also facilitates the server to 너entife the tag in its database with 0(1) computational complexity, because the server can directly use the pseudonym to locate the corresponding entry in its database and perform necessary computations for this matched entry only. Furthermore, each tag only needs constant quantity of internal values, i.e., 0(1) key space. These excellent features make the VP-based approach more attractive than the other ones. However, due to the synchronization requirement, the VP-based protocols are prone to the de-synchronization attacks (or the Denial-of-Service (DOS) attacks) [7, 8, 17, 18], if an adversary can manipulate the communications to let the tag and the server be out of synchronization. The protocols proposed in [5, 8, 11, 15, 16, 17, 18, 23, 24, 25] adopt this approach. It should be noted that some challenge-response-based protocols like [2, 7, 9] also synchronize the state between the tags and the server. But these protocols do not send a varying pseudonym to facilitate the server to perform fast identification, and therefore, we do not count them in the VP approach.

Ⅲ. Discussions of previous VP-based protocols

In this section, we take several previous VP- based protocols as examples to examine their vulnerability to the DOS attacks.

A. SRAC Protocol

Lee and Verbauwhede [15] proposed a VP-based RFID authentication protocol called the SRAC protocol. The SRAC protocol keeps two sets of records for each tag to resist the DOS attack. However, this strategy does not work.

The SRAC protocol is depicted in Fig. 2. Initially, each tag shares one secret key Key with the server, while the server keeps two sets of keys for each tag: Keyprev is for the previous one and Keycurr is for the potential next one. Upon receiving the query from the reader or the server, the tag computes MetaID=h(Key), which is regarded as pseudonym, and sends it to the server. The server uses the MetalD to search its database. If the MatalD matches one record in its database, then the server generates a random number Rs and checks whether h(Key®Rs) collides with any existing one. If so, the server regenerates a new Rs until h(Key®Rs) is unique. Note that h(KeyeRs) would be used as the next potential key. After that, the server updates the local state as specified in Fig. 2, and sends {Rs, h(Key || Rs)} to the tag. Finally, the tag uses {Rs, h(Key || Rs)} to verify the reader and then updates its local state as in Fig. 2 if the verification process succeeds.

Figure 2. SRAC protocol

Ideally, if an adversary can jam the communications all the time, then the service is, of course, out of function. However, such kind of attack can be easily detected and fixed in practice. We, therefore, exclude such kind of impractical attacks from our discussions. Lee and Verbauwhede [15] had noticed a practical attack: An attacker might intercept the 3rd message in Fig. 2 such that the tag and the server would be out of synchronization if the server only keeps one key for each tag. This practical attack would let a legitimate tag no longer be accessed. Therefore, the SRAC protocol arranges the server keeps two sets of keys for each tag. For this reason, such attack does not de-synchronize the state, because the server still can use the previous key Keyprev to authenticate the tag. However, we find out that the SRAC protocol still cannot resist a sophisticated attack as shown in Fig. 3..

Figure 3. DOS attack on SRAC protocol

DOS attack on SRAC protocol : A potential DOS attack on the SRAC protocol is plotted as follows. Initially, we assume that the tag has Key=\ and the server keeps two sets of keys, Keyprev =1 and Keycurr =1, for the tag. The attack consists of two stages. In the first stage, the attacker eavesdrops the communications between the ta옹 and the server. In this stage, the server generates the random number Rs, and we assume that the value of h{{Key=l)® Rs) to be 2. So, after the first stage, the tag would update Ke尸2, and the server has Key* =1 and Keycurr = 2. In the second stage, the attacker pretends to be the tag and replays the MetaID=h(Keye= 1), where the server will find a matched record with h(Keyprev =1) in its database and generates a new random number Rs . Now, the server would have Keyprev =1 and KeycutT = h(eKey=X)^ Rs ). At this time, Keycurr is supposed to be updated as 3 in our example of Fig. 3, but the tag still holds the old key Key=2. So, the DOS attack succeeds and the tag can on longer be accessed. This attack exploits the weakness of lacking of message freshness checking in the SRAC protocol. Such attack can also apply to the RFID ownership transfer protocol [22], due to the same reason.

B. LCAP Protocol

Lee et al. [16] proposed another VP-based RFID authentication protocol called the LCAP protocol. Like the SRAC protocol, the LCAP protocol keeps two sets of records for each tag. Fortunately, the LCAP protocol further generates a new random number in every authentication request to deter the replay attack stated above. However, a more sophisticated DOS attack still can de-synchronize the tag and the server.

The LCAP protocol is depicted in Fig. 4. The server maintains two sets of records with respect to each tag: one set is the last matched record and the other is the potential next one. Each set contains ID, h(ID), TD and DATA, where ID denotes tag's varying identity, h(ID) takes as tag's metalD, TD is a pointer to the other record of the same tag (i.e., TDprev points to TDcurr, and TDcurr points to TD?心and DATA denotes the other information of the tag. Upon receiving a request challenge r, the tag responds with HaID=h(ID) and hL(ID\\ r), where hL(ID\\ r) denotes the left half substring of h(ID\\ r). Based on HalD, the server first searches its current database to see whether a matched record exists; otherwise, it searches the previous database. If a record is found, the server uses the matched record to check whether 方z(/Z기I r) equals the received one. If the verification succeeds and the matched one is in the current database, the server copies the current record to the previous one, and updates HaID=h(JD®r) and ID=ID®r in the current record. Otherwise, if the matched one is in the previous database, the server directly updates the current ones as HaID=h(ID®r) and ID=ID®r. After that, the server returns hR(ID\\ r), on which the tag can verify the reader/the server and decides whether or not to update its local values as HaID=h(ID £ r) and ID=ID £ r.

Figure 4. LCAP protocol

Obviously, the replay attack plotted in Figure 3 does not work on the LCAP protocol, because each response in Step 2 should depend on the new challenge r. However, a deliberated attack like the one plotted in Fig. 5 can still de-synchronize the server and the tag.

Figure 5. DOS attack on LCAP protocol

DOS attack on LCAP protoc이 : The attack consists of three stages. In the first stage, the attacker just intercepts the message in Step 3 to let the server updates its records as IDprev = ID/ and IDcurr = (we denotes it as ID2) but the tag still has ID}. In the second stage, the reader sends a new challenge r2 and the tags responds with HaIDeh(IDi) and hL(lDi\\ , 2). In this stage, the attacker also intercepts the message in Step 3 to let the server updates records as IDprev = IDi and IDcurr = ID }®r2 (we denotes it as ID3) but the tag still has IDj. In the third stage, the attacker impersonates the reader and replays the request eavesdropped in the first stage to let the tag locally updates its ID as ID = ID ⑥门 which should be ID2. Now the tag and the server are out of synchronization and the DOS attack succeeds. Again, this attack exploits the weakness of lacking of message freshness checking in Step 3 in the LCAP protocol.

C. Henrici-MAuller s protocol

In order to defeat the DOS attacks plotted in Fig. 3 and Fig. 5, the protocol proposed by Henrici and MAuller [11] utilizes a more deliberated technique of using a blinded counter to defeat such attacks.

The Henrici-MAuller's protocol is depicted in Fig. 6. Initially, the tag stores ID, DB-ID, TID, and LST in its memory, where ID denotes the varying pseudonym (VP), DB-ID denotes the corresponding database for this tag, TID denotes the tag's current counter which will be incremented after each query, LST denotes the counter value of the last successful authentication. Meanwhile, the database keeps HID, ID, TID, LST, AE, and DATA for each tag, where ID denotes the VP, HID equals h(ID), TID denotes the last received counter, AE points to the other record entry of the same tag if s느ch an record exists, and DATA points to the tag-related information.

Figure 6. Henrici-MAuller's protocol

For initializing each tag, ID is selected as a random number, TID and LST are another random number with the same value, AE points to null. Upon receiving a query, the tag increments its TID, computes ATID - TID-LST, and sends out the data in Step 2. The server then uses h(ID) to identify the matched record, and uses ATID and its local LST to compute 77D*=A77 +LST. If TID*<TID, then this could be a replay message and the server stops the protocol. Otherwise, the server verifies h (TID©ID). After the success of verification, the server generates a random number RND and computes ID*=RND©ID. Finally, the server updates the two entries such that one entry records the new data and the other entry records the current matched data. Meanwhile, both entries5 TIDs are updated to TID*, and the two AEs are pointed to each other.

Yang et al. [31] had pointed out that, in Henrici- MAuller's protocol, a tag is traceable between two consecutive successful authentications. Avonine and Oechslin [3] also had shown another tracing problem which is not limited to the time period between two successful authentications. Note that Henrici- MAullere protocol can effectively withstand our DOS attacks plotted in previous section. However, a more sophisticated attack can still de-synchronize the state as depicted in Fig. 7.

Figure 7. DOS attack on Henrici-MAller's protocol

DOS attack on the Henrici-MAuller's protocol: A possible DOS attack on Henrici-MAullere protocol is launched as fbliows. Recall that the tag increments its local counter TID for each query. The last bit of TID is either 0 or 1 (each case is of probability 1/2). Assume that the TID of the zth query is of the form ' 지t看『1…지 0 where / denotes the bit length 쟎f the counter and (either 1 or 0) denotes the jth This assumption holds with a probability of 1/2. That is5 놘le last bit of TID for the zth query is 0. So, the next counter TID+1 for the (z+l)-th query will be of the form ' 暫叼시…旳1 \ Our attack is sated in the following and depicted as Figure 7.

In Fig. 7, we only describe the attack for the normal case(A7W=1). Note that 쟈ur attack still works even if The attack consists of two stages. In the first stage, the attacker intercepts the 3헌 message 为-成^…加。’ h(RND®TID@ID)} between the server and the tag, where yo<y</_i denotes the /th bit of RND, In the z*th query, the attacker eavesdrops the communications and intercepts 也e 3rd message such that the server will successfully authenticate 出e tag and has two entries for the tag {(HID, ID认HID« ID")}, where ID is the current matehed pseudonym, and ID' is the potential next one. Note that the tag still holds the old one ID, In the second stage, the attacker pretends to be the reader and 졶ends the (z+l)-th query. At this time, the tag increments the counter TID, i.e., TID will be

changed from 旳_μ勺_1..“目0 to 旳_μ孑_1..应]1. The attacker intercepts the 2nd message from the tag, inverts the last bit of RND, denoted as RND"= 力니J农」…J侦o , and sends {RND", h(RND@TID®ID)} as the server's response to the tag, where the h(RND® TID®IU) is the eavesdropped in the first stage. It is easy to check that the tag will accept the fake message<RND”, h(RND©TID©1D)} and updates its pseudonym ID'- RND"®ID accordingly, because of eRNDeTID+iyQID) 그 h( 刃t刃_i..必孙 ® 而T지 T …珂1 ®ID) = h( 力- DJ …冗而 © 习니叫T…旳 0 W ) = h(RND®TlD®lD). Now the tag's pseudonym ID” is in-consistent with the two entries (JD, 丑)')in the database. The DOS attack succeeds, if the last bit of TID in the first stage is 0. The successful probability for such attack is 1/2 per each attack launched.

The attack exploits the weakness of no strong integrity protection provided in Henrici-MAulleres protocol. The same weakness can also be found in Kim et a//s protocol [14]. Recently, Peris-Lopez et al. [23, 24, 25] proposed a series of ultra-lightweight RFID authentication protocols for very low-cost tags, where only simple bit-wise operations like AND, OR, XOR are supported. However, due to lacking of strong integrity protection provided, these protocols still face the de-synchronization attacks plotted by Li and Deng [17], Li and Wang [18], and Chien and Huang [8].

Ⅳ. VP-based RFID authentication protocols resistant to DOS attack

Based on the analysis in Section 3, we highlight that strong mechanisms for mutual authentication and integrity protection are necessary rationales for resisting various DOS attacks. In this section, we shall propose some practical solutions against the DOS attacks stated in the previous sections. Our solutions preserve the excellent merits of the VP approach, and all of them require 0(1) computational complexity for identifying a tag and 0(1) key space per tag. The countermeasures against possible DOS attacks are given in the following.

A, VP Protocol 1

This solution is modified from Ohkubo et al.'s hash chain-based scheme. This solution not only conquers the weaknesses of the replay attack and the tracing problem in the original scheme. Assume that two one-way hash functions, hQ and g0, and a random number generator are ported on the tags. Initially, each tag shares two random seeds namely as Sq and go=g(s°) with the server. Denote Sj = , for z > 1, as the hashing chain that will be used as the varying shared key between the tag and the server. Denote g( = gC” ), for z > 0, as the VPs. The server maintains two sets of (力, & ) for each tag: one is the last successfully matched set and the other is the potential next one. Initially, the two sets all contain(50, = g(s0)). In the following, R denotes the reader/the server, T denotes the tag, RtT denotes the message is from R to T, and Nr / NT respectively denotes the random nonce from R and T. The following protocol describes the authentication process where the tag's current state is (尖, gi = g(s») and the server's state for the tag is {(sji , gj—1), (% gi)}-

1. #

2. #

Upon receiving the query, the tag generates a new random number NT , and sends (力(% II Nr II Nt) } to the server.

3. #

Upon receiving the data in Step 2, the server first uses the pseudonym gj to identify the tag and uses the matched record in its database to verify the received data, h(st || NR || NT) . If the verification succeeds, the server updates its database by keeping one set of (呂, g;) and the other is (%」, gi+i). After that, the server returns g(q || NR || NT')to the tag who will use its local data to verify II Nr II Nt) . Finally, the server updates its state to (q+i, gj+i) if the verification succeeds.

From the protocol description, it is noticed that even an attacker could intercept the message in Step 3, the ta응 and the server can still authenticate each other using the set (呂, g, ). Of course, an attacker can trace the tag between two successful authentications. However, such kind of tracing does not produce significant practical value.

B. VP Protocol 2

This solution assumes that only one hash function hQ and one random number generator are supported on the tag. Initially, each tag shares one pseudonym IDS and one secret key K with the server. For each tag, the server maintains two records: one is the last matched set and the other is the potential next one. Initially, the two sets all contain the same values. The protocol is described as follows.

1.#

2.#

Upon receiving the query, the tag generates a new random number N T , and sends { IDS, h(K II Nr)®Nt~) , h(K II Nr II Nt) } to the server, where h(K || NR || NT) is regarded as the message authentication code of (K, Nr , NT).

3.#

After receiving the data in Step 2, the server first uses IDS for identifying the matched records in its database, uses the K in the matched record for retrieving NT from h(K || NR)®NT , and finally uses the retrieved value NT and the local K for verifying the message authentication code h(K II Nr II Nt) . If the verification succeeds, i.e., the tag is successfully authenticated, and the server computes a new IDS'^ h{IDS || NT || K) and a new K"= h(K II IDS II Nt) , and updates the two records for this tag in its database such that one record keeps the potential next values (IDS”, fC') and the other keeps the current matched one (IDS, K). The server finally sends the tag the data /z(/Z)S"|| AT"|| K) as a confirmation of the message in Step 2 and of the new data (IDS", K"). Upon receiving the data in Step 3, the tag uses its local values (IDS, NT , K) to compute the new IDS= h(IDS || || K) and the new K= h(K R IDS V Nt), uses the new values to verify the received 五(丑K”|| K) . If the verification succeeds, it uses the new values to replace the old ones.

The above protocols assume that one-way hash function could be effectively implemented on the tags. However, some low-cost RFIDs (like EPC Gen2 tag) still cannot afford the porting of one-way hash functions, and some very low cost tags even cannot support random number generator. Notice that even if we assume two tags share the same pseudonym, the probability that the two tags also 아lare the same key is ne이igible so that the protocol can differentiate and authenticate the two tags.

V. Security analysis and performance evaluation

In this section, we analyze the security of the proposed solutions, and evaluate their performance.

A. Security Analysis

Some possible but potential attacks and security requirements (anonymity, un-traceability, and forward secrecy) on our proposed solutions are discussed as follows:

Mutual authentication/resistance to replay attacks: In our solutions, both the tag and the server will generate new random numbers, and the designated receiver should generate its response based on the secret key and the new challenge. It is easy to check that the proposed solutions can achieve mutual authentication and resist replay attacks.

Anonymity/un-traceability: The VP protocol 1 is modified from Ohkubo et aUs hash chain-based scheme. Upon a query, the tag will respond with a new pseudonym gj = g(s» and 9 is updated as Sj = such that attackers can not identify the tag and cannot trace the tag, since each pseudonym seems random to the attackers. In the VP protocol 2, the pseudonym is updated consequently followed by the secret key K and the blinded random number NT . Therefore, an attacker cannot identify the tag and cannot trace the tag. Of course, an attacker can trace a tag between two successful authentications. However, such kind of tracing could have little practical value.

Forward secrecy: Forward secrecy requires that even if a tag is compromised some day later, the past communications from the same tag cannot be linked. Solution 1 inherits this property from the extra oneway hash gj = g(Si) on the hash chain & =从%。. The inspiration of using two hash functions was first introduced by Ohkubo et al. [4]. The solution 2 also preserves forward secrecy. Even if a tag is compromised some day later, the attacker Can get the values of the current (IDS, K). However, since the computation of the new IDS and the K are respectively defined as WV - h(IDS || || K) and K"= h(K II ZDS II 7盼), the attacker cannot deduce the previous IDS and the previous K from the equations. Therefore, the attacker cannot trace the past communications, based on the current IDS and K. The forward secrecy is preserved.

Resistance to DOS attacks: Our proposed solutions provide strong authentication mechanisms between the server and the tag. Also, they provide strong integrity protection on the communication messages. Therefore, an attacker cannot de-synchronize the state by modifying the messages without being detected. Actually, an attacker can intercept the 3rd message in the two solutions to deter the tag from updating its state. However, since the server always keeps two sets of records for each tag: one is the potential next one and the other is the last matched one. So, the server can still authenticate the tag under such condition.

B. Performance Evaluation

In our proposed VP protocol 1, the tag is required to support two hash functions and one random number generator. In our proposed VP protocol 2, the tag only is required to support one hash function. To identify a tag, both protocols only need 0(1) computation, because the server directly uses the pseudonym to identify the potential tag in its database and performs necessary matched entry only. Our solutions only require three interactions to achieve mutual authentication. The features of distinct approaches are summarized in Table 1. Because the difference of the numbers of steps among distinct approaches is not significant, and the number of steps highly depends on the design of the protocol but not the approach adopted, we, therefore, do not count the number of steps (the communication complexity) in Table 1. Table 2 summarizes the properties of some well-known VP-based protocols. From Table 2, one can see that our proposed protocols out-perform the other VP-based schemes in the security respect and preserve the low storage requirement and high computational performance of the VP approach.

Table 1. Summaries of features of distinct approaches

Table 2. Comparisons among various VP-based protocols

Ⅵ. Conclusion

In this paper, we have discussed the features of different approaches to anonymously authenticate RFIDs and have shown the possible and potential DOS attacks on some well-known previously proposed VP-based protocols. We also have proposed two VP-based protocols to enforce the security weaknesses inherent in the previous work. Our solutions require only 0(1) computational cost to identify a tag, and need only 0(1) key space on the tag. These excellent performances make them very attractive to many RFID applications.