Boyeon Song (2009) RFID Authentification Protocols using Symmetric Cryptography.
Full text access: Open
Radio Frequency IDentification (RFID) is emerging in a variety of applications as an important technology for identifying and tracking goods and assets. The spread of RFID technology, however, also gives rise to significant user privacy and security issues. One possible solution to these challenges is the use of a privacy-enhancing cryptographic protocol to protect RFID communications. This thesis considers RFID authentication protocols that make use of symmetric cryptography. We first identify the privacy, security and performance requirements for RFID systems. We then review recent related work, and assess the capabilities of previously proposed protocols with respect to the identified privacy, security and performance properties. The thesis makes four main contributions. First, we introduce server impersonation attacks as a novel security threat to RFID protocols. RFID tag memory is generally not tamper-proof, since tag costs must be kept low, and thus it is vulnerable to compromise by physical attacks. We show that such attacks can give rise to desynchronisation between server and tag in a number of existing RFID authentication protocols. We also describe possible countermeasures to this novel class of attacks. Second, we propose a new authentication protocol for RFID systems that provides most of the identified privacy and security features. The new protocol resists tag information leakage, tag location tracking, replay attacks, denial of service attacks and backward traceability. It is also more resistant to forward traceability and server impersonation attacks than previously proposed schemes. The scheme requires less tag-side storage than existing protocols and requires only a moderate level of tag-side computation. Next, we survey the security requirements for RFID tag ownership transfer. In some applications, the bearer of an RFID tag might change, with corresponding changes required for the RFID system infrastructure. We propose novel authentication protocols for tag ownership and authorisation transfer. The proposed protocols satisfy the requirements presented, and have desirable performance characteristics. Finally, we address the issue of scalability in anonymous RFID authentication protocols. Many previously proposed protocols suffer from scalability issues because they require a linear search to identify or authenticate a tag. Some RFID protocols, however, only require constant time for tag identification; unfortunately, all previously proposed schemes of this type have serious shortcomings. We propose a novel RFID pseudonym protocol that takes constant time to authenticate a tag, and meets the identified privacy, security and performance requirements. The proposed scheme also supports tag delegation and ownership transfer in an efficient way.
This is a Published version This version's date is: 16/12/2009 This item is peer reviewed
https://repository.royalholloway.ac.uk/items/f6edcf8a-1c1b-8028-cfba-491f6cf9dd26/1/
Deposited by () on 24-Jun-2010 in Royal Holloway Research Online.Last modified on 15-Dec-2010
[1] S. Aissi, N. Dabbous, and A. R. Prasad. Security for Mobile Networks andPlatforms. Universal Personal Communications. Artech House, Norwood, MA,USA, 2006.
[2] G. Avoine. Cryptography in Radio Frequency Identi cation and Fair ExchangeProtocols. PhD thesis, Ecole Polytechnique Federale de Lausanne (EPFL),Lausanne, Switzerland, December 2005.
[3] G. Avoine, E. Dysli, and P. Oechslin. Reducing time complexity in RFIDsystems. In B. Preneel and S. Tavares, editors, Selected Areas in Cryptography| SAC 2005, volume 3897 of Lecture Notes in Computer Science, pages 291{306, Kingston, Canada, August 2005. Springer-Verlag.
[4] G. Avoine and P. Oechslin. A scalable and provably secure hash based RFIDprotocol. In International Workshop on Pervasive Computing and Communi-cation Security | PerSec 2005, pages 110{114, Kauai Island, Hawaii, USA,March 2005. IEEE Computer Society Press.
[5] H. Bar-El. Introduction to side channel attacks. White paper, Discretix TechnologiesLtd., October 2002.
[6] A. Bondi. Characteristics of scalability and their impact on performance. Inthe 2nd International Workshop on Software and Performance | WOSP 2000,pages 195{203, Ottawa, Ontario, Canada, September 2000. ACM Press.
[7] M. Burmester, B. de Medeiros, and R. Motta. Anonymous RFID authenticationsupporting constant-cost key-lookup against active adversaries. Journal ofApplied Cryptography, 1(2):79{90, 2008.
[8] M. Burmester, T. van Le, and B. de Medeiros. Provably Secure UbiquitousSystems: Universally Composable RFID Authentication Protocols. In the 2ndIEEE/CreateNet International Conference on Security and Privacy for Emerg-ing Areas in Communication Networks | SecureComm 2006, pages 1{9, Baltimore,Maryland, USA, August 2006. IEEE.
[9] S. Cai, Y. Li, T. Li, and R. Deng. Attacks and Improvements to an RFIDMutual Authentication Protocol and its Extensions. In Second ACM Conferenceon Wireless Network Security | WiSec'09, pages 51{58, Zurich, Switzerland,March 2009. ACM Press.
[10] H. Chien and C. Chen. Mutual authentication protocol for RFID conformingto EPC class 1 generation 2 standards. Computer Standards & Interfaces,29(2):254{259, February 2007.
[11] Y. Choi, M. Kim, T. Kim, and H. Kim. Low power implementation of SHA-1algorithm for RFID system. In IEEE Tenth International Symposium on Con-sumer Electronics | ISCE '06, pages 1{5, St.Petersburg, Russia, September2006. IEEE.
[12] I. Damgard and M. stergaard. RFID Security: Tradeo s between Securityand Eciency. Cryptology ePrint Archive, Report 2006/234, 2006.
[13] T. Dimitriou. A lightweight RFID protocol to protect against traceability andcloning attacks. In Conference on Security and Privacy for Emerging Areas inCommunication Networks | SecureComm 2005, pages 59{66, Athens, Greece,September 2005. IEEE.
[14] D. N. Duc, J. Park, H. Lee, and K. Kim. Enhancing security of EPCglobal gen-2 RFID tag against traceability and cloning. In Symposium on Cryptographyand Information Security | SCIS 2006, Hiroshima, Japan, January 2006. TheInstitute of Electronics, Information and Communication Engineers.
[15] EPCglobal. EPC Standard Speci cation, version 1.1 rev. 1.24, April 2004.
[16] EPCglobal. EPCTM Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocols for Communications at 860 MHz { 960 MHz, Version1.2.0, October 2008.
[17] M. Feldhofer. Low-Power Hardware Design of Cryptographic Algorithms forRFID Tags. PhD thesis, Graz University of Technology, Institute for AppliedInformation Processing and Communications (IAIK), Graz, Austria, November2008.
[18] M. Feldhofer and C. Rechberger. A case against currently used hash functions inRFID protocols. In R. Meersman, Z. Tari, and P. Herrero et al., editors, On theMove to Meaningful Internet Systems 2006 | OTM 2006 Workshops, volume4277 of Lecture Notes in Computer Science, pages 372{381. Springer-Verlag,November 2006.
[19] K. Finkenzeller. RFID Handbook: Fundamentals and Applications in Contact-less Smart Cards and Identi cation. Wiley, second edition, 2003.
[20] S. Fouladgar and H. A . An ecient delegation and transfer of ownershipprotocol for RFID tags. In First International EURASIP Workshop on RFIDTechnology, Vienna, Austria, September 2007.
[21] S. Fouladgar and H. A . A simple privacy protecting scheme enabling delegationand ownership transfer for RFID tags. Journal of Communications,2(6):6{13, November 2007.
[22] S. Gar nkel, A. Juels, and R. Pappu. RFID Privacy: An Overview of Problemsand Proposed Solutions. IEEE Security and Privacy, 3(3):34{43, May-June2005.
[23] B. Glover and H. Bhatt. RFID Essentials. O'Reilly, Gravenstein HighwayNorth, Sebastopol, CA, USA.
[24] T. Haver. Security and privacy in RFID applications. Master's thesis, NorwegianUniversity of Science and Technology, Trondheim, Norway, June 2006.
[25] A. Henrici and P. Muller. Hash-based enhancement of location privacy forradio-frequency identi cation devices using varying identi ers. In R. Sandhuand R. Thomas, editors, International Workshop on Pervasive Computing andCommunication Security | PerSec 2004, pages 149{153, Orlando, Florida,USA, March 2004. IEEE Computer Society.
[26] S. Holloway. RFID: An Introduction. Technical report, Microsoft DeveloperNetwork, 2006.
[27] International Organization for Standardisation, Geneve, Switzerland. ISO7498-2: 1989, Information processing systems | Open systems Interconnec-tion | Basic reference model | Part 2: Security arichitecture, 1989.
[28] A. Juels. Minimalist Cryptography for Low-Cost RFID Tags. In C. Blundo andS. Cimato, editors, International Conference on Security in CommunicationNetworks | SCN 2004, volume 3352 of Lecture Notes in Computer Science,pages 149{164, Amal , Italia, September 2004. Springer-Verlag.
[29] A. Juels. RFID security and privacy: A research survey. IEEE Journal onSelected Areas in Communications, 24:381{394, February 2006.
[30] A. Juels, D. Molnar, and D.Wagner. Security and Privacy Issues in E-passports.In Conference on Security and Privacy for Emerging Areas in CommunicationsNetworks | SecureComm 2005, pages 74{88, Athens, Greece, September 2005.IEEE.
[31] A. Juels and S. Weis. Authenticating Pervasive Devices with Human Protocols.In Victor Shoup, editor, Advances in Cryptology | CRYPTO'05, volume3126 of Lecture Notes in Computer Science, pages 293{308, Santa Barbara,California, USA, August 2005. Springer-Verlag.
[32] A. Juels and S. Weis. De ning Strong Privacy for RFID. In InternationalConference on Pervasive Computing and Communications | PerCom 2007,pages 342{347, New York City, New York, USA, March 2007. IEEE ComputerSociety Press.
[33] S. Karthikeyan and N. Nesterenko. RFID security without extensive cryptography.In Workshop on Security of Ad Hoc and Sensor Networks | SASN '05,pages 63{67, Alexandria, Virginia, USA, November 2005. ACM Press.
[34] F. Kerschbaum and A. Sorniotti. RFID-Based Supply Chain Partner Authenticationand Key Agreement. In Second ACM Conference on Wireless NetworkSecurity | WiSec'09, pages 41{50, Zurich, Switzerland, March 2009. ACMPress.
[35] J. F. Korsh. Data Structures, Algorithms and Program Style. PWS PublishingCo., Boston, MA, USA, 1986.
[36] J. Landt. Shrouds of time: The history of RFID. 1 October 2001. http://www.rfidconsultation.eu/docs/ficheiros/shrouds_of_time.pdf.[37] A. Laurie. Practical attacks against RFID. Network Security, 2007(9):4{7,September 2007.
[38] Y. Li and X. Ding. Protecting RFID Communications in Supply Chains. In the2nd ACM Symposium on Information, Computer and Communications Security| ASIACCS '07, pages 234{241, Singapore, Republic of Singapore, 2007. ACMPress.
[39] I. Liersch. Electronic passports | from secure speci cations to secure implementations.Elsevier Information Security Technical Report, 14(2):96{100, May2009.
[40] C. Lim and T. Korkishko. mCrypton | A Lightweight Block Cipher For Securityof Low-Cost RFID Tags and Sensors. In J. Song, T. Kwon, and M. Yung,editors, Workshop on Information Security Applications | WISA'05, volume3786 of Lecture Notes in Computer Science, pages 243{258, Jeju Island, SouthKorea, August 2005. Springer-Verlag.
[41] C. Lim and T. Kwon. Strong and robust RFID authentication enabling perfectownership transfer. In P. Ning, S. Qing, and N. Li, editors, Conferenceon Information and Communications Security | ICICS '06, volume 4307 ofLecture Notes in Computer Science, pages 1{20, Raleigh, North Carolina, USA,December 2006. Springer-Verlag.
[42] K. Mayes, K. Markantonakis, and G. Hancke. Transport ticketing security andfraud controls. Elsevier Information Security Technical Report, 14(2):87{95,May 2009.
[43] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of AppliedCryptography, volume 6 of Discrete Mathematics and Its Applications. CRCPress, 1996.
[44] C. J. Mitchell. Cryptography for mobile security. In C. J. Mitchell, editor,Security for Mobility, IET Telecommunications, chapter 1, pages 3{10. TheInstitution of Engineering and Technology, December 2003.
[45] D. Molnar, A. Soppera, and D. Wagner. A scalable, delegatable pseudonymprotocol enabling ownership transfer of RFID tags. In B. Preneel and S. Tavares,editors, Selected Areas in Cryptography | SAC 2005, volume 3897 of LectureNotes in Computer Science, pages 276{290, Kingston, Canada, August 2005.Springer-Verlag.
[46] D. Molnar and D. Wagner. Privacy and security in library RFID: Issues, practices,and architectures. In B. P tzmann and P. Liu, editors, Conference onComputer and Communications Security | ACM CCS, pages 210{219, Washington,DC, USA, October 2004. ACM Press.[47] P. Najera and J. Lopez. RFID: Technological Issues and Privacy Concerns.In A. Acquisti, S. Gritzalis, C. Lambrinoudakis, and S. di Vimercati, editors,Digital Privacy: Theory, Technologies and Practices, chapter 14, pages 285{306.Taylor & Francis Group, 2008.
[48] D. W. Nance and T. L. Naps. Introduction to Computer Science: Program-ming, Problem Solving and Data Structures. West Publishing Company, secondedition, 1992.
[49] M. Ohkubo, K. Suzki, and S. Kinoshita. Cryptographic approach to \privacyfriendly"tags. In RFID Privacy Workshop, MIT, MA, USA, November 2003.http://www.rfidprivacy.us/2003/agenda.php.
[50] K. Osaka, T. Takagi, K. Yamazaki, and O. Takahashi. An ecient and secureRFID security method with ownership transfer. In Y. Wang, Y. Cheung, andH. Liu, editors, Computational Intelligence and Security | CIS 2006, volume4456 of Lecture Notes in Computer Science, pages 778{787. Springer-Verlag,September 2006.
[51] K. Oua and R. C.-W. Phan. Traceable Privacy of Recent Provably-SecureRFID Protocols. In S.M. Bellovin, R. Gennaro, A. Keromytis, and M. Yung,editors, 6th International Conference on Applied Cryptography and NetworkSecurity | ACNS 2008, volume 5037 of Lecture Notes in Computer Science,pages 479{489, New York City, New York, USA, June 2008. Springer-Verlag.
[52] P. Peris-Lopez, J. Hernandez-Castro, J. Estevez-Tapiador, and A. Ribagorda.Cryptanalysis of a novel authentication protocol conforming to EPC-C1G2 standard.Computer Standards & Interfaces, 31(2):372{380, 2009.
[53] P. Peris-Lopez, J. C. Hernandez-Castro, J. M. Estevez-Tapiador, and A. Ribagorda.An ecient authentication protocol for RFID systems resistant to activeattacks. In M. K. Denko, C. Shih, K. Li, S. Tsao, Q. Zeng, S. Park, Y. Ko,S. Hung, and J. Park, editors, Emerging Directions in Embedded and Ubiqui-tous Computing | EUC 2007 Workshops: SecUbiq, volume 4809 of LectureNotes in Computer Science, pages 781{794, Taipei, Taiwan, December 2007.Springer-Verlag.
[54] R. D. Pietro and R. Molva. Information con nement, privacy, and security inRFID systems. In J. Biskup and J. Lopez, editors, European Symposium Re-search Computer Security | ESORICS 2007, volume 4734 of Lecture Notesin Computer Science, pages 187{202, Dresden, Germany, September 2007.Springer-Verlag.
[55] N. Pramstaller, C. Rechberger, and V. Rijmen. A compact FPGA implementationof the hash function Whirlpool. In ACM/SIGDA 14th InternationalSymposium on Field Programmable Gate Arrays | FPGA'06, pages 159{166,New York, 2006. ACM Press.
[56] B. Preneel et al. Final report of European project IST-1999-12324: New Europeanschemes for signatures, integrity, and encryption. http://www.cosic.esat.kuleuven.be/nessie/, April 2004.
[57] M. Rieback, B. Crispo, and A. Tanenbaum. The Evolution of RFID Security.IEEE Pervasive Computing, 5(1):62{69, January{March 2006.
[58] R. Roman, C. Alcaraz, and J. Lopez. A survey of cryptographic primitivesand implementations for hardware-constrained sensor network nodes. MobileNetworks and Applications, 12(4):231{244, 2007.
[59] J. Saito, K. Imamoto, and K. Sakurai. Reassignment Scheme of an RFID Tag'sKey for Owner Transfer. In T. Enokido, L. Yan, B. Xiao, D. Kim, Y. Dai, andL.T. Yang, editors, Emerging Directions in Embedded and Ubiquitous Com-puting | EUC 2005 Workshops, volume 3823 of Lecture Notes in ComputerScience, pages 1303{1312. Springer-Verlag, November 2005.
[60] B. Schneier. Applied Cryptography: Protocols, Algorithems, and Source Codein C. John Wiley & Sons, Inc., New York, NY, USA, 1996.
[61] A. Shamir. SQUASH | A New MAC with Provable Security Properties forHighly Constrained Devices Such as RFID Tags. In K. Nyberg, editor, Fast Soft-ware Encryption: 15th International Workshop | FSE 2008, Revised SelectedPapers, volume 5086 of Lecture Notes in Computer Science, pages 144{157,Lausanne, Switzerland, February 2008. Springer-Verlag.
[62] W. Shieh and J. Wang. Ecient remote mutual authentication and key agreement.Computer & Security, 25(1):72{77, 2006.
[63] B. Song. RFID Tag Ownership Transfer. In Workshop on RFID Security |RFIDSec 08, Budapest, Hungary, July 2008.
[64] B. Song. Server Impersonation Attacks on RFID Protocols. In Second Inter-national Conference on Mobile Ubiquitous Computing, Systems, Services andTechnologies | UBICOMM 08, pages 50{55, Valencia, Spain, October 2008.IEEE Computer Society.
[65] B. Song and C. J. Mitchell. RFID authentication protocol for low-cost tags.In V. D. Gligor, J. Hubaux, and R. Poovendran, editors, ACM Conference onWireless Network Security | WiSec '08, pages 140{147, Alexandria, Virginia,USA, April 2008. ACM Press.
[66] B. Song and C. J. Mitchell. Scalable RFID Pseudonym Protocol. In 3rd Interna-tional Conference on Network & System Security | NSS 2009, pages 216{224,Gold Coast, Queensland, Australia, October 2009. IEEE Computer Society.
[67] B. Song and C. J. Mitchell. Scalable RFID Security Protocols supporting TagOwnership Transfer. Computer Communications, submitted, 2009.
[68] W. Stallings. Cryptography and Netwrok Security: Principles and Practice.Prentice Hall, Upper Saddle River, New Jersey, second edition, 1999.
[69] D. Stinson. Cryptography: Theory and Practice. CRC Press, Boca Raton,Florida, second edition, 2002.
[70] H. Stockman. Communication by means of reected power. Proceedings of TheInstitute of Radio Engineers, 36(10):1196{1204, October 1948.
[71] F. Thornton, B. Haines, A. M. Das, H. Bhargava, A. Campbell, and J. Kleinschmidt.RFID Security. Syngress, Massachusetts, USA, 2006.
[72] G. Tsudik. YA-TRAP: Yet another trivial RFID authentication protocol. InFourth IEEE Annual Conference on Pervasive Computing and Communications| PerCom 2006, pages 640{643, Pisa, Italy, March 2006. IEEE ComputerSociety.
[73] G. Tsudik. A family of dunces: Trivial RFID identi cation and authenticationprotocols. In N. Borisov and P. Golle, editors, Privacy Enhancing Technologies,7th International Symposium | PET 2007, volume 4776 of Lecture Notes inComputer Science, pages 45{61, Ottawa, Canada, June 2007. Springer-Verlag,Berlin.
[74] Istvan Vajda and Levente Buttyan. Lightweight authentication protocols forlow-cost RFID tags. In Second Workshop on Security in Ubiquitous Computing| Ubicomp 2003, Seattle, WA, USA, October 2003.
[75] T. van Deursen and S. Radomirovic. Attacks on RFID Protocols. CryptologyePrint Archive, Report 2008/310, July 2008.
[76] T. van Le, M. Burmester, and B. de Medeiros. Universally composableand forward-secure RFID authentication and authenticated key exchange. InR. Deng and P. Samarati, editors, ACM Symposium on information, Computerand Communications Security | ASIACCS '07, pages 242{252, New York, NY,USA, March 2007. ACM Press.
[77] S. Vaudenay. On Privacy Models for RFID. In K. Kurosawa, editor, Advancesin Cryptology | Asiacrypt 2007, volume 4833 of Lecture Notes in ComputerScience, pages 68{87, Kuching, Malaysia, December 2007. Springer-Verlag.
[78] R. D. Vines. Wireless Security Essentials: Defending Mobile Systems from DataPiracy. Wiley, August 2002.
[79] S. Weis, S. Sarma, R. Rivest, and D. Engels. Security and privacy aspectsof low-cost radio frequency identi cation systems. In D. Hutter, G. Muller,W. Stephan, and M. Ullmann, editors, International Conference on Security inPervasive Computing | SPC 2003, volume 2802 of Lecture Notes in ComputerScience, pages 201{212, Boppard, Germany, March 2003. Springer-Verlag.
[80] K. Yuksel. Universal hashing for ultra-low-power cryptographic hardware applications.Master's thesis, Dept. of Electronical Engineering, Worcester PolytechnicInstitute, Worcester, MA, USA, 2004.
[81] Y. Zhang and P. Kitsos. Security in RFID and Sensor Networks. AuerbachPublications, April 2009.