Difference between revisions of "Groestl"

Latest revision as of 11:12, 1 August 2013

1 The algorithm

Author(s): Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Website: http://www.groestl.info
NIST submission package:
- Round 3: Groestl_FinalRnd.zip
- Round 1/2: Grostl_Round2.zip (old version: Grostl.zip)

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate

,2011

http://www.groestl.info/Groestl.pdf
Bibtex

Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl -- a SHA-3 candidate
In : -
Address :
Date : 2011

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl Addendum

,2009

http://groestl.info/Groestl-addendum.pdf
Bibtex

Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl Addendum
In : -
Address :
Date : 2009

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate

,2008

http://groestl.info/Groestl-0.pdf
Bibtex

Author : Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Grøstl -- a SHA-3 candidate
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: 10 rounds (n=224,256); 14 rounds (n=384,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	224,256	3 rounds	2⁶⁴	-	Schläffer
collision	512	3 rounds	2¹⁹²	-	Schläffer

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	permutation	256	9 rounds	2³⁶⁸	2⁶⁴	Jean,Naya-Plasencia,Peyrin
distinguisher	permutation	512	8 rounds	2²⁸⁰	2⁶⁴	Jean,Naya-Plasencia,Peyrin
distinguisher	permutation	512	9 rounds	2³²⁸	2⁶⁴	Jean,Naya-Plasencia,Peyrin
distinguisher	permutation	512	10 rounds	2³⁹²	2⁶⁴	Jean,Naya-Plasencia,Peyrin
preimage	output transformation	256	5 rounds	2²⁰⁶	2⁴⁸	Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage	hash function	256	5 rounds	2^244.85	2^230.13	Wu,Feng,Wu,Guo,Dong,Zou
preimage	output transformation	512	8 rounds	2⁴⁹⁵	2¹⁶	Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage	hash function	512	8 rounds	2^507.32	2⁵⁰⁷	Wu,Feng,Wu,Guo,Dong,Zou
preimage	output transformation	256	6 rounds	2²⁵¹		Khovratovich
preimage	compression function	256	6 rounds	2¹²⁸		Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	6 rounds / 2⁶⁴ targets	2⁶⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	6 rounds / 2⁸ targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	7 rounds / 2⁸⁰ targets	2⁶⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	7 rounds / 2²⁴ targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	8 rounds / 2¹⁹² targets	2⁶⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	8 rounds / 2¹³⁶ targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	compression function	256	9 rounds / 2¹⁹² targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	5 rounds / 2⁶⁴ targets	2⁸⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	6 rounds / 2¹⁶ targets	2¹³⁶	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	6 rounds / 2⁶⁴ targets	2⁶⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	6 rounds / 2⁸ targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	7 rounds / 2⁸⁰ targets	2⁶⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage	hash function	256	7 rounds / 2²⁴ targets	2¹²⁰	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
preimage	hash function	256	5 rounds	2¹⁴⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
preimage	hash function	256	6 rounds	2¹⁴⁴	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
pseudo preimage	hash function	256	6 rounds	2¹²⁸	2⁶⁴	Emami,Guaravaram,Pieprzyk,Steinfeld
distinguisher	permutation	256	10 rounds	2⁵⁰⁹		Boura,Canteaut,DeCannière
semi-free-start collision	compression function	256	6 rounds	2¹²⁰	2⁶⁴	Schläffer
semi-free-start collision	compression function	384,512	6 rounds	2¹⁸⁰	2⁶⁴	Schläffer
collision	hash function	224,256	5 rounds (Round 1/2)	2⁴⁸	2³²	Ideguchi,Tischhauser,Preneel
collision	hash function	256	6 rounds (Round 1/2)	2¹¹²	2³²	Ideguchi,Tischhauser,Preneel
collision	hash function	224,256	4 rounds (Round 1/2)	2⁶⁴	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
collision	hash function	224,256	3 rounds (Round 1/2)	2⁶⁴	-	Mendel,Rechberger,Schläffer,Thomsen
collision	hash function	384,512	5 rounds (Round 1/2)	2¹⁷⁶	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
collision	hash function	384,512	4 rounds (Round 1/2)	2⁶⁴	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
distinguisher	compression function	256	10 rounds (Round 1/2)	2¹⁷⁵	2⁶⁴	Naya-Plasencia
distinguisher	compression function	512	11 rounds (Round 1/2)	2⁶³⁰	2⁶⁴	Naya-Plasencia
distinguisher	permutation	256	8 rounds	2⁴⁸	2⁸	Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision	compression function	512	7 rounds	2¹⁵²	2⁵⁶	Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision	compression function	224,256	7 rounds (Round 1/2)	2⁸⁰	2³²	Ideguchi,Tischhauser,Preneel
semi-free-start collision	compression function	224,256	8 rounds (Round 1/2)	2¹⁹²	2⁶⁴	Ideguchi,Tischhauser,Preneel
distinguisher	permutation	224,256	7 rounds	2¹⁹	-	Ideguchi,Tischhauser,Preneel
distinguisher	permutation	224,256	8 rounds	2⁶⁴	2⁶⁴	Ideguchi,Tischhauser,Preneel
distinguisher	compression function	256	10 rounds (Round 1/2)	2¹⁹²	2⁶⁴	Peyrin
distinguisher	compression function	256	9 rounds (Round 1/2)	2⁸⁰	2⁶⁴	Peyrin
distinguisher	compression function	512	11 rounds (Round 1/2)	2⁶⁴⁰	2⁶⁴	Peyrin
semi-free-start collision	compression function	256	7 rounds (Round 1/2)	2¹²⁰	2⁶⁴	Gilbert,Peyrin
distinguisher	compression function	256	8 rounds (Round 1/2)	2¹¹²	2⁶⁴	Gilbert,Peyrin
distinguisher	permutation	256	8 rounds	2¹¹²	2⁶⁴	Gilbert,Peyrin
semi-free-start collision	compression function	256	7 rounds (Round 1/2)	2¹²⁰	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision	compression function	384,512	7 rounds (Round 1/2)	2¹⁵²	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision	compression function	224,256	6 rounds (Round 1/2)	2⁶⁴	2⁶⁴	Mendel,Peyrin,Rechberger,Schläffer
distinguisher	output transformation	224,256	7 rounds	2⁵⁶	-	Mendel,Peyrin,Rechberger,Schläffer
distinguisher	permutation	224,256	7 rounds	2⁵⁵	-	Mendel,Peyrin,Rechberger,Schläffer
semi-free-start collision	compression function	256	6 rounds (Round 1/2)	2¹²⁰	2⁶⁴	Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision	compression function	224,256	5 rounds (Round 1/2)	2⁶⁴	-	Mendel,Rechberger,Schläffer,Thomsen
observation	hash	all				Kelsey
observation	block cipher	all				Barreto
free-start collision	compression function	all	any	2^2n/3	2^2n/3	submission document
pseudo-preimage	compression function	all	any	2ⁿ	-	submission document

Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin - Improved Rebound Attack on the Finalist Grøstl.

FSE pp. 110-126,2012

http://dx.doi.org/10.1007/978-3-642-34047-5_7
Bibtex

Author : Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin
Title : Improved Rebound Attack on the Finalist Grøstl.
In : FSE -
Address :
Date : 2012

Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou - (Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)

,2012

http://eprint.iacr.org/2012/206.pdf
Bibtex

Author : Shuang Wu, Dengguo Feng, Wenling Wu, Jian Guo, Le Dong, Jian Zou
Title : (Pseudo) Preimage Attack on Round-Reduced Gr{\o}stl Hash Function and Others (Extended Version)
In : -
Address :
Date : 2012

Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld - (Chosen-multi-target) preimage attacks on reduced Grøstl-0

http://web.science.mq.edu.au/~rons/preimageattack-final.pdf
Bibtex

Author : Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld
Title : (Chosen-multi-target) preimage attacks on reduced Grøstl-0
In : -
Address :
Date :

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

Christina Boura, Anne Canteaut, Christophe De Cannière - Higher-order differential properties of Keccak and Luffa

FSE 6733:252-269,2011

http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf
Bibtex

Author : Christina Boura, Anne Canteaut, Christophe De Cannière
Title : Higher-order differential properties of Keccak and Luffa
In : FSE -
Address :
Date : 2011

Martin Schläffer - Updated Differential Analysis of Grøstl

, January 2011

http://groestl.info/groestl-analysis.pdf
Bibtex

Author : Martin Schläffer
Title : Updated Differential Analysis of Grøstl
In : -
Address :
Date : January 2011

María Naya-Plasencia - Scrutinizing rebound attacks: new algorithms for improving the complexities

,2010

http://eprint.iacr.org/2010/607.pdf
Bibtex

Author : María Naya-Plasencia
Title : Scrutinizing rebound attacks: new algorithms for improving the complexities
In : -
Address :
Date : 2010

Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta - New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl

ASIACRYPT 6477:38-55,2010

http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SASAKI_ECHOanalysisFinal.pdf
Bibtex

Author : Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta
Title : New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
In : ASIACRYPT -
Address :
Date : 2010

Kota Ideguchi, Elmar Tischhauser, Bart Preneel - Improved Collision Attacks on the Reduced-Round Grøstl Hash Function

ISC 6531:1-16,2010

http://eprint.iacr.org/2010/375.pdf
Bibtex

Author : Kota Ideguchi, Elmar Tischhauser, Bart Preneel
Title : Improved Collision Attacks on the Reduced-Round Grøstl Hash Function
In : ISC -
Address :
Date : 2010

Thomas Peyrin - Improved Differential Attacks for ECHO and Grostl

CRYPTO 6223:370-392,2010

http://eprint.iacr.org/2010/223.pdf
Bibtex

Author : Thomas Peyrin
Title : Improved Differential Attacks for ECHO and Grostl
In : CRYPTO -
Address :
Date : 2010

Henri Gilbert, Thomas Peyrin - Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations

FSE 6147:365-383,2010

http://eprint.iacr.org/2009/531.pdf
Bibtex

Author : Henri Gilbert, Thomas Peyrin
Title : Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations
In : FSE -
Address :
Date : 2010

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Rebound Attacks on the Reduced Grøstl Hash Function

CT-RSA 5985:350-365,2010

http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=128007&pCurrPk=47053
Bibtex

Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Rebound Attacks on the Reduced Grøstl Hash Function
In : CT-RSA -
Address :
Date : 2010

Florian Mendel, Thomas Peyrin, Christian Rechberger, Martin Schläffer - Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher

SAC 5867:16-35,2009

http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124407&pCurrPk=44420
Bibtex

Author : Florian Mendel, Thomas Peyrin, Christian

Rechberger, Martin Schläffer
Title : Improved Cryptanalysis of the Reduced Grøstl

Compression Function, ECHO Permutation and AES Block Cipher
In : SAC -
Address :
Date : 2009

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl

FSE 5665:260-276,2009

http://online.tu-graz.ac.at/tug_online/voe_main2.getVollText?pDocumentNr=124409&pCurrPk=40943
Bibtex

Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl
In : FSE -
Address :
Date : 2009

John Kelsey - Some notes on Grøstl

, April 2009

http://ehash.iaik.tugraz.at/uploads/d/d0/Grostl-comment-april28.pdf
Bibtex

Author : John Kelsey
Title : Some notes on Grøstl
In : -
Address :
Date : April 2009

Paulo S. L. M. Barreto - An observation on Grøstl

, November 2008

http://www.larc.usp.br/~pbarreto/Grizzly.pdf
Bibtex

Author : Paulo S. L. M. Barreto
Title : An observation on Grøstl
In : -
Address :
Date : November 2008

@@ Line 126: / Line 126: @@
 | distinguisher  || permutation || 256 || 10 rounds || 2<sup>509</sup> || || [http://fse2011.mat.dtu.dk/slides/Higher-order%20differential%20properties%20of%20Keccak%20and%20Luffa.pdf Boura,Canteaut,DeCannière]
 |-
-| semi-free-start collision || compression function || 256 || 6 rounds || 2<sup>112</sup> || 2<sup>64</sup> || [http://groestl.info/groestl-analysis.pdf Schläffer]
+| semi-free-start collision || compression function || 256 || 6 rounds || 2<sup>120</sup> || 2<sup>64</sup> || [http://groestl.info/groestl-analysis.pdf Schläffer]
 |-
 | semi-free-start collision || compression function || 384,512 || 6 rounds || 2<sup>180</sup> || 2<sup>64</sup> || [http://groestl.info/groestl-analysis.pdf Schläffer]

Difference between revisions of "Groestl"

Latest revision as of 11:12, 1 August 2013

Contents

1 The algorithm

2 Cryptanalysis

2.1 Hash function

2.2 Building blocks

Navigation menu

Views

Personal tools

Navigation

Search

Tools