Difference between revisions of "CubeHash"

From The ECRYPT Hash Function Website
m (updated link to round 2 submission)
(separate cryptanalysis tables)
Line 40: Line 40:
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
 +
 +
We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.
 +
A description of the following tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 +
 +
=== Hash function ===
 +
 +
Here we list results on the actual hash function. The only allowed modification is to change the security parameter.
 +
 +
Recommended security parameter: r/b = '''16/32'''
  
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
|- 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 Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference  
 
|-                     
 
|-                     
−
| style="background:greenyellow" | preimage || hash || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+
| style="background:greenyellow" | preimage || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 
|-           
 
|-           
−
| multi-collision ||  || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+
| multi-collision || all ||  || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 
|-                     
 
|-                     
−
| observations ||  || all ||  ||  ||  || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+
| observations || all ||  ||  ||  || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 
|-           
 
|-           
−
| style="background:greenyellow" | preimage || hash || 512 ||  || 2<sup>511</sup> || 2<sup>508</sup> || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
+
| style="background:greenyellow" | preimage || 512 ||  || 2<sup>511</sup> || 2<sup>508</sup> || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 
|-                     
 
|-                     
−
| preimage || hash || 512 || r/4 || 2<sup>496</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
+
| preimage || 512 || r/4 || 2<sup>496</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 
|-                     
 
|-                     
−
| preimage || hash || 512 || r/8 || 2<sup>480</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
+
| preimage || 512 || r/8 || 2<sup>480</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolić,Weinmann]
 
|-                     
 
|-                     
−
| collision || hash || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
+
| collision || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
 
|-     
 
|-     
−
| collision || hash || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
+
| collision || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
 
|-     
 
|-     
−
| collision || hash || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 
|-
 
|-
−
| collision || hash || all || 2/3 || 2<sup>46</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || all || 2/3 || 2<sup>46</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 
|-
 
|-
−
| collision || hash || 384/512 || 4/4 || 2<sup>189</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || 384,512 || 4/4 || 2<sup>189</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 
|-
 
|-
−
| collision || hash || 512 || 4/3 || 2<sup>207</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || 512 || 4/3 || 2<sup>207</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 
|-                       
 
|-                       
−
| collision || hash || all || 3/64 || 2<sup>89</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || all || 3/64 || 2<sup>89</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
−
|-            
+
|-          
−
| collision || hash || 512 || 5/64 || 2<sup>231</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
+
| collision || 512 || 5/64 || 2<sup>231</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 
|-                     
 
|-                     
−
| collision || hash || 512 || 2/2 || 2<sup>196</sup> || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
+
| collision || 512 || 2/2 || 2<sup>196</sup> || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
 
|-  
 
|-  
−
| collision || hash || all || 3/64 || example (2<sup>24</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
+
| collision || all || 3/64 || example (2<sup>24</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
 
|-  
 
|-  
−
| collision || hash || all || 4/64 || example (2<sup>34</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt Brier,Khazaei,Meier,Peyrin]
+
| collision || all || 4/64 || example (2<sup>34</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt Brier,Khazaei,Meier,Peyrin]
 
|-  
 
|-  
−
| collision || hash || all || 4/48 || example (2<sup>37</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt Brier,Khazaei,Meier,Peyrin]
+
| collision || all || 4/48 || example (2<sup>37</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt Brier,Khazaei,Meier,Peyrin]
 
|-  
 
|-  
−
| collision || hash || 512 || 7/64 || 2<sup>203</sup> || - || [http://eprint.iacr.org/2009/382.pdf Brier,Khazaei,Meier,Peyrin]
+
| collision || 512 || 7/64 || 2<sup>203</sup> || - || [http://eprint.iacr.org/2009/382.pdf Brier,Khazaei,Meier,Peyrin]
 
|-
 
|-
−
| observations ||  || all ||  ||  ||  || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
+
| observations || all ||  ||  ||  || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
 
|-
 
|-
 
|}                     
 
|}                     
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
+
 
 +
=== 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).  
 +
 
 +
 
  
  

Revision as of 21:29, 29 January 2010

1 The algorithm


Daniel J. Bernstein - CubeHash specification (2.B.1)

,2009
http://cubehash.cr.yp.to/submission2/spec.pdf
Bibtex
Author : Daniel J. Bernstein
Title : CubeHash specification (2.B.1)
In : -
Address :
Date : 2009

Daniel J. Bernstein - CubeHash parameter tweak: 16 times faster

,2009
http://cubehash.cr.yp.to/submission/tweak.pdf
Bibtex
Author : Daniel J. Bernstein
Title : CubeHash parameter tweak: 16 times faster
In : -
Address :
Date : 2009

Daniel J. Bernstein - CubeHash Specification (2.B.1)

,2008
http://cubehash.cr.yp.to/submission/spec.pdf
Bibtex
Author : Daniel J. Bernstein
Title : CubeHash Specification (2.B.1)
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 following tables is given here.


2.1 Hash function

Here we list results on the actual hash function. The only allowed modification is to change the security parameter.

Recommended security parameter: r/b = 16/32

Type of Analysis Hash Size (n) Parameters/Variants Compression Function Calls Memory Requirements Reference
preimage all 2513-4b ? Aumasson,Meier,Naya-Plasencia,Peyrin
multi-collision all 2513-4b ? Aumasson,Meier,Naya-Plasencia,Peyrin
observations all Aumasson,Meier,Naya-Plasencia,Peyrin
preimage 512 2511 2508 Khovratovich,Nikolić,Weinmann
preimage 512 r/4 2496 - Khovratovich,Nikolić,Weinmann
preimage 512 r/8 2480 - Khovratovich,Nikolić,Weinmann
collision 512 2/120 example - Aumasson
collision 512 1/45, 2/89 example - Dai
collision 512 2/4 example - Brier,Peyrin
collision all 2/3 246 - Brier,Peyrin
collision 384,512 4/4 2189 - Brier,Peyrin
collision 512 4/3 2207 - Brier,Peyrin
collision all 3/64 289 - Brier,Peyrin
collision 512 5/64 2231 - Brier,Peyrin
collision 512 2/2 2196 - Brier,Khazaei,Meier,Peyrin
collision all 3/64 example (224) - Brier,Khazaei,Meier,Peyrin
collision all 4/64 example (234) - Brier,Khazaei,Meier,Peyrin
collision all 4/48 example (237) - Brier,Khazaei,Meier,Peyrin
collision 512 7/64 2203 - Brier,Khazaei,Meier,Peyrin
observations all Bloom,Kaminsky


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



Jean-Philippe Aumasson, Eric Brier, Willi Meier, María Naya-Plasencia, Thomas Peyrin - Inside the Hypercube

ACISP 5594:202-213,2009
http://www.131002.net/data/papers/ABMNP08.pdf
Bibtex
Author : Jean-Philippe Aumasson, Eric Brier, Willi Meier, María Naya-Plasencia, Thomas Peyrin
Title : Inside the Hypercube
In : ACISP -
Address :
Date : 2009

Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann - Preimage attack on CubeHash512-r/4 and CubeHash512-r/8

,2008
http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf
Bibtex
Author : Dmitry Khovratovich, Ivica Nikolić, Ralf-Philipp Weinmann
Title : Preimage attack on CubeHash512-r/4 and CubeHash512-r/8
In : -
Address :
Date : 2008

Jean-Philippe Aumasson - Collision for CubeHash2/120-512

,2008
http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt
Bibtex
Author : Jean-Philippe Aumasson
Title : Collision for CubeHash2/120-512
In : -
Address :
Date : 2008

Wei Dai - Collisions for CubeHash1/45 and CubeHash2/89

,2008
http://www.cryptopp.com/sha3/cubehash.pdf
Bibtex
Author : Wei Dai
Title : Collisions for CubeHash1/45 and CubeHash2/89
In : -
Address :
Date : 2008

Eric Brier, Thomas Peyrin - Cryptanalysis of CubeHash

,2009
http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf
Bibtex
Author : Eric Brier, Thomas Peyrin
Title : Cryptanalysis of CubeHash
In : -
Address :
Date : 2009

Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin - Attack for CubeHash-2/2 and collision for CubeHash-3/64

,2009
http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt
Bibtex
Author : Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin
Title : Attack for CubeHash-2/2 and collision for CubeHash-3/64
In : -
Address :
Date : 2009

Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin - Real Collisions for CubeHash-4/64

,2009
http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt
Bibtex
Author : Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin
Title : Real Collisions for CubeHash-4/64
In : -
Address :
Date : 2009

Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin - Real Collisions for CubeHash-4/48

,2009
http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt
Bibtex
Author : Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin
Title : Real Collisions for CubeHash-4/48
In : -
Address :
Date : 2009

Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin - Linearization Framework for Collision Attacks: Application to CubeHash and MD6

,2009
http://eprint.iacr.org/2009/382.pdf
Bibtex
Author : Eric Brier, Shahram Khazaei, Willi Meier, Thomas Peyrin
Title : Linearization Framework for Collision Attacks: Application to CubeHash and MD6
In : -
Address :
Date : 2009

Benjamin Bloom, Alan Kaminsky - Single Block Attacks and Statistical Tests on CubeHash

,2009
Bibtex
Author : Benjamin Bloom, Alan Kaminsky
Title : Single Block Attacks and Statistical Tests on CubeHash
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=CubeHash&oldid=3317"