CubeHash - Revision history

JAumasson: /* Building blocks */ dashes added

2010-11-09T07:46:24Z

‎Building blocks: dashes added

JAumasson: added eprint 2010/506

2010-11-08T15:27:21Z

added eprint 2010/506

JAumasson: added eprint 2010/535 results

2010-11-08T10:07:59Z

added eprint 2010/535 results

Fmendel at 12:54, 5 July 2010

2010-07-05T12:54:06Z

Mschlaeffer at 13:53, 8 June 2010

2010-06-08T13:53:08Z

JAumasson: Added Ferguson/Lucks/McKay paper

2010-05-27T12:15:51Z

Added Ferguson/Lucks/McKay paper

JAumasson: added Kaminsky's paper

2010-05-27T12:03:36Z

added Kaminsky's paper

JAumasson: correct placement of rec sec par

2010-04-29T07:09:22Z

correct placement of rec sec par

JAumasson: fixed introductory sentences

2010-02-15T13:46:02Z

fixed introductory sentences

JAumasson: link to designer's analysis added

2010-02-15T09:44:49Z

link to designer's analysis added

@@ Line 110: / Line 110: @@
 | 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]
+| 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  || 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]
+| 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]
+|  observations || hash || all ||  || - || - || [http://eprint.iacr.org/2010/262.pdf Kaminsky]
 |-
-| observations || hash || all ||  ||  ||  || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
+| observations || hash || all ||  || - || - || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
 |-
 | 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]
+| observations || permutation|| all  ||  || - || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
 |-
 |}

@@ Line 109: / Line 109: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 | 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]
 |-
@@ Line 124: / Line 126: @@
 |}
 <bibtex>
@@ Line 133: / Line 148: @@
      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.. }
+     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>

@@ Line 109: / Line 109: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 |  observations || hash || all ||  ||  ||  || [http://eprint.iacr.org/2010/262.pdf Kaminsky]
 |-
@@ Line 120: / Line 124: @@
 |}
 <bibtex>

@@ Line 51: / Line 51: @@
 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" style="text-align:center"
+{| border="1" cellpadding="4" cellspacing="0" class="wikitable sortable" style="text-align:center"
 |- style="background:#efefef;"
 | Type of Analysis || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
@@ Line 106: / Line 106: @@
 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" style="text-align:center"
+{| 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

@@ Line 45: / Line 45: @@
 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/1''' (n=384,512)
+Recommended security parameters: r/b = '''16/32''' (n=224,256); '''16/32''' (n=384,512)
 === Hash function ===
@@ Line 55: / Line 55: @@
 | Type of Analysis || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| preimage || 384,512 || 16/32 || 2<sup>383.7</sup> || - || [http://eprint.iacr.org/2010/273.pdf Ferguson,Lucks,McKay]
+| 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 || 16/33 || 2<sup>257.6</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]
@@ Line 89: / Line 89: @@
 | 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 ||  || 2<sup>511</sup> || 2<sup>508</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]
 |-
-| style="background:greenyellow" | preimage || all ||  || 2<sup>513-4b</sup> || - || [http://eprint.iacr.org/2008/486.pdf Aumasson,Meier,Naya-Plasencia,Peyrin]
+| 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 || all ||  || 2<sup>521-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
+| collision || all || r/b || 2<sup>521-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
 |-
-| preimage || all ||  || 2<sup>522-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
+| style="background:greenyellow" | preimage || all || r/b || 2<sup>522-4b-log b</sup> || - || [http://cubehash.cr.yp.to/submission/generic.pdf submission document]
 |-
 |}

@@ Line 106: / Line 106: @@
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 | observations || hash || all ||  ||  ||  || [http://eprint.iacr.org/2009/407.pdf Bloom,Kaminsky]
 |-
@@ Line 116: / Line 118: @@
 <bibtex>
-@misc{cryptoeprint:2009:407,
+@misc{cubehashKam10,
      author = {Benjamin Bloom and Alan Kaminsky},
      title = {Single Block Attacks and Statistical Tests on CubeHash},
      howpublished = {Cryptology ePrint Archive, Report 2009/407},
      year = {2009},
      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.},