1 Introduction

Radio frequency identification (RFID) systems, thanks to their low cost and their convenience in identifying an object without physical contact, have found many applications in manufacturing, supply chain management, parking garage management, and inventory control. RFID is also one of the key technologies that facilitate the development of Internet of Things (IoT). An RFID system consist of radio frequency (RF) tags, readers and backend servers, where readers can inquire tags of their identifications and contents by broadcasting an RF signal, and then read or update the corresponding data in backend servers.

The widespread deployment of RFID systems not only enhances the efficiency and convenience in our daily life but also exposes potential security threats and risks either to corporations or individuals. Forging of participated entity (either tag or reader) is one key threat, and disclosure of sensitive data is another. In addition, as the co-related information of tags labeled on products might be utilized to reveal an user’s identity, his location, his movement, and his habits. Therefore, a desirable RFID authentication solution should protect identity privacy (anonymity) and tracking resistance (un-linkability). However, as most popular tags (like Mifare, Suicard, ISO 15693, EPC Gen2 [1]) have cost pressure from the market, they all call for computationally lighter algorithms.

The RFID authentication has been extensively studied like [2–19], and readers are referred to Avoine’s RFID Security and Privacy Lounge [2] for a comprehensive list of related works. Among them, solution based on ECC has recently attracted many researchers’ attention [20–27], owing to Elliptic Curves Cryptography’s (ECC) excellent performance in terms of strong security, smaller key size and lighter computation. Some [20–23] of these schemes achieved only basic authentication functions while others [27] aimed at achieving full-fledged security functions like mutual authentication, anonymity, tracking resistance and denial-of-service (DOS) attack resistance. Liao and Hsiao [27] recently did a critical survey of these ECC-based schemes and proposed a security-improved solution. However, we find one key security weakness of these schemes and it has been neglected: most of the previous schemes only considered passive tracking and fell victim to active tracking attack. An attacker in passive-tracking attacks passively eavesdrops on the transmission to track RFID tags, while an active-tracking attacker would track RFID tags through various active involvements like intercepting, modification, replaying message, and so on. As RFID communicates via wireless radio frequency and the devices are cheap, it is practically feasible to conduct various active attacks, and these threats should be carefully deterred.

In this paper, we describe our active-tracking attacks on several recent publications and then propose our scheme to conquer the weakness. The rest of this paper is organized as follows. In Sect. 2, we introduce some preliminaries of ECC, related hard problems and bilinear pairing computations which will be used to facilitate the attacks. We review several ECC-based schemes in Sect. 3.1, and show the attacks in Sect. 3.2. In Sect. 4, we propose our new scheme, and the security analysis and performance evaluation are conducted in Sect. 5. Finally, Sect. 6 states our conclusion.

2 Preliminaries

In this section, we give some preliminaries on ECC, related hard problems, and bilinear pairing.

Elliptic curves over

GF(p): A non-supersingular elliptic curve E(Fp) is the set of points P = (x, y), for x, y ∊ Z P satisfying the equation \(y^{2} \equiv x^{3} + ax + b \, (\bmod \,p)\), where a, b ∊ Z p are constants such that \(4a^{3} + 27b^{2} \ne 0\,\bmod \,p\), together with the point O called the point at infinity. Two points P = (x 1, y 1) and Q = (x 2, y 2) on the elliptic curve E can be added together using the following rule: if x 2 = x 1 and y 2 = −y 1, then P + Q = O; otherwise, P + Q = (x 3, y 3) where: \(x_{3} = \lambda^{2} - x_{1} - x_{2} \;\bmod \,p\), \(y_{3} = \lambda (x_{1} - x_{3} ) - y_{1} \;\bmod \,p\), and λ = (y 2 − y 1)/(x 2 − x 1) if P ≠ Q or λ = (3x 21  + a)/(2y 1) if P = Q.

Definition 1

The computational elliptic curve Diffie–Hellman problem (ECDHP) [28] is: given an elliptic curve over a finite field F p , a point P ∊ E(F p ) of order q, and points A = aP, B = bP ∊ <P>, find the point C = abP.

Definition 2

The elliptic curve discrete logarithm problem (ECDLP) [28] is: given an elliptic curve over a finite field F p , two points P, Q ∊ E(F p ), find a number k such that Q = kP.

It is believed that both the ECDLP and the ECDHP are hard problems for proper parameter setting, and many security systems have been proposed based on them [28].

Definition 3

(Non-degenerate, bilinear, computable map) [29] Let G 1 and G 2 be cyclic groups of prime order q, where G 1 is an additive group on elliptic curves and G 2 is multiplicative. Let e: G 1 × G 1 → G 2 be a map with the following properties below.

  1. (1)

    Non-degenerate: There exists X,Y∊ G 1 such that e(X, Y) ≠ 1.

  2. (2)

    Bilinear: e(X 1 + X 2, Y) = e(X 1, Y)·e(X 2, Y) and e(X, Y 1 + Y 2) = e(X, Y 1)·e(X, Y 2). Computable: There is an efficient algorithm for evaluating e.

  3. (3)

    Computability: There exist efficient algorithms to compute e(P, Q) for all P, Q ∊ G 1.

3 Security Weaknesses of Several ECC-Based RFID Authentication Schemes

In this section, we review two ECC-based RFID authentication schemes and demonstrate active tracking attacks and other weaknesses of them.

We introduce the notations as follows, and we will omit the mod q operation to simplify the presentation when the context is clear.

E(Fp), P, q: P ∊ E(F p ) is a generator point of a group over E(F p ) of order q.

h(): cryptographic hash function.

T, S: T and S respectively denote the tag and the server.

ID T , ID S : ID T and ID S respectively denote the identity of the tag and that of the server.

x T , x S , P C , P S : x T , x S ∊ Z q * respectively denote the private key of T and that of S. P T  = x T P and P S  = x S P respectively denote their corresponding public keys.

r 1, r 2, r 3, R 1, R 2, R 3: r 1, r 2, r 3∊ Z q * respectively denote ephemeral private keys. R 1 = r 1 P, R 2 = r 2 P, R 3 = r 3 P denote their corresponding public keys.

⊕, ||: ⊕ denotes exclusive OR operation, and || denotes concatenation. Here we abusively use the notation ⊕ between two elliptic curve points to represent (x 1, y 1) ⊕ (x 2, y 2) = (x 1 ⊕ x 2, y 1 ⊕ y 2).

3.1 Attacks on Zhang et al.’s Scheme [21]

3.1.1 Zhang et al.’s Scheme

Initially, tag T owns two private keys x T1, x T2 and two public keys P T1 = x T1, P T2 = x T2, and the server S owns its private key x S and its public key P S  = x S P. The server keeps {x T1, x S , P T1, P T2, P S , P}, and tag T keeps {x T1, x T2, P, P S }.

During authentication process, T and S perform the following steps. Figure 1 depicts the process.

Fig. 1
figure 1

Zheng et al.’s scheme

Full size image
  1. 1.

    S → T: r 2

    The server chooses a random number r 2 ∊  R Z q *, and sends it as a challenge to T.

  2. 2.

    T → S: Y 1, Y 2, v, r 3

    Upon receiving the challenge, T chooses two random numbers r 1, r 3 ∊  R Z q *, validates whether r 2 ≠ 0, and then computes Y 1 = r 1 P, Y 2 = (x T1 + r 1 + r 3)P S and \(v = (r_{1} x_{T1} + r_{2} x_{T2} )\bmod q\).

  3. 3.

    S:

    S first computes P’ T1 = x −1 S Y 2 − Y 1 − r 3 P = (x T1 + r 1 + r 3)P − r 1 P − r 3 P = x T1 P and uses P T1′ to look up a matched entry {x T1, P T1, P T2}. It uses the data from the matched entry to verify whether the equation \(r_{2}^{ - 1} (vP - x_{T1} Y_{1} )\mathop = \limits^{?} P_{T2}\). If the equation holds, then it accepts the tag.

3.1.2 Security Weaknesses

Apparently, the scheme only provided unilateral authentication of tag to server. We now introduce an active-tracking attack as follows. Let Eve be the attacker. She sends the same challenge r 2 to tags it encounters. If the same tag T receives the same challenge r 2 twice, then it will respond with {Y 1 = r 1 P, Y 2 = (x T1 + r 1 + r 3)P S , v = (r 1 x T1 + r 2 x T2), r 3} in one session and {Y 1′ = r 1′P, Y 2′ = (x T1 + r 1′ + r 3′)P S , v′ = (r 1′x T1 + r 2 x T2), r 3′} in the other session, where (r 1, r 3) and (r 1′, r 3′) are respectively the random numbers chosen by T in the two sessions.

Now Eve computes the values Y 1 − Y 1′ = (r 1 − r 1′)P and v − v′ = (r 1 x T1 + r 2 x T2) − (r 1′x T1 + r 2 x T2) = (r 1 − r 1′)x T1. Next, she checks whether the equation \(e(Y_{1} - Y_{1}^{{\prime }} ,P_{T1} )\mathop = \limits^{?} e((v - v^{{\prime }} )P,P)\) holds to validate whether the two sessions came from the same tag T. The above equation should hold if the transcripts came from the same tag T, because e(Y 1 − Y 1′, P T1) = e((r 1 − r 1′)P, x T1 P) = \(e((r_{1} - r_{1}^{{\prime }} )P,P)^{{x_{T1} }} = e((r_{1} - r_{1}^{{\prime }} )x_{T1} P,P) = e((v - v^{{\prime }} )P,P)\). That is, the scheme falls victim to our active-tracking attack.

3.2 Attacks on Liao–Hsiao’s Scheme [27]

3.2.1 Liao–Hsiao’s Scheme

Initially, tag T owns one private key x T and one public key P T  = x T P, and the server S owns its private key x S and its public key P S  = x S P. The server keeps {x T , x S , P T , P S , P}, and tag T keeps {x T , P T , P, P S }.

During the authentication process, T and S perform the following steps. The process is also depicted in Fig. 2.

Fig. 2
figure 2

Liao–Hsiao’s scheme

Full size image
  1. 1.

    S → T: R 2

    The server chooses a random number r 2 ∊  R Z * q , and sends R 2 = r 2 P as a challenge to T.

  2. 2.

    T → S: R 1, Auth T

    Upon receiving the challenge, T chooses one random numbers r 1 ∊  R Z * q , and computes R 1 = r 1 P, TK T1 = r 1 R 2, TK T2 = r 1 P S and Auth T  = P T  + TK T1 + TK T2.

  3. 3.

    S → T: Auth S

    S first computes TK S1 = r 2 R 1, TK S2 = x S R 1 and Auth T  − TK S1 − TK S2 = P T . It uses P T to look up a matched entry in its database. If a matched entry is found, then it accepts the tag and computes Auth S  = x T R 1 + r 2 P T . It sends Auth S to the tag.

  4. 4.

    T:

    The tag checks whether \(Auth_{S} \mathop = \limits^{?} r_{1} P_{T} + x_{T} R_{2}\) holds. If it holds, then the tag accepts the server.

3.2.2 Security Weaknesses

3.2.2.1 Active-Tracking Attack Using Two Sessions

We now introduce an active-tracking attack using two sessions. Let Eve be the attacker. She chooses an integer r 2 and sends the same challenge R 2 = r 2 P to tags. If the same tag T receives the same challenge R 2 twice, then it will respond with {R 1, Auth T  = P T  + TK T1 + TK T2} in one session and {R 1′, Auth T ′ = P T  + TK T1′ + TK T2′} in the other session, where R 1 = r 1 P, R 1′ = r 1′P, TK T1 = r 1 R 2, TK T2 = r 1 P S , TK T1′ = r 1′R 2, TK T2′ = r 1′P S and (r 1, r 1′) are respectively the random numbers chosen by T in the two sessions.

Now Eve computes the values r 2 R 1 = TK T1 and r 2 R 1′ = TK T1′. Next she computes Auth T  − TK T1 = P T  + TK T2, Auth T ′ − TK T1′ = P T  + TK T2′ and \(P_{T} + TK_{{T2}} - \left( {P_{T} + TK_{{T2}}^{\prime } } \right) = TK_{{T2}} - TK_{{T2}}^{\prime } = \left( {r_{1} - r_{1}^{\prime } } \right)P_{S}\). Finally, she checks whether the equation \(e((r_{1} - r_{1}^{{\prime }} )P_{S} ,P)\mathop = \limits^{?} e(R_{1} - R_{1}^{{\prime }} ,P_{S} )\) holds to validate whether the two sessions came from the same tag T. The above equation should hold if the transcripts came from the same tag T, because e((r 1 − r 1)P S , P) = e((r 1 − r 1)x S P, P) = e((r 1 − r 1)P, x S P) = e(R 1 − R 1′, P S ). That is, the scheme falls victim to our active-tracking attack.

3.2.2.2 Passive-Tracking Attack Using Two Sessions

We further show our passive-tracking attack using two sessions, where Eve, instead of actively involving the communications, only passively eavesdrops on the communications. From the eavesdropped data, she gets {Auth S  = x T R 1 + r 2 P T } in one session and {Auth S ′ = x T R 1′ + r 2′P T } in the other. Now she computes Auth S  − Auth S ′ = (x T R 1 + r 2 P T ) − (x T R 1′ + r 2′P T ) = x T (r 1 − r 1′)P + (r 2 − r 2′)P T . Finally, she checks whether the equation \(e(Auth_{S} - Auth_{S}^{\prime } ,P)\mathop = \limits^{?} e(R_{1} - R_{1}^{\prime } ,P_{T} ) \cdot e(R_{2} - R_{2}^{\prime } ,P_{T} )\) holds to validate whether the two sessions came from the same tag T. The equation should hold if they came from the same tag, because \(e\left( {Auth_{S} - Auth_{S}^{\prime } ,P} \right) = e\left( {x_{T} \left( {r_{1} - r_{1}^{\prime } } \right)P + \left( {r_{2} - r_{2}^{\prime } } \right)P_{T} ,P} \right) = e\left( {x_{T} \left( {r_{1} - r_{1}^{\prime } } \right)P,P} \right) \cdot e\left( {\left( {r_{2} - r_{2}^{\prime } } \right)P_{T} ,P} \right) = e\left( {\left( {r_{1} - r_{1}^{\prime } } \right)P,x_{T} P} \right) \cdot e\left( {\left( {r_{2} - r_{2}^{\prime } } \right)P,x_{T} P} \right) = e\left( {R_{1} - R_{1}^{\prime } ,P_{T} } \right) \cdot e\left( {R_{2} - R_{2}^{\prime } ,P_{T} } \right)\). The scheme is vulnerable to the passive-tracking attack.

3.2.2.3 Impersonating a Tag

The scheme authenticates a tag by checking whether the tag can form a valid Auth T  = P T  + TK T1 + TK T2 value. But, we should notice that P T is a public key, and TK T1 = r 1 R 2, TK T2 = r 1 P S could be computed by an attacker using his chosen random number r 1. That is, an attacker can forge valid Auth T . The scheme fails in authenticating a tag.

3.2.2.4 Disclosing the Tag’s identity Using One Active-Involved Session

Now we show how to disclose a tag’s identity using one simple probing. Eve just chooses a random number r 2 ∊  R Z q *, and sends R 2 = r 2 P as a challenge to T. T will respond with R 1 = r 1 P, Auth T  = P T  + TK T1 + TK T2, where TK T1 = r 1 R 2 and TK T2 = r 1 P S . Next she computes Auth T  − r 2 R 1 = P T  + TK T1 + TK T2 − r2R 1 = P T  + TK T2. Now she iteratively picks up one potential tag T′ with public key P T ′ from its database and checks whether the equation \(e(P_{T} + TK_{T2} - P_{{T^{{\prime }} }} ,P)\mathop = \limits^{?} e(R_{1} ,P_{S} )\) holds. The equation should hold, if P T ′ = P T , as e(P T  + TK T2 − P T’, P) = e(TK T2, P) = e(r 1 P S , P) = e(r 1 P, x S P) = e(R 1, P S ). If the verification holds, then the attacker can identify the identity of the tag. The scheme fails in protecting tag’s anonymity.

4 The Proposed Scheme

Now we propose a new scheme to improve the security properties. Initially, tag T owns one private key x T , one public key P T  = x T and one secret key K T  = x T P S  = x T x S P with the server; the server S owns its private key x S and its public key P S  = x S P. The server keeps {x S , P T , P S , P, K T , h()}, and tag T keeps {x T , P T ,P, P S , K T , h()}. Please note the server in our scheme does not keep tag’s secret keys.

T and S perform the following steps during the authentication, and Fig. 3 depicts the process.

Fig. 3
figure 3

New scheme

Full size image
  1. 1.

    S → T: R 2

    The server chooses a random number r 2 ∊  R Z * q , and sends R 2 = r 2 P as a challenge to T.

  2. 2.

    T → S: R 1, Auth T1, Auth T2

    Upon receiving the challenge, T chooses one random number r 1 ∊  R Z * q , and computes R 1 = r 1 P, TK T1 = r 1 R 2, TK T2 = r 1 P S , Auth T1 = (P T  + TK T1) ⊕ h(TK T2), and Auth T2 = h(TK T1 ⊕ K T ).

  3. 3.

    S → T: Auth S

    S first computes TK S1 = r 2 R 1, TK S2 = x S R 1 and (Auth T1 ⊕ h(TK S2)) - TK S1 = P T . It uses P T to look up a matched entry in its database. If a matched entry is found, then it verifies the validity of Auth T2. If the verification succeeds, then it accepts the tag and computes Auth S  = h(TK S1 ⊕ TK S2). It sends Auth S to the tag.

  4. 4.

    T:

    The tag checks whether \(Auth_{S} \mathop { = h}\limits^{?} (TK_{S1} \oplus TK_{S2} )\) holds. If it holds, then the tag accepts the server.

    The final session key could be computed as sess = h(P T , P S , TK S1).

5 Security Analysis and Performance Evaluation

We analyze the security properties of our scheme in Sect. 5.1, and then evaluate the performance in Sect. 5.2.

5.1 Security Analysis

We analyze the security properties of the proposed scheme as follows.

Mutual authentication The authentication of a tag depends on the validity of Auth T2. To generate a valid Auth T2 = h(TK T1 ⊕ K T ), it needs the knowledge of the secret key K T with the fresh, random challenge TK T1. It ensures only a genuine tag can generate the value. The authentication of the server depends on the validity of Auth S  = h(TK S1 ⊕ TK S2), where TK T1 = r 1 R 2 = r 2 R 1 is the ephemeral Diffie–Hellman key depending on tag’s and server’s challenges, and TK T2 = r 1 P S  = x S R 1 requires the server to demonstrate its knowledge of x S . This ensures the authenticity of the server.

Anonymity of the tag Among the transmitted data, only the value Auth T1 = (P T  + TK T1) ⊕ h(TK T2)involves tag-specific public key P T . Auth T1 can be viewed as an encryption using the two keys TK T1 and TK T2, where the computation TK T1 = r 1 R 2 = r 2 R 1 needs either tag’s random secret or the server’s random secret, and the computation of TK T2 = r 1 P S needs either the knowledge of tag’s secret challenge r 1 or the server’s secret key. This ensures that only the genuine server could derive the tag’s public key P T .

Resistance to tracking To track a tag either passively or actively, one needs to link two sessions to the same source or to differentiate one session from others. In our protocol, R 1, R 2 are random and fresh in each session, and the values Auth T2 = h(TK T1 ⊕ K T ), Auth S  = h(TK S1 ⊕ TK S2) are hashing of secret key and the ephemeral Diffie–Hellman (D–H) key TK T1 and TK S2; therefore, an outsider who has no knowledge of (K T , TK S2) cannot infer any clue that whether these values came from any two sessions. The value Auth T1 = (P T  + TK T1) ⊕ h(TK T2) encrypts a tag’s public key P T using the key h(TK T2), where the computation of TK T2 = r 1 P S needs either the knowledge of tag’s secret challenge r 1 or the server’s secret key: it ensures that only the server or the sender itself is capable of calculating the value. This ensures the protection of the transmission P T and the possible linking of any two sessions.

Forward secrecy The session key is defined as sess = h(P T , P S , TK S1), where TK T1 = r 1 R 2 = r 2 R 1 is an ephemeral D–H key. So even assume that the long-term private keys of the tag and the server are compromised some day later, the previous session keys of our scheme are still secure. This ensures the forward secrecy property.

5.2 Performance Evaluation

We make a comparison of the performance of ECC-based schemes in Table 1. First, we specify what kind of authentication a scheme tried to provide: unilateral or mutual. Among those schemes in Table 1, only our scheme and Liao–Hsiao’s scheme aimed at providing mutual authentication. Next, we concern the security properties: vulnerability to passive tracing attack or active tracing attack, disclosing tag’s identity, and impersonation of tag. From the table, we can see that only our scheme can resist all the attacks while others are vulnerable to some of the threats.

Table 1 Summary of comparison among ECC-based RFID authentication
Full size table

Now we discuss the computational cost for a server to identify a tag. Some schemes [20, 21, 27] and our scheme only need to perform few calculations to identify a tag and the number of calculations is independent of the number of potential tags. Here we use O(1) to denote this notation. While the complexity of computation for identifying a tag in other schemes like [22, 23] is proportional to the number of potential tags. Here we use O(n) to denote the notation, where n is the number of tags in the database. Both our scheme and Liao–Hsiao’s mutual authentication scheme are O(1) in this context.

Finally, we evaluate the computational complexity of tag. Here we only count those computations un-negligible but neglect those light computations like exclusive OR and simple field addition. T EM denotes the time complexity of one elliptic curve point multiplication, T EA denotes that for one elliptic curve point addition, T h denotes that for one hash operation, T mul,q denotes that for one multiplication in Field q. Our scheme needs 2T EM  + 1T EA  + 3T h , and Liao–Hsiao’s mutual authentication scheme needs 5T EM  + 3T EA . Apparently, our scheme demands much lighter computation than its mutual ECC-based counterpart [27].

To further assess the computational performance, we evaluate the computational cost under the practical setting from NSA [30] and the algebra equations of elliptic curve operations [31]. The security of ECC with 160-bit key is equivalent to that of RSA with 1024-bit key or D–H algorithm with 1024-bit key. Under the above figures, T mul,p (the time complexity of a field multiplication in Z p , where p is 1024-bit) is 41 times T mul,q (the time complexity of field multiplication in Z q , where q is 160-bit), T EM  ∼= 29T mul,p , and T EM  ∼= 241 T EA , where ∼=  means “roughly equal”. To simplify the comparison and get an insight of the computational performance, we can focus on the number of ECC point multiplication, point addition, modular exponentiation and modular multiplication only because the other operations are not computationally significant. In this simplification, the tag in our scheme needs 2T EM  + T EA  ∼= 58.12T mul,p , the tag in [27] needs 5T EM  + 3T EA  ∼= 145.36T mul,p . Based on these figures, we can get an insight that the tag in our scheme only takes roughly 39 % computational complexity of Liao–Hsiao’s ECC-based scheme [27].

In summary, our scheme owns better performance than other schemes in terms of security, server’s computational performance, and tag’s computational performance.

6 Conclusion

In this paper, we have shown the security weaknesses of Zhang et al.’s scheme and Liao–Hsiao’s scheme, and we highlight that active-tracking attack is one powerful attack that compromises all previous ECC-based scheme. We have proposed a new scheme to conquer the security weaknesses. Compared to Liao–Hsiao’s mutual authentication scheme, our scheme not only improves the security but also needs only 39 % tag’s computational complexity.