Universally Composable RFID Identification and Authentication Protocols

ABSTRACT

As the number of RFID applications grows, concerns about their security and privacy become greatly amplified. At the same time, the acutely restricted and cost-sensitive nature of RFID tags rules out simple reuse of traditional security/privacy solutions and calls for a new generation of extremely lightweight identification and authentication protocols.

This article describes a universally composable security framework designed especially for RFID applications. We adopt RFID-specific setup, communication, and concurrency assumptions in a model that guarantees strong security, privacy, and availability properties. In particular, the framework supports modular deployment, which is most appropriate for ubiquitous applications. We also describe a set of simple, efficient, secure, and anonymous (untraceable) RFID identification and authentication protocols that instantiate the proposed framework. These protocols involve minimal interaction between tags and readers and place only a small computational load on the tag, and a light computational burden on the back-end server. We show that our protocols are provably secure within the proposed framework.

REFERENCES

• 1: Anderson, R. 2000. Two remarks on public-key cryptology. In Proceedings of the 4th Annual Conference on Computer and Communications Security(CCS’00).
• 2: Giuseppe Ateniese , Jan Camenisch , Breno de Medeiros, Untraceable RFID tags via insubvertible encryption, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102134]
• 3: 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]
• 4: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 5: Beaver, D. 1991b. Secure multi-party protocols and zero-knowledge proof systems tolerating a faulty minority. J. Crypt. 4, 2, 75--122.
• 6: Donald Beaver , Shafi Goldwasser, Multiparty Computation with Faulty Majority, Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, p.589-590, August 20-24, 1989
• 7: Stephen C. Bono , Matthew Green , Adam Stubblefield , Ari Juels , Aviel D. Rubin , Michael Szydlo, Security analysis of a cryptographically-enabled RFID device, Proceedings of the 14th conference on USENIX Security Symposium, p.1-1, July 31-August 05, 2005, Baltimore, MD
• 8: Mike Burmester , Breno de Medeiros , Rossana Motta, Robust, anonymous RFID authentication with constant key-lookup, Proceedings of the 2008 ACM symposium on Information, computer and communications security, March 18-20, 2008, Tokyo, Japan [doi>10.1145/1368310.1368351]
• 9: Burmester, M., van Le, T., and de Medeiros, B. 2006. Provably secure ubiquitous systems: Universally composable RFID authentication protocols. In Proceedings of the 2nd IEEE/CreateNet International Conference on Security and Privacy in Communication Networks (SECURECOMM’06). IEEE Press.
• 10: Canetti, R. 1995. Studies in secure multiparty computation and application. Ph.D. thesis, Weizmann Institute of Science.
• 11: Canetti, R. 2000. Security and composition of multi-party cryptographic protocols. J. Crypt. 13, 1, 143--202.
• 12: 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
• 13: Ran Canetti , Marc Fischlin, Universally Composable Commitments, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.19-40, August 19-23, 2001
• 14: Canetti, R. and Herzog., J. 2004. Universally composable symbolic analysis of cryptographic protocols (the case of encryption-based mutual authentication and key exchange). Tech. rep. E-print rep. # 2004/334, International Association for Cryptological Research.
• 15: Ran Canetti , Hugo Krawczyk, Universally Composable Notions of Key Exchange and Secure Channels, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.337-351, May 02, 2002
• 16: Ran Canetti , Yehuda Lindell , Rafail Ostrovsky , Amit Sahai, Universally composable two-party and multi-party secure computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509980]
• 17: 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
• 18: EPC Global. EPC tag data standards, vs. 1.3. http://www.epcglobalinc.org/standards/EPCglobal_Tag_Data_Standard_TDS_Version_1.3.pdf.
• 19: Gilbert, H., Rodshaw, M., and Sibert, H. 2005. An active attack against HB+: A provably secure lightweight authentication protocol. Tech. rep., International Association for Cryptological Research.
• 20: Oded Goldreich, Foundations of Cryptography: Volume 1, Cambridge University Press, New York, NY, 2006
• 21: 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]
• 22: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 23: Hell, M., Johansson, T., and Meier, W. 2005. Grain: A stream cipher for constrained environments. Tech. rep. eSTREAM # 2005/010, European Network of Excellence for Cryptology.
• 24: A. Herzberg , H. Krawczyk , G. Tsudik, On Travelling Incognito, Proceedings of the 1994 First Workshop on Mobile Computing Systems and Applications, p.205-211, December 08-09, 1994 [doi>10.1109/WMCSA.1994.29]
• 25: Hofheinz, D., Müller-Quade, J., and Steinwandt, R. 2003. Initiator-resilient universally composable key exchange. In Proceedings of the European Symposium on Research in Computer Security (ESORICS’03). Lecture Notes in Computer Science, vol. 2808, 61--84.
• 26: ISO/IEC. Standard # 18000. RFID air interface standard. http://www.hightechaid.com/standards/18000.htm.
• 27: Juels, A. and Weis, S. A. 2005. Authenticating pervasive devices with human protocols. In Proceedings of the Conference on the Advances in Cryptology (CRYPTO’05). Lecture Notes in Computer Science, vol. 3621, 293.
• 28: Katz, J. and Shin, J. S. 2006. Parallel and concurrent security of the HB and HB+ protocols. In Proceedings of the Conference on the Advances in Cryptology (CRYPTO06).
• 29: Ziv Kfir , Avishai Wool, Picking Virtual Pockets using Relay Attacks on Contactless Smartcard, Proceedings of the First International Conference on Security and Privacy for Emerging Areas in Communications Networks, p.47-58, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.32]
• 30: Peeter Laud, Secrecy types for a simulatable cryptographic library, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102126]
• 31: Lee, H. and Hong, D. 2006. The tag authentication scheme using self-shrinking generator on RFID system. In Proceedings of the World Academy of Science, Engineering and Technology (WASET’06). Vol. 18, 52--57.
• 32: Alexander Maximov, Cryptanalysis of the "Grain" family of stream ciphers, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan [doi>10.1145/1128817.1128859]
• 33: Molnar, D., Soppera, A., and Wagner, D. 2006. A scalable, delegatable pseudonym protocol enabling ownership transfer of RFID tags. In Proceedings of the Workshop on Selected Areas in Cryptography (SAC’05). Lecture Notes in Computer Science, vol. 3897. Springer.
• 34: Network of Excellence within the Information Societies Technology (IST) Programme of the European Commission. Estream: The stream cipher project. http://www.ecrypt.eu.org/stream.
• 35: Oren, Y. and Shamir, A. 2006. Power analysis of RFID tags. http://www.wisdom.weizmann.ac.il/~yossio/rfid/.
• 36: Birgit Pfitzmann , Michael Waidner, Composition and integrity preservation of secure reactive systems, Proceedings of the 7th ACM conference on Computer and communications security, p.245-254, November 01-04, 2000, Athens, Greece [doi>10.1145/352600.352639]
• 37: Birgit Pfitzmann , Michael Waidner, A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.184, May 14-16, 2001
• 38: Siegmund Redl , Matthias Weber , Malcolm Oliphant, GSM and Personal Communications Handbook, Artech House, Inc., Norwood, MA, 1998
• 39: Jason Reid , Juan M. Gonzalez Nieto , Tee Tang , Bouchra Senadji, Detecting relay attacks with timing-based protocols, Proceedings of the 2nd ACM symposium on Information, computer and communications security, March 20-22, 2007, Singapore [doi>10.1145/1229285.1229314]
• 40: 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
• 41: Steiner, J., Neuman, B., and Schiller, J. 1988. Kerberos: An authentication service for open network systems. In Proceedings of the USENIX Technical Conference (USENIX’88). 191--202.
• 42: Chiu C. Tan , Bo Sheng , Qun Li, Severless Search and Authentication Protocols for RFID, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications, p.3-12, March 19-23, 2007 [doi>10.1109/PERCOM.2007.30]
• 43: 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]
• 44: Tsudik, G. 2007. A family of dunces: Trivial RFID identification and authentication protocols. In Privacy Enhancing Technologies. Lecture Notes in Computer Science, vol. 4776. Springer, 45--61.
• 45: 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]
• 46: Andrew C. Yao, Theory and application of trapdoor functions, Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, p.80-91, November 03-05, 1982

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Design, Security, Theory

Keywords:
RFID security, authentication and key-exchange protocols, universal composability