Difference between revisions of "Keccak"

Revision as of 11:06, 15 February 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
Bibtex

Author : 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
Bibtex

Author : 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
Bibtex

Author : 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
Bibtex

Author : 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.

2.1 Hash function

Here we list results on the actual hash function. The only allowed modification is to change the security parameter.

Recommended security parameter: 24 rounds (Keccak-f [1600])

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⁽¹⁾	permutation	all	18 rounds	2¹³⁷⁰		Boura,Canteaut
distinguisher⁽¹⁾	permutation	all	16 rounds	2^1023.88		Aumasson,Meier
key recovery	secret-prefix MAC	224	4 rounds	2¹⁹	?	Joel,Lathrop
observations	permutation	all				Aumasson,Khovratovich

⁽¹⁾The Keccak team commented on these distinguishers and provide generic constructions in this note.

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Note on zero-sum distinguishers of Keccak-f

,2010

http://keccak.noekeon.org/NoteZeroSum.pdf
Bibtex

Author : 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
Bibtex

Author : 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
Bibtex

Author : 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
Bibtex

Author : Joel Lathrop
Title : Cube Attacks on Cryptographic Hash Functions
In : -
Address :
Date : 2009

Jean-Philippe Aumasson, Dmitry Khovratovich - First Analysis of Keccak

,2009

http://131002.net/data/papers/AK09.pdf
Bibtex

Author : Jean-Philippe Aumasson, Dmitry Khovratovich
Title : First Analysis of Keccak
In : -
Address :
Date : 2009

@@ Line 79: / Line 79: @@
 |- style="background:#efefef;"
 | Type of Analysis || Hash Function Part || Hash Size (n) || Parameters/Variants || Compression Function Calls || Memory Requirements ||   Reference
-|-
-| observations || permutation || all ||  ||  ||  || [http://131002.net/data/papers/AK09.pdf Aumasson,Khovratovich]
 |-
-| cube attack  || partial preimage || 224 || 4 rounds || 2<sup>19</sup> || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Joel,Lathrop]
+| 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 || 16 rounds || 2<sup>1023.88</sup> || || [http://www.131002.net/data/papers/AM09.pdf Aumasson,Meier]
 |-
-| 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]
+| key recovery  || secret-prefix MAC || 224 || 4 rounds || 2<sup>19</sup> || ? || [http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf Joel,Lathrop]
+|-
+| observations || permutation || all ||  ||  ||  || [http://131002.net/data/papers/AK09.pdf Aumasson,Khovratovich]
 |-
 |}
 <sup>(1)</sup>The Keccak team commented on these distinguishers and provide generic constructions in [http://keccak.noekeon.org/NoteZeroSum.pdf this note].
 <bibtex>
-@misc{keccakAK09,
+@misc{KeccakNoteZeroSum,
-  author    = {Jean-Philippe Aumasson and Dmitry Khovratovich},
+author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
-  title     = {First Analysis of Keccak},
+title = {Note on zero-sum distinguishers of Keccak-f},
-  url        = {http://131002.net/data/papers/AK09.pdf},
+url = {http://keccak.noekeon.org/NoteZeroSum.pdf},
-  howpublished = {Available online},
+howpublished = {NIST mailing list},
-  year      = {2009},
+year = {2010},
-  abstract  = {We apply known automated cryptanalytic tools to the Keccak-f[1600] permutation, using
-a triangulation tool to solve the CICO problem, and cube testers to detect some structure in the
-algebraic description of the reduced Keccak-f[1600]. The applicability of our tools was notably limited
-by the strength of the inverse permutation.},
-}
-</bibtex>
-<bibtex>
-@misc{keccakAK09,
-  author    = {Joel Lathrop},
-  title     = {Cube Attacks on Cryptographic Hash Functions},
-  url        = {http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf},
-  howpublished = {Available online},
-  year      = {2009},
-  abstract  = {The thesis includes a successful cube attack against 4-round Keccak complete with a table of maxterms, analysis of the attack, and the estimated limits of its extension to higher numbers of rounds.},
 }
-</bibtex>
-<bibtex>
-@misc{keccakAM09,
-  author    = {Jean-Philippe Aumasson and Willi Meier},
-  title     = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
-  url        = {http://www.131002.net/data/papers/AM09.pdf},
-  howpublished = {NIST mailing list}
-  year      = {2009},
-  abstract  = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
 </bibtex>
@@ Line 151: / Line 125: @@
 <bibtex>
-@misc{KeccakNoteZeroSum,
+@misc{keccakAM09,
-author = {G. Bertoni and J. Daemen and M. Peeters and G. Van Assche},
+  author    = {Jean-Philippe Aumasson and Willi Meier},
-title = {Note on zero-sum distinguishers of Keccak-f},
+  title     = {Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi},
-url = {http://keccak.noekeon.org/NoteZeroSum.pdf},
+  url        = {http://www.131002.net/data/papers/AM09.pdf},
-howpublished = {NIST mailing list},
+  howpublished = {NIST mailing list}
-year = {2010},
+  year      = {2009},
+  abstract  = {We present a new type of distinguisher, called zero-sum distinguisher, and apply it to reduced versions of the Keccak-f permutation. We obtain practical and deterministic distinguishers on up to 9 rounds, and shortcut distinguishers on up to 16 rounds, out of 18 in total. These observations do not seem to affect the security of Keccak. We also briefly describe application of zero-sum distinguishers to the core permutations of Luffa and Hamsi.},
+</bibtex>
+<bibtex>
+@misc{keccakAK09,
+  author    = {Joel Lathrop},
+  title     = {Cube Attacks on Cryptographic Hash Functions},
+  url        = {http://www.cs.rit.edu/~jal6806/thesis/thesis.pdf},
+  howpublished = {Available online},
+  year      = {2009},
+  abstract  = {The thesis includes a successful cube attack against 4-round Keccak complete with a table of maxterms, analysis of the attack, and the estimated limits of its extension to higher numbers of rounds.},
+}
+</bibtex>
+<bibtex>
+@misc{keccakAK09,
+  author    = {Jean-Philippe Aumasson and Dmitry Khovratovich},
+  title     = {First Analysis of Keccak},
+  url        = {http://131002.net/data/papers/AK09.pdf},
+  howpublished = {Available online},
+  year      = {2009},
+  abstract  = {We apply known automated cryptanalytic tools to the Keccak-f[1600] permutation, using
+a triangulation tool to solve the CICO problem, and cube testers to detect some structure in the
+algebraic description of the reduced Keccak-f[1600]. The applicability of our tools was notably limited
+by the strength of the inverse permutation.},
 }
 </bibtex>

Difference between revisions of "Keccak"

Revision as of 11:06, 15 February 2010

Contents

1 The algorithm

2 Cryptanalysis

2.1 Hash function

2.2 Building blocks

Navigation menu

Views

Personal tools

Navigation

Search

Tools