Difference between revisions of "ECHO"

From The ECRYPT Hash Function Website
m
(→‎Building blocks: added Sasaki et al.)
 
(3 intermediate revisions by the same user not shown)
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 62: Line 64:
 
|- 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 || permutation || 256 || 8 rounds || 2<sup>151</sup> || 2<sup>67</sup> || [http://eprint.iacr.org/2010/607.pdf Naya-Plasencia]
 
|-  
 
|-  
−
| 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]
+
| distinguisher || permutation || 224,256 || 8 rounds || 2<sup>182</sup> || 2<sup>37</sup> || [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf Sasaki,Li,Wang,Sakayima,Ohta]
 +
|-
 +
| 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 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]
+
| 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]
 
|-
 
|-
−
| 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]
+
| 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]
−
|-                  
+
|-  
−
| 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 87: Line 91:
 
|}   
 
|}   
  
−
      
+
<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:607,
 +
     author = {María Naya-Plasencia},
 +
    title = {Scrutinizing rebound attacks: new algorithms for improving the complexities},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/607},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/607.pdf},
 +
    abstract = {Rebound attacks are a state-of-the-art analysis method for hash functions. These cryptanalysis methods are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this paper we study rebound attacks in detail and find for a great number of cases, that complexities of existing attacks can be improved. This is done by determining problems that adapt optimally to the cryptanalytic situation, and by using better algorithms to follow the differential path. These improvements are essentially based on merging big lists in a more efficient way, as well as on new ideas on how to reduce the complexities. As a result, we introduce general purpose new algorithms for enabling further rebound analysis to be as performant as possible. We illustrate our new algorithms for real hash functions and demonstrate how to reduce the complexities of the best known analysis on five hash functions: JH, Grøstl, ECHO, Luffa and Lane (the first four are round two SHA-3 candidates).},
 +
}
 +
</bibtex>
 +
 
 +
<bibtex>
 +
@misc{groestlechoSLWSO10,
 +
  author = {Yu Sasaki and Yang Li and Lei Wang and Kazuo Sakiyama and Kazuo Ohta},
 +
  title = {New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
 +
},
 +
  howpublished = {Second SHA-3 Candidate Conference},
 +
  year = {2010},
 +
  url = {http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf},
 +
  abstract = {In this paper, we present non-full-active Super-Sbox analysis which can detect non-ideal
 +
properties of a class of AES-based permutations with a low complexity. We apply this framework
 +
to SHA-3 round-2 candidates ECHO and Grøstl. The first application is for the full-round (8-round)
 +
ECHO permutation, which is a building block for 256-bit and 224-bit output sizes. By combining several
 +
observations specific to ECHO, our attack detects a non-ideal property with a time complexity of 2^182
 +
and 2^37 amount of memory. The complexity, especially in terms of the product of time and memory,
 +
is drastically reduced from the previous best attack which required 2^512 x 2^512. To the best of our knowledge, this is the first result on the full-round ECHO permutation with both time and memory below 2^256 or 2^224. Note that this result does not impact the security of the ECHO compression function nor the overall hash function. We also show that our method can detect non-ideal properties of the 8-round Grøstl-256 permutation with a practical complexity, and finally show that our approach leads
 +
to an improvement on a semi-free-start collision attack on the 7-round Grøstl-512 compression function.
 +
Our approach is based on a series of attacks on AES-based hash functions such as rebound attack and
 +
Super-Sbox analysis. The core idea is using a new differential path consisting of only non-full-active
 +
states.}
 +
}
 +
</bibtex>
 +
 
 +
<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>
 +
@misc{cryptoeprint:2010:569,
 +
    author = {Jérémy Jean and Pierre-Alain Fouque},
 +
    title = {Practical Near-Collisions and Collisions on Round-Reduced ECHO-256 Compression Function},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/569},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/569.pdf},
 +
    abstract = {In this paper, we present new results on the second-round SHA-3 candidate ECHO. We describe a method to construct a collision in the compression function of ECHO-256 reduced to four rounds in 2^52 operations on AES-columns without significant memory requirements. Our attack uses the most recent analyses on ECHO, in particular the SuperSBox and SuperMixColumns layers to utilize efficiently the available freedom degrees. We also show why some of these results are flawed and we propose a solution to fix them. Our work improve the time and memory complexity of previous known techniques by using available freedom degrees more precisely. Finally, we validate our work by an implementation leading to near-collisions in 2^36 operations.},
 +
}
 +
</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>           
 
<bibtex>           
Line 133: Line 208:
 
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>

Latest revision as of 14:43, 8 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 permutation 256 8 rounds 2151 267 Naya-Plasencia
distinguisher permutation 224,256 8 rounds 2182 237 Sasaki,Li,Wang,Sakayima,Ohta
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.


María Naya-Plasencia - Scrutinizing rebound attacks: new algorithms for improving the complexities

,2010
http://eprint.iacr.org/2010/607.pdf
Bibtex
Author : María Naya-Plasencia
Title : Scrutinizing rebound attacks: new algorithms for improving the complexities
In : -
Address :
Date : 2010

Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta - New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl

,2010
http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf
Bibtex
Author : Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta
Title : New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
In : -
Address :
Date : 2010

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=3663"