Difference between revisions of "Keccak"

From The ECRYPT Hash Function Website
m
(Cryptanalysis updated)
Line 78: Line 78:
 
|- style="background:#efefef;"                   
 
|- style="background:#efefef;"                   
 
| 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 || 20 rounds || 2<sup>1586</sup> || || [http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf Boura,Canteaut]
 
|-   
 
|-   
 
| 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]
 
| 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]
Line 90: Line 94:
 
|-   
 
|-   
 
|}
 
|}
−
             
+
 
 
<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>).
 
<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{cryptoeprint:2009:224,
 +
    author = {Christina Boura and Anne Canteaut and Christophe De Canniere},
 +
    title = {Higher-order differential properties of Keccak and Luffa},
 +
    howpublished = {Cryptology ePrint Archive, Report 2010/589},
 +
    year = {2010},
 +
    note = {\url{http://eprint.iacr.org/}},
 +
    url = {http://eprint.iacr.org/2010/589.pdf},
 +
    abstract = {In this paper, we identify higher-order differential and zero-sum properties in the full Keccak-f permutation, in the Luffa v1 hash function, and in components of the Luffa v2 algorithm. These structural properties rely on a new bound on the degree of iterated permutations with a nonlinear layer composed of parallel applications of smaller balanced Sboxes. These techniques yield zero-sum partitions of size $2^{1590}$ for the full Keccak-f permutation and several observations on the Luffa hash family. We first show that Luffa v1 applied to one-block messages is a function of 255 variables with degree at most 251. This observation leads to the construction of a higher-order differential distinguisher for the full Luffa v1 hash function, similar to the one presented by Watanabe et al. on a reduced version. We show that similar techniques can be used to find all-zero higher-order differentials in the Luffa v2 compression function, but the additional blank round destroys this property in the hash function.},
 +
}
 +
</bibtex>
 +
 +
<bibtex>
 +
@inproceedings{sacBC10,
 +
  author = {Christina Boura, Anne Canteau},
 +
  title = {Zero-Sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256},
 +
  url = {http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf},
 +
  booktitle  = {SAC},
 +
  year      = {2010},
 +
  series    = {LNCS},
 +
  publisher  = {Springer},
 +
  note = {To appear}
 +
  abstract = {The zero-sum distinguishers introduced by Aumasson and Meier are investigated. First, the minimal size of a zero-sum is established. Then, we analyze the impacts of the linear and the nonlinear layers in an iterated permutation on the construction of zero-sum partitions. Finally, these techniques are applied to the Keccak-f permutation and to Hamsi-256. We exhibit several zero-sum partitions for 20 rounds (out of 24) of Keccak-f and some zero-sum partitions of size $2^{19}$ and $2^{10}$ for the finalization permutation in Hamsi-256.}
 +
</bibtex>
  
 
<bibtex>
 
<bibtex>

Revision as of 17:15, 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

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 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).


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=3640"