Robust, anonymous RFID authentication with constant key-lookup

ABSTRACT

A considerable number of anonymous RFID authentication schemes have been proposed. However, current proposals either do not provide robust security guarantees, or suffer from scalability issues when the number of tags issued by the system is very large. In this paper, we focus on approaches that reconcile these important requirements. In particular, we seek to reduce the complexity of identifying tags by the back-end server in anonymous RFID authentication protocols---what we term the key-lookup problem.

We propose a compiler that transforms a generic RFID authentication protocol (supporting anonymity) into one that achieves the same guarantees with constant key-lookup cost even when the number of tags is very large. This approach uses a lightweight one-way trapdoor function and produces protocols that are suitable for deployment into current tag architectures. We then explore the issue of minimal assumptions required, and show that one-way trapdoor functions are necessary to achieve highly scalable, robustly secure solutions. We then relax the requirement of unlinkable anonymity, and consider scalable solutions that are provably secure and for which the loss of privacy is minimal.

REFERENCES

• 1: Gildas Avoine , Philippe Oechslin, A Scalable and Provably Secure Hash-Based RFID Protocol, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.110-114, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.12]
• 2: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 3: M. Burmester, T. van Le, and B. de Medeiros. Provably secure ubiquitous systems: Universally composable RFID authentication protocols. In Proc. of the 2nd IEEE/CreateNet International Conference on Security and Privacy in Communication Networks (SECURECOMM 2006). IEEE Press, 2006.
• 4: R. Canetti. Studies in Secure Multiparty Computation and Application. PhD thesis, Weizmann Institute of Science, Rehovot 76100, Israel, June 1995.
• 5: R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 13:1:143--202, 2000.
• 6: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 7: Don Coppersmith , Hugo Krawczyk , Yishay Mansour, The shrinking generator, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.22-39, January 1994, Santa Barbara, California, United States
• 8: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 9: Tassos Dimitriou, A Lightweight RFID Protocol to protect against Traceability and Cloning attacks, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.59-66, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.4]
• 10: EPC Global. EPC tag data standards, vs. 1.3. http://www.epcglobalinc.org/standards/EPCglobal_Tag_Data_Standard_TDS_Version_1.3.pdf.
• 11: M. Feldhofer, S. Dominikus, and J. Wolkerstorfer. Strong authentication for RFID systems using the AES algorithm. In Proc. of the Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), volume 3156 of LNCS. Springer, 2004.
• 12: M. Feldhofer, J. Wolkerstorfer, and V. Rijmen. AES implementation on a grain of sand. In IEE Proc. on Information Security, volume 152(1), pages 13--20, 2005.
• 13: Oded Goldreich , Shafi Goldwasser , Silvio Micali, How to construct random functions, Journal of the ACM (JACM), v.33 n.4, p.792-807, Oct. 1986 [doi>10.1145/6490.6503]
• 14: Dirk Henrici , Paul Müller, Hash-based Enhancement of Location Privacy for Radio-Frequency Identification Devices using Varying Identifiers, Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops, p.149, March 14-17, 2004
• 15: A. Juels. Minimalist cryptography for low-cost RFID tags. In Proc. Intern. Conf. on Security in Communication Networks (SCN 2004), volume 3352 of LNCS, pages 149--164. Springer, 2004.
• 16: H. Lee and D. Hong. The tag authentication scheme using self-shrinking generator on rfid system. In Transactions on Engineering, Computing, and Technology, volume 18, pages 52--57, 2006.
• 17: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 18: D. Molnar, A. Soppera, and D. Wagner. A scalable, delegatable pseudonym protocol enabling ownership transfer of RFID tags. In Proc. Workshop on Selected Areas in Cryptography (SAC 2005), volume 3897 of LNCS. Springer, 2006.
• 19: M. Ohkubo, K. Suzuki, and S. Kinoshita. Cryptographic approach to "privacy-friendly" tags. In Proc. RFID Privacy Workshop, 2003.
• 20: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 21: A. Shamir. Squash: A new one-way hash function with provable security properties for highly constrained devices such as RFID tags. In Invited Talk, Internat. Conf. on RFID Security (RFIDSec'07), 2007.
• 22: Sanjay E. Sarma , Stephen A. Weis , Daniel W. Engels, RFID Systems and Security and Privacy Implications, Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.454-469, August 13-15, 2002
• 23: Gene Tsudik, YA-TRAP: Yet Another Trivial RFID Authentication Protocol, Proceedings of the 4th annual IEEE international conference on Pervasive Computing and Communications Workshops, p.640, March 13-17, 2006 [doi>10.1109/PERCOMW.2006.152]
• 24: Tri Van Le , Mike Burmester , Breno de Medeiros, Universally composable and forward-secure RFID authentication and authenticated key exchange, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1229319]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
  C.4 PERFORMANCE OF SYSTEMS

  D. Software
  D.2 SOFTWARE ENGINEERING
  D.4 OPERATING SYSTEMS

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS

General Terms:
Algorithms, Design, Reliability, Security, Theory

Keywords:
RFID, availability, privacy, provably secure protocols, scalability, unlinkability