A Low-Cost RFID Authentication Protocol Against Desynchronization with a Random Tuple

Abstract

Radio frequency identification (RFID) technology will become one of the most popular technologies to identify objects in the near future. However, the major barrier that the RFID system is facing presently is the security and privacy issue. Recently, a lightweight anti-desynchronization RFID authentication protocol has been proposed to provide security and prevent all possible malicious attacks. However, it is discovered that a type of desynchronization attacks can successfully break the proposed scheme. To overcome the vulnerability under the desynchronization attacks, we propose a low-cost RFID authentication protocol which integrates the operation of the XOR, build-in CRC-16 function, permutation, a random tuple and secret key backup technology to improve the security functionality without increasing any cost than the utralightweight protocols. The analysis shows that our proposal has a strong ability to prevent existing malicious attacks, especially the desynchronization attacks.

1 Introduction

Radio frequency identification (RFID) is a technology for automatic identification of objects and people [1]. There are many application scenarios to employ the RFID technology with aims to promote the production efficiency in the areas such as agriculture, industry, transportation, education, military and defence, and government, etc. With much more and more applications, the RFID technology will become one of the most popular technologies to improve economy and social lives in the near future. A RFID system contains three types of key elements: RFID tags, RFID readers, and a back-end database server which has the ability to identify objects with increased speed and accuracy. The reader is used to query the tag identify (TID) and forwards it to the back-end server. Once the tag is found valid, the back-end server will check the information kept by the tag for further processing. The RFID tags have experienced two generation of the development. And it is widely believed that Generation 2 (Gen2) tags are the major tags used currently for the development of RFID applications because the effective reading range is relatively larger [2]. In a typical RFID system, the information transmitted in the air between the tag and the reader could easily be intercepted and eavesdropped due to its radio transmission nature, which indicates that the security issues will be the major concerns to block further development of the RFID applications, especially, in the military area or some other secrecy sensitive areas.

Currently, the RFID security and privacy protection mechanisms mainly can be classified into two major categories: physical approaches and encryption mechanisms and protocols. The proposals on the physical security mechanisms for the RFID tags mainly include the Faraday Cage [3], kill command mechanism [4], the locker tag [5]. Further research results indicate that although the physical security approaches can achieve some degree of security, it will cause the increase of the cost of an entire RFID system. On the other hand, the encryption technology based security protocols have shown to be more attractive to the development of the RFID systems, which will be soon widely adopted. The encryption technology based security protocols can be classified into four classes in Chien [6]. They are full-fledged, simple, lightweight and ultralightweight RFID authentication protocols.

In terms of simple protocols, the hash-Lock scheme has been introduced in [3, 7] used $metaID =\hbox {H}(K)$ to hide the real ID of a tag, where $K$ is the shared secret between the tag and the back-end server, H is a one-way hash function. Although this scheme offers certain level of reliability at a low cost, an adversary can easily track the tag via its metaID and thus the transaction secret or privacy would be at risks. Furthermore, since the key shared between the tag and the back-end server is sent in plaintext, even an inactive adversary can easily sniff the transmission channel to spoof the tag information. The hash based ID variation protocol in Henrici and Muller [8] is similar to the hash chain protocol, which uses a random number to refresh the tag identifier dynamically. The random number increases after each successful authentication session so that this protocol is able to defend against the replay attacks. The protocol can also resolve the location attacks by making the ID of a tag randomized in every interrogation. It is also reliable to prevent data loss because it can restore the data from the previous record. Unfortunately, this protocol cannot resist the man-in-the-middle attacks, the intermittent position tracing attacks defined in Gao et al. [9], and the desynchronization attacks reported in Zhou et al. [10], where a novel RFID security protocol (RIPTA-DA) has been designed, which employs a stochastic dynamic multi-key mechanism to encrypt the information and employs the noise disturbance technology to overcome the vulnerabilities under the both attacks.

On the other hand, in terms of lightweight protocols, Hopper and Blum (HB), HB+, HB++ protocols have been proposed in [11–14] as a family, which has used the learning parity in the presence of noise (LPN) to provide stronger security functionality. However, it is found that if an aggressor replays challenges on a tag with $\hbox {O}[(1-\eta )/(1-2\eta )^{2}]$, where $\eta$ is a noise parameter. Each tag has a noise generator, by which the probability of generating a noise is $v = \{ 0, 1 | \,\hbox {prob}\,[v = 1] = \eta \}, \eta \in (0, 1 / 2)$, where $v$ is a vector, which is a binary string, while $\eta$ is the probability of the number of “1” in the binary string $v$ times. It is possible to obtain the value of $a \cdot x$, where $\cdot$ is a point multiplication operation, with very high probability. A synchronization-based communication protocol for RFID devices has been presented in Duc et al. [15]. The protocol targets to protect the Gen-2 RFID tags which support only simple cryptographic primitives like pseudo random noise generation (PRNG) and cyclic redundancy check (CRC). It can prevent the cloned tags and the malicious readers from the impersonating attacks and abusing legitimate tags, respectively. In addition, the protocol is able to provide that each RFID tag emits a different bit string (pseudonym) when receiving each query from different readers. Therefore, it makes possible for the tracking activities and personal preferences of a tag’s owner impractical to provide the user’s privacy. It’s possible for a malicious reader can get $M_{1} =\hbox {CRC}(\hbox {TID}|| r_{1})\oplus K_{i}$, and $M_{2} =\hbox {CRC(TID}|| r_{2})\oplus K_{i}$, where $k$ represents string concatenation and $r_{1}, r_{2}$ are nonce values. In this way, the attacker can identify a tag by the following way $M_{1}\oplus M_{2} = \hbox {CRC(TID}|| r_{1})\oplus \hbox {CRC(TID}|| r_{2})$. Once the tag is queried by a valid reader which causes the key update, the attacker can restart the attack. Although the protocol is defective, the application of CRC function in the design has opened a new way to design a low cost RFID system. In Doss et al. [16, 17], three solutions have been proposed for the authentication and privacy in the RFID systems employing the quadratic residues technology. But due to the usage of high cost hash functions and complex encryption algorithms, they are not suitable to the low cost RFID systems.

In terms of ultralightweight protocols, a minimalist mutual-authentication protocol $(\hbox {M}^{2}\hbox {AP})$ for low cost RFID tags has been proposed in Lopez and Castro [18] using some simple logical operations such as XOR, OR, AND, and sum of modulo. A tag and a reader can share a pseudonym session identifier (SID) and four keys. During each session, the reader generates two random numbers. By this protocol, the tag verifies the reader by checking the value extracted from the first two messages. The tag then responds to the reader if it is correct. Both SID and four keys must be updated after each session to provide forward secrecy. Recently, a desynchronization attack to break the $\hbox {M}^{\mathrm {2}}\hbox {AP}$ protocol has been reported in Bárász et al. [19]. By this attack, an adversary could discover the tag’s identity and some shared secrets in two rounds of eavesdropping. Furthermore, the attacker can undertake desynchronization attacks by using the known keys.

An interesting lightweight authentication protocol has been proposed providing strong authentication and strong integrity (SASI) for the low cost RFID systems in Chien [6]. An index-pseudonym, the tag’s private identification (ID), and two keys $(k_{1}, k_{2})$ are stored both on the tag and in the back-end database. Simple logical functions such as bitwise XOR, bitwise AND, bitwise OR, addition and left rotate function are required on the tag. Additionally, a PRNG is required at the reader. The proposed scheme is ultralightweight, while the active tracking attacks are possible among two valid readers because the IDS in SASI is a static value. It is also shown that a desynchronization attack on the SASI scheme can succeed with at most 96 trials [20]. Gossamer protocol has been introduced in Peris-Lopez et al. [21], which has a very good security performance to keep the confidentiality and integrity of data in the authentication procedure with a forward security by a rotation operation, which is a combined function with circular shift function and the Mixbits function. Gossamer protocol has shown to have an extremely lightweight nature, as only bitwise right shift and additions functions have been employed. The abovementioned protocols have certain security functionality equipped with simple operations at a low cost, while they are not able to resist some type of the desynchronization attacks [22].

A new ultralightweight RFID authentication protocol with permutation (UAPP) has been proposed in Tian et al. [23]. It has avoided using unbalanced OR and AND operations and has introduced a new operation named permutation. A tag involves only with three operations: bitwise XOR, left rotation and permutation. The performance evaluation illustrates that since the UAPP scheme only uses fewer resources on the tags in terms of computation operation, storage requirement and necessary communication, the total cost of the UAPP scheme is much lower. The security analysis in Tian et al. [23] has claimed that the UAPP scheme can resist to all possible existing attacks. However, one type of the desynchronization attacks has been found to be able to break the protocol. Based on the solution in Tian et al. [23], we have proposed a security authentication protocol to prevent the desynchronization attacks with CRC function and permutation function to improve the security functionality of the authentication protocols without increase any hardware cost in Paolo and Santis [24].

It is obvious that the simple authentication protocols can effectively resist various malicious attacks by using complicated hash functions resulting in a higher cost. Although the lightweight authentication protocols have not been equipped with complex hash functions, the security cost is relative higher due to the random number generator introduced. On the other hand, the security functionality of the ultralightweight RFID authentication protocols are questionable. In this paper, the anti-desynchronization RFID authentication protocol reported in Zhou et al. [10] will be reviewed to explore its vulnerability under one type of the desynchronization attacks. Further, to overcome the vulnerability under the desynchronization attacks, we propose a low cost RFID authentication protocol authentication protocol with a random tuple (APRT) which integrates the operation of the XOR, the CRC-16 function, the permutation function, random tuples and the secret key backup technology to improve the security functionality without increasing much cost than the existing utralightweight protocols. The analysis shows that our proposal has a strong ability to prevent the existing malicious attacks, especially the desynchronization attacks.

The remainder of the paper is organized as follows. The scheme in Zhou et al. [10] is reviewed to explore its vulnerability under one type of the desynchronization attacks in Sect. 2. In Sect. 3, the $\hbox {UP}^{2}\hbox {RT}$ scheme is presented to overcome the flaws in the scheme in Zhou et al. [10]. The security analysis on the $\hbox {UP}^{2}\hbox {RT}$ scheme is presented in Sect. 4. Then, in Sect. 5, the performance evaluation on the proposed $\hbox {UP}^{2}\hbox {RT}$ is demonstrated in terms of the computation operation, the storage requirement, the communication cost and the capability to resist malicious attacks. Finally, the paper is concluded in Sect. 6.

2 Vulnerability in the Protocol in Zhou et al. [10]

A desynchronization attack is an active malicious attack with aim to make the attacked RFID system lose desynchronization without an ability to be authenticated as normal. The RFID ultralightweight protocols are mainly used for special circumstances, such as library, warehouse and hospital. By the desynchronization attacks, the attacker can make the library, warehouse and hospital out of working as normal, where the system could be paralyzed under the desynchronization attacks. We have also found some references such as [9, 10, 20, 22, 23, 25, 26] to address against the desynchronization attacks. So we believe that the research results against the desynchronization attacks are significant.

There are two types of the desynchronization attacks, which are retransmission desynchronization attacks and bit tamper desynchronization attacks [6]. An retransmission desynchronization attack refers to the interception action in the secret key updating phase of authentication process. Suppose the database send a message with variables to a tag, then the database update the secret key. An attacker could interrupt the message so that the tag will not be able to update its variables, which will cause that the secret keys at the database and the tag are not able to be synchronized. A bit tamper desynchronization attack is that, for example, the database will reply with A, B, C to the tag. An attacker’s goal is to forge a tuple ($\hbox {A}', \hbox {B}', \hbox {C}'$) that is accepted by the tag. The attacker makes $\hbox {A}^{\prime } = \hbox {A}^{*}$ where $\hbox {A}^{*}$ is the flip of the kth bit in $\hbox {A}, \hbox {B}' = \hbox {B}$, and $\hbox {C}' = \hbox {C}^{*}$, where $\hbox {C}^{*}$ is the flip of the kth bit in C. Then, the attacker replies the tag with ($\hbox {A}', \hbox {B}', \hbox {C}'$). In this way, $\hbox {C}'$ always flips and C$^{{*}}$ from the attacker will pass the verification process of the tag. In the next authentication, when the reader tries to read the tag, the tag can be found in the database. But the reader will be rejected by the tag because the secret key in the tag is no longer synchronized with the database.

In order to show the vulnerability of the protocol in Zhou et al. [10] under the retransmission desynchronization attacks, we need first to review the operations of the protocol as shown in Fig. 1.

Fig. 1

The operation of the authentication protocol in Zhou et al. [10]

2.1 Review the Protocol in Zhou et al. [10]

• Step 1: Reader $\rightarrow$ Tag(Challenge Message): First, the reader generates a random number $r$ and challenges the tag with it.

• Step 2: Tag $\rightarrow$ Reader(Responding Message): While receiving the challenge, the tag responds the reader with $IDS = H( Key _{i}),H(T_{i}\oplus r)$ and $m$-$left = H$-$left ( key _{i}\oplus r\oplus H(T_{i}\oplus r)\oplus C)$ where m-left is the left part of the output of the hash function H, C is a constant.

• Step 3: Reader $\rightarrow$ Back-end Database(Forwarding Message): While receiving the response from the tag, the reader forwards the received authentication message r, $IDS _{i}$, m-left, and $H(T_{i}\oplus r)$ to the back-end database.

• Step 4: Back-end Database $\rightarrow$ Reader(Authenticating Tag Message): After receiving the authentication message from the reader, the back-end database needs to complete the authentication and respond $R, { n}$-$right ={ H}$-$right ( key _{i}\oplus R\oplus H(T_{i}\oplus r))$ to the reader. If the authentication succeeds, the back-end database updates secret key.

• Step 5: Reader $\rightarrow$ Tag(Authenticating Reader Message): The reader will send $R$ and n-right to the tag. While receiving the reader’s authenticating messages, the tag retrieves the shared key from its local storage and calculates the local n-right $=$ H-right $(key_{i}\oplus R\oplus H(T_{i}\oplus r))$. If the value of local n-right equals to the received one, the tag authenticates the reader successfully and updates the shared $key_{i+1}$ to $Key_{i}\oplus n$-left. Otherwise, the tag will consider that the reader is invalid and will not update the shared key.

2.2 Vulnerability of the Protocol

In the operation of the protocol, it is assumed that there is a synchronized tag. We call the legal reader which controlled by the adversary as the malicious legal reader. An adversary is able to trigger a malicious legal reader which can generate a specified random number to attack the tag. The notations used in this section are listed in Table 1.

Table 1 Notations

The fist step of the attack to the protocol is shown in Fig. 2. The adversary can interrupt $r$ at step 1, $IDS _{i}$, m-left, $H(T_{i}\oplus r)$ at step 2 and $R$, n-right at the step 5 in Fig. 1. Let r as r $', IDS _{i}$ as $IDS _{i}'$, m-left as m-left $'$ and $H(T_{i}\oplus r)$ as $H(T_{i}\oplus r)'$ . Then the adversary holds up the messages which is sent to the tag at the step 5 in Fig. 1. Since the tag is not able to receive the messages form the reader, it will not update its variables at the last step. But the database has updated its variables as follows. (a) $IDS _{1}={ IDSD}_{ Old }= 30$. (b) $IDS _{2}= IDSD _{ New }=H( key _{i+1})= H( key _{i}\oplus n$-$left )= H( key _{i}\oplus H$-$left ( key _{i}\oplus R\oplus H(T_{i}\oplus r)))=47$, while the tag variable of $IDS _{T}$ is still 30. The first step is preparing the retransmission information for the following desynchronization attack.

Fig. 2

The Step 1 of the attack to the protocol in Zhou et al. [10]

The second step of the attack to the protocol in Zhou et al. [10] is shown in Fig. 3. At this moment, the reader and the tag execute the authentication without any attack. Since $IDS _{2}= IDSD _{ New }= 47$ is not able to be found in the tag, both the database and the tag use the old secret $IDS _{1}= IDS _{T} = 30$ as the communication secret key. Thus, the tag will update its variable list to $IDS _{3}= IDSD _{ New }= ( key _{i}\oplus H$-$left ( key _{i}\oplus R\oplus H(T_{i}\oplus r)))= 50$. In the database, the value is updated as $IDS _{1}= IDSD _{ Old } = 30$ and $IDS _{3}= IDSD _{ New }= 50$. The second step is the prerequisite of the subsequent desynchronization attack. At the third step, the desynchronization attack has been launched by using the interrupted information at the first step to break the consistency of secret key between the tag and the database.

Fig. 3

The Step 2 of the attack to the protocol in Zhou et al. [10]

The third step of the attack to the protocol in Zhou et al. [10] is shown in Fig. 4. The adversary is able to use a malicious legal reader to produce a random number $R_{0} = r'$, where $r'$ is the value intervened at the first step before. Then, the malicious legal reader sends the $R_{0}$ to the adversary. The adversary compounds $R_{0}$ and $IDS_{i}'$, m-left $'$, $H(T_{i}\oplus r)'$ obtained at the first step and sends them to the malicious legal reader. After that, the adversary sends $IDS _{i}', H(T_{i}\oplus r)', { m}$-$left '$ and $R_{0}$ to the back-end database by a replay attack and a spoofing attack. Then, the back-end database will authenticate the retransmission of $IDS _{i}', H(T_{i}\oplus r)', m$-$left '$ and $R_{0}$ as a valid message at step 3 in Fig. 1. Then it will update its variables and secret key as: (a) $IDS _{1}= IDSD _{ Old }=30$, (b) $IDS _{2} = IDSD _{ New } =H( key _{i+1}) =H( key _{i}\oplus n$-$left) = H(key _{i}\oplus H$-$left(key _{i}\oplus R\oplus H(T_{i}\oplus R_{0}))) =48$. Since $IDS _{T}= 50\cap ( IDSD _{ New } =48\cup IDSD _{ Old } =30)=\varnothing$. It is clear to draw the conclusion that the desynchronization attack to the protocol in [5] is successful.

Fig. 4

The Step 3 of the attack to the protocol in Zhou et al. [10]

3 Proposed $\hbox {UP}^{2}\hbox {RT}$ Scheme

3.1 Defines 1: Definition of the variable

Suppose X and Y are two l-bit strings, where $\mathrm{X} = \hbox {a}_{1}\hbox {a}_{2} \ldots \hbox {a}_{\mathrm{l}}, \hbox {a}_{\mathrm {i}} \in \{ 0, 1\}, \hbox {i} =1, 2, \ldots ,l, \hbox {Y} = \hbox {b}_{1}\hbox {b}_{2} \ldots \hbox {b}_{\mathrm{l}}, \hbox {b}_{\mathrm{i}} \in \{ 0, 1\}, \hbox {j} =1, 2, \ldots ,l$. Moreover, the Hamming weight of B, wt(Y), is m(0 $\le$ m $\le l$) and $\hbox {b}_{k1} = \hbox {b}_{k2} = \cdots = \hbox {b}_{{km}}=1, \hbox {b}_{{km+1}} = \hbox {b}_{km+2} = \cdots =\hbox {b}_{kl}=0$, where 1 $\le \hbox {k}_{1}< \hbox {k}_{2}< \cdots < \hbox {k}_{m} \le l$ and $1 \le \hbox {k}_{m+1}< \hbox {k}_{m+2}< \cdots < k_{l} \le l$. Then, the permutation of X according to Y, denoted as Per(X, Y),  is Per(X, Y) = $\hbox {a}_{k1}~\hbox {a}_{k2} \ldots \hbox {a}_{km}\hbox {a}_{kl}\hbox {a}_{kl-1} \hbox {a}_{km+}{}_{2}\hbox {a}_{km+1}$. Figure 5 shows the computation of Per(X, Y).

Fig. 5

The computation of the example

In view of the defects of the existing protocols, we propose a low-cost RFID authentication protocol which integrates the operation of the XOR, build-in CRC-16 function, the permutation, a random tuple and secret key backup technologies to overcome the vulnerability under the desynchronization attacks without increasing the cost. The analysis shows that our proposal has a strong ability to prevent existing possible malicious attacks. The notations used are listed in Table 2. The proposed protocol is shown in Fig. 6. The detailed operation for each step is described as follows.

• Step 1 The reader challenges the tag.

• Step 2 While receiving the challenge, the tag responds with TID to the reader.

• Step 3 After receiving TID, the reader uses it as an index to search a matched entry in the database. If it is an old TID, the reader will use $\{ KeyH ^{ old }, KeyM ^{ old }, KeyL ^{ old }\}$ to compute the messages. If TID is new, $\{ KeyH ^{ new }, KeyM ^{ new }, KeyL ^{ new } \}$ will be used. If TID is not in the database, the reader will terminate the session as this may be an invalid tag. Suppose the reader has found { KeyH, KeyL, KeyM } as the tag’s entry. It will compute $\gamma _{1}, \gamma _{2} {\ldots } \gamma _{\mathrm {i}}$ and $\alpha$ with $R_{S}, R_{T1}, R_{T2},{\ldots } R_{Ti}$. Then the reader send the random number $R_{T1}, R_{T2}, R_{Ti}$ and $R_{S}$ with a mask to the tag.

• Step 4 The reader sends $\gamma _{1}, \gamma _{2} {\ldots } \gamma _{\mathrm {i}}$ and $\alpha$ to the tag.

• Step 5 The tag extracts $R_{S}$ by XOR $\alpha$ with CRC(Per(keyH,keyM)), and $R_{Ti}$ by XOR $\gamma _{i}$ with CRC(Per($R_{Ti-2}, R_{Ti-1}))$ . The tag computes the value of $B$ with $R_{S}'$ and $R_{T}$. Finally the tag computes the value of $\beta$ by CRC (Per($R_{S}', \hbox {CRC}(R_{Ti}\oplus B)))$.

• Step 6 The tag sends the $\beta$ to the reader.

• Step 7 When receiving $\beta$, the reader will compare it with the local $\beta$ to authenticate the tag. If the tag is authenticated, the reader will compute the value of $\zeta _{1} {\ldots } \zeta _{i},T', B'$ and $\delta$ with $R_{S}'', R_{x1} {\ldots }$ and $R_{xi}.$

• Step 8 The reader sends $\zeta _{1} {\ldots } \zeta _{i}$, and $\delta$ to the tag.

• Step 9 The tag extracts $R_{xi}$ from $\zeta _{i}$ and computes a local value of $\delta$. If the local value of $\delta$ equates to the received $\delta$, the tag will authenticate the reader and update the corresponding entry. And it updates the pseudonym and the secret key.

Table 2 Notation

Table 3 shows the experimental data of the authentication process of the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ Protocol. And the variable marked in bold is the transmitted message. The variables in the Table 3 are binary numbers with 16 bits.

Fig. 6

The operation of the $\hbox {UP}^{2}\hbox {RT}$ protocol

Table 3 Experimental data of the $\hbox {UP}^{2}\hbox {RT}$ protocol

4 Security Analysis

We analyse the security of the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme in the ability to resist various malicious attacks. We show that the proposed $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme has the ability to prevent various existing attacks including the desynchronization attacks, tracing attacks, replay attacks, and man-in-the-middle attacks.

We introduce the function of the random triple before performing the security analysis. In the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ protocol, the random triple ($R_{s}', T, B$) will be employed to resist the existing attacks. The $R_{s}'$ in ($R_{s}', T, B$) is a random number of $n$ bits. The value of $T$ equal to $\{(p_{0},m_{0}), {\ldots } (p_{i},m_{i}), {\ldots }, (p_{i},m_{j}), (p_{i+1},m_{j+1})\}$, where $p_{i}$ with length of $log 2^{n}$ bits is the intercepting bit of $i$ in $R_{s}'$. The $m_{i}$ in $T$ is the intercepting length from the $R_{s}'$ starting at $i$. If the length of $m_{i}$ is 3 bits, and the possible intercepted value of $R_{s}'$ is 000, 001, 010, 011, 100, 101, 110 or 111. Let $m_{0}+ {\cdots } +m_{i}+ {\cdots } +m_{j}\le n \le m_{0}+ {\cdots }+m_{i}+ {\cdots } +m_{j}+ m_{j+1}, b_{i}= \mathrm{Ror}\_ \mathrm{left}(R_{s}, p_{i}, m_{i}), B=\{ b_{1}, b_{2} {\ldots } {b}_{i} {\ldots } {b}_{j} {\ldots } {b}_{j+1}\}$ and $B= \hbox {Ror}\_\mathrm{left}({ B,0,n}$). For example, if $R_{s}' =10111101/10111110/11110111/11101101, R_{T}' =R_{T1}\cup R_{T2} \cup {\cdots } R_{Ti} =\mathbf{00000}001$/00011011/00101100/10010010/00100011/11001010/11010100/10001001 /01000001/01101011/01010101/11111011, then we can deduce that the value of $T$ equal to { (0, 1), (3, 3), (5, 4), (20, 2), (4, 3), (25, 2), (26, 4), (17, 1), (8, 1), (13, 3), (10, 5), (31, 3)} . Further, we can obtain that the value of $B$ equal to 1 111 1011 01 110 11 1011 1 1 110 11111 110.

4.1 Resistance to Desynchronization Attacks

If an adversary tries to attack the tag by using the retransmission desynchronization attacks, he will intercept and retransmit some messages at the Steps 4, 6, 8 in Fig. 7. Because the $\hbox {UP}^{2}\hbox {RT}$ scheme is a mutual authentication protocol and the transmitted messages are all correlative with the random number, the method used in Sect. 2 is not able to create the desynchronization between tags and readers. For example, an adversary intercepts and retransmits $\alpha , \gamma _{1}, \gamma _{2}{ {\ldots }} \gamma _{i}$ to the tag. Then he attack $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme by the method used in Sect. 2.2. The first step and the sceond step can perform as Sect. 2.2. But the third step can not succeed, according to the retransmit $\alpha , \gamma _{1}, \gamma _{2} {\ldots } \gamma _{i}$ the tag will compute $\beta$ with the old $R_{S}, R_{Ti}, B$. Then, $\beta$ will be not able to pass the authentication of the reader because the new random number $R_{S}$ is used to compute the local $\beta$ at the reader. So we may use the secret key backup technology to complete the normal authentication in the next time. We can concluded that $\hbox {UP}^{2}\hbox {RT}$ scheme resist the retransmission desynchronization attacks. Next we will analyze the bit tampering desynchronization attacks.

Fig. 7

Bit tampering desynchronization attacks to $\hbox {UP}^{2}\hbox {RT}$

It is possible for an adversary to attack the tag by the bit tampering desynchronization attacks as Chien [6]. For example, if an adversary tries to modify $R_{S}$ by flipping certain bits in $\alpha$, and wants to use the forged messages to passing the subsequent authentication, the tag cannot authenticate the messages because it is very difficult for the adversary to guess a correct $\beta$ by using the permutation, CRC-16, XOR and the random tuple. The analysis shows that it is not feasible to attack $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ by using the bit tampering desynchronization attacks. Firstly, for the $\hbox {UP}^{2}\hbox {RT}$ scheme, the permutation, XOR and the random tuple have been used to reduce the correlation of the transmitting messages. Secondly, the one-way CRC-16 function is also able to reduce the guessing possibility of the secret key greatly. The probability which the attackers can guess a forged $\beta$ to pass the authentication is far smaller than $\hbox {ADV}_{\mathrm {A}}=1/ (2^{\mathrm {n1}} \cdot 2 ^{\mathrm {n2}}\cdot (\hbox {n2/m}_{\mathrm {i}}) \cdot 2^{p}\cdot \sum \nolimits _{0\le p\le i}C^{mi}_{n}))^{Ti}$. The length of the tuple one is n1, which is no less than the length of the secret key. The length of the tuple two is n2 and is greater than the length of the secret key, determined by the interception on the tuple three. For an easy transfer, the length of the tuple three is n, which equals to the length of the secret key. The $\hbox {p}_{\mathrm {i}}$ in the tuple two indicates that the interception position is starting from ith bit of the tuple one. The value of $\hbox {p}_{\mathrm {i}}$ could be between 1 to $\mathrm{log}_{2}^{\mathrm {n}}$. The $\hbox {m}_{\mathrm {i}}$ in the tuple two is the length of the interception, or the number of the bits to be intercepted. When the value of n is larger, the attacker is almost impossible to derive the tuple one and tuple two from the tuple three, so the protocol can resist various existing attacks well. A more detailed description of the random triples can be found in Tables 2, 3 and Sect. 4.

Therefore, we can conclude that the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme can resist the desynchronization attacks well by using the permutation, CRC-16, XOR functions with a random tuple. The Fig. 7 shows the SPIN model of the operation of the proposed $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme under a bit tampering desynchronization attack. In the process of the attack, the attacker changes two bits of $\alpha$. The value of the $\beta$ will be changed to $\beta '$ due to the changes of $\alpha$. It is shown by the experiment result, the attack is not able to cheat the tag to get it authenticated by the proposed $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme due to its use of XOR operation, build-in CRC-16 function, permutation and the secret key backup technology. It is clear that the proposed solution has a strong ability to prevent the particular desynchronization attacks.

4.2 Man-in-the-Middle Attacks

A man-in-the-middle (MITM) attack is a form of eavesdropping where communication between two users is monitored and modified by an unauthorized party. Data confidentiality refers that the information cannot be unauthorized to use in the transmission and stored in the process. So if a protocol can assure the data confidentiality, it will be able to resist the MITM attack as well. In terms of data confidentiality, the messages $\alpha , \gamma _{1}, \gamma _{2} {\ldots } \gamma _{i}, \beta , \zeta _{1} {\ldots } \zeta _{i},$ and $\delta$ are all related to the secret key and a random number. And the messages $\alpha , \gamma _{1}, \gamma _{2} {\ldots } \gamma _{i}, \beta , \zeta _{1} {\ldots } \zeta _{i},$ and $\delta$ are encrypted by the application of the permutation, CRC-16, XOR and the random tuple. It is difficult to recover the random number without knowing the secret key. And it is impossible to guess the KeyH, KeyM, KeyL, $R_{S}, R_{T}$ or $R_{X}$ due to the application of the permutation, CRC, XOR and the random tuple. So the data confidentiality can be assured. In addition, the transmitted messages $\beta$ and $\delta$ do not only provide the evidence for authentication of the reader, but also assure the integrity of the tag. Since our protocol can assure data confidentiality, it can resist the MITM attacks too.

4.3 Resistance Tracing Attacks Scheme Choose

A tracing attack is one of the most powerful attacks which could be issued by a “malicious active reader”. The goal of the attack is to discover the presence of a specific tag. The attacker actively scans the tag from a far distance by the small device near the tag. According to the $A_{ query }$ phase (the certification stage of tag to reader), the RFID security protocols can be divided into two types. One type is the static RFID security protocol, which is the security protocol with a fixed TID or pseudonym. But, this type protocol cannot resist tracing attacks. Another one is the dynamic RFID security protocol, which has the authentication information changed in the $A_{ query }$ phase. The proposed protocol belongs to the second type. The value of TID, $\alpha ,\gamma _{1}, \gamma _{2} \ldots \gamma _{i}, \beta ,\zeta _{1} \ldots \zeta _{i},$ and $\delta$ will be changed according to the value of Rs, $R_{T}$ and $R_{X}$ after each successful authentication. In this way, the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ can resist the tracing attacks well.

4.4 Resistance to Replay Attacks

If there is a malicious reader attempts to retransmit TID, $\alpha , \gamma _{1}, \gamma _{2} {\ldots } \gamma _{i}, \beta , \zeta _{1} \ldots \zeta _{i},$ and $\delta$ to a tag, the tag will compute $R_{s}$, $R_{T}$ by the replayed $\alpha ,\gamma _{1}, \gamma _{2} \ldots \gamma _{i}$ passively. Then, the tag will compute the value of $\beta$ with a new random tuple and random numbers. Since the retransmitted variables use    the old random numbers, it is possible to cause the authentication failure. Similarly, at each follow-up step, only one authentication on either the tag or on the reader can be successful by using the old random numbers. The authentication of both the tag and the reader cannot be successful. Therefore, the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ can resist the replay attacks.

5 Cost Analysis and Performance Evaluation

Figure 8 shows the logic diagram of the proposed $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ scheme. Due to the fact that a message consists of two or more pieces, it requires one register of $n$ bits to temporarily store intermediate results. The core component of the $\hbox {UP}^{\mathrm {2}}\hbox {RT}$ logic is the arithmetic logic unit (ALU). The ALU has two inputs and one control signal. One of the inputs is the data path for data to be fetched from the register, while another is the bit stream from outside. The control to the ALU is the control signal (C_1) to select the input to the ALU from either the bit stream or the data stored in the register. The control signal C_2 will determine the operation that will be performed in the ALU.

Fig. 8

Logic scheme of $\hbox {UP}^{\mathrm {2}}\hbox {RT}$

Table 4 shows the comparison of logical gates required for different length of the secret key in $\hbox {UP}^{2}\hbox {RT}$ scheme. A hash function like MD5 generally needs 16,000 logical gates. SHA-1 needs 20,000 logical gates. The number of the logical gates required by the proposed protocol is much less than that of the protocols equipped with the complicated hash functions obviously. Therefore, the proposed $\hbox {UP}^{2}\hbox {RT}$ scheme is suitable for the low cost RFID systems.

Table 4 Comparison of logical gates and length of the secret key

We analyse the performance of the proposed $\hbox {UP}^{2}\hbox {RT}$ scheme in terms of the number of computation operations, the storage requirements and communication cost for a tag. The number of the computation operations is indicated by the number of different types of operations required for each tag. The storage requirements are easured by the memory size required to store a dynamic tag TID, three shared elements and some random numbers in a tag. The communication cost is calculated by the amount of the messages sent by the tag in one execution of the protocol. The comparison results among the solution in [17], some other protocols and the proposed protocol are listed in Table 5. In Table 5, “$+$” denotes the addition mod $2^{\mathrm {L}}$. We can conclude that the cost of $\hbox {UP}^{2}\hbox {RT}$ is very close to the existing ultralightweight protocols, but it has a strong ability to prevent existing possible attacks.

Table 5 Comparison of logical gates and length of the secret key

6 Conclusion

In this paper, we have reviewed the scheme in Zhou et al. [10] with the vulnerability exploration. It is discovered that the scheme in Zhou et al. [10] cannot resist one particular type of desynchronization attacks. In order to overcome the vulnerability, we have proposed a low-cost RFID authentication protocol which integrates the operation of the XOR, build-in CRC-16 function, permutation function, secret key backup with a random tuple to improve the security functionality without increasing much cost than the utralightweight protocols. The analysis shows that our proposal has a strong ability to prevent existing malicious attacks, especially the particular type of desynchronization attacks.