Difference between revisions of "Skein"

From The ECRYPT Hash Function Website
m (typo)
(Added results of four recent cryptanalysis papers)
 
(11 intermediate revisions by 3 users not shown)
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/]
 
* Website: [http://www.schneier.com/skein.html http://www.schneier.com/skein.html]; [http://skein-hash.info/ http://skein-hash.info/]
 
* NIST submission package:  
 
* NIST submission package:  
−
** 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 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])
  
 +
 +
<bibtex>
 +
@misc{sha3F+10,
 +
  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/skein1.3.pdf},
 +
  howpublished = {Submission to NIST (Round 3)},
 +
  year      = {2010},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 22: 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},
 
   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},
 
   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)},
 
   howpublished = {Submission to NIST (Round 1)},
 
   year      = {2008},
 
   year      = {2008},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
  
 
== Cryptanalysis ==
 
== Cryptanalysis ==
Line 35: Line 45:
 
A description of the tables is given [http://ehash.iaik.tugraz.at/wiki/Cryptanalysis_Categories#Individual_Hash_Function_Tables here].
 
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
+
Recommended security parameter: '''72''' rounds (Skein-256 and Skein-512)
 +
 
  
 
=== Hash function ===
 
=== Hash function ===
Line 41: Line 52:
 
Here we list results on the hash function according to the NIST requirements. The only allowed modification is to change the security parameter.
 
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;"                   
 
|- style="background:#efefef;"                   
 
| 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  
 
|-                     
 
|-                     
−
| || || || || ||
+
| collision || 256 || 2 rounds || 2<sup>85</sup>    || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 +
|-
 +
| collision || 256 || 12 rounds || 2<sup>126.5</sup>  || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 +
|-
 +
| collision || 512 || 5 rounds  || 2<sup>192</sup>    || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 +
|-
 +
| collision || 512 || 14 rounds || 2<sup>254.5</sup>  || - || [http://eprint.iacr.org/2012/141.pdf Khovratovich]
 +
|-                   
 +
| preimage || 512 || 22 rounds || 2<sup>511.0</sup>  || 2<sup>6</sup> || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
 +
|-                   
 +
| preimage || 512 || 72 rounds || 2<sup>511.76</sup>  || - || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
 
|-                     
 
|-                     
 
|}
 
|}
 +
  
 
=== Building blocks ===
 
=== Building blocks ===
Line 55: Line 77:
 
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).  
 
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;"                   
 
|- 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  
 
|-
 
|-
−
|-  
+
| preimage || compression function || 512 || 22 rounds || 2<sup>508</sup>  ||  2<sup>6</sup>  || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
 +
|-
 +
| preimage || compression function || 512 || 37 rounds || 2<sup>511.2</sup>  || 2<sup>64</sup> || [http://eprint.iacr.org/2011/286.pdf Khovratovich,Rechberger,Savelieva]
 +
|-
 +
| distinguisher || compression function || 512 || 32 rounds || 2<sup>104.5</sup>  || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
 +
|-
 +
| distinguisher || compression function || 512 || 36 rounds || 2<sup>454</sup>  || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
 +
|-
 +
| key recovery || block cipher || 512 || 32 rounds || 2<sup>181</sup>  || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
 +
|-
 +
| key recovery || block cipher || 512 || 34 rounds || 2<sup>424</sup>  || - || [http://eprint.iacr.org/2012/238.pdf Yu,Chen,Wang]
 +
|-
 +
| near-collision || compression function || 256 || 32 rounds || 2<sup>105</sup>  || - || [http://eprint.iacr.org/2011/148.pdf Yu,Chen,Jia,Wang]
 +
|-
 +
| 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 (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]
 +
|-
 +
| near-collision || compression function || 256 || 24 rounds (No. 12-35), Skein-256 || 2<sup>60</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
| near-collision || compression function || all || 24 rounds, Skein-1024 || 2<sup>395</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
 +
|-
 +
|  observations || hash || all || ||  ||  || [http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf Gligoroski]
 +
|-
 
|  observations || block cipher || all || - || - || - || [http://eprint.iacr.org/2010/282.pdf McKay,Vora]
 
|  observations || block cipher || all || - || - || - || [http://eprint.iacr.org/2010/282.pdf McKay,Vora]
 
|-
 
|-
Line 82: Line 129:
 
|}         
 
|}         
  
 +
 +
 +
 +
<bibtex>
 +
@misc{skeinK12,
 +
    author = {Dmitry Khovratovich},
 +
    title = {Bicliques for permutations: collision and preimage attacks in stronger settings},
 +
    howpublished = {Cryptology ePrint Archive, Report 2012/141},
 +
    year = {2012},
 +
    url = {http://eprint.iacr.org/2012/141.pdf},
 +
    abstract = { We extend and improve biclique attacks, which were recently introduced for the cryptanalysis of block ciphers and hash functions. While previous attacks required a primitive to have a key or a message schedule, we show how to mount attacks on the primitives with these parameters fixed, i.e. on permutations. We introduce the concept of sliced bicliques, which is a translation of regular bicliques to the framework with permutations.
 +
 +
The new framework allows to convert preimage attacks into collision attacks and derive the first collision attacks on the reduced SHA-3 finalist Skein in the hash function setting up to 11 rounds. We also demonstrate new preimage attacks on the reduced Skein and the output transformation of the reduced Gr{\o}stl. Finally, the sophisticated technique of message compensation gets a simple explanation with bicliques. }
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{skeinKRS12,
 +
  author = {Dmitry Khovratovich and Christian Rechberger and Alexandra Savelieva},
 +
  title = {Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family},
 +
  booktitle = {Fast Software Encryption (FSE)},
 +
  year      = {2012},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  url = {http://eprint.iacr.org/2011/286.pdf},
 +
  abstract = {We present the new concept of biclique as a tool for preimage attacks, which
 +
employs many powerful techniques from differential cryptanalysis of block ciphers and hash
 +
functions.
 +
The new tool has proved to be widely applicable by inspiring many authors to publish new re-
 +
sults of the full versions of AES, KASUMI, IDEA, and Square. In this paper, we demonstrate
 +
how our concept results in the first cryptanalysis of the Skein hash function, and describe an
 +
attack on the SHA-2 hash function with more rounds than before.}
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@misc{skeinY+12,
 +
    author = {Hongbo Yu and Jiazhe Chen and Xiaoyun Wang},
 +
    title = {The Boomerang Attacks on the Round-Reduced Skein-512},
 +
    howpublished = {Cryptology ePrint Archive, Report 2012/238},
 +
    year = {2012},
 +
    url = {http://eprint.iacr.org/2012/238.pdf},
 +
    abstract = {The hash function Skein is one of the five finalists of the NIST SHA-3 competition;it is based on the block cipher Threefish which only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). This paper studies the boomerang attacks on Skein-512. Boomerang distinguishers on the compression function reduced to 32 and 36 rounds are proposed, with complexities 2^{104.5} and 2^{454} respectively. Examples of the distinguishers on 28-round and 31-round are also given. In addition, the boomerang distinguishers are applicable to the key-recovery attacks on reduced Threefish-512. The complexities for key-recovery attacks reduced to 32-/33-/34-round are about 2^{181}, 2^{305} and 2^{424}. Because Laurent et al. [14] pointed out that the previous boomerang distinguishers for Threefish-512 are in fact not compatible, our attacks are the first valid boomerang attacks for the final round Skein-512.  }
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@misc{skeinY+12,
 +
    author = {Hongbo Yu and Jiazhe Chen and Ketingjia and Xiaoyun Wang},
 +
    title = {Near-Collision Attack on the Step-Reduced Compression Function of Skein-256},
 +
    howpublished = {Cryptology ePrint Archive, Report 2011/148},
 +
    year = {2011},
 +
    url = {http://eprint.iacr.org/2011/148.pdf},
 +
    abstract = {The Hash function Skein is one of the 5 finalists of NIST SHA-3 competition. It is designed based on the threefish block cipher and it only uses three primitive operations: modular addition, rotation and bitwise XOR (ARX). In this paper, we combine two short differential paths to a long differential path using the modular differential technique. And we present the semi-free start near-collision attack up to the 32-step Skein-256 with the Hamming difference 51. The complexity of our attack is about $2^{105}$. }
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{skeinKNR10,
 +
  author = {Dmitry Khovratovich and Ivica Nikolić and Christian Rechberger},
 +
  title = {Rotational Rebound Attacks on Reduced Skein},
 +
  booktitle = {ASIACRYPT},
 +
  year      = {2010},
 +
  pages    = {1-19},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6477},
 +
  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.
 +
 +
The new techniques include an analytical search for optimal input values in the rotational cryptanalysis, which allows to extend the outbound phase of the attack with a precomputation phase, an approach never used in any rebound-style attack before. Further we show how to combine multiple inside-out computations and neutral bits in the inbound phase of the rebound attack, and give well-defined rotational distinguishers as certificates of weaknesses for the compression functions and block ciphers.}
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@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},
 +
  booktitle = {CANS},
 +
  year      = {2010},
 +
  pages    = {124-139},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {6467},
 +
  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.}
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@misc{skeinGli10,
 +
  author    = {Danilo Gligoroski},
 +
  title    = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
 +
  url        = {http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf},
 +
  howpublished = {NIST mailing list},
 +
  year      = {2010},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>
Line 90: Line 230:
 
     year = {2010},
 
     year = {2010},
 
     url = {http://eprint.iacr.org/2010/282.pdf},
 
     url = {http://eprint.iacr.org/2010/282.pdf},
−
    note = {\url{http://eprint.iacr.org/}},
 
 
     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.}
 
     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 102: Line 241:
 
     year = {2010},
 
     year = {2010},
 
     url = {http://eprint.iacr.org/2010/262.pdf},
 
     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. }
 
     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>
−
 
 
<bibtex>
 
<bibtex>
−
@misc{skeinA+09,
+
@inproceedings{cryptoeprint:2009:526,
−
     author = {Jean-Philippe Aumasson and Cagdas Calik and Willi Meier and Onur Ozen and Raphael C.-W. Phan and Kerem Varici},
+
     author = {Dmitry Khovratovich and Ivica Nikolic},
−
     title = {Improved Cryptanalysis of Skein},
+
     title = {Rotational Cryptanalysis of ARX},
−
     howpublished = {Cryptology ePrint Archive, Report 2009/438},
+
  pages     = {333-346},
−
    year = {2009},
+
  booktitle = {FSE},
−
    url = {http://eprint.iacr.org/2009/438.pdf},
+
  publisher = {Springer},
−
    note = {\url{http://eprint.iacr.org/}},
+
  series    = {LNCS},
−
     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.},
+
  volume    = {6147},
 +
    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
 +
modular additions, rotations, and XORs (ARX systems). We provide
 +
both theoretical support for their security and practical cryptanalysis of
 +
real ARX primitives. We use a technique called rotational cryptanalysis,
 +
that is universal for the ARX systems and is quite efficient. We illustrate
 +
the method with the best known attack on reduced versions of the block
 +
cipher Threefish (the core of Skein). Additionally, we prove that ARX
 +
with constants are functionally complete, i.e. any function can be realized
 +
with these operations.
 +
},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
 
@misc{cryptoeprint:2009:526,
 
@misc{cryptoeprint:2009:526,
Line 126: Line 273:
 
     year = {2009},
 
     year = {2009},
 
     url = {http://eprint.iacr.org/2009/526.pdf},
 
     url = {http://eprint.iacr.org/2009/526.pdf},
−
    note = {\url{http://eprint.iacr.org/}},
 
 
     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.},
 
     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.},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
−
@misc{cryptoeprint:2009:526,
+
@inproceedings{skeinA+09,
−
     author = {Dmitry Khovratovich and Ivica Nikolic},
+
     author = {Jean-Philippe Aumasson and Cagdas Calik and Willi Meier and Onur Ozen and Raphael C.-W. Phan and Kerem Varici},
−
     title = {Rotational Cryptanalysis of ARX},
+
     title = {Improved Cryptanalysis of Skein},
−
     howpublished = {Preproceedings of FSE 2010},
+
  booktitle = {ASIACRYPT},
−
    year = {2010},
+
  year      = {2009},
−
     url = {http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf},
+
  pages     = {542-559},
−
     abstract = {In this paper we analyze the security of systems based on
+
  publisher = {Springer},
−
modular additions, rotations, and XORs (ARX systems). We provide
+
  series    = {LNCS},
−
both theoretical support for their security and practical cryptanalysis of
+
  volume    = {5912},
−
real ARX primitives. We use a technique called rotational cryptanalysis,
+
     url = {http://eprint.iacr.org/2009/438.pdf},
−
that is universal for the ARX systems and is quite efficient. We illustrate
+
     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.},
−
the method with the best known attack on reduced versions of the block
 
−
cipher Threefish (the core of Skein). Additionally, we prove that ARX
 
−
with constants are functionally complete, i.e. any function can be realized
 
−
with these operations.
 
−
},
 
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
−
=== Archive ===
 
−
 
 
<bibtex>
 
<bibtex>
 
@misc{SkeinAum09,
 
@misc{SkeinAum09,

Latest revision as of 12:26, 2 October 2012

1 The algorithm


Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker - The Skein Hash Function Family

,2010
http://www.skein-hash.info/sites/default/files/skein1.3.pdf
Bibtex
Author : Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
Title : The Skein Hash Function Family
In : -
Address :
Date : 2010

Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker - The Skein Hash Function Family

,2009
http://www.skein-hash.info/sites/default/files/skein1.2.pdf
Bibtex
Author : Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
Title : The Skein Hash Function Family
In : -
Address :
Date : 2009

Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker - The Skein Hash Function Family

,2008
http://www.skein-hash.info/sites/default/files/skein1.1.pdf
Bibtex
Author : Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
Title : The Skein Hash Function Family
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: 72 rounds (Skein-256 and Skein-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 256 2 rounds 285 - Khovratovich
collision 256 12 rounds 2126.5 - Khovratovich
collision 512 5 rounds 2192 - Khovratovich
collision 512 14 rounds 2254.5 - Khovratovich
preimage 512 22 rounds 2511.0 26 Khovratovich,Rechberger,Savelieva
preimage 512 72 rounds 2511.76 - Khovratovich,Rechberger,Savelieva


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
preimage compression function 512 22 rounds 2508 26 Khovratovich,Rechberger,Savelieva
preimage compression function 512 37 rounds 2511.2 264 Khovratovich,Rechberger,Savelieva
distinguisher compression function 512 32 rounds 2104.5 - Yu,Chen,Wang
distinguisher compression function 512 36 rounds 2454 - Yu,Chen,Wang
key recovery block cipher 512 32 rounds 2181 - Yu,Chen,Wang
key recovery block cipher 512 34 rounds 2424 - Yu,Chen,Wang
near-collision compression function 256 32 rounds 2105 - Yu,Chen,Jia,Wang
distinguisher compression function all 57 rounds (Round 2) 2503 - Khovratovich,Nikolić,Rechberger
distinguisher compression function 256 53 rounds (Round 2) 2251, Skein-256 - Khovratovich,Nikolić,Rechberger
near-collision compression function all 24 rounds (No. 20-43) 2230 - Su,Wu,Wu,Dong
near-collision compression function 256 24 rounds (No. 12-35), Skein-256 260 - Su,Wu,Wu,Dong
near-collision compression function all 24 rounds, Skein-1024 2395 - Su,Wu,Wu,Dong
observations hash all Gligoroski
observations block cipher all - - - McKay,Vora
observations compression function all - - - Kaminsky
key recovery block cipher 256 39 rounds 2254.1 - Khovratovich,Nikolic
key recovery block cipher 512 42 rounds 2507 - Khovratovich,Nikolic
key recovery block cipher 512 32 rounds (Round 1) 2226 (2222) 212 Chen,Jia
key recovery block cipher 512 33 rounds (Round 1) 2352.17 (2355.5) - Chen,Jia
near collision compression function 512 17 rounds (Round 1) 224 - Aumasson,Calik,Meier,Ozen,Phan,Varici
distinguisher block cipher 512 35 rounds (Round 1) 2478 - Aumasson,Calik,Meier,Ozen,Phan,Varici
impossible differential block cipher 512 21 rounds (Round 1) - - Aumasson,Calik,Meier,Ozen,Phan,Varici
key recovery block cipher 512 32 rounds (Round 1) 2312 - Aumasson,Calik,Meier,Ozen,Phan,Varici



Dmitry Khovratovich - Bicliques for permutations: collision and preimage attacks in stronger settings

,2012
http://eprint.iacr.org/2012/141.pdf
Bibtex
Author : Dmitry Khovratovich
Title : Bicliques for permutations: collision and preimage attacks in stronger settings
In : -
Address :
Date : 2012

Dmitry Khovratovich, Christian Rechberger, Alexandra Savelieva - Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family

Fast Software Encryption (FSE) ,2012
http://eprint.iacr.org/2011/286.pdf
Bibtex
Author : Dmitry Khovratovich, Christian Rechberger, Alexandra Savelieva
Title : Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family
In : Fast Software Encryption (FSE) -
Address :
Date : 2012

Hongbo Yu, Jiazhe Chen, Xiaoyun Wang - The Boomerang Attacks on the Round-Reduced Skein-512

,2012
http://eprint.iacr.org/2012/238.pdf
Bibtex
Author : Hongbo Yu, Jiazhe Chen, Xiaoyun Wang
Title : The Boomerang Attacks on the Round-Reduced Skein-512
In : -
Address :
Date : 2012

Hongbo Yu, Jiazhe Chen, Ketingjia, Xiaoyun Wang - Near-Collision Attack on the Step-Reduced Compression Function of Skein-256

,2011
http://eprint.iacr.org/2011/148.pdf
Bibtex
Author : Hongbo Yu, Jiazhe Chen, Ketingjia, Xiaoyun Wang
Title : Near-Collision Attack on the Step-Reduced Compression Function of Skein-256
In : -
Address :
Date : 2011

Dmitry Khovratovich, Ivica Nikolić, Christian Rechberger - Rotational Rebound Attacks on Reduced Skein

ASIACRYPT 6477:1-19,2010
http://eprint.iacr.org/2010/538.pdf
Bibtex
Author : Dmitry Khovratovich, Ivica Nikolić, Christian Rechberger
Title : Rotational Rebound Attacks on Reduced Skein
In : ASIACRYPT -
Address :
Date : 2010

Bozhan Su, Wenling Wu, Shuang Wu, Le Dong - Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE

CANS 6467:124-139,2010
http://eprint.iacr.org/2010/355.pdf
Bibtex
Author : Bozhan Su, Wenling Wu, Shuang Wu, Le Dong
Title : Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE
In : CANS -
Address :
Date : 2010

Danilo Gligoroski - Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains

,2010
http://people.item.ntnu.no/~danilog/Hash/Non-random-behaviour-narrow-pipe-designs-03.pdf
Bibtex
Author : Danilo Gligoroski
Title : Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains
In : -
Address :
Date : 2010

Kerry A. McKay, Poorvi L. Vora - Pseudo-Linear Approximations for ARX Ciphers: With Application to Threefish

,2010
http://eprint.iacr.org/2010/282.pdf
Bibtex
Author : Kerry A. McKay, Poorvi L. Vora
Title : Pseudo-Linear Approximations for ARX Ciphers: With Application to Threefish
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

Dmitry Khovratovich, Ivica Nikolic - Rotational Cryptanalysis of ARX

FSE 6147:333-346
http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf
Bibtex
Author : Dmitry Khovratovich, Ivica Nikolic
Title : Rotational Cryptanalysis of ARX
In : FSE -
Address :
Date :

Jiazhe Chen, Keting Jia - Improved Related-key Boomerang Attacks on Round-Reduced Threefish-512

,2009
http://eprint.iacr.org/2009/526.pdf
Bibtex
Author : Jiazhe Chen, Keting Jia
Title : Improved Related-key Boomerang Attacks on Round-Reduced Threefish-512
In : -
Address :
Date : 2009

Jean-Philippe Aumasson, Cagdas Calik, Willi Meier, Onur Ozen, Raphael C.-W. Phan, Kerem Varici - Improved Cryptanalysis of Skein

ASIACRYPT 5912:542-559,2009
http://eprint.iacr.org/2009/438.pdf
Bibtex
Author : Jean-Philippe Aumasson, Cagdas Calik, Willi Meier, Onur Ozen, Raphael C.-W. Phan, Kerem Varici
Title : Improved Cryptanalysis of Skein
In : ASIACRYPT -
Address :
Date : 2009

Jean-Philippe Aumasson, Willi Meier, Raphael Phan - Improved analyis of Threefish

,2009
http://131002.net/data/talks/threefish_rump.pdf
Bibtex
Author : Jean-Philippe Aumasson, Willi Meier, Raphael Phan
Title : Improved analyis of Threefish
In : -
Address :
Date : 2009
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Skein&oldid=3765"