Abstract
Due to recent breakthroughs in hash functions cryptanalysis, some new hash schemes have been proposed. Grindahl is a novel hash function, designed by Knudsen, Rechberger and Thomsen and published at FSE 2007. It has the particularity that it follows the Rijndael design strategy, with an efficiency comparable to SHA-256. This paper provides the first cryptanalytic work on this new scheme. We show that the 256-bit version of Grindahl is not collision resistant. With a work effort of approximatively 2112 hash computations, one can generate a collision.
Chapter PDF
Similar content being viewed by others
Keywords
References
Augot, D., Finiasz, M., Sendrier, N.: A Family of Fast Syndrome Based Cryptographic Hash Functions. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 64–83. Springer, Heidelberg (2005)
Bellare, M., Ristenpart, T.: Multi-Property-Preserving Hash Domain Extension and the EMD Transform. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 299–314. Springer, Heidelberg (2006)
Bentahar, K., Page, D., Saarinen, M.-J.O., Silverman, J.H., Smart, N.P.: LASH. In: Proceedings of Second NIST Cryptographic Hash Workshop (2006). Available from: www.csrc.nist.gov/pki/HashWorkshop/2006/program_2006.htm
Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: RadioGatun, a Belt-and-Mill Hash Function. In: Proceedings of Second NIST Cryptographic Hash Workshop (2006). Available from: www.csrc.nist.gov/pki/HashWorkshop/2006/program_2006.htm
Biham, E., Dunkelman, O.: A Framework for Iterative Hash Functions: HAIFA. In: Proceedings of Second NIST Cryptographic Hash Workshop (2006). Available from: www.csrc.nist.gov/pki/HashWorkshop/2006/program_2006.htm
Billet, O., Robshaw, M.J.B., Peyrin, T.: On Building Hash Functions From Multivariate Quadratic Equations. In: Pieprzyk, J. (ed.) Information Security and Privacy – ACISP 2007. LNCS, Springer, Heidelberg (2007)
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)
De Cannière, C., Rechberger, C.: Finding SHA-1 Characteristics: General Results and Applications. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 1–20. Springer, Heidelberg (2006)
Contini, S., Lenstra, A.K., Steinfeld, R.: VSH, an Efficient and Provable Collision-Resistant Hash Function. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 165–182. Springer, Heidelberg (2006)
Damgård, I.: A Design Principle for Hash Functions. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 416–427. Springer, Heidelberg (1990)
Daemen, J., Rijmen, V.: The Design of Rijndael. Springer, Heidelberg (2002)
Menezes, A.J., Vanstone, S.A., Van Oorschot, P.C.: Handbook of Applied Cryptography. CRC Press, Boca Raton, FL, USA (1996)
Hirose, S.: Some Plausible Constructions of Double-Block-Length Hash Functions. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 210–225. Springer, Heidelberg (2006)
Hoch, J.J., Shamir, A.: Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 179–194. Springer, Heidelberg (2006)
Hong, D., Chang, D., Sung, J., Lee, S., Hong, S., Lee, J., Moon, D., Chee, S.: Dedicated 256-Bit Hash Function: FORK-256. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol. 4047, pp. 195–209. Springer, Heidelberg (2006)
Joux, A.: Multi-collisions in Iterated Hash Functions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (2004)
Kelsey, J., Kohno, T.: Herding Hash Functions and the Nostradamus Attack. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 183–200. Springer, Heidelberg (2006)
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.: Truncated and Higher Order Differentials. In: Preneel, B. (ed.) Fast Software Encryption. LNCS, vol. 1008, pp. 196–211. Springer, Heidelberg (1995)
Knudsen, L.R., Rechberger, C., Thomsen, S.S.: Grindahl - A family of hash functions. In: Biryukov, A. (ed.) Fast Software Encryption – FSE 2007. LNCS, Springer, Heidelberg (2007)
Matusiewicz, K., Peyrin, T., Billet, O., Contini, S., Pieprzyk, J.: Cryptanalysis of FORK-256. In: Biryukov, A. (ed.) Fast Software Encryption – FSE 2007. LNCS, Springer, Heidelberg (2007)
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 197: Advanced Encryption Standard, November 2001. Available from: www.csrc.nist.gov
National Institute of Standards and Technology. Advanced Hash Standard. Available from: www.csrc.nist.gov/pki/HashWorkshop/index.html
National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard (August 2002). Available from: www.csrc.nist.gov .
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)
Preneel, B.: Analysis and Design of Cryptographic Hash Functions. PhD thesis, Katholieke Universiteit Leuven (1993)
Preneel, B., Govaerts, R., Vandewalle, J.: Hash Functions Based on Block Ciphers: A Synthetic Approach. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 368–378. Springer, Heidelberg (1994)
Rivest, R.L.: RFC 1321: The MD5 Message-Digest Algorithm (April 1992). Available from, www.ietf.org/rfc/rfc1321.txt
Seurin, Y., Peyrin, T.: Security Analysis of Constructions Combining FIL Random Oracles. In: Biryukov, A. (ed.) Fast Software Encryption – FSE 2007. LNCS, Springer, Heidelberg (2007)
Wang, X., Lai, X., Feng, D., Chen, H., Yu, X.: Cryptanalysis of the Hash Functions MD4 and RIPEMD. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 1–18. Springer, Heidelberg (2005)
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)
Wang, X., Yu, H., Yin, Y.L.: Efficient Collision Search Attacks on SHA-0. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 1–16. Springer, Heidelberg (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peyrin, T. (2007). Cryptanalysis of Grindahl . In: Kurosawa, K. (eds) Advances in Cryptology – ASIACRYPT 2007. ASIACRYPT 2007. Lecture Notes in Computer Science, vol 4833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76900-2_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-76900-2_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76899-9
Online ISBN: 978-3-540-76900-2
eBook Packages: Computer ScienceComputer Science (R0)