Hash function Grøstl – SHA-3 candidate

Home Specification Implementations Analysis Name Team SHA-3 cryptanalysis

Links

NIST SHA-3 IAIK @ TU Graz MAT @ DTU SHA-3 Zoo

Analysis

Below we list all currently known analysis results on Grøstl.

Hash function analysis

A subset of the Grøstl team considered hash function attacks on Grøstl with reduced security parameters. The results are collisions for up to 4 out of 10 rounds of Grøstl-256 and up to 5 out of 14 rounds of Grøstl-512:

F. Mendel, C. Rechberger, M. Schläffer, and S. S. Thomsen. Rebound Attacks on the Reduced Grøstl Hash Function. In J. Pieprzyk, editor, Topics in Cryptology - CT-RSA 2010, Proceedings, volume 5985 of Lecture Notes in Computer Science, pages 350-365. Springer, 2010.

Compression function analysis

Grøstl is among the very few SHA-3 candidates with security claims that go beyond those required by NIST, namely claiming collision resistance and preimage resistance of the compression function up to the level needed for the hash function. The chaining input of the wide-pipe Grøstl compression function is as big as the message input. Hence, allowing an adversary direct access to the chaining input increases the degrees of freedom of an attack significantly. Even in this much simpler setting no collision or preimage attack is found. This clearly serves as a reassurance of the collision and preimage resistance of the Grøstl hash function.

Compression function collisions for Grøstl-256 on 7/10 rounds and Grøstl-512 on 7/14 rounds are given in:

Also, Henri Gilbert and Thomas Peyrin provide compression function collisions on 7/10 rounds of Grøstl-256 in their work:

H. Gilbert and T. Peyrin. Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations. Cryptology ePrint Archive, Report 2009/531, November 2009. http://eprint.iacr.org/. To appear in FSE 2010.

Earlier, different collision attacks on 6/10 rounds of the Grøstl-256 compression function are described in:

F. Mendel, C. Rechberger, M. Schläffer, and S. S. Thomsen. The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl. In O. Dunkelman, editor, Fast Software Encryption 2009, Proceedings, volume 5665 of Lecture Notes in Computer Science, pages 260-276. Springer, 2009.

F. Mendel, T. Peyrin, C. Rechberger, and M. Schläffer. Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES. In M. J. Jacobson Jr., V. Rijmen, and R. Safavi-Naini, editors, Selected Areas in Cryptography 2009, Proceedings, volume 5867 of Lecture Notes in Computer Science, pages 16-35. Springer, 2009.

Non-random properties of building blocks

Non-random properties of the actual Grøstl hash function are not known. In here, we consider non-random properties of some of the underlying building blocks. The Grøstl compression function is claimed to be collision and preimage resistant up to the level needed for the hash function. Even though these properties are not strictly necessary, they serve as a reassurance of the collision and preimage resistance of the Grøstl hash function. On the other hand, the Grøstl compression function is known to be non-random. Hence, the wide pipe and the strong output transformation are essential parts of the design. Nevertheless, here we give an incomplete list of known non-random properties of the compression function.

Many fixed points can be found in the compression function in time 1. See the submission document.
Generalized birthday collision attack in time 2¹⁷¹ for Grøstl-256 and 2³⁴² for Grøstl-512. See the submission document.
Memoryless preimage attack in time 2^b/2, where b ≥ 2n is the output size of the compression function.

The Grøstl compression function is built from two permutations. Non-random properties of the Grøstl-256 permutations for 8/10 and 7/10 rounds are shown in these two papers:

Observations by John Kelsey

John Kelsey submitted a public comment to NIST with some observations on Grøstl. This document describes the observations, which include some possible approaches to finding collisions, and an observation on the output transformation that shows that what precludes length extension attacks is the truncation, not the "P(x) + x" part.

Alternative view of Grøstl by P. Barreto

In an e-mail to the hash-forum, Paulo Barreto wrote:

There is an interesting alternative way (N.B. this is *not* an attack) to look at the Groestl compression function f, namely, as conventional Davies-Meyer on top of an Even-Mansour cipher.

Details in http://www.larc.usp.br/~pbarreto/Grizzly.pdf

Grøstl – a SHA-3 candidate