Universally composable and forward-secure RFID authentication and authenticated key exchange

ABSTRACT

Recently, a universally composable framework for RFID authentication protocols providing availability, anonymity, and authenticity was proposed. In this paper we extend that framework to address forward-security issues in the presence of key compromise.We also introduce new, provably secure, and highly practical protocols for anonymous authentication and key-exchange by RFID devices. The new protocols are lightweight, requiring only a pseudo-random bit generator. The new protocols satisfy forward-secure anonymity, authenticity, and availability requirements in the Universal Composability model.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Avoine, G. Security and privacy in RFID systems. http://lasecwww.epf1.ch/~gavoine/rfid/.
	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	Batina, L., Lano, J., Mentens, N., Örs, S. B., Preneel, B., and Verbauwhede, I. Energy, performance, area versus security trade-offs for stream ciphers. In The State of the Art of Stream Ciphers, Workshop Record (2004), ECRYPT.
	5	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
	6	Beaver, D. Secure multi-party protocols and zero-knowledge proof systems tolerating a faulty minority. Journal of Cryptology 4:2 (1991), 75--122.
	7	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
	8	Bono, S. C., Green, M., Stubblefield, A., Rubin, A. J. A. D., and Szydlo, M. Security analysis of a cryptographically-enabled RFID device. In Proc. USENIX Security Symposium (USENIX Security 2005) (2005), USENIX, pp. 1--16.
	9	Burmester, M., Van Le, T., and De Medeiros, B. Provably secure ubiquitous systems: Universally composable RFID authentication protocols. In Proc. of IEEE International Conference on Security and Privacy in Communication Networks (SecureComm). August 2006, Baltimore, USA. ISBN 1-4244-0422-3, IEEE Press.
	10	Canetti, R. Studies in Secure Multiparty Computation and Application. PhD thesis, Weizmann Institute of Science, Rehovot 76100, Israel, June 1995.
	11	Canetti, R. Security and composition of multi-party cryptographic protocols. Journal of Cryptology 13:1 (2000), 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. Universally composable symbolic analysis of cryptographic protocols (the case of encryption-based mutual authentication and key exchange). Tech. Rep. E-print Report # 2004/334, International Association for Cryptological Research, 2004.
	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, August 22-26, 1993
	18	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 (SECURECOMM'05), p.59-66, September 05-09, 2005 [doi>10.1109/SECURECOMM.2005.4]
	19	Gilbert, H., Rodshaw, M., and Sibert, H. An active attack against HB+- a provably secure lightweight authentication protocol. Tech. rep., International Association for Cryptological Research, 2005.
	20	Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
	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	Hell, M., Johansson, T., and Meier, W. Grain - A stream cipher for constrained environments. Tech. Rep. eSTREAM # 2005/010, ECRYPT (European Network of Excellence for Cryptology), 2005.
	23	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
	24	Hofheinz, D., Müller-Quade, J., and Steinwandt, R. Initiator-resilient universally composable key exchange. In Proc. European Symp. on Research in Computer Security (ESORICS 2003) (2003), vol. 2808 of LNCS, Springer, pp. 61--84.
	25	Juels, A. Minimalist cryptography for low-cost RFID tags. In Proc. Intern. Conf. on Security in Communication Networks (SCN 2004) (2004), vol. 3352 of LNCS, Springer, pp. 149--164.
	26	Juels, A., and Weis, S. A. Authenticating pervasive devices with human protocols. In Proc. Advances in Cryptology (CRYPTO 2005) (2005), vol. 3621 of LNCS, Springer, p. 293.
	27	Juels, A., and Weis, S. A. Defining strong privacy for RFID. E-print report 2006/137, International Association for Cryptological Research, 2006.
	28	Katz, J., and S. Shin, J. Parallel and concurrent security of the HB and HB+ protocols. In Proc. Advances in Crypotology (EUROCRYPT 2006) (2006), LNCS, Springer.
	29	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]
	30	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]
	31	Molnar, D., Soppera, A., and Wagner, D. A scalable, delegatable pseudonym protocol enabling ownership transfer of RFID tags. In Proc. Workshop on Selected Areas in Cryptography (SAC 2005) (2006), vol. 3897 of LNCS, Springer.
	32	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.
	33	Ohkubo, M., Suzuki, K., and Kinoshita, S. Cryptographic approach to "privacy-friendly" tags. RFID Privacy Workshop, November 2003.
	34	Oren, Y., and Shamir, A. Power analysis of RFID tags. Appeared in the rump session of Advances in Cryptology, CRYPTO 2006. Available online at http://www.wisdom.weizmann.ac.il/~yossio/rfid/, Weizmann Institute, 2006.
	35	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]
	36	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
	37	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]
	38	Yao, A. C. Theory and application of trapdoor functions. In Proc. IEEE Symp. on Foundations of Computer Science (FOCS 1982) (1982), pp. 80--91.