hat case, Reader sends “start left” to Tag A. Then Tag A generates a new random number and calculates. Tag A replies for Reader. Reader generates a new random number as being received. Then Reader challenges Tag

Figure 2. Lv et al.’s tracking attack [10].

B with and. After the challenge messages arriving, Tag B generates a random number as well as computes and

Then Tag B replies and. At this moment, Attacker blocks these messages and forges these messages as

and

.

Then Attacker sends and to Reader. And Reader forwards to Tag A. Once Tag A received, Tag A computes and replies it for Reader. Reader collects grouping proof messages as and forwards to Verifier. Then Verifier verifies

and

successfully. Thus, Attacker can perform a tracking attack which makes the leakage of tag location in the protocol.

3.4. The Revised Protocol Proposed by Lv et al.

Lv et al.’s proposed a revised protocol [10] to resist tracking attack for Batina et al.’s protocol [9]. The revised protocol is shown in Figure 3 and described as follows.

1) Reader sends the messages “start left” to Tag A.

2) Tag A generates a random number ra and computes the corresponding EC point. Then Tag A sends to Reader.

3) Reader generates a random number. Then Read-

Figure 3. Lv et al.’s revised protocol [10].

er sends “start right”, and to challenge Tag B.

4) Tag B generates a random number and computes EC points and

.

Then Tag B responds and to Reader.

5) Reader forward to tag A. Tag A computes and sends to Reader.

6) Then Reader collects the grouping proof and forwards to Verifier.

7) At the last, Verifier verifies

and

.

4. The Impracticability of Lv et al.’s Revised Protocol

Batia et al.’s protocol [9] was designed on the basis of public-key cryptography, therefore public key and private key were involved. Basically, Lv et al.’s protocol [10] was revised from Batia et al.’s protocol [9]. Thus, Lv et al.’s revised protocol [10] should follow the princeple of public-key cryptography. However, we find Lv et al.’s revised protocol [10] has impracticability on the basis of public-key cryptography.

In Lv et al.’s protocol [10], Reader collects the grouping proof and provides for Verifier to verify. Then in accordance with the step (7) in subsection 3.4, Verifier needs to compute and. But based on public-key cryptography, Verifier cannot have tags’ secret keys, and, to execute this verification. In the other case of and, Verifier can get tags’ public keys, and, but cannot get and to compute and. Consequently, this verification cannot be completed. Obviously, Lv et al.’s protocol [10] is impracticable in the public-key cryptography.

5. Proposed Protocol

In this section, we propose a new protocol to satisfy the functionalities of Batia et al.’s protocol [9] and resist the Lv et al.’s attack model [10]. The new protocol is described step by step in subsection 5.1. Then we analyze the security of the protocol and use Lv et al.’s attack [10] to our protocol to show its resistibility for this kind tracing attack.

5.1. Protocol Description

The proposed protocol is described as the following steps and shown as Figure 4.

1) Reader sends the message “start left” to Tag A.

2) Tag A generates a random number and a nonce. Then Tag A computes the corresponding EC point and sends to reader.

3) Reader generates a random number. Then Reader sends “start right”, and to challenge Tag B.

4) Tag B generates a random number rb and a nonce nb. Then Tag B computes EC points and . Then Tag B responds and to Reader.

5) Reader forwards to Tag A. Tag A computes and sends to Reader.

6) Then Reader collects the grouping proof and forwards to Verifier.

7) At the last, Verifier verifies

and

.

5.2. Analysis

In this section, we use Lv et al.’s attack [10] on our protocol and prove the protocol can resist this attack. As the tracking attack shown in Figure 2, the attacker eavesdrops on messages, , , , in Phase I. Then the attacker challenges Tag B by sending and

Figure 4. Proposed protocol.

. In our protocol, Tag B generates a nonce which guarantees every response include a different nonce in

.

Then in the Phase III,

and

Verifier computes

and

Therefore, the verification is failed. Thus our protocol can resist Lv et al.’s attack [10] and keep all secure properties of Batina et al.’s protocol [9].

6. Comparison with Previous Protocols

In this section we compare our protocol with previous ECC-based privacy-preserving grouping proof protocols as Table 1. At first, our protocol and Batina et al.’s protocol [9] are based on public-key cryptosystem that can avoid key management problem and support those applications which have large number of users. Both our protocol and Lv et al.’s protocol [10] can resist the tracking attack of [10] to possess untraceability, but our protocol is based on public-key cryptosystem that means our protocol has the practicability. To get better privacy security in our protocol, we needed additional two nonce involve in the protocol. In the last column of Table 1, we let MEC, MS and AS denote the scale multiplication of elliptic curve point, scale multiplication and the scale addition separately. The protocol computation overhead is shown in this column. And our protocol is only two more scale addition operations than the other protocols.

Table 1. Comparision between ECC-based privacy-preserving grouping proof protocols.

7. Conclusion

In this paper, we have reviewed related papers those are based on ECC and provided the privacy-preserving grouping proof for RFID applications. Lv et al. [10] successfully attacked on Batina et al.’s protocol [9] in untraceability. And then they proposed revised Batina et al.’s protocol [9] to resist the tracing attack. However, we found that Batina et al.’s protocol [9] was designed on the basis of public-key cryptography, but Lv et al.’s revised protocol [10] cannot execute properly in public-key cryptography. During the execution of the Lv et al.’s protocol [10], Verifier cannot get tags’ public keys to implement their verification. Besides, Verifier can get tags’ public keys, but cannot solve the ECDLP from and to get and for the verification. Therefore, Lv et al.’s protocol [10] is impractical. To fix this problem, we propose a practical ECC-based privacypreserving grouping proof protocol on the basis of public-key cryptography. We have proved that our protocol can resist the Lv et al.’s tracking attack [10] to complete the untraceability and inherits the security properties of Batina et al.’s protocol [9]. Therefore our new protocol provide the contributions to give the solutions for the defect of Lv et al.’s protocol [10] and the vulnerability of Batina et al.’s protocol [9] simultaneously.

8. Acknowledgements

The authors would like to thank the National Science Council of the Republic of China, Taiwan for financially supporting this research under Contract No. NSC100- 2221-E-182-040.

REFERENCES

  1. A. Juels, “‘Yoking-Proofs’ for RFID Tags,” Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, Orlando, 14-17 March 2004, pp. 138-143.
  2. W. Diffe and M. E. Hellman, “New Directions in Cryptography,” IEEE Transaction on Information Theory, Vol. 22, No. 6, 1976, pp. 644-654. doi:10.1109/TIT.1976.1055638
  3. S. Vaudenay, “On Privacy Models for RFID,” In: Advances in Cryptology (ASI-ACRYPT’07), Lecture Notes in Computer Science, Vol. 4833, Springer-Verlag, Berlin, 2007, pp. 68-87.
  4. N. Koblitz, “Elliptic Curve Cryptosystems,” Mathematics of Computation, Vol. 48, 1987, pp. 203-209. doi:10.1090/S0025-5718-1987-0866109-5
  5. V. Miller, “Use of Elliptic Curves in Cryptography,” In: Advances in Cryptology CRYPTO85, Lecture Notes in Computer Science, Vol. 218, Springer-Verlag, Berlin, 1986, pp. 417-426.
  6. S. Galbraith, “Mathematics of Public Key Cryptography,” 2011. http://www.math.auckland.ac.nz/~sgal018/crypto-book/crypto-book.html
  7. J. Wolkerstorfer, “Is Elliptic Curve Cryptography Suitable to Secure RFID Tags?” Workshop on RFID and Lightweight Crypto, Graz, 13-15 July 2005.
  8. D. Hein, J. Wolkerstorfer and N. Felber, “ECC Is Ready for RFID—A Proof in Silicon,” Lecture Notes in Computer Science, Vol. 5381, 2008, pp. 401-413.
  9. L. Batina, Y. K. Lee, S. Seys, D. Singelée and I. Verbauwhede, “Short Paper: Privacy Preserving ECC-based Grouping Proofs for RFID,” Lecture Notes in Computer Science, Vol. 6531, 2010, pp. 159-165.
  10. C. Lv, H. Li, J. Ma, B. Niu and H. Jiang, “Security Analysis of a Privacy-Preserving ECC-Based Grouping-Proof Protocol,” Journal of Convergence Information Technology, Vol. 6 No. 3, 2011, pp. 113-119. doi:10.4156/jcit.vol6.issue3.13
  11. T. van Deursen, S. Mauw and S. Radomirovic, “Un-Traceability of RFID Protocols,” Lecture Notes in Computer Science, Vol. 5019, 2008, pp. 1-15. doi:10.1007/978-3-540-79966-5_1
  12. T. van Deursen, “50 Ways to Break RFID Privacy,” IFIP Advances in Information and Communication Technology, Vol. 352, 2011, pp. 192-205. doi:10.1007/978-3-540-79966-5_1
  13. D. Hankerson, A. Menezes and S. Vanstone, “Guide to Elliptic Curve Cryptography,” Springer-Verlag, Berlin, 2004.

NOTES

*Corresponding author.

Journal Menu >>