Abstract
The need for lightweight (that is, compact, low-power, low-energy) cryptographic hash functions has been repeatedly expressed by professionals, notably to implement cryptographic protocols in RFID technology. At the time of writing, however, no algorithm exists that provides satisfactory security and performance. The ongoing SHA-3 Competition will not help, as it concerns general-purpose designs and focuses on software performance. This paper thus proposes a novel design philosophy for lightweight hash functions, based on the sponge construction in order to minimize memory requirements. Inspired by the stream cipher Grain and by the block cipher KATAN (amongst the lightest secure ciphers), we present the hash function family Quark, composed of three instances: u-Quark, d-Quark, and s-Quark. As a sponge construction, Quark can be used for message authentication, stream encryption, or authenticated encryption. Our hardware evaluation shows that Quark compares well to previous tentative lightweight hash functions. For example, our lightest instance u-Quark conjecturally provides at least 64-bit security against all attacks (collisions, multicollisions, distinguishers, etc.), fits in 1379 gate-equivalents, and consumes on average 2.44 μW at 100 kHz in 0.18 μm ASIC. For 112-bit security, we propose s-Quark, which can be implemented with 2296 gate-equivalents with a power consumption of 4.35 μW.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ågren, M. Hell, T. Johansson, W. Meier, A new version of Grain-128 with authentication, in ECRYPT Symmetric Key Encryption Workshop 2011 (2011). Available at http://skew2011.mat.dtu.dk/
J.-P. Aumasson, E. Brier, W. Meier, M. Naya-Plasencia, T. Peyrin, Inside the hypercube, in ACISP, ed. by C. Boyd, J. Manuel González Nieto. LNCS, vol. 5594 (Springer, Berlin, 2009), pp. 202–213
J.-P. Aumasson, I. Dinur, L. Henzen, W. Meier, A. Shamir, Efficient FPGA implementations of highly-dimensional cube testers on the stream cipher Grain-128, in SHARCS (2009)
J.-P. Aumasson, I. Dinur, W. Meier, A. Shamir, Cube testers and key recovery attacks on reduced-round MD6 and Trivium, in FSE, ed. by O. Dunkelman. LNCS, vol. 5665 (Springer, Berlin, 2009), pp. 1–22
J.-P. Aumasson, L. Henzen, W. Meier, M. Naya-Plasencia, Quark: a lightweight hash, in Mangard and Standaert [50] (2010), pp. 1–15
G.V. Bard, N. Courtois, J. Nakahara, P. Sepehrdad, B. Zhang, Algebraic, AIDA/cube and side channel analysis of KATAN family of block ciphers, in Gong and Gupta [39] (2010), pp. 176–196
M. Bellare, T. Ristenpart, Multi-property-preserving hash domain extension and the EMD transform, in ASIACRYPT, ed. by X. Lai, K. Chen. LNCS, vol. 4284 (Springer, Berlin, 2006), pp. 299–314
M. Bernet, L. Henzen, H. Kaeslin, N. Felber, W. Fichtner, Hardware implementations of the SHA-3 candidates Shabal and CubeHash, in CT-MWSCAS (IEEE, New York, 2009)
D.J. Bernstein, CubeHash appendix: complexity of generic attacks. Submission to NIST, 2008. http://cubehash.cr.yp.to/submission/generic.pdf
D.J. Bernstein, CubeHash parameter tweak: 16 times faster, 2009. http://cubehash.cr.yp.to/submission/tweak.pdf
D.J. Bernstein, CubeHash specification (2.B.1). Submission to NIST (Round 2), 2009. http://cubehash.cr.yp.to/submission2/spec.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, RadioGatún, a belt-and-mill hash function, in Second NIST Cryptographic Hash Function Workshop (2006). http://radiogatun.noekeon.org/
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, On the indifferentiability of the sponge construction, in EUROCRYPT, ed. by N.P. Smart. LNCS, vol. 4965 (Springer, Berlin, 2008), pp. 181–197
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Keccak sponge function family main document (version 2.1). Submission to NIST (Round 2), 2010. http://keccak.noekeon.org/Keccak-main-2.1.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Sponge-based pseudo-random number generators, in Mangard and Standaert [50] (2010), pp. 33–47
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, On the security of the keyed sponge construction, in ECRYPT Symmetric Key Encryption Workshop 2011 (2011). Available at http://skew2011.mat.dtu.dk/
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Sponge functions. http://sponge.noekeon.org/SpongeFunctions.pdf
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Duplexing the sponge: single-pass authenticated encryption and other applications. Cryptology ePrint Archive, Report 2011/499, 2011
E. Biham, O. Dunkelman, A framework for iterative hash functions—HAIFA. Cryptology ePrint Archive, Report 2007/278, 2007
A. Biryukov, D. Wagner, Slide attacks, in FSE, ed. by L. Knudsen. LNCS, vol. 1636 (Springer, Berlin, 1999), pp. 245–259
A. Bogdanov, C. Rechberger, A 3-subset meet-in-the-middle attack: cryptanalysis of the lightweight block cipher KTANTAN. Cryptology ePrint Archive, Report 2010/532, 2010
A. Bogdanov, L.R. Knudsen, G. Leander, C. Paar, A. Poschmann, M.J.B. Robshaw, Y. Seurin, C. Vikkelsoe, PRESENT: an ultra-lightweight block cipher, in CHES, ed. by P. Paillier, I. Verbauwhede. LNCS, vol. 4727 (Springer, Berlin, 2007), pp. 450–466
A. Bogdanov, G. Leander, C. Paar, A. Poschmann, M.J.B. Robshaw, Y. Seurin, Hash functions and RFID tags: mind the gap, in CHES, ed. by E. Oswald, P. Rohatgi. LNCS, vol. 5154 (Springer, Berlin, 2008), pp. 283–299
A. Bogdanov, M. Knezevic, G. Leander, D. Toz, K. Varici, I. Verbauwhede, SPONGENT: a lightweight hash function, in CHES, ed. by B. Preneel, T. Takagi. LNCS, vol. 6917 (Springer, Berlin, 2011), pp. 312–325
J.Y. Cho, Linear cryptanalysis of reduced-round PRESENT, in CT-RSA, ed. by J. Pieprzyk. LNCS, vol. 5985 (Springer, Berlin, 2010), pp. 302–317
C. Clavier, K. Gaj (eds.), Cryptographic Hardware and Embedded Systems—CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6–9, 2009, Proceedings. LNCS, vol. 5747 (Springer, Berlin, 2009)
J.-S. Coron, Y. Dodis, C. Malinaud, P. Puniya, Merkle–Damgård revisited: how to construct a hash function, in CRYPTO, ed. by V. Shoup. LNCS, vol. 3621 (Springer, Berlin, 2005), pp. 430–448
C. De Cannière, B. Preneel, Trivium, in New Stream Cipher Designs. LNCS, vol. 4986 (Springer, Berlin, 2008), pp. 84–97
C. De Cannière, Ö. Kücük, B. Preneel, Analysis of Grain’s initialization algorithm, in SASC 2008 (2008)
C. De Cannière, O. Dunkelman, M. Knezevic, KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers, in Clavier and Gaj [26] (2009), pp. 272–288
I. Dinur, A. Shamir, Cube attacks on tweakable black box polynomials, in EUROCRYPT, ed. by A. Joux. LNCS, vol. 5479 (Springer, Berlin, 2009), pp. 278–299
I. Dinur, A. Shamir, Breaking Grain-128 with dynamic cube attacks. Cryptology ePrint Archive, Report 2010/570, 2010
I. Dinur, T. Güneysu, C. Paar, A. Shamir, R. Zimmermann, An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware, in ASIACRYPT, ed. by D.H. Lee, X. Wang. LNCS, vol. 7073 (Springer, Berlin, 2011), pp. 327–343
H. Englund, T. Johansson, M.S. Turan, A framework for chosen IV statistical analysis of stream ciphers, in INDOCRYPT, ed. by K. Srinathan, C. Pandu Rangan, M. Yung. LNCS, vol. 4859 (Springer, Berlin, 2007), pp. 268–281
M. Feldhofer, C. Rechberger, A case against currently used hash functions in RFID protocols, in OTM Workshops (1), ed. by R. Meersman, Z. Tari, P. Herrero. LNCS, vol. 4277 (Springer, Berlin, 2006), pp. 372–381
M. Feldhofer, J. Wolkerstorfer, Strong crypto for RFID tags—a comparison of low-power hardware implementations, in ISCAS 2007 (IEEE, New York, 2007), pp. 1839–1842
W. Fischer, B.M. Gammel, O. Kniffler, J. Velten, Differential power analysis of stream ciphers, in SASC 2007 (2007)
P.-A. Fouque, G. Leurent, D. Réal, F. Valette, Practical electromagnetic template attack on HMAC, in Clavier and Gaj [26] (2009), pp. 66–80
G. Gong, K.C. Gupta (eds.), Progress in Cryptology—INDOCRYPT 2010—11th International Conference on Cryptology in India, Hyderabad, India, December 12–15, 2010. LNCS, vol. 6498 (Springer, Berlin, 2010)
T. Good, M. Benaissa, Hardware performance of eSTREAM phase-III stream cipher candidates, in SASC (2008)
J. Guo, T. Peyrin, A. Poschmann, The PHOTON family of lightweight hash functions, in CRYPTO, ed. by P. Rogaway. LNCS, vol. 6841 (Springer, Berlin, 2011), pp. 222–239
J. Guo, T. Peyrin, A. Poschmann, The PHOTON family of lightweight hash functions (2011). Available on https://sites.google.com/site/photonhashfunction/. Full version of [41]
M. Hell, T. Johansson, A. Maximov, W. Meier, A stream cipher proposal: Grain-128, in IEEE International Symposium on Information Theory (ISIT 2006) (2006)
M. Hell, T. Johansson, W. Meier, Grain: a stream cipher for constrained environments. Int. J. Wirel. Mob. Comput. 2(1), 86–93 (2007)
E.B. Kavun, T. Yalcin, A lightweight implementation of Keccak hash function for radio-frequency identification applications, in RFIDSec, ed. by S.B.O. Yalcin. LNCS, vol. 6370 (Springer, Berlin, 2010), pp. 258–269
J. Kelsey, T. Kohno, Herding hash functions and the Nostradamus attack, in EUROCRYPT, ed. by S. Vaudenay. LNCS, vol. 4004 (Springer, Berlin, 2006), pp. 183–200
S. Knellwolf, W. Meier, M. Naya-Plasencia, Conditional differential cryptanalysis of NLFSR-based cryptosystems, in ASIACRYPT, ed. by M. Abe. LNCS, vol. 6477 (Springer, Berlin, 2010), pp. 130–145
S. Knellwolf, W. Meier, M. Naya-Plasencia, Conditional differential cryptanalysis of Trivium and KATAN, in Selected Areas in Cryptography, ed. by A. Miri, S. Vaudenay. LNCS, vol. 7118 (Springer, Berlin, 2012), pp. 200–212
Y. Lee, K. Jeong, J. Sung, S. Hong, Related-key chosen IV attacks on Grain-v1 and Grain-128, in ACISP, ed. by Y. Mu, W. Susilo, J. Seberry. LNCS, vol. 5107 (Springer, Berlin, 2008), pp. 321–335
S. Mangard, F.-X. Standaert (eds.), Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17–20, 2010. LNCS, vol. 6225 (Springer, Berlin, 2010)
R.P. McEvoy, M. Tunstall, C.C. Murphy, W.P. Marnane, Differential power analysis of HMAC based on SHA-2, and countermeasures, in WISA, ed. by S. Kim, M. Yung, H.-W. Lee. LNCS, vol. 4867 (Springer, Berlin, 2007), pp. 317–332
NIST, Cryptographic hash algorithm competition. http://www.nist.gov/hash-competition
M. O’Neill, Low-cost SHA-1 hash function architecture for RFID tags, in Workshop on RFID Security RFIDsec (2008)
M. Renauld, F.-X. Standaert, Combining algebraic and side-channel cryptanalysis against block ciphers, in 30th Symposium on Information Theory in the Benelux (2009), pp. 97–104. http://www.dice.ucl.ac.be/~fstandae/68.pdf
M.-J.O. Saarinen, Chosen-IV statistical attacks on eStream ciphers, in SECRYPT, ed. by M. Malek, E. Fernández-Medina, J. Hernando (INSTICC Press, Setubal, 2006), pp. 260–266
P. Sarkar, S. Maitra, Construction of nonlinear boolean functions with important cryptographic properties, in EUROCRYPT, ed. by B. Preneel. LNCS, vol. 1807 (Springer, Berlin, 2000), pp. 485–506
A. Shamir, SQUASH—a new MAC with provable security properties for highly constrained devices such as RFID tags, in FSE, ed. by K. Nyberg. LNCS, vol. 5086 (Springer, Berlin, 2008), pp. 144–157
P. Stankovski, Greedy distinguishers and nonrandomness detectors, in Gong and Gupta [39] (2010), pp. 210–226
G. Van Assche, Errata for Keccak presentation. Email sent to the NIST SHA-3 mailing list on Feb. 7, 2011, on behalf of the Keccak team
L. Wei, C. Rechberger, J. Guo, H. Wu, H. Wang, S. Ling, Improved meet-in-the-middle cryptanalysis of KTANTAN (poster), in ACISP, ed. by U. Parampalli, P. Hawkes. LNCS, vol. 6812 (Springer, Berlin, 2011), pp. 433–438
H. Yoshida, D. Watanabe, K. Okeya, J. Kitahara, H. Wu, O. Kucuk, B. Preneel, MAME: a compression function with reduced hardware requirements, in ECRYPT Hash Workshop 2007 (2007)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Mitsuru Matsui
Extended version of an article appearing at CHES 2010. The specification of Quark given in this version differs from that in the CHES 2010 proceedings, namely, the parameter n has been increased to address a flaw in the initial analysis (as reported in [59]). This work was partially supported by European Commission through the ICT programme under contract ICT-2007-216676 ECRYPT II.
This work was done when the second author was with ETHZ, Switzerland.
This work was done when the fourth author was with FHNW, Switzerland.
Rights and permissions
About this article
Cite this article
Aumasson, JP., Henzen, L., Meier, W. et al. Quark: A Lightweight Hash. J Cryptol 26, 313–339 (2013). https://doi.org/10.1007/s00145-012-9125-6
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-012-9125-6