Difference between revisions of "Skein"

From The ECRYPT Hash Function Website
m
(added rotational attack on reduced threefish)
Line 35: Line 35:
 
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 (n=256,512)
  
 
=== Hash function ===
 
=== Hash function ===
  
−
Here we list results on the actual hash function. 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.
−
 
 
−
Recommended security parameter: '''72''' rounds (Skein-512)
 
  
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
 
{| border="1" cellpadding="4" cellspacing="0" class="wikitable" style="text-align:center"                   
Line 72: Line 71:
 
|-   
 
|-   
 
|  key recovery || block cipher || 512 || 33 rounds (Round 1) || 2<sup>352.17</sup> (2<sup>355.5</sup>) || - || [http://eprint.iacr.org/2009/526.pdf Chen,Jia]
 
|  key recovery || block cipher || 512 || 33 rounds (Round 1) || 2<sup>352.17</sup> (2<sup>355.5</sup>) || - || [http://eprint.iacr.org/2009/526.pdf Chen,Jia]
 +
|-
 +
|  key recovery || block cipher || 256 || 39 rounds || 2<sup>254.1</sup> || - || [https://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf Khovratovich,Nikolic]
 +
|-
 +
|  key recovery || block cipher || 512 || 42 rounds|| 2<sup>507</sup> || - || [https://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf Khovratovich,Nikolic]
 
|-
 
|-
 
|}         
 
|}         
Line 99: Line 102:
 
     note = {\url{http://eprint.iacr.org/}},
 
     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>
 +
@misc{cryptoeprint:2009:526,
 +
    author = {Dmitry Khovratovich and Ivica Nikolic},
 +
    title = {Rotational Cryptanalysis of ARX},
 +
    howpublished = {Preproceedings of FSE 2010},
 +
    year = {2010},
 +
    url = {https://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>

Revision as of 18:01, 15 February 2010

1 The algorithm


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/skein.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 (n=256,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

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
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
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
key recovery block cipher 256 39 rounds 2254.1 - Khovratovich,Nikolic
key recovery block cipher 512 42 rounds 2507 - Khovratovich,Nikolic



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

,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 : -
Address :
Date : 2009

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

Dmitry Khovratovich, Ivica Nikolic - Rotational Cryptanalysis of ARX

,2010
https://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf
Bibtex
Author : Dmitry Khovratovich, Ivica Nikolic
Title : Rotational Cryptanalysis of ARX
In : -
Address :
Date : 2010

2.3 Archive

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=3382"