Abstract
The security challenges posed by RFID-tag deployments are well-known. In response there is a rich literature on new cryptographic protocols and an on-tag hash function is often assumed by protocol designers. Yet cheap tags pose severe implementation challenges and it is far from clear that a suitable hash function even exists. In this paper we consider the options available, including constructions based around compact block ciphers. While we describe the most compact hash functions available today, our work serves to highlight the difficulties in designing lightweight hash functions and (echoing [17]) we urge caution when routinely appealing to a hash function in an RFID-tag protocol.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
An, Y., Oh, S.: RFID System for User’s Privacy Protection. In: IEEE Asia-Pacific Conference on Communications, pp. 16–519. IEEE Computer Society, Los Alamitos (2005)
Avoine, G., Oechslin, P.: A Scalable and Provably Secure Hash-based RFID Protocol. In: 3rd IEEE Conference on Pervasive Computing and Communications Workshops (PerCom 2005 Workshops), pp. 110–114. IEEE Computer Society, Los Alamitos (2005)
Baretto, P., Rijmen, V.: The Whirlpool Hashing Function, http://paginas.terra.com.br/informatica/-paulobarreto/WhirlpoolPage.html
Biham, E., Dunkelman, O.: A Framework for Iterative Hash Functions - HAIFA. Presented at Second NIST Cryptographic Hash Workshop, August 24-25 (2006), csrc.nist.gov/groups/ST/hash/
Black, J., Rogaway, P., Shrimpton, T.: Black-Box Analysis of the Block-Cipher-Based Hash-Function Constructions from PGV. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 320–335. Springer, Heidelberg (2002)
Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: Present: An Ultra-Lightweight Block Cipher. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 450–466. Springer, Heidelberg (2007)
Rolfes, C., Poschmann, A., Leander, G., Paar, C.: Ultra-Lightweight Implementations for Smart Devices - Security for 1000 Gate Equivalents. In: CARDIS 2008. Springer, Heidelberg (to appear, 2008)
Brown, L., Pieprzyk, J., Seberry, J.: LOKI - A Cryptographic Primitive for Authentication and Secrecy Applications. In: Seberry, J., Pieprzyk, J.P. (eds.) AUSCRYPT 1990. LNCS, vol. 453, pp. 229–236. Springer, Heidelberg (1990)
Chang, D.: A Practical Limit of Security Proof in the Ideal Cipher Model: Possibility of Using the Constant As a Trapdoo. In: Several Double Block Length Hash Functions. IACR Cryptology ePrint Archive, Report 2006/481, http://eprint.iacr.org/2006/481
Coppersmith, D., Pilpel, S., Meyer, C.H., Matyas, S.M., Hyden, M.M., Oseas, J., Brachtl, B., Schilling, M.: Data authentication using modification detection codes based on a public one way encryption function. U.S. Patent No. 4,908,861 (March 13, 1990)
Damgård, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Dean, R.D.: Formal Aspects of Mobile Code Security. PhD thesis, Princeton University (1999)
Dimitriou, T.: A Lightweight RFID Protocol to Protect Against Traceability and Cloning Attacks. In: Proceedings of IEEE International Conference on Security and Privacy of Emerging Areas in Communication Networks (SecureComm 2005), pp. 59–66. IEEE Computer Society, Los Alamitos (2005)
ECRYPT Network of Excellence. The Stream Cipher Project: eSTREAM, http://www.ecrypt.eu.org/stream
Good, T., Chelton, W., Benaissa, M.: Hardware Results for Selected Stream Cipher Candidates. In: SASC 2007 (February 2007), http://www.ecrypt.eu.org/stream/
Feldhofer, M., Dominikus, S., Wolkerstorfer, J.: Strong Authentication for RFID Systems Using the AES Algorithm. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 357–370. Springer, Heidelberg (2004)
Feldhofer, M., Rechberger, C.: A Case Against Currently Used Hash Functions in RFID Protocols. In: Meersman, R., Tari, Z., Herrero, P. (eds.) OTM 2006 Workshops. LNCS, vol. 4277, pp. 372–381. Springer, Heidelberg (2006)
Gao, X., **an, Z., Wang, H., Shen, J., Huang, J., Song, S.: An Approach to Security and Privacy of RFID System for Supply Chain. In: IEEE International Conference on E-Commerce Technology for Dynamic E-Business, pp. 164–168. IEEE Computer Society, Los Alamitos (2004)
Handschuh, H., Knudsen, L.R., Robshaw, M.J.B.: Analysis of SHA-1 in Encryption Mode. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 70–83. Springer, Heidelberg (2001)
Henrici, D., Götze, J., Müller, P.: A Hash-based Pseudonymization Infrastructure for RFID Systems. In: Georgiadis, P., Lopez, J., Gritzalis, S., Marias, G. (eds.) SecPerU 2006, pp. 22–27. IEEE Computer Society Press, Los Alamitos (2006)
Hirose, S.: Provably Secure Double-Block-Length Hash Functions in a Black-Box Model. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol. 3506, pp. 330–342. Springer, Heidelberg (2005)
Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210–225. Springer, Heidelberg (2006)
Hirose, S.: How to Construct Double-Block-Length Hash Functions. In: Second Cryptographic Hash Workshop, Santa Barbara (August 2006)
Hong, D., Sung, J., Hong, S., Lim, J., Lee, S., Koo, B.-S., Lee, C., Chang, D., Lee, J., Jeong, K., Kim, H., Kim, J., Chee, S.: HIGHT: A New Block Cipher Suitable for Low-Resource Device. In: Goubin, L., Matsui, M. (eds.) CHES 2006. LNCS, vol. 4249, pp. 46–59. Springer, Heidelberg (2006)
Joux, A.: Multi-Collisions in Iterated Hash Functions. Application to Cascaded Constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)
Juels, A., Weis, S.A.: Authenticating Pervasive Devices With Human Protocols. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 198–293. Springer, Heidelberg (2005)
Kelsey, J., Schneier, B.: Second Preimages on n-bit Hash Functions for Much Less than 2n Work. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 474–490. Springer, Heidelberg (2005)
Knudsen, L.R., Lai, X.: New Attacks on all Double Block Length Hash Functions of Hash Rate 1, Including the Parallel-DM. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 410–418. Springer, Heidelberg (1995)
Lai, X., Massey, J.L.: Hash Functions Based on Block Ciphers. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 55–70. Springer, Heidelberg (1993)
Lai, X., Waldvogel, C., Hohl, W., Meier, T.: Security of Iterated Hash Functions Based on Block Ciphers. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 379–390. Springer, Heidelberg (1994)
Lee, S., Hwang, Y., Lee, D., Lim, J.: Efficient Authentication for Low-Cost RFID Systems. In: Gervasi, O., Gavrilova, M.L., Kumar, V., Laganá, A., Lee, H.P., Mun, Y., Taniar, D., Tan, C.J.K. (eds.) ICCSA 2005. LNCS, vol. 3480, pp. 619–627. Springer, Heidelberg (2005)
Lim, C., Korkishko, T.: mCrypton - A Lightweight Block Cipher for Security of Low-cost RFID Tags and Sensors. In: Song, J., Kwon, T., Yung, M. (eds.) WISA 2005. LNCS, vol. 3786, pp. 243–258. Springer, Heidelberg (2005)
Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography. CRC Press, Inc., Boca Raton (1996)
Merkle, R.C.: One Way Hash Functions and DES. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 428–446. Springer, Heidelberg (1990)
National Institute of Standards and Technology. FIPS 46-3: Data Encryption Standard (DES) (October 1999), http://csrc.nist.gov
National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard (August 2002), http://csrc.nist.gov
National Institute of Standards and Technology. FIPS 197: Advanced Encryption Standard (AES) (November 2001), http://csrc.nist.gov
National Institute of Standards and Technology. FIPS 198: The Keyed-Hash Message Authentication Code (March 2002), http://csrc.nist.gov
Ohkubo, M., Suzuki, K., Kinoshita, S.: Cryptographic Approach to Privacy-Friendly Tags. In: RFID Privacy Workshop, MIT, Cambridge (2003)
Okeya, K.: Side Channel Attacks Against HMACs Based on Block-Cipher Based Hash Functions. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 432–443. Springer, Heidelberg (2006)
Peyrin, T., Gilbert, H., Muller, F., Robshaw, M.J.B.: Combining Compression Functions and Block Cipher-Based Hash Functions. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 315–331. Springer, Heidelberg (2006)
Poschmann, A., Leander, G., Schramm, K., Paar, C.: New Lightweight DES Variants Suited for RFID Applications. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 196–210. Springer, Heidelberg (2007)
Preneel, B., Bosselaers, A., Govaerts, R., Vandewalle, J.: Collision-Free Hash Functions Based on Block Cipher Algorithms. In: Proceedings 1989 International Carnahan Conference on Security Technology, pp. 203–210. IEEE, Los Alamitos (1989)
Preneel, B.: Ph.D. thesis. Katholieke Universiteit Leuven (1993)
Quisquater, J.-J., Girault, M.: 2n-bit Hash-Functions Using n-bit Symmetric Block Cipher Algorithms. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 102–109. Springer, Heidelberg (1990)
Rivest, R.L.: RFC 1321: The MD5 Message-Digest Algorithm (April 1992 ), http://www.ietf.org/rfc/rfc1321.txt
Rogaway, P.: Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (2004)
Seurin, Y., Peyrin, T.: Security Analysis of Constructions Combining FIL Random Oracles. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol. 4593, pp. 119–136. Springer, Heidelberg (2007)
Shamir, A.: SQUASH - a New MAC With Provable Security Properties for Highly Constrained Devices Such As RFID Tags. In: Nyberg, K. (ed.) FSE 2008, Springer, Heidelberg (to appear, 2008)
Steinberger, J.P.: The Collision Intractability of MDC-2 in the Ideal-Cipher Model. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 34–51. Springer, Heidelberg (2007)
Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 17–36. Springer, Heidelberg (2005)
Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 19–35. Springer, Heidelberg (2005)
Yoshida, H., Watanabe, D., Okeya, K., Kitahara, J., Wu, J., Kucuk, O., Preneel, B.: MAME: A Compression Function With Reduced Hardware Requirements. In: Paillier, P., Verbauwhede, I. (eds.) CHES 2007. LNCS, vol. 4727, pp. 148–165. Springer, Heidelberg (2007)
Yu, Y., Yang, Y., Fan, Y., Min, H.: Security Scheme for RFID Tag. Auto-ID Labs white paper WP-HARDWARE-022, http://www.autoidlabs.org/
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bogdanov, A., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y. (2008). Hash Functions and RFID Tags: Mind the Gap. In: Oswald, E., Rohatgi, P. (eds) Cryptographic Hardware and Embedded Systems – CHES 2008. CHES 2008. Lecture Notes in Computer Science, vol 5154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85053-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-85053-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85052-6
Online ISBN: 978-3-540-85053-3
eBook Packages: Computer ScienceComputer Science (R0)