An Improvement over a Server-less‎ RFID Authentication Protocol

Published Online December 2014 in MECS DOI: 10.5815/ijcnis.2015.01.05

Radio Frequency Identification (RFID) is a wireless technology, which is used to automatic identify remote objects embedded with RFID tags [1]. RFID can be used in a great variety of applications such as supply chain management, transportation, livestock management, animal tracking, human implants, library, and so on [2].

In an RFID system, the cost of the tags is low, which implies that the tags have very limited computational capabilities and storage. General-purpose security protocols cannot be applied directly to the RFID system [3]. The low cost demanded for RFID tags forces them to be very resource limited. Typically, they can only store hundreds of bits, have 5-10K logic gates, and a maximum communication range of a few meters. Within this gate counting, only between 250 and 3000 gates can be devoted to security functions. It is interesting to recall that for a standard implementation of the Advanced Encryption Standard (AES), 20-30K gates are needed [4].

Therefore, these protocols mostly use lightweight primitives known to be implementable on RFID tags. Additionally, power restrictions should be taken into account, since most RFID tags in use are passive. Furthermore, these systems are unable to store passwords securely because they are not tamper-resistant at all[4].

According to the cryptogrophic primitives used in the RFID authentication protocols, they are usuelly classified into four groups, based on the structure of the protocol. The first class contains the protocols that apply ordinary cryptographic functions, such symmetric encryption, cryptographic hash function, or even the public key algorithms. The second class are protocolas that use random number generator and one-way hash functions. The third class refers to those protocols that apply random number generators and cyclic redundancy code(CRC) checksum, which sometimes are called as “Lightwright” protocols. The last class, are the “Ultra Lightweight” protocols. These protocols apply simple bitwise operations such as XOR, AND, OR, etc.

According to the components used in a RFID system, they are divided into two categories. The first category is based on a back-end server [5, 6, 7]. In back-end server based RFID systems, the reader has to communicate with the back-end server containing information of all readers and tags through a secure channel in order to get the required data from a tag, Fig 1.

While the back-end server approach provides security and privacy protections, it is dependent on a reliable connection between an RFID reader and the back-end database [8]. The authentication protocol should be provided, even if the connection between the reader and the back-end server was not established.

Several studies have recently been made on authentication protocol for RFID tag and reader without back-end server [9, 10, 11, 12]. Fig 2 shows the process of the authentication process without the back-end server.

Fig 1: Server-Based RFID protocols.

In server-less protocols, an abstraction of information of a particular reader and all tags are kept in every reader. Obliviously these protocols are more practical, since the assumption of the existence of a secure communicating channel between reader and server is not needed here.

Fig 2: Server-less RFID protocols.

In 2010 Hoque et al. suggested a server less, untraceable authentication, and forward secure protocol for RFID tags [13]. Hoque’s authentication protocol safeguards both reader and tag against attacks as often as possible without the intervention of back-end server.

After that, in 2014 Deng et al. showed that the Hoque’s authentication protocol is vulnerable to attacks of data desynchronization [14], and proposed an improvement over Hoque’s authentication protocol and claimed that it can withstand the attack of data desynchronization.

However, our analysis shows that Deng’s protocol is still vulnerable to data desynchronization attack, when the protocol is performed for more than two runs. We propose an improvement over Deng’s et al. protocol, which is secure under desynchronization attack.

In the rest of this paper, first in Section II a brief review of Deng’s authentication protocol is presented. Then after showing the vulnerability of their protocol in Section III , we describe an improvement over this protocol in Section IV . After that in Section V , we discuss the security requirements of our protocol, and in Section VI , the performance evolution of our protocol is introduced. Finally, conclusions will be drawn in Section VII .

• •   ||: Concatenation operation.

• •   Ф: Exclusive-or operation.

• •    Rand i : Random number generated by reader R i .

• •    Rand j : Random number generated by tag T j .

• •    r i : Identifier of reader R i .

• •    t j : Secret value of tag T j .

• •    n i :  Message generated by reader  R i   for

authentication.

• •    n j :   Message generated by tag  T j    for

authentication.

• •   Seed Tj : (h(r i , t j )) the secret value shared between

reader R_i and tag T j .

• •   Seed PTj : The previous secret value stored in

reader R i .

• •    L i : Downloaded list of tags information from CA by reader R i where,

  L =

  i

  
  

SeedT1 , SeedPT1Seed , Seed

Tn        PTn

• 2) Deng’s Protocol description

Deng et al. protocol, is a server-less RFID protocol and the RFID reader R_i stores contact list L_i and an identifier r i in its nonvolatile memory. The contact list L i comprises information about the RFID tags that R i can access to and each tag contains the current seed Seed Tj , and the previous seed Seed PTj . The protocol is shown in Fig 3.

In a general authentication process, the current seed of T j , will be utilized to accomplish the mutual authentication between the reader and the tag. Nevertheless, if the reader fails to look up the current seed for the desynchronization of the shared secret, it may use the previous seed to complete the authentication.

• II.    Deng’Ѕ Authentication Protocol

In this section we review Deng’s authentication protocol [14].

• 1)    Notions and assumptions

In the system, all tags and readers have knowledge of a function M(...) and a pseudorandom number generator P(...). P(...) is a low cost random number generator which applies to the RFID system. M(...) and h(...) are assumed as an one way hash functions. Each RFID reader R has a contact list L and a unique identifier r. L and r are obtained from a Certificate Authority (CA). In addition, each tag T includes a unique secret t and a unique identifier id. Subscripts are utilized to describe a particular T or R and their variables. Other notations are listed below:

• III.    Vulnerability of Deng’S Protocol

Deng improved Hoque’s protocol to troubleshoot primary protocol from desynchronization attack [6]. In this section we claim that, this protocol is secure under desynchronization attack only for one run, but it is vulnerable to this attack when the protocol is performed for more than a single run.

The main goal of this attack is to ruin the synchronization between a legitimate reader and a tag, in order to prevent them from successfully communicating with each other in the latter communications. Moreover, this attack can be carried to prevent the reader from successfully updating the information (identification for instance) of a tag after a successful communication.

• 1.    R_i       T j : request , rand_i

• 2.    Tj : n j = P(seed_T ⊕ (randi || randj))

• 3.    R_i        T j : n j , rand j

• 4.    R_i : n_i = rand_i

• 5.    for all m from 1 to n

• 6.    Let n m = P(seed m ⊕ (rand i || rand j ))

• 7.    if (n_m == n j ) then

• 8.    Let s = M(seed m )

• 9.     n i = P(s)

• 10.   seed_m = M(s)

• 11.    R i         T j : n i

• 12.    else Let n m = P(seed m ⊕ (rand i || rand j ))

• 13.    if (n m == n j ) then

• 14.   Let s = M(seed mp )

• 15.   n i = P(s)

• 16.   seed m = M(s)

• 17.   Ri —> T j : n i

• 18.    T j : Let k = M(seed_T j )

• 19.    Let a = P(k)

• 20.    if (a == n i ) then

• 21.   seed Tj = M(k)

• 22.    else

• 23.   Reader is not authorized

or is an adversary

Fig 3: Deng et al. Protocol

Our proposed desynchronization attack uses two runs. Due to the protocol, before starting the protocol the following values are stored in Reader R_i and Tag T j database:

R i : Seed Tj , Seed PTj

T j : Seed Tj (which is equal to Seed PTj for the first time).

In which Seed_T j is supposed to store the latest value of shared agreed seed between reader R_i and tag T j , and Seed_PT j is a constant for the first value of seed, obtained from CA since the beginning of construction. (In Deng’s protocol the value of Seed PTj is not supposed to change through different runs.)

Assume that Reader and Tag perform a successful run, then the following values are replaced in Reader’s and Tag’s databases:

R i : Ѕeed’ Tj , Seed PTj

Tj: Ѕeed’Tj in which Ѕeed’Tj is a fresh value.

In the second run of the protocol reader R_i sends request to tag T j and T j replies with the value of Ѕeed’_T j . The reader R i authenticates the tag T j since the value of Ѕeed’ Tj is the same in both participant’s databases, then R i updates the value of Ѕeed’ Tj to Ѕeed’’ Tj and sends the fresh value to T j .

In line 11 or 17 of the protocol (which the Reader is responding to the Tag) an adversary can change the value of message n i or prevent T j receiving n i . Thus, the reader

R_i has replaced the Ѕeed’_T j with Ѕeed’’_T j while the tag T j has the previous value. Therefore, the shared secret between the tag T j and the reader R i is not identical, which will threw the RFID system into confusion (Fig 4).

After a successful data desynchronization attack, since adversary makes the reader R i and the valid tag T j share the different secrets. The attack destroys the availability of the protocol.

Reader R i	Tag T j
Seed TJ   Seed PTJ 1 C C	Seed TJ I e C e TJ
Beginning: Both side’s information are sync.
Seed TJ   Seed PT J 1 U 1 .J C J	Seed PT J i                      i 1 U 1
After one successful run: Seed PTJ is fixed for future use and Seed TJ Is same both sides.
Seed TJ   Seed PTJ ।                      i                      i 1 U 2 -J C	Seed PT J ।                          i 1 U 1
In second Run: Adversary prevents recieveing the update message (U2) by Tag T j . Tag and Reader are not sync and can not communicate with eachother any more.

Fig 4: Desynchronization attack on Deng’s protocol.

• IV.    Improved Protocol

The security gap which led to de-synchronization attack in Deng et al. protocol, is the fixed value, C, in reader’s database. The goal of storing this value is to make further communications possible even if in a specific run the updated message is not received by tag. The idea is a common idea to solve these kind of desynchronization attack (e.g. [15], [16], [17]) but it has not established correctly in [14] and as described in previous section it is still vulnerable to this attack.

In order to settle the data de-synchronization attack issue, the reader ought to update the value of SeedPTj to latest authorized value in every successful run of the protocol. If the value of SeedPTj changes dynamically in every run, even if an adversary interrupt the message ni or prevent ni to be received by the tag the values of SeedPTj in reader’s database and ЅeedTj in tag’s database are identical yet and they still can be authorized by each other ( Fig 5).

Therefore, in improved protocol reader sends the request and generated nonce, and tag responses with its seed and nonces (both reader’s nonce and its own generated nonce). Reader after receiving this message, extracts tag’s seed and checks if it is equal to latest updated value from last run of the protocol.

Reader R i	Tag T j
SeedTJ  Seed PTJ 1 C "I C -J	SeedTJ I e C e TJ
Beginning: Both side’s information are sync.
SeedTJ  Seed PTJ 1 U 1 -J C -J	Seed PTJ 1                          1 1 U 1
After one successful run: Seed PTJ is fixed for future use and SeedTJ Is same both sides.
SeedTJ  Seed PTJ 1   U 2 J U 1	Seed PTJ i                      i 1 U 1 J
SeedTJ  Seed PTJ	Seed PTJ
U i+1      U i	।                      i 1 U i
In every Run: Even if adversary prevent recieveing the update message (U i+1 ) by Tag T j , Tag and Reader can authenticate eachother by Ui.

Fig 5: Resistance against desynchronization attack of improved protocol.

In case of equality reader authenticates the tag, and otherwise it check whether it is equal to the latest value which is accepted in last successful run of the protocol.

The rest of the protocol is the same as the original one except the update step. In improved protocol the value of SeedPTJ will update to last accepted SeedTJ. Our improved protocol is shown in Fig 6.

1.	Ri       T j : request , randi
2.	Tj : n j = P(seedT ⊕ (randi || randj))
3.	R         T j : n j , rand j
4.	Ri : ni = randi
5.	for all m from 1 to n
6.	Let n m = P(seed m ⊕ (rand i || rand j ))
7.	if (nm == n j ) then
8.	seed PTj = seed Tj \\Updating the old seed
9.	Let s = M(seedT j )
10.	n i = P(s)
11.	seed m = M(s) \\Updating the new seed
12.	R i         T j : n i
13.	else for all m from 1 to n
14.	Let nm = P(seedPT j ⊕ (randi || rand j ))
15.	if (nm == n j ) then
16.	Let s = M(seed PTj )
17.	n i = P(s)
18.	seedm = M(s) \\Updating the new seed
19.	R i         T j : n i
20.	T j : Let k = M(seed Tj )
21.	Let a = P(k)
22.	if(a == n i ) then
23.	seed Tj = M(k)
24.	else
25.	Reader is not authorized or is an adversary

Fig 6: Improved protocol

• V.    Security Analysis

In this section, we analyze our protocol against different types of attacks. For each attack, we first give a brief description of the attack, and the common assumptions about the adversary. It is followed by an explanation of how the protocol defends against the attack. We denote the adversary as A , and a legitimate reader and tag as R_i and T j respectively. A fake tag j impersonating the real tag j is depicted as Ť.

Basic attack This attack occurs when A can access the information of tag. Under this attack, we generally assume that A has a list of targeted RFID tags. Our protocol is not vulnerable under this attack because consider for example, the tag T j attached to a valuable container in a warehouse. A then queries every tag in the warehouse to decide the most valuable one to steal. In our protocol, each time any reader queries T j , T j generates a new response P(seed_T ⊕ (rand_i ||rand j )) for authentication. Thus A cannot identify which RFID tag is on his list. This protects the privacy of the tag.

Tracking Under this attack, A tries to distinguish T j from other RFID tags over time. For example, T j could be attached to a passport. By repeatedly querying with a value that yields a consistent reply, A will be able to track the movements of T j over time.

Under our protocol, A can reuse the same nA and randA for every query, but cannot predict the random randj generated each time by Tj. In the protocol, we return the entire P(seedTj⊕ (randi || randj)).Since randj is a random number chosen by the tag for each query, A learns nothing from repeated queries.

Cloning Under this attack, A will usually first query T j and obtain a response. He then places the response on a fake RFID tag, Ť j . By creating fake RFID tags that contain the responses of real RFID tags, A attempts to pass off his counterfeits as legitimate. A succeeds if R_i believes that Ť j is T j . Under our protocol, T j will return a different response based on the random n_i and rand_i provided by R_i each time. Since A cannot predict the random rand i generated each time by R i , the response that A obtains from T j will not be the same. Thus A cannot create a Ť j that can fool R i .

Eavesdropping In this attack, A captures all the messages transferring between readers and tags in RFID system, which means that A is able to observe all interactions between R_i and T j . By this ability A tries to use the data to launch any of the three attacks mentioned above.

In our protocol, every transaction between R i and T j begin by both parties generating a different n i and n j . An A eavesdropping on the communication observes a different query and a different response each time, even if R_i is querying the same tag T j . Thus, our protocol prevents A from using eavesdropping to launch a basic privacy attack, tracking attack or cloning attack.

Physical attack We consider two different flavors of physical attack. First, we consider A compromising R i . The adversary will know the contents of L i , as well as rand i . He will therefore be able to impersonate R i and obtain data from tags T₁,...,T_n . The goal is to prevent A from using the knowledge to create counterfeit tags. Let T j be in L_i, and A wishes to create a counterfeit tag Ť j that can fool another authenticated RFID reader R_x. A knows M(r i ,t j ) and id j from L i . To create Ť j to fool R x , A has to be able to derive M(r x ,t j ). This is because each M(.,.) value in the access list is different for every RFID reader. R i will have M(r i ,t j ),and R x will have M(r x ,t j ). Thus A cannot substitute his M(r_i,t j ) and id j into Ť j . Since M(.,.) is irreversible, A cannot derive t j from M(r_i,t j ).

Next, we consider A compromising tag T j . The adversary will now be able to create a fake Ť j that can fool the honest R i . We want to prevent A from creating another tag that can fool R i . We let this other tag be T x , and assume that T x is inside L i . Since A has compromised T j , we assume that A knows any information that R i passes to T j . To create T_x to fool R_i, A has to be able to generate the correct M(r_i,t_x). However, each RFID tag has a unique secret t. Thus A knowing t j cannot derive t_x. Therefore, A cannot create a fake T_x to fool R_i [8].

Denial of service (DoS) attack In DoS attacks A tries to find a way to fail target tag from receiving services. To launch a DoS attack, A sends a large number of requests to the backend server to overwhelm the server. This results in a legitimate Ri being unable to access the database to obtain information about the tag. Under our solutions, a reader only needs to contact the server once to obtain an access list Li .The reader is then able to interact with RFID tags without further interaction with the server. A DoS attack under our schemes will not affect readers that have already been authenticated.

Desynchronization attack In desynchronization attack, which is one kind of DoS attacks, the shared secret values among the tag and the reader are made inconsistent by an A . Then, the tag and reader cannot recognize each other in future and tag becomes disabled. For protocols that require some synchronization between central database and tag, a common defense against DoS attacks is to require Tj to change its value only after receiving some confirmation generated by the database[18, 19]. Under our protocol the value of Seed PTj for reader R i changes dynamically in every run, even if an adversary changes the message n_i or prevent n_i to be received by the tag the values of Seed_PT j in reader’s database and Seed_T j in tag’s database are identical and they still can be authorized by each other. Thus our protocol is guaranteed under this attack.

• VI.    Performance Evolution

RFID technology requires that the RFID protocols not only to be secure, but to be practical and efficient. In this section, we evaluate the performance of our protocol by estimating its communication cost, the number of needed operations and its needed space.

The overall communication costs of our authentication protocol are similar with the overall communication costs of Deng’s authentication protocol. Considering communication cost, assuming that both reader and tag id_s have the same length, the authentication protocol requires 2|n| + 2|id j | + m bits where |n| is the length of the random numbers rand_i and rand j .

Next we study computational cost of protocol. Ѕimilarly to Deng’s protocol the improved authentication protocol contains two hash functions, M(.) and h(,), but the reader get L i from CA, and h(,) is computed by CA. Therefore the cost of the protocol may be determined based on the computation of M(.) function. In our protocol it can be seen that M(.) is computed twice. The cost for our protocols is higher than alternative protocols [20, 21, 22], which require the tag to perform only one hash function.

Now we study the required space of the protocol. An RFID tag in improved scheme just stores its one seed for every RFID reader in the system. Certainly a tag still requires other memory space for communication and computation. However, computation in the improved protocol only contains hash operation and only one value utilized as authentication needs to be stored, so the required memory space is very limited [6].

• VII.    Conclusion

RFID authentication systems are rapidly developing in different areas. But, designing a secure authentication protocol for low-cost RFID tags is still a challenging problem. In this paper the cryptanalysis of a recent lightweight RFID authentication protocol is proposed, and we showed that the improved RFID authentication protocol proposed by Deng is still vulnerable to attack of data desynchronization.

Our Improved protocol is resistant against data desynchronization attack, and it satisfies the required security requirements, such as privacy protection, tracking attack resistance, cloning and physical attack resistance. Our improved protocol is lightweight which makes it suitable for the low-cost RFID environment.