A low-resource public-key identification scheme for RFID tags and sensor nodes

ABSTRACT

We revisit a public key scheme presented by Shamir in [19] (and simultaneously by Naccache in [15]) and examine its applicability for general-purpose RFID tags in the supply chain. Using a combination of new and established space-saving methods, we present a full-fledged public key identification scheme, which is secure yet highly efficient. The 1024-bit scheme fits completely (including RAM) into 4682 gate equivalents and has a mean current consumption of 14.2μA. The main novelty in our implementation is the replacement of the long pseudo-random sequence, originally stored on 260 bytes of EEPROM in [19], by a reversible stream cipher using less than 300 bits of RAM. We show how our scheme offers tag-to-reader and reader-to-tag authentication and how it can be fit into the existing RFID supply chain infrastructure.

REFERENCES

• 1: D. V. Bailey and A. Juels. Shoehorning security into the EPC tag standard. In R. D. Prisco and M. Yung, editors, Security and Cryptography for Networks, 5th International Conference, SCN 2006, LNCS, volume 4116, pages 303--320. Springer-Verlag GmbH, September 2006. http://snurl.com/wiprBJ.
• 2: A. Bogdanov , L. R. Knudsen , G. Leander , C. Paar , A. Poschmann , M. J. Robshaw , Y. Seurin , C. Vikkelsoe, PRESENT: An Ultra-Lightweight Block Cipher, Proceedings of the 9th international workshop on Cryptographic Hardware and Embedded Systems, September 10-13, 2007, Vienna, Austria [doi>10.1007/978-3-540-74735-2_31]
• 3: M. Feldhofer, S. Dominikus, and J. Wolkerstorfer. Strong authentication for RFID systems using the AES algorithm. In J.-J. Q. Marc Joye, editor, Cryptographic Hardware and Embedded Systems -- CHES 2004: 6th International Workshop, LNCS, volume 3156, pages 357--370. Springer-Verlag GmbH, July 2004. http://snurl.com/wiprDFW.
• 4: M. Feldhofer and C. Rechberger. A Case Against Currently Used Hash Functions in RFID Protocols. In First International OTM Workshop on Information Security (IS'06), Montpellier, France, Oct 30 - Nov 1, 2006. Proceedings, Part I, LNCS, volume 4277, pages 372--381, Graz, Austria, October 2006. http://snurl.com/wiprFR.
• 5: M. Finiasz and S. Vaudenay. When stream cipher analysis meets public-key cryptography. In E. Biham and A. M.Youssef, editors, Selected Areas in Cryptography -- 13th International Workshop, SAC 2006, LNCS, volume 4356, pages 266--284. Springer-Verlag GmbH, September 2007. http://snurl.com/wiprFV.
• 6: J. Furbass, F.; Wolkerstorfer. ECC Processor with Low Die Size for RFID Applications. IEEE International Symposium on Circuits and Systems, 2007, pages 1835--1838, 27-30 May 2007. http://snurl.com/wiprFW.
• 7: Gunnar Gaubatz , Jens-Peter Kaps , Erdinc Ozturk , Berk Sunar, State of the Art in Ultra-Low Power Public Key Cryptography for Wireless Sensor Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications Workshops, p.146-150, March 08-12, 2005 [doi>10.1109/PERCOMW.2005.76]
• 8: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 9: E. Inc. EPC radio-frequency identity protocols class-1 generation-2 UHF RFID protocol for communications at 860 MHz -- 960 MHz, version 1.0.9. Online, September 2005. http://snurl.com/wiprEPC.
• 10: A. M. Johnston. Digitally watermarking RSA moduli. Cryptology ePrint Archive, Report 2001/013. http://snurl.com/wiprJ.
• 11: A. K. Lenstra , H. W. Lenstra, Jr. , M. S. Manasse , J. M. Pollard, The number field sieve, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.564-572, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100295]
• 12: A. K. Lenstra and E. R. Verheul. Selecting cryptographic key sizes. Journal of Cryptology: the journal of the International Association for Cryptologic Research, 14(4):255--293, 2001. http://snurl.com/wiprLV.
• 13: Michael Luby , Charles Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM Journal on Computing, v.17 n.2, p.373-386, April 1988 [doi>10.1137/0217022]
• 14: M. McLoone and M. Robshaw. Public key cryptography and RFID tags. In M. Abe, editor, Topics in Cryptology -- The Cryptographers' Track at the RSA Conference 2007, LNCS, volume 4337, pages 372--384. Springer-Verlag GmbH, February 2007. http://snurl.com/wiprMcLR.
• 15: D. Naccache. Method, sender apparatus and receiver apparatus for modulo operation. European patent application no. 91402958.2, Filed 10/27/1992. http://snurl.com/wiprN.
• 16: K. Nohl and H. Pl¨otz. MIFARE -- little security, despite obscurity. Technical report, 24th Chaos Communication Congress, December 2007. http://snurl.com/wiprNP.
• 17: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 18: S. E. Sarma, S. A. Weis, and D. W. Engels. Security and privacy aspects of low-cost radio frequency identification systems. In First International Conference on Security in Pervasive Computing, 2003. http://snurl.com/wiprSWE.
• 19: A. Shamir. Memory efficient variants of public-key schemes for smart card applications. In A. D. Santis, editor, Advances in Cryptology -- EUROCRYPT '94, LNCS, volume 950, page 445. Springer-Verlag GmbH, January 1995. http://snurl.com/wiprS.
• 20: Adi Shamir, SQUASH --- A New MAC with Provable Security Properties for Highly Constrained Devices Such as RFID Tags, Fast Software Encryption: 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, Springer-Verlag, Berlin, Heidelberg, 2008 [doi>10.1007/978-3-540-71039-4_9]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Standard cells**

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Security

Keywords:
hardware implementation, public-key encryption, rabin encryption, rfid technology