Cryptanalysis and improvement of an efficient mutual authentication RFID scheme based on elliptic curve cryptography

Abstract

Radio frequency identification (RFID) is a wireless technology for automatic identification and data capture. Security and privacy issues in the RFID systems have attracted much attention. Many approaches have been proposed to achieve the security and privacy goals. One of these approaches is RFID authentication protocols by which a server and tags can authorize each other through an intracity process. Recently, Chou proposed a RFID authentication protocol based on elliptic curve cryptography. However, this paper demonstrates that the Chou’s protocol does not satisfy tag privacy, forward privacy and authentication, and server authentication. Based on these security and privacy problems, we also show that Chou’s protocol is defenseless to impersonation attacks, tag cloning attacks and location tracking attacks. Therefore, we propose a more secure and efficient scheme, which does not only cover all the security flaws and weaknesses of related previous protocols, but also provides more functionality. We prove the security of the proposed improved protocol in the random oracle model.

1 Introduction

Radio frequency identification (RFID) technology is rapidly becoming ubiquitous, gradually replacing barcodes as the means of product or item identification [1]. A typical RFID system consists of three components: tags, readers, and a back-end server. An RFID tag is a radio transponder that is composed of an integrated circuit for storing and processing identification information, as well as an antenna for communicating with RFID readers [2, 3]. When a back-end server wants to identify one or more tags, a reader emits an interrogation signal via its antenna. Any tag within range of the signal responds with certain stored data, such as a tag identifier. The reader then passes the received tag data to the back-end server for further processing, including tag identification and information retrieval [4]. The radio interface between the tags and reader is generally insecure, while the channel between the reader and back-end server is a fixed infrastructure and can be generally assumed to be secure. The insecure wireless communication channel between the tags and reader will induce some serious security and privacy problems. The possible security threats to RFID systems include denial of service, man in the middle, counterfeiting, spoofing, eavesdropping, traffic analysis, traceability, de-synchronization etc. One of the most important way to assure privacy and security in RFID systems is authentication protocol [5, 6].

Many efficient and private RFID authentication schemes have been proposed in the literature. Most attempts to design RFID authentication protocols rely on the use of symmetric key cryptography (e.g., [7–12]). The main reason why most RFID authentication protocols use symmetric-key primitives, lies in the common perception of public-key cryptography being too slow, power-hungry and too complicated for such low-cost environments. However, recent works proved this concept to be wrong, as for example the smallest published elliptic curve implementations [13, 14] consume less area than the candidate cryptographic hash algorithms proposed in the SHA-3 competition [15]. Moreover, symmetric-key solutions usually suffer from scalability problems, that is, the back-end server requires a linear search to identify a tag [16–19]. These have led to the introduction of public-key based RFID authentication protocols using elliptic curve cryptography (ECC). This approach solves the scalability issues, prevents cloning attacks and offers advanced privacy protection [20, 21].

In 2006, the first ECC-based RFID authentication protocol was proposed by Tuyls and Batina [22] using the Schnorr identification scheme [23]. In 2007, Batina et al. [24] proposed a similar ECC-based solution by applying Okamoto identification scheme [25]. But, Lee et al. [26] pointed both Tuyls and Batina’s protocol, and Batina et al.’s protocol suffer from privacy problems. To address these privacy problems, Lee et al. [26], O’Neill and Robshaw [27] and Godor et al. [28] separately proposed improved ECC-based RFID authentication protocols. However, Chou [21] recently indicated that the three schemes [26–28] still have no scalability. Chou then designed a novel ECC-based RFID authentication protocol, to avoid these issues.

In this paper, we show that Chou’s protocol [21] does not achieve tag (forward) privacy, tag authentication, server authentication, and mutual authentication. As such the protocol is susceptible to impersonation attacks, location tracking attacks and tag cloning attacks. Then, we propose an improved protocol to enhance the security of Chou’s protocol. Our improved protocol does not only maintain the merits and cover the demerits of the Xie’s protocol, but also meets all the requirements of such protocols. Finally, the security of the proposed protocol is proved in the random oracle model.

The rest of this paper is organized as follows. Section 2 introduces the definitions of elliptic curves and security model of RFID authentication protocols. In Sect. 3, we review the Chou’s RFID authentication protocol. In Sect. 4, we describe the weaknesses of the Chou’s protocol. An improved protocol is proposed and analyzed in Sect. 5. In Sect. 6, we make a comparison between our protocol and some related protocols. In Sect. 7 we make a comparison between security and performance. Finally 8 concludes the paper.

2 Preliminaries

2.1 Elliptic curves

An elliptic curve $E$ over a field $\mathbb {F}_{p}$ is defined by an equation

$$\begin{aligned} E:y^{2} + a_{1} xy + a_{3} y = x^{3} + a_{2} x^{2} + a_{4} x + a_{6} \end{aligned}$$

where $a_{1} ,a_{2} ,a_{3} ,a_{4} ,a_{6} \in \mathbb {F}_{p}$ and $\Delta \ne 0$ where $\Delta$ is the discriminate of $E$. The above equation is called the Weierstrass equation. The condition $\Delta \ne 0$ ensures that the elliptic curve is smooth, that is, there are no points at which the curve has two or more distinct tangent lines. Also included in the definition of an elliptic curve is a single element denoted by $\mathcal {O}$ and called the point at infinity. The chord and tangent rule is used for adding two points to give a third point on an elliptic curve. Together with this addition operation, the set of points denoted as $E(\mathbb {F}_{p})$ forms a commutative group $\mathbb {G}$ under addition with $\mathcal {O}$ serving as its identity and $P$ as its generation.

Elliptic curves have been widely used to construct cryptographic primitives including encryption functions, signature scheme, cryptographic protocols and so on (e.g., [29–34]).

2.2 Computational assumptions

Let $\mathbb {G}$ be a cyclic additive group generated by $P$, whose order is a prime $p$.

Definition 1

(Discrete Logarithm Problem (DLP)) Given $P,aP\in \mathbb {G}$, find $a \in \mathbb {Z}^{*}_{p}$.

Definition 2

(Computational Diffie–Hellman Problem (CDHP)) For $a, b \in \mathbb {Z}^{*}_{p}$, given $P,aP,bP\in \mathbb {G}$, find $abP\in \mathbb {G}$.

Definition 3

(Decision Diffie–Hellman Problem (DDHP)) For $a,b,c \in \mathbb {Z}^{*}_{p}$, given $P,aP,bP,cP\in \mathbb {G}$, find if $cP=abP$.

2.3 Security requirements

Several security requirements for RFID systems were described in the literature [35].

• Anonymity The most important information of a tag which need to be kept secure is tag’s identifier. This identifier is used in the authentication procedures between the tag and the server. Disclosure the tag’s identity makes the RFID system vulnerable to various attacks including cloning attack and tracking attack. Thus, it is needed for a RFID system to provide the tag anonymity.

• Location privacy In a RFID system, the location of users should be kept private as well as tags’ identifier. Location privacy means that, an adversary cannot distinguish two messages sent from a particular tag. This property guarantees that the adversary cannot track or monitor the tags.

• Mutual authentication This property means that the tags and the legal reader/server can successfully authorize each other. In the other words, an attacker cannot masquerade as a legal tag or the reader/server.

• Forward privacy This property means that, an adversary who compromises a tag and obtains the stored data in the tag’s memory cannot trace the tag through past conversations the tag involved in.

• Resistant to replay attack In a replay attack, an adversary who eavesdropped and captured the conversation between a tag and the server replays the obtained messages to the legitimate destination as being authentic. It is necessary for a RFID system to resist this attack.

3 Review of Chou’s scheme

There are two roles: server/reader and tag in Chou’s RFID system. The server is used to stand for server/reader and the communication between the server and tag is assumed to be insecure. Chou’s system consists of two phases: setup phase and authentication phase. The notations used to describe the system are listed in Table 1.

Table 1 Notations

3.1 Setup phase

In this phase, the server chooses a random number $y \in \mathbb {Z}_{q}$ as its private key and computes $Y =yP$ as its public key. It also chooses a random point $X_{i} \in \mathbb {G}$ as the identifier of $i$th tag and then stores each tag’s identifier and related information in its database, where the information includes the name of the tag and production number, and so on. Finally, the server stores {$X_{i}$, $Y$, $P$} in each tag’s memory.

3.2 Authentication phase

When interrogating a set of tags, the server broadcasts a random point. Each tag in the range of the interrogation signal performs the authentication protocol shown in Fig. 1 as follows:

• Step 1: The server chooses a random integer $r \in \mathbb {Z}_{q}$, computes $C_{0} = rY$ and broadcasts interrogation message $C_{0}$ to the Tag$_{i}$.

  Fig. 1

  

  Chou’s RFID mutual-authentication scheme

• Step 2: On receiving the interrogation, Tag$_{i}$ picks a random integer $k \in \mathbb {Z}_{q}$ and computes $K = kP$ and $C_{1} = kC_{0}$. Tag$_{i}$ then sets a register $R$ as $K + K$ and computes $C_{2} = X_{i} + R$ and $C_{3} = h(X_{i}, K)$. Then Tag$_{i}$ sends {$C_{1}$, $C_{2}$, $C_{3}$} to the server.

• Step 3: On receiving the message {$C_{1}$, $C_{2}$, $C_{3}$}, the server extracts $K^{\prime } = y ^{-1}r^{-1}C_{1}$ and computes candidate tag identifier $X^{\prime } = C_{2} - 2K^{\prime }$. The server then computes a hash value, $h(X^{\prime }, K^{\prime })$ and compares it with the received $C_{3}$. If they are equal, the server directly fetches $X^{\prime }$ from its database. If succeeds, the Tag$_{i}$’s identity is authenticated, and the server will authenticate itself to the Tag$_{i}$ by making a hash value $C_{4} = h(X_{i}, 3K^{\prime })$. If the candidate $X^{\prime }$ is not found in the server’s database, the server sets $C_{4}$ as a random integer $u$ to prevent possible location privacy leakage. Finally, the server returns $C_{4}$ to the Tag$_{i}$.

• Step 4: On receiving $C_{4}$, the Tag$_{i}$ increments the register $R$ by $K$ (now the value in register $R$ is $3K$) and computes a hash value $h(X_{i}, R)$. Then Tag$_{i}$ compares the hash result with the received $C_{4}$. If they are equal, Tag$_{i}$ believes that the counterpart is the true server.

4 Weaknesses of Chou’s scheme

4.1 Lack of tag privacy

Tag privacy relies on the inability of the adversary to learn the tag’s identifier $X_{i}$. However, the tag’s identifier can easily be obtained from the tag in Chou’s scheme, without physical attacks. To do so, the adversary $\mathcal {A}$ performs the following steps with Tag$_{i}$ as shown in Fig. 2):

• Step 1: The adversary $\mathcal {A}$ generates and sends the message $C_{0} = P$ to the Tag$_{i}$.

  Fig. 2

  

  Breaking the privacy of Chou’s scheme

• Step 2: On receiving the interrogation, Tag$_{i}$ picks a random integer $k \in \mathbb {Z}_{q}$ and computes $K = kP$ and

  $$\begin{aligned} C_{1} = kC_{0} = kP =K. \end{aligned}$$

  Tag$_{i}$ then sets a register $R$ as $K + K$ and computes

  $$\begin{aligned} C_{2}&= X_{i} + R = X_{i} + 2K \\ C_{3}&= h(X_{i}, K). \end{aligned}$$

  Then Tag$_{i}$ sends {$C_{1}$, $C_{2}$, $C_{3}$} to the server.

• Step 3: The adversary $\mathcal {A}$ intercepts the message {$C_{1}$, $C_{2}$, $C_{3}$}. Since $C_{1} = K$ and $C_{2} = X_{i} + 2K$, the adversary $\mathcal {A}$ can obtain the Tag$_{i}$’s identifier $X_{i}$ as follows:

  $$\begin{aligned} C_{2} - 2C_{1}&= (X_{i} + 2K) - 2K \\&= X_{i}. \end{aligned}$$

4.2 Lack of forward privacy

Forward privacy relies on the inability of the adversary to track Tag$_{i}$ by knowing the identifier $X_{i}$. Chou’s scheme obviously lacks forward privacy. This is because when an adversary performs above-mentioned steps and obtains the identifier $X_{i}$ of a specific tag Tag$_{i}$, he/she can use this $X_{i}$ to determine whether a past conversation, {$C^{*}_{0}$, $C^{*}_{1}$, $C^{*}_{2}$, $C^{*}_{3}$}, belongs to the specific tag by computing $K^{*} = 2^{-1}(C^{*}_{2} - X_{i})$, and evaluating the equation $h(X_{i}, K^{*}) ?= C^{*}_{2}$. Therefore, Chou’s scheme is vulnerable to location tracking attacks.

4.3 Lack of mutual authentication

After obtaining the Tag$_{i}$’s identifier $X_{i}$, the adversary $\mathcal {A}$ can impersonate not only Tag$_{i}$ but also the server. To impersonate Tag$_{i}$, the adversary $\mathcal {A}$ performs same as the actual tag because he/she know the secret identifier $X_{i}$. To impersonate the server, the adversary $\mathcal {A}$ can continues the attack described in Sect. 4.1 by sending $C_{4} = h(X_{i},3C_{1}) = h(X_{i},3K)$ to Tag$_{i}$’s. On receiving $C_{4}$, Tag$_{i}$’s compares it with $h(X_{i},3K)$, and accepts it because they are equal. Therefore, the adversary $\mathcal {A}$ have succeeded to masquerade as the legal server. Therefore, Chou’s protocol does not achieve tag authentication, server authentication, and mutual authentication.

5 Our improved scheme

To solve the security problems of RFID authentication protocols, we propose an improved ECC-based protocol.

5.1 Protocol description

When interrogating a set of tags, the server broadcasts a random point. Each tag in the range of the interrogation signal performs the authentication protocol shown in Fig. 3 as follows:

• Step 1: The server chooses a random integer $r \in \mathbb {Z}_{q}$, computes

  $$\begin{aligned} C_{0} = rP, \end{aligned}$$

  (1)

  and broadcasts interrogation message $C_{0}$ to the Tag$_{i}$.

  Fig. 3

  

  Improved RFID mutual-authentication scheme

• Step 2: On receiving the interrogation message $C_{0}$, Tag$_{i}$ picks a random integer $k \in \mathbb {Z}_{q}$ and computes

  $$\begin{aligned} K&= kP, \end{aligned}$$

  (2)
  $$\begin{aligned} C_{1}&= kY, \end{aligned}$$

  (3)
  $$\begin{aligned} C_{2}&= X_{i} + h(C_{0},C_{1},K). \end{aligned}$$

  (4)

  Tag$_{i}$ then sends {$C_{1}$, $C_{2}$} to the server.

• Step 3: On receiving the message {$C_{1}$, $C_{2}$}, the server extracts

  $$\begin{aligned} K^\prime = y ^{-1}C_{1} \end{aligned}$$

  (5)

  and computes candidate tag identifier

  $$\begin{aligned} X^\prime _{i} = C_{2} - h(C_{0},C_{1},K^\prime ). \end{aligned}$$

  (6)

  The server then directly fetches $X^\prime _{i}$ from its database. If succeeds, the server makes a hash value

  $$\begin{aligned} C_{3} = h(X^\prime _{i}, K^\prime ). \end{aligned}$$

  (7)

  Finally, the server returns $C_{3}$ to the Tag$_{i}$.

• Step 4: On receiving $C_{3}$, the Tag$_{i}$ checks if

  $$\begin{aligned} h(X_{i}, K) ?= C_{3}. \end{aligned}$$

  (8)

  If it holds, Tag$_{i}$ believes that the counterpart is the true server.

6 Security analysis of our improved protocol

In this section, we prove the correctness and the privacy of the improved authentication RFID scheme in the random oracle model.

6.1 Security model of RFID authentication protocols

6.1.1 Participants

A RFID authentication protocol is run in a network of a number of interconnected participants where each participant is either a tag $T \in \mathcal {T}$ or a trusted server $S \in \mathcal {S}$. The set $\mathcal {S}$ is assumed to involve only a single server for simplicity. Each of the participants may have several instances called oracles involved in distinct executions of the protocol $\Pi$. We refer to $i$th instance of $T$ (resp. $S$) in a session as $\Pi ^{i}_{T}$ (resp. $\Pi ^{i}_{S}$). Every instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$) has a partner identifier $pid^{i}_{T}$ (resp:$pid^{j}_{S}$), a session identifier $sid^{i}_{T}$ (resp:$sid^{j}_{S}$), and an output decision $output^{i}_{T}$ (resp:$output^{j}_{S}$). $pid^{i}_{T}$ (resp:$pid^{j}_{S}$) denotes the set of the identities that are involved in this instance. $sid^{i}_{T}$ (resp:$sid^{j}_{S}$) denotes the flows that are sent and received by the instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$). $output^{i}_{T}$ (resp:$output^{j}_{S}$) is either $Accept$ or $Reject$; if the instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$) feels the protocol has been normally executed outputs $Accept$, otherwise it outputs $Reject$.

Definition 4

(Accepted Instance) An instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{i}_{S}$) is said to be Accepted if and only if it holds (1) a session identifier $sid^{i}_{T}$ (resp:$sid^{j}_{S}$), (2) a partner identifier $pid^{i}_{T}$ (resp:$pid^{j}_{S}$), and (3) an output decision $output^{i}_{T} = Accept$ (resp:$output^{j}_{S} = Accept$).

Definition 5

(Partnered Instances) Two instances $\Pi ^{i}_{T}$ and $\Pi ^{j}_{S}$ are partners if and only if: (1) $pid^{i}_{T} = pid^{j}_{S}$; (2) $sid^{i}_{T} = sid^{j}_{S}$.

6.1.2 Long-lived keys

Each tag $T \in \mathcal {T}$ holds a secret identifier $X_{T}$. The server $S$ holds a vector $\langle X_{T} \rangle _{T \in \mathcal {T}}$ with an entry for each tag, and a public/privat key pair $\langle y_{S},Y_{S}=y_{S}P \rangle$.

6.1.3 Adversary model

The communication network is assumed to be fully controlled by an adversary $\mathcal {A}$, which schedules and mediates the sessions among all the parties. The adversary $\mathcal {A}$ is allowed to issue the following queries in any order:

• Execute($\Pi ^{i}_{T}$, $\Pi ^{j}_{S}$): This query models passive attacks in which the attacker eavesdrops on honest executions among the tag instance $\Pi ^{i}_{T}$ and the trusted server instance $\Pi ^{j}_{S}$. The output of this query consists of the messages that were exchanged during the honest execution of the protocol.

• Send($\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$), $m$): The adversary makes this query to intercept a message and then modify it, create a new one, or simply forward it to the instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$). The output of this query is the message that the instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$) would generate upon receipt of message $m$. Additionally, the adversary is allowed to initiate the protocol between the tag $T$ and the server $S$ by invoking Send($\Pi ^{i}_{T}$, ($\Pi ^{i}_{S}$, $Start$)) (resp. Send($\Pi ^{i}_{S}$, ($\Pi ^{i}_{T}$, $Start$))).

• Corrupt($T$): This query returns to the adversary the secret identifier $X_{T}$ of the tag $T$.

• Test($T$): Only one query of this form is allowed to be made by the adversary to an uncorrupted $T$. To respond to this query, a random bit $b \in \{0,1\}$ is selected. If $b = 1$, then a Execute($\Pi ^{i}_{T}$, $\Pi ^{j}_{S}$) query is made and the messages that were exchanged during the honest execution of the protocol are respond to the adversary. Otherwise, uniformly chosen random values are returned.

6.1.4 Untraceable privacy

To model the untraceable privacy of an authentication RFID protocol, a game between an adversary $\mathcal {A}$ and a challenger $\mathcal {C}$ as follows:

• Learning Phase: $\mathcal {A}$ can issue any Execute, Send, and Corrupt queries.

• Challenging Phase: In this phase, $\mathcal {A}$ issues a Test query on an uncorrupted tag. The Challenger tosses a random bit $b \in \{0, 1\}$ and responses according to the Test query. $\mathcal {A}$ then continues making any Execute, Send, and Corrupt queries.

• Guessing Phase: Eventually, $\mathcal {A}$ outputs a prediction ($b^\prime$) on $b$. $\mathcal {A}$ wins the game if $b^\prime = b$, and we define $\mathcal {A}$’s advantage ($l$ is the security parameter) in winning the game as

  $$\begin{aligned} Adv^{\mathcal {A}}(l) = |\Pr [b^\prime = b]-1/2|. \end{aligned}$$

  (9)

Definition 6

(Negligible Function) A function $\epsilon (l)$ is called negligible (in the parameter $l$) if for every $c \ge 0$ there exists an integer $k_{c} > 0$ such that for all $l > k_{c}$, $\epsilon (l) < l^{-c}$.

Definition 7

(Untraceable Privacy) An authentication RFID protocol has untraceable privacy if:

• 1. Correctness: In the presence of a benign adversary, which faithfully conveys messages, both partner instances $\Pi ^{i}_{T}$ and $\Pi ^{j}_{S}$ output Accept decisions (i.e., $output^{i}_{T} = output^{j}_{S} = Accept$).

• 2. Privacy: For any polynomial time adversary $\mathcal {A}$, the advantage $Adv^{\mathcal {A}} (l)$ in winning the above game is negligible.

6.2 Security proof

Lemma 1

(Correctness) In the presence of a benign adversary, which faithfully conveys messages, both partner instances $\Pi ^{i}_{T}$ and $\Pi ^{j}_{S}$ in the improved authentication RFID scheme output Accept decisions (i.e., $output^{i}_{T} = output^{j}_{S} = Accept$).

Proof

According to the protocol description, the server $S$ accepts tag$_{i}$ if the parameter $X^\prime _{i}$ computed by $S$ is equal to the Tag$_{i}$’s identifier $X_{i}$. This equality holds, since according to the Eqs. (1), (3), (4), (5) and (6):

$$\begin{aligned} X^\prime _{i}&= C_{2} - h(C_{0},C_{1},K^\prime ). \\&= (X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1}ry ^{-1}C_{1}) \\&= (X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1},y ^{-1}kY) \\&= (X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1},y ^{-1}kyP) \\&= (X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1},kP) \\&= (X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1},K) \\&= X_{i}. \end{aligned}$$

Moreover, the server is accepted by Tag$_{i}$ if the Eq. (8) holds. We show that it holds as follows:

$$\begin{aligned} C_{3}&= h(X^\prime _{i}, K^\prime ) \\&= h((C_{2} - h(C_{0},C_{1},K^\prime )),y ^{-1}C_{1}) \\&= h((C_{2} - h(C_{0},C_{1},y ^{-1}C_{1})),y ^{-1}C_{1}) \\&= h((C_{2} - h(C_{0},C_{1},kP)),kP) \\&= h(((X_{i} + h(C_{0},C_{1},K)) - h(C_{0},C_{1},kP)),kP) \\&= h(((X_{i} + h(C_{0},C_{1},kP)) - h(C_{0},C_{1},kP)),kP) \\&= h(X_{i},kP) \\&= h(X_{i},K). \end{aligned}$$

$\square$

Lemma 2

(Privacy) In the improved authentication RFID scheme, for any polynomial time adversary $\mathcal {A}$, the advantage $Adv^{\mathcal {A}} (l)$ in winning the game with a challenger is negligible.

Proof

For a contradiction, assume that there is an adversary $\mathcal {A}$ against our scheme that has a non-negligible advantage $\epsilon (l)$. Using this adversary, we show how to construct a challenger $\mathcal {C}$ that can solve the DDH problem with non-negligible advantage $\epsilon ^\prime (l)$. Suppose the challenger $\mathcal {C}$ is given an instance ($P_{1}=P$, $P_{2}=aP$, $P_{3}=bP$, $P_{4}=cP) \in \mathbb {G}$ of the DDH problem for $a,b,c \in \mathbb {Z}^{*}_{q}$, and is faced to find if $P_{4} = abP$.

Assume that the game between $\mathcal {C}$ and $\mathcal {A}$ involves $n_{t}(l)$ tags where $l$ is the security parameter. The challenger $\mathcal {C}$ works by interacting with the adversary $\mathcal {A}$ as follows:

• Setup Phase: $\mathcal {C}$ simulates the system setup to the adversary $\mathcal {A}$ and defines the system public parameters {$\mathbb {G}$, $P$, $h$}. $\mathcal {C}$ then sets the public key of the server as $Y=P_{2} = aP$ which is the input of DDH problem and gives it to $\mathcal {A}$; hence $\mathcal {C}$ does not know the long-term private key of the server. $\mathcal {C}$ then randomly chooses $I \in \{1,\ldots ,n_{t}(l)\}$ to assign Tag$_{I}$ as the target of Test query.

• Learning Phase: $\mathcal {A}$ can issue any Execute, Send, and Corrupt queries.

• Execute($\Pi ^{i}_{T}$, $\Pi ^{j}_{S}$): $\mathcal {C}$ returns the tuple {$C_{0}$, $C_{1}$, $C_{2}$, $C_{3}$} to $\mathcal {A}$, which are the exchanged message between to instances $\Pi ^{i}_{T}$ and $\Pi ^{j}_{S}$.

• Send($\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$), $m$): $\mathcal {C}$ returns to the adversary the message that the instance $\Pi ^{i}_{T}$ (resp. $\Pi ^{j}_{S}$) would generate upon receipt of message $m$.

• Corrupt(Tag$_{t}$): $\mathcal {C}$ returns to the adversary the secret identifier $X_{t}$ of Tag$_{t}$.

• Challenging Phase: In this phase, $\mathcal {A}$ issues a Test query on an uncorrupted tag Tag$_{t}$. If Tag$_{t}$ $\ne$ Tag$_{I}$, $\mathcal {C}$ aborts the simulation. Otherwise, $\mathcal {C}$ chooses random numbers $r,s \in \mathbb {Z}_{q}^{*}$ and sets $C_{0} = rP$ and $K =rP$. Since $b$ and $b$ are unknown, $\mathcal {C}$ can not compute the real parameters $C_{1}$ as $abP$, thus it sets $C_{1} = P_{4} =cP$ and computes $C_{2} = X_{I} + h(C_{0},C_{1},K)$ and $C_{3} = sP$. Then, $\mathcal {C}$ returns {$C_{0}$, $C_{1}$, $C_{2}$, $C_{3}$} to $\mathcal {A}$.

• Guessing Phase: Eventually, $\mathcal {A}$ outputs a guess with a non-negligible advantage $\epsilon (l)$ to indicate that whether the received response in the challenging phase is a valid tuple or not. If the guess is YES, then $C_{1} = abP$; if NO, $C_{1} \ne abP$. Therefore, $\mathcal {C}$ can find if $C_{1} = abP$ using $\mathcal {A}$ and resultantly can compute the DDH problem. In the following we compute the success probability of $\mathcal {C}$ to solve DDH problem within this game.

• Success Probability: $\mathcal {C}$ aborts the simulation only if $\mathcal {A}$ issues a Test query on an tag Tag$_{t}$ other than the chosen tag Tag$_{I}$. Therefore, the success probability that $\mathcal {C}$ solves DDH problem is

  $$\begin{aligned} \epsilon ^\prime (l) \ge (\frac{1}{n_{t}(l)}) \epsilon (l), \end{aligned}$$

  which is a non-negligible function.

$\square$

Theorem 1

The improved authentication RFID scheme has untraceable privacy, provided the DDH assumption holds. Specifically, suppose an adversary $\mathcal {A}$ wins the game with non-negligible advantage $\epsilon (l)$. Then there exists a polynomial-time algorithm $\mathcal {C}$ to solve the DDH problem with non-negligible advantage $\epsilon ^\prime (l) \ge (\frac{1}{n_{t}(l)})\epsilon (l)$.

Proof

From Lemma 1 and Lemma 2. $\square$

7 Security and performance comparison

In this section, we evaluate the performance and functionality of our proposed protocol and make comparisons with some related ECC-based RFID authentication protocols. Table 2 shows the performance comparisons of our proposed protocol and some other related protocols. It can be seen that the computation cost of the proposed protocol is same as the Chou’s scheme.

Table 3 lists the security comparisons among our proposed protocol and other related protocols. It demonstrates that our protocol has many excellent features and is more secure than other related protocols.

Table 2 Performance comparison

Table 3 Security comparison

8 Conclusion

In this paper, we briefly reviewed the Chou’s ECC-based RFID authenticated protocol. We Showed that the Chou’s protocol does not satisfy tag (forward) privacy, tag authentication, server authentication, and mutual authentication. As such the protocol was susceptible to impersonation attacks, location tracking attacks and tag cloning attacks. To overcome the security weaknesses, we proposed an improved protocol. In comparison to the related schemes, the proposed scheme not only is secure against well-known cryptographical attacks, but also provides more security features. However, the total computation of the improved protocol seems to be high for a RFID system. Therefore, reducing the computational cast especially for tag side is our future work. It can be achieved by using pre-computing technics.