Difference between revisions of "Keccak"

From The ECRYPT Hash Function Website
(Cryptanalysis updated)
(Cryptanalysis updated)
Line 65: Line 65:
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
| Type of Analysis || Hash Size (n) || Parameters || Compression Function Calls || Memory Requirements ||  Reference  
 
|-                     
 
|-                     
−
| || || || || ||
+
| 2nd preimage || 512 || 6 rounds || 2<sup>506</sup> || 2<sup>176</sup> || [http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt Bernstein]
 +
|-                   
 +
| 2nd preimage || 512 || 7 rounds || 2<sup>507</sup> || 2<sup>320</sup> || [http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt Bernstein]
 +
|-                   
 +
| 2nd preimage || 512 || 8 rounds || 2<sup>511.5</sup> || 2<sup>508</sup> || [http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt Bernstein]
 
|-                     
 
|-                     
 
|}
 
|}
Line 79: Line 83:
 
| 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  
 
|-   
 
|-   
−
| distinguisher  || permutation || all || || 2<sup>1590</sup> || || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
+
| distinguisher  || permutation || all || 24 rounds || 2<sup>1590</sup> || || [http://eprint.iacr.org/2010/589.pdf Boura,Canteaut,DeCanniere]
 
|-   
 
|-   
 
| distinguisher  || permutation || all || 20 rounds || 2<sup>1586</sup> || || [http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf Boura,Canteaut]
 
| distinguisher  || permutation || all || 20 rounds || 2<sup>1586</sup> || || [http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf Boura,Canteaut]
Line 99: Line 103:
 
<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>).
 
<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>).
  
 +
 +
<bibtex>
 +
@misc{KeccakBernstein10,
 +
author = {Daniel J. Bernstein},
 +
title = {Second preimages for 6 (7? (8??)) rounds of Keccak?},
 +
url = {http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt},
 +
howpublished = {NIST mailing list},
 +
year = {2010},
 +
}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Revision as of 17:39, 6 December 2010

1 The algorithm


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.

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
2nd preimage 512 6 rounds 2506 2176 Bernstein
2nd preimage 512 7 rounds 2507 2320 Bernstein
2nd preimage 512 8 rounds 2511.5 2508 Bernstein

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 24 rounds 21590 Boura,Canteaut,DeCanniere
distinguisher permutation all 20 rounds 21586 Boura,Canteaut
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 ? 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).


Daniel J. Bernstein - Second preimages for 6 (7? (8??)) rounds of Keccak?

,2010
http://ehash.iaik.tugraz.at/uploads/6/65/NIST-mailing-list_Bernstein-Daemen.txt
Bibtex
Author : Daniel J. Bernstein
Title : Second preimages for 6 (7? (8??)) rounds of Keccak?
In : -
Address :
Date : 2010

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

,2010
http://eprint.iacr.org/2010/589.pdf
Bibtex
Author : Christina Boura, Anne Canteaut, Christophe De Canniere
Title : Higher-order differential properties of Keccak and Luffa
In : -
Address :
Date : 2010

Christina Boura, Anne Canteau - Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256

SAC ,2010
http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf
Bibtex
Author : Christina Boura, Anne Canteau
Title : Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256
In : SAC -
Address :
Date : 2010

Pawel Morawiecki, Marian Srebrny - A SAT-based preimage analysis of reduced KECCAK hash functions

,2010
http://eprint.iacr.org/2010/285.pdf
Bibtex
Author : 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
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
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=Keccak&oldid=3642"