Difference between revisions of "Groestl"

From The ECRYPT Hash Function Website
m (broken links fixed)
(Added Peyrin results)
Line 66: Line 66:
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
| 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  
 +
|-         
 +
| distinguisher || compression function || 256 || 10 rounds || 2<sup>192</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-                     
 
|-                     
−
| semi-free-start collision || compression || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
+
| distinguisher || compression function || 256 || 9 rounds || 2<sup>80</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-                     
 
|-                     
−
| distinguisher || compression || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
+
| distinguisher || compression function || 512 || 11 rounds || 2<sup>640</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 +
|- 
 +
| semi-free-start collision || compression functoin || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 +
|-                   
 +
| distinguisher || compression function || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
|-                     
 
|-                     
 
| distinguisher || permutation || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,Peyrin]
 
| distinguisher || permutation || 256 || 8 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2009/531.pdf Gilbert,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=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function || 256 || 7 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 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=128007&pCurrPk=47053 Mendel,Rechberger,Schläffer,Thomsen]
+
| semi-free-start collision || compression function|| 384,512 || 7 rounds || 2<sup>152</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053 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]
+
| semi-free-start collision || compression function || 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]
 
| 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]
Line 83: Line 89:
 
| 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]
 
| 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 function || 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 || 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]
+
| semi-free-start collision || compression function || 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]
 
|-                     
 
|-                     
 
| observation || hash  || all  ||  ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
 
| observation || hash  || all  ||  ||  ||  || [http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf Kelsey]
Line 91: Line 97:
 
| observation || block cipher || all ||  ||  ||  || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
 
| observation || block cipher || all ||  ||  ||  || [http://www.larc.usp.br/~pbarreto/Grizzly.pdf Barreto]
 
|-                     
 
|-                     
−
| free-start collision || compression || all || any || 2<sup>2n/3</sup> || 2<sup>2n/3</sup> || [http://www.groestl.info/Groestl.pdf submission document]
+
| free-start collision || compression function || 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]
+
| pseudo-preimage || compression function || all || any || 2<sup>n</sup> || - || [http://www.groestl.info/Groestl.pdf submission document]
 
|-                     
 
|-                     
 
|}
 
|}
  
  
−
 
+
<bibtex>         
 +
@misc{Pey10,
 +
    author = {Thomas Peyrin},
 +
    title = {Improved Differential Attacks for ECHO and Grostl},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/223},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abstract = {We present improved cryptanalysis of two second-round SHA-3 candidates: the AES-based hash functions ECHO and Grostl. We explain methods for building better differential trails for ECHO by increasing the granularity of the truncated differential paths previously considered. In the case of Grostl, we describe a new technique, the internal differential attack, which shows that when using parallel computations designers should also consider the differential security between the parallel branches. Then, we exploit the recently introduced start-from-the-middle or Super-Sbox attacks, that proved to be very efficient when attacking AES-like permutations, to achieve a very efficient utilization of the available freedom degrees. Finally, we obtain the best known attacks so far for both ECHO and Grostl. In particular, we are able to mount a distinguishing attack for the full Grostl-256 compression function.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Revision as of 09:00, 29 April 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
distinguisher compression function 256 10 rounds 2192 264 Peyrin
distinguisher compression function 256 9 rounds 280 264 Peyrin
distinguisher compression function 512 11 rounds 2640 264 Peyrin
semi-free-start collision compression functoin 256 7 rounds 2120 264 Gilbert,Peyrin
distinguisher compression function 256 8 rounds 2112 264 Gilbert,Peyrin
distinguisher permutation 256 8 rounds 2112 264 Gilbert,Peyrin
semi-free-start collision compression function 256 7 rounds 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 384,512 7 rounds 2152 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 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 function 256 6 rounds 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 224,256 5 rounds 264 - Mendel,Rechberger,Schläffer,Thomsen
observation hash all Kelsey
observation block cipher all Barreto
free-start collision compression function all any 22n/3 22n/3 submission document
pseudo-preimage compression function all any 2n - submission document


Thomas Peyrin - Improved Differential Attacks for ECHO and Grostl

,2010
Bibtex
Author : Thomas Peyrin
Title : Improved Differential Attacks for ECHO and Grostl
In : -
Address :
Date : 2010

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=128007&pCurrPk=47053
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=3470"