**On the Indifferentiability of the Grøstl Hash Function**

*Elena Andreeva, Bart Mennink and Bart Preneel*

**Abstract: **The notion of indifferentiability, introduced by Maurer et al., is an important criterion for the security of hash functions. Concretely, it ensures that a hash function has no structural design flaws and thus guarantees security against generic attacks up to the exhibited bounds. In this work we prove the indifferentiability of Grøstl, a second round SHA-3 hash function candidate. Grøstl combines characteristics of the wide-pipe and chop-Merkle-Damgård iterations and uses two distinct permutations P and Q internally. Under the assumption that P and Q are random l-bit permutations, where l is the iterated state size of Grøstl, we prove that the advantage of a distinguisher to differentiate Grøstl from a random oracle is upper bounded by O((Kq)^4/2^l), where the distinguisher makes at most q queries of length at most K blocks. For the specific Grøstl parameters, this result implies that Grøstl behaves like a random oracle up to q=O(2^{n/2}) queries, where n is the output size.
Furthermore, we show that the output transformation of Grøstl, as well as `Grøstail' (the composition of the final compression function and the output transformation), are clearly differentiable from a random oracle. This renders out indifferentiability proofs which rely on the idealness of a final state transformation.

**Category / Keywords: **secret-key cryptography / hash functions, indifferentiability, SHA-3, Groestl

**Publication Info: **Presented at SCN 2010

**Date: **received 18 May 2010, last revised 20 Sep 2010

**Contact author: **bmennink at esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20100920:102641 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]