(Pseudo) Preimage Attack on Round-Reduced Grøstl Hash Function and Others (Extended Version)

Shuang Wu; Dengguo Feng; Wenling Wu; Jian Guo; Le Dong; Jian Zou

Paper 2012/206

(Pseudo) Preimage Attack on Round-Reduced Grøstl Hash Function and Others (Extended Version)

Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, and Jian Zou

Abstract

The Grøstl hash function is one of the 5 final round candidates of the SHA-3 competition hosted by NIST. In this paper, we study the preimage resistance of the Grøstl hash function. We propose pseudo preimage attacks on Grøstl hash function for both 256-bit and 512-bit versions, i.e. we need to choose the initial value in order to invert the hash function. Pseudo preimage attack on 5(out of 10)-round Grøstl-256 has a complexity of $(2^{244.85},2^{230.13})$ (in time and memory) and pseudo preimage attack on 8(out of 14)-round Grøstl-512 has a complexity of $(2^{507.32},2^{507.00})$. To the best of our knowledge, our attacks are the first (pseudo) preimage attacks on round-reduced Grøstl hash function, including its compression function and output transformation. These results are obtained by a variant of meet-in-the-middle preimage attack framework by Aoki and Sasaki. We also improve the time complexities of the preimage attacks against 5-round Whirlpool and 7-round AES hashes by Sasaki in FSE~2011.

Note: Extended Version for the camera-ready version that will be published at FSE 2012 proceeding

Metadata

Available format(s): PDF
Publication info: Published elsewhere. FSE 2012
Keywords: hash function meet-in-the-middle preimage attack Grøstl Whirlpool AES
Contact author(s): wushuang @ is iscas ac cn
History: 2012-09-10: last of 3 revisions; 2012-04-22: received; See all versions
Short URL: https://ia.cr/2012/206
License: CC BY

BibTeX

@misc{cryptoeprint:2012/206,
      author = {Shuang Wu and Dengguo Feng and Wenling Wu and Jian Guo and Le Dong and Jian Zou},
      title = {(Pseudo) Preimage Attack on Round-Reduced Grøstl Hash Function and Others (Extended Version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/206},
      year = {2012},
      url = {https://eprint.iacr.org/2012/206}
}