Groestl

From The ECRYPT Hash Function Website

Jump to: navigation, search

Contents

1 The algorithm


Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate
Submission to NIST (Round 3), 2011
[Electronic Edition] [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 : Submission to NIST (Round 3) -

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl Addendum
Submission to NIST (Round 2), 2009
[Electronic Edition] [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 : Submission to NIST (Round 2) -

Praveen Gauravaram, Lars R. Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Grøstl -- a SHA-3 candidate
Submission to NIST (Round 1/2), 2008
[Electronic Edition] [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 : Submission to NIST (Round 1/2) -

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 264 - Schläffer
collision 512 3 rounds 2192 - 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 2368 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 8 rounds 2280 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 9 rounds 2328 264 Jean,Naya-Plasencia,Peyrin
distinguisher permutation 512 10 rounds 2392 264 Jean,Naya-Plasencia,Peyrin
preimage output transformation 256 5 rounds 2206 248 Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage hash function 256 5 rounds 2244.85 2230.13 Wu,Feng,Wu,Guo,Dong,Zou
preimage output transformation 512 8 rounds 2495 216 Wu,Feng,Wu,Guo,Dong,Zou
pseudo preimage hash function 512 8 rounds 2507.32 2507 Wu,Feng,Wu,Guo,Dong,Zou
preimage output transformation 256 6 rounds 2251 Khovratovich
preimage compression function 256 6 rounds 2128 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 6 rounds / 264 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 6 rounds / 28 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 7 rounds / 280 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 7 rounds / 224 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 8 rounds / 2192 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 8 rounds / 2136 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage compression function 256 9 rounds / 2192 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 5 rounds / 264 targets 280 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 216 targets 2136 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 264 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 6 rounds / 28 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 7 rounds / 280 targets 264 264 Emami,Guaravaram,Pieprzyk,Steinfeld
chosen multitarget preimage hash function 256 7 rounds / 224 targets 2120 264 Emami,Guaravaram,Pieprzyk,Steinfeld
preimage hash function 256 5 rounds 2144 264 Emami,Guaravaram,Pieprzyk,Steinfeld
preimage hash function 256 6 rounds 2144 264 Emami,Guaravaram,Pieprzyk,Steinfeld
pseudo preimage hash function 256 6 rounds 2128 264 Emami,Guaravaram,Pieprzyk,Steinfeld
distinguisher permutation 256 10 rounds 2509 Boura,Canteaut,DeCannière
semi-free-start collision compression function 256 6 rounds 2120 264 Schläffer
semi-free-start collision compression function 384,512 6 rounds 2180 264 Schläffer
collision hash function 224,256 5 rounds (Round 1/2) 248 232 Ideguchi,Tischhauser,Preneel
collision hash function 256 6 rounds (Round 1/2) 2112 232 Ideguchi,Tischhauser,Preneel
collision hash function 224,256 4 rounds (Round 1/2) 264 264 Mendel,Rechberger,Schläffer,Thomsen
collision hash function 224,256 3 rounds (Round 1/2) 264 - Mendel,Rechberger,Schläffer,Thomsen
collision hash function 384,512 5 rounds (Round 1/2) 2176 264 Mendel,Rechberger,Schläffer,Thomsen
collision hash function 384,512 4 rounds (Round 1/2) 264 264 Mendel,Rechberger,Schläffer,Thomsen
distinguisher compression function 256 10 rounds (Round 1/2) 2175 264 Naya-Plasencia
distinguisher compression function 512 11 rounds (Round 1/2) 2630 264 Naya-Plasencia
distinguisher permutation 256 8 rounds 248 28 Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision compression function 512 7 rounds 2152 256 Sasaki,Li,Wang,Sakiyama,Ohta
semi-free-start collision compression function 224,256 7 rounds (Round 1/2) 280 232 Ideguchi,Tischhauser,Preneel
semi-free-start collision compression function 224,256 8 rounds (Round 1/2) 2192 264 Ideguchi,Tischhauser,Preneel
distinguisher permutation 224,256 7 rounds 219 - Ideguchi,Tischhauser,Preneel
distinguisher permutation 224,256 8 rounds 264 264 Ideguchi,Tischhauser,Preneel
distinguisher compression function 256 10 rounds (Round 1/2) 2192 264 Peyrin
distinguisher compression function 256 9 rounds (Round 1/2) 280 264 Peyrin
distinguisher compression function 512 11 rounds (Round 1/2) 2640 264 Peyrin
semi-free-start collision compression function 256 7 rounds (Round 1/2) 2120 264 Gilbert,Peyrin
distinguisher compression function 256 8 rounds (Round 1/2) 2112 264 Gilbert,Peyrin
distinguisher permutation 256 8 rounds 2112 264 Gilbert,Peyrin
semi-free-start collision compression function 256 7 rounds (Round 1/2) 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 384,512 7 rounds (Round 1/2) 2152 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 224,256 6 rounds (Round 1/2) 264 264 Mendel,Peyrin,Rechberger,Schläffer
distinguisher output transformation 224,256 7 rounds 256 - Mendel,Peyrin,Rechberger,Schläffer
distinguisher permutation 224,256 7 rounds 255 - Mendel,Peyrin,Rechberger,Schläffer
semi-free-start collision compression function 256 6 rounds (Round 1/2) 2120 264 Mendel,Rechberger,Schläffer,Thomsen
semi-free-start collision compression function 224,256 5 rounds (Round 1/2) 264 - Mendel,Rechberger,Schläffer,Thomsen
observation hash all Kelsey
observation block cipher all Barreto
free-start collision compression function all any 22n/3 22n/3 submission document
pseudo-preimage compression function all any 2n - submission document


Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin - Improved Rebound Attack on the Finalist Grøstl.
In Proceedings of FSE, , pp. 110-126, 2012
[Electronic Edition] [Bibtex]
Author : Jérémy Jean, María Naya-Plasencia, Thomas Peyrin, Thomas Peyrin
Title : Improved Rebound Attack on the Finalist Grøstl.
In : In Proceedings of FSE -
[Abstract]

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)
Cryptology ePrint Archive, Report 2012/206, 2012
[Electronic Edition] [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 : Cryptology ePrint Archive, Report 2012/206 -
[Abstract]

Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld - (Chosen-multi-target) preimage attacks on reduced Grøstl-0
[Electronic Edition] [Bibtex]
Author : Sareh Emami, Praveen Gauravaram, Josef Pieprzyk, Ron Steinfeld
Title : (Chosen-multi-target) preimage attacks on reduced Grøstl-0
In : -
[Abstract]

Dmitry Khovratovich - Bicliques for permutations: collision and preimage attacks in stronger settings
Cryptology ePrint Archive, Report 2012/141, 2012
[Electronic Edition] [Bibtex]
Author : Dmitry Khovratovich
Title : Bicliques for permutations: collision and preimage attacks in stronger settings
In : Cryptology ePrint Archive, Report 2012/141 -
[Abstract]

Christina Boura, Anne Canteaut, Christophe De Cannière - Higher-order differential properties of Keccak and Luffa
In Proceedings of FSE, LNCS 6733, pp. 252-269, Springer, 2011
[Electronic Edition] [Bibtex]
Author : Christina Boura, Anne Canteaut, Christophe De Cannière
Title : Higher-order differential properties of Keccak and Luffa
In : In Proceedings of FSE -
[Abstract]

Martin Schläffer - Updated Differential Analysis of Grøstl
Grøstl website, January, 2011
[Electronic Edition] [Bibtex]
Author : Martin Schläffer
Title : Updated Differential Analysis of Grøstl
In : Grøstl website -
[Abstract]

María Naya-Plasencia - Scrutinizing rebound attacks: new algorithms for improving the complexities
Cryptology ePrint Archive, Report 2010/607, 2010
[Electronic Edition] [Bibtex]
Author : María Naya-Plasencia
Title : Scrutinizing rebound attacks: new algorithms for improving the complexities
In : Cryptology ePrint Archive, Report 2010/607 -
[Abstract]

Yu Sasaki, Yang Li, Lei Wang, Kazuo Sakiyama, Kazuo Ohta - New Non-Ideal Properties of AES-Based Permutations: Applications to ECHO and Grøstl
In Proceedings of ASIACRYPT, LNCS 6477, pp. 38-55, Springer, 2010
[Electronic Edition] [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 : In Proceedings of ASIACRYPT -
[Abstract]

Kota Ideguchi, Elmar Tischhauser, Bart Preneel - Improved Collision Attacks on the Reduced-Round Grøstl Hash Function
In Proceedings of ISC, LNCS 6531, pp. 1-16, Springer, 2010
[Electronic Edition] [Bibtex]
Author : Kota Ideguchi, Elmar Tischhauser, Bart Preneel
Title : Improved Collision Attacks on the Reduced-Round Grøstl Hash Function
In : In Proceedings of ISC -
[Abstract]

Thomas Peyrin - Improved Differential Attacks for ECHO and Grostl
In Proceedings of CRYPTO, LNCS 6223, pp. 370-392, Springer, 2010
[Electronic Edition] [Bibtex]
Author : Thomas Peyrin
Title : Improved Differential Attacks for ECHO and Grostl
In : In Proceedings of CRYPTO -
[Abstract]

Henri Gilbert, Thomas Peyrin - Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations
In Proceedings of FSE, LNCS 6147, pp. 365-383, Springer, 2010
[Electronic Edition] [Bibtex]
Author : Henri Gilbert, Thomas Peyrin
Title : Super-Sbox Cryptanalysis: Improved Attacks for AES-like permutations
In : In Proceedings of FSE -
[Abstract]

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - Rebound Attacks on the Reduced Grøstl Hash Function
In Proceedings of CT-RSA, LNCS 5985, pp. 350-365, Springer, 2010
[Electronic Edition] [Bibtex]
Author : Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen
Title : Rebound Attacks on the Reduced Grøstl Hash Function
In : In Proceedings of CT-RSA -
[Abstract]

Florian Mendel, Thomas Peyrin, Christian Rechberger, Martin Schläffer - Improved Cryptanalysis of the Reduced Grøstl Compression Function, ECHO Permutation and AES Block Cipher
In Proceedings of SAC, LNCS 5867, pp. 16-35, Springer, 2009
[Electronic Edition] [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 : In Proceedings of SAC -
[Abstract]

Florian Mendel, Christian Rechberger, Martin Schläffer, Søren S. Thomsen - The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl
In Proceedings of FSE, LNCS 5665, pp. 260-276, Springer, 2009
[Electronic Edition] [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 : In Proceedings of FSE -
[Abstract]

John Kelsey - Some notes on Grøstl
NIST hash function mailing list, April, 2009
[Electronic Edition] [Bibtex]
Author : John Kelsey
Title : Some notes on Grøstl
In : NIST hash function mailing list -
[Abstract]

Paulo S. L. M. Barreto - An observation on Grøstl
NIST hash function mailing list, November, 2008
[Electronic Edition] [Bibtex]
Author : Paulo S. L. M. Barreto
Title : An observation on Grøstl
In : NIST hash function mailing list -
[Abstract]
Personal tools