A Secure and Privacy Friendly ECC Based RFID Authentication Protocol for Practical Applications

Abstract

Radio frequency identification (RFID) is a promising and widespread wireless communication technology for entity identification or authentication. By the emerging Internet of Things phenomenon, the use of RFID is densely augmenting in various daily life applications. However, RFID systems suffer from security and privacy issues. Recently, many researchers propose RFID authentication protocols based on elliptic curve cryptography (ECC) to efficiently mitigate the aforementioned concerns. In this work, we extensively examine the state-of-the-art RFID authentication protocols based on ECC in terms of security and performance. Some of these works claim that their protocols provide all general security and privacy properties. We revisit Vaudenay’s formal privacy model and show that they do not provide forward and/or backward privacy under this model contrary to their claim. Then, we propose a secure, privacy-preserving and efficient ECC based RFID authentication protocol. We also present a security and performance analysis of our proposed protocol and compare it to the existing relevant schemes in detail. Furthermore, we implement our proposal in a real RFID system to demonstrate its practicability. To the best of our knowledge, our proposed scheme is the most efficient ECC based RFID authentication protocol realized in a real-world environment that satisfies all common security and privacy features including backward and forward privacy.

1 Introduction

Nowadays, many emerging technologies are widely used with advances in information and communication disciplines. The increasing demand for identification and authentication promotes Radio Frequency Identification (RFID) as a pervasive and promising wireless communication technology. The popularity of RFID has been rising day by day with the expeditious development of the Internet of Things (IoT) paradigm. In fact, the first idea of IoT was originated from a network of objects connected by RFID, and IoT tells us that “anything that can be connected, will be connected”. It is predicted that by 2020, the number of daily life things that will be connected to each other will reach about 50 billion [1]. This means that RFID will continue to have a high impact on our daily activities and behaviors, and penetrate in our everyday lives rapidly by providing easy, efficient, cheap, secure and private connections of “things” which also includes people [2]. Although RFID technology is used in numerous real-world applications such as payment systems, healthcare system, e-passports, e-voting, national e-ID management, smart homes, access control, manufacturing, asset management, supply chain, etc. [3,4,5,6,7], RFID is still regarded to be its infancy today [8].

A basic RFID system includes a back-end server, a reader (verifier) and a tag (prover). An RFID tag is designed for wireless data transmission with a chip and an antenna. The tag uses the chip for processing and storing of information, and an antenna is used for wireless communication, respectively. The back-end server/database stores all data (keys, IDs, etc.) about tags. An RFID reader interrogates tags and relays the gathered information to the server.

RFID tags are classified into passive, semi-passive and active tags. Passive tags which are battery-free, solely use the back-scattered interrogation signal of the reader to energize their chips. Active tags are battery-supported and have their own power source. Semi-passive tags are triggered by the reader (need the reader’s magnetic or electromagnetic field for transmitting data) and use their own power source for internal processing. In many application, battery-free low-cost RFID tags are preferred because of their smaller sizes and prices. However, passive low-cost tags have some difficulties such as computation, energy and size restrictions [9]. Furthermore, several standards are also published for the use of RFID systems in different ranges and operating frequencies [4]. For instance, ISO 15693, ISO 14443 and ISO 18000-3 standards are developed for high frequency (HF) and ISO 18000-6, ISO 18000-7 are intended for ultra high frequency (UHF). In fact, the development and improvement of NFC standards also increase the use of HF RFID tags.

Security and privacy concerns in RFID systems result from exchanging sensitive information (i.e. credit card data, personal healthcare data) of tags with a reader in an insecure wireless channel. An adversary might be able to catch and change the messages transmitted in the air. The adversary can cause security and privacy issues with performing various attacks such as tag impersonating, reader spoofing man-in-the-middle (MiTM), tracking, replay, denial of service (DoS) attacks, etc. Therefore, many authentication schemes have been designed for mitigating security and privacy problems in RFID systems [10]. In the RFID literature, all protocol designers claim that their own schemes are secure and privacy-friendly while providing some other requirements such as mutual authentication and scalability. However, it is shown in the literature that most of them are not resistant to every type of attacks and do not efficiently accomplish a least one of security and privacy properties such as forward privacy, backward privacy, impersonation resistance, desynchronization resistance etc [10,11,12,13,14,15,16]. Also, some RFID privacy models are presented to methodically and formally analyze authentication schemes in terms of security and privacy. Although Vaudenay’s model [17] is still successful and acceptable, in the course of time, several works have been proposed to improve and extend his model [11, 18,19,20].

Public-key (asymmetric) cryptography (PKC) can bring elegant solutions to security and privacy problems stated above. Especially nowadays, elliptic curve cryptography (ECC) is preferred in various RFID authentication schemes in order to reduce the key sizes, memory storage, and computation cost. Many protocol designers think that using ECC in their designs efficiently and achieve security and privacy properties (see Sect. 2). Although some researchers have doubts that PKC might not be affordable for constraint tags, the feasibility of using ECC in the tags is shown in [21,22,23,24,25]. Moreover, both privacy and scalability in RFID systems are more easily accomplished by using PKC rather than symmetric cryptographic blocks [25, 26].

On the other hand, the feasibility of using ECC in practice is important for real life RFID applications. Recent works show the implementations of their protocols in different environments such as Wireless Identification and Sensing Platform (WISP), Field Programmable Gate Array (FPGA) [27, 28]. There are also some RFID tags that are presented for implementations in Java cards, BasicCard, Mifare Card, and NFC cards. Especially HF RFID tags including NFC (Near Field Communications) tags have been densely preferred for IoT security applications [29]. In particular, the BasicCard environment [30] offers good opportunities for RFID systems as a powerful development tool in simulation and implementation.

2 Related Work

This section introduces previous works in ECC based RFID authentication protocols and outlines the contributions of this paper. To solve the various security and privacy problems in RFID systems, countless RFID protocols have been published.

A recent comprehensive survey of related work about these protocols is provided in Avoine’s RFID Security and Privacy Lounge [10]. Among all researchers that used public key cryptography (PKC), nearly all preferred ECC-based protocols because of their ability to provide stronger security with smaller key sizes, as well as lighter and efficient computations.

Wolkerstorfer [31] asserts that ECC implementation in RFID tags was suitable. Tulys and Batina [32] firstly propose an ECC-based RFID identification scheme using the Schnorr identification protocol [33] by referring to the conclusion of Wolkerstorfer’s work. They claim that their scheme is secure against cloning attacks. But, the implementation of this protocol is caused by security and privacy vulnerabilities. In the interactive phase, an adversary can obtain the information to calculate the ID-verifier and she can track the tag. The protocol has also a scalability problem. In the authentication phase, the verifier has to search the many public keys for each tag. Moreover, this protocol does not provide mutual authentication and anonymity [34].

Later, Batina et al. [24] propose a new scheme by applying Okamoto’s identification protocol [35] to improve security and privacy. They also aim to discuss the feasibility of ECC based RFID identification protocols and present the implementation of Okamoto’s protocol as an example. However, Batina et al.’s protocol does not solve the security, privacy and efficiency issues [36]. The adversary still can obtain the ID-verifier and track the tag. In addition, the forward privacy is not provided in Batina et al.’s scheme similar to the situations in [32].

Lee et al. [34] show the weaknesses of Schnorr’s and Okamoto’s identification problems and propose a new RFID authentication protocol named EC-RAC using ECC to mitigate the security and privacy flaws mentioned above. But it is shown that this protocol has security and privacy issues, and is vulnerable to tracking attack, MiTM attack, algebraic attacks, etc. [25, 37,38,39,40]. Similarly, the protocol provides only one-way authentication.

Lee et al. [41] revise the EC-RAC protocol [34] and propose six different RFID authentication protocols by expanding the EC-RAC protocol. They state that their protocols are secure against common attacks, but each protocol provides different security properties. Lee et al. [39] address the existing vulnerabilities of EC-RAC protocols and present a new efficient searching scheme for the the RFID reader so as to query for a specific tag while protecting the tag’s privacy.

Zhang et al. [42] present an ECC-based randomized key RFID authentication protocol to improve EC-RAC and Schnorr protocols to defeat their weaknesses. The proposal focuses on finding a way to solve the tracking attack effectively. However, this scheme is defenseless to active-tracking attack. Furthermore, updating tag information increases the computation complexity of the back-end server and causes scalability problems in this scheme. It also lacks mutual authentication [43]. Lv et al. [40], in 2012, show the weaknesses of EC-RAC protocols and propose three ECC-based RFID protocols which are the revision of EC-RAC protocols to overcome tracking attack. Later, An et al. [44] demonstrate that Lv et al.’s protocols are not secure against MiTM attack.

Liao and Hsiao [45] present an ECC-based RFID authentication scheme to satisfy the essential requirements of RFID systems including mutual authentication, anonymity, forward privacy, confidentiality, and scalability. But, it is shown that this scheme is inadequate in terms of computational cost and memory storage [43, 46,47,48]. Zhao [49] proposes a new protocol and shows that Liao and Hsiao’s protocol suffers from the key compromise attack in which the adversary can obtain the private key stored in the tag. It is shown that Liao and Hsiao’s protocol does not achieve any security and privacy properties in [50]. Chien [43] also proves that Liao and Hsiao’s protocol is vulnerable to active tracking attack. Zhao’s scheme does not provide tag anonymity, location privacy, data integrity, backward and forward privacy [27, 28, 51].

Later, Chou [36], designs a new and efficient RFID mutual authentication protocol based on ECC. Unfortunately, this scheme is defenseless against tag impersonation, cloning, and tracking attacks and it also does not satisfy tag anonymity, forward privacy and mutual authentication [28, 52, 53]. Zhang and Qi [53] point out that Chou’s scheme does not provide tag information, backward and forward privacy. They also propose an enhanced new RFID scheme based on Chou’s protocol to overcome the vulnerabilities of his scheme. But, it is shown that Zhang and Qi’s scheme does not provide location privacy, backward and forward privacy [27, 28]. In the same year, He et al. [47] propose a new ECC RFID scheme that integrated with an ID verifier transfer. However, Jin et al. [54] state that He et al.’s scheme is not resistant to various attacks such as tag impersonation, server spoofing, replay, DoS, etc. On the other hand, in 2015, He and Zeadally [13] present a detailed survey of ECC based RFID authentication protocols up to that date.

Farash et al. [48] demonstrate the security and privacy vulnerabilities of [36, 45, 49, 53]’s schemes. In fact, it is shown that none of them provide forward privacy and provable security. Farash et al. also compare their performance and propose an efficient RFID authentication scheme to improve the security and privacy of previous protocols. However, their protocol does not fulfill tag anonymity and location privacy [27]. Jin et al. [55] present an RFID mutual authentication scheme based on ECC to enhance patient privacy while achieving security requirements and overcoming various existing attacks. But, it is shown that their scheme does not provide data integrity and is vulnerable to key compromise problem [51, 56].

Chien [43] shows the attacks on [42, 45]’s schemes and proposes a new ECC-based RFID mutual authentication to defeat the security weaknesses. In the same year, Benssalah et al. [27] propose a secure RFID authentication scheme (we call BDD17) based on elliptic curve message recovery (ECMR) signature to provide significant security features and better performance compared to famous authentication protocols based on ECC in the RFID literature. They analyze their design using a formal security analysis with a random oracle model and claim that their protocol is provably secure. Besides, they implement ECMR in FPGA and validate its practical feasibility. However, it is shown in this paper that BDD17 scheme does not provide forward and backward privacy.

Ibrahim and Dalkılıç [28] propose an authentication scheme (we call ID17) for RFID tags based on both symmetric and asymmetric cryptographic algorithms such as ECC and advanced encryption standard (AES). They claimed that their protocol design is secure, private and provides mutual authentication only in two steps. Moreover, they implement their protocol in the wireless identification and sensing platform (WISP5) and present the performance results. However, it is shown again in this paper that their proposal does not provide forward and backward privacy, as they claim.

Alexander et al. [51] present a survey of the most promising ECC based RFID authentication protocols proposing a different methodology to evaluate recent RFID schemes. They develop a ranking method to compare several RFID protocols in terms of performance and security properties. However, in their evaluation, all ranking points in each category are equal. In other words, different ranks in different categories are weighted the same value. For instance, if a scheme is vulnerable to an attack (i.e. impersonation attack), it loses only a point and is classified into an appropriate rank order. We do not agree with their evaluation because we think that firstly security and performance of a scheme should be evaluated separately, and secondly ranking the security properties or performance of a scheme is not the proper approach to compare RFID protocols because it is hard to grade a certain security property among the others. Besides, Alexander et al. claim that Dinarvand and Barati’s [56] scheme (we call DB19) provides all security and privacy requirements. But, we show that their scheme grade security does not provide backward privacy.

Liu et al. [57] propose a novel ECC based RFID authentication protocol (we call LZKZ18) establishing a key negotiation mechanism. They claim that their protocol design has higher security and privacy. However, it is shown in this paper that their scheme does not achieve forward and backward privacy.

Most recently, several ECC-based RFID authentication protocols have been proposed [58,59,60,61,62,63,64]. Kumar et al. present a framework called RSEAP for vehicular cloud computing [61]. They claim that their protocol provides security and privacy by using formal and information security analyses. However, Safkhani et al. [62] publish a new authentication scheme named RSEAP2 by showing the weaknesses of [61]. Kumari et al. [65] present a protocol called ESEAP and claim that it is more secure than the predecessors but [66, 67] state that their scheme is insecure. Also, Izza et al. [63] propose an ECC-based RFID authentication protocol to fulfill the security and privacy of healthcare applications by overcoming the security issues of Naeem et al. [60]. They also claim that their scheme provides better security than [56, 58, 59, 68]. However, their design has heavy computation, communication, and storage costs. Lastly, Agrahari and Varma [64] define a new scheme based on the EC Qu-Vanstone concept but they present the performance of their design without implementing it. Moreover, they claim that their protocol satisfies only forward untraceability property but they do not mention backward untraceability.

To sum up, we present the following evaluations as an analysis of the literature review. Firstly, we realize that almost all of ECC-based RFID authentication protocols have not been implemented. Hence, the practical performance of these schemes in a real-world environment is questionable. Secondly, most of them suffer from many security and privacy vulnerabilities. The rest of them are not able to satisfy all common security and privacy requirements. Especially, both forward and backward secrecy properties have been overwhelmingly not mentioned in their security analysis. Finally, while many schemes claim to provide higher security and privacy, their performances are less efficient in terms of computation and communication costs. Motivation by this need, we focus on RFID authentication protocols using ECC mechanisms to lead our contributions to the literature. The contributions of this paper can be summarized as follows:

• We show that ID17 [28], BDD17 [27], DB19 [56] and LZKZ18 [57] do not provide forward and/or backward privacy, contrary to their claim. We reveal the vulnerabilities of these schemes under Vaudenay’s [17] formal privacy model. For this purpose, we first revisit Vaudenay’s model and then, we prove our attacks by utilizing privacy games.

• We propose a new secure and privacy-friendly ECC based authentication protocol by improving ID17. We elaborately analyze our proposed scheme in terms of security and performance and our analysis indicates that our scheme achieves all well-known security and privacy properties.

• We present implementation results of our proposed protocol in a real-world RFID system in order to show the practicability and feasibility of our proposal.

• We present detailed security and performance comparisons between our protocol and the related existing schemes. To the best of our knowledge, in the RFID literature, we claim that only our proposal is the up-to-the-minute implemented and tested protocol that can efficiently satisfy all essential security and privacy requirements for an RFID system

The rest of this paper is organized as follows. In Sect. 3, we give preliminary information about common cryptographic concepts used in this paper. In Sect. 4, we revisit Vaudenay’s privacy model that will be used in our attacks. Then, in Sect. 5, we present the security analysis of recent works [27, 28, 56, 57] under Vaudenay’s model to show privacy vulnerabilities. In Sect. 6, we describe our proposed protocol. In Sect. 7, we show the security analysis of our proposal. In Sect. 8, we compare our proposed protocol with existing schemes in terms of security and performance aspects, and also describe real world implementation. Finally, Sect. 9 concludes the paper.

3 Preliminaries

In this section, we introduce some preliminaries on main cryptographic topics utilized in this paper such as ECC cryptosystems, hash functions, and digital signatures.

3.1 Elliptic Curve Cryptography Cryptosystems

ECC is public-key cryptography based on elliptic curves over Galois or finite fields. More than 30 years ago, the use of EC in cryptography is firstly discussed by Koblitz [69] and Miller [70], independently. Today, more than billions of wireless communication systems prefer ECC based solutions to fulfill the security requirements in different sectors such as financial services, health care, government services, etc., because they need efficient and secure asymmetric cryptosystem for confidentiality, integrity, authentication, privacy, nonrepudiation (i.e. signature), etc. The advantages of ECC for wireless security is briefly overviewed in [71].

3.1.1 Theory of ECC

In this subsection, initially the theory of ECC is summarized, then security and benefits of ECC are discussed. An elliptic curve (E) used for cryptographical purposes can be generally defined over a prime finite field ${\mathbb {F}}_{p}$ (or Galois field) includes a group of points $\left( x,y\right)$ that satisfies $y^{2} \equiv x^{3}+ax+b (mod p)$ equation, where $\left( a,b\right) \in E$, $\triangle = 4a^{3}+27b^{2}$ $\implies \triangle \not \equiv 0 (mod p)$ and p is a large prime number. The EC cyclic group is formally defined as $E({\mathbb {F}}_{p}) = \left\{ \left( x,y\right) :x,y\in E\left( a,b\right) \right\} \cup \left\{ {\mathcal {O}}\right\}$, where ${\mathcal {O}}$ denotes point at infinity and satisfies the following group properties. Let $\forall R,S\in E\left( {\mathbb {F}}_{p}\right)$ and $R=(x_1,y_1)$, $S=(x_2,y_2)$,

• Identity: $R+{\mathcal {O}}={\mathcal {O}}+R$

• Negatives: $R+\left( -R\right) ={\mathcal {O}}$, where $-R=\left( x_1,-y_1\right)$. Also, ${\mathcal {O}}=-{\mathcal {O}}$

• Point addition: $R+S=\left( x_{3},y_{3}\right) \in E\left( {\mathbb {F}}_{p}\right)$

• Point doubling: $P\ne \left( -P\right) \implies P+P=2P=\left( x_{3},y_{3}\right) \in E\left( {\mathbb {F}}_{p}\right)$

Order of an EC group refers to the number of points (elements) in that group and can be easily computed by Schoof’s algorithm. Actually, ECC uses cyclic subgroups formed by EC with having cyclically repeated points. This type of groups has a base point (generator). Note that Schoof’s algorithm cannot be used for finding the order of the subgroup. Let G be a cyclic subgroup of $E\left( {\mathbb {F}}_{p}\right)$ with order k and generator P, then $nP={\mathcal {O}}$. Furthermore, a cofactor of G is $h=N/k$, where N is the order of $E\left( {\mathbb {F}}_{p}\right)$ and $h \in {\mathbb {Z}}$ because of Lagrange’s theorem. In fact, cryptographers want a high order of an EC subgroup so before they find a generator, they first choose a large enough order then try to reach a suitable generator.

Lastly, the EC point multiplication is defined as $Q=aP$, where $Q,P\in E\left( F\right)$ and $a\in Z$. This operation corresponds to adding P by itself a times.

Domain parameters: ECC domain parameters are all the elements defining the EC (E) such as base point, prime order, cofactor of the base point, etc. Both tag and reader must agree on them to securely and efficiently use ECC. Their generation of them is out of the scope of this work. The are several secure standard curves and we prefer one of them, namely the ECC Brainpool [72].

3.1.2 Security and Benefits of ECC

The security of ECC-based schemes depends on the hardness of the EC discrete logarithm problem (ECDLP).

Definition 1

(Elliptic curve discrete logarithm problem (ECDLP)). Given $P,Q\in E\left( F_{q}\right)$ and $Q=kP$ where $k\in \left[ 1,q-1\right]$ and q is the point order. Then, it is hard to compute k by an algorithm in polynomial-time.

Using the EC scheme offers some advantages: smaller key sizes with respect to the other known PKC algorithms (at the same security level, see Table 1 [73]), higher speed, reduced memory storage as well as consumed power and bandwidth efficiency. Thus, these benefits make ECC desirable in many usage areas of asymmetric cryptographic schemes such as key agreement, encryption and digital signatures [71, 74,75,76,77,78].

Table 1 Key size (bits) comparisons for equivalent security levels [73]

3.2 Elliptic Curve Diffie-Hellman (ECDH)

Generally, ECDH (a variant of the DH scheme) is a secure key agreement scheme whereby two or more entities can agree on a secret key by using ECC over an insecure channel. Both entities already have pre-shared public keys of each other. They use their own private keys to recover the shared key, but an adversary cannot calculate the shared key from the public information.

Definition 2

(Computational Elliptic Curve Diffie-Hellman Problem). Given P, R $,S\in E\left( {\mathbb {F}}_{q}\right)$, $S=sP$ and $R=rP$ where $s,r\in \left[ 1,q-1\right]$ and q is the order of the base point P. Then, it is hard to compute srP by an algorithm in polynomial-time.

Evidently, these problems satisfy $DLP\Leftarrow DHP$. For specific groups, DHP is sometimes called Diffie-Hellman assumptions because DHP is assumed as a hard problem. Moreover, public keys in ECDH schemes might be either static or ephemeral (ECDHE).

3.3 Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA is a variant of the Digital Signature Algorithm (DSA) that uses ECC. ECDSA is used for authentication, non-repudiation, and integrity. Therefore, the source of the message is authenticated, the entity that transmitted the message cannot deny it and the integrity of the message is ensured over an insecure channel. In this scheme, basically, the signer signs the message by using its own secret key and the verifier verifies the signature with a public key of the signer by using ECC. The security of ECDSA is based on ECDLP. Moreover, ECDSA is more effective than other known schemes such as RSA and DSA. It is accepted by ANSI, IEEE, and NIST.

3.4 Cryptographic Hash Function

Cryptographic hash functions are used in many cryptographic schemes to provide integrity service as deterministic algorithms [79]. It can be formally defined as below.

Definition 3

(Hash Function). Hash function is a function that takes an arbitrary length of inputs and maps a fixed size outputs. Let H be a hash function $H\left( x\right) =y$, where x is arbitrary sized input string and y is fixed size output string. H should be deterministically computable in polynomial time. H should provide the following properties to be a cryptographic hash function.

• Pre-image resistance: This property means that any polynomial-time algorithm cannot find the input of a hash function for a given output. Finding x is hard for a given y, i.e. $H\left( x\right) =y$.

• Second pre-image resistance: This property means that any polynomial-time algorithm cannot find a new input for a given input and output pair of a hash function. Finding $x^{'}$, where $x^{'}\ne x$ is hard for a given x, y, i.e. $H\left( x\right) =y$.

• Collision resistance: This property means that any polynomial-time algorithm cannot find two different inputs to map the same output for a hash function. Finding $\left( x,x^{'}\right)$ that provides $y = y^{'}$ equality is hard for a hash function H, i.e. $H\left( x\right) =y$ and $H\left( x^{'}\right) =y^{'}$.

If H is resistant against collision attacks, it always provides second pre-image resistance, otherwise, but opposite implication might not be valid. This assumption is theoretically true, however, it is recommended that cryptographic hash functions need to satisfy all three requirements in practical applications. In practice, there are several known cryptographic hash functions with different digest sizes from 128 bits to 512 bits e.g. SHA family MD5, BLAKE, etc. Finally, all secure hash algorithms are published by NIST as a standard (FIPS).

4 Security and Privacy of RFID Schemes

In this section, we briefly introduce Vaudenay’s model (VM) [17]. VM is an acknowledged, a well-defined and mature model that allows methodological security and privacy analysis of RFID schemes.

Basically, a simple RFID system consists of three entities such as a tag ${{\varvec{T}}}$, a reader ${{\varvec{R}}}$ and a back-end system/database ${{\varvec{DB}}}$. A reader ${{\varvec{R}}}$ interrogates a tag ${{\varvec{T}}}$ and identifies/authenticates ${{\varvec{T}}}$ by using its identifier $ID_{{{\varvec{T}}}}$. Also, ${{\varvec{DB}}}$ stores all information (secret keys, parameters, identifiers, etc.) of the valid tags. ${{\varvec{R}}}$ has a secure communication with ${{\varvec{DB}}}$ and accesses ${{\varvec{DB}}}$ during authentication/identification phase of ${{\varvec{T}}}$. ${{\varvec{DB}}}$ might be constituted as a part of the reader. Furthermore, we assume that ${{\varvec{R}}}$ is more powerful than the tag. ${{\varvec{T}}}$ has a less computational capacity, memory storage, and a limited energy source. We also assume that an adversary ${{\varvec{A}}}$ is able to corrupt ${{\varvec{T}}}$ and utilize its internal sensitive data against the whole RFID system but she cannot corrupt ${{\varvec{R}}}$ because it is considered as a tamper-resistant device. ${{\varvec{A}}}$ always tends to attack the RFID system by investigating the vulnerabilities of an RFID protocol.

VM can be summarized in modeling an RFID scheme, adversary and privacy classes. For further detailed information on VM, [17] can be examined.

4.1 RFID Scheme Model

According to VM, an RFID scheme ${{\varvec{Sch}}}$ can be constructed by the procedures of SetupReader, SetupTag, and IdentTag. By using SetupReader algorithm, public and private key pairs of ${{\varvec{R}}}$ and a corresponding empty ${{\varvec{DB}}}$ are generated and a public key is distributed to all entities. SetupTag is a polynomial-time probabilistic algorithm that generates a ${{\varvec{T}}}$ with a secret key and updatable internal memory, assigns a unique identifier ID and inserts ${{\varvec{T}}}$ into ${{\varvec{DB}}}$ when it is valid. On the other hand, IdentTag is a polynomial-time algorithm that runs an interaction protocol between ${{\varvec{R}}}$ and ${{\varvec{T}}}$. Finally, it outputs identifier ID of ${{\varvec{T}}}$ if ${{\varvec{T}}}$ is valid. But if ${{\varvec{T}}}$ is not legitimate, it outputs $\bot$. The result of this protocol execution might reveal some secondary information to an adversary.

4.2 Adversaries

An adversary ${{\varvec{A}}}$ is known as a malicious party who aims to break the security and privacy of an RFID scheme by using its vulnerabilities. Formally, an adversary can be defined as a polynomial-time algorithm takes all public information of an ${{\varvec{Sch}}}$ and is able to run the below oracles. Note that a polynomial-time adversary is just able to run polynomial time algorithms due to the fact that her computational abilities are asymptotically bounded. In general, ${{\varvec{A}}}$ may act as a dishonest reader to communicate with a ${{\varvec{T}}}$ but we assume that ${{\varvec{T}}}$ is unaware of this interaction and is deceived that ${{\varvec{A}}}$ is the legitimated ${{\varvec{R}}}$. Therefore, there are three essential characteristics: (i) querying oracles, (ii) playing games to attack the system and reach her goal and (iii) interacting with the system using the rules of the game.

We consider that in an RFID scheme, there is solely one ${{\varvec{R}}}$ and there might be more than one legitimate or illegitimate tags. We also consider that these tags have only one status free or are drawn for a certain time and this status can be changed by the related oracle. Moreover, we assume that ${{\varvec{R}}}$ cannot be corrupted, whereas ${{\varvec{T}}}$ cannot be tamper-resistant. Hence, the secret key $K_{s}$ is kept secret. We also assume that at the beginning of each game, there are no tags. The adversary plays her game only using the following oracles:

• ${\mathcal {O}}^{CreateTag}\left( ID,l\right)$: Let ID is a unique identifier and $l\in \left\{ 0,1\right\}$, this oracle generates a fresh ${{\varvec{T}}}$ with ID and registers the tag by updating ${{\varvec{DB}}}$, if $l=1$. Else, the newly generated tag is invalid.

• ${\mathcal {O}}^{DrawTag}\left( p_d, n\right)$ $\rightarrow$($\psi _{{{{\varvec{T}}}}_{1}},l_{1},\ldots ,\psi _{{{{\varvec{T}}}}_{n}},l_{n}$): This oracle randomly chooses n free tags from previously generated ones with a given probability distribution $p_d$ by changing their status to drawn and dedicates an ephemeral pseudonym $\psi _i$ (anonymously addressing ${{\varvec{T}}}_{i}$) to the drawn $i^{th}$ tag for each selection. The adversary can interact with drawn tags for only one individual session because the pseudonyms are refreshed for each session. The relations between pseudonyms and IDs ($\psi _{{{{\varvec{T}}}}_{i}}$ $,ID_{i}$) are stored in a hidden table. This oracle also outputs a bit array $\left( l_{1},l_{2},\ldots ,l_{n}\right)$ where $l_{i}$ of the $i^{th}$ tag shows whether it is valid or not. Moreover, the oracle may return $\bot$ if there are no existing tags or the querying tags are already drawn.

• ${\mathcal {O}}^{Free}\left( \psi _{{{\varvec{T}}}}\right)$ : This oracle changes the status of drawn $\psi _{{{\varvec{T}}}}$ tag to free and ${{\varvec{A}}}$ cannot reach ${{\varvec{T}}}$ anymore using the $\psi _{{{{\varvec{T}}}}}$

• ${\mathcal {O}}^{Corrupt}\left( \psi _{{{\varvec{T}}}}\right)$$\rightarrow {\mathfrak {M}}$ : This oracle allows to capture the whole memory ${\mathfrak {M}}$ of ${{\varvec{T}}}$ taking $\psi _{{{{\varvec{T}}}}}$.

• ${\mathcal {O}}^{Launch}\left( \right)$$\rightarrow \pi$ : This oracle runs an IdentTag by utilizing legitimate ${{\varvec{R}}}$ and outputs a session identifier $\pi$ of this protocol instance.

• ${\mathcal {O}}^{SendReader}\left( msg,\pi \right)$$\rightarrow msg'$ : This oracle sends msg messages to ${{\varvec{R}}}$ for $\pi$ protocol session and outputs the responding message $msg'$ by ${{\varvec{R}}}$.

• ${\mathcal {O}}^{SendTag}\left( m,\pi \right)$$\rightarrow m'$ : This oracle sends msg messages to ${{\varvec{T}}}$ for $\pi$ protocol session and outputs the responding message $msg'$ by ${{\varvec{T}}}$.

• ${\mathcal {O}}^{Execute}\left( \psi _{{{\varvec{T}}}}\right)$$\rightarrow \left( \pi ,transcript\right)$: This oracle runs an entire protocol between ${{\varvec{R}}}$ and ${{\varvec{T}}}$ taking $\psi _{{{\varvec{T}}}}$ as an input and outputting a transcript that includes all successive messages of $\pi$.

• ${\mathcal {O}}^{Result}\left( \pi \right)$$\rightarrow z$ : This oracle takes the protocol instance $\pi$ of ${{\varvec{T}}}$ and outputs $z\in \left\{ 0,1\right\}$. If ${{\varvec{T}}}$ is identified by ${{\varvec{R}}}$ in its $\pi$ during the IdentTag protocol $z=1$. Otherwise, ${{\varvec{T}}}$ is invalid and the oracle outputs $z=0$.

4.2.1 Adversary Classes

VM mainly groups adversaries into four classes that restrict their attack capabilities. An adversary ${{\varvec{A}}}$ within each class is only allowed to utilize certain oracles. STRONG ${{\varvec{A}}}$ (meaning ${{\varvec{T}}}$ is a member of STRONG adversary class) can freely use all aforementioned oracles without any limitation. WEAK ${{\varvec{A}}}$ cannot call ${\mathcal {O}}^{Corrupt}$ oracle but she has permission to reach the others. DESTRUCTIVE ${{\varvec{A}}}$ cannot utilize any oracle after querying the ${\mathcal {O}}^{Corrupt}$ oracle. The first query of ${\mathcal {O}}^{Corrupt}$ destroys the related ${{\varvec{T}}}$. Finally, FORWARD ${{\varvec{A}}}$ cannot reach any oracles except ${\mathcal {O}}^{Corrupt}$ after her first calling of the ${\mathcal {O}}^{Corrupt}$ oracle.

4.3 Security of RFID Schemes

We summarize some important security notions for an RFID scheme below.

Definition 4

(Completeness). An RFID scheme provides the Completeness property if the probability that an IdentTag protocol returns with $\bot$ result for each legitimate tags is negligible.

Definition 5

(Soundness). An RFID scheme provides the Soundness property if the probability that ${{\varvec{A}}}$ impersonates a legitimate ${{\varvec{T}}}$ is negligible.

4.4 Privacy of RFID Schemes

Vaudenay states that indistinguishability of a tag is closely related to privacy notion. In general, privacy refers to secretly keeping the relation of the identifier of a tag ID within its protocol messages. Put differently, if an adversary cannot find out any relation between the identifier of a tag ID and its obtained protocol instances, the protocol is private. The adversary performs her attack by playing a security game (an experiment) on an RFID scheme to see whether she finds a target RFID tag correctly in two phases; such as attack and analysis phases. First, the adversary uses the related oracles according to her own adversary class and puts forward a hypothesis. Second, she analyzes all pieces of information gathered and returns 1 if her hypothesis is true and 0 otherwise. An RFID scheme provides privacy if the success probability of this adversary is not negligible.

Definition 6

(Privacy). Let consider that an adversary ${{\varvec{A}}}$ is as a member of the adversary class, where $P\in \left\{ STRONG,DESTRUCTIVE,FORWARD,WEAK\right\}$ and $pr_{S}^{{{\varvec{A}}}}$ is the probability of ${{\varvec{A}}}$ to successfully prove her hypothesis by playing a security game. If $\forall {{\varvec{A}}} \in P$, $pr_{S}^{{{\varvec{A}}}}$ is negligible, then an RFID system is P-private.

Vaudenay also defines an untraceability property related to the notion of privacy. In general, untraceability means indistinguishability of two different tags in an RFID scheme. In the RFID literature, the notion of untraceability is categorized into two types: backward untraceability and forward untraceability [80,81,82]. Sometimes they are also called forward secrecy/privacy and backward secrecy/privacy, respectively. Notably, these terms express the opposite meaning of their word meaning. For instance, backward privacy means keeping the privacy of an RFID scheme, even if the tags in the scheme had been corrupted in the past. Actually, “backward” and “forward” terms are originated from the certain time that an adversary can obtain the internal privileges of an RFID tag (i.e. tampering or having ownership transfer) [81]. She is also able to record both a set of backward and forward protocol interactions so that she can destroy the tag privacy.

Let $prb_{s}^{{{\varvec{A}}}}\left( t,\Phi _{t_{0}}^{T}\right) \rightarrow y$ be a function that outputs the probability of an adversary ${{\varvec{A}}}$ to successfully trace a tag ${{\varvec{T}}}$ at time t knowing $\Phi _{t_{0}}^{T}$, where $\Phi _{t_{0}}^{T}$ denotes the whole internal knowledge (e.g. secret keys and parameters) of ${{\varvec{T}}}$ at time $t_{0}$ (i.e. A can obtain $\Phi _{t_{0}}^{T}$ by corrupting ${{\varvec{T}}}$ at time $t_{0}$) and $0\le y\le 1$.

Definition 7

(Backward Untraceability/Forward Privacy). An RFID scheme satisfies backward untraceability property, if $prb_{s}^{A}\left( t,\Phi _{t_{0}}^{T}\right)$ is negligible, where $t < t_0$.

Definition 8

(Forward Untraceability/Backward Privacy). An RFID scheme satisfies forward untraceability property, if $prb_{s}^{A}\left( t,\Phi _{t_{0}}^{T}\right)$ is negligible, where $t > t_0$.

It has been considered that both backward and forward privacy are the essential security requirements for an RFID authentication scheme. Lim and Kwon [81] introduce forward untraceability property and argue that in general, providing this property for an RFID scheme is harder than accomplishing backward untraceability. They focus on the importance of forward untraceability and state that it is at least as crucial as backward untraceability, for RFID authentication schemes. Moreover, Vaudenay says that only a STRONG adversary can break the forward untraceability of an RFID scheme since she can call other oracles after corrupting the tag. Vaudenay also shows in his paper that the ultimate privacy level for RFID systems can be ensured by using PKC [17].

5 Analysis of Previous Authentication Schemes

In this section, we first briefly introduce four recent and relatively popular RFID protocols, namely ID17 [28], BDD17 [27], DB19 [56] and LZKZ18 [57]. Then, we present that these schemes do not ensure forward and/or backward privacy as they claimed.

5.1 Analysis of ID17 RFID Authentication Scheme

In this subsection, we first briefly describe ID17 [28] and then show our proposed attacks.

5.1.1 The Protocol Description

ID17 scheme (illustrated in Fig. 1) has two phases called initialization and authentication, respectively. In the initialization phase, reader and tag make an agreement on EC. Later on, the reader generates a random number as its private key, $k_{r}^{'}$ and calculates its public key $k_{R}^{'}=k_{r}^{'}P$, where P is base point of EC. Meanwhile, the tag executes a similar process so it possesses the public $k_{t}^{'}$ and private $k_{T}^{'}$ keys. At the end of the phase, both reader and tag share their public keys with each other.

In the authentication phase, the reader first randomly generates an ephemeral private key $k_{r}$ and calculates its own ephemeral public key, where $k_R = k_rP$. Then, the reader signs $k_R$ with its private key $k_r^{'}$ using ECDSA. The signature of $k_R$ is (x, y), where $(x,y) = ECDSA_{k_r^{'}}(k_R)$. After signing, the reader sends $k_R$ and its signature (x, y) to the tag.

Fig. 1

ID17 RFID authentication scheme proposed in [28]

When the tag receives the messages of the reader $(k_R, x, y)$, the tag checks that (x, y) are integers in the range $\left[ 1,n-1\right]$. If not, the tag terminates the session. Else, it continues the verification process and verifies $k_R$ using the public key of the reader $k_R^{'}$. If the verification is succeeded, the tag authenticates the reader. Otherwise, it rejects the session. In case of authentication, the tag also randomly picks $k_t$ as an ephemeral private key and computes its own ephemeral public key, $k_{TT} = k_tP$. Then, the tag signs $k_{TT}$ and gets the signature pair (w, v) using ECDSA, where $\left[ w, v\right] =ECDSA_{k_t^{'}}\left( k_{TT}\right)$. After signing, the tag calculates $K_{TR} = k_tk_R$ as an ephemeral shared secret key. Later on, the tag encrypts its ID with $K_{TR}$ and obtains message C, where $C=AES_{K_{TR}}\left( ID\right)$. The tag sends $k_{TT}, w, v, C$ to the reader.

Upon receiving the tag’s response, the reader also checks that w, v are integers in the range $\left[ 1,n-1\right]$. If not, the reader drops the session. Else, the reader continues the verification process and verifies $k_{TT}$. If the verification is succeeded, the reader also computes the ephemeral shared secret key, where $K_{TR} = k_rk_{TT}$. The reader decrypts C using $K_{TR}$ and obtains the ID of the tag. If the reader finds that the ID belongs to the tag registered in the database, the tag is authenticated, too. This scheme is shown in Fig. 1.

5.1.2 Proposed Attacks on the Protocol

The authors claim that their protocol (ID17) provides forward and backward security but we prove that when an adversary corrupts a tag, she can distinguish the tag among the others using its past and future transactions [28]. The authors, in their analysis, state that an adversary cannot perform these attacks because all the transmitted messages are updated for each protocol session. We show that their design does not fulfill randomization in each session to prevent the untraceability since the adversary can verify every signature of the tag if she obtains the private key of the tag once. Therefore, the adversary can violate the backward and forward privacy. Formally, the adversary plays the following games to show how to break the forward and backward privacy properties.

Theorem 1

ID17 scheme does not provide backward privacy.

Proof

: Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(ID_{0},1)$ and ${\mathcal {O}}^{CreateTag}(ID_{1},1)$ to create two valid tags $T_{0}$ and $T_{1}$, respectively.

• 2. A randomly picks one tag $T_{i}$ by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseu-donym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$,she calls ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ and obtains the internal values of the tag with pseudonym ${\psi _{\textit{T}_{i}}}$. These are $a,b,q,P,n,h,k_{TT_{i}}^{'},k_{t_{i}^{'}},ID_{i}$, $k_{R_{i}^{'}}$.

• 4. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 5. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$. During $I_{1}$, A calls${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and receives two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 6. A arbitrarily selects one of the drawn tags $\left( {\mathrm{e.g.}}\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle. She gets $k_{R_{1}}^{I_{1}},x_{1}^{I_{1}},y_{1}^{I_{1}},k_{TT_{1}}^{I_{1}},$ $w_{1}^{I_{1}},v_{1}^{I_{1}},C_{1}^{I_{1}}$ as a protocol transcript.

• 7. A frees the tags by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{0}}\right)$ and ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{1}}\right)$ oracle.

• 8. Then, A tries to verify the signature $\left( w_{1}^{I_{1}},v_{1}^{I_{1}}\right)$ of the ephemeral public key $k_{TT_{1}}^{I_{1}}$ of the tag with the pseudonym $\psi _{\textit{T}_{1}}$ by using the corrupted static key $k_{TT_{i}}^{'}$ of the tag.

• 9. If the signature is valid, she claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, she claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

Obviously, the success probability of this adversary is 1 and she wins the game. This means that A can distinguish the future transactions of the tag. Therefore, this scheme does not provide backward privacy. $\square$

Theorem 2

ID17 scheme does not provide forward privacy.

Proof

Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(ID_{0},1)$ and ${\mathcal {O}}^{CreateTag}(ID_{1},1)$ to create two valid tags $T_{0}$ and $T_{1}$, respectively.

• 2. A randomly picks two tags by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and gets two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$, she arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle. Then, A gets $k_{R_{1}}^{I_{0}},z_{1}^{I_{0}},$ $s_{1}^{I_{0}},k_{TT_{1}}^{I_{0}},g_{1}^{I_{0}}$ $,h_{1}^{I_{0}},C_{1}^{I_{0}}$ as a protocol transcript for $\psi _{\textit{T}_{1}}$.

• 4. A frees the tags by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{0}}\right)$ and ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{1}}\right)$ oracle.

• 5. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$. During $I_{1}$, A randomly chooses a tag $T_{i}$ by calling${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseudonym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 6. A calls ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle and gets $a,b,q,P,n,h,k_{TT_{i}}^{'},k_{t_{i}^{'}},ID_{i}$ and $k_{R_{i}^{'}}$

• 7. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 8. Then, A tries to verify the signature $\left( w_{1}^{I_{0}},v_{1}^{I_{0}}\right)$ of the ephemeral public key $k_{TT_{1}}^{I_{0}}$ of the tag with the pseudonym $\psi _{\textit{T}_{1}}$by using the corrupted static key $k_{TT_{i}}^{'}$of the tag.

• 9. If the signature is valid, she claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, she claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

The success probability of this adversary is 1 and she wins the game. This means that A has stored some past transcripts. Then, when she obtains the internal values of the tag, thereby she can verify the signature of the ephemeral public key and identify the tag using a previous transcript. Therefore, this scheme does not provide forward privacy. $\square$

5.2 Analysis of BDD17 RFID Authentication Scheme

Tn this subsection, we first briefly describe the BDD17 [27] scheme and then show our proposed attacks.

5.2.1 The Protocol Description

BDD17 scheme shown in Fig. 2 has three phases: setup phase, authentication phase, and update phase. In the setup phase, a trusted issuer generates the system parameters $<Z_{BS_{j}},ID_{T_{i}},x_{T_{i}},SID_{j},P_{s},m>$, $<Z_{BS_{j}},x_{R_{i}},SID_{j},P_{s},V_{k},W_{k}>$ and $<Z_{T_{i}},Z_{R_{i}^{'}}$ $,ID_{T_{i}},RID_{i^{'}},SID_{j},x_{BS_{j}},x_{R_{i^{'}}},P_{s},m,IDs_{T_{i}}^{old},IDs_{T_{i}}^{new}>$ to be stored by all involved entities (tags, readers and the back-end server, respectively).

Fig. 2

BDD17 RFID authentication scheme proposed in [27]

In the mutual authentication and an updating phase, reader ($R_{i^{'}}$) controls the user’s password and checks whether $V_{k}^{'}=V_{k}$. If it is held, then $R_{i^{'}}$ generates a random number $r_{R}$ and broadcast the request ${(r_{R},auth)}$ to tag $T_{i}$. When the tag receives the request, it signs $r_{R}$ with a pre-shared message m and a random scalar k using elliptic curve message recovering signature algorithm (ECMR). Then, the tag responds with an anonymous identity $ID_{s_{T_{i}}}$ and an ECMR signature (r, s). Upon receiving this response, the reader gets the current timestamp $T_{r_{1}}$ and computes the message $V=h\left( x_{R_{i^{'}}}\Vert r_{R}\Vert T_{r_{1}}\right)$. Then, the reader sends $r,s,r_{R},V,T_{r_{1}},ID_{s_{T_{i}}}$ to $BS_{j}$. $BS_{j}$ firstly checks the validity of the timestamp and authenticates the reader checking the value V. $BS_{j}$ finds the related tag’s parameter using $ID_{s_{T_{i}}}$ in O(1) time. Then, $BS_{j}$ recovers message $m^{'}$ and verifies its validity by calculating $\gamma =h\left( r\Vert r_{R}\right) \left( Z_{T_{i}}+\left( \left( Z_{T_{i}}\right) _{x}+ID_{T_{i}}\right) P_{s}\right)$ and $\left( r_{R}\oplus m^{'}\right) =r-\left( \left( sG+\gamma \right) x_{BS_{j}}\right) _{x}mod\left( n\right)$.

If the signature is not correct, it rejects $T_{i}$. Otherwise, $BS_{j}$ server gets the current timestamp $T_{s_{2}}$ and performs the following calculations: $\beta =Z_{R_{i}^{'}}+\left( \left( Z_{R_{i}^{'}}\right) _{x}+RID_{i^{'}}\right) P_{s}$, $r_{i}^{'}=Data_{i}$ $+h\left( r_{i-1}^{'}\oplus \left( l\left( \beta \right) \right) _{x}\right)$ $mod\left( n\right)$,   $R=h\left( r_{1}^{'}\Vert r_{2}^{'}\Vert \cdots \Vert r_{n}^{'}\Vert T_{s_{2}}\right)$, $s^{'}=l-Rx_{BS_{j}}mod\left( n\right)$ and $C=h\left( s\Vert SID_{j}\Vert m\Vert r_{R}\right)$.

After $BS_{j}$ sending the message $({C,R,r_{1}^{'},r_{2}^{'},\ldots ,r_{n}^{'},T_{s_{2}}})$ to the reader, it updates $IDs_{T_{i}}^{new}\leftarrow h\left( IDs_{T_{i}}\Vert m\Vert r_{R}\Vert x_{T_{i}}\right)$. When $R_{i^{'}}$ receives the response of the server, it firstly verifies the validity of the timestamp, $\mid T_{r_{2}}-T_{r_{1}}\mid <\triangle T$. It also verifies the validity and integrity of the transmitted message by calculating: $\varphi =\left( Z_{BS_{j}}\right) _{x}+SID_{j}$, $\xi =R^{'}\left( Z_{BS_{j}}+\left( \varphi \right) P_{s}\right)$, $\chi =r_{i}^{'}\oplus \left( \left( s^{'}G+\xi \right) x_{R_{i^{'}}}\right) _{x}$ and $Data_{i}=r_{i}^{'}-h\left( \chi \right) mod\left( n\right)$. If the verifications are succeeded, then the reader $R_{i^{'}}$ relays the message C to the tag $T_{i}$ for mutual authentication. When the tag receives C, it checks $C=h\left( s\Vert SID_{j}\Vert m\Vert r_{R}\right)$. If succeeded, $T_{i}$ authenticates $BS_{j}$; else, it rejects. Finally, $T_{i}$ updates its pseudonym $IDs_{T_{i}}^{new}\leftarrow h\left( IDs_{T_{i}}\Vert m\Vert r_{R}\Vert x_{T_{i}}\right)$ and terminates the session.

5.2.2 Proposed Attacks on the Protocol

The authors claim that their protocol provides the forward security but we prove that when an adversary corrupts a tag, she can distinguish backward and forward transactions of the tag and destroy its privacy [27]. The authors, in their analysis, state that even if an attacker discovers the tag secret parameters, she cannot track the tag’s past positions because she does not reach the timestamps and random values. However, we show that their scheme does not provide backward and forward privacy since an adversary can check the updates of the anonymous identifier $IDs_{T_{i}}$ and break the tag’s privacy. Formally, the adversary can perform the following attack.

Theorem 3

BDD17 protocol does not provide backward privacy.

Proof

Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(ID_{T_{0}}^{0},1)$ and ${\mathcal {O}}^{CreateTag}(ID_{T_{1}}^{0},1)$ to create two valid tags $T_{0}$ and $T_{1}$ with initial identifiers (the tags update their own identifier after authenticating the reader.), respectively.

• 2. A randomly picks one tag $T_{i}$ by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseu-donym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$, she calls a ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle and gets $<Z_{BS_{j}}^{I_{0}},ID_{\psi _{\textit{T}_{i}}}^{I_{0}},x_{\psi _{\textit{T}_{i}}}^{I_{0}},SID_{j}^{I_{0}},P_{s}^{I_{0}},m^{I_{0}}>$.

• 4. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 5. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$ . During $I_{1}$, A calls${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and receives two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 6. A arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle. She gets $r_{R}^{I_{1}^{1}},auth^{I_{1}^{1}},$ $r^{I_{1}^{1}},s^{I_{1}^{1}},IDs_{\psi _{\textit{T}_{1}}}^{I_{1}^{1}},C^{I_{1}^{1}}$as a protocol transcript.

• 7. A calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle again and gets $r_{R}^{I_{1}^{2}},auth^{I_{1}^{2}},$ $r^{I_{1}^{2}},s^{I_{1}^{2}},IDs_{\psi _{\textit{T}_{1}}}^{I_{1}^{2}},C^{I_{1}^{2}}$.

• 8. A frees the tags by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{0}}\right)$ and ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{1}}\right)$ oracle.

• 9. Then, A tries to verify the message $IDs_{\psi _{\textit{T}_{1}}}^{I_{1}^{2}}$ for the tag $\psi _{\textit{T}_{i}}$ by computing $IDs_{\psi _{\textit{T}_{1}}}^{I_{1}^{2}}\overset{?}{=}h\left( IDs_{\psi _{\textit{T}_{1}}}^{I_{1}^{1}}\Vert m^{I_{0}}\Vert r^{I_{1}^{2}}\Vert x_{\psi _{\textit{T}_{i}}}^{I_{0}}\right)$.

• 10. If the verification is succeeded, she claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, she claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

The success probability of this adversary is 1 and she wins the game. This means that A can distinguish the future interactions of $T_{i}$ checking the updates of the anonymous identifier $IDs_{T_{i}}$. Therefore, this scheme does not provide backward privacy. $\square$

Theorem 4

BDD17 protocol does not provide forward privacy.

Proof

Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(ID_{T_{0}}^{0},1)$ and ${\mathcal {O}}^{CreateTag}(ID_{T_{1}}^{0},1)$ to create two valid tags $T_{0}$ and $T_{1}$ with initial identifiers (the tags update their own identifier after authenticating the reader), respectively.

• 2. A randomly picks two tags by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and gets two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$, she arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle. Then, A gets $r_{R}^{I_{0}^{1}},auth^{I_{0}^{1}}, r^{I_{0}^{1}},s^{I_{0}^{1}}$ $,IDs_{\psi _{\textit{T}_{1}}}^{I_{0}^{1}},C^{I_{0}^{1}}$ as a protocol transcript for $\psi _{\textit{T}_{1}}$.

• 4. A calls ${\mathcal {O}}^{Execute}\left( \psi _{\textit{T}_{1}}\right)$ oracle again and gets $r_{R}^{I_{0}^{2}},auth^{I_{0}^{2}},$ $r^{I_{0}^{2}},s^{I_{0}^{2}},IDs_{\psi _{\textit{T}_{1}}}^{I_{0}^{2}},C^{I_{0}^{2}}$

• 5. A frees the tags by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{0}}\right)$ and ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{1}}\right)$ oracle.

• 6. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$. During $I_{1}$, A randomly chooses a tag $T_{i}$ by calling${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseudonym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 7. A calls ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle and gets $<Z_{BS_{j}}^{I_{1}},ID_{\psi _{\textit{T}_{i}}}^{I_{1}},x_{\psi _{\textit{T}_{i}}}^{I_{1}},SID_{j}^{I_{1}},P_{s}^{I_{1}},m^{I_{1}}>$

• 8. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 9. Then, A tries to verify the message $IDs_{\psi _{\textit{T}_{1}}}^{I_{0}^{2}}$ for the tag $\psi _{\textit{T}_{i}}$ by computing $IDs_{\psi _{\textit{T}_{1}}}^{I_{0}^{2}}\overset{?}{=}h\left( IDs_{\psi _{\textit{T}_{1}}}^{I_{0}^{1}}\Vert m^{I_{1}}\Vert r^{I_{0}^{2}}\Vert x_{\psi _{\textit{T}_{i}}}^{I_{1}}\right)$.

• 10. If the verification is succeeded, she claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, she claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

The success probability of this adversary is 1 and she wins the game. This means that A has stored some past transcripts. Then, when she obtains the internal values of the tag, she can identify the tag using previous transcripts by verifying the message $IDs_{T_{i}}^{new}$. Therefore, this scheme does not provide forward privacy as claimed. $\square$

5.3 Analysis of DB19 RFID Authentication Scheme

In this subsection, we first briefly describe the DB19 [56] scheme and then show our proposed attacks.

5.3.1 The Protocol Description

DB19 scheme (illustrated in Fig. 3) consists of 3 phases: setup phase, authentication phase, and updating phase. Before the authentication, public and private key pairs, ECC domain and some system parameters are securely shared to the readers and the tags in the system. The authentication and updating phases are described below.

Fig. 3

DB19 RFID authentication scheme proposed in [56]

Authentication Phase. In this phase, mutual authentication is provided. Firstly, the reader picks a random number $r_1$, computes $R_1$ and sends it to the tag. When the tag receives the challenge of the reader, the tag also picks a random number $r_2$, computes $R_2$ and sends $R_2$, and pseudonym IDS back to the reader. When the reader receives the response of the tag, it searches IDS in the database. If the reader does not find it, the reader terminates the protocol. Otherwise, the reader obtains the corresponding identifier ($x_t$) and key (k) corresponding to $IDS^{new}$ or $IDS^{old}$. Then, the reader computes $TK_{S_1}=r_1kR_2$, $TK_{S_2}=x_SkR_2$ and $Auth_{s}=TK_{s_{1}}\oplus TK_{s_{2}}\oplus x_{t}$. After receiving $Auth_{s}$, the tag computes $TK_{t_{1}}=r_{2}kR_{2}$, $TK_{s_{2}}=x_{s}kR_{2}$ and checks if $x_{t}^{'}\overset{?}{=}Auth_{s}\oplus TK_{t_{1}}\oplus TK_{t_{2}}$. If the obtained identifier $x_{t}^{'}$ does not match, the tag terminates the session. Otherwise, the tag authenticates the reader, computes $Auth_{t}=x_{t}^{'}\oplus 2TK_{t_{1}}\oplus 2TK_{t_{2}}$ and sends $Auth_{t}$ to the reader. When the reader receives the message, it checks if $Auth_{t}\overset{?}{=}x_{t}\oplus 2TK_{s_{1}}\oplus 2TK_{s_{2}}$. If checking succeeds, the reader authenticates the tag. Otherwise, the reader rejects the $Auth_{t}$ and terminates the protocol.

Updating Phase. When the authentication is successfully accomplished, both the reader and the tag refresh their secret keys k and the pseudonyms (IDS). The reader also keeps old and new IDS. The tag performs the following updates: $IDS^{*}=X\left( TK_{t_{1}}\right) \oplus IDS\oplus k$, $k^{*}=X\left( TK_{t_{2}}\right) \oplus 2k$ and $IDS=IDS^{*}, k=k^{*}$.

The reader performs the following updates: If $IDS^{old}$ is received, the reader computes $IDS^{new}=X\left( TK_{S_{1}}\right) \oplus IDS^{old}\oplus k$ and $k^{new}=X\left( TK_{S_{2}}\right) \oplus 2k^{old}$. If $IDS^{new}$ is received, the reader updates $IDS^{old}=IDS^{new}$ and $k^{old}=k^{new}$. The reader, then, computes $IDS^{new}=X\left( TK_{S_{1}}\right) \oplus IDS^{old}\oplus k$ and $k^{new}=X\left( TK_{S_{2}}\right) \oplus 2k^{old}$

5.3.2 Proposed Attacks on the Protocol

Dinarvand and Barati [56] claim that their protocol (BD17) provides forward privacy. However, they do not mention backward privacy in their paper. In this subsection, we show that their scheme does not achieve backward privacy which is one of the well-known privacy requirements. In other words, we prove that when an adversary obtains the secrets of a tag once, she can distinguish the tag with using its future transactions. An adversary can directly reveal the identifier of the tag $x_{t}$ with sending $P_{s}$ to the tag instead of $R_1$ after obtaining the secrets of the tag. Formally, the adversary plays the following game to show how to break the forward untraceability property.

Theorem 5

BD17 scheme does not provide backward privacy.

Proof

Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(x_{t}^{T_{0}},1)$ and ${\mathcal {O}}^{CreateTag}(x_{t}^{T_{1}},1)$to create two valid tags $T_{0}$ and $T_{1}$, respectively, where $x_{t}^{T_{0}}$ denotes the identifier of a tag.

• 2. A randomly picks one tag $T_{i}$ by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseu-donym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$,calls a ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle. She obtains all internal values of the tag with pseudonym ${\psi _{\textit{T}_{i}}}$. These are $x_{t}^{T_{i}},IDS_{i},k_{i},P$ and $P_{s}$.

• 4. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 5. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$ . During $I_{1}$, A calls${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and receives two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 6. A arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Launch}\left( \right)$ oracle. She starts a new protocol execution with $\pi _{1}$

• 7. A calls ${\mathcal {O}}^{SendTag}\left( P_{s},\pi _{1}\right)$ oracle and she sends $P_{s}$ message instead of $R_{1}$ message. The tag $\psi _{\textit{T}_{1}}$ respones with $R_{2}^{I_{1}},IDS^{I_{1}}$but A does not need these messages.

• 8. A sends $x_{t}^{T_{i}}$ to the tag instead of $Auth_{s}^{I_{1}}$ message (in step-3) by calling ${\mathcal {O}}^{SendTag}(x_{t}^{T_{i}}$ $, \pi _{1})$ oracle and waits for the response of the tag.

• 9. If the tag $\psi _{\textit{T}_{1}}$ responds with $Auth_{t}^{I_{1}}$, A directly gets $x_{t}^{T_{1}}$ and claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$, since the response means that the tag authenticates A. In fact, $Auth_{t}^{I_{1}}=x_{t}^{T_{1}}$ because of $Auth_{t}^{I_{1}}=x_{t}^{T_{1}}\oplus 2\left( r_{2}k_{1}P_{s}\right) \oplus 2\left( r_{2}k_{1}P_{s}\right)$.

• 10. If the tag $\psi _{\textit{T}_{1}}$ does not respond, this means that the tag does not authenticate and terminates the session. Therefore, A claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

Obviously, the success probability of this adversary is 1 and she wins the game. Therefore, BD17’s scheme does not provide forward untraceability property. $\square$

5.4 Analysis of LZKZ18 RFID Authentication Scheme

In this subsection, we first describe LZKZ18 [57] scheme and then show our proposed attacks.

5.4.1 The Protocol Description

LZKZ18 scheme (illustrated in Fig. 4) includes two processes: a setup process and an implementation process. In the setup process which is also divided into initialization and bidirectional authentication phases, the server and the reader securely share and store the needed keys. The reader, server and tag agree on the ECC domain parameters, too.

Fig. 4

LZKZ18 RFID authentication scheme proposed in [57]

In the implementation process, at first, the reader picks a random $x_R$, computes $R_1$ and initiates a new protocol session sending the query request Query and $R_1$. When the tag receives a request, the tag picks a random $x_T$ and computes $T_2$ and $T_3$. The tag sends $T_1,T_2$ and $T_3$ to the reader. When the reader receives the response of the tag, the reader computes $R_2$ and checks if $R_2\overset{?}{=}T_2$. If the checking is false, the authentication fails and the session drops. Otherwise, the reader considers that the tag is legitimate and computes $R_3$ and $R_4$. Then, the reader sends $R_1, R_2, R_3, T_1, T_3$ and $t_R$ to the server. After receiving the message, the server firstly checks the timestamp $t_R$. If the $t_R$ exceed the time limit, the server finishes the authentication. Otherwise, the server picks a random number $x_S$ and computes $S_1$ and $S_2$. If $S_{2}\ne R_{3}$, then the authentication fails. Otherwise, the server authenticates the reader and calculates $S_3$. If $S_{3}\ne R_{D}$, then the authentication fails again. Otherwise, the server obtains the reader’s authorization identifier and computes $S_4$ and checks if $S_4\overset{?}{=}T_D$. If $S_{4}\ne T_{D}$, then the authentication fails. Otherwise, the server obtains the tag’s authorization identifier and calculates $S_5$ and $S_6$. Later on, the server sends $S_1, S_5$ and $S_6$ to the reader. When the reader gets this, it computes $R_5$ and checks if $R_5\overset{?}{=}S_5$. If $R_5=S_5$, the reader authenticates the server. Otherwise, the authentication fails. After the successful authentication, the reader sends $S_1, S_6$ to the tag. The tag then computes $T_4$. Finally, the tag checks if $T_4\overset{?}{=}S_6$. If $T_{4}\ne S_{6}$, the tag rejects the authentication and terminates the session. Otherwise, the tag authenticates the reader and the back-end server, too.

5.4.2 Proposed Attacks on the Protocol

The authors claim that LZKZ18 protocol provides forward security without presenting any analysis [57]. In this paper, we show that their scheme does not fulfill both backward and forward privacy because an adversary can destroy the privacy of a tag by sending $P_{s}$ instead of $R_1$ and checking if $T_{2}\overset{?}{=}H\left( T_{3}-T_{D}-cP_{S}\right)$.

Theorem 6

LZKZ18 scheme does not provide backward privacy.

Proof

Let A is a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(T_{D_{0}},1)$ and ${\mathcal {O}}^{CreateTag}(T_{D_{1}},1)$ to create two valid tags $T_{0}$ and $T_{1}$, respectively.

• 2. A randomly picks one tag $T_{i}$ by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseu-donym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$,calls a ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle. She obtains all internal values of the tag with pseudonym ${\psi _{\textit{T}_{i}}}$. These are $T_{D_{i}},k_{AC},c_{i},P_{T_{i}}$ and $P_{S}$.

• 4. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 5. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$. During $I_{1}$, A calls${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and receives two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 6. A arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Launch}\left( \right)$ oracle. She starts a new protocol execution with $\pi _{1}$

• 7. A calls ${\mathcal {O}}^{SendTag}\left( P_{S},\pi _{1}\right)$ oracle so she sends $P_{S}$ message instead of $R_{1}$ message. The tag $\psi _{\textit{T}_{1}}$ responses with $T_{1}^{I_{1}},T_{2}^{I_{1}},T_{3}^{I_{1}}$.

• 8. A checks $T_{2}^{I_{1}}\overset{?}{=}H\left( T_{3}^{I_{1}}-T_{D_{i}}-c_{i}P_{S}\right)$. If succeeds, A claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, A claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

Obviously, the success probability of this adversary is 1 and she wins the game. Therefore, LZKZ’s scheme does not ensure backward privacy. $\square$

Theorem 7

LZKZ18 scheme does not provide forward privacy.

Proof

Let A be a STRONG adversary that plays a security game as below.

• 1. A calls ${\mathcal {O}}^{CreateTag}(T_{D_{0}},1)$ and ${\mathcal {O}}^{CreateTag}(T_{D_{1}},1)$ to create two valid tags $T_{0}$ and $T_{1}$, respectively.

• 2. A randomly picks two tags by querying ${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},2\right)$ oracle and gets two pseudonyms $\psi _{\textit{T}_{0}}$ and $\psi _{\textit{T}_{1}}$.

• 3. A chooses a time interval $I_{0}$. During $I_{0}$, she arbitrarily selects one of the drawn tags $\left( e.g.\,\psi _{\textit{T}_{1}}\right)$ and calls ${\mathcal {O}}^{Launch}\left( \right)$ oracle. A starts a new protocol execution with $\pi _{1}$

• 4. A calls ${\mathcal {O}}^{SendTag}\left( P_{S},\pi _{1}\right)$ oracle so she sends $P_{S}$ message instead of $R_{1}$message. The tag $\psi _{\textit{T}_{1}}$ responses with $T_{1}^{I_{0}},T_{2}^{I_{0}},T_{3}^{I_{0}}$.

• 5. Then, A frees the tags by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{0}}\right)$ and ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{1}}\right)$ oracle.

• 6. A chooses another time interval $I_{1}$, where $I_{1}>I_{0}$. During $I_{1}$, A randomly chooses a tag $T_{i}$ by calling${\mathcal {O}}^{DrawTag}\left( \frac{1}{2},1\right)$ oracle and gets a pseudonym $\psi _{\textit{T}_{i}}$, where $i\in _{R}\left\{ 0,1\right\}$.

• 7. A calls ${\mathcal {O}}^{Corrupt}\left( \psi _{\textit{T}_{i}}\right)$ oracle and gets $T_{D_{i}},k_{AC},c_{i},P_{T_{i}}$ and $P_{S}$.

• 8. A frees the tag by calling ${\mathcal {O}}^{Free}\left( \psi _{\textit{T}_{i}}\right)$ oracle.

• 9. Then, A checks if $T_{2}^{I_{0}}\overset{?}{=}H\left( T_{3}^{I_{0}}-T_{D_{i}}-c_{i}P_{S}\right)$. If succeeds, A claims that $i=1$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{1}}\right)$. Otherwise, A claims that $i=0$ $\left( \psi _{\textit{T}_{i}}=\psi _{\textit{T}_{0}}\right)$.

Obviously, the success probability of this adversary is 1 and she wins the game. Therefore, LZKZ’s scheme does not provide forward privacy. $\square$

6 Our Improved Protocol

We propose a new privacy-friendly ECC based RFID authentication protocol depicted in Fig. 5 by enhancing ID17 scheme [28]. Our focus is to overcome the privacy weaknesses of their protocol. We consider that transmitting the ephemeral public key and its signature in an insecure channel causes privacy issues. Therefore, we claim that if an ephemeral public key is broadcasted with an indistinguishable encrypted signature, then an attacker cannot track the past and future interactions of any tag so that both forward and backward untraceability properties are provided.

We consider that both the reader and the back-end server (BS) are trusted entities but a tag might be corrupted, compromised or illegitimate. For the sake of simplicity, we also consider both BS and reader as a single entity and the tag is the second entity of our scheme. Note that this does not affect the generality since most of the applications accept that the communication of tag−reader is not secure but the communication of reader−BS is secure (as shown in Fig. 6). Before describing the protocol, we present the following notations in Table 2 to improve the intelligibility.

Table 2 Notations of our proposed protocol

6.1 Protocol Description

We present a brief description of our scheme below. Figure 5 also elaborately shows the details. Our proposed protocol consists of a setup phase and an authentication phase.

6.1.1 Setup Phase

Reader and tags must agree on ECC domain parameters of the scheme to use elliptic curve cryptosystem. Hence, in the setup, both tags and readers firstly agree on a curve with ECC domain parameters. In our scheme, we prefer ECC brainpoolP160r1, a standard curve, to be used for the domain parameter values [72]. In this phase, all unique identifiers $ID_{i}$ of the tags are stored in BS. An integer $k_{t}^{'}$ is randomly chosen as the private key of the tag, where $1\le k_{t}^{'}\le n-1$ and its public key is computed as $k_{T}^{'}=k_{t}^{'}G$. Then, the key pairs are stored in the tag. $k_{T}^{'}$ is shared with the reader. On the other hand, an integer $k_{r}^{'}$ is randomly chosen as the private key of the reader, where $1\le k_{r}^{'}\le n-1$ and its public key is computed as $k_{R}^{'}=k_{r}^{'}G$. Then, the key pairs are stored in BS, while $k_{R}^{'}$ is shared with all tags.

Fig. 5

Our proposed scheme

6.1.2 Authentication Phase

In this phase, the mutual authentication is accomplished in two rounds with the following steps. Note that Fig. 5 also depicts each step of our protocol execution.

Step-1::

First, the reader randomly generates an ephemeral private key $k_{r}$ and calculates its own ephemeral public key, where $k_R = k_rG$.

Step-2::

The reader signs $k_R$ with its private key $k_r^{'}$ using ECDSA, where $(z,s) = ECDSA_{k_r^{'}}(k_R)$

Step-3::

The reader sends $k_R$ and the signature (z, s) to the tag.

Step-4::

The tag firstly verifies $k_R$ using the public key of the reader $k_R^{'}$.

Step-5::

If the verification is succeeded, the tag will authenticate the reader. Otherwise, it rejects the session. In case of authentication, the tag also randomly picks $k_t$ as an ephemeral private key and computes its own ephemeral public key, $k_{TT} = k_tG$.

Step-6::

The tag signs $k_{TT}$ and gets its signature (g, f) by computing $\left( g, h\right)$ $=ECDSA_{k_t^{'}}\left( k_{TT}\right)$.

Step-7::

The tag calculates $K_{TR} = k_tk_R$ as an ephemeral shared secret key.

Step-8::

The tag encrypts ID and the signature (g, f) together as a plaintext using the ephemeral key $K_{TR}$, where $C=AES_{K_{TR}}\left( ID\Vert g\Vert f\right)$.

Step-9::

The tag transmits only C and $k_{TT}$ messages to the reader.

Step-10::

When the reader receives the message of the tag, the reader computes the ephemeral shared secret key $K_{TR} = k_rk_{TT}$, where $k_{r}k_{TT}=k_{r}(k_{t}G)=k_{r}k_{t}G$.

Step-11::

Then, the reader can meaningfully decrypt message C using $K_{TR}$, obtain ID and signature (g, f) if the shared key is valid. Otherwise, the reader has a garbage message.

Step-12::

The reader verifies the decrypted messages. It checks if g and f are integers in the range $\left[ 1,n-1\right]$. If not, it rejects the session. After that, the reader also verifies the $k_{TT}$ with using the decrypted signature (g, f). If the verification is not succeeded, it rejects the session.

Step-13::

The reader checks if $x_{2}\overset{?}{=}g$ $mod\left( n\right)$ and searches if the ID belongs to a tag registered in the database ($ID = ID_{i}$), the tag is authenticated. Otherwise, the reader rejects the session.

7 Security Analysis of Our Proposed Protocol

In this section, we give the security and privacy analysis of our proposed protocol and prove that our scheme provides all essential security and privacy properties.

Theorem 8

Our protocol provides confidentiality.

Proof

In our protocol, the sensitive information is the identity of tag ID and the private keys of the reader and the tag. The private keys are protected well and are not transmitted. Furthermore, ID is transmitted as ciphertext encrypted by AES. The key of AES is ephemerally derived using elliptic-curve Diffie–Hellman mechanism by both the reader and the tag. Therefore, an adversary A who collects $k_{R}, z, s, k_{TT}$ and C transcripts, cannot obtain any confidential information without breaking AES or ECDHE in polynomial time. $\square$

Theorem 9

Our protocol provides integrity.

Proof

In our protocol, we use the ECDSA signatures that are basically used to provide the integrity of $k_{R}$ and $k_{TT}$ messages. An adversary A cannot change the content of the protocol transcripts because both the reader and the tag verify the transmitted signatures (z, s) and (g, f). A can modify the transmitted message or forge the related signatures if she solves the elliptic curve discrete logarithm problem (ECDLP) but ECDSA is computationally secure and it is a hard problem for polynomial time attackers. Consequently, the protocol guarantees the integrity of transmitted messages. $\square$

Theorem 10

Our protocol provides availability.

Proof

In our protocol, the tag identifier ID and the pre-shared keys are securely stored and protected well. Hence, it is not needed to synchronously refresh these values for our scheme. In fact, there is no update mechanism between the tag and reader. Therefore, the protocol can be executed all the time between the reader and the tag. Hence, our scheme provides availability. $\square$

Theorem 11

Our protocol provides tag anonymity.

Proof

In the authentication phase, the tag responds when it receives challenges from the reader. Hence, anonymity is becoming one of the utmost important and imperative security requirement for privacy. In our protocol, an adversary A collects the only $k_{R}, z, s, k_{TT}$ and C transcripts and cannot reach the tag identifier ID because A is not able to ECDLP in polynomial time and gain $k_{TR}$. A also cannot break C without having $k_{TR}$ because AES-128 is considered computationally secure. In fact, Theorem 8 also shows that A can never obtain any confidential information. Moreover, if $k_{TT}$ and C messages were not randomly generated for each session, the adversary can ruin the anonymity. However, all messages of the tag in our scheme are randomized for each protocol session and A cannot even distinguish any tag’s messages sent in different sessions. Therefore, the protocol achieves tag’s anonymity property and the adversary cannot attain any indicator to point out a tag anymore. $\square$

Theorem 12

Our protocol provides mutual authentication.

Proof

Mutual authentication (two-way authentication) is an important property in which both entities in a protocol link authenticate each other. In the authentication phase of our protocol, the reader sends randomly generated $k_{TR}$ and its signature z, s by using ECDSA. The tag can verify $k_{TR}$ using the pre-shared public key of the reader $k_{R}^{'}$, herewith the reader can be authenticated. Likewise, the reader authenticates the tag after verifying $k_{TT}$. For this authentication, the reader firstly decrypts C, gets the unique tag identifier ID and the ECDSA signature of $k_{TT}$ which is g, f. Secondly, the reader verifies g, f using the pre-shared public key of the tag $k_{T}^{'}$. If the verification is successful, the reader finally searches ID in its database. If the reader finds it (matches $ID=ID_{i}$), the tag is authenticated, too. Therefore, the proposed protocol provides mutual authentication. $\square$

Theorem 13

Our protocol provides scalability.

Proof

The scalability is a crucial property that reduces the computational cost, searching time of a tag in the database and authentication time. In most cases, the searching time linearly increases proportionally proliferating the registered tags in the database with search complexity $O\left( N\right)$, where N is the number of valid tags. In our protocol, the reader decrypts C and gets the $ID_{i}$ (where $1\le i\le N$). Then, the reader searches the matched entry in the database with search complexity $O\left( 1\right)$ because each entry $ID_{i}$ matches only one tag in DB. Therefore, our proposed protocol is scalable.

$\square$

Theorem 14

Our protocol provides forward privacy.

Proof

Forward security is explained in Definition 7. In our proposed protocol, the reader freshly sends $k_{R}$ and its signature z, s for each protocol session. The tag also generates a new fresh $k_{TT}$ and C messages. The ephemeral $K_{TR}$ ensures that C is randomized. Because of randomization of all session messages, if a probabilistic polynomial-time (ppt) adversary A corrupts a tag T, discloses the secrets $ID, k^{'}_{t}$ and collects the past protocol transcripts, A can distinguish the corrupted tag and its transactions with a negligible probability. A never gets any advantage to overcome the previous indistinguishable transactions of our scheme. Therefore, our protocol provides backward untraceability property. $\square$

Theorem 15

Our protocol provides backward privacy.

Proof

As mentioned in the proof of Theorem 14, if the same adversary A collects the future protocol transcripts, A can distinguish the corrupted tag and its transactions with a negligible probability. A never gets any advantage to overcome the future indistinguishable transaction of our scheme. Therefore, our protocol provides forward untraceability property. $\square$

Theorem 16

Our protocol provides location, traceability privacy and withstands the tracking attack.

Proof

In Theorems 14 and 15, we prove that future and backward untraceability property of our protocol. An adversary A cannot destroy the privacy of a tag T, even if A has the secrets of T and the past/future protocol transcripts in related protocols. Hence, A certainly cannot ruin location privacy of T without any confidential information of the tag and track T. In other words, untraceability properties imply this result. Therefore, our protocol provides location, traceability privacy and it is resistant against the tracking attack. $\square$

Theorem 17

Our protocol withstands the tag impersonation and reader spoofing attacks.

Proof

An adversary A can impersonate a tag T only by obtaining ID and $k^{'}_{t}$ but solving ECDLP is computationally infeasible in polynomial time. Hence, A cannot impersonate T. Similarly, A can never produce valid C, z, s messages without having $K_{TR}, ID$ and $k^{'}_{t}$ because of the aforementioned computational infeasibilities. Thus, A cannot spoof the reader. $\square$

Theorem 18

Our protocol withstands the replay attack.

Proof

In a replay attack, an adversary A imitates a tag A or a reader R by reusing the intercepted past protocol messages. In our proposed protocol, A cannot generate and reuse valid $k_{R}, z, s$ messages because they are randomly changed for each session. Similarly, A cannot generate and reuse valid $k_{TT}, C$ messages because they are ephemerally generated random transcripts. This attack can be succeeded, only if A reveals the tag secrets $k^{'}_{t}, ID$ and reader private key $k^{'}_{r}$. Therefore, the proposed protocol is resistant against the replay attack. $\square$

Theorem 19

Our protocol withstands the denial-of-service (DoS) and de-synchroni-zation attack.

Proof

We prove that our proposed protocol provides availability in Theorem 10 which shows that both a tag and a reader always remain synchronized during each protocol execution. An adversary cannot desynchronize both entities and execute DoS attack. Thus, the scheme is resistant against the DoS and de-synchronization attack. $\square$

Theorem 20

Our protocol withstands MiTM attack.

Proof

Our scheme provides mutual authentication property (see Theorem 12 ). Therefore, our design is resistant to MiTM attack. $\square$

Theorem 21

Our protocol withstands the cloning attacks .

Proof

In our proposed protocol, each tag has its own identity $ID_{i}$ and the secret key $t^{'}$. Even if an adversary can obtain some tags’ IDs and their private keys, she cannot reach the other tags’ IDs and their secret keys. Thus, the protocol is resistant to the cloning attack. $\square$

Theorem 22

Our protocol provides unforgeability.

Proof

In our scheme, only the valid tag and the reader can generate a legitimate signature. An adversary can never perform a forgery attack without having the private keys as their security leans to the hardness of ECDLP. Therefore, the proposed protocol provides unforgeability. $\square$

Theorem 23

Our protocol withstands modification attack

Proof

According to Theorem 9, our proposed protocol provides integrity property. Therefore, it is resistant to any modification attack. $\square$

8 Comparison and Implementation

In this section, we compare our proposed scheme with other existing ECC-based RFID authentication works in terms of security and performance.

8.1 Security Comparison

We enumerate the security and privacy comparison of our proposed scheme and related protocols in Table 3. It can be obviously seen that our scheme provides all essential security and privacy requirements of an RFID system and is more secure than the previously proposed protocols [27, 28, 36, 45, 49, 53, 56, 57]. Furthermore, we proved in Sect. 5 that the state-of-the-art protocols [27, 28, 56, 57] cannot provide forward and/or backward privacy . Our scheme not only guarantees the related security and privacy requirements but also provides additional properties such as mutual authentication and efficiency in search of the tags during the identification process.

Table 3 Security and privacy comparison ($\checkmark$:provide, x:do not provide, –:not mentioned )

8.2 Performance Comparison

Although security and privacy properties are indispensable for RFID schemes, the performance of these schemes is vital to effectively use RFID systems in real applications. While our priority is proposing an authentication scheme that solves all essential security and privacy issues existing in RFID systems; we target to design an efficient scheme for practical applications. In this section, we first analyze our protocol and compare it to previous prominent ECC-based RFID authentication protocols [27, 28, 36, 45, 49, 53, 56, 57] in terms of computational and communication costs. A detailed performance comparison (including computation and communication costs) in the literature are summarized in Table 4.

8.2.1 Communication Cost Comparison

Communication cost is crucial because of determining availability delays. Increase in delays usually obstacles the effective usage of the entire system. In terms of communication cost, there are two dominant factors to determine the effects, i.e. the number of protocol rounds and communication overhead. According to our analysis, only our protocol and the inspired ID17 have two rounds. DB19 scheme has four rounds and the other protocols require three rounds to provide authentication. Furthermore, the communication overhead of our protocol from reader-to-tag is 80 bytes (the public key and its signature), and 88 bytes (the public key and 3 blocks of AES encryption) transmitted from tag-to-reader. Hence, the total overhead of our protocol is 168 bytes. As seen in Table 4, ZQ14’s scheme achieves the lowest communication overhead. However, they use SHA-1 algorithm for hashing the messages but SHA-1 is cryptographically insecure [83, 84]. Their communication overhead will be greater if they prefer a secure alternative hash function in their scheme. In fact, two works [13, 28] evaluate that CH14’s and ZQ14’s schemes have 184–186 bytes and 160–165 bytes communication overhead, respectively. Therefore, we deduce that our protocol provides the minimum communication cost considering the aforementioned factors.

Moreover, ECC point compression methods could be applied during sending public keys in the channel so that the communication efficiency might be increased in terms of communication overhead. For instance, our protocol can gain roughly 38 bytes in transmission and the communication overhead will be only 130 bytes in this case. However, this compression causes extra computations on both tag and reader sides. Note that, this point compression load might be delegated to only the reader since it has higher computational capabilities.

Table 4 Performance comparison

8.2.2 Computational Cost Comparison

In this section, we compare the computational cost of our protocol with existing ECC-based RFID authentication protocols [27, 28, 36, 45, 49, 53, 56, 57]. Table 6 summarizes the results in more detail. At first, to make an appropriate comparison, we will consider the primary operations which directly affects and determine the computation efficiency of an authentication protocol such as $T_{ecm}, T_{eca}, T_{inv}, T_{mul}, T_{h}$ and $T_{aes}$. Kobliz et al. [85] and Wu and Chen [86] analyze the time complexity of various operations in terms of $T_{mul}$. Also, these metrics are accepted by [13, 27]. Table 5 depicts their running time comparison of these primary operations.

Table 5 Notations and running time of primary operations in terms of $T_{mul}$ [86]

We calculate the computation cost of our proposed protocol and the related works based on the above analysis in terms of $T_{mul}$. The tag and reader computational cost of our protocol are separately around $4T_{ecm} + 1T_{eca} + 2T_{inv} + 4T_{mul} + 2T_{h} + 2AES = 4817T_{mul}$, so the total cost is roughly $8T_{ecm}+2T_{eca}+4T_{inv}+8T_{mul}+4T_{h}+2AES = 9634T_{mul}$. According to Table 6, it is clearly seen that our scheme performs an acceptable computational cost. The schemes [36, 53] have better computational efficiency, however, they have serious security and privacy issues. In fact, these results show us that EC point multiplication $T_{ecm}$ is a dominant and decisive operation to determine the computational cost of a protocol. Hence, we claim that calculating $T_{ecm}$ is enough for evaluating the computational cost of an ECC based authentication protocol, in general. We presented this interpretation in Table 4 to intelligibly demonstrate our performance comparison.

Table 6 Computational cost comparison

8.2.3 Our Implementation Environment and Results

To explore the practical usage of our proposed design, we implemented our scheme in a real-world RFID system. the overwhelming majority of authors [13, 27, 36, 45, 49, 51, 53, 56], except [28], present computational cost of their protocols by referencing previous simulation results [87, 88] in their performance evaluations. Hence, a real world implementation is valuable.

We implemented our proposed scheme in ZeitControl’s BasicCard environment [89]. We use a personal computer as a back-end server which has Intel Core i5 CPU processor @2.5GHz, 6GB RAM and 64-bit Windows 7 operating system to run simulations, develop codes (P-Code) and download codes to RFID tag. We can test our codes even if we do not have RFID reader and tag, by simulating the BasicCard environment in the computer. This feature is quite useful for protocol designers before testing their schemes in real-wold applications. The computer basically controls the reader and stores the system data. Also, the software of the BasicCard environment, which is free and functional, supports a higher level language such as Java or ZC-Basic (dialect of Basic). We write our own codes with ZC-Basic because using ZC-Basic is easy to program and there is a detailed library about its usage. Additionally, the heart of a BasicCard processor is its P-Code (like Java programming language) interpreter and written codes are compiled into a machine-independent language called P-Code which is similar to machine code [89].

Fig. 6

Overview of our RFID system [i. Back-end server, ii. Reader (OMNIKEY 5321), iii. Tag (BasicCard ZC7.5)]

Moreover, we use OMNIKEY 5321 device as an RFID reader. The reader complies with ISO 15693 and ISO 14443 standards and can communicate 13.56 MHz RFID tags. We implement our proposed scheme in professional version BasicCard ZC7.5 cards supporting ISO-14443 standard as RFID tag. The tag contains 32K of EEPROM and 4.3K RAM. In the tag, there are also three processors such as CPU, RSA/ECC, and DES/AES co-processors. The overview of our RFID system is depicted in Fig. 6. Finally, our implementation considers the following parameters: a binary 160-bit elliptic curve over of the form $y^2 = x^3 + ax + b$ complying with brainpoolP160r1 standard [72].

We first simulate an RFID system and run several simulations to accelerate and mature our implementation using BasicCard development environment (v8.55). Then, we run tens of realizations and take the average time of all. In the end, we obtain the results presented in Table 7. According to the table, our proposal uses 488 bytes as code size and 3278 bytes as data size on the reader side. Besides, it has a 567 bytes EEPROM usage and 1510 bytes RAM usage on the tag side. Also, the running time of our protocol is on average 442 ms. Actually, we realize that a remarkable amount of the time is consumed for wireless channel communication.

Table 7 Time-memory cost of our proposed protocol implementation in BasicCard

At this point, we would like to emphasize that implementers might obtain different realization results because of some reasons: implementation platform and implementation approach (pipelining the algorithms in FPGA or using processors, etc.). For instance, the running time of ID17 scheme, in WISP platform, is roughly 12,742 ms. Its FLASH/FRAM usage is 29,450 bytes for code size and 3296 bytes for data size. The RAM usage is 1595 bytes. Thus, our implementation has better results than their WISP realization.

In our implementation, an EC point multiplication $T_{ecm}$ takes on average 27 ms. But, this running time includes some extra operations that are used to prevent the RFID tag against side channel attacks.

On the other hand, it is obtained that $T_{ecm}$ takes on average 1, 471 ms in the implementation of ID17 scheme [28]. The authors implement only the main components units (ECMR signature unit and ECMR recovery unit) in FPGA but they do not give any numerical results about the running time of BDD17 scheme [27]. They just present the usage hardware resources for these units such as number of flip flops, slice registers, and LUTs. Finally, the other related papers use Gódor et al.’s [87, 88] simulation results in their works. They accept that $T_{ecm}$ takes averagely 64 ms which is slower than our result, too.

Fig. 7

Computation cost, communication cost and securiy-privacy analysis of the compared works

Figure 7 summarizes the security and performance analysis of aforementioned protocols in Tables 3, 4 and 6. It depicts the computation and communication costs in terms of number of transmitting bytes and number of the executing modular multiplication operations equivalence. It is interpreted that the performance of a scheme increases with approaching the origin point of the figure (0, 0). The more efficient protocols are located on the left-bottom of the figure. The figure also indicates the number of security and privacy vulnerabilities of a protocol within the parenthesis. Smaller value means providing more security and privacy requirements. None of the protocols, except ours, provides all the security and privacy properties mentioned in Table 3. DB19 and ours are only schemes that satisfy forward privacy. Moreover, the mean computation cost of the schemes is 9, 626 $T_{mul}$ equivalence. ID17 and our design is very close the average. ZQ14 and C14 have higher computation efficiency with roughly 4, 800 $T_{mul}$. Also, the mean of byte transmission is approximately 183 bytes. Meanwhile, BDD17 and LZKZ18 are suffering from high communication cost.

9 Conclusion

In this paper, we mainly focused on both theoretical and practical aspects of ECC based RFID authentication protocols. First, we investigated vulnerabilities of the existing protocols and showed that ID17 [28], BDD17 [27], DB19 [56] and LZKZ18 [57] schemes did not provide forward and/or backward privacy. We presented our attacks against these schemes under Vaudenay’s privacy model. Then, we enhanced ID17 scheme and proposed a new and practical ECC based authentication RFID protocol to efficiently satisfy all essential security and privacy properties. Thereafter, we analyzed our improved protocol in terms of security and performance perspectives. We also compared it with recent ECC-based assertive schemes and give an in-depth comparison.

Considering the practicality, we explored the realization of the existing protocols. To the best of our knowledge, the overwhelming majority of ECC based RFID protocols have not yet been implemented and tested so far in a real-word RFID system. Among the previous protocols, the conservative approach for evaluating the performance was utilizing only previous simulation results [87, 88]. Contrary to this approach, we implemented and tested our proposed protocol in ZeitControl’s BasicCard environment, and presented the implementation results. Finally, we evaluated our realization outcomes especially in terms of communication and computational cost to show the performance of our proposed scheme in practice. We demonstrated that our proposed scheme had higher performance providing all common security and privacy features including backward and forward privacy rather than the ECC based RFID authentication protocols implemented in a real-world environment. Also, we believe that this work will shed light on future designs and evaluations of ECC based RFID protocol designers.