Difference between revisions of "ECHO"

From The ECRYPT Hash Function Website
m
(Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function)
Line 44: 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  
 
|-                     
 
|-                     
−
| || || || || ||
+
| distinguisher || 256 || 5 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 
|-                     
 
|-                     
 +
| near-collision|| 256 || 4.5 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-                   
 +
| collision|| 256 || 4 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-
 
|}                     
 
|}                     
  
Line 59: Line 63:
 
| 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 (chosen salt) || compression function || 256 || 7 rounds || 2<sup>107</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-                   
 +
| free-start near-collision (chosen salt) || compression function || 256 || 6.5 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-
 +
| distinguisher (chosen salt) || compression function || 512 || 7 rounds || 2<sup>106</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-                   
 +
| free-start near-collision (chosen salt) || compression function || 512|| 6.5 rounds || 2<sup>96</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/321.pdf Schläffer]
 +
|-                   
 
| semi-free-start collision || compression function || 256 || 3 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
| semi-free-start collision || compression function || 256 || 3 rounds || 2<sup>64</sup> || 2<sup>64</sup> || [http://eprint.iacr.org/2010/223.pdf Peyrin]
 
|-                   
 
|-                   
Line 121: Line 133:
 
rounds of the AES block cipher and the internal permutation used in
 
rounds of the AES block cipher and the internal permutation used in
 
ECHO.}
 
ECHO.}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2010:321,
 +
    author = {Martin Schläffer},
 +
    title = {Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/321},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/321.pdf},
 +
    abstract = {In this work we present the first results for the ECHO hash function. We provide a subspace distinguisher for 5/8 rounds, near-collisions on 4.5/8 rounds and collisions for 4/8 rounds of the ECHO-256 hash function. The complexities are $2^{96}$ compression function calls for the distinguisher and near-collision attack, and $2^{64}$ for the collision attack. The memory requirements are $2^{64}$ for all attacks. Furthermore, we provide improved compression function attacks on ECHO-256 to get a distinguisher on 7/8 rounds and near-collisions for 6.5/8 rounds with chosen salt. The compression function attacks also apply to ECHO-512. To get these results, we consider new and sparse truncated differential paths through ECHO. We are able to construct these paths by analyzing the combined MixColumns and BigMixColumns transformation. Since in these sparse truncated differential paths at most 1/4 of all bytes of each ECHO state are active, missing degrees of freedom are not a problem. Therefore, we are able to mount a rebound attack with multiple inbound phases to efficiently find according message pairs for ECHO.},
 +
}
 
</bibtex>
 
</bibtex>

Revision as of 14:34, 5 July 2010

1 The algorithm


Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin - SHA-3 Proposal: ECHO

,2009
http://crypto.rd.francetelecom.com/echo/doc/echo_description_1-5.pdf
Bibtex
Author : Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
Title : SHA-3 Proposal: ECHO
In : -
Address :
Date : 2009

Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin - SHA-3 Proposal: ECHO

,2008
http://crypto.rd.francetelecom.com/echo/doc/echo_description.pdf
Bibtex
Author : Ryad Benadjila, Olivier Billet, Henri Gilbert, Gilles Macario-Rat, Thomas Peyrin, Matt Robshaw, Yannick Seurin
Title : SHA-3 Proposal: ECHO
In : -
Address :
Date : 2008


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.

Recommended security parameter: 8 rounds (n=224,256); 10 rounds (n=384,512)

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.

Type of Analysis Hash Size (n) Parameters Compression Function Calls Memory Requirements Reference
distinguisher 256 5 rounds 296 264 Schläffer
near-collision 256 4.5 rounds 296 264 Schläffer
collision 256 4 rounds 264 264 Schläffer


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).

Type of Analysis Hash Function Part Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
distinguisher (chosen salt) compression function 256 7 rounds 2107 264 Schläffer
free-start near-collision (chosen salt) compression function 256 6.5 rounds 296 264 Schläffer
distinguisher (chosen salt) compression function 512 7 rounds 2106 264 Schläffer
free-start near-collision (chosen salt) compression function 512 6.5 rounds 296 264 Schläffer
semi-free-start collision compression function 256 3 rounds 264 264 Peyrin
distinguisher compression function 256 4 rounds 264 264 Peyrin
semi-free-start collision compression function 512 3 rounds 296 264 Peyrin
distinguisher compression function 512 6 rounds 296 264 Peyrin
distinguisher permutation all 8 rounds 2768 2512 Gilbert,Peyrin
distinguisher permutation all 7 rounds 2384 264 Mendel,Peyrin,Rechberger,Schläffer
distinguisher permutation all 7 rounds 2896 - 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, 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

Martin Schläffer - Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function

,2010
http://eprint.iacr.org/2010/321.pdf
Bibtex
Author : Martin Schläffer
Title : Subspace Distinguisher for 5/8 Rounds of the ECHO-256 Hash Function
In : -
Address :
Date : 2010
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=ECHO&oldid=3520"