Paper 2010/298

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.