Difference between revisions of "Skein"

From The ECRYPT Hash Function Website
m (fixed bibtex ordering)
(added eprint 2010/538 result)
Line 58: Line 58:
 
|- 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  
 +
|-
 +
| distinguisher || compression function || all || 57 rounds || 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]
 
|-
 
|-
 
| 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 || all || 24 rounds (No. 20-43) || 2<sup>230</sup>  || - || [http://eprint.iacr.org/2010/355.pdf Su,Wu,Wu,Dong]
Line 91: Line 95:
  
 
<bibtex>
 
<bibtex>
@misc{blakeSuWWD10,
+
@misc{skeinKNR10,
 +
  author = {Dmitry Khovratovich and Ivica Nikolić and Christian Rechberger},
 +
  title = {Rotational Rebound Attacks on Reduced Skein},
 +
  howpublished = {Cryptology ePrint Archive, Report 2010/538},
 +
  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.
 +
 
 +
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>
 +
@misc{skeinSuWWD10,
 
   author = {Bozhan Su and Wenling Wu and Shuang Wu and Le Dong},
 
   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},
 
   title = {Near-Collisions on the Reduced-Round Compression Functions of Skein and BLAKE},
Line 102: Line 119:
  
 
<bibtex>
 
<bibtex>
@misc{skinGli10,
+
@misc{skeinGli10,
 
   author    = {Danilo Gligoroski},
 
   author    = {Danilo Gligoroski},
 
   title    = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},
 
   title    = {Narrow-pipe SHA-3 candidates differ significantly from ideal random functions defined over big domains},

Revision as of 12:02, 8 November 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 (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

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
distinguisher compression function all 57 rounds 2503 - Khovratovich,Nikolić,Rechberger
distinguisher compression function 256 53 rounds 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, Ivica Nikolić, Christian Rechberger - Rotational Rebound Attacks on Reduced Skein

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

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

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

,2010
http://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

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

,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

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