ECC-based untraceable authentication for large-scale active-tag RFID systems

Abstract

Radio frequency identification tag authentication protocols are generally classified as non-full-fledged and full-fledged, according to the resource usage of the tags. The non-full-fledged protocols typically suffer de-synchronization, impersonation and tracking attacks, and usually lack scalability. The full-fledged protocols, supporting cryptographic functions, are designed to overcome these weaknesses. This paper examines several elliptic-curve-cryptography (ECC)-based full-fledged protocols. We found that some still have security and privacy issues, and others generate excessive communication costs between the tag and the back-end server. Motivated by these observations, we construct two novel protocols, PI and PII. PI is designed for secure environments and is suitable for applications, including E-Passport and toll payment in vehicular ad-hoc networks. PII is for hostile environments and can be applied in pseudonymous payment and anti-counterfeiting services. After analysis, we conclude that PII can resist many attacks, outperform previous ECC-based proposals in communication efficiency, and provide mutual authentication function and scalability.

1 Introduction

For some time, commercial products have been identified by attached barcodes. The barcodes, however, must be read one by one through an optical reader with a line-of-sight pathway. Nowadays, radio frequency identification (RFID) tags can be scanned hundreds at a time in a contactless manner, and thus potentially could become a replacement for barcodes. A typical RFID system is composed of tags, readers, and a back-end server. Tags are of two types: passive and active. A passive tag does not carry a battery, has a short communication range, is equipped with extremely simple hardware, and is very low cost. Conversely, an active tag has a battery, has a larger communication range, can accommodate more complex computing components, and costs more. Low-cost tags are adapted for general merchandise identification. High-cost active tags can be used for personal identification or luxury goods.

RFID applications, however, also raise new challenges of security and privacy. For example, data passing through the air could allow the product information disclosure. Tags attached to goods carried by people could expose their location and thus violate their privacy. Privacy can be considered into three concepts: anonymity in which the real ID of a tag must be unknown, untraceability in which the (in)equality of two tags must be impossible to determine [40], and backward/forward privacy, which indicates, even if the internal state of a tag is exposed, a tag remains untraceability for its previous/subsequent activities [45]. Besides these privacy issues, literature [13] has identified other potential threats with RFID systems.

• Replay attack An attacker intercepts the data transmitted between a tag and a reader and reuses it to spoof the tag.

• De-synchronization attack An attacker merely intercepts and drops the communication between a tag and a reader, or sends spoofed messages in order to cause the data updated in the tag site and the server site to be out of synchronization. This makes the tag permanently unidentifiable.

• Impersonation attack An attacker uses a message eavesdropped earlier to impersonate a legitimate tag (or server) to pass a server’s (or tag’s) authentication.

• Man-in-the-middle attack An attacker modifies a message transmitted between a tag and a server, creating a false impression that they are communicating with the intended party, when in fact, they are communicating with the attacker.

• Physical attack An attacker corrupts a tag, extracts the confidential data, and then uses it to launch various attacks on other tags.

Facing the above-mentioned new challenges and threats, researchers have proposed many secure and privacy-preserving RFID authentication protocols [6, 10, 13, 15, 18, 26, 35, 41–43, 58, 61, 65, 66, 69, 73, 77, 78, 83, 84]. According to the computation capability and operations supported on the tags, these protocols can be categorized into four basic classes: (1) full-fledged, (2) simple, (3) lightweight and (4) ultra-lightweight [14]. Class (1) supports cryptographic functions such as hashing, encryption [4, 36, 37, 52, 55, 82], and even a public key algorithm [3, 6, 20–22, 24, 38, 39, 46–48, 51, 53, 56, 57]. Class (2) supports a random number function and a hash function, but not encryption or a public key algorithm [7, 64, 75, 80, 81, 85]. Class (3) supports a Pseudo Random Number Generator (PRNG) and Cyclic Redundancy Code (CRC), but has no hashing function [12, 27, 33, 34, 44, 49, 60, 68, 71, 74]. Finally, class (4) contains only simple bit-wise operations like XOR, AND, OR and modular addition [11, 14, 17, 59, 72, 76].

The most frequently used standard for the non-full-fledged tags is the electronic product code (EPC) global UHF Class 1 Generation 2, denoted as Gen2. Gen2 adopts CRC and PRNG components only. Although this tag type is low cost [65], it has considerable privacy issues. This is because the Gen2 protocol transmits unprotected tag identity through the air and allows for information leakage and traceability of the carrier’s location. While the other non-full-fledged RFID tag authentication proposals do focus on privacy issues, they are sometimes accompanied by other problems such as de-synchronization. In the following document, we use several recent proposals to illustrate the typical challenges associated with these non-full-fledged approaches.

Study [15] presented a Gen2-conforming RFID authentication protocol which tried to address Gen2 privacy problems. However, it suffers impersonation and de-synchronization attacks [26]. Later, a remedy against these defects was proposed in [84]. Nevertheless, this remedy exposes tag locations because the tag’s response to the reader’s query always contained an unchanged index $(C_{i})$. Thus, anyone could use this index to distinguish and trace the tag. Meanwhile, another Gen2-conforming solution, named TRAP-3, was proposed by the authors in [10]. However, a de-synchronization attack was found, and an improvement was presented in [83]. This improvement still suffered the same vulnerability; we will show the details in Sect. 3.1. Study [58] presented an ultra-lightweight RFID protocol to address de-synchronization problems. Two reports [73, 83], however, showed that the protocol failed in its attempt, and each further offered a refinement. Unfortunately, both refinements kept the tags’ pseudonyms unchanged before being successfully identified. This fixed data could still jeopardize location privacy.

Several non-full-fledged schemes in [18, 67, 69] tried to provide scalability. However, the scheme in [18] still requires a server to perform a linear search for the tag identification when the tags suffer successive interrogation attacks. The cost of a linear search can be denoted as O($N$), where $N$ is the number of the tags in an RFID system. Study [67] introduces a great many of readers (each reader shares a key with a set of tags, and therefore, the tags are divided into different searching groups) to reduce the searching cost to O($N/\alpha$), where $\alpha$ is the number of readers. We think the scalability of study [67] is still unsatisfactory since deploying too many readers in a site seems impractical. In addition, it suffers tracking problems because the dynamic tag identity $( ID_{i})$ remains the same when the last pass of the previous session is intercepted. This also causes a de-synchronization problem since the server has updated the tag identity, but the tag has not. We will show this in Sect. 3.1. Thus far, the most efficient non-full-fledged proposal to ensure scalability is the scheme in [12], which reduces the server’s searching cost to O($N^{1/2}\hbox {log}N)$. This may still be insufficient when applied in a large-scale environment such as E-Passport or specific industry products, because the database would have to be sorted before the protocol execution.

Motivated by these unsatisfactory non-full-fledged RFID authentication proposals, we consider that a full-fledged approach using a public key cryptosystem could be an attractive solution [6, 35, 78]. Of the available public key cryptosystems, elliptic curve cryptography (ECC) offers the same security level as the others, using shorter keys. This makes ECC a suitable component to embed in resource-limited tags [77]. Many low-cost implementations of ECC primitives have been proposed [3, 6, 20–22, 24, 38, 39, 46–48, 51, 53, 56, 57]. We have reviewed several recent ECC RFID authentication protocols and found that all need at least three passes when active tags are applied. This paper, therefore, constructs two novel two-pass ECC RFID authentication protocols, PI and PII. PI is for secure environments and PII for hostile environments. Both can be applied for large-scale object identification. The potential applications of our proposals are E-Passport [1, 2, 30, 31, 79], public transportation tickets, pseudonymous credit cards [9, 63], payment or targeted re-calls in vehicular ad-hoc networks (VANETs) [28, 29], and anti-counterfeiting for luxury goods [19].

The remainder of this paper is organized as follows. Section 2 introduces the background of the protocols. Section 3 reviews some recent RFID protocols, both non-full-fledged and full-fledged. Section 4 presents our protocols and their security analyses. The discussions are demonstrated in Sect. 5. Finally, we present our conclusion in Sect. 6.

2 Preliminaries

This section introduces the elliptic curve cryptography in Sect. 2.1. Then, a privacy model used to examine the robustness of the traceability for an RFID scheme is described in Sect. 2.2.

2.1 Elliptic curve cryptography (ECC)

We show the concept of ECC [50, 70] below. Suppose $a$ and $b$ are two integers that define the curve of the equation $y^{2 }=x^{3 }+ax + b$. Points $(x,\, y)$ satisfying the elliptic curve equation along with an infinite point $O$ and an addition operation form a cyclic additive group $G$. The operations of group $G$ are defined below.

• $P = (x,\, y)$ is a Group element, then define $-P = (x, -y)$ and $P+ (-P)=O$.

• If $P$ and $Q$ are two distinct elements and $P \ne -Q$, define $P+Q$ as follows: Draw a line through $P$ and $Q$, then the line will intersect with the curve, the intersected point is denoted as -$R$, and define $P +Q =R$.

• If a group element $P = (x, 0)$, then $P + P = O$. Otherwise, draw a tangent line through $P$, the intersected point is defined as $-R$, afterwards $P + P = 2P = R$.

In addition, for the group $G$, there exists a base point $P$, also called generator or primitive root, and it can generate the group $G$. That is $G= \{P,\, 2P,\, 3P, {\ldots }. (n-1)P, nP = O\}$, where $n$ is the order (size) of $G$. The security of ECC builds on the difficulty of the elliptic curve discrete logarithm problem (ECDLP). That is, when the order of $G$ is sufficiently large, given a random group element $Q$, outputting an integer $\alpha$ such that $Q =\alpha P$ is computationally infeasible. In practice, the security level of ECC with the key size (i.e. the order of group $G$) of 160 bits is approximately equal to the security level of RSA cryptosystem with key size of 1,024 bits.

2.2 RFID privacy model

For an RFID authentication protocol, Untraceable Privacy and Backward/Forward Privacy are desirable properties. Untraceable Privacy, i.e. untraceability, indicates that given any two uncorrupted tags and their communication transcripts, it is impossible to determine which transcript belongs to which tag. Backward Privacy means even given all the internal states of a target tag at time $t$, an attacker cannot identify the target tag’s transcripts that occur at time $t',\, t' < t$ [45]. Likewise, Forward Privacy is defined in the same manner, except for that $t'$ should be greater than $t$. In the following, we refer [25, 32, 54] to define these privacy notions formally. We first model the capability of an adversary $A$ through the following queries, where $R$ indicates a reader and $T$ a tag.

• Execute $(R,\, T,\, i)$ query: $A$ eavesdrops on the protocol running between the two communicating parties, $R$ and $T$, in session $i$ of the protocol execution. This query models a passive attack.

• Send $(R,\, T,\, m,\, i)$ query: $A$ impersonates some reader $R$ (or tag $T$) in session $i$ of the protocol by sending message $m$ to a tag $T$ (or a reader $R$). This query will be sent to the victim $T$ (or $R$), and models an active attack.

• Corrupt $(T)$ query: $A$ physically accesses tag $T$’s memory to obtain all its stored keys and memory data. This query also models an active attack.

• Test $(T\_{0},\, T_{1})$ query: This query generates a random bit $b\in \, \{0, 1\}$ and returns $T_{b}$ to adversary $A$. $A$ wins if he guesses $b$ correctly.

Then we have the following definitions.

Definition 1

(Untraceable Privacy) An adversary $A$ and a challenger $C$ are involved in the following game.

• Learning phase $A$ issues above Execute, Send, Corrupt queries to any readers and tags in a given RFID system.

• Challenge phase $A$ chooses two uncorrupted tags, $T_{0 }$ and $T_{1}$, and sends Test $(T_{0},\, T_{1})$ query to $C$. $C$ flips a coin to select bit $b \in \{0, 1\}$ and gives $T_{b}$ to $A$. $A$ then makes any Execute and Send queries to $T_{b}$. Finally, $A$ outputs $b'$.

The probability of $A$ wins the game is denoted by $Adv_A^{Upriv} (k) = {\vert }\hbox { pr}(b'=b)$ - pr(random flip coin) =$\mid \hbox {pr}(b'=b)$ - $1/2\mid$, where $k$ is the security parameter (usually the key size). We say the given RFID authentication scheme possesses the property of Untraceable Privacy if $Adv_A^{Upriv} (k)$ is negligible.

Definition 2

(Backward Privacy) An adversary $A$ and a challenger $C$ are involved in the following game.

• Learning phase $A$ issues above Execute, Send, Corrupt queries to any readers and tags in a given RFID system.

• Challenge phase $A$ chooses two uncorrupted tags, $T_{0 }$ and $T_{1}$, and sends Test $(T_{0},\, T_{1})$ query to $C$. $C$ flips a coin to select bit $b\in \{0, 1\}$ and gives $T_{b }$ to $A$. $A$ then makes Corrupt $(T_{b})$ query to obtain all keys and data in $T_{b}$’s memory. Finally, $A$ outputs $b'$.

The probability of $A$ wins the game is denoted by $Adv_A^{Bpriv} (k) = {\vert }\hbox { pr}(b'=b)$ - pr(random flip coin) =$\mid \hbox { pr}(b'=b)$ - $1/2\mid$, where $k$ is the security parameter (usually the key size). We say the given RFID authentication scheme possesses the property of Backward Privacy if $Adv_A^{Bpriv} (k)$ is negligible.

Definition 3

(Forward Privacy) The definition is the same as the Forward Privacy except that, after $A$ making Corrupt $(T_{b})$ query in the challenge phase, $A\_$is allowed to make Execute and Send query to both tags $T_{0}$ and $T_{1}$. Similarly, we say the given RFID authentication scheme possesses the property of Forward Privacy if $Adv_A^{Fpriv} (k)$ is negligible.

3 Review of RFID authentication protocols

In this section, we review two non-full-fledged and several recently proposed full-fledged RFID authentication protocols in Sects. 3.1 and 3.2, respectively.

3.1 Non-full-fledged RFID authentication protocols

As mentioned in the Introduction, study [83] shows an improvement of TRAP-3, but it still has a de-synchronization problem. Figure 1 illustrates the improved protocol. To demonstrate the de-synchronization attack on this improvement, we assume that there exists an attacker $X$ interacting with two legal readers $R_{A}$ and $R_{B}$, as shown in Fig. 2a through Fig. 2c. At time $T_{0}$, a server and tag pair communicated via $R_{A}$ in session $A$. Supposes $X$ intercepts $M^{\prime }_{20A}$ and suspends the session. $X$ then waits until time $T_{1}$, and when the same pair communicates via another legal reader $R_{B}$ in session $B,\,X$ intercepts $M^{\prime }_{20B}$ and abandons session $B$.

Fig. 1

A TRAP-3 improvement [83]

Fig. 2

a $A$ intercepts $M'_{20A}$ and suspends this session. b $A$ intercepts $M'_{20B}$ and abandons this session. c $A$ sends $M'_{20A}$ to the tag

Subsequently, $X$ resumes session $A$ at time $T_{2}$ and sends $M^{\prime }_{20A}$ to the tag. As a result, the keys stored in both the server $(K^{old} = K^{j} = k_{0} \,{\vert }{\vert } \,k_{1}, K^{cur}=M^{\prime }_{40B} ||M^{\prime }_{5B} )$ and the tag $(K =M^{\prime }_{40B} ||M^{\prime }_{5A} )$ are different. Thus, we demonstrate that Yeh et al.’s improved version of TRAP-3 is still vulnerable to the de-synchronization attack.

Study [69] was designed to resist a de-synchronization attack, but we found it cannot attain the goal still. We depict their protocol in Fig. 3 and demonstrate the attack as follows.

Fig. 3

An RFID authentication and secret update protocol [69]

In Cases 2 and 3 (confidential update) of their protocol, as shown in Fig. 3, server $S$ sends $(r, M_{s})$ to tag $T$, where $r$ is a random number generated by $S$ and $M_{s} (= g_{k}(r \,{\vert }{\vert }\, M_{T}) \oplus (s \,{\vert }{\vert }\,k' \,{\vert }{\vert }\, m'))$ is a $(2l + \,{\vert }m'{\vert }\,)$-bit string. Upon receiving $(r, M_{s}), T$ computes $(s \,{\vert }{\vert }\, k' \,{\vert }{\vert }\, m')=M_{S} \oplus g_{k}(r \,{\vert }{\vert }\, M_{T})$ and checks, whether $h(s) = k$ holds. If it holds, $T$ updates its key $k$ to $k'$ and its counter $c$ to $m$’. However, if the adversary modifies the second $l$ bits of string$M_{s}$ to obtain $M'_{s}$ and sends it to $T$. When $T$ uses $M'_{s}$ to compute $(s \,{\vert }{\vert }\, k' \,{\vert }{\vert }\, m')$, its second $l$ bits would be different from the value $k'$ owned by $S$. Hence, $T$ will have a distinct key from $k'$. This is why we say that Song et al.’s protocol could not resist the de-synchronization attack.

3.2 Full-fledged RFID authentication protocols

This section reviews several recent ECC RFID authentication protocols. An RFID protocol was proposed in [77], which uses ECC Schnorr identification technique to resist passive attacks and counterfeiting. We depict the protocol in Fig. 4.

Fig. 4

An ECC-Schnorr-identification-based RFID protocol [77]

However, this protocol has a tracking problem [42]. When an adversary eavesdrops tag and server’s communications and obtains a transcript, $\{T,\, e,\, y\}$, he can use $e^{-1}$ to obtain the tag ID-verifier,$Z (= -sP)$ by computing $e^{-1}(T - yP)$. Then, the adversary can track the tag with $Z$. We show another way to track a specific tag. An adversary $A$ first eavesdrops a transcript $\{T_{1} = r_{1}P,\, e,\, y_{1} = se+r_{1}\}$. $A$ then pretends a legitimate reader to interrogate a target tag. After receiving $T_{2} (= r_{2}P)$ from a tag, $A$ sends a challenge $e' (= e)$ back to the tag, and obtains $y_{2} (= ae+r_{2})$. $A$ then can recognize the specific tag by checking whether $(y_{2} - y_{1})P$ is equal to $T_{2} - T_{1}$.

In addition to the tracking problem, this protocol is vulnerable to man-in-the-middle attacks because the data of a communication transcript are linearly related to the tag ID-verifier (refer to the note in Fig. 5). In Fig. 5, an adversary $E$ stands between a tag and a server to communicate with each by tampering original transmitted messages. The server and the tag eventually complete the identification process but do not know at all that they connect with $E$ indeed.

Fig. 5

A man-in-the-middle attack to the protocol [77]

Regarding the scalability, we let the server compute $Z^{*} = e^{-1}(T - yP)$ and then directly look up a tag in server’s DB with $Z^{*}$. Tuyls et al.’s protocol, therefore, provides scalability.

An improvement of [77] uses ECC Okamoto’s identification technique to resist active attacks was proposed in [6]. However, the protocol in [6] like the one in [77] also has a tracking problem and a man-in-the-middle vulnerability.

Study [42] presented an Elliptic Curve Based Randomized Access Control (EC-RAC) protocol to address the tracking problem. Unfortunately, EC-RAC protocol later was found not to resist tracking and replay attacks by the authors in [43]. Therefore, a revised version EC-RAC II was proposed. However, this revised version exposes to the risk of man-in-the-middle threats [41]. Accordingly, study [41] presented EC-RAC IV to overcome both tracking and man-in-the-middle vulnerabilities through eliminating the possibility of linear operations on the communication transcripts. Figure 6 illustrates the scheme EC-RAC IV, where $x( eP)$ indicates the x-coordinate of the elliptic curve point eP. Another variant of EC-RAC IV [40] is shown in Fig. 7 allows an additional password transfer. These two schemes eventually achieved their security and privacy goals.

Fig. 6

EC-RAC IV RFID identification protocol

Fig. 7

EC-RAC IV variant with password transfer

Study [53] employed CryptoGPS primitives [23, 62] to design an ECC digital signature scheme for low-cost RFID tags, as shown in Fig. 8. The study also presented a low-cost hardware implementation. Its goal is to prevent tag cloning, and for data authentication to prevent transmission forgery. As a digital signature scheme, the scheme in this study causes tag traceability in essence, because the tag should claim who it is, i.e. presents its public key $Z$ to a server in the second transmitted message (see Fig. 8). Alternatively, the scheme could be treated as a privacy-preserving scheme which turns the tag’s public key $Z$ into a secret ID-Verifier shared with the server only. Under this case, it can resist possible deduction of an ID-Verifier from a communication transcript due to the one-way property of the hash function. However, the tag still can be tracked by an attacker who replays an earlier eavesdropped message $m$ to a tag and observes whether the tag response is the same as the earlier eavesdropped response $\{c,\, y\}$. Another problem is a brute searching for server identifying a tag with the ID-Verifier $Z$. Thirdly, the Forward and Backward Privacy cannot be preserved when the stored data (i.e., $s,\, Z$, and $t =H(rP)$) in a tag are exposed to an adversary.

Fig. 8

An RFID signature scheme [53]

The above-mentioned so far are protocols in which a tag initiates the first message and therefore, cannot be applied for passive RFID tags without battery embedded. All of them could serve for passive tags if the additional hello message is first initiated from a server to a tag and makes the tag charged. Nevertheless, this result in a three-pass protocol into a four-pass protocol and generate excessive communication costs. In contrast, the scheme [16] can be applied for both active and passive tags without any adjustment, as shown in Fig. 9. Moreover, it provides mutual authentication and scalability, and resists many threats, including tracking and man-in-the-middle attacks.

Fig. 9

An RFID mutual authentication protocol [16]

4 Proposed protocols

Our goal of this research aims to propose a two-pass ECC-based RFID authentication protocol while considering privacy protection, scalability and various attack prevention. We propose two such kinds of protocols, PI and PII. PI is for secure environments and PII for hostile ones. As usual, we assume that the server and the readers communicate via secure channels. Therefore, we use “server” to represent “server/reader” for short. Each of our protocols consists of two phases, namely, an initialization phase and an authentication phase. Before describing PI and PII, we first define the used notations.

$G$ :

an additive group of order $q$ on an elliptic curve,

$P$ :

a primitive element of $G$,

$\textit{ID}_{i}$ :

tag$_{i}$’s identity,

$s$ :

server’s private key,

$Y$ :

server’s public key,

$H$ :

a one-way hash function mapping from $\{0, 1\}^{*}$ to $\{0, 1\}^{q^{\prime }}$,

$H_{1}$ :

a one-way hash function mapping from $G$ to $\{0, 1\}^{q^{\prime }}$,

$H_{2}$ :

a one-way hash function mapping from $Z_{q} \times G$ to $\{0, 1\}^{q^{\prime }}$,

$q'$ :

the hash output length, and

$k, r$ :

two random numbers in $Z_{q}$.

4.1 Protocol PI for secure environments

A secure environment assumes that the reader is trusted and there is no attacker exists around the reader and the tag, for example, an E-Passport gateway in the airport. That is, a reader in the gateway checks each E-Passport passing, which is always guarded against by the police. In practice, a secure environment may be fulfilled by setting a detector to monitor possible intruders periodically. Thus, the proposed PI scheme does not need to consider the eavesdropping or other threats around the reader and the tag, but only focus on the security of a distant back-end server. For example, the tag communication transcripts logged on server’s DB could leak due to server insider attacks or outsider intrusions. The following is the proposed PI scheme.

4.1.1 Initialization phase

In this phase, server $S$ generates an elliptic-curve group $G$ with a base point $P$ and order $q$, and the ECDLP on $G$ is computationally infeasible. $S$ also generates a random number $s$ as its private key and computes Y $=$ sP as its public key. In addition, S defines two secure hash functions: $H$: $\{0, 1\}^{*}\rightarrow \{0,1\}^{q}$. Then, $S$ starts to initialize all tags in the system. It produces a database containing two fields, $ID_{i}$ and $H(ID_{i})P$, and sorts it by $H( ID_{i})P$ for each tag. Finally, $S$ distributes $ID_{i},\,H( ID_{i})P$ and $Y$ to each $Tag_{i}$, over a secure channel, where $i = 1$ to $N$ and $N$ is the number of tags in the system.

4.1.2 Authentication phase

In this phase, server $S$ and $Tag_{i}$ perform the following steps, also depicted in Fig. 10.

Step1:

$S$chooses a random number $r$, computes $T_{1} = rY$, and broadcasts $T_{1}$.

Step2:

Upon receiving $T_{1},\,Tag_{i}$ computes $T_{2} = H(ID_{i}) T_{1}$ and $v = H_{2}(ID_{i},\,T_{2})$, and sends the message $\{T_{2},\, v\}$ back to the server.

Step3:

Upon receiving $\{T_{2},\,v\},\,S$ applies its private key $s$ and the one-time secret $r$ to compute $X =s^{-1}r^{-1} T_{2}$, which is supposed to be $s^{-1}r^{-1} H(ID_{i}) T_{1}=s^{-1}r^{-1} H(ID_{i}) rY = H(ID_{i})P$. Then it looks up a tag record with $X$. If the corresponding tag not found, $S$ aborts the message and terminates. Otherwise, S gets the tag’s ID from the found record and verifies whether $H_{2}(ID_{i},\,T_{2})$ is equal to the received $v$. If the verification passes, $S$ accepts $Tag_{i}$.

Fig. 10

Proposed RFID authentication protocol PI

4.1.3 Security and privacy analysis

Since the PI protocol is performed in a secure environment, only an authorized reader is allowed to interrogate a tag. In other words, the interrogation message $T_{1}$ must be a randomly generated message from the legal reader. In addition, $T_{1}$ is not impossibly replayed in a secure environment. Therefore, the communication transcript $\{T_{1},\, T_{2},\,v\}$ is always different and looks random. From the theoretical viewpoint, the probability of the occurrence of two identical interrogation messages is $1/q$. This is negligible since $q$ must be sufficiently large to make ECDLP infeasible. Due to the randomness of communication transcripts, the anonymity and untraceability privacy can be preserved even when the server’s DB is intruded by hackers.

Regarding the scalability, the proposed PI allows the server to directly look up a possible tag record by using the computed $X$ which is supposed equal to $Tag_{i}$’s identifier $H( ID_{i})P$ (also see the Step 3 above). We emphasize that the identifier $H(ID_{i})P$ can be correctly computed simply when $Tag_{i}$’s response $\{T_{2},\, v\}$ is not tampered by any attackers, i.e. only a secure environment can achieve this circumstance. Therefore, the server searching cost O(1) can be ensured.

Other threats like eavesdropping, impersonation, man-in-the-middle and replay can be easily avoided due to the guarantee of the secure environments.

4.2 Protocol PII

PII is designed for any environments, secure or hostile. In this case, a tag cloud be interrogated by a malicious reader; a man in the middle or an eavesdropper cloud around a tag or a reader. Therefore, all kinds of possible threats should be taken into account. The following is the details of the proposed PII.

4.2.1 Initialization phase

In this phase, server $S$ first generates system parameters like PI does. Thus we have $G,\, q,\, P,\, s$ and Y $=$ sP. In addition, $S$ defines three secure hash functions, $H$: $\{0, 1\}^{*}\rightarrow \{0, 1\}^{q^{\prime }},\, H_{1}$: $G{\rightarrow }\{0, 1\}^{q^{\prime }}$, and $H_{2}$: $\{0, 1\}^{q} \times G \, {\rightarrow }\{0, 1\}^{q^{\prime }}$. Secondly, $S$ starts to initialize all tags in the system. $S$ generates a random number $ID_{i}$, computes $H( ID_{i})$ for each tag, and produces a database containing two fields, $ID_{i}$ and $H(ID_{i})$, and sorts it by $H(ID_{i})$. Finally, $S$ distributes $H(ID_{i}),\,ID_{i}$ and server’s public key $Y$ to each $Tag_{i}$ over a secure channel. Each tag then stores them into its memory.

4.2.2 Authentication phase

In this phase, when authenticating $Tag_{i},\,S$ carries out the following steps, also depicted in Fig. 11.

Step 1:

$S$ generates a random number $r$, computes $C_{1}= rP$ and $C_{2}= rY$, and uses its private key to produce a signature $sn = r + s \cdot H_{1}(C_{2})$. Then it broadcasts $C_{1},\, C_{2}$ and sn.

Step 2:

Upon receiving the broadcast message, $Tag_{i}$ uses the server’s public key to verify the received signature, i.e. $sn\cdot P =? C_{1} + H_{1}(C_{2})\cdot Y$. If the equation does not hold, $Tag_{i}$ aborts the message and stops. Otherwise, $Tag_{i}$ accepts the server’s interrogation message and then prepares authentication data. $Tag_{i}$ computes $C_{3 }= kC_{2},\, c= H(ID_{i}) + H_{1}( kC_{1})$ and $d = H_{2}( ID_{i},\,kC_{1})$, and answers $C_{3},\, c$ and $d$ to the server.

Step 3:

Upon receiving $Tag_{i}$’s response, $S$ computes $H(ID)^{*}= c - H_{1}(s^{-1}C_{3})$, which is supposed that $H(ID_{i})^{*} = c - H_{1}(s^{-1}T_{3})=H_{1}(ID_{i}) + H_{1}( kC_{1})- H_{1}(s^{-1}kC_{2})=H_{1}( ID_{i})$. $S$ then uses $H(ID_{i})^{*}$ to look up a tag in the DB. If it does not find the corresponding tag, $S$ aborts the response and terminates. Otherwise, $S$ gets the tag’s identity $ID^{*}$ from the found record, and verifies whether $H_{2}(ID_{i}$, $s^{-1}C_{3})$ is equal to the received $d (=H_{2}( ID_{i},kC_{1}))$, where $s^{-1}C_{3}=s^{-1}kC_{2}=s^{-1} krY = krP = kC_{1}$. If the verification passes, $S$ identifies $Tag_{i}$.

Fig. 11

Proposed RFID authentication protocol PII

4.2.3 Security and privacy analysis

In the following, we first discuss some attacks, (1) through (3), on our protocol PII, which often occur in RFID systems. Then, we show that our protocol has scalability and mutual authentication at items (4) and (5). Finally, we apply the formal privacy model to analyze the Untraceable Privacy and Backward/Forward Privacy of the proposed PII.

Replay attack

When an attacker replays an old message flow, says $\{C_{1}^{(old)},\, C_{2}^{(old)},sn^{(old)}\}$, to a Tag. Although the Tag cannot recognize the message as a replayed one, it answers a random response, says $\{C_{3}^{(new)},\, c^{(new)},\, d^{(new)}\}$, based on Tag’s randomly chosen integer $k$. In other words, the random response $\{C_{3}^{(new)},\, c^{(new)},\, d^{(new)}\}$ cannot be distinguished from any other response e.g., $\{C_{3}^{*},\, c^{*},\,d^{*}\}$ due to the randomness of $k^{(new)}$ and $k^{(*)}$. As a result, the attacker gains no advantage of the response, i.e. it cannot be used for identifying or tracking any tags. On the other hand, if an old flow $\{C_{3}^{(old)},\, c^{(old)}, \,d^{(old)}\}$ is replayed as a response to a new interrogation $\{C_{1}^{(new)},\, C_{2}^{(new)},\,sn^{(new)}\}$, the server will reject $\{C_{3}^{(old)},\, c^{(old)},\, d^{(old)}\}$. This is because the server cannot obtain the corresponding tag’s ID due to the different $k^{(new)}$ and $k^{(old)}$, i.e. the probability of $s^{-1}T_{3}^{(old)}=k^{(new)}T_{1}^{(new)}$ is sufficiently small to be negligible. Therefore, replaying an aged response $\{C_{3}^{(old)},\, c^{(old)},\, d^{(old)}\}$ cannot cause any effect.

Man-in-the middle attack

Assume that an adversary $A$ launches a man-in-the-middle attack (MIMA) between a server and a tag. He pretends to be the real server to the tag and vice versa. We now detail this attack prevention of our scheme as follows and also illustrate it in Fig. 12.

Fig. 12

Man-in-the-middle attack on PII

Step 1:

The server chooses a random number $r$, prepares $\{C_{1} = rP, C_{2}= rY,sn =r+s \cdot H_{2}(T_{2})\}$ and sends them to the tag.

Step 2:

$A$ intercepts the message and chooses a random number $r'$ to compute $C_{1}'=rP + r'P$ and $C_{2}'= rY + r'Y$. The value of sn’ should be equal to $(r+ r')+s \cdot H_{2}(C_{2}')$. However, without the knowledge of $s, A$ cannot generate valid sn’ to be successfully verified by the tag.

Step 3:

Assume that $A$ succeeded in step 2, i.e. valid $sn' = (r+ r')+s \cdot H_{2}(T_{2}')$ were produced. The tag will accept $\{C_{1}',\,C_{2}', sn'\}$ and then prepare an autnetication message. It chooses a random $k$, computes $C_{3 }=kC_{2}',\,c= H(ID)+ H(kC_{1}')$ and $d=H_{2}(ID,kT_{1}')$, and sends $\{C_{3},\,c,\, d\}$ to the server.

Step 4:

$A$ intercepts $\{C_{3},c,d\}$ and tries to produce valid $\{C_{3}', c', d'\}$. $A$ can randomly select an integer $k'$ and computes $C_{3}'=k'C_{2}$. Then, to produce a valid $c',A$ should know tag’s $H(ID)$ from the intercepted $c(= H( ID) + H(kC_{1}'))$. However, without the knowledge of $k$ (a one-time secret generated by the tag), it is hard to extract $H(ID)$ and produce valid $c'$.

From the above analysis, we can see such an MIMA attack cannot work.

Physical attack

Supposing that an adversary $A$ uses physical means to obtain $Tag_{i}$’s secrets $ID_{i}$ and $H(ID_{i})$, the proposed PII scheme can still keep the Backward and Forward Privacy, i.e., the previous and subsequent communication scripts of the $Tag_{i}$ cannot be recognized. This is because any transcript $\{C_{1}, C_{2},sn,C_{3},c,b\}$ of PII is uniformly random due to the random integers $r$ and $k$. Any transcript of PII therefore, cannot be computationally linked to the specific $ID_{i}$. A formal analysis of Backward and Forward Privacy of PII will be presented in (7).

Scalability

It is obviously that server takes O(1) to search for a tag by using the computed $H(ID_{i})^{*}$. Therefore, the proposed PII provides scalability.

Mutual authentication

In our scheme, a server computes $\{C_{1} = rP,C_{2} = rY,sn = r +sH_{1}(C_{2})\}$, where sn is server’s signature related both $C_{1}$ and $C_{2}$, and sends them to a tag. Then, the tag verifies the signature Sn by applying server’s public key $Y$. On the other hand, the tag which has identity $ID_{i}$ computes $C_{3}= kC_{2},\, c =H(ID_{i})+ H_{1}(kC_{1})$ and $d= H_{2}( ID_{i},kC_{1})$ to be checked by the server. We know that only legal $Tag_{i }$ has valid $ID_{i}$ embedded to let the server find it in its DB. Thus, our protocol can achieve mutual authentication.

Anonymity

From the transmitted data of the proposed PII, $\{C_{1} = rP, C_{2} = rY,{sn} = r + {sH}_{1}(C_{2}),\, C_{3} = {kC}_{2},\,c =H({ID}_{i})+ H_{1}({kC}_{1}),\,d= H_{2}( ID_{i},kC_{1})\}$, only $c$ and $b$ contain tag’s ID. However, the tag ID be shuffled through one-way hash functions. One-way property indicates obtaining a pre-image (e.g., $ID_{i})$ from a hash result (e.g., $H({ ID}_{i}))$ is very hard. Thus, our scheme has anonymity.

Untraceable privacy and backward/forward privacy

We use the formal notions described in Sect. 2.2 to show that the proposed PII possesses Untraceable Privacy and Backward Privacy and Forward Privacy.

Lemma 1

According to Definition 1, we claim our RFID identification protocol PII possesses Untraceable Privacy.

Proof

We prove this lemma using the following reduction. In the adversary game, if $A$ could differentiate two uncorrupted tags $\{T_{b}, T_{1-b}\}$, where $b = 0$ or 1, from a tag response $\{C_{3}, c, d\}$ to a query $\{C_{1},\, C_{2},{sn}\}$. This implies that $A$ knew $H({ID}_{b})$, without the knowledge of server’s secret $s$ and could derive rkP, when giving $C_{3} =krsP,\, c=H({ID}_{b}) + H_{1}({rkP})$ and $d = H_{2}({ID}_{b}, krP)$. However, this is computationally infeasible. If this happened, we could use $A$ to construct an algorithm $B$ to extract rkP from$C_{3}$, and then use algorithm $B$ to solve the ECDLP. This is a contradiction. The design of algorithm $B$ is shown in Fig. 13. We prove this lemma.

$\square$

Fig. 13

$B$’s construction of solving ECDLP

Lemma 2

According to Definition 2, we claim our RFID identification protocol PII possesses Backward Privacy.

Proof

We prove this lemma using the following reduction. In the adversary game, $A$ is given the corrupted $T_{b}$’s secret $\{{ ID}_{b},\, H({ID}_{b})\}$, where $b = 0$ or 1, and two historic communication transcripts $\{C_{1}^{(0)},\, C_{2}^{(0)},\,sn^{(0)},\,C_{3}^{(0)},\, c^{(0)},\,d^{(0)}\}$ and $\{C_{1}^{(1)},\, C_{2}^{(1)},sn^{(1)},\, C_{3}^{(1)},\,c^{(1)},\,d^{(1)}\}$. If $A$ could determine which transcript belongs to $T_{b}$, this implies $A$ must be able to deduce $krP^{(b)}$ from $H_{1}(krP^{(b)})$ to confirm $d^{(b)}$ for assuring the right tag. However, again this is impossible. Since, if it were true, the one-way property of hash function $H_{1}$ is violated. We thus prove this lemma.$\square$

Lemma 3

According to Definition 3, we claim our RFID identification protocol PII possesses Forward Privacy.

Proof

As this property is similar to Backward Privacy, the proof of this lemma can refer to Lemma 2.$\square$

5 Discussions

In this section, we compare our work PII with recent ECC RFID authentication schemes, including ECRAC IV, ECRAC IV variant, the scheme (with secret ID-verifier) in [53], and the scheme in [16], all of which are reviewed in Sect. 3.2.

As we know, ECC-based RFID protocols belong to the full-fledged class and are believed to attain scalability and avoid de-synchronization more easily than the non-full-fledged protocols. Our scheme, EC-RAC IV, EC-RAC IV variant and the scheme in [16] do achieve these two aims, but the scheme in [53] does not have scalability if it makes the tag ID-verifier secret for the anonymity (see Sect. 3.2). A recent ECC RFID protocol [24] has de-synchronization issue because it adopts a dynamic ID as the non-full-fledged protocols did, which need a server and a tag synchronously update the dynamic ID. Therefore, we can see that inadvertent designed ECC proposals could cause scalability and de-synchronization problems.

Mutual authentication is another important feature that many RFID schemes aimed at. This feature allows a tag and a server to confirm that the received messages are sent by the intended party. It thus can avoid malicious probing or wrong data updating. The schemes, EC-RAC IV, EC-RAC IV variant and [53], provide only tag-to-server authentication but not server-to-tag authentication. Our scheme provides server-to-tag authentication by letting a server sign the transmitted data, and also provides tag-to-server authentication through a hash result generated with the tag identifier (see Sect. 4.2(5) for details). The scheme in [16] uses two hash results for tag-to-server and server-to-tag authentications respectively. Both our scheme and scheme [16] require a hash function calculator embedded on tags. This increase the hardware cost of a tag, although the computation cost of an ECC point multiplication (e.g., $rP= P+P {\cdots }+P$, which is $r - 1$ times of point additions) is about 500 times a hash value generating [24]. In other words, the increase of hash computations is trivial but the increase of hash hardware for an RFID tag should be carefully considered. For a high-cost tag, additional hash hardware may be not a burden. We will discuss more tag hardware cost in a later paragraph.

Regarding the MIMA, earlier ECC solutions based on Schnorr identification schemes [6, 42, 43, 77] suffer this attack, but EC-RAC IV terminates this weakness. The scheme in [53] also based on Schnorr identification, but it takes advantage of the one-way property of a hash function to prevent the MIMA. Our scheme and scheme [16] both employ the signature technique and the one-way hash results for authenticating entities. Such strategies seem work for prevention the MIMA by eliminating the possibility of linear composition from the communication transcripts.

Privacy-preserving is always an important issue in RFID identification study. Except the basic requirements of anonymity and untraceability, Backward Privacy and Forward Privacy are stronger privacy notions that we have mentioned. Recently, privacy notions of wide (or narrow) and strong (or weak) have been introduced in [40, 78]. Weak privacy is equivalent to untraceability while strong privacy is equivalent to both Backward and Forward Privacy in our study. The wide (or narrow) indicates that an attacker has knowledge of the verification result (accept or reject) from a side channel, e.g., the question, whether a door opens or not. Another example as shown in [5] demonstrated that if tags emit a distinctive “radio fingerprint,” then no protocol-level countermeasures can prevent privacy infringement. Therefore, when focusing only on protocol-level privacy, we can see that EC-RAC IV, EC-RAC IV variant, scheme [16] and our work do have the strong privacy, i.e., the Backward and Forward Privacy. In addition, scheme [53] (without publicly transmitting tag ID-verifier) can preserve untraceability if it applied in a secure environment, e.g., E-Passport.

Communication efficiency is another important goal for this study. Our RFID authentication protocol is very efficient. It uses only two passes to achieve the same security and privacy requirements as EC-RAC IV, EC-RAC IV variant and scheme [16] do (these schemes need at least three passes). Although, scheme [53] is a two-pass protocol, their design does not focus on privacy preserving. To be as competitive as our proposal, we try to reduce EC-RAC IV to a two-pass protocol as shown in Fig. 14. However, we found the reduced version is vulnerable to tag impersonation attack. In the attack, an adversary $A$ eavesdrops two successful protocol runs between the server and a specific tag, obtaining the transcripts of $\{e,\, T_{1} =rP,\, T_{2}= (r + s\hat{e})Y\}$ and $\{e',T_{1}'=r'P,\, T_{2}'= (r' + s\hat{e}')Y\}$. $A$ can then compute $e''=e' - e, \hat{e}'' = x(e''P), T_{1}''=T_{1}' - T_{1} = (r' - r)P$, and $T_{2}''=T_{2}' - T_{2} = (r' +\hat{e}''s)Y - (r +\hat{e}s)Y = (r' - r)Y + (\hat{e}'' -\hat{e})sY$. We found that $T_{1}''$ and $T_{2}''$ satisfy $\hat{e}''{-1}(y^{-1}T_{2}'' -T_{1}'') = \hat{e}''^{-1}((r' - r)P + (e' - e)sP - (r' - r)P)= (e'- e)^{-1}(e'- e)sP = sP$. This means that by using $\{e'',\, T_{1}'',\,T_{2}''\}$, the tag will be successfully authenticated by the server. In this way, ${A}$ can generate any legitimate authentication messages at his will to impersonate any specific tag successfully. Therefore, the attempt to convert EC-RAC IV to a protocol with fewer passes fails.

Fig. 14

Reduced EC-RAC IV

The tag hardware cost for the compared schemes is a combination of three factors (which all are measured in gates): typical ECC implementation (with point multiplication), CryptoGPS (without point multiplication), and hash function. An efficient typical ECC implementation [6] takes 8,214 gates for 160-bit key size, attaining about the 80-bit security level. CryptoGPS identification technique [23, 62] adopted by [53] takes only 1,967 gates to compute modular multiplications and modular additions with respect to ECC point coefficients (e.g., $y= r + sc$). In addition, an implementation of SHA-1 proposed by the authors in [53] takes 5,527 gates. Due to the high cost of SHA-1 implementation, we think it might be too expensive for the tags of our proposal PII and therefore, consider another cheaper hash implementation, such as the low-cost hash function study [8] which transforms symmetric block cipher schemes into low-cost hash function. In the study, a DM-PRESENT-80 hash function (Davies-Meyer mode, 80-bit block length, 64-bit hash length, 64-bit security), focusing on one-way property only, takes about 2,000 gates. While a DM-AES-128 hash function (Davies-Meyer mode, 128-bit block length, 128-bit hash length, 80-bit security), focusing on both collision-resistance and one-wayness, takes about 4,400 gates. In summary, scheme [53] requires the lowest tag hardware cost, because it uses of CryptoGPS and a hash implementation. Scheme [16] and our PII require tag hardware about 10K gates; it is still believed to be acceptable for a high-cost RFID tag. Besides, for low-cost consideration, PII tag can adopt only one hash function, Hash(.), for all hash computations of $H(.),\, H_{1}(.)$ and $H_{2}(.)$. More precisely, the input of the function Hash(.) can be any input of $H(.), H_{1}(.)$ and $H_{2}(.)$; the output of Hash(.) is a 64-bit random string. The low-cost DM-PESENT-128 can be a candidate Hash(.).

Table 1 shows the comparison result that we discussed above.

Table 1 Comparisons of recent ECC RFID authentication protocols

We further examine the tag computation load and transmission size. As we know, in the ECC-based RFID schemes, the point multiplication is the heaviest computations. According to [53], it takes about 500 times of time cost than a hash computation. In Table 1, we show only the number of point multiplications and hash computations the protocols need but ignore the other minor computations like random number generating and modular operations. It is obvious that scheme [53] has the best performance taking only one hash. Our PII, requiring four point multiplications and three hashing, takes a little higher computation overhead. To save it, we reduce the PII protocol by eliminating the signature verification for the tag which takes two point multiplications and one hashing (But the reduced PII will lose the server-to-tag authentication function). As a result, the reduced PII is competitive with EC-RAC IV. Regarding the transmission size, we adopt an ECC point as 160 bits and a hash value as 64 bits. Then EC-RAC IV and scheme [53] have the smallest size with 480 bits. While our PII has the biggest size with 748 bits, but the reduced PII has a moderate size with 608 bits.

To sum up, compared to EC-RAC IV the proposed PII takes only two passes and possesses mutual authentication but requires more cost in tag hardware, computation overhead and transmission size. Reducing the cost that the tag authenticates the server (i.e., the signature verification takes two point multiplications and one hashing) or finding other authentication approaches could be the aim of the future work.

6 Conclusion

In this paper, we reviewed several recent lightweight and ECC-based RFID authentication protocols and showed that they either have a certain security deficiency or are less efficient. We, therefore, based on ECC proposed two novel RFID authentication protocols, PI and PII, to overcome the drawbacks. We showed that PI works correctly and PII can resist various attacks and has scalability, untraceability, and forward and backward privacy. From the comparison results among PII and various ECC-based RFID authentication protocols, we conclude that the proposed protocol PII (the reduced version), which requires only two passes, and uses just two point multiplications and two hash operations on the tag side, not only had the same security level as EC-RAC IV but also was more efficient than the recently proposed solutions. We, therefore, conclude that PII is suitably applied in a real mobile world which needs high security and large-scale deployment, such as E-Passport.