Simulation-Based Traceability Analysis of RFID Authentication Protocols

Abstract

Nowadays low-cost RFID systems have moved from obscurity into mainstream applications which cause growing security and privacy concerns. The lightweight cryptographic primitives and authentication protocols are indispensable requirements for these devices to grow pervasive. In recent years, there has been an increasing interest in intuitive analysis of RFID protocols. This concept has recently been challenged by formal privacy models. This paper investigates how to analyse and solve privacy problems in formal model. First, we highlight some vague drawbacks especially in forward and backward traceability analysis and extend it in the simulation-based privacy model family. Then, the privacy weaknesses of three new-found RFID authentication protocols are analysed in formal privacy models and three improved protocols are proposed to prevent the aforementioned attacks.

1 Introduction

Using radio frequency identification (RFID) system was commenced in the World War II, when the identify friend of foe (IFF) system was deployed [1]. An RFID system usually consists of a large number of passive tags, readers, and one back-end server. RFID technology generally provides short distance wireless communication between the readers and the tags in varied applications such as biometric passport, enhanced driver license, pass checking in supply chain, ticketing in public transportation, anti-theft cars, e-health, etc. [2–4].

Although RFID systems are now one of the most popular technologies, they suffer from intrinsic restrictions on memory and computation capabilities. RFID is susceptible to tracing, replay attack, counterfeiting, denial of service, and physical tampering (reverse engineering of tags) [5]. It is undeniable that a secure and private RFID authentication protocol is essential to prevent the attacks.

Using strong cryptographic elements such as standard block ciphers, hash functions, and public key cryptography schemes are not acceptable. Therefore, to provide security and privacy, RFID authentication protocols are inevitably designed by lightweight cryptographic elements such as bitwise operations, pseudo random number generators, lightweight symmetric ciphers and hash functions [6–10]. Many RFID authentication protocols are compliant with electronic product code (EPC) standards [11, 12] that constraint protocols to apply only to cyclic redundancy checks (CRCs) and pseudo random number generators (PRNGs) on RFID tags. For the sake of simplicity, the notations used throughout this paper are presented in Table 1.

Table 1 List of notations

On the other hand, many proposed RFID authentication protocols have been analysed via ad hoc methods but all of their drawbacks have not been discovered. Hence, there is no doubt that we require a formal method to discover the privacy and security drawbacks, particularly information leakage and traceability in lightweight RFID authentication protocols [13].

In recent years, there has been an increasing amount of literatures on RFID privacy models. In 2005, Avoine et al. [14–16] introduced the first privacy model based on the untraceability notion for the RFID protocols. Avoine’s model is only able to consider 3-flows RFID protocols and therefore cannot highlight possible privacy attacks in all the protocols. Afterwards, Lim and Kwon [17] extended the Avoine’s approach to introduce a formal definition for forward and backward untraceability. Moreover, Juels and Weis [18] proposed another privacy model based on indistinguishability of the tags. In 2008, Ouafi and Phan [19, 20] published papers in which a more practical and understandable version of Juels’s model was described.

An RFID privacy model based on zero-knowledge was introduced by Deng et al. [21]. Although they claimed that the zero-knowledge based model is stronger compared to the Juels and Weis and Ouafi and Phan models, In 2012, Moriyama et al. [22] proved that these models have equivalent ability to privacy analysis.

In ASIACRYPT 2007, Vaudenay proposed the first simulation based model that not only allows the adversary to create fake tags, but the adversary’s ability is also classified into $2\times 4$ categories [23, 24]. Although, there is an ambiguous relationship between Vaudenay’s model and forward/backward traceability notion, regarding to some points in Sect. 2.6, the Vaudenay’s model is still almost the most complete model. The points impose no functionality changes on Vuadenay model. Thus, in the following, we analyse some new-found RFID protocols based on the Vaudenay formal privacy model.

The rest of this paper is organized as follows: Sect. 2 elaborates Vaudenay privacy model and its pros and cons. Although Vaudenay’s model contains worthwhile and unique features, we highlight some vague drawbacks especially in forward and backward traceability analysis and extend it. Then, three recently proposed protocols in [25–27] are analysed and modified via nine theorems in Sects. 3, 4 and 5, respectively. We compare the protocols with the improved versions and evaluate their performances in Sect. 6. Finally, the conclusion is presented in Sect. 7.

2 Privacy Models

Privacy models are utilized to consider possible vulnerabilities of RFID via some queries to the oracles. In this section, we review the existing simulation-based privacy models.

Vaudenay’s model is one of the most complete and powerful models so far. Since the tags are not tamper-proof, the powerful malicious adversary of Vaudenay’s model who can eavesdrop and interfere with all the communications, corrupts all the tags, and reveals both the related keys and initial states. However, strong private authentication protocols prevent adversary from tag tracing, identification, information leakage, and linking tags. Only in this model, every tag can be $\mathsf {free}$ or $\mathsf {drawn}$, and the adversary’s identity is temporary, also the adversary can create fake tags. In this section, after giving basic definitions and assumptions, the Vaudenay simulation-based model is criticized. The mentioned weaknesses only alter the pre-assumptions of Vaudenay model particularly in forward/backward traceability analysis and practically does not impose any change on the model. Therefore, the original Vaudenay model with revised assumpitions is applied for analysis in the next sections.

2.1 Basic Definitions

An RFID system comprise numerous tags and a few readers. $\mathcal {T}$ is a passive transponder with a few distinctive keys and an ID without battery. Being tamper-resistant for RFID tags is very uncertain and questionable. Hence, the rewritable memory of tags is not tamper-resistant and is vulnerable to corruption via $\mathcal {A}$. RFID tags are only able to perform lightweight cryptographic primitives. $\mathcal {T}$ and $\mathcal {R}$ communicate via an insecure RF interface. $\mathcal {T}$ can just operate into $\mathcal {R}$’s field communication. $\mathcal {R}$ is a device by some transceivers that has a secure connection with the back-end server. The $\mathcal {R}$’s first task is to authenticate legitimate tags for mutual interaction. The reader has the keys and the identity of every $\mathcal {T}$ in its database.

Definition 1

(RFID framework) Every RFID system performs the following algorithms [23, 28]:

• $\mathsf {SetupReader(1^{k})}$ generates all the essential system parameters including public/private pairwise keys depending on the security parameter $k$ for a secure connection with the server.

• $\mathsf {SetupTag(ID)}$ is utilized to generate tag secret key $K_{T}$ and initial state $S$ via system parameters. The created $K_{T}$ and $S$ should be stored into the $\mathcal {R}$’s database as well.

• $\mathsf {Protocol}$ is a polynomial-time, consecutive, and interactive messages exchanged between $\mathcal {T}$ and $\mathcal {R}$ governing the authentication process.

2.2 Adversary Oracles

In the Vaudenay’s model, the links between the reader and database is secure. However, $\mathcal {A}$ has permission to run the following queries for privacy analysis.

• $\mathsf {CreateTag^{b}}( ID )$ creates the $\mathsf {free}$ tag with unique $\mathcal {T_{ ID }}$ from the set of tags built by $\mathsf {SetupTag( ID _{i})} (1\le i \le n)$. $\mathcal {T}$ is either fake ($b=0$) or legitimate ($b=1$).

• $\mathsf {DrawTag}()$ randomly conveys one $\mathcal {T}$ from the set of $\mathsf {free}$ tags to the set of $\mathsf {drawn}$ tags as vtag. It also outputs the bit $b$ to indicate whether the drawn tag is legitimate or not. Subsequently, the pair $( vtag , ID )$ is registered into $\mathcal {R}$’s database ($\mathsf {DB}$).

• $\mathsf {Free}( vtag )$ returns the $vtag$ to the set of $\mathsf {free}$ tags. Therefore, $\mathcal {A}$ cannot access the $vtag$ again unless it is made $\mathsf {drawn}$ via $\mathsf {DrawTag}()$ under the new $vtag ^{'}$ identifier. In fact a tag can be $\mathsf {free}$ or $\mathsf {drawn}$ every time and it has two temporary identities provided that the same tag with $\mathcal {T_{ ID }}$ is drawn, freed, and drawn. Moreover, the related ${ ID}$ is deleted from $\mathsf {DB}( vtag )$ as well.

• $\mathsf {Launch}()\rightarrow \pi$ gives permission to $\mathcal {R}$ to begin a new session of protocol $\pi$.

• $\mathsf {SendReader}(m,\pi )\rightarrow m^{'}$ sends message $m$ to $\mathcal {R}$ in protocol instance $\pi$. $m^{'}$ is returned as a unique and unrepeatable response.

• $\mathsf {SendTag}(m, vtag )\rightarrow m^{'}$ sends the message $m$ to the $\mathcal {T}_{ ID }$ which is identified as $vtag$ for $\mathcal {A}$ and responds with $m^{'}$.

• $\mathsf {Result}(\pi )$ outputs 1 if the session $\pi$ is successfully completed or 0 otherwise.

• $\mathsf {Corrupt}( vtag )\rightarrow S$ returns the initial states and secret keys of the tag $vtag$.

2.3 Adversary Class

An adversary is a polynomial time algorithm against the RFID system $\mathcal {S}$ that can arbitrarily utilize the oracles mentioned in Sect. 2.2. The adversary’s ability is classified into $2\times 4$ categories [23, 24] ($\{\mathsf {Wide}, \mathsf {Narrow} \} \cup \{ \mathsf {Weak, Forward,} \mathsf { Destructive, Strong} \}$) based on access to $\mathsf {Result}$ and $\mathsf {Corrupt}$ oracles:

• $\mathsf {Strong} \, \mathcal {A}$ has access to all the eight oracles without any restrictions.

• $\mathsf {Destructive} \, \mathcal {A}$ destroys the corrupted tag. It does not have permission to query any oracle after sending the first $\mathsf {Corrupt}()$ to $vtag$. However, $\mathcal {A}$ can use the corrupted information against the other tags.

• $\mathsf {Forward} \, \mathcal {A}$ is restricted to use $\mathsf {Corrupt}$ only once as the last oracle.

• $\mathsf {Weak} \, \mathcal {A}$ cannot access to $\mathsf {Corrupt}$ at all. Orthogonal to the four classes:

• $\mathsf {Narrow} \, \mathcal {A}$ is not able to use $\mathsf {Result}$ oracle.

• $\mathsf {Wide} \, \mathcal {A}$ has access to the $\mathcal {R}$ verification result, opposite to $\mathsf {Narrow}$.

It is open-and-shut that $\mathsf {Weak} \subseteq \mathsf {Forward} \subseteq \mathsf {Destructive} \subseteq \mathsf {Strong}$. Regarding the broad range of $\mathcal {A}$’s ability from $\mathsf {Narrow-Weak}$ to $\mathsf {Wide-Strong}$, the Vaudenay-based models [21, 23, 24, 28, 29] are so-called simulation-based models.

Definition 2

(Privacy levels) [13, 30]. Let $X$ be an adversary class according to Sect. 2.3. The RFID system $\mathcal {S}$ is $X$-private if the same $X$-level $\mathcal {A}$ can win the privacy experiment only with negligible probability. The relation between privacy levels are described below ($\mathsf {N.}$ stands for $\mathsf {Narrow}$):

The $\mathsf {Nil}$ privacy level is dedicated for protocols that do not provide any privacy level [30].

2.4 Privacy Experiment

The Vaudenay’s simulation-based privacy game consists of two parts including attack and analysis phases. In the attack phase, $\mathcal {A}$ is able to send oracles regarding the adversary class $X$. In the analysis phase, $\mathcal {A}$ receives $\mathcal {R}$’s database ($\mathsf {DB}$) related to the $vtag$ which has been hidden to it till this phase. Then, it outputs true or false. As long as the outcome be true with more than negligible probability, the adversary will be succeeded. In contrast, the related $\mathcal {A}$ is trivial and the authentication protocol supports $X$-privacy level.

Definition 3

(Privacy) A blinded adversary $\mathcal {A^{B}}$ does not have access to $\mathsf {Launch}, \mathsf {SendReader}, \mathsf {SendTag}$, and $\mathsf {Result}$. It can only query $\mathsf {Corrupt}$ oracle. Then, if $|Pr(Exp^\mathcal {A}_{S} succeeds )- Pr (Exp^\mathcal {A^{B}}_{S} \quad succeeds )|$ is negligible, $\mathcal {A}$ is called trivial $\mathcal {A}$ depending on the related adversary class. The privacy rely on success probability of trivial adversary.

Therefore, since $\mathcal {A^{B}}$ is not permitted to execute protocols, the trivial adversary indicates the information leakage ratio in the wireless channel. Intuitively, since tag corruption is exactly the same as privacy compromising, if both $\mathcal {A}$ and $\mathcal {A^{B}}$ produce same output, the adversary is trivial and the protocol is $X$-private. The adversary’s ability, in privacy analysis (Theorems 1–9), is equivalent to the highest related privacy level. Indeed, an RFID authentication protocol is $X$-private, provided the $X$-level $\mathcal {A}$ could not win the privacy experiment with more than negligible probability.

2.5 Simulation-Based Privacy Models

After Vaudenay’s model, in recent years, there has been an increasing amount of literature to extend it. In this part, we survey the seminal simulation-based privacy models and analyze their pros and cons.

Despite the fact that the adversary in Vaudenay’s model is only allowed to create unregistered fake tags, the model has no precise definition for the privacy notion [13]. For instance, although the majority of privacy concepts such as traceability and forward/backward traceability [19, 20] can be simulated via this model, there is an inconsistency with adversary’s abilities.

Moreover, Vaudenay’s analysis does not take account of reader authentication to tags. In 2008, Paise and Vaudenay [24] enriched the model to get secure mutual authentication. Indeed, $\mathcal {T}$ can accept or reject a legitimate $\mathcal {R}$. Armknecht et al. [31, 32] however claim that Paise and Vaudenay improvement could not guarantee both the strongest privacy notions and reader authentication together. More recent arguments against Armknecht’s viewpoint have been summarised in [33]. Not only the privacy definition and the adversary goal presented by Armknecht et al. are completely different from the Paise–Vaudenay ones, but also the highest achievable privacy level is $\mathsf {Narrow-Weak}$, not $\mathsf {Strong}$.

In 2010, Canard et al. [34] propose another Vaudenay-based model only for untraceability notion examination. Contrary to Vaudenay’s model, the adversary class is decreased from 8 to 3 levels. The authors with the aid of the notion of non-obvious link (NOL) and dummy $\mathcal {A}$ instead of blinder $\mathcal {A}$ recommend a formal untraceability analysis routine. Nevertheless, this method contains number of limitations. Perhaps the most serious disadvantage of this method is that no $\mathsf {Narrow}$ adversary is applied; thus many protocols are regarded untraceable.

Following Vaudenay’s model, Hermans et al. [28] propose a new indistinguishable privacy model. Although Vaudenay derived that $\mathsf {Wide-Strong}$ privacy is impossible even with IND-CCA public key cryptosystems, they proved that $\mathsf {Wide-Strong}$ privacy level is accessible via public key cryptography even though the related oracles are quite similar to Vaudenay’s model.

Although Hermans et al. recently assert that their model does not suffer from the identified drawbacks, it has several defects: (1) $\mathsf {DrawTag}$ is only applicable on two tags ($\mathcal {T}_{i},\mathcal {T}_{j}$). In fact $\mathcal {A}$ is constrained to opt just between the two drawn tags; (2) the adversary cannot create fake tags; (3) $\mathsf {Corrupt}$ oracle is not authorized on the $\mathsf {drawn}$ tags; (4) similar to Vaudenay’s model, it still has vague privacy notion [13]. On the whole, as the authors mentioned, this refurbished version of Vaudenay’s model does not take into account the attributes that might leak private information. Hermans et al. practically performs a trade-off between $\mathcal {A}$’s power and achievable privacy levels.

On the other hand, as it is impossible to achieve the strongest privacy level of Vaudenay’s model ($\mathsf {Wide \, Strong}$), several adaptations have been performed lately. Ng et al. [29] restrain the adversary to $\mathsf {Wise}$ adversary such that it is not able to utilize the same oracle again with the same input and categorize the eight privacy level of Vaudenay’s model into three levels. Although they proved that it is possible to achieve strong privacy, the adversary’s ability is indeed restricted to wise level compared with $\mathcal {A}$ of Vaudenay’s model. Additionally, Armknecht et al. also show the impossibility of reader authentication combined with strong privacy.

Afterwards, Avoine et al. [35] highlight a notion about $\mathcal {R}$’s computational time in Vaudenay’s model with the new $\mathsf {TimeFul}$ oracle. Since the tags have to constantly send the time variant information to $\mathcal {R}$ owing to untraceability characteristic, the reader needs to carry out an exhaustive search procedure in its $\mathsf {DB}$. The search time that $\mathcal {R}$ require to authenticate $\mathcal {T}$ is regularly fixed. Therefore, $\mathcal {A}$ can find the given $\mathcal {T}$ provided it computes the time itself via $\mathsf {TimeFul}$ oracle. Thus, apart from $\mathsf {Narrow}$, the four privacy levels can be $\mathsf {TimeFul}$ (e.g. $\mathsf {TimeFul-Strong}$). Although it is an important issue for private protocols, it needs the further information leakage as side channel information from $\mathcal {R}$ to $\mathcal {A}$.

2.6 Forward/Backward Untraceability Notions

In this section we revisit forward and backward untraceability (UNT) notions in Vaudenay’s model. Forward and backward-UNT should not be regarded as a kind of traceability attack. However, all of them can be considered as the location privacy notion. Not only $\mathcal {A}$ lacks $\mathsf {Corrupt}$ oracle to query in the notion of traceability attack, but also the traceability analysis is only executed at present. To find traceability vulnerabilities, $\mathcal {A}$ has only permission to perform both active and passive attacks in the attack phase without $\mathsf {Corrupt}$ oracle. Then, after receiving $\mathsf {DB}$ in the analysis phase, it should distinguish the original $\mathcal {T}$ between the set of tags.

The notion of forward untraceability, which is essential for private ownership transfer of RFID tags, is defined as: even if a tag is corrupted at the session $r$ leaking its stored secret, it should be impossible for the $\mathsf {Strong}$ adversary to trace the tag at the session $r'$ that $r'\ge r+2$ [20, 36].

In contrast, the notion of backward untraceability (forward privacy) is related to prior to the tag corruption. Backward untraceability states that even if given all the internal states of a tag at session $r$, the $\mathsf {Strong}$ adversary should not be able to identify the target tag’s interactions that occur at the session $r'$ that $r'< r''$ [36]. In fact $\mathcal {A}$ desires to trace the paced way in the past by corruption in the current session. Finally, the experiments $Exp^{Forward}_{S, \mathcal {A}}(k)$ or $Exp^{Backward}_{S, \mathcal {A}}(k)$ succeed as long as $\mathcal {A}$ returns true.

In 2011, Akgün and Çağlayan [37] lately apply the Vaudenay’s model for forward untraceability consideration of three symmetric lightweight RFID authentication protocols. Vaudenay proved that only public key cryptography can guarantee the highest level of feasible privacy ([$\mathsf {Narrow}$]-$\mathsf {Strong}$ privacy) and symmetric cryptography-based protocols can achieve at last either $\mathsf {Desructive}$ or $\mathsf {Forward}$ privacy levels [23, 24]. Since Akgün and Çağlayan utilize $\mathsf {Strong}$ adversary to analyse symmetric lightweight protocols, it seems that their understanding of the Vaudenay framework is highly questionable. There is no way to apply $\mathsf {Strong} \mathcal {A}$ for the protocols with $\mathsf {Desructive}$ or $\mathsf {Forward}$ privacy levels.

Moreover, Ng et al. classify the mutual synchronized RFID authentication protocols based on their constructions. They mentioned that $\mathsf {Narrow-Forward} \mathcal {A}$ against symmetric mutual protocols with key updating procedure and no access to $\mathsf {Corrupt}$ and $\mathsf {Result}$ oracles, succeeds to win $Exp^{N.- Forward \mathcal {A}}_{S}(k)$ by overwhelming probability [30]. Thus the protocols are only able to achieve $\mathsf {Weak}, \mathsf {Narrow-Weak}$, or $\mathsf {Nil}$ privacy levels and forward/backward untraceability consideration are impractical.

On the other hand, Ouafi and Phan in [19, 20] defined a modified version of [36] based on Juels model [18]. In contrast to Vaudenay’s model, this IND-based model gives permission to $\mathcal {A}$ for finding forward/backward traceable vulnerabilities apart from both $\mathcal {A}$’s strength and traceability analysis outcomes.

For instance, assume symmetric protocol A is weak in both forward traceability and traceability attacks and symmetric protocol B resists forward traceability attack but it is vulnerable to traceability attack in the IND-based Ouafi model. Nevertheless, the Vaudenay’s model claims that A and B protocols ensure only either $\mathsf {Narrow-Weak}$ or $\mathsf {Nil}$ privacy levels. Therefore, although the Vaudenay’s model has good unique features associated with the present time, unlike the Ouafi, it can not distinguish between A and B and requires to be amended with the Ouafi forward/backward-UNT notions in the past and future. Perhaps this is the most serious disadvantage of Vaudenay method. Although Vaudenay’s model seems to be a comprehensive model, there is the subtle distinguished advantage of IND-based models (e.g. Ouafi) compared with simulation-based models (e.g. Vaudenay). Hence the pre-assumption of Vaudenay’s model should be alleviated to compensate its drawback in forward/backward analysis.

In a nutshell, at first glance Akgün and Çağlayan wrongly used Vaudenay’s model because they did not mention the faint drawback. This finding, while preliminary, suggests that the Vaudenay’s model is able to simulate forward/backward-UNT notions regardless of the achievable privacy level because the privacy notions of all the IND-based models can be simulated through it. Thus, we practically apply Vaudenay’s model without functionality changes but with different pre-assumption’s interpretation.

For more readability, the notified privacy models are compared in Table 2 due to [13]. As can be seen, The Vaudenay model has noticeable advantages. In the following sections, the traceability notions are simulated by means of Vaudenay model inspired Ouafi model in assumptions. We analyse three new-found symmetric RFID authentication protocols. Not only we clearly prove that the three of these protocols suffer from the traceability attacks, also the mentioned weaknesses are alleviated in the improved protocols.

Table 2 The comparison of presented privacy models [13]

3 The NRS Protocol

Fernando and Abawajy [25] proposed an lightweight RFID authentication protocol, called NRS, based on EPCglobal Class-1 Generatio-2 standard [11, 12]. NRS uses only hash function and XOR operation. Figure 1 displays the detailed interaction flows of the NRS authentication protocol. Although the authors claim that NRS is immune to security and privacy attacks, we prove that NRS suffer from both traceability and forward/backward traceability attacks.

Fig. 1

The NRS protocol [25]

Theorem 1

The NRS protocol does not support even $\mathsf {Narrow-Forward}$ privacy.

Proof

To prevent desynchronization attack, the NRS contains reader authentication and key updating, however, it achieves at last $\mathsf {Weak}$ privacy level. First, $\mathcal {A}$ obtains $M_{1},M_{2}$ and $M_{3}$ related to $ID _{b}$ and obstructs $M_{3}$ in the attack phase. Then, $\mathsf {Corrupt}( vtag ^{'})$ is queried as the last oracle. After receiving $\mathsf {DB}$ in the analysis phase, $\mathcal {A}$ is able to compute $M_{3}^{b}$ by means of the corrupted keys. It terminates the attack and outputs bit $x$. The attack fails only with negligible probability provided the secrets of $\mathcal {T}_{ ID _{0}}$ and $\mathcal {T}_{ ID _{1}}$ represent the same. Since there is just one time access to $\mathsf {Corrupt}( vtag ^{'})$ as the last query and no access to $\mathsf {Result}(\pi )$, this is a $\mathsf {Narrow-Forward}$ privacy level attack.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi ^{i}\longleftarrow \mathsf {Launch}$

• $M_{1}^{i}, M_{2}^{i}\longleftarrow \mathsf {SendReader}(\pi ^{i}, Init , ID )$

• $M_{3}^{i}\longleftarrow \mathsf {SendTag}( vtag ,M_{1}^{i}, M_{2}^{i})$

• $\mathsf {Free}( vtag )$ The $i$th session is incomplete.

• $vtag ^{'} \longleftarrow \mathsf {DrawTag}()$

• $K_{1_{x}}, K_{2_{x}}, EPC _{x}\longleftarrow \mathsf {Corrupt}( vtag ^{'})$

• The queries is ended, receive $\tau ( vtag )= ID _{b}$

• $r_{x}^{i}=M_{2}^{i} \oplus K_{1_{x}}$ and $M_{3}^{b}=H( EPC _{x} \oplus K_{2_{x}} \oplus r_{x}^{i})$

• If $M_{3}^{b}=M_{3}^{i}$ then $x=b$ O.W. $x=\vert 1-b\vert$

• Output whether $\tau ( vtag ^{'})= ID _{x}$ $\square$

Theorem 2

The NRS protocol is traceable and only $\mathsf {Nil}$-private.

Proof

Although $\mathcal {A}$ is not permitted to apply $\mathsf {Corrupt}$ and $\mathsf {Result}$ based on traceability definition, the NRS protocol is still traceable just by means of active and passive attacks. Generally, every traceable protocol has no privacy level ($\mathsf {Nil}$). $\mathcal {A}$ eavesdrops the whole of one session and in the third flow toward $\mathcal {T}$ it modifies $M_{4}$ and $M_{5}$ to two random numbers ($r_{m_{4}}, r_{m_{5}}$). Then, in the analysis phase, $M_{1}$ and $M_{2}$ are sent again for $vtag ^{'}$. It is not hard to see that $vtag ^{'}$ is exactly the same as $vtag$ provided $M_{3}^{'}=M_{3}$, and vice versa.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi \longleftarrow \mathsf {Launch}$

• $M_{1}, M_{2}\longleftarrow \mathsf {SendReader}(\pi , Init , ID )$

• $M_{3}\longleftarrow \mathsf {SendTag}( vtag ,M_{1}, M_{2})$

• $M_{4}, M_{5}\longleftarrow \mathsf {SendReader}(\pi , M_{3})$

• $\mathcal {A}$ chooses 2 random number $r_{m_{4}}$ and $r_{m_{5}}$

• $Null\longleftarrow \mathsf {SendTag}( vtag ,r_{m_{4}},r_{m_{5}})$

• $\mathsf {Free}( vtag )$

• $vtag ^{'}\longleftarrow \mathsf {DrawTag}()$ between 2 tags

• $M_{3}^{'}\longleftarrow \mathsf {SendTag}( vtag ^{'},M_{1},M_{2})$

• The queries is ended, receive $\tau ( vtag )= ID _{b}$

• If $M_{3}^{'}=M_{3}$ then $x=b$    O.W.    $x=\vert 1-b\vert$ $\square$

Theorem 3

The NRS protocol does not provide forward untraceability.

Proof

$\mathcal {A}$ makes $\mathsf {Corrupt}(\mathcal {T}_{b})$ to obtains $K_{1_{i}}, K_{2_{i}}, ID _{i},$ and $EPC$. Then,

$$ \begin{aligned}&K_{1_{i+1}}=(K_{1_{i_{right}}}\parallel \ K_{2_{i_{left}}})\oplus r_{2} \quad \& \quad K_{2_{i+1}}=(K_{2_{i_{right}}}\parallel K_{1_{i_{left}}})\oplus r_{2} \nonumber \\&\quad \Longrightarrow K_{1_{i+1}} \oplus K_{2_{i+1}} =(K_{1_{i_{right}}}\parallel K_{2_{i_{left}}}) \oplus (K_{2_{i_{right}}}\parallel K_{1_{i_{left}}}) \nonumber \\&=(K_{1_{i_{right}}} \oplus K_{2_{i_{right}}} )\parallel (K_{2_{i_{left}}}\oplus K_{1_{i_{left}}}) \nonumber \\&=(K_{1_{i}} \oplus K_{2_{i}} )_{right}\parallel (K_{2_{i}}\oplus K_{1_{i}})_{left} \end{aligned}$$

(1)

Subsequently,

$$\begin{aligned} K_{1_{i+2}} \oplus K_{2_{i+2}}&= \left( K_{1_{i+1_{ right }}} \oplus K_{2_{i+1_{ right }}}\right) \parallel \left( K_{2_{i+1_{ left }}} \oplus K_{1_{i+1_{ left }}}\right) \nonumber \\&= \left( K_{1_{i+1}} \oplus K_{2_{i+1}}\right) _{ right }\parallel \left( K_{2_{i+1}} \oplus K_{1_{i+1}}\right) _{ left } \nonumber \\&=\left( K_{1_{i}}\oplus K_{2_{i}}\right) _{ left } \parallel \left( K_{1_{i}}\oplus K_{2_{i}}\right) _{ right } \nonumber \\&=K_{1_{i}} \oplus K_{2_{i}} \end{aligned}$$

(2)

Since $K_{1_{i+1}}\oplus K_{2_{i+1}}$ is independent of any random numbers, we prove that $K_{1_{i+2}} \oplus K_{2_{i+2}}$ is simply computable via corruption of $K_{1_{i}}$ and $K_{2_{i}}$ in session $i$.

Regarding this drawback, the NRS is vulnerable to forward traceability attack. After $vtag$ corruption in the attack phase of the experiment, $\mathcal {A}$ queries $\mathsf {Execute}$ oracle in session $i+2$ to achieve $M_{1}^{i+2},M_{2}^{i+2},$ and $M_{3}^{i+2}$. Later, $\mathcal {A}$ randomly sends $\mathsf {DrawTag}( ID _{c})$ between $ID _{0}$ and $ID_{1} ( c \in \lbrace 0,1\rbrace )$ and mostly chooses $i+2$ time interval for the analysis phase. Related to $vtag ^{x}$, it can compute $\quad Y=K_{2_{x}}^{i+2}\oplus r_{x}^{i+2}= M_{2_{x}}^{i+2} \oplus K_{1_{x}}^{i+2} \oplus K_{2_{x}}^{i+2}$.

Finally, the related $\mathcal {T}$ is distinguished by means of $M_{3}^{i+2}$.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $K_{1_{c}}^{i}, K_{2_{c}}^{i}, ID _{c}^{i}\longleftarrow \mathsf {Corrupt}()$

• $\mathsf {Free}( vtag )$

• $vtag ^{x}\longleftarrow \mathsf {DrawTag}( ID _{c})$

• $\mathcal {A}$ chooses another time interval $I\ge (i+2)th$ session (generally $I=[i+2]$)

• $\pi _{i+2}\longleftarrow \mathsf {Launch}$

• $M_{1}^{i+2},M_{2}^{i+2}\longleftarrow \mathsf {SendReader}(\pi _{i+2}, Init )$

• $M_{3}^{i+2}\longleftarrow \mathsf {SendTag}( vtag ^{x},M_{1}^{i+2},M_{2}^{i+2})$

• If $H( EPC \oplus Y)=M_{3}^{i+2}$ then $x=c$    O.W.    $x=\vert 1-c \vert$ $\square$

Theorem 4

The NRS protocol is backward traceable as well.

Proof

This attack is quite similar to forward traceability. However, the notion of backward untraceability (forward privacy) is related to prior to corruption of the tag. The adversary receives $\mathcal {T}_{b}$’s secrets and computes $H( EPC \oplus K_{2}^{i-1} \oplus r^{i-1})$ to compare with $M_{3}^{i-1}$. Similar to equation 1, $K_{1}^{i-1} \oplus K_{2}^{i-1}$ is computable as following:

$$\begin{aligned}&K_{1}^{i} \oplus K_{2}^{i} =\left( K_{1}^{i-1} \oplus K_{2}^{i-1}\right) _{ right }\parallel \left( K_{2}^{i-1}\oplus K_{1}^{i-1}\right) _{ left } \nonumber \\&\quad \Longrightarrow K_{1}^{i-1} \oplus K_{2}^{i-1}= \left( K_{1}^{i} \oplus K_{2}^{i}\right) _{ right } \parallel \left( K_{1}^{i} \oplus K_{2}^{i}\right) _{ left } \end{aligned}$$

(3)

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $K_{1_{c}}^{i}, K_{2_{c}}^{i}, ID _{c}^{i}\longleftarrow \mathsf {Corrupt}()$

• $\mathsf {Free}( vtag )$

• $vtag ^{x}\longleftarrow \mathsf {DrawTag}( ID _{c})$

• $\mathcal {A}$ chooses another time interval $I\le (i-1)th$ session (generally $I=[i-1]$)

• $\pi _{i-1}\longleftarrow \mathsf {Launch}$

• $M_{1}^{i-1},M_{2}^{i-1}\longleftarrow \mathsf {SendReader}(\pi _{i-1}, Init)$

• $M_{3}^{i-1}\longleftarrow \mathsf {SendTag}( vtag ^{x},M_{1}^{i-1},M_{2}^{i-1})$

• $Z=M_{2_{x}}^{i-1} \oplus K_{1_{x}}^{i-1} \oplus K_{2_{x}}^{i-1}= K_{2_{x}}^{i-1} \oplus r^{i-1}$

• If $H( EPC \oplus Z)=M_{3}^{i-1}$ then $x=c$ O.W. $x=\vert 1-c\vert$

Eventually, it is clear that $Pr [\mathcal {A} \, succeeds ]=1$ but $Pr[\mathcal {A^{B}} \, succeeds ]=\frac{1}{2}$ because $\mathcal {A^{B}}$ could not eavesdrop the protocol’s flows. Thus, since the adversary is not trivial the backward traceability attack is applicable on the NRS as well.

$$\begin{aligned} Pr [\mathcal {A} \, succeeds ]- Pr [\mathcal {A^{B}} \, succeeds ] \gg \epsilon . \end{aligned}$$

$\square$

3.1 The Improved NRS

As aforementioned, the NRS suffers from both traceability and forward/backward traceability attacks. The vulnerability of the protocol arises because $\mathcal {T}$ does not have any contribution in the randomness of the NRS protocol. The simplest most logical way to restrain from traceability is using the PRNG. Due to the fact that the PRNG is not utilized any more in the tag’s side of NRS protocol and PRNG also imposes the noticeable computational and memory overhead on the tags, the solution is irrational. Thus one more bit $\alpha$ assists us for prevention traceability. $\mathcal {T}$ sets $\alpha =0$ at the end of the correct key updating phase. At the same time and prior to $M_{3}$ computing (flow 2), $\alpha$ is checked. If $\alpha \ne 0$, the flow 3 ($M_{4}\parallel M_{5}$) was modified at the last session and $\mathcal {T}$ computes $\tilde{M}_{3}=H(H( EPC )\oplus K_{2} \oplus r)$ rather than $M_{3}$, otherwise $\mathcal {T}$ computes $M_{3}$ and sets $\alpha =r$. On the other side, $\mathcal {R}$ computes $\tilde{C}_{2}$ to compare with $\tilde{M}_{3}$ as long as $C_{2} \ne M_{3}$. If $\mathcal {A}$ repeats the previous attack scenario two times, the traceability of tag is impractical in the improved NRS protocol because $\mathcal {R}$ synchronizes the keys with $ID _{ old }, K_{1 old },$ and $K_{2 old }$ in every session for prevention of the attack.

Furthermore, lack of correlation between $K_{1_{ new }} \oplus K_{2_{ new }}$ and random numbers $r \mathrm{and} r_{2}$ causes forward/backward traceability. As an alleviation, $\mathcal {T}$ should update the common keys as below in every session:

$$\begin{aligned} K_{1 new }=H[(K_{1 right } \parallel K_{2 left }) \oplus r_{2}] \quad \mathrm{and} \quad K_{2 new }=H[(K_{2 right } \parallel K_{1 left }) \oplus r_{2}] \end{aligned}$$

Proof

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi \longleftarrow \mathsf {Launch}$

• $M_{1}, M_{2}\longleftarrow \mathsf {SendReader}(\pi , Init, ID)$

• $M_{3}\longleftarrow \mathsf {SendTag}( vtag ,M_{1}, M_{2})$

• $M_{4}, M_{5}\longleftarrow \mathsf {SendReader}(\pi , M_{3})$

• $\mathcal {A}$ chooses 2 random number $r_{m_{4}}$ and $r_{m_{5}}$

• $Null\longleftarrow \mathsf {SendTag}( vtag ,r_{m_{4}},r_{m_{5}})$

• $\mathsf {Free}( vtag )$

• $vtag ^{'}\longleftarrow \mathsf {DrawTag}()$ between 2 tags

• $\tilde{M}_{3}\longleftarrow \mathsf {SendTag}( vtag ^{'},M_{1},M_{2})$ (Since $\alpha \ne 0$)

• The queries is ended, receive $\tau ( vtag )= ID _{b}$

• Since $\tilde{M}_{3} \ne M_{3} \mathcal {A}$ is not able to trace $vtag ^{'}$ and eventually

• $Pr [\mathcal {A} \, succeeds ]- Pr [\mathcal {A^{B}} \, succeeds ] \ll \epsilon \nonumber$ in the Improved-NRS protocol. $\square$

4 The FSA Protocol

He et al. [38] proposed the forward-secure protocol, but Zhu et al. [26] find its drawbacks and alleviate it as the improved forward-secure (FSA) protocol. The lightweight hash-based FSA protocol is depicted in Fig. 2.

Fig. 2

The FSA protocol [26]

Theorem 5

The FSA protocol does not even support $\mathsf {Narrow-Forward}$ privacy.

Proof

Although FSA is traceable and $\mathsf {Nil}- private$ (see Theorem 6), it supports at the most $\mathsf {Weak}$ privacy level regardless of traceability attack analogous to the NRS protocol. First, $\mathcal {A}$ eavesdrops the whole of one session and changes the third flow to the random number $s$. Then, since it can obtain $K_{ ID _{x}}$ via corruption in the analysis phase, $\tilde{h}_{1}^{i}$ is computable and comparable with $h_{1}^{i}$ revealed in the attack phase and $\mathcal {A}$ succeeds with overwhelming probability. Since there is just one time access to $\mathsf {Corrupt}( vtag ^{'})$ as the last query and no access to $\mathsf {Result}(\pi )$, this is the attack on $\mathsf {Narrow-Forward}$ privacy level.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi ^{i}\longleftarrow \mathsf {Launch}$

• $t_{r}^{i}, r_{r}^{i}\longleftarrow \mathsf {SendReader}(\pi ^{i}, Init)$

• $h_{1}^{i}, r_{t}^{i}\longleftarrow \mathsf {SendTag}( vtag ,t_{r}^{i}, r_{2}^{i})$

• $h_{2}^{i}\longleftarrow \mathsf {SendReader}(\pi ^{i}, h_{1}^{i}, r_{t}^{i})$

• Replace $h_{2}^{i}$ with the random number $s\ne h_{2}^{i}$

• $null \longleftarrow \mathsf {SendTag}( vtag ,s)$

• $\mathsf {Free}( vtag )$ The update phase is not executed.

• $vtag ^{'} \longleftarrow \mathsf {DrawTag}()$

• $K_{ ID _{x}}\longleftarrow \mathsf {Corrupt}( vtag ^{'})$

• The queries is ended, receive $\tau ( vtag ^{'})= ID _{b}$

• $K_{x}^{i}$ is revealed If $h_{1}^{i}=\tilde{h}_{1}^{i}\longleftarrow \lbrace H_{K_{x}^{i}}(0,t_{r}^{i},r_{r}^{i}) \, or \, H_{K_{x}^{i}}(1,r_{t}^{i},r_{r}^{i})\rbrace$

• Then $x=b$ O.W. $x=\vert 1-b\vert$

• Output whether $\tau ( vtag ^{'})= ID _{x}$ $\square$

Theorem 6

The FSA protocol is traceable and only $\mathsf {Nil}$-private.

Proof

$\mathcal {A}$ eavesdrops the flows 1 and 2 of one session. After receiving $\mathsf {DB}$ in the analysis phase, it queries $\mathsf {SendTag}$ to obtain $h_{1}^{'}, r_{t}^{'}$ at $t_{r}^{'}$ which clearly $t_{r}^{'}>t_{r}$ with noticeably higher than negligible probability.

$$\begin{aligned} \left( Pr [\mathcal {A} \, succeeds ]=1 - Pr [\mathcal {A^{B}} \, succeeds ]=\frac{1}{2}\right) \gg \varepsilon \end{aligned}$$

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi \longleftarrow \mathsf {Launch}$

• $t_{r}, r_{r}\longleftarrow \mathsf {SendReader}(\pi , Init)$

• $h_{1}, r_{t}\longleftarrow \mathsf {SendTag}( vtag ,t_{r}, r_{r})$

• $\mathsf {Free}( vtag )$

• $vtag ^{'} \longleftarrow \mathsf {DrawTag}()$ randomly between the two tags

• $h_{1}^{'}, r_{t}^{'}\longleftarrow \mathsf {SendTag}( vtag ^{'},t_{r}^{'}>t_{r}, r_{r})$

• $t_{r}^{'}>t_{r} \Rightarrow t_{r}^{'}>t_{t}^{'}$

• If $h_{1}^{'}=h_{1}$ Then $x=b$ O.W. $x=\vert 1-b\vert$

• Output whether $\tau ( vtag ^{'})= ID _{x}$ $\square$

Although the traceability proof is rather similar to the proof of Theorem 5, the untraceability notion of Ouafi model is generally lower than Vaudeney’s forward privacy level because the $\mathcal {T}$ corruption is not utilized.

Theorem 7

The FSA protocol does not provide forward untraceability.

Proof

$\mathcal {A}$ sends $\mathsf {Corrupt}$ oracle to $\mathcal {T}_{c}$ in session $i$. It can plainly compute the secret key of corrupted tag in the future. So in session $i+2, \mathcal {A}$ obtains a transcript of the executed protocol between $\mathcal {T}_{c}$ and $\mathcal {R}$. The adversary can compute $h_{1_{x}}^{i+2}$ and $h_{1_{x}}^{'^{i+2}}$ with the aid of $K_{i+2}^{x}$. If $h_{1}^{i+2}=h_{1_{x}}^{i+2}$ or $h_{1}^{i+2}=h_{1_{x}}^{'^{i+2}}, vtag ^{'}$ is $\mathcal {T}_{c}$; otherwise $\mathcal {T}_{\vert 1-c \vert }$.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}( ID _{c})$ where $c \mathop {\varepsilon }\limits ^{R} \lbrace 0,1 \rbrace$

• $K_{i}^{c}\longleftarrow \mathsf {Corrupt}()$ at time interval $[i-1 i+1]$

• $\mathsf {Free}( vtag )$

• $vtag ^{x} \longleftarrow \mathsf {DrawTag}( ID _{x})$ randomly between the two tags

• $\mathcal {A}$ chooses another time interval (generally $I=[i+2]$)

• ($K_{i+1}^{x}=H(K_{i}^{x}), \quad K_{i+2}^{x}=H(K_{i+1}^{x})$)

• $\pi _{i+2}\longleftarrow \mathsf {Launch}$

• $t_{r}^{i+2}, r_{r}^{i+2}\longleftarrow \mathsf {SendReader}(\pi _{i+2}, Init)$

• $h_{1}^{i+2}, r_{t}^{i+2}\longleftarrow \mathsf {SendTag}( vtag ^{x},t_{r}^{i+2}, r_{r}^{i+2})$

• $\mathcal {A}$ computes $h_{1_{x}}^{i+2}=H_{K_{x}^{i+2}}(0,t_{r}^{i+2},r_{r}^{i+2}) \, \mathrm{and} \, h_{1_{x}}^{'^{i+2}}=H_{K_{x}^{i}}(1,r_{t}^{i+2},r_{r}^{i+2})$

• The queries is ended, receive $\tau ( vtag ^{'})= ID _{x}$

• If either $h_{1}^{i+2}=h_{1_{x}}^{i+2}$ or $h_{1}^{i+2}=h_{1_{x}}^{'^{i+2}}$ Then $x=c$ O.W. $x=\vert 1-c\vert$

• Output whether $\tau ( vtag ^{x})= ID _{x}$ $\square$

4.1 The Improved FSA

In the FSA protocol, the most important drawback is lack of refresher in $h_{1}$ computing when $t_{r} > t_{t}$. We suggest $h_{1}^{*}=H_{k}(\lbrace 0 \, or 1 \, \rbrace , r_{t}, r_{r})$ rather than $h_{1}=H_{K}(\lbrace 0 \, or 1 \, \rbrace ,\lbrace t_{r} \, or \, r_{t} \rbrace , r_{r})$. Moreover, the key updating procedure should be improved by means of $r_{t_{i}}$ to prevent forward traceability. After receiving the flow 3 ($h_{2}$) in Fig. 2 and confirmation, $\mathcal {T}$ updates the related keys $K_{i+1}=H(K_{i},r_{t_{i}})$. Even if $\mathcal {A}$ corrupts $K_{i}$ in session $i$, the computation of $K_{i+2}=H(K_{i+1},r_{t_{i+1}})$ is impractical because it has no access to $K_{i+1}$.

Proof

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}( ID _{c})$ where $c \mathop {\varepsilon }\limits ^{R} \lbrace 0,1 \rbrace$

• $K_{i}^{c}\longleftarrow \mathsf {Corrupt}()$ at time interval $[i-1$ $i+1]$

• $\mathsf {Free}( vtag )$

• $vtag ^{x} \longleftarrow \mathsf {DrawTag}( ID _{x})$ randomly between the two tags

• $\mathcal {A}$ chooses another time interval (generally $I=[i+2]$)

• ($K_{i+1}^{x}=H(K_{i}^{x}, r_{t_{i}}), \quad K_{i+2}^{x}=H(K_{i+1}^{x}, r_{t_{i+1}})$)

• $\pi _{i+2}\longleftarrow \mathsf {Launch}$

• $t_{r}^{i+2}, r_{r}^{i+2}\longleftarrow \mathsf {SendReader}(\pi _{i+2}, Init)$

• $h_{1}^{i+2}, r_{t}^{i+2}\longleftarrow \mathsf {SendTag}( vtag ^{x},t_{r}^{i+2}, r_{r}^{i+2})$

• The queries is ended, receive $\tau ( vtag ^{'})= ID _{x}$

• If either $h_{1}^{i+2}=h_{1_{x}}^{i+2}$ or $h_{1}^{i+2}=h_{1_{x}}^{'^{i+2}}$ Then $x=c$ O.W. $x=\vert 1-c\vert$

• Output whether $\tau ( vtag ^{x})= ID _{x}$

• (The lack of knowledge about $,r_{t}^{i+1}$ causes ambiguity for $\mathcal {A}$ to distinguish between $vtag$ and $vtag ^{x}$.)

• Since $\mathcal {A}$ cannot compute $h_{1_{x}}^{i+2}$ without $K_{x}^{i+2}$, $\mathcal {A}$ is not trivial and

  $$\begin{aligned} \left\{ \mathsf {Adv_{\mathcal {A}}^{UPriv-ImprovedFSA}}(k),\mathsf {Adv_{\mathcal {A}}^{Forward-UPriv-ImprovedFSA}}(k) \right\} =0\ll \epsilon . \end{aligned}$$

$\square$

5 The LPP Protocol

The lightweight cryptography primitives are quite practical for RFID systems. Hummingbird-2 is a new lightweight block cipher specialized for RFID systems [39]. Fan et al. [27] propose a lightweight privacy-preserving (LPP) mutual authentication protocol based on the internal state, initial vector, and secret key of the Hummingbird-2. The LPP protocol is detailed in Fig. 3. $INIT _{K}( IV )$ is the initialization function of Hummingbird-2 with secret key $K$ and 64-bits initial vector $IV$. $RS _{i} (i=1,\ldots ,8)$ is the $i$th 16-bit internal state register of Hummingbird-2.

Fig. 3

The LPP protocol [27]

Although the authors claim that LPP is privacy preserve, the Theorems 8 and 9 clarify that LPP not only supports $\mathsf {Wide-Weak}$ privacy level in Vaudenay’s model, also it is forward traceable.

Theorem 8

The LPP protocol does not even support $\mathsf {Narrow-Forward}$ privacy.

Proof

The narrow-forward adversary eavesdrops one session to obtain $r_{1}, r_{2},r_{3}, r_{4}, CT _{1}, CT _{2}, CT _{5}^{'},$ and $CT _{6}^{'}$. The attacker transmits $r_{5}$ and $r_{6}$ instead of $CT _{5}^{'}$ and $CT _{6}^{'}$ to $vtag$ in third flow. In analysis phase, $\mathcal {A}$ queries $\mathsf {Corrupt}$ oracle as the last one and receives $K_{ ID _{x}}, RS _{1} \boxplus RS _{3}$, and $\mathsf {DB}$. Obviously, $CT _{5}^{x}$ and $CT _{6}^{x}$ are computable via $CT _{3}^{x}, CT _{4}^{x}$ and internal states. Since $\mathcal {R}$ and $\mathcal {T}$ are synchronize, $CT _{i}^{x}= CT _{i}^{'} \, (i\in \lbrace 5,6\rbrace )$ with overwhelming probability and finally $\mathcal {T}_{x}$=$\mathcal {T}_{b}$.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}()$

• $\pi \longleftarrow \mathsf {Launch}$

• $r_{1}\longleftarrow \mathsf {SendReader}(\pi , Init)$

• $r_{2}, CT _{1}, CT _{2}\longleftarrow \mathsf {SendTag}( vtag ,r_{1})$

• $r_{3},r_{4},CT^{'}_{5},CT^{'}_{6}\longleftarrow \mathsf {SendReader}(\pi , r_{2}, CT _{1}, CT _{2})$

• $\mathcal {A}$ Replaces $CT^{'}_{5}$ and $CT^{'}_{6}$ with two random numbers $r_{5}$ and $r_{6}$

• $null \longleftarrow \mathsf {SendTag}( vtag ,r_{3},r_{4},r_{5},r_{6})$

• $\mathsf {Free}( vtag )$

• $vtag ^{'} \longleftarrow \mathsf {DrawTag}()$

• $K_{ ID _{x}}, RS _{1} \boxplus RS _{3}\longleftarrow \mathsf {Corrupt}( vtag ^{'})$

• The queries is ended, receive $\tau ( vtag ^{'})= ID _{b}$

• $CT _{3}^{x}=E_{K_{x}}(r_{3})$ and $CT _{4}^{x}=E_{K_{x}}(r_{4})$

• $CT _{5}^{x}=E_{K_{x}}( RS _{1} \boxplus RS _{3})$ and $CT _{6}^{x}=E_{K_{x}}( RS _{1} \boxplus RS _{3})$

• If $CT _{5}^{x}= CT _{5}^{'}$ and $CT _{6}^{x}= CT _{6}^{'}$ then $x=b$ O.W. $x=\vert 1-b \vert$

• Output $\tau ( vtag ^{x})= ID _{x}$ $\square$

Theorem 9

The LPP protocol provides forward traceability.

Proof

The $\mathsf {Narrow-Strong}\,\mathcal {A}$ executes session $i$. The secrets are corrupted and two random numbers $r_{3}^{i^{*}}$ and $r_{4}^{i^{*}}$ are applied to compute $CT _{5}^{i^{*}}$ and $CT _{6}^{i^{*}}$. The $vtag$ confirms the third flow and computes $K_{ ID _{c}}^{i+1}$ via Key-Updating section. Nevertheless, $\mathcal {R}$ is not able to confirm $vtag$ as legitimate tag. In session $i+2, \mathcal {A}$ obtains a transcript of the executed protocol between $vtag ^{x}$ and $\mathcal {R}$. If $\tilde{ CT }_{1,2}^{i+2}= CT _{1,2}^{i+2}, \mathcal {T}_{x}==\mathcal {T}_{c}$ with overwhelming probability, and vice versa.

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}( ID _{c}), c \in \lbrace 0,1 \rbrace$

• $\pi ^{i}\longleftarrow \mathsf {Launch}$

• $r_{1}^{i}\longleftarrow \mathsf {SendReader}(\pi ^{i}, Init)$

• $r_{2}^{i}, CT _{1}^{i}, CT _{2}^{i}\longleftarrow \mathsf {SendTag}( vtag ,r_{1}^{i})$

• $K_{ ID _{c}}^{i}, RS _{1} \boxplus RS _{3} \longleftarrow \mathsf {Corrupt}()$ at $i$th session $\in [i-1 \, \quad i+1]$

• $\mathcal {A}$ randomly chooses $r_{3}^{i^{*}},r_{4}^{i^{*}}$ and computes

• $CT _{3}^{i^{*}}=E_{K_{ ID _{c}}^{i}}(r_{3}^{i^{*}})$ and $CT _{4}^{i^{*}}=E_{K_{ ID _{c}}^{i}}(r_{4}^{i^{*}})$

• $CT _{5}^{i^{*}}=E_{K_{ ID _{c}}^{i}}( RS _{1} \boxplus RS _{3})$ and $CT _{6}^{i^{*}}=E_{K_{ ID _{c}}^{i}}( RS _{1} \boxplus RS _{3})$

• $null \longleftarrow \mathsf {SendTag}( vtag ,r_{3}^{i^{*}},r_{4}^{i^{*}}, CT _{5}^{i^{*}}, CT _{6}^{i^{*}})$

• $K_{ ID _{c}}^{i+1}= Key - Updating - ALG .(K_{ ID _{c}}^{i})$

• $\mathsf {Free}( vtag )$

• $vtag ^{x} \longleftarrow \mathsf {DrawTag}( ID _{x})$ randomly between the two tags $\lbrace 0,1 \rbrace$

• $\mathcal {A}$ chooses another time interval after $i+1$th session (generally $I=[i+2]$)

• $\pi ^{i+2}\longleftarrow \mathsf {Launch}$

• $r_{1}^{i+2}\longleftarrow \mathsf {SendReader}(\pi ^{i+2}, Init)$

• $r_{2}^{i+2}, CT _{1}^{i+2}, CT _{2}^{i+2}\longleftarrow \mathsf {SendTag}( vtag ^{x},r_{1}^{i+2})$

• $\tilde{ CT }_{1}^{i+2}=E_{K_{ ID _{x}}^{i+2}}( RS _{1} \boxplus RS _{3}) \quad$ and $\quad \tilde{ CT }_{2}^{i+2}=E_{K_{ ID _{x}}^{i+2}}( RS _{1} \boxplus RS _{3})$

• If $\tilde{ CT }_{1}^{i+2}= CT _{1}^{i+2} \quad$ and $\quad \tilde{ CT }_{2}^{i+2}= CT _{2}^{i+2}$ then $x=c$ O.W. $x=\vert 1-c \vert$

• Output $\tau ( vtag ^{x})= ID _{c}$

5.1 The Improved LPP

The most important drawback in LPP is the conditions under which $r_{2}, r_{3}$ and $r_{4}$ are transmitted. As an alleviation, both $\mathcal {R}$ and $\mathcal {T}$ should save $K_{ old }^{i}=K^{i-1}$. As long as $\mathcal {T}$ sends $E_{K_{ old }}^{i}(r_{2})$ instead of $r_{2}$ in second flow, adversary cannot reveal $r_{2}$ by eavesdropping. Also since $\mathcal {R}$ knows $K_{ old }^{i}$, every active attack in session $i$ is detectable in the next session. However, $\mathcal {T}$ requires more memory compared with LPP. Indeed, if $\mathcal {A}$ modifies $r_{3}^{i},r_{4}^{i}$ for beginning forward traceability, $\mathcal {R}$ can discover the malicious attack in session $i+1$ via $K_{ old }^{i}$ and synchronize the common key with $\mathcal {T}$.

Proof

• $\mathsf {CreateTag}( ID _{0}),\mathsf {CreateTag}( ID _{1})$

• $vtag \longleftarrow \mathsf {DrawTag}( ID _{c}), c \in \lbrace 0,1 \rbrace$

• $\pi ^{i}\longleftarrow \mathsf {Launch}$

• $r_{1}^{i}\longleftarrow \mathsf {SendReader}(\pi ^{i}, Init)$

• $E_{K_{ old }}^{i}(r_{2}^{i}), CT _{1}^{i}, CT _{2}^{i}\longleftarrow \mathsf {SendTag}( vtag ,r_{1}^{i}) // K_{ old }=K_{i-1}$

• $K_{ ID _{c}}^{i}, RS _{1} \boxplus RS _{3} \longleftarrow \mathsf {Corrupt}()$ at $i$th session $\in [i-1 \, \quad i+1]$

• $\mathcal {A}$ randomly chooses $r_{3}^{i^{*}},r_{4}^{i^{*}}$ and computes

• $CT _{3}^{i^{*}}=E_{K_{ ID _{c}}^{i}}(r_{3}^{i^{*}})$    and   $CT _{4}^{i^{*}}=E_{K_{ ID _{c}}^{i}}(r_{4}^{i^{*}})$

• $CT _{5}^{i^{*}}=E_{K_{ ID _{c}}^{i}}( RS _{1} \boxplus RS _{3})$    and    $CT _{6}^{i^{*}}=E_{K_{ ID _{c}}^{i}}( RS _{1} \boxplus RS _{3})$

• $null \longleftarrow \mathsf {SendTag}( vtag ,r_{3}^{i^{*}},r_{4}^{i^{*}}, CT _{5}^{i^{*}}, CT _{6}^{i^{*}})$

• $K_{ ID _{c}}^{i+1}= Key - Updating - ALG .(K_{ ID _{c}}^{i})$

• $\mathsf {Free}( vtag )$

• $vtag ^{x} \longleftarrow \mathsf {DrawTag}( ID _{x})$ randomly between the two tags $\lbrace 0,1 \rbrace$

• $\mathcal {A}$ chooses another time interval after $i+1$th session (generally $I=[i+2]$)

• $\pi ^{i+2}\longleftarrow \mathsf {Launch}$

• $r_{1}^{i+2}\longleftarrow \mathsf {SendReader}(\pi ^{i+2}, Init)$

• $E_{K_{ old }}^{i}(r_{2}^{i+2}), CT _{1}^{i+2}, CT _{2}^{i+2}\longleftarrow \mathsf {SendTag}( vtag ^{x},r_{1}^{i+2})$

• $//$ Although $\mathcal {R}$ and $\mathcal {T}$ have been desyncronized in the $i$th session, they

• $//$ alleviate the situation via re-synchronization in the $(i+1)$th session with

• $//$ the aid of $K_{ old }^{i}=K^{i-1}$.

• $\tilde{ CT }_{1}^{i+2}=E_{K_{ ID _{x}}^{i+2}}( RS _{1} \boxplus RS _{3})$    and   $\tilde{ CT }_{2}^{i+2}=E_{K_{ ID _{x}}^{i+2}}( RS _{1} \boxplus RS _{3})$

• Since $\tilde{ CT }_{1}^{i+2} \ne CT _{1}^{i+2} \quad$ and $\quad \tilde{ CT }_{2}^{i+2} \ne CT _{2}^{i+2}, vtag$ is untraceable. $\square$

6 Comparison

To sum up, the computation overhead and privacy drawbacks of improved protocols in Sects. 3.1, 4.1 and 5.1 are compared with NRS, FSA and LPP protocols in Table 3. Since a tag has a quite restricted hardware for saving and computation, we only compare tag operations. According to Table 3, although the LPP only suffers from forward traceability, it has the highest computational complexity. The NRS with the lowest computations but without PRNG undergoes widespread weaknesses. It can be seen from the data in Table 3 that the disadvantages are alleviated with the least overhead in improved protocols. Moreover, we proved that both NRS and FSA provide no privacy ($\mathsf {Nil}$) level and LPP only supports $\mathsf {Wide-Weak}$ privacy level.

Table 3 The comparison of computation overheads and privacy vulnerabilities of related RFID authentication protocols

7 Conclusion

Authentication protocols are the foundation of the secure RFID systems. In this paper, the drawbacks of Vaudenay’s model were highlighted. We also analysed privacy aspects in three novel and recently proposed protocols based on lightweight cryptography including the NRS, FSA, and LPP via Ouafi privacy notions in Vaudenay’s privacy model. Eventually, due to inhibition of mentioned shortcomings, three improved protocols were proposed with the lowest communication and computation extra overheads.