Difference between revisions of "Skein"

Revision as of 11:52, 8 November 2010

1 The algorithm

Author(s): Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, Jesse Walker
Website: http://www.schneier.com/skein.html; http://skein-hash.info/
NIST submission package:
- round 1: SkeinUpdate.zip (old version: Skein.zip)
- round 2: Skein_Round2.zip

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
near-collision	compression function	all	24 rounds (No. 20-43)	2²³⁰	-	Su,Wu,Wu,Dong
near-collision	compression function	256	24 rounds (No. 12-35), Skein-256	2⁶⁰	-	Su,Wu,Wu,Dong
near-collision	compression function	all	24 rounds, Skein-1024	2³⁹⁵	-	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	2^254.1	-	Khovratovich,Nikolic
key recovery	block cipher	512	42 rounds	2⁵⁰⁷	-	Khovratovich,Nikolic
key recovery	block cipher	512	32 rounds (Round 1)	2²²⁶ (2²²²)	2¹²	Chen,Jia
key recovery	block cipher	512	33 rounds (Round 1)	2^352.17 (2^355.5)	-	Chen,Jia
near collision	compression function	512	17 rounds (Round 1)	2²⁴	-	Aumasson,Calik,Meier,Ozen,Phan,Varici
distinguisher	block cipher	512	35 rounds (Round 1)	2⁴⁷⁸	-	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)	2³¹²	-	Aumasson,Calik,Meier,Ozen,Phan,Varici

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

@@ Line 136: / Line 136: @@
 <bibtex>
-@misc{skeinA+09,
+@misc{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},
+     howpublished = {Preproceedings of FSE 2010},
-     year = {2009},
+     year = {2010},
-     url = {http://eprint.iacr.org/2009/438.pdf},
+     url = {http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf},
-    note = {\url{http://eprint.iacr.org/}},
+     abstract = {In this paper we analyze the security of systems based on
-     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.},
+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 Threeﬁsh (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>
@@ Line 160: / Line 168: @@
 <bibtex>
-@misc{cryptoeprint:2009:526,
+@misc{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},
+     howpublished = {Cryptology ePrint Archive, Report 2009/438},
-     year = {2010},
+     year = {2009},
-     url = {http://cryptolux.org/mediawiki/uploads/5/5b/Rotational_Cryptanalysis_of_Skein.pdf},
+     url = {http://eprint.iacr.org/2009/438.pdf},
-     abstract = {In this paper we analyze the security of systems based on
+    note = {\url{http://eprint.iacr.org/}},
-modular additions, rotations, and XORs (ARX systems). We provide
+     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.},
-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 Threeﬁsh (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>

Difference between revisions of "Skein"

Revision as of 11:52, 8 November 2010

Contents

1 The algorithm

2 Cryptanalysis

2.1 Hash function

2.2 Building blocks

2.3 Archive

Navigation menu

Views

Personal tools

Navigation

Search

Tools