Difference between revisions of "Keccak"
Mschlaeffer (talk | contribs) m |
Mschlaeffer (talk | contribs) m (references updated) |
||
| Line 144: | Line 144: | ||
howpublished = {Cryptology ePrint Archive, Report 2011/023}, | howpublished = {Cryptology ePrint Archive, Report 2011/023}, | ||
year = {2011}, | year = {2011}, | ||
| − | |||
url = {http://eprint.iacr.org/2011/023.pdf}, | url = {http://eprint.iacr.org/2011/023.pdf}, | ||
abstract = {K$\textsc{eccak}$ is one of the five hash functions selected for the final round of the SHA-3 competition and its inner primitive is a permutation called K$\textsc{eccak}$-$f$. In this paper, we find that for the inverse of the only one nonlinear transformation of K$\textsc{eccak}$-$f$, the algebraic degrees of any output coordinate and of the product of any two output coordinates are both 3 and also 2 less than its size 5. Combining the observation with a proposition from an upper bound on the degree of iterated permutations, we improve the zero-sum distinguisher of full 24 rounds K$\textsc{eccak}$-$f$ permutation by lowering the size of the zero-sum partition from $2^{1590}$ to $2^{1579}$.}, | abstract = {K$\textsc{eccak}$ is one of the five hash functions selected for the final round of the SHA-3 competition and its inner primitive is a permutation called K$\textsc{eccak}$-$f$. In this paper, we find that for the inverse of the only one nonlinear transformation of K$\textsc{eccak}$-$f$, the algebraic degrees of any output coordinate and of the product of any two output coordinates are both 3 and also 2 less than its size 5. Combining the observation with a proposition from an upper bound on the degree of iterated permutations, we improve the zero-sum distinguisher of full 24 rounds K$\textsc{eccak}$-$f$ permutation by lowering the size of the zero-sum partition from $2^{1590}$ to $2^{1579}$.}, | ||
| Line 166: | Line 165: | ||
howpublished = {Cryptology ePrint Archive, Report 2010/589}, | howpublished = {Cryptology ePrint Archive, Report 2010/589}, | ||
year = {2010}, | year = {2010}, | ||
| − | |||
url = {http://eprint.iacr.org/2010/589.pdf}, | 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.}, | 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.}, | ||
| Line 180: | Line 178: | ||
year = {2010}, | year = {2010}, | ||
series = {LNCS}, | series = {LNCS}, | ||
| − | publisher | + | pages = {1-17}, |
| − | + | publisher = {Springer}, | |
| + | volume = {6544}, | ||
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.} | 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> | ||
Revision as of 10:14, 22 April 2011
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 3: Keccak_FinalRnd.zip
- Round 2: Keccak_Round2.zip
- Round 1: Keccak.zip
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - The Keccak SHA-3 submission
- ,2011
- http://keccak.noekeon.org/Keccak-submission-3.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : The Keccak SHA-3 submission
In : -
Address :
Date : 2011
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - The Keccak reference
- ,2011
- http://keccak.noekeon.org/Keccak-reference-3.0.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : The Keccak reference
In : -
Address :
Date : 2011
G. Bertoni, J. Daemen, M. Peeters, G. Van Assche - Cryptographic sponge functions
- ,2011
- http://sponge.noekeon.org/CSF-0.1.pdf
BibtexAuthor : G. Bertoni, J. Daemen, M. Peeters, G. Van Assche
Title : Cryptographic sponge functions
In : -
Address :
Date : 2011
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 |
| 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 | 21579 | Duan,Lai | |
| 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).
Ming Duan, Xuajia Lai - Improved zero-sum distinguisher for full round Keccak-f permutation
- ,2011
- http://eprint.iacr.org/2011/023.pdf
BibtexAuthor : Ming Duan, Xuajia Lai
Title : Improved zero-sum distinguisher for full round Keccak-f permutation
In : -
Address :
Date : 2011
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
BibtexAuthor : 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
BibtexAuthor : 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 6544:1-17,2010
- http://www-rocq.inria.fr/secret/Christina.Boura/data/sac.pdf
BibtexAuthor : 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
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
