Paper 2010/298

On the Indifferentiability of the Grøstl Hash Function

Elena Andreeva, Bart Mennink, and Bart Preneel


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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Presented at SCN 2010
hash functionsindifferentiabilitySHA-3Groestl
Contact author(s)
bmennink @ esat kuleuven be
2010-09-20: revised
2010-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elena Andreeva and Bart Mennink and Bart Preneel},
      title = {On the Indifferentiability of the Grøstl Hash Function},
      howpublished = {Cryptology ePrint Archive, Paper 2010/298},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.