Difference between revisions of "Keccak"
Mschlaeffer (talk | contribs) (SAT-based preimage analysis added) |
Mschlaeffer (talk | contribs) m |
||
| Line 79: | Line 79: | ||
| 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 | ||
|- | |- | ||
| − | | preimage || hash || 1024 || 3 rounds, | + | | preimage<sup>(2)</sup> || hash || 1024 || 3 rounds, 40 bit message || 1852 seconds (2<sup>34.11</sup>) || ? || [http://eprint.iacr.org/2010/285.pdf Morawiecki,Srebrny] |
|- | |- | ||
| distinguisher<sup>(1)</sup> || permutation || all || 18 rounds || 2<sup>1370</sup> || || [http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf Boura,Canteaut] | | distinguisher<sup>(1)</sup> || permutation || all || 18 rounds || 2<sup>1370</sup> || || [http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf Boura,Canteaut] | ||
| Line 92: | Line 92: | ||
<sup>(1)</sup>The Keccak team commented on these distinguishers and provide generic constructions in [http://keccak.noekeon.org/NoteZeroSum.pdf this note]. | <sup>(1)</sup>The Keccak team commented on these distinguishers and provide generic constructions in [http://keccak.noekeon.org/NoteZeroSum.pdf this note]. | ||
| + | |||
| + | <sup>(2)</sup>The Keccak team estimated the complexity of this attack with 2<sup>34.11</sup> evaluations of 3-rounds of Keccak-f[1600] in [http://ehash.iaik.tugraz.at/uploads/5/5b/Note_SAT-basedPreimageAnalysis.txt this note] (exhaustive search: 2<sup>40</sup>). | ||
Revision as of 13:39, 18 June 2010
1 The algorithm
- Author(s): Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche
- Website: http://keccak.noekeon.org/
- NIST submission package:
- round 1: Keccak.zip
- round 2: Keccak_Round2.zip
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Keccak specifications
- ,2009
- http://keccak.noekeon.org/Keccak-specifications-2.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Keccak specifications
In : -
Address :
Date : 2009
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Keccak sponge function family main document
- ,2009
- http://keccak.noekeon.org/Keccak-main-2.0.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Keccak sponge function family main document
In : -
Address :
Date : 2009
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Keccak specifications
- ,2008
- http://keccak.noekeon.org/Keccak-specifications.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Keccak specifications
In : -
Address :
Date : 2008
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Keccak sponge function family main document
- ,2008
- http://keccak.noekeon.org/Keccak-main-1.0.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Keccak sponge function family main document
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: 24 rounds (Keccak-f [1600])
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 |
| preimage(2) | hash | 1024 | 3 rounds, 40 bit message | 1852 seconds (234.11) | ? | Morawiecki,Srebrny |
| distinguisher(1) | permutation | all | 18 rounds | 21370 | Boura,Canteaut | |
| distinguisher(1) | permutation | all | 16 rounds | 21023.88 | Aumasson,Meier | |
| key recovery | secret-prefix MAC | 224 | 4 rounds | 219 | ? | Joel,Lathrop |
| observations | permutation | all | Aumasson,Khovratovich |
(1)The Keccak team commented on these distinguishers and provide generic constructions in this note.
(2)The Keccak team estimated the complexity of this attack with 234.11 evaluations of 3-rounds of Keccak-f[1600] in this note (exhaustive search: 240).
Pawel Morawiecki, Marian Srebrny - A SAT-based preimage analysis of reduced KECCAK hash functions
- ,2010
- http://eprint.iacr.org/2010/285.pdf
BibtexAuthor : Pawel Morawiecki, Marian Srebrny
Title : A SAT-based preimage analysis of reduced KECCAK hash functions
In : -
Address :
Date : 2010
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Note on zero-sum distinguishers of Keccak-f
- ,2010
- http://keccak.noekeon.org/NoteZeroSum.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Note on zero-sum distinguishers of Keccak-f
In : -
Address :
Date : 2010
Christina Boura, Anne Canteaut - A Zero-Sum property for the Keccak-f Permutation with 18 Rounds
- ,2010
- http://www-roc.inria.fr/secret/Anne.Canteaut/Publications/zero_sum.pdf
BibtexAuthor : Christina Boura, Anne Canteaut
Title : A Zero-Sum property for the Keccak-f Permutation with 18 Rounds
In : -
Address :
Date : 2010
Jean-Philippe Aumasson, Willi Meier - Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi
- ,2009
- http://www.131002.net/data/papers/AM09.pdf
BibtexAuthor : Jean-Philippe Aumasson, Willi Meier
Title : Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi
In : -
Address :
Date : 2009
Joel Lathrop - Cube Attacks on Cryptographic Hash Functions
- ,2009
- http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf
BibtexAuthor : Joel Lathrop
Title : Cube Attacks on Cryptographic Hash Functions
In : -
Address :
Date : 2009
Jean-Philippe Aumasson, Dmitry Khovratovich - First Analysis of Keccak
