CryptoDB
On the Indifferentiability of the Gr{\o}stl Hash Function
| Authors: | |
|---|---|
| Download: | |
| 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{\o}stl, a second round SHA-3 hash function candidate. Gr{\o}stl combines characteristics of the wide-pipe and chop-Merkle-Damg{\aa}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{\o}stl, we prove that the advantage of a distinguisher to differentiate Gr{\o}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{\o}stl parameters, this result implies that Gr{\o}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{\o}stl, as well as `Gr{\o}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. |
BibTeX
@misc{eprint-2010-23199,
title={On the Indifferentiability of the Gr{\o}stl Hash Function},
booktitle={IACR Eprint archive},
keywords={secret-key cryptography / hash functions, indifferentiability, SHA-3, Groestl},
url={http://eprint.iacr.org/2010/298},
note={ bmennink@esat.kuleuven.be 14747 received 18 May 2010},
author={Elena Andreeva and Bart Mennink and Bart Preneel},
year=2010
}