Sage Journals: Discover world-class research

Abstract

RFID is one of the most protuberant systems in the field of ubiquitous computing. Since RFID tags have limited computation capabilities, numerous ultralightweight authentication protocols have been proposed to provide privacy and security. However all the previously proposed ultralightweight mutual authentication protocols have some security apprehensions and are vulnerable to various desynchronization and full disclosure attacks. This paper proposes a new ultralightweight mutual authentication protocol to provide robust confidentiality, integrity, and authentication (RCIA) in a cost effective manner. RCIA introduces a new ultralightweight primitive recursive hash, which efficiently detects the message tempering and also avoids all possible desynchronization attacks. RCIA involves only bitwise operations such as XOR, AND, left rotation, and recursive hash. Performance evaluation illustrates that RCIA requires less resources on tag in terms of on-chip memory, communication cost, and computational operations.

1. Introduction

Radio frequency identification (RFID) is a rapidly growing identification scheme; nonline of sight capability makes RFID systems superior and dominant than their contending systems. Cost effectiveness and miniaturization are the two rudimentary tools which have increased its commercialization and transformed its deployment into massive deployment. Unlike bar codes, in RFID systems each object is labeled with a miniaturized integrated circuit (IC) equipped with antenna and other memory blocks [1]. The demand for low cost RFID tags limits using only a few and cost effective computational operations on the tag side. Practically, the low cost RFID systems can store only hundreds of bits and can have 5 to 10 K gates. However only 250 to 3 K gates can be allocated to security related operations for EPC (electronic product code) class-1 generation 2 passive RFID tags [2].

In 2006, Peris-Lopez et al. [3, 4] proposed a family of lightweight authentication protocols for such low cost RFID systems. These protocols provide the basic security using only simple bitwise operations (XOR, AND, and OR). Later on, some security vulnerabilities of these protocols were reported in different articles [5–7]. In 2007, Chien [8] classified the security protocols into four types: full-fledged, simple, lightweight, and ultralightweight. (1)

Full-fledged protocols can incorporate the traditional cryptographical algorithms and solutions, like one way hash functions, public or private key cryptography, and so forth.

(2)

Simple authentication protocols can support random number generator and one-way hash functions only.

(3)

Lightweight protocols can support only random number generators and simple functions such as cyclic redundancy check (CRC) but cannot use hash functions.

(4)

Ultralightweight protocols can incorporate only simple bitwise logical operations and even random number generator cannot be used at the tag's side.

In this paper, a new ultralightweight mutual authentication protocol has been proposed: introduction of novel ultralightweight primitive “recursive hash” makes it much more robust than its contending protocols [3, 4, 8–14] against various desynchronization and full disclosure attacks. We have named the protocol “RCIA” to highlight its main features of robust confidentiality, integrity, and authentication.

The rest of the paper is organized as follows: Section 2 discusses the related works. Section 3 introduces the novel protocol which is followed by the security analysis in Section 4. Section 5 shows the performance evaluation of the proposed protocol and finally conclusion will be highlighted in Section 6.

2. Related Work

Nowadays, RFID systems are becoming an integral part of various commercial and industrial applications because of their enriched features and functional haste. On the other hand, the enormous deployment of such systems also alters the espionage to salvage the communicated data so conjecture secret data can be retrieved. In order to secure RFID systems in cost effective way, several ultralightweight mutual authentication protocols have already been proposed. However, all previously proposed protocols have some vulnerabilities and serious security flaws. A detailed survey of ultralightweight protocols and their vulnerabilities is described as follows.

In 2006, Peris-Lopez et al. [3, 4] proposed a family of ultralightweight protocols: LMAP (lightweight mutual authentication protocol) and EMAP (efficient mutual authentication protocol). These protocols use simple bitwise logical operations (triangular functions) to provide basic security and rudimentary working of these protocols involving three steps: tags identification, mutual authentication, and variables (pseudonyms and keys) updating. The randomness of the exchanged messages has been tested with ENT [15], NIST [16], and Diehard [17] randomness test suites. However, Li and Wang [18] exploited the inherent poor diffusion properties of triangular functions and proposed two attacks (desynchronization and full disclosure) on LMAP and EMAP. These attacks successfully challenged the security claims of both protocols.

In 2007, Chien [8] proposed a new ultralightweight RFID authentication protocol to provide strong authentication and strong integrity (SASI). A new left rotation (Rot) function has been extensively used in SASI in addition to simple bitwise logical operations to avoid the full disclosure and desynchronization attacks. However Avoine et al. [19] highlighted the poor designing of the messages in SASI and presented a practical passive attack on SASI. The proposed attack requires 2¹⁷ eavesdrop sessions to launch full disclosure attack. In 2013 Avoine et al. [20] improved the full disclosure attack from 2¹⁷ eavesdropped sessions to a few sessions. Sun et al. [21] found two desynchronization attacks on SASI and thus put the SASI among vulnerable ultralightweight mutual authentication protocols.

In 2008, Peris-Lopez et al. [12] proposed a more sophisticated ultralightweight authentication protocol named GOASSMER. Peris introduced a new primitive: MixBits (using genetic programming) in GOASSMER. MixBits function enhanced the diffusion properties of the exchanged messages; however, the confrontation between protocol developers and cryptanalysts continued. In 2009, Bilal et al. [22] highlighted few vulnerabilities in GOASMER protocol. They proposed denial of service (DoS) and desynchronization attacks on GOASSMER protocol. These attacks raised the question mark on GOASSMER security litigations. In 2012, Zubair et al. proposed a counter based methodology in [23] to augment the performance of GOASSMER protocol. Integration of the counter in GOASSMER makes it resilient against DOS and desynchronization attacks.

David and Prasad [10] presented a new ultralightweight authentication protocol using only AND and XOR operations in 2009. David-Prasad protocol introduced a concept of day certificate “C” for reader to eradicate the threat of reader impersonation. The protocol requires extremely less computational power at tag side thanks to inclusion of simple bitwise logical operations. However Hernandez-Castro et al. [24] proposed traceability and full disclosure attack (Tango) on the David-Prasad protocol. Tango attack requires GA (good approximations) equations based on hamming distance with unknown variable. Then Barrero et al. in [25] modified the Tango attack and presented genetic tango attack; the later one resolved the exhaustive searching of GA equations.

In 2012, Tian et al. [9] proposed a new ultralightweight authentication protocol: RAPP. RAPP introduced a new ultralightweight nontriangular primitive “Permutation” to enhance the diffusion properties of the secret variables. RAPP involves simple bitwise XOR, left rotation (Rot), and permutation $(Per)$ operations, which ensures high security, low computational complexity, and low cost of the tags. In 2013, Ahmadian et al. [26] highlighted the poor composition of RAPP messages and proposed a desynchronization attack on the protocol. In the same year, Shao-hui et al. [27] showed the poor diffusion properties of the newly proposed permutation $(Per)$ function, which can be easily exploited to reveal concealed secrets in tag. Ahmadian et al. [28] also introduced two new security models (frameworks): recursive linear and recursive differential cryptanalysis to evaluate the security performance of ultralightweight mutual authentication protocols. Both security models exploited the weak properties of T functions used in ultralightweight authentication protocols to retrieve the concealed secrets.

In [3, 4, 8–14] ultralightweight authentication mutual protocols for RFID systems have been proposed with several variations in design and primitives but cryptanalysis performed in [5–7, 19–30] highlighted the security loop holes and vulnerabilities in the abovementioned protocols. This raises the need of a new secure and robust ultralightweight mutual authentication protocol to combat against all types of malicious activities.

3. RCIA: A New Ultralightweight RFID Authentication Protocol

In RCIA, tags involve only three main operations: bitwise AND, XOR, and left rotation $Rot (A, B)$ . A new nontriangular primitive, recursive hash $(R_{h})$ (composed of Rot and XOR), has been extensively used in RCIA. Recursive hash of any variable can be computed as follows.

Computation of Recursive Hash Function ${(R}_{h})$ . Suppose A is a “n” bit string, where

\begin{matrix} A = a_{1} a_{2} \dots a_{n}, a_{i} \in \{0,1\}, i = 1,2, \dots, n . \end{matrix}

(1)

Then computation of recursive hash of

A, R_{h} (A)

, involves the following three steps.

(1)

Decimate the string A into “K” number of chunks (memory blocks) with equal number of bits “l” per memory block ( $K = n / l$ ).

For EPC class-1 generation-2 ultralightweight tags [2]: $n = 96$ bits and for efficient hardware implementation, $l = 12$ bits, and $K = {8 (k}_{1} \dots k_{8})$ .

(2)

After extracting random numbers $(n_{1} and n_{2})$ from messages sent by reader, tag calculates the seed (index of the memory block) for recursive hash in following manner.

(a)

Compute $R = n_{1} \oplus n_{2}$ .

(b)

Seed (index of memory block) $= wt (R) \mod K$ , where $wt (R)$ represents the hamming weight of R.

(3)

Seed calculated in step 2 will select the corresponding memory block $(k_{i})$ of decimated string A and perform the following operations to compute final recursive hash of $A, R_{h} (A)$ .

(a)

Take XOR between selected memory block $(k_{i})$ with all other blocks except the block itself.

(b)

Left rotate the $k_{i}$ with itself: $Rot (k_{i}, {wt (k}_{i}))$ .

To better understand the concept of recursive hash function consider the following example.

Example. Given $A = 100100101011110101111110$ , $n = 24$ , $l = 6$ , and $K = k_{1} k_{2} \dots k_{4}$ and assume Seed $= 3$ .

Then we have

\begin{matrix} R_{h} (A) = 001010011101011011000101 . \end{matrix}

(2)

Algorithm 1 shows the computation of the above example.

Algorithm 1: The computation of recursive hash (example).

Assume: $A = 100100101011110101111110, Seed = 3$ ; $n = 24$ , $l = 6$ , $K = k_{1}, k_{2}, \dots, k_{4}$

Step 2. As, seed = 3, so $k_{3}$ (110101) memory block will be selected for Recursive hash.

Step 3. Take XOR between $k_{3}$ and all other memory blocks except itself and left rotate $k_{i}, Rot (k_{i}, wt (k_{i}))$

$\begin{matrix} \oplus    \\ Rot (k_{3}, wt (k_{3}))                \\ R_{h} (A)                         \end{matrix} \begin{matrix} \frac{\begin{matrix} 100100 & 101011 & 110101 & 111110 \\ 110101 & 110101 & 110101 \end{matrix}}{\begin{matrix} 010001 & 011110 & — & 001011 \end{matrix}} \\ \frac{\begin{matrix} 011101 \end{matrix}}{\begin{matrix} 010001 & 011110 & 011101 & 001011 \end{matrix}} \end{matrix}$

The rotation function used in RCIA is explained as follows.

$Rot (A, B)$ is cyclic left rotation of A according to B's hamming weight [21]. For $B = b_{1} b_{2} \dots b_{n}$ , each input $b_{i}$ , where $1 \leq i \leq n$ , is tested and cyclic left rotation operation is performed if $b_{i} = 1$ , otherwise no operation was performed. So $Rot (A, B)$ is in fact $Rot (A, wt (B))$ , where $wt (B)$ represents the hamming weight of B. Rot is a simple operation but time (clock cycle) consuming function because term A is cyclic left rotated for a minimum of zero and maximum of n-bits (examining of B requires n clock cycles for the rotation operation).

RCIA mainly involves three entities: tag, reader, and backend database. Usually, it is assumed that communication channel between reader and backend database is secure since both reader and tag can incorporate traditional cryptographical algorithms for secure communications [3]. The channel between tag and reader is wireless and susceptible to all types of adverse attacks because of limited computational power at tag side. Each tag has unique static ID and preshares a pseudonym IDS and two keys $(K_{1} and K_{2})$ with backend database. To avoid the desynchronization attacks, both reader and tag store the values of old $(IDS)$ pseudonym and old ${(K}_{1} and K_{2})$ keys. According to EPC-class-1 Gen 2, the length of $ID, IDS$ , and two keys ${(K}_{1} and K_{2})$ is kept 96 bits for low cost passive RFID tags [2]. Both the tag and reader will update their pseudonym “IDS” and keys ${(K}_{1} and K_{2})$ after each successful authentication session. RCIA comprises three steps: tag identification, mutual authentication, and variable updating (pseudonyms and keys). Figure 1 shows the specifications of the protocol. The working details of the protocol are as follows. (1)

Reader sends a “ $H e l l o$ ” message to the tag to initiate the protocol session.

(2)

Upon receiving the reader's query, tag responds with its “IDS.”

(3)

On receiving IDS, the reader will use it as a matching index in the database. If it is an old one, IDS_old, then the reader will use $K_{1, old} and K_{2, old}$ for computation of messages $(A ‖B‖ C)$ . If IDS is new one, IDS_new, then reader will use $K_{1, new} and K_{2, new}$ to compute messages $(A ‖B‖ C)$ . If IDS is not in the database, then reader will immediately terminate the authentication session with the particular tag. However if a match is found in the database, reader will generate two random nonces $(n_{1} and n_{2})$ and conceal them in messages $A and B$ . The reader will also compute $R = n_{1} \oplus n_{2}$ , and seed for computation of recursive hash function. The seed is computed by taking mod of hamming weight of R given by $wt (R) \mod K$ . Finally, the reader will use recursive hash $(R_{h})$ of the variables $(K_{1}, K_{2}, K_{1}^{*}, K_{2}^{*}, n_{1}, n_{2})$ to compute “C” message.

(4)

The tag first extracts random nonces ${(n}_{1} and n_{2})$ from messages A and B. Then it computes the seed for recursive hash function using $R = n_{1} \oplus n_{2}$ and $wt (R) \mod K$ . The tag further calculates $K_{1}^{*}$ and $K_{2}^{*}$ to compute the local value of $C^{*}$ and compare it with the received C. If both the values are equal, then the tag will perform two tasks: firstly calculate and transmit D message towards reader and secondly update its pseudonym (IDS) and keys ${(K}_{1} and K_{2})$ .

(5)

Upon receiving message D, the reader will compute a local value of D and if match occurs, then reader will also update its pseudonym (IDS) and keys ${(K}_{1} and K_{2})$ for that particular tag.

The statistical properties of the messages

A, B, C, and D

have also been analyzed with three well-known randomness tests, Diehard [17], ENT [15], and NIST [16]. We have generated 11 MB file for each message and some of the results are presented in Table 1. We can observe from Table 1 that all messages are not easily distinguishable from a random source and even not for adversary or attacker.

Table 1

Randomness test with ENT, Diehard, and NIST.

	A	B	C	D
Entropy (bits/bytes)	7.99998	7.99799	7.99986	7.99899
Compression rate	0%	0%	0%	0%
$X^{2}$ statistic	254.87	248.64	238.98	258.13
Arithmetic mean	127.4930	127.5779	127.5045	127.3187
Monte Carlo π estimation	3.14319	3.14058	3.14958	3.14512
Diehard battery (Overall P value)	0.586823	0.48523	0.41509	0.64381
NIST battery	Pass	Pass	Pass	Pass

Figure 1

RCIA protocol.

4. Security Analysis

We analyze the security of RCIA in two aspects: basic functionality of the protocol and resistance to the various cryptanalysis attacks. As the name suggests, confidentiality, integrity, and authentication are the basic functionalities of the RCIA protocol, and these functionalities will be evaluated first. We have considered desynchronization, replay attack, traceability, impersonation, full disclosure, and recently proposed formal structural cryptanalysis such as Tango and recursive linear and differential cryptanalysis. Brief description of security analysis is presented in Figure 2.

Figure 2

Security analysis model.

4.1. Functionality of the Protocol

4.1.1. Confidentiality

RCIA ensures the data confidentiality by encrypting the publically disclosed messages $A, B, C$ , and D with preshared (between reader and tag) secret keys $(K_{1}, K_{2})$ . Furthermore, it is impossible to retrieve random numbers $(n_{1}, n_{2})$ , recursive hash $(R_{h})$ of the variables, and tag's secret ID from the transmitted messages without knowing keys ${(K}_{1}, K_{2})$ . Khovratovich [31] proposed rotational cryptanalysis to analyze the security of the systems based on modular addition, rotation, and XOR (ARX). For a given number of additions/rotations/XOR P, the logarithmic probability $(\Pr)$ of any ARX systems for $P < - t / \log_{2} (\Pr)$ is considered being vulnerable to rotational cryptanalysis. Therefore rotational cryptanalysis can be avoided if a larger number of rotations and XOR operations are incorporated in the scheme [32]. In RCIA, recursive hash makes extensive use of XOR and rotation operations, which amplifies the diffusion (nonlinearity) properties of the protocol and provides optimal confidentiality to the system.

4.1.2. Integrity

The messages $B and C$ not only provide evidence for authentication of reader but also assure the integrity of the transmitted messages. For example, if an attacker tries to modify the random number $n_{1}$ by flipping certain bits of message A, then the impact of this alteration directly transfers to message B and tag will extract invalid random number $n_{2}$ from message B. This invalid computation of $n_{2}$ will calculate erroneous seed $(R)$ for recursive hash. Hence tag will not verify C message and abort the protocol. However it is impossible for an attacker to adjust the value of B to a correct value because $Rot (IDS \land n_{1}, K_{2})$ ensures that any change in $n_{1}$ will lead to computation of entirely different $n_{2}$ . Hence the optimal messages construction in RCIA ensures the integrity of the messages.

4.1.3. Mutual Authentication

The genuine readers and genuine tags can authenticate each other. The messages $A, B, C, and D$ are based on preshared $K_{1} and K_{2}$ (keys), so only genuine pair of reader and tag can generate these messages that will be accepted by both parties. In RCIA, reader is authenticated by checking the legitimacy and correctness of message C. The message C is computed with preshared keys and pseudorandom numbers ${(n}_{1}, n_{2})$ , so only the valid tag can verify the message C. Once the tag authenticates reader successfully, it transmits its shared secrets in the form of message D. The reader authenticates tag after verifying the legitimacy of message D; therefore only genuine reader and tag can generate valid values in RCIA.

4.2. Security Model/Attacks

4.2.1. Desynchronization Attack

In RCIA, both reader and tag update their shared secret keys $(K_{1}, K_{2})$ and IDS after every successful authentication session to maintain synchronization between each other. The synchronization depends upon the reception of messages C and D, so there are two possible approaches which can break the synchronization.

(a) Attacker Interrupts Message C. Since tag does not receive message C from reader, it will not update its values and will keep the tuple $(K_{1}^{i}, K_{2}^{i} and {IDS}^{i})$ in its memory. Secondly, tag also aborts the protocol session and will not compute D message. Hence reader will also remain in the same state as that of tag (synchronized).

(b) Attacker Interrupts Message D. Since reader does not receive message D from tag, it will make the tag update its values but nothing happens at reader's end. As both tag and reader keep two entries of keys and $IDS (K_{1}^{new}, K_{2}^{new}, K_{1}^{old}, K_{2}^{old}, {IDS}^{new} and {IDS}^{old})$ , so reader and tag (both) can still authenticate each other using old (previous) values. Moreover, if an attacker tries to make reader and tag use different random numbers ${(n}_{1}, n_{2})$ to update their values by tampering the messages A and B, the attacker will not succeed because tag will notice this tampering and abort such protocol session.

4.2.2. Replay Attack

In RCIA, for each new session: reader generates new random numbers $(n_{1}, n_{2})$ and computation of D message involves potential next keys ( $K_{1}^{*} and K_{2}^{*}$ ). If an attacker replays previously captured message D of valid tag, then the reader will not authenticate this tag (attacker). Another possible replay attack scenario, to make tag and reader desynchronized, has been proposed by Sun et al. [21]. The said attack takes advantage of single entry of local values (IDS and keys). RCIA caters the attack by storing two (previous and current) values of local values. The description of Sun et al. attack for RCIA is as follows.

Suppose a reader initiates the protocol session with a particular tag. The attacker sniffs and records IDS and the messages $(A ‖B‖ C)$ as ${IDS}^{I}$ and $(A^{i} ‖B^{i}‖ C^{i})$ , respectively. The attacker then interrupts the message D, so that tag will update its values but reader will not. Next, attacker allows the reader and tag to run the protocol again without intervening them. On receiving of reader's query, tag will respond with its ${IDS}^{next}$ but as attacker had blocked D message in previous authentication session so reader will ask for old values to start new authentication session. After successful completion of authentication session both reader and tag update their values in accordance with new $(n_{1}, n_{2})$ values. Now attacker starts a new protocol session with valid tag, pretending himself a valid reader (Impersonation). Tag responds with currently updated IDS but reader (attacker) asks for old values for execution of the protocol. On receiving ${IDS}^{i}$ it will transmit the precaptured messages $(A^{i} ‖B^{i}‖ C^{i})$ whose tag will definitely accept and update its values. However, this attack will also not affect the synchronization between reader and tag, because in RCIA both parties store the two entries of their Keys and IDS. The storage of previous and current values of keys and IDS makes RCIA much more robust against desynchronization and replay attacks.

4.2.3. Traceability Attack

In RCIA, tag uses its IDS for interaction with reader instead of its original ID while the IDS will be updated after each successful session. Secondly, the updating operation involves pseudorandom numbers $(n_{1} and n_{2})$ ; therefore, this will protect tag's anonymity and make tracking impossible. Moreover, adversary will not be able to track the tags through exchanged messages $(A, B, C, and D)$ because the freshness of message is ensured with $(n_{1} and n_{2})$ pseudorandom numbers.

4.2.4. Full Disclosure Attack

RCIA protocol has extensively incorporated nontriangular functions such as recursive hash ( $R_{h}$ ) and left rotation (Rot) instead of simple T-functions (XOR, AND, and OR) which makes it impossible to find probabilistic and other disclosure attacks for our protocol. Recursive hash function basically encompasses internal modular left Rot and XOR operations. In RCIA, we have further left rotated the recursive hash of values to compute publically transmitted messages, thus amplifying the diffusion properties of the messages. In most of the full disclosure attacks, the attacker tries numerous slightly modified combinations of the messages to find suitable approximation of internal secrets. However use of recursive hash in RCIA increases overall computational complexity for reverse engineering approximations as there can be many different pairs that may yield the same results.

4.2.5. Formal Structural Cryptanalysis

Most of the attacks proposed on UMAP protocols are based on ad hoc or probabilistic methods which are not extendible to a broader class of ultralightweight protocols for their security analysis. To the best of our knowledge, only two formal structural cryptanalysis methods (frameworks) with certain limitations, namely, Tango and recursive linear and differential cryptanalysis, exist to evaluate the security analysis of UMAP protocols. RCIA evades these formal structured cryptanalysis in the following manner.

(a) Tango Attack. Tango attack [24] mainly exploits the inherent poor diffusion properties of triangular functions and improper designing of the protocol messages (equations). The attack is divided into two phases: (a) selection of good approximations (GA) for secrets (keys and ID) and (b) comparison of combination of GA to reveal the desired secret (for various iterative sessions) with optimal precomputed threshold value $(T (X))$ , where X is the total number of 1's in GA (columns); then $(T (X))$ can be computed as follows:

\begin{matrix} T (X) = \{\begin{cases} if (X_{i} \geq γ) then assign 1 \\ if (X_{i} \leq γ) then assign 0, \end{cases} \end{matrix}

(3)

where,

γ = (1 / 2) * N_{A} * N_{S}

N_{A} = Number of approximations for a Secret

N_{S} = Number of eavesdropped sessions (Iterations)

GA that are used in Tango attack to retrieve the conjecture secrets are linear approximations. Tango attack cannot be applied to UMAP protocols which incorporate nontriangular functions abundantly. This limitation of Tango attack has also been highlighted by the Hernandez-Castro et al. [24]. However, in RCIA none of the unbalanced operations is used and as recursive hash comprises one left rotation (for one memory chunk ${(S}_{i})$ of 12 bits) and seven XOR operations (for one memory chunk $(S_{i})$ of 12 bits) which will further increase the overall complexity, $O (2^{7 S_{i}} \times \log_{2} (S_{i}))$ for approximation of each secret value. Secondly, hamming distance between $Rot (X, Y)$ and X varies according to the value of Y. In RCIA hamming distance between X and $R_{h} (X)$ also differs according to the seed value $(R = (n_{1} \oplus n_{2}))$ . So, it is impossible to find optimal approximations of secrets using nonlinear (left rotated and recursive hashed) public messages in the RCIA protocol. Therefore, RCIA is highly resistive to such Tango attacks. Hence in order to estimate the secret values for RCIA, other kinds of approximation should be considered.

(b) Recursive Linear and Differential Attacks [28]. recursive linear cryptanalysis (RLC) also exploits the T-functions and constructs the system of linear equations for each bit of the secret values (Keys and ID). The RLC then solves the linear equations recursively (bitwise) starting from least significant bit (LSB) to retrieve all concealed secret variables. RLC is passive and deterministic and requires only one authentication session. However RLC completely fails to retrieve the secret variables of UMAP protocols which incorporate nontriangular functions ( $Rot, Permutation and Recursive hash$ , etc.) in their design [28]. Since RCIA extensively uses nontriangular function recursive hash, so RLC is not applicable on RCIA.

Recursive differential cryptanalysis (RDC) is more powerful attack than RLC and evidently has some more requirements. RDC is an active attack and requires more than one authentication sessions to construct the set of linear equations. In RDC, the attacker tends to limit both the reader and tag to run their new authentication sessions in previous state (Old), so that both parties will not update their variables (Keys and IDS). For each new session, all the dynamic secret variables will remain the same except random numbers ${(n}_{i})$ . Moreover these new random numbers usually have clear differential relation with previous ones that can be used to generate linear equations for secret variables. RDC also fails to construct the optimal linear equations for nontriangular incorporated protocols [28]. Hence, RCIA avoids both (RLC and RDC) attacks because the impact of recursive hash ( $R_{h}$ ) affects (nonlinear bit positioning) the computation of all dynamic secrets, so the even differential relation of the random numbers (new and old) will not allow attacker to construct linear set of equations for secret variables approximations.

5. Performance Evaluation

In this section, the performance analysis of RCIA protocol in terms of computational operations, memory storage requirement, communication cost, and security for each tag is presented. As far as computational operations are concerned, the tag involves simple bitwise operations: XOR, AND, left rotation, and recursive hash. Recursive hash is basically composed of three basic ultralightweight operations: grouping, left rotation, and XORing. These operations are extremely lightweight in nature and can easily be implemented on low cost passive tags. Regarding storage requirement, each tag requires a ROM memory of 7L bits to store L bits of its static ID and 6L bits rewritable memory (two entries) of its pseudonyms (IDS, $K_{1}$ , and $K_{2}$ ). The communication cost of the tag is basically number of messages sent by a tag in one protocol run. Here in RCIA tag transmits altogether two messages; hence, the communication cost is 2L bits.

RCIA provides robust security as compared to its contending previously proposed ultralightweight mutual authentication protocols [3, 4, 8–13]. None of these protocols completely satisfies the proposed security model presented in Section 4. The existing ultralightweight mutual authentication protocols fail to provide the basic functionalities (confidentiality, integrity, and authentication) which are the unavoidable requirement for any security protocol. On the other hand, as discussed in Section 4, RCIA can withstand all the security attacks mentioned in the security model, as shown in Figure 1. A simple comparison of some ultralightweight protocols is listed in Table 2. The analysis depicts that RCIA outperforms the others while using minimal resources.

Table 2

Performance analysis of several ultralightweight mutual authentication protocols (tag side).

	LMAP [3]	EMAP [4]	SASI [8]	David-Prasad [10]	GOASSMER [12]	RAPP [9]	RCIA
Computational operations on Tag	$\oplus$ , OR, +	$\oplus$ , AND, OR	$\oplus$ , AND, OR, Rot, +	$\oplus$ , AND	$\oplus$ , +, Rot, MixBits	$\oplus$ , Rot, Per	$\oplus$ , Rot, AND

Memory requirement on Tag	$6 L^{*}$	$6 L$	$7 L$	$5 L$	$7 L$	$5 L$	$7 L$

Communication messages generated by tag	$2 L$	$3 L$	$2 L$	$3 L$	$2 L$	$2 L$	$2 L$

Total number of messages for mutual authentication	$4 L$	$5 L$	$4 L$	$5 L$	$4 L$	$5 L$	$5 L$

Resistance to desynchronization attacks	No	No	No	No	No	No	Yes

Resistance to full disclosure attacks	No	No	No	No	Yes	No	Yes

Resistance to traceability attacks	No	No	No	No	No	No	Yes

$^{*} L$ denotes the bit length = 96 bits.

6. Conclusion

In this paper, we have proposed a novel ultralightweight mutual authentication protocol using recursive hash. The proposed scheme provides robust confidentiality, integrity of the transmitted messages, and authentication in optimal and cost effective way. In RCIA, there are only three computational operations at the tag's end: XOR, AND, and left rotation (Rot). A new ultralightweight primitive recursive hash has also been introduced in this paper which makes the proposed algorithm more secure and robust against various attacks. These tremendous features make RCIA the best choice for low cost and very low cost RFID tags.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Nawaz

Ahmed

Mujahid

RFID system: design parameters and security issues

World Applied Sciences Journal 2013 23 2 236 244

10.5829/idosi.wasj.2013.23.02.171

2-s2.0-84879003430

GS1 EPCglobal tag data standards version 1.4, http://www.epcglobalinc.org/standards/

Peris-Lopez

Hernandez-Castro

J. C.

Tapiador

J. M. E.

Ribagorda

LMAP: a real lightweight mutual authentication protocol for low-cost RFID tags

Proceedings of the 2nd Workshop on RFID Security

2006

Graz, Austria

100 112

Peris-Lopez

Hernandez-Castro

J. C.

Estevez-Tapiador

J. M.

Ribagorda

EMAP: an efficient mutual-authentication protocol for low-cost RFID tags

Proceedings of the 1st International Workshop on Information Security (OTM '06)

2006

Montpellier, France

352 361

Peris-Lopez

Hernandez-Castro

J. C.

Phan

R. C. -W.

Tapiador

J. M. E.

Quasi-linear cryptanalysis of a secure RFID ultralightweight authentication protocol

Proceedings of the 6th International Conference on Information Security and Cryptology

2011

Shanghai, China

427 442

Han

Gröbner basis attacks on lightweight RFID authentication protocols

Journal of Information Processing Systems 2011 7 4 691 706

10.3745/jips.2011.7.4.691

Wang

Security analysis of two ultra-lightweight RFID authentication protocols

New Approaches for Security, Privacy and Trust in Complex Environments: Proceedings of the IFIP TC-11 22nd International Information Security Conference (SEC 2007), 14–16 May 2007, Sandton, South Africa 2007 232

New York, NY, USA

Springer

109 120 IFIP International Federation for Information Processing

Chien

H.-Y.

SASI: a new ultralightweight RFID authentication protocol providing strong authentication and strong integrity

IEEE Transactions on Dependable and Secure Computing 2007 4 4 337 340

10.1109/tdsc.2007.70226

2-s2.0-36248982045

Tian

Chen

A new ultralightweight RFID authentication protocol with permutation

IEEE Communications Letters 2012 16 5 702 705

10.1109/lcomm.2012.031212.120237

2-s2.0-84862788058

10.

David

Prasad

N. R.

Providing strong security and high privacy in low-cost RFID networks

Proceedings of the International Conference on Security and Privacy in Mobile Information and Communication Systems

2009

Catania, Italy

172 179

11.

Yeh

K.-H.

N. W.

Winata

An efficient ultralightweight authentication protocol for RFID systems

2010

Istanbul, Turkey

Proceedings of the Workshop on RFID Security and Privacy

49 60

12.

Peris-Lopez

Hernandez-Castro

J. C.

Tapiador

J. M. E.

Ribagorda

Advances in ultralightweight cryptography for low-cost RFID tags: gossamer protocol

Information Security Applications: The 9th International Workshop on Information Security Applications (WISA '08) 2009 5379 56 68 Lecture Notes in Computer Science

10.1007/978-3-642-00306-6_5

13.

Jeon

I.-S.

Yoon

E.-J.

A new ultra-lightweight RFID authentication protocol using merge and separation operations

International Journal of Mathematical Analysis 2013 7 49–52 2583 2593

10.12988/ijma.2013.36146

2-s2.0-84886544857

14.

Bilal

Martin

Ultra-lightweight mutual authentication protocols: weaknesses and countermeasures

Proceedings of the 8th International Conference on Availability, Reliability and Security (ARES '13)

September 2013

Regensburg, Germany

304 309

10.1109/ARES.2013.41

15.

Walker

ENT Randomness Test

1998, http://www.fourmilab.ch/random/

16.

Suresh

Charanjit

Rao

J. R.

Rohatgi

A cautionary note regarding evaluation of AES candidates on smart-cards

Proceedings of the 2nd Advanced Encryption Standard (AES) Candidate Conference

1999

http://csrc.nist.gov/archive/aes/round1/conf2/papers/chari.pdf

17.

Marsaglia

Tsang

W. W.

Some difficult-to-pass tests of randomness

Journal of Statistical Software 2002 7 3 37 51

2-s2.0-0347666758

18.

Wang

Security analysis on a family of ultra-lightweight RFID authentication protocols

Journal of Software 2008 3 3

2-s2.0-70450286845

19.

Avoine

Carpent

Martin

Strong authentication and strong integrity (SASI) is not that strong

Workshop on RFID Security and Privacy

2010

Istanbul, Turkey

50 64

20.

Avoine

Carpent

Martin

Privacy-friendly synchronized ultralightweight authentication protocols in the storm

Journal of Network and Computer Applications 2012 35 2 826 843

10.1016/j.jnca.2011.12.001

2-s2.0-84856217397

21.

Sun

H.-M.

Ting

W.-C.

Wang

K.-H.

On the security of Chien's ultralightweight RFID authentication protocol

IEEE Transactions on Dependable & Secure Computing 2011 8 2 315 317

10.1109/tdsc.2009.26

2-s2.0-78751641225

22.

Bilal

Masood

Kausar

Security analysis of ultra-lightweight cryptographic protocol for low-cost RFID tags: Gossamer protocol

Proceedings of the International Conference on Network-Based Information Systems (NBIS '09)

August 2009

Indianapolis, Ind, USA

IEEE

260 267

10.1109/NBiS.2009.9

23.

Zubair

Mujahid

Najam-ul-Islam Ahmed

Cryptanalysis of RFID ultra-lightweight protocols and comparison between its solutions approaches

BUJICT Journal 2012 5 1 58 63

24.

Hernandez-Castro

J. C.

Peris-Lopez

Phan

R. C.-W.

Tapiador

J. M. E.

Cryptanalysis of the David-Prasad RFID ultralightweight authentication protocol

Proceedings of the 6th International Workshop on Radio Frequency Identification: Security and Privacy Issues (RFID '10)

2010

Istanbul, Turkey

22 34

10.1007/978-3-642-16822-2_3

25.

Barrero

D. F.

Hernández-Castro

J. C.

Peris-Lopez

Camacho

R-Moreno

M. D.

A genetic tango attack against the David-Prasad RFID ultra-lightweight authentication protocol

Expert Systems 2014 31 1 9 19

10.1111/j.1468-0394.2012.00652.x

2-s2.0-84893079876

26.

Ahmadian

Salmasizadeh

Aref

M. R.

Desynchronization attack on RAPP ultralightweight authentication protocol

Information Processing Letters 2013 113 7 205 209

10.1016/j.ipl.2013.01.003

2-s2.0-84873319425

27.

Shao-hui

Zhijie

Sujuan

Dan-wei

Security analysis of RAPP: an RFID authentication protocol based on permutation

Cryptology ePrint Archive Report 2012 2012/327 https://eprint.iacr.org/2012/327

28.

Ahmadian

Salmasizadeh

Aref

M. R.

Recursive linear and differential cryptanalysis of ultralightweight authentication protocols

IEEE Transactions on Information Forensics and Security 2013 8 7 1140 1151

10.1109/tifs.2013.2263499

2-s2.0-84879953566

29.

D'Arco

de Santis

On ultralightweight RFID authentication protocols

IEEE Transactions on Dependable and Secure Computing 2011 8 4 548 563

10.1109/tdsc.2010.75

2-s2.0-79957590172

30.

Mujahid

Najam-ul-islam

Ahmed

Mujahid

Cryptanalysis of ultralightweight RFID authentication protocol

Report 2013/385 2013 https://eprint.iacr.org/2013/385

31.

Khovratovich

Rotational cryptanalysis of ARX

6147

Proceedings of the 17th International Conference on Fast Software Encryption (FSE '10)

2010

Seoul, Republic of Korea

Springer

333 346 Lecture Notes in Computer Science

10.1007/978-3-642-13858-4_19

32.

Özcanhan

M. H.

Dalkılıç

Mersenne twister-based RFID authentication protocol

Turkish Journal of Electrical Engineering & Computer Sciences 2015 23 231 254

10.3906/elk-1212-95

RCIA: A New Ultralightweight RFID Authentication Protocol Using Recursive Hash

Abstract

1. Introduction

2. Related Work

3. RCIA: A New Ultralightweight RFID Authentication Protocol

Algorithm 1: The computation of recursive hash (example).

4. Security Analysis

4.1. Functionality of the Protocol

4.1.1. Confidentiality

4.1.2. Integrity

4.1.3. Mutual Authentication

4.2. Security Model/Attacks

4.2.1. Desynchronization Attack

4.2.2. Replay Attack

4.2.3. Traceability Attack

4.2.4. Full Disclosure Attack

4.2.5. Formal Structural Cryptanalysis

5. Performance Evaluation

6. Conclusion

Footnotes

Conflict of Interests

References