Difference between revisions of "Groestl"

From The ECRYPT Hash Function Website
m (fixed bibtex entry)
(SAC 2009 paper added)
Line 27: Line 27:
 
| 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]
 
|-                     
 
|-                     
−
| 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=99359 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=107049 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=106996 Mendel,Peyrin,Rechberger,Schläffer]
 +
|-                   
 +
| semi-free-start collision || compression || 256 || 7 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=106996 Mendel,Peyrin,Rechberger,Schläffer]
 
|-                     
 
|-                     
 
|}   
 
|}   
Line 60: Line 64:
 
   author    = {Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
 
   author    = {Florian Mendel and Christian Rechberger and Martin Schläffer and Søren S. Thomsen},
 
   title    = {The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl},
 
   title    = {The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl},
−
   url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=99359},
+
   url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=107049},
 
   booktitle  = {FSE},
 
   booktitle  = {FSE},
 
   editor    = {Orr Dunkelman},
 
   editor    = {Orr Dunkelman},
Line 69: Line 73:
 
   pages    = {260-276},
 
   pages    = {260-276},
 
   note = {To appear}
 
   note = {To appear}
−
   abstract = {In this work, we propose the rebound attack, a new tool for the cryptanalysis of
+
   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
−
hash functions. The idea of the rebound attack is to use the available degrees
+
rounds.
−
of freedom in a collision attack to efficiently bypass the low probability parts
+
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}$.}
−
of a differential trail. The rebound attack consists of an inbound phase with a
+
</bibtex>
−
match-in-the-middle part to exploit the available degrees of freedom, and a
+
 
−
subsequent probabilistic outbound phase. Especially on AES based hash
+
<bibtex>
−
functions, the rebound attack leads to new attacks for a surprisingly high
+
@inproceedings{sacMPRS09,
−
number of rounds.
+
  author    = {Florian Mendel and Thomas Peyrin and Christian Rechberger and Martin Schläffer},
−
We use the rebound attack to construct collisions for 4.5 rounds of the 512-bit
+
  title    = {Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher},
−
hash function Whirlpool with a complexity of $2^{120}$ compression function
+
  url = {http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=106996},
−
evaluations and negligible memory requirements. The attack can be extended to
+
  booktitle  = {SAC},
−
a near-collision on 7.5 rounds of the compression function of Whirlpool and 8.5
+
  year      = {2009},
−
rounds of the similar hash function Maelstrom. Additionally, we apply the
+
  note = {To appear}
−
rebound attack to the SHA-3 submission Grøstl, which leads to an attack on
+
  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 compression function, as well as an improved known-key distinguisher for 7 rounds of the AES block cipher and the internal permutation used in ECHO.}
−
6 rounds of the Grøstl-256 compression function with a complexity of $2^{120}$
 
−
and memory requirements of about $2^{64}$.}
 
 
</bibtex>
 
</bibtex>

Revision as of 17:52, 29 July 2009

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: Grostl.zip


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


2 Cryptanalysis

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
observation block cipher all Barreto
observation hash all Kelsey
semi-free-start collision compression 256 6 rounds 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression 256 6 rounds 264 264 Mendel,Peyrin,Rechberger,Schläffer
semi-free-start collision compression 256 7 rounds 2112 264 Mendel,Peyrin,Rechberger,Schläffer

A description of this table is given here.


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

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

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=107049
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

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 ,2009
http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=106996
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
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Groestl&oldid=3199"