Difference between revisions of "CubeHash"

From The ECRYPT Hash Function Website
m
m (→‎Building blocks: dashes added)
 
(25 intermediate revisions by 3 users not shown)
Line 3: Line 3:
 
* Author(s): Dan Bernstein  
 
* Author(s): Dan Bernstein  
 
* Website: [http://cubehash.cr.yp.to/ http://cubehash.cr.yp.to/]  
 
* Website: [http://cubehash.cr.yp.to/ http://cubehash.cr.yp.to/]  
−
* NIST submission package: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/CubeHash.zip CubeHash.zip]
+
* NIST submission package:
 +
** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/CubeHash.zip CubeHash.zip]
 +
** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/CubeHash_Round2.zip CubeHash_Round2.zip]
  
 +
 +
<bibtex>
 +
@misc{sha3Bernstein09a,
 +
  author    = {Daniel J. Bernstein},
 +
  title    = {CubeHash specification (2.B.1)},
 +
  url        = {http://cubehash.cr.yp.to/submission2/spec.pdf},
 +
  howpublished = {Submission to NIST (Round 2)},
 +
  year      = {2009},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{sha3Bernstein09,
 +
  author    = {Daniel J. Bernstein},
 +
  title    = {CubeHash parameter tweak: 16 times faster},
 +
  url        = {http://cubehash.cr.yp.to/submission/tweak.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2009},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 11: Line 33:
 
   title    = {CubeHash Specification (2.B.1)},
 
   title    = {CubeHash Specification (2.B.1)},
 
   url        = {http://cubehash.cr.yp.to/submission/spec.pdf},
 
   url        = {http://cubehash.cr.yp.to/submission/spec.pdf},
−
   howpublished = {Submission to NIST},
+
   howpublished = {Submission to NIST (Round 1)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
Line 19: Line 41:
 
== Cryptanalysis ==
 
== Cryptanalysis ==
  
−
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
+
We distinguish between two cases: results on the complete hash function, and results on underlying building blocks.
 +
 
 +
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 +
 
 +
Recommended security parameters: r/b = '''16/32''' (n=224,256); '''16/32''' (n=384,512)
 +
 
 +
=== 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.
 +
 
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" 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 || 384,512 || r/32 || 2<sup>383.7</sup> || - || [http://eprint.iacr.org/2010/273.pdf Ferguson,Lucks,McKay]
 +
|-
 +
| preimage || 384,512 || r/33 || 2<sup>257.6</sup> || - || [http://eprint.iacr.org/2010/273.pdf Ferguson,Lucks,McKay]
 +
|-
 +
| collision || 512 || 7/64 || 2<sup>203</sup> || - || [http://eprint.iacr.org/2009/382.pdf 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 || 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 || 3/64 || example (2<sup>24</sup>) || - || [http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt Brier,Khazaei,Meier,Peyrin]
 
|-                     
 
|-                     
−
| style="background:greenyellow" | preimage || hash || all || || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,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]
−
|-        
+
|-           
−
| multi-collision ||  || all || || 2<sup>513-4b</sup> || ? || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+
| collision || 512 || 5/64 || 2<sup>231</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 || 512 || 4/3 || 2<sup>207</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 || all || 2/3 || 2<sup>46</sup> || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 +
|-   
 +
| collision || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf Brier,Peyrin]
 +
|-   
 +
| collision || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
 
|-                     
 
|-                     
−
| observations || || all ||  || || || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+
| collision || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
−
|-         
 
−
| 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]
 
 
|-                     
 
|-                     
−
| 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/8 || 2<sup>480</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',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/4 || 2<sup>496</sup> || - || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',Weinmann]
 +
|-         
 +
| style="background:greenyellow" | preimage || 512 || r/1 (round 1) || 2<sup>511</sup> || 2<sup>508</sup> || [http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf Khovratovich,Nikolic',Weinmann]
 
|-                     
 
|-                     
−
| collision || hash || 512 || 2/120 || example || - || [http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt Aumasson]
+
| style="background:greenyellow" | preimage || all || r/b || 2<sup>513-4b</sup> || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
−
|-    
+
|-
−
| collision || hash || 512 || 1/45, 2/89 || example || - || [http://www.cryptopp.com/sha3/cubehash.pdf Dai]
+
| collision || all || r/b || 2<sup>521-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
−
|-  
 
−
| collision || hash || 512 || 2/4 || example || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
 
 
|-
 
|-
−
| collision || hash || 512 || 2/3 || 2<sup>46</sup> || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
+
| style="background:greenyellow" | preimage || all || r/b || 2<sup>522-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
 
|-
 
|-
−
| collision || hash || 512 || 4/4 || 2<sup>189</sup> || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
+
|}                   
 +
 
 +
 
 +
=== 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).
 +
 
 +
{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"                 
 +
|- style="background:#efefef;"                 
 +
| Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||  Reference
 +
|- 
 +
| quantum preimage || hash || 512 || || 2<sup>192</sup> || - || [http://eprint.iacr.org/2008/506.pdf Leurent]
 +
|- 
 +
| distinguisher || permutation|| all  || 14 rounds  || 2<sup>812</sup> || - || [http://eprint.iacr.org/2010/535.pdf Ashur,Dunkelman]
 +
|-   
 +
| distinguisher || permutation|| all  || 11 rounds  || 2<sup>470</sup> || - || [http://eprint.iacr.org/2010/535.pdf Ashur,Dunkelman]
 +
|- 
 +
|  observations || hash || all ||  || - || - || [http://eprint.iacr.org/2010/262.pdf Kaminsky]
 
|-
 
|-
−
| collision || hash || 512 || 4/3 || 2<sup>207</sup> || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
+
| observations || hash || all || || - || - || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
−
|-                     
 
−
| collision || hash || 512 || 3/64 || 2<sup>89</sup> || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
 
 
|-             
 
|-             
−
| collision || hash || 512 || 5/64 || 2<sup>231</sup> || - || [http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf Brier,Peyrin]
+
| multi-collision || hash || all  || || 2<sup>513-4b</sup> || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 
|-                     
 
|-                     
 +
| observations || permutation|| all  ||  || - || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 +
|-         
 
|}                     
 
|}                     
  
−
A description of this table is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
  
 +
<bibtex>
 +
@misc{cubehashLeu10,
 +
    author = {Gaëtan Leurent},
 +
    title = {Quantum Preimage and Collision Attacks on CubeHash},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/506},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/506.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abtract = {In this short note we show a quantum preimage attack on CubeHash-normal-512 with complexity 2^192. This kind of attack is expected to cost 2^256 for a good 512-bit hash function, and we argue that this violates the expected security of CubeHash. The preimage attack can also be used as a collision attack, given that a generic quantum collision attack on a 512-bit hash function require 2^256 operations, as explained in the CubeHash submission document.
 +
This attack only use very simple techniques: we use the symmetry properties of CubeHash which were already described in the submission document and have been analyzed in detail later, together with Gover's algorithm which is also discussed in the submission document.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashAD10,
 +
    author = {Tomer Ashur and Orr Dunkelman},
 +
    title = {Linear Analysis of Reduced-Round CubeHash},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/535},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/535.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abtract = {Recent developments in the field of cryptanalysis of hash functions has inspired NIST to announce a competition for selecting a new cryptographic hash function to join the SHA family of standards. One of the 14 second-round candidates is CubeHash designed by Daniel J. Bernstein. CubeHash is a unique hash function in the sense that it does not iterate a common compression function, and offers a structure which resembles a sponge function, even though it is not exactly a sponge function. In this paper we analyze reduced-round variants of CubeHash where the adversary controls the full 1024-bit input to reduced-round CubeHash and can observe its full output. We show that linear approximations with high biases exist in reduced-round variants. For example, we present an 11-round linear approximation with bias of 2^{&#8722;235}, which allows distinguishing 11-round CubeHash using about 2^{470} queries. We also discuss the extension of this distinguisher to 12 rounds using message modification techniques. Finally, we present a linear distinguisher for 14-round CubeHash which uses about 2^{812} queries.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashFLM10,
 +
    author = {Niels Ferguson and Stefan Lucks and Kerry A. McKay},
 +
    title = {Symmetric States and their Structure:  Improved Analysis of CubeHash},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/273},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/273.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abtract = {This paper provides three improvements over previous work on analyzing CubeHash, based on its classes of symmetric states: (1) We present a detailed analysis of the hierarchy of symmetry classes. (2) We point out some flaws in previously claimed attacks which tried to exploit the symmetry classes. (3) We present and analyze new multicollision and preimage attacks. For the default parameter setting of CubeHash, namely for a message block size of b = 32, the new attacks are slightly faster than 2^384 operations. If one increases the size of a message block by a single byte to b = 33, our multicollision and preimage attacks become much faster – they only require about 2^256 operations. This demonstrates how sensitive the security of CubeHash is, depending on minor changes of the tunable security parameter b. }
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashKam10,
 +
    author = {Alan Kaminsky},
 +
    title = {Cube Test Analysis of the Statistical Behavior of CubeHash and Skein},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/262},
 +
    year = {2010},
 +
    url = {http://eprint.iacr.org/2010/262.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abstract = {This work analyzes the statistical properties of the SHA-3 candidate cryptographic hash algorithms CubeHash and Skein to try to find nonrandom behavior. Cube tests were used to probe each algorithm's internal polynomial structure for a large number of choices of the polynomial input variables. The cube test data were calculated on a 40-core hybrid SMP cluster parallel computer. The cube test data were subjected to three statistical tests: balance, independence, and off-by-one. Although isolated statistical test failures were observed, the balance and off-by-one tests did not find nonrandom behavior overall in either CubeHash or Skein. However, the independence test did find nonrandom behavior overall in both CubeHash and Skein. }
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashBK09,
 +
    author = {Benjamin Bloom and Alan Kaminsky},
 +
    title = {Single Block Attacks and Statistical Tests on CubeHash},
 +
    howpublished = {Cryptology ePrint Archive, Report 2009/407},
 +
    year = {2009},
 +
    url = {http://eprint.iacr.org/2009/407.pdf},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    abstract = {This paper describes a second preimage attack on the CubeHash cryptographic one-way hash function. The attack finds a second preimage in less time than brute force search for these CubeHash variants: CubeHash $r$/$b$-224 for $b > 100$; CubeHash$r$/$b$-256 for $b > 96$; CubeHash$r$/$b$-384 for $b > 80$; and CubeHash$r$/$b$-512 for $b > 64$. However, the attack does not break the CubeHash variants recommended for SHA-3. The attack requires minimal memory and can be performed in a massively parallel fashion. This paper also describes several statistical randomness tests on CubeHash. The tests were unable to disprove the hypothesis that CubeHash behaves as a random mapping. These results support CubeHash's viability as a secure cryptographic hash function.},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{cubehashAMPP08,
+
@misc{cubehashBKMP09b,
−
  author   = {Jean-Philippe Aumasson and Willi Meier and María Naya-Plasencia and Thomas Peyrin},
+
    author = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
−
  title    = {Inside the Hypercube},
+
    title = {Linearization Framework for Collision Attacks: Application to CubeHash and MD6},
−
  url       = {http://eprint.iacr.org/2008/486.pdf},
+
     howpublished = {Cryptology ePrint Archive, Report 2009/382},
−
  howpublished = {Cryptology ePrint Archive, Report 2008/486},
+
    year = {2009},
−
  year      = {2008},
+
    url = {http://eprint.iacr.org/2009/382.pdf},
−
  abstract = {Bernstein’s CubeHash is a hash function family that includes four functions submitted to the NIST Hash Competition. A CubeHash function is parametrized by a number of rounds r, a block byte size b, and a digest bit length h. The 1024-bit internal state of CubeHash is represented as a five-dimension hypercube. Submissions to NIST have r = 8, b = 1, and $h \in {224, 256, 384, 512}$.  
+
    note = {\url{http://eprint.iacr.org/}},
−
This paper gives the first external analysis of CubeHash, with
+
    abstract = {In this paper, an improved differential cryptanalysis framework for finding collisions in hash functions is provided. Its principle is based on linearization of compression functions in order to find low weight differential characteristics as initiated by Chabaud and Joux. This is formalized and refined however in several ways: for the problem of finding a conforming message pair whose differential trail follows a linear trail, a condition function is introduced so that finding a collision is equivalent to finding a preimage of the zero vector for the condition function. Then, the dependency table concept shows how much influence every input bit of the condition function has on its output bits. Careful analysis of the dependency table reveals degrees of freedom that can be exploited in accelerated preimage reconstruction of the condition function. These concepts are applied to an in-depth collision analysis of reduced-round versions of the two SHA-3 candidates CubeHash and MD6, and are demonstrated to give by far the best currently known collision attacks on these SHA-3 candidates.},
−
- improved standard generic attacks for collisions and preimages
 
−
- a multicollision attack that exploits fixed points
 
−
- a study of the round function symmetries
 
−
- a preimage attack that exploits these symmetries
 
−
- a practical collision attack on a weakened version of CubeHash
 
−
- high-probability truncated differentials over the 8-round transform
 
−
Our results do not contradict the security claims about CubeHash.},
 
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{cubehashKNW08,
+
@misc{cubehashBKMP09a,
−
   author    = {Dmitry Khovratovich and Ivica Nikolić and Ralf-Philipp Weinmann},
+
   author    = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
−
   title    = {Preimage attack on CubeHash512-r/4 and CubeHash512-r/8},
+
   title    = {Real Collisions for CubeHash-4/48},
−
   url       = {http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf},
+
   url = {http://ehash.iaik.tugraz.at/uploads/5/50/Bkmp_ch448.txt},  
−
   howpublished = {Available online},
+
   howpublished = {NIST mailing list (local link)},
−
   year     = {2008},
+
   year = {2009},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{cubehashA08,
+
@misc{cubehashBKMP09a,
−
   author    = {Jean-Philippe Aumasson},
+
   author    = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
−
   title    = {Collision for CubeHash2/120-512},
+
   title    = {Real Collisions for CubeHash-4/64},
−
   url = {http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt},  
+
   url = {http://ehash.iaik.tugraz.at/uploads/9/93/Bkmp_ch464.txt},  
 
   howpublished = {NIST mailing list (local link)},
 
   howpublished = {NIST mailing list (local link)},
−
   year = {2008},
+
   year = {2009},
 
}
 
}
 
</bibtex>
 
</bibtex>
  
 
<bibtex>
 
<bibtex>
−
@misc{cubehashD08,
+
@misc{cubehashBKMP09,
−
   author    = {Wei Dai},
+
   author    = {Eric Brier and Shahram Khazaei and Willi Meier and Thomas Peyrin},
−
   title    = {Collisions for CubeHash1/45 and CubeHash2/89},
+
   title    = {Attack for CubeHash-2/2 and collision for CubeHash-3/64},
−
   url = {http://www.cryptopp.com/sha3/cubehash.pdf},  
+
   url = {http://ehash.iaik.tugraz.at/uploads/3/3a/Peyrin_ch22_ch364.txt},  
−
   howpublished = {Available online},
+
   howpublished = {NIST mailing list (local link)},
−
   year = {2008},
+
   year = {2009},
−
  abstract = {Collisions were found for the hash functions CubeHash1/45-512 and CubeHash2/89-512. Attack code is included.},
 
 
}
 
}
 
</bibtex>
 
</bibtex>
Line 121: Line 245:
 
   author    = {Eric Brier and Thomas Peyrin},
 
   author    = {Eric Brier and Thomas Peyrin},
 
   title    = {Cryptanalysis of CubeHash},
 
   title    = {Cryptanalysis of CubeHash},
−
   url = {http://thomas.peyrin.googlepages.com/Brier_Peyrin_cubehash.pdf},  
+
   url = {http://thomas.peyrin.googlepages.com/BrierPeyrinCubehash.pdf},  
 
   howpublished = {Available online},
 
   howpublished = {Available online},
 
   year = {2009},
 
   year = {2009},
 
   abstract = {CubeHash is a family of hash functions submitted by Bern stein as a SHA-3 candidate. In this paper, we provide two different cryptanalysis approaches concerning its collision resistance. Thanks to the first approach, related to truncated differentials, we computed a collision for the CubeHash-1/36 hash function, i.e. when for each iteration 36 bytes of message are incorporated and one call to the permutation is applied. Then, the second approach, already used by Dai, much more efficient and simply based on a linearization of the scheme, allowed us to compute a collision for the CubeHash-2/4 hash function. Finally, a theoretical collision attack against CubeHash-2/3, CubeHash-4/4 and CubeHash-4/3 is described. This is currently the best known cryptanalysis result on this SHA-3 candidate.},
 
   abstract = {CubeHash is a family of hash functions submitted by Bern stein as a SHA-3 candidate. In this paper, we provide two different cryptanalysis approaches concerning its collision resistance. Thanks to the first approach, related to truncated differentials, we computed a collision for the CubeHash-1/36 hash function, i.e. when for each iteration 36 bytes of message are incorporated and one call to the permutation is applied. Then, the second approach, already used by Dai, much more efficient and simply based on a linearization of the scheme, allowed us to compute a collision for the CubeHash-2/4 hash function. Finally, a theoretical collision attack against CubeHash-2/3, CubeHash-4/4 and CubeHash-4/3 is described. This is currently the best known cryptanalysis result on this SHA-3 candidate.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashD08,
 +
  author    = {Wei Dai},
 +
  title    = {Collisions for CubeHash1/45 and CubeHash2/89},
 +
  url = {http://www.cryptopp.com/sha3/cubehash.pdf},
 +
  howpublished = {Available online},
 +
  year = {2008},
 +
  abstract = {Collisions were found for the hash functions CubeHash1/45-512 and CubeHash2/89-512. Attack code is included.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashA08,
 +
  author    = {Jean-Philippe Aumasson},
 +
  title    = {Collision for CubeHash2/120-512},
 +
  url = {http://ehash.iaik.tugraz.at/uploads/a/a9/Cubehash.txt},
 +
  howpublished = {NIST mailing list (local link)},
 +
  year = {2008},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{cubehashKNW08,
 +
  author    = {Dmitry Khovratovich and Ivica Nikolic' and Ralf-Philipp Weinmann},
 +
  title    = {Preimage attack on CubeHash512-r/4 and CubeHash512-r/8},
 +
  url        = {http://ehash.iaik.tugraz.at/uploads/6/6c/Cubehash.pdf},
 +
  howpublished = {Available online},
 +
  year      = {2008},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{cubehashAMPP09,
 +
  author    = {Jean-Philippe Aumasson and Eric Brier and Willi Meier and María Naya-Plasencia and Thomas Peyrin},
 +
  title    = {Inside the Hypercube},
 +
  booktitle = {ACISP},
 +
  publisher = {Springer},
 +
  editor = {Colin Boyd and Juan Manuel Gonz{\'a}lez Nieto},
 +
  series    = {LNCS},
 +
  pages    = {202-213},
 +
  volume    = {5594},
 +
  url = {http://www.131002.net/data/papers/ABMNP08.pdf},
 +
  year      = {2009},
 +
  abstract  = {Bernstein’s CubeHash is a hash function family that includes four functions submitted to the NIST Hash Competition. A CubeHash function is parametrized by a number of rounds r, a block byte size b, and a digest bit length h. The 1024-bit internal state of CubeHash is represented as a five-dimension hypercube. Submissions to NIST have r = 8, b = 1, and $h \in {224, 256, 384, 512}$.
 +
This paper gives the first external analysis of CubeHash, with
 +
- improved standard generic attacks for collisions and preimages
 +
- a multicollision attack that exploits fixed points
 +
- a study of the round function symmetries
 +
- a preimage attack that exploits these symmetries
 +
- a practical collision attack on a weakened version of CubeHash
 +
- high-probability truncated differentials over the 8-round transform
 +
Our results do not contradict the security claims about CubeHash.},
 
}
 
}
 
</bibtex>
 
</bibtex>

Latest revision as of 09:46, 9 November 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 tables is given here.

Recommended security parameters: r/b = 16/32 (n=224,256); 16/32 (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/Variants Compression Function Calls Memory Requirements Reference
preimage 384,512 r/32 2383.7 - Ferguson,Lucks,McKay
preimage 384,512 r/33 2257.6 - Ferguson,Lucks,McKay
collision 512 7/64 2203 - Brier,Khazaei,Meier,Peyrin
collision all 4/48 example (237) - Brier,Khazaei,Meier,Peyrin
collision all 4/64 example (234) - Brier,Khazaei,Meier,Peyrin
collision all 3/64 example (224) - Brier,Khazaei,Meier,Peyrin
collision 512 2/2 2196 - Brier,Khazaei,Meier,Peyrin
collision 512 5/64 2231 - Brier,Peyrin
collision all 3/64 289 - Brier,Peyrin
collision 512 4/3 2207 - Brier,Peyrin
collision 384,512 4/4 2189 - Brier,Peyrin
collision all 2/3 246 - Brier,Peyrin
collision 512 2/4 example - Brier,Peyrin
collision 512 1/45, 2/89 example - Dai
collision 512 2/120 example - Aumasson
preimage 512 r/8 2480 - Khovratovich,Nikolic',Weinmann
preimage 512 r/4 2496 - Khovratovich,Nikolic',Weinmann
preimage 512 r/1 (round 1) 2511 2508 Khovratovich,Nikolic',Weinmann
preimage all r/b 2513-4b - Aumasson,Meier,Naya-Plasencia,Peyrin
collision all r/b 2521-4b-log b - submission document
preimage all r/b 2522-4b-log b - submission document


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
quantum preimage hash 512 2192 - Leurent
distinguisher permutation all 14 rounds 2812 - Ashur,Dunkelman
distinguisher permutation all 11 rounds 2470 - Ashur,Dunkelman
observations hash all - - Kaminsky
observations hash all - - Bloom,Kaminsky
multi-collision hash all 2513-4b - Aumasson,Meier,Naya-Plasencia,Peyrin
observations permutation all - - Aumasson,Meier,Naya-Plasencia,Peyrin


Gaëtan Leurent - Quantum Preimage and Collision Attacks on CubeHash

,2010
http://eprint.iacr.org/2010/506.pdf
Bibtex
Author : Gaëtan Leurent
Title : Quantum Preimage and Collision Attacks on CubeHash
In : -
Address :
Date : 2010

Tomer Ashur, Orr Dunkelman - Linear Analysis of Reduced-Round CubeHash

,2010
http://eprint.iacr.org/2010/535.pdf
Bibtex
Author : Tomer Ashur, Orr Dunkelman
Title : Linear Analysis of Reduced-Round CubeHash
In : -
Address :
Date : 2010

Niels Ferguson, Stefan Lucks, Kerry A. McKay - Symmetric States and their Structure: Improved Analysis of CubeHash

,2010
http://eprint.iacr.org/2010/273.pdf
Bibtex
Author : Niels Ferguson, Stefan Lucks, Kerry A. McKay
Title : Symmetric States and their Structure: Improved Analysis of CubeHash
In : -
Address :
Date : 2010

Alan Kaminsky - Cube Test Analysis of the Statistical Behavior of CubeHash and Skein

,2010
http://eprint.iacr.org/2010/262.pdf
Bibtex
Author : Alan Kaminsky
Title : Cube Test Analysis of the Statistical Behavior of CubeHash and Skein
In : -
Address :
Date : 2010

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

,2009
http://eprint.iacr.org/2009/407.pdf
Bibtex
Author : Benjamin Bloom, Alan Kaminsky
Title : Single Block Attacks and Statistical Tests on CubeHash
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

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 - 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 - 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, 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

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

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

Dmitry Khovratovich, Ivica Nikolic', 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 Nikolic', Ralf-Philipp Weinmann
Title : Preimage attack on CubeHash512-r/4 and CubeHash512-r/8
In : -
Address :
Date : 2008

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