Difference between revisions of "Groestl"

From The ECRYPT Hash Function Website
m
(Tables split + designers analysis added)
Line 26: Line 26:
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
Line 37: Line 36:
 
=== Hash function ===
 
=== Hash function ===
  
−
Here we list results on the actual hash function. The only allowed modification is to change the security parameter.
+
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
  
 
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
 
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
Line 45: Line 44:
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
|-                     
 
|-                     
−
| || || || || ||
+
| collision || 224,256 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || 224,256 || 3 rounds || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || 384,512 || 5 rounds || 2<sup>176</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| collision || 384,512 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
 
|}                     
 
|}                     
Line 55: Line 60:
  
 
Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).  
 
Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).  
 +
 +
Recommended security parameters: '''10''' rounds (n=224,256); '''14''' rounds (n=384,512)
  
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
Line 60: Line 67:
 
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|-                     
 
|-                     
−
| observation || block cipher || all || || || || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
+
| semi-free-start collision || compression || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Henri,Peyrin]
 +
|-                   
 +
| distinguisher || compression || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Henri,Peyrin]
 +
|-                   
 +
| distinguisher || permutation || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Henri,Peyrin]
 +
|-                   
 +
| semi-free-start collision || compression || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| semi-free-start collision || compression || 384,512 || 7 rounds || 2<sup>152</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759 Mendel,Rechberger,Schläffer,Thomsen]
 +
|-                   
 +
| semi-free-start collision || compression || 224,256 || 6 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 +
|-                   
 +
| distinguisher || output transformation || 224,256 || 7 rounds || 2<sup>56</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
|-                     
 
|-                     
−
| observation || hash  || all  || || || || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
+
| distinguisher || permutation || 224,256 || 7 rounds || 2<sup>55</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
 
|-                     
 
|-                     
 
| semi-free-start collision || compression || 256 || 6 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
 
| semi-free-start collision || compression || 256 || 6 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression || 256 || 6 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
+
| semi-free-start collision || compression || 224,256 || 5 rounds || 2<sup>64</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943 Mendel,Rechberger,Schläffer,Thomsen]
 
|-                     
 
|-                     
−
| distinguisher || output transformation || 256 || 7 rounds || 2<sup>56</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
+
| observation || hash  || all  || || ||  || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
 +
|-                   
 +
| observation || block cipher || all ||  ||  || || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
 
|-                     
 
|-                     
−
| distinguisher || permutation || 256 || 7 rounds || 2<sup>55</sup> || - || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420 Mendel,Peyrin,Rechberger,Schläffer]
+
| free-start collision || compression || all || any || 2<sup>2n/3</sup> || 2<sup>2n/3</sup> || [http://www.groestl.info/Groestl.pdf submission document]
 +
|-                  
 +
| pseudo-preimage || compression || all || any || 2<sup>n</sup> || - || [http://www.groestl.info/Groestl.pdf submission document]
 
|-                     
 
|-                     
 
|}
 
|}
Line 78: Line 101:
  
 
<bibtex>
 
<bibtex>
−
@misc{groestlB08,
+
@inproceedings{fseGP10,
−
   author    = {Paulo S. L. M. Barreto},
+
   author    = {Henri Gilbert and Thomas Peyrin},
−
   title    = {An observation on Grøstl},
+
  title    = {Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations},
−
   url       = {http://www.larc.usp.br/~pbarreto/Grizzly.pdf},
+
  url = {http://eprint.iacr.org/2009/531.pdf},
−
   howpublished = {Available online},
+
  booktitle  = {FSE},
−
   year     = {2008},
+
  year      = {2010},
−
   abstract = {An alternative view of the Groestl SHA-3 submission is presented. It does not lead to an effective attack nor reveals a weakness in the design, but illustrates the importance of the double-width pipe in this construction.},
+
  series    = {LNCS},
−
}
+
  note = {To appear}
 +
  abstract = {In this paper, we improve the recent rebound and start-from-the-middle attacks on AES-like permutations. Our new cryptanalysis technique uses the fact that one can view two rounds of such permutations as a layer of big Sboxes preceded and followed by simple affine transformations. The big Sboxes encountered in this alternative representation are named Super-Sboxes. We apply this method to two second-round SHA-3 candidates Grostl and ECHO, and obtain improvements over the previous cryptanalysis results for these two schemes. Moreover, we improve the best distinguisher for the AES block cipher in the known-key setting, reaching 8 rounds for the 128-bit version.}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@inproceedings{ctrsaMRST10,
 +
  author    = {Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
 +
   title    = {Rebound Attacks on the Reduced Grøstl Hash Function},
 +
   url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759},
 +
   booktitle  = {CT-RSA},
 +
   year       = {2010},
 +
  publisher  = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {5985},
 +
  pages    = {350-365},
 +
  note = {To appear}
 +
   abstract = {Grøstl is one of 14 second round candidates of the
 +
NIST SHA-3 competition. Cryptanalytic results on the wide-pipe compression
 +
function of Grøstl-256 have already been published. However, little is known
 +
about the hash function, arguably a much more interesting cryptanalytic
 +
setting. Also, Grøstl-512 has not been analyzed yet. In this paper, we show
 +
the first cryptanalytic attacks on reduced-round versions of the Grøstl hash
 +
functions. These results are obtained by several extensions of the rebound
 +
attack. We present a collision attack on 4/10 rounds of the Grøstl-256 hash
 +
function and 5/14 rounds of the Grøstl-512 hash functions. Additionally, we
 +
give the best collision attack for reduced-round (7/10 and 7/14) versions of the
 +
compression function of Grøstl-256 and Grøstl-512.}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{groestlK09,
+
@inproceedings{sacMPRS09,
−
   author    = {John Kelsey},
+
   author    = {Florian Mendel and Thomas Peyrin and Christian
−
   title    = {Some notes on Grøstl},
+
Rechberger and Martin Schläffer},
−
   url       = {http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf},
+
   title    = {Improved Cryptanalysis of the Reduced Grøstl
−
   howpublished = {Available online},
+
Compression Function, ECHO Permutation and AES Block Cipher},
−
   year     = {2009},
+
   url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420},
−
   abstract = {These are some quick notes on some properties and observations of Grøstl. Nothing in this note threatens the hash function; instead, I'm pointing out some properties that are a bit surprising, and some broad approaches someone might take to get attacks to work.},
+
   booktitle  = {SAC},
−
}
+
   year       = {2009},
 +
  volume    = {5867},
 +
  pages    = {16-35},
 +
   abstract = {In this paper, we propose two new ways to mount attacks
 +
on the SHA-3 candidates Gr{\o}stl, and ECHO, and apply these attacks
 +
also to the AES. Our results improve upon and extend the rebound
 +
attack. Using the new techniques, we are able to extend the number of
 +
rounds in which available degrees of freedom can be used. As a result,
 +
we present the first attack on 7 rounds for the Gr{\o}stl-256 output
 +
transformation and improve the semi-free-start collision attack on 6
 +
rounds. Further, we present an improved known-key distinguisher for 7
 +
rounds of the AES block cipher and the internal permutation used in
 +
ECHO.}
 
</bibtex>
 
</bibtex>
  
Line 111: Line 172:
 
   volume    = {5665},
 
   volume    = {5665},
 
   pages    = {260-276},
 
   pages    = {260-276},
−
  note = {To appear}
+
   abstract = {In this work, we propose the rebound attack, a new tool
−
   abstract = {In this work, we propose the rebound attack, a new tool for the cryptanalysis of hash functions. The idea of the rebound attack is to use the available degrees of freedom in a collision attack to efficiently bypass the low probability parts of a differential trail. The rebound attack consists of an inbound phase with a match-in-the-middle part to exploit the available degrees of freedom, and a subsequent probabilistic outbound phase. Especially on AES based hash functions, the rebound attack leads to new attacks for a surprisingly high number of
+
for the cryptanalysis of hash functions. The idea of the rebound
 +
attack is to use the available degrees of freedom in a collision
 +
attack to efficiently bypass the low probability parts of a
 +
differential trail. The rebound attack consists of an inbound phase
 +
with a match-in-the-middle part to exploit the available degrees of
 +
freedom, and a subsequent probabilistic outbound phase. Especially on
 +
AES based hash functions, the rebound attack leads to new attacks for
 +
a surprisingly high number of
 
rounds.
 
rounds.
−
We use the rebound attack to construct collisions for 4.5 rounds of the 512-bit hash function Whirlpool with a complexity of $2^{120}$ compression function evaluations and negligible memory requirements. The attack can be extended to a near-collision on 7.5 rounds of the compression function of Whirlpool and 8.5 rounds of the similar hash function Maelstrom. Additionally, we apply the rebound attack to the SHA-3 submission Gr{\o}stl, which leads to an attack on 6 rounds of the Gr{\o}stl-256 compression function with a complexity of $2^{120}$ and memory requirements of about $2^{64}$.}
+
We use the rebound attack to construct collisions for 4.5 rounds of
 +
the 512-bit hash function Whirlpool with a complexity of $2^{120}$
 +
compression function evaluations and negligible memory requirements.
 +
The attack can be extended to a near-collision on 7.5 rounds of the
 +
compression function of Whirlpool and 8.5 rounds of the similar hash
 +
function Maelstrom. Additionally, we apply the rebound attack to the
 +
SHA-3 submission Gr{\o}stl, which leads to an attack on 6 rounds of
 +
the Gr{\o}stl-256 compression function with a complexity of $2^{120}$
 +
and memory requirements of about $2^{64}$.}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{groestlK09,
 +
  author    = {John Kelsey},
 +
  title    = {Some notes on Grøstl},
 +
  url        = {http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2009},
 +
  abstract  = {These are some quick notes on some properties and
 +
observations of Grøstl. Nothing in this note threatens the hash
 +
function; instead, I'm pointing out some properties that are a bit
 +
surprising, and some broad approaches someone might take to get
 +
attacks to work.},
 +
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@inproceedings{sacMPRS09,
+
@misc{groestlB08,
−
   author    = {Florian Mendel and Thomas Peyrin and Christian Rechberger and Martin Schläffer},
+
   author    = {Paulo S. L. M. Barreto},
−
   title    = {Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher},
+
   title    = {An observation on Grøstl},
−
   url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420},
+
   url       = {http://www.larc.usp.br/~pbarreto/Grizzly.pdf},
−
   booktitle  = {SAC},
+
   howpublished = {Available online},
−
   year       = {2009},
+
   year     = {2008},
−
  note = {To appear}
+
   abstract = {An alternative view of the Groestl SHA-3 submission is
−
   abstract = {In this paper, we propose two new ways to mount attacks on the SHA-3 candidates Gr{\o}stl, and ECHO, and apply these attacks also to the AES. Our results improve upon and extend the rebound attack. Using the new techniques, we are able to extend the number of rounds in which available degrees of freedom can be used. As a result, we present the first attack on 7 rounds for the Gr{\o}stl-256 output transformation and improve the semi-free-start collision attack on 6 rounds. Further, we present an improved known-key distinguisher for 7 rounds of the AES block cipher and the internal permutation used in ECHO.}
+
presented. It does not lead to an effective attack nor reveals a
 +
weakness in the design, but illustrates the importance of the
 +
double-width pipe in this construction.},
 +
}
 
</bibtex>
 
</bibtex>

Revision as of 15:41, 15 February 2010

1 The algorithm

  • Author(s): Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
  • Website: http://www.groestl.info
  • NIST submission package:


Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate

,2008
http://www.groestl.info/Groestl.pdf
Bibtex
Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl -- a SHA-3 candidate
In : -
Address :
Date : 2008

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl Addendum

,2009
http://groestl.info/Groestl-addendum.pdf
Bibtex
Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl Addendum
In : -
Address :
Date : 2009

2 Cryptanalysis

We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.

A description of the tables is given here.


2.1 Hash function

Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.

Recommended security parameters: 10 rounds (n=224,256); 14 rounds (n=384,512)

Type of Analysis Hash Size (n) Parameters Compression Function Calls Memory Requirements Reference
collision 224,256 4 rounds 264 264 Mendel,Rechberger,Schläffer,Thomsen
collision 224,256 3 rounds 264 - Mendel,Rechberger,Schläffer,Thomsen
collision 384,512 5 rounds 2176 264 Mendel,Rechberger,Schläffer,Thomsen
collision 384,512 4 rounds 264 264 Mendel,Rechberger,Schläffer,Thomsen


2.2 Building blocks

Here we list results on underlying building blocks, and the hash function modified by other means than the security parameter.

Note that these results assume more direct control or access over some internal variables (aka. free-start, pseudo, compression function, block cipher, or permutation attacks).

Recommended security parameters: 10 rounds (n=224,256); 14 rounds (n=384,512)

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
semi-free-start collision compression 256 7 rounds 2120 264 Henri,Peyrin
distinguisher compression 256 8 rounds 2112 264 Henri,Peyrin
distinguisher permutation 256 8 rounds 2112 264 Henri,Peyrin
semi-free-start collision compression 256 7 rounds 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression 384,512 7 rounds 2152 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression 224,256 6 rounds 264 264 Mendel,Peyrin,Rechberger,Schläffer
distinguisher output transformation 224,256 7 rounds 256 - Mendel,Peyrin,Rechberger,Schläffer
distinguisher permutation 224,256 7 rounds 255 - Mendel,Peyrin,Rechberger,Schläffer
semi-free-start collision compression 256 6 rounds 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression 224,256 5 rounds 264 - Mendel,Rechberger,Schläffer,Thomsen
observation hash all Kelsey
observation block cipher all Barreto
free-start collision compression all any 22n/3 22n/3 submission document
pseudo-preimage compression all any 2n - submission document



Henri Gilbert, Thomas Peyrin - Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations

FSE ,2010
http://eprint.iacr.org/2009/531.pdf
Bibtex
Author : Henri Gilbert, Thomas Peyrin
Title : Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations
In : FSE -
Address :
Date : 2010

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Rebound Attacks on the Reduced Grøstl Hash Function

CT-RSA 5985:350-365,2010
http://online.tu-graz.ac.at/tug_online/voe_main2.getvolltext?pDocumentNr=122759
Bibtex
Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Rebound Attacks on the Reduced Grøstl Hash Function
In : CT-RSA -
Address :
Date : 2010

Florian Mendel, Thomas Peyrin, Christian Rechberger, Martin Schläffer - Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher

SAC 5867:16-35,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420
Bibtex
Author : Florian Mendel, Thomas Peyrin, Christian

Rechberger, Martin Schläffer
Title : Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher
In : SAC -
Address :
Date : 2009

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl

FSE 5665:260-276,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943
Bibtex
Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl
In : FSE -
Address :
Date : 2009

John Kelsey - Some notes on Grøstl

,2009
http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf
Bibtex
Author : John Kelsey
Title : Some notes on Grøstl
In : -
Address :
Date : 2009

Paulo S. L. M. Barreto - An observation on Grøstl

,2008
http://www.larc.usp.br/~pbarreto/Grizzly.pdf
Bibtex
Author : Paulo S. L. M. Barreto
Title : An observation on Grøstl
In : -
Address :
Date : 2008
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Groestl&oldid=3374"