×

Quark: a lightweight hash. (English) Zbl 1279.94053

Summary: 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\, \mu W\) at 100 kHz in \(0.18\, \mu 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\, \mu W\).

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ågren, M.; Hell, M.; Johansson, T.; Meier, W., A new version of Grain-128 with authentication, ECRYPT Symmetric Key Encryption Workshop 2011 (2011)
[2] Aumasson, J.-P.; Brier, E.; Meier, W.; Naya-Plasencia, M.; Peyrin, T.; Boyd, C.; Manuel González Nieto, J., Inside the hypercube, ACISP, 202-213 (2009), Berlin: Springer, Berlin · Zbl 1307.94035
[3] Aumasson, J.-P.; Dinur, I.; Henzen, L.; Meier, W.; Shamir, A., Efficient FPGA implementations of highly-dimensional cube testers on the stream cipher Grain-128, SHARCS (2009)
[4] Aumasson, J.-P.; Dinur, I.; Meier, W.; Shamir, A.; Dunkelman, O., Cube testers and key recovery attacks on reduced-round MD6 and Trivium, FSE, 1-22 (2009), Berlin: Springer, Berlin · Zbl 1291.94051
[5] Aumasson, J.-P.; Henzen, L.; Meier, W.; Naya-Plasencia, M., Quark: a lightweight hash, Mangard and Standaert [50], 1-15 (2010) · Zbl 1297.94043
[6] Bard, G. V.; Courtois, N.; Nakahara, J.; Sepehrdad, P.; Zhang, B., Algebraic, AIDA/cube and side channel analysis of KATAN family of block ciphers, Gong and Gupta [39], 176-196 (2010) · Zbl 1266.94020
[7] Bellare, M.; Ristenpart, T.; Lai, X.; Chen, K., Multi-property-preserving hash domain extension and the EMD transform, ASIACRYPT, 299-314 (2006), Berlin: Springer, Berlin · Zbl 1172.94561
[8] Bernet, M.; Henzen, L.; Kaeslin, H.; Felber, N.; Fichtner, W., Hardware implementations of the SHA-3 candidates Shabal and CubeHash, CT-MWSCAS (2009), New York: IEEE, New York
[9] D.J. Bernstein, CubeHash appendix: complexity of generic attacks. Submission to NIST, 2008. http://cubehash.cr.yp.to/submission/generic.pdf
[10] D.J. Bernstein, CubeHash parameter tweak: 16 times faster, 2009. http://cubehash.cr.yp.to/submission/tweak.pdf
[11] D.J. Bernstein, CubeHash specification (2.B.1). Submission to NIST (Round 2), 2009. http://cubehash.cr.yp.to/submission2/spec.pdf
[12] Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G., RadioGatún, a belt-and-mill hash function, Second NIST Cryptographic Hash Function Workshop (2006)
[13] Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G.; Smart, N. P., On the indifferentiability of the sponge construction, EUROCRYPT, 181-197 (2008), Berlin: Springer, Berlin · Zbl 1149.94304
[14] 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
[15] Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G., Sponge-based pseudo-random number generators, Mangard and Standaert [50], 33-47 (2010) · Zbl 1297.94050
[16] Bertoni, G.; Daemen, J.; Peeters, M.; Van Assche, G., On the security of the keyed sponge construction, ECRYPT Symmetric Key Encryption Workshop 2011 (2011)
[17] G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, Sponge functions. http://sponge.noekeon.org/SpongeFunctions.pdf
[18] 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 · Zbl 1292.94030
[19] E. Biham, O. Dunkelman, A framework for iterative hash functions—HAIFA. Cryptology ePrint Archive, Report 2007/278, 2007
[20] Biryukov, A.; Wagner, D.; Knudsen, L., Slide attacks, FSE, 245-259 (1999), Berlin: Springer, Berlin · Zbl 0942.94020
[21] 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 · Zbl 1292.94032
[22] Bogdanov, A.; Knudsen, L. R.; Leander, G.; Paar, C.; Poschmann, A.; Robshaw, M. J.B.; Seurin, Y.; Vikkelsoe, C.; Paillier, P.; Verbauwhede, I., PRESENT: an ultra-lightweight block cipher, CHES, 450-466 (2007), Berlin: Springer, Berlin · Zbl 1142.94334
[23] Bogdanov, A.; Leander, G.; Paar, C.; Poschmann, A.; Robshaw, M. J.B.; Seurin, Y.; Oswald, E.; Rohatgi, P., Hash functions and RFID tags: mind the gap, CHES, 283-299 (2008), Berlin: Springer, Berlin · Zbl 1184.68229
[24] Bogdanov, A.; Knezevic, M.; Leander, G.; Toz, D.; Varici, K.; Verbauwhede, I.; Preneel, B.; Takagi, T., SPONGENT: a lightweight hash function, CHES, 312-325 (2011), Berlin: Springer, Berlin
[25] Cho, J. Y.; Pieprzyk, J., Linear cryptanalysis of reduced-round PRESENT, CT-RSA, 302-317 (2010), Berlin: Springer, Berlin · Zbl 1274.94051
[26] Clavier, C.; Gaj, K., Cryptographic Hardware and Embedded Systems—CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings (2009), Berlin: Springer, Berlin
[27] Coron, J.-S.; Dodis, Y.; Malinaud, C.; Puniya, P.; Shoup, V., Merkle-Damgård revisited: how to construct a hash function, CRYPTO, 430-448 (2005), Berlin: Springer, Berlin · Zbl 1145.94436
[28] De Cannière, C.; Preneel, B., Trivium, New Stream Cipher Designs, 84-97 (2008), Berlin: Springer, Berlin · Zbl 1285.94054
[29] De Cannière, C.; Kücük, Ö.; Preneel, B., Analysis of Grain’s initialization algorithm, SASC 2008 (2008) · Zbl 1142.94340
[30] De Cannière, C.; Dunkelman, O.; Knezevic, M., KATAN and KTANTAN—a family of small and efficient hardware-oriented block ciphers, Clavier and Gaj [26], 272-288 (2009) · Zbl 1290.94060
[31] Dinur, I.; Shamir, A.; Joux, A., Cube attacks on tweakable black box polynomials, EUROCRYPT, 278-299 (2009), Berlin: Springer, Berlin · Zbl 1239.94045
[32] I. Dinur, A. Shamir, Breaking Grain-128 with dynamic cube attacks. Cryptology ePrint Archive, Report 2010/570, 2010 · Zbl 1282.94042
[33] Dinur, I.; Güneysu, T.; Paar, C.; Shamir, A.; Zimmermann, R.; Lee, D. H.; Wang, X., An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware, ASIACRYPT, 327-343 (2011), Berlin: Springer, Berlin · Zbl 1227.94042
[34] Englund, H.; Johansson, T.; Turan, M. S.; Srinathan, K.; Pandu Rangan, C.; Yung, M., A framework for chosen IV statistical analysis of stream ciphers, INDOCRYPT, 268-281 (2007), Berlin: Springer, Berlin · Zbl 1153.94373
[35] Feldhofer, M.; Rechberger, C.; Meersman, R.; Tari, Z.; Herrero, P., A case against currently used hash functions in RFID protocols, OTM Workshops (1), 372-381 (2006), Berlin: Springer, Berlin
[36] Feldhofer, M.; Wolkerstorfer, J., Strong crypto for RFID tags—a comparison of low-power hardware implementations, ISCAS 2007, 1839-1842 (2007), New York: IEEE, New York
[37] Fischer, W.; Gammel, B. M.; Kniffler, O.; Velten, J., Differential power analysis of stream ciphers, SASC 2007 (2007) · Zbl 1177.94145
[38] Fouque, P.-A.; Leurent, G.; Réal, D.; Valette, F., Practical electromagnetic template attack on HMAC, Clavier and Gaj [26], 66-80 (2009)
[39] Gong, G.; Gupta, K. C., Progress in Cryptology—INDOCRYPT 2010—11th International Conference on Cryptology in India (2010), Berlin: Springer, Berlin · Zbl 1202.94009
[40] Good, T.; Benaissa, M., Hardware performance of eSTREAM phase-III stream cipher candidates, SASC (2008)
[41] Guo, J.; Peyrin, T.; Poschmann, A.; Rogaway, P., The PHOTON family of lightweight hash functions, CRYPTO, 222-239 (2011), Berlin: Springer, Berlin · Zbl 1287.94069
[42] 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] · Zbl 1287.94069
[43] Hell, M.; Johansson, T.; Maximov, A.; Meier, W., A stream cipher proposal: Grain-128, IEEE International Symposium on Information Theory (ISIT 2006) (2006)
[44] Hell, M.; Johansson, T.; Meier, W., Grain: a stream cipher for constrained environments, Int. J. Wirel. Mob. Comput., 2, 1, 86-93 (2007)
[45] Kavun, E. B.; Yalcin, T.; Yalcin, S. B.O., A lightweight implementation of Keccak hash function for radio-frequency identification applications, RFIDSec, 258-269 (2010), Berlin: Springer, Berlin
[46] Kelsey, J.; Kohno, T.; Vaudenay, S., Herding hash functions and the Nostradamus attack, EUROCRYPT, 183-200 (2006), Berlin: Springer, Berlin · Zbl 1140.94354
[47] Knellwolf, S.; Meier, W.; Naya-Plasencia, M.; Abe, M., Conditional differential cryptanalysis of NLFSR-based cryptosystems, ASIACRYPT, 130-145 (2010), Berlin: Springer, Berlin · Zbl 1253.94056
[48] Knellwolf, S.; Meier, W.; Naya-Plasencia, M.; Miri, A.; Vaudenay, S., Conditional differential cryptanalysis of Trivium and KATAN, Selected Areas in Cryptography, 200-212 (2012), Berlin: Springer, Berlin · Zbl 1292.94095
[49] Lee, Y.; Jeong, K.; Sung, J.; Hong, S.; Mu, Y.; Susilo, W.; Seberry, J., Related-key chosen IV attacks on Grain-v1 and Grain-128, ACISP, 321-335 (2008), Berlin: Springer, Berlin · Zbl 1285.94076
[50] Mangard, S.; Standaert, F.-X., Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop (2010), Berlin: Springer, Berlin
[51] McEvoy, R. P.; Tunstall, M.; Murphy, C. C.; Marnane, W. P.; Kim, S.; Yung, M.; Lee, H.-W., Differential power analysis of HMAC based on SHA-2, and countermeasures, WISA, 317-332 (2007), Berlin: Springer, Berlin
[52] NIST, Cryptographic hash algorithm competition. http://www.nist.gov/hash-competition
[53] O’Neill, M., Low-cost SHA-1 hash function architecture for RFID tags, Workshop on RFID Security RFIDsec (2008)
[54] Renauld, M.; Standaert, F.-X., Combining algebraic and side-channel cryptanalysis against block ciphers, 30th Symposium on Information Theory in the Benelux, 97-104 (2009)
[55] Saarinen, M.-J. O.; Malek, M.; Fernández-Medina, E.; Hernando, J., Chosen-IV statistical attacks on eStream ciphers, SECRYPT, 260-266 (2006), Setubal: INSTICC Press, Setubal
[56] Sarkar, P.; Maitra, S.; Preneel, B., Construction of nonlinear boolean functions with important cryptographic properties, EUROCRYPT, 485-506 (2000), Berlin: Springer, Berlin · Zbl 1082.94529
[57] Shamir, A.; Nyberg, K., SQUASH—a new MAC with provable security properties for highly constrained devices such as RFID tags, FSE, 144-157 (2008), Berlin: Springer, Berlin · Zbl 1154.68410
[58] Stankovski, P., Greedy distinguishers and nonrandomness detectors, Gong and Gupta [39], 210-226 (2010) · Zbl 1294.94078
[59] 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
[60] Wei, L.; Rechberger, C.; Guo, J.; Wu, H.; Wang, H.; Ling, S.; Parampalli, U.; Hawkes, P., Improved meet-in-the-middle cryptanalysis of KTANTAN (poster), ACISP, 433-438 (2011), Berlin: Springer, Berlin · Zbl 1295.94153
[61] Yoshida, H.; Watanabe, D.; Okeya, K.; Kitahara, J.; Wu, H.; Kucuk, O.; Preneel, B., MAME: a compression function with reduced hardware requirements, ECRYPT Hash Workshop 2007 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.