Grøstl – a SHA-3 candidate
Analysis
Below, we list all currently known analysis results on Grøstl (with tweak) and Grøstl-0 (without tweak). In most attacks, especially the degrees of freedom are a limiting factor which provides additional strength in Grøstl.
Hash function analysis
NEW! We have updated the security analysis of Grøstl to the tweaked version. For the round-reduced hash function, we get collisions for 3 out of 10 rounds of Grøstl-256 and 3 out of 14 rounds of Grøstl-512 in [8].
Andreeva, Mennink, and Preneel prove [7] all Grøstl versions indifferentiable from a random oracle up to the birthday bound.
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.
NEW! Compression function collisions for Grøstl-256 on 6/10 rounds and Grøstl-512 on 6/14 rounds are given in [8].
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.
- Distinguishers based on k-sums (of value zero) or differential q-multicollisions are easy to find for the compression function. We give one example for a 4-sum here: Let H1 + H2 + H3 + H4 = 0 and H1 + H2 = M1 + M2, then f(H1,M1) + f(H2,M2) + f(H3,M1) + f(H4,M2) = 0. Note that this also implies H1 + H2 = H3 + H4 = Δ1 and f(H1,M1) + f(H2,M2) = f(H3,M1) + f(H4,M2) = Δ2.
- Generalized birthday collision attack in time 2171 for Grøstl-256 and 2341 for Grøstl-512. See the submission document.
- Memoryless preimage attack in time 2b/2, where b ≥ 2n is the output size of the compression function. Note that for a given target T, one can compute M, X using cycle finding algorithms such that T = H + P(H + M) + Q(M) = X + P(X) + M + Q(M) with H = X + M.
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 [4] and [2]. New results with much higher complexity for 9/10 of Grøstl-256 and 10/14 rounds of Grøstl-512 are shown in [9]
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
Analysis of Grøstl-0
Previously, a subset of the Grøstl team considered hash function attacks on Grøstl-0 with reduced security parameters. The results are collisions for up to 4 out of 10 rounds of Grøstl-0-256 and up to 5 out of 14 rounds of Grøstl-0-512 in [3].
Also, Kota Ideguchi, Elmar Tischhauser and Bart Preneel have analyzed Grøstl-0 and found collisions for up to 6 out of 10 rounds for Grøstl-0-256 in [6].
Compression function collisions for Grøstl-0-256 on 7/10 rounds and Grøstl-0-512 on 7/14 rounds are given in [3].
Further compression function collision attacks for 7/10 rounds of Grøstl-0-256 are provided by Henri Gilbert and Thomas Peyrin in [4], and Kota Ideguchi, Elmar Tischhauser and Bart Preneel in [6].
Earlier, different collision attacks on 6/10 rounds of the Grøstl-0-256 compression function are described in [1] and [2].
Thomas Peyrin has published a distinguisher for the compression function of Grøstl-0-256 with a complexity of 2192 in [5].
References:
[1] 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.
[2] 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.
[3] 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.
[4] H. Gilbert and T. Peyrin. Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations. In S. Hong and T. Iwata, editors, Fast Software Encryption 2010, Proceedings, volume 6147 of Lecture Notes in Computer Science, pages 365-383. Springer, 2010.
[5] T. Peyrin. Improved Differential Attacks for ECHO and Grøstl. In T. Rabin, editor, Advances in Cryptology - CRYPTO 2010, Proceedings, volume 6223 of Lecture Notes in Computer Science, pages 370-392. Springer, 2010.
[6] K. Ideguchi, E. Tischhauser, and B. Preneel. Improved Collision Attacks on the Reduced-Round Grøstl Hash Function. In M. Burmester, G. Tsudik, S. S. Magliveras, and I. Ilic, editors, Information Security Conference (ISC) 2010, Proceedings, volume 6531 of Lecture Notes in Computer Science, pages 1-16. Springer, 2011.
[7] E. Andreeva, B. Mennink, and B. Preneel. On the Indifferentiability of the Grøstl Hash Function. In J. A. Garay and R. D. Prisco, editors, Security and Cryptography for Networks (SCN) 2010, Proceedings, volume 6280 of Lecture Notes in Computer Science, pages 88-105. Springer, 2010.
[8] M. Schläffer. Updated Differential Analysis of Grøstl. January 2011.
[9] J. Jean, M. Naya-Plasencia and T. Peyrin. Improved Rebound Attack on the Finalist Grøstl. Fast Software Encryption (FSE) 2012, To appear.