Skein - Revision history

Crechberger: Added results of four recent cryptanalysis papers

2012-10-02T10:26:15Z

Added results of four recent cryptanalysis papers

Mschlaeffer: references updated

2011-04-22T08:22:03Z

references updated

Mschlaeffer at 08:35, 4 April 2011

2011-04-04T08:35:04Z

Fmendel at 18:37, 22 March 2011

2011-03-22T18:37:56Z

Mschlaeffer at 09:27, 21 March 2011

2011-03-21T09:27:35Z

Mschlaeffer at 08:51, 21 March 2011

2011-03-21T08:51:00Z

Mschlaeffer at 07:34, 21 March 2011

2011-03-21T07:34:28Z

JAumasson: added eprint 2010/538 result

2010-11-08T10:02:07Z

added eprint 2010/538 result

JAumasson: fixed bibtex ordering

2010-11-08T09:52:43Z

fixed bibtex ordering

Mschlaeffer at 12:54, 5 July 2010

2010-07-05T12:54:18Z

@@ 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 parameter: '''72''' rounds (Skein-512)
+Recommended security parameter: '''72''' rounds (Skein-256 and Skein-512)
@@ Line 56: / Line 56: @@
 | Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| || || || || ||
+| collision || 256 ||  2 rounds || 2<sup>85</sup>     || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 |-
 |}
@@ Line 70: / Line 80: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
 | distinguisher || compression function || all || 57 rounds  (Round 2) || 2<sup>503</sup>  || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
@@ Line 106: / Line 130: @@
 <bibtex>
 @inproceedings{skeinKNR10,
@@ Line 122: / Line 198: @@
+}
 </bibtex>
 <bibtex>
 @inproceedings{skeinSuWWD10,
@@ Line 169: / Line 244: @@
+}
 </bibtex>
 <bibtex>
 @inproceedings{cryptoeprint:2009:526,
@@ Line 192: / Line 266: @@
+}
 </bibtex>
 <bibtex>
 @misc{cryptoeprint:2009:526,
@@ Line 203: / Line 276: @@
+}
 </bibtex>
 <bibtex>
 @inproceedings{skeinA+09,
@@ Line 218: / Line 290: @@
+}
 </bibtex>
 <bibtex>
 @misc{SkeinAum09,

@@ Line 107: / Line 107: @@
 <bibtex>
-@misc{skeinKNR10,
+@inproceedings{skeinKNR10,
    author = {Dmitry Khovratovich and Ivica Nikolić and Christian Rechberger},
    title = {Rotational Rebound Attacks on Reduced Skein},
-   howpublished = {Cryptology ePrint Archive, Report 2010/538},
+   booktitle = {ASIACRYPT},
-   year = {2010},
+  year      = {2010},
    url = {http://eprint.iacr.org/2010/538.pdf},
    abstract = {In this paper we combine the recent rotational cryptanalysis with the rebound attack, which results in the best cryptanalysis of Skein, a candidate for the SHA-3 competition. The rebound attack approach was so far only applied to AES-like constructions. For the first time, we show that this approach can also be applied to very different constructions. In more detail, we develop a number of techniques that extend the reach of both the inbound and the outbound phase, leading to rotational collisions for about 53/57 out of the 72 rounds of the Skein-256/512 compression function and the Threefish cipher. At this point, the results do not threaten the security of the full-round Skein hash function.
@@ Line 120: / Line 124: @@
 <bibtex>
-@misc{skeinSuWWD10,
+@inproceedings{skeinSuWWD10,
    author = {Bozhan Su and Wenling Wu and Shuang Wu and Le Dong},
    title = {Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE},
-   howpublished = {Cryptology ePrint Archive, Report 2010/355},
+   booktitle = {CANS},
-   year = {2010},
+  year      = {2010},
    url = {http://eprint.iacr.org/2010/355.pdf},
    abstract = {The SHA-3 competition organized by NIST aims to find a new hash standard as a replacement of SHA-2. Till now, 14 submissions have been selected as the second round candidates, including Skein and BLAKE, both of which have components based on modular addition, rotation and bitwise XOR (ARX). In this paper, we propose improved near-collision attacks on the reduced-round compression functions of Skein and a variant of BLAKE. The attacks are based on linear differentials of the modular additions. The computational complexity of near-collision attacks on a 4-round compression function of BLAKE-32, 4-round and 5-round compression functions of BLAKE-64 are 2^{21}, 2^{16} and 2^{216} respectively, and the attacks on a 24-round compression functions of Skein-256, Skein-512 and Skein-1024 have a complexity of 2^{60}, 2^{230} and 2^{395} respectively.}
@@ Line 147: / Line 155: @@
      year = {2010},
      url = {http://eprint.iacr.org/2010/282.pdf},
      abstract = {The operations addition modulo 2^n and exclusive-or have recently been combined to obtain an efficient mechanism for nonlinearity in block cipher design. In this paper, we show that ciphers using this approach may be approximated by pseudo-linear expressions relating groups of contiguous bits of the round key, round input, and round output. The bias of an approximation can be large enough for known plaintext attacks. We demonstrate an application of this concept to a reduced-round version of the Threefish block cipher, a component of the Skein entry in the secure hash function competition.}
+}
@@ Line 159: / Line 166: @@
      year = {2010},
      url = {http://eprint.iacr.org/2010/262.pdf},
      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. }
+}
@@ Line 165: / Line 171: @@
 <bibtex>
-@misc{cryptoeprint:2009:526,
+@inproceedings{cryptoeprint:2009:526,
      author = {Dmitry Khovratovich and Ivica Nikolic},
      title = {Rotational Cryptanalysis of ARX},
-     howpublished = {Preproceedings of FSE 2010},
+  pages     = {333-346},
-    year = {2010},
+  booktitle = {FSE},
      url = {http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf},
      abstract = {In this paper we analyze the security of systems based on
@@ Line 191: / Line 200: @@
      year = {2009},
      url = {http://eprint.iacr.org/2009/526.pdf},
      abstract = {Hash function Skein is one of the 14 NIST SHA-3 second round candidates. Threefish is a tweakable block cipher as the core of Skein, defined with a 256-, 512-, and 1024-bit block size. The 512-bit block size is the primary proposal of the authors. In this paper we construct two related-key boomerang distinguishers on round-reduced Threefish-512 using the method of \emph{modular differential}. With a distinguisher on 32 rounds of Threefish-512, we improve the key recovery attack on 32 rounds of Threefish-512 proposed by Aumasson et al. Their attack requires $2^{312}$ encryptions and $2^{71}$ bytes of memory. However, our attack has a time complexity of $2^{226}$ encryptions with memory of $2^{12}$ bytes. Furthermore, we give a key recovery attack on Threefish-512 reduced to 33 rounds using a 33-round related-key boomerang distinguisher, with $2^{352.17}$ encryptions and negligible memory. Skein had been updated after it entered the second round and the results above are based on the original version. However, as the only differences between the original and the new version are the rotation constants, both of the methods can be applied to the new version with modified differential trails. For the new rotation constants, our attack on 32-round Threefish-512 has a time complexity $2^{222}$ and $2^{12}$ bytes' memory. Our attack on 33-round Threefish-512 has a time complexity $2^{355.5}$ and negligible memory.},
+}
@@ Line 197: / Line 205: @@
 <bibtex>
-@misc{skeinA+09,
+@inproceedings{skeinA+09,
      author = {Jean-Philippe Aumasson and Cagdas Calik and Willi Meier and Onur Ozen and Raphael C.-W. Phan and Kerem Varici},
      title = {Improved Cryptanalysis of Skein},
-    howpublished = {Cryptology ePrint Archive, Report 2009/438},
+  booktitle = {ASIACRYPT},
-     year = {2009},
+  year      = {2009},
      url = {http://eprint.iacr.org/2009/438.pdf},
      abstract={The hash function Skein is the submission of Ferguson et al. to the NIST Hash Competition, and is arguably a serious candidate for selection as SHA-3. This paper presents the first third-party analysis of Skein, with an extensive study of its main component: the block cipher Threefish. We notably investigate near collisions, distinguishers, impossible differentials, key recovery using related-key differential and boomerang attacks. In particular, we present near collisions on up to 17 rounds, an impossible differential on 21 rounds, a related-key boomerang distinguisher on 34 rounds, a known-related-key boomerang distinguisher on 35 rounds, and key recovery attacks on up to 32 rounds, out of 72 in total for Threefish-512. None of our attacks directly extends to the full Skein hash. However, the pseudorandomness of Threefish is required to validate the security proofs on Skein, and our results conclude that at least 36 rounds of Threefish seem required for optimal security guarantees.},
+}

@@ Line 4: / Line 4: @@
 * Website: [http://www.schneier.com/skein.html http://www.schneier.com/skein.html]; [http://skein-hash.info/ http://skein-hash.info/]
 * NIST submission package:
-** round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Skein_FinalRnd.zip Skein_FinalRnd.zip]
+** Round 3: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Skein_FinalRnd.zip Skein_FinalRnd.zip]
-** round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Skein_Round2.zip Skein_Round2.zip]
+** Round 2: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/documents/Skein_Round2.zip Skein_Round2.zip]
-** round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SkeinUpdate.zip SkeinUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Skein.zip Skein.zip])
+** Round 1: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/SkeinUpdate.zip SkeinUpdate.zip] (old version: [http://csrc.nist.gov/groups/ST/hash/sha-3/Round1/documents/Skein.zip Skein.zip])
@@ Line 38: / Line 38: @@
+}
 </bibtex>
 == Cryptanalysis ==

@@ Line 72: / Line 72: @@
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
 |-
-| distinguisher || compression function || all || 57 rounds || 2<sup>503</sup>  || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
+| distinguisher || compression function || all || 57 rounds  (Round 2) || 2<sup>503</sup>  || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
 |-
-| distinguisher || compression function || 256 || 53 rounds || 2<sup>251</sup>, Skein-256  || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
+| distinguisher || compression function || 256 || 53 rounds (Round 2) || 2<sup>251</sup>, Skein-256  || - || [http://eprint.iacr.org/2010/538.pdf Khovratovich,Nikolić,Rechberger]
 |-
 | near-collision || compression function || all || 24 rounds (No. 20-43) || 2<sup>230</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]

@@ Line 38: / Line 38: @@
+}
 </bibtex>
 == Cryptanalysis ==
@@ Line 46: / Line 47: @@
 Recommended security parameter: '''72''' rounds (Skein-512)
 === Hash function ===
@@ Line 58: / Line 60: @@
 |-
 |}
 === Building blocks ===
@@ Line 205: / Line 208: @@
+}
 </bibtex>
 <bibtex>

@@ Line 33: / Line 33: @@
    author    = {Niels Ferguson and Stefan Lucks and Bruce Schneier and Doug Whiting and Mihir Bellare and Tadayoshi Kohno and Jon Callas and Jesse Walker},
    title     = {The Skein Hash Function Family},
-   url        = {http://www.skein-hash.info/sites/default/files/skein.pdf},
+   url        = {http://www.skein-hash.info/sites/default/files/skein1.1.pdf},
    howpublished = {Submission to NIST (Round 1)},
    year      = {2008},

@@ Line 41: / Line 41: @@
 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 || Compression Function Calls || Memory Requirements ||   Reference
@@ Line 55: / Line 55: @@
 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