Difference between revisions of "ECHO"

From The ECRYPT Hash Function Website
(added eprint 2010/569)
(→‎Cryptanalysis)
Line 28: Line 28:
  
  
 +
                                                                   
 +
                                                                   
 +
                                                                   
 +
                                           
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
Line 44: Line 48:
 
| 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]
+
| collision<sup>(1)</sup> || 256 || 5 rounds || 2<sup>112</sup> || 2<sup>85.3</sup> || [http://eprint.iacr.org/2010/588.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]
 
−
|-
 
 
|}                     
 
|}                     
 +
 +
<sup>(1)</sup> In this attack some problems in the [http://eprint.iacr.org/2010/321.pdf previous attacks] (pointed out by [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]) have been corrected.
  
  
Line 63: Line 65:
 
| 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<sup>(1)</sup> (chosen salt) || compression function || 256 || 7 rounds || 2<sup>160</sup> || 2<sup>128</sup> || [http://eprint.iacr.org/2010/588.pdf Schläffer]
 +
|-                   
 +
| free-start collision<sup>(1)</sup> (chosen salt) || compression function || 256 || 6 rounds || 2<sup>160</sup> || 2<sup>128</sup> || [http://eprint.iacr.org/2010/588.pdf Schläffer]
 +
|-
 
| semi-free-start collision || compression function || 256 || 4 rounds || 2<sup>52</sup> || 2<sup>16</sup> || [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]
 
| semi-free-start collision || compression function || 256 || 4 rounds || 2<sup>52</sup> || 2<sup>16</sup> || [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]
 
|-   
 
|-   
−
| 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 89: Line 87:
 
|}   
 
|}   
  
 +
<sup>(1)</sup> In this attack some problems in the [http://eprint.iacr.org/2010/321.pdf previous attacks] (pointed out by [http://eprint.iacr.org/2010/569.pdf Jean,Fouque]) have been corrected.
 +
 +
 +
<bibtex>
 +
@misc{cryptoeprint:2010:588,
 +
    author = {Martin Schläffer},
 +
    title = {Improved Collisions for Reduced ECHO-256},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/588},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/588.pdf},
 +
    abstract = {In this work, we present a collision attack on 5 out of 8 rounds of the ECHO-256 hash function with a complexity of $2^{112}$ in time and $2^{85.3}$ memory. In this work, we further show that the merge inbound phase can still be solved in the case of hash function attacks on ECHO. As correctly observed by Jean et al., the merge inbound phase of previous hash function attacks succeeds only with a probability of $2^{-128}$. The main reason for this behavior is the low rank of the linear SuperMixColumns transformation. However, since there is enough freedom in ECHO we can solve the resulting linear equations with a complexity much lower than $2^{128}$. On the other hand, also this low rank of the linear SuperMixColumns transformation allows us to extend the collision attack on the reduced hash function from 4 to 5 rounds. Additionally, we present a collision attack on 6 rounds of the compression function of ECHO-256 and show that a subspace distinguisher is still possible for 7 out of 8 rounds of the compression function of ECHO-256. Both compression function attacks have a complexity of $2^{160}$ with memory requirements of $2^{128}$ and chosen salt.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Revision as of 15:26, 7 December 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
collision(1) 256 5 rounds 2112 285.3 Schläffer

(1) In this attack some problems in the previous attacks (pointed out by Jean,Fouque) have been corrected.


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(1) (chosen salt) compression function 256 7 rounds 2160 2128 Schläffer
free-start collision(1) (chosen salt) compression function 256 6 rounds 2160 2128 Schläffer
semi-free-start collision compression function 256 4 rounds 252 216 Jean,Fouque
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

(1) In this attack some problems in the previous attacks (pointed out by Jean,Fouque) have been corrected.


Martin Schläffer - Improved Collisions for Reduced ECHO-256

,2010
http://eprint.iacr.org/2010/588.pdf
Bibtex
Author : Martin Schläffer
Title : Improved Collisions for Reduced ECHO-256
In : -
Address :
Date : 2010

Jérémy Jean, Pierre-Alain Fouque - Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function

,2010
http://eprint.iacr.org/2010/569.pdf
Bibtex
Author : Jérémy Jean, Pierre-Alain Fouque
Title : Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function
In : -
Address :
Date : 2010

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

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
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=ECHO&oldid=3653"