The Keccak sponge function family

Guido Bertoni1, Joan Daemen1,2, Michaël Peeters1 and Gilles Van Assche1

1STMicroelectronics
2Radboud University

Pages

Documents

Notes

Software and other files

Figures

The figures above are available under the Creative Commons Attribution license. In short, they can be freely used, provided that attribution is properly done in the figure caption, either by linking to this webpage or by citing the article where the particular figure first appeared.

Links

Third-party cryptanalysis

This page lists all the third-party cryptanalysis results that we know of on Keccak, including FIPS 202 and SP 800-185 instances, KangarooTwelve and the authenticated encryption schemes Ketje and Keyak. We may have forgotten some results, so if you think your result is relevant and should be on this page, please do not hesitate to contact us.

The results are divided into the following categories:

In each category, the most recent results come first.

Analysis of unkeyed modes

First, the Crunchy Crypto Collision and Pre-image Contest contains third-party cryptanalysis results with practical complexities.


K. Qiao, L. Song, M. Liu and J. Guo, New Collision Attacks on Round-Reduced Keccak, Eurocrypt 2017

In this paper, Kexin Qiao, Ling Song, Meicheng Liu and Jian Guo develop a hybrid method combining algebraic and differential techniques to mount collision attacks on Keccak. They can find collisions on various instances of Keccak with the permutation Keccak-f[1600] or Keccak-f[800] reduced to 5 rounds. This includes the 5-round collision challenges in the Crunchy Contest. In the meanwhile, they refined their attack and produced a 6-round collision that took 250 evaluations of reduced-round Keccak-f[1600].


D. Saha, S. Kuila and D. R. Chowdhury, SymSum: Symmetric-Sum Distinguishers Against Round Reduced SHA3, Fast Software Encryption 2017

In this paper, Dhiman Saha, Sukhendu Kuila and Dipanwita Roy Chowdhury combine the analysis of symmetries and of the algebraic degree of the Keccak-f permutation to propose a distinguisher on the Keccak sponge function. It can reach up to 9 rounds with a complexity of 2511.


M. Amy, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent and J. Schanck, Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3, SAC 2016

In this paper, Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent and John Schanck investigate the cost of Grover's quantum search algorithm when used to find preimage attacks on SHA3-256 (i.e., Keccak[r=1088, c=512] with 256 bits of output), as well as on SHA-2. They compare the cost of a classical generic attack (2256 operations) with that on a quantum computer with a carefully motivated cost metric (2166 logical-qubit-cycles).


J. Guo, M. Liu and L. Song, Linear Structures: Applications to Cryptanalysis of Round-Reduced Keccak, Asiacrypt 2016

In this paper, Jian Guo, Meicheng Liu and Ling Song develop the technique of linear structures and show how to linearize 3 rounds of Keccak-f. They then apply it in preimage attacks on up to 4 rounds. For instance, a preimage on SHAKE128 reduced to 4 rounds with 128 bits of output can be found in complexity 2106. The same technique has been used to solve the 3-round pre-image challenge in the Crunchy Contest. They also used the linear structures to improve the complexity of zero-sum distinguishers on Keccak-f[1600].


P. Morawiecki, Malicious Keccak, Cryptology ePrint Archive Report 2015/1085, 2015

In this article, Paweł Morawiecki investigates a variant of Keccak with different round constants. This is an interesting experiment providing third-party motivation for the choice of the Keccak-f round constants.


S. Das and W. Meier, Differential Biases in Reduced-Round Keccak, Africacrypt 2014

In this paper, Sourav Das and Willi Meier investigate the bias of difference bits after the propagation of low-weight differential trails after two rounds of Keccak-f. They apply this technique to find distinguishers on Keccak when the permutation is reduced to 6 rounds, with a complexity of 252.


P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Preimage attacks on the round-reduced Keccak with the aid of differential cryptanalysis, Cryptology ePrint Archive Report 2013/561, 2013

In this paper, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present a preimage attack on Keccak[r=576, c=1024] reduced to 3 rounds and 512 bits of output with complexity 2503. They also present a partial preimage attack, where 256 bits of a 640-bit input message are unknown. This attack works on 4 rounds with a complexity of 2251.


S. Kölbl, F. Mendel, T. Nad and M. Schläffer, Differential Cryptanalysis of Keccak Variants, IMA Int. Conf. 2013

In this paper, Stefan Kölbl, Florian Mendel, Tomislav Nad and Martin Schläffer analyze the differential properties of Keccak-f[800] and Keccak-f[1600]. They present collision attacks with practical complexity on Keccak when the permutation is reduced to 4 rounds. The instances covered include c≤352 when using Keccak-f[800] and c≤640 when using Keccak-f[1600].


I. Dinur, O. Dunkelman and A. Shamir, Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials, Fast Software Encryption 2013

In this paper, Itai Dinur, Orr Dunkelman and Adi Shamir present collision attacks on Keccak with practical complexity up to 3 rounds of Keccak-f[1600] and with complexity 2115 for 5 rounds.


P. Morawiecki, J. Pieprzyk and M. Srebrny, Rotational cryptanalysis of round-reduced Keccak, Fast Software Encryption 2013

In this paper, Paweł Morawiecki, Josef Pierpzyk and Marian Srebrny apply rotational cryptanalysis to Keccak. They use it to construct a 5-round distinguisher for Keccak-f[1600] and to do preimage generation for 4 rounds of Keccak[r=1024,c=576] truncated to 512 bits with complexity 2506 calls to Keccak-f[1600].


I. Dinur, O. Dunkelman and A. Shamir, New attacks on Keccak-224 and Keccak-256, Fast Software Encryption 2012 and Journal of Cryptology 27(2) (pp. 183-209), 2014

The authors of this paper present practical-time collisions on Keccak[r=1088,c=512] (and lower capacity) with 4 rounds. They combine a low-weight trail over 3 rounds with algebraic techniques. They also find near-collisions when the number of rounds is reduced to 5.


M. Naya-Plasencia, A. Röck and W. Meier, Practical Analysis of Reduced-Round Keccak, Indocrypt 2011

In this paper, the authors propose several practical-time attacks on the Keccak hash function with 2 to 4 rounds. First, they give a differential distinguisher exploiting a low-weight differential trail. Its complexity is 225 for 4 rounds. Then, they show how to produce a collision (resp. near-collision) on 2 (resp. 3) rounds of Keccak[r=1088,c=512] (and lower capacity) with complexity 233 (resp. 225). Finally, they present an algorithm to find (second) preimages in time 231 and memory 229.


D. J. Bernstein, Second preimages for 6 (7? (8??)) rounds of Keccak?, NIST hash forum mailing list, November 27, 2010

The attack exploits the low degree of Keccak-f's round function and turns it into a (second) preimage attack at the sponge function level. The downside of the attack is that this workload reduction comes at the cost of memory. For 6 rounds, 2176 bits of memory give a workload reduction by a factor 50 (~6 bits); for 7 rounds, 2320 bits of memory give a workload reduction by a factor 37 (~5 bits); and for 8 rounds, 2508 bits of memory give a workload reduction by a factor 1.4 (half a bit). The author was awarded the fourth prize for the best cryptanalysis.


P. Morawiecki and M. Srebrny, A SAT-based preimage analysis of reduced Keccak hash functions, Cryptology ePrint Archive Report 2010/285, 2010

In this paper, Paweł Morawiecki and Marian Srebrny report on experiments for generating preimages using SAT solvers. They attack Keccak versions calling Keccak-f with width 50, 200 and 1600 and with a reduced number of rounds. They compare the SAT solver approach with plain exhaustive search and it turns out to be faster for up to 3 rounds.


Analysis of keyed modes

X. Dong, Z. Li, X. Wang and L. Qin, Cube-like Attack on Round-Reduced Initialization of Ketje Sr, Fast Software Encryption 2017

In this paper, Xiaoyang Dong, Zheng Li, Xiaoyun Wang and Ling Qin mount cube attacks on the Ketje family of authenticated encryption schemes, with a focus on the primary recommendation Ketje Sr. They can successfully recover the key when the number of rounds of the initialization step is reduced from 12 down to 6, with various complexities (e.g., from 296 for Ketje Minor or Major to 2113 for Ketje Sr).


S. Huang, X. Wang, G. Xu, M. Wang and J. Zhao, Conditional Cube Attack on Reduced-Round Keccak Sponge Function, Eurocrypt 2017

In this paper, Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang and Jingyuan Zhao generalize cube attacks into conditional cube testers. They present different attacks in different settings. With a MAC mode on top of Keccak with a reduced-round Keccak-f[1600], they can recover the secret key up to 7 rounds with a time and data complexity of 272. On Lake Keyak, their attack extends to 8 rounds with a time and data complexity of 274. Finally, they also propose (unkeyed) distinguishers on Keccak reduced to 7 rounds.


I. Dinur, P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Cube Attacks and Cube-attack-like Cryptanalysis on the Round-reduced Keccak Sponge Function, Eurocrypt 2015

In their paper, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present attacks that combine cube attacks and structural properties of Keccak. They target different keyed modes of Keccak as well as Keyak v1. They achieve forgery attacks up to 7 rounds (complexity: 265), key recovery attacks up to 7 rounds (complexity: 276) and keystream predictions up to 9 rounds (complexity: 2256).

These are the attacks that reach the largest number of rounds of Keccak and Keyak v1.


I. Dinur, P. Morawiecki, J. Pieprzyk, M. Srebrny and M. Straus, Practical Complexity Cube Attacks on Round-Reduced Keccak Sponge Function, Cryptology ePrint Archive Report 2014/259, 2014

In their paper, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus present some cube attacks on stream cipher and MAC modes of Keccak. The attacks allow to recover the key with a small complexity of 236 when the permutation is reduced to 6 rounds or less.


J. Lathrop, Cube Attacks on Cryptographic Hash Functions, Master's thesis, Rochester Institute of Technology, 2009

In his thesis, Joel Lathrop shows that cube attacks can not only be applied to keyed cryptosystems but also to hash functions by way of a partial preimage attack. Cube attacks are applied to reduced-round variants of ESSENCE and Keccak.


Analysis of the Keccak-f permutations

J. Jean and I. Nikolic, Internal Differential Boomerangs: Practical Analysis of the Round-Reduced Keccak-f Permutation, Fast Software Encryption 2015

In this paper, Jérémy Jean and Ivica Nikolić introduce the technique of internal differential boomerang distinguishers. They analyze the symmetry inside the permutation and propose distinguishers up to 8 rounds of Keccak-f[1600] with practical complexities.


S. Kuila, D. Saha, M. Pal, D. R. Chowdhury, Practical Distinguishers against 6-Round Keccak-f Exploiting Self-Symmetry, Africacrypt 2014

In this paper, Sukhendu Kuila, Dhiman Saha, Madhumangal Pal and Dipanwita Roy Chowdhury consider distinguishers on Keccak-f[1600] where the state is self-symmetric, i.e., it has a period less than 64 along the z-axis. They show distinguishers up to 6 rounds with a complexity of 211.


A. Duc, J. Guo, T. Peyrin and L. Wei, Unaligned Rebound Attack: Application to Keccak, Fast Software Encryption 2012

This paper analyzes two aspects of differential cryptanalysis on Keccak: efficient trails and rebound attacks. In the former, the authors propose a heuristic to build differential trails with a low restriction weight. For Keccak-f[1600], they obtained trails of weight 32, 142 and 709 for 3, 4 and 5 rounds, respectively. In the latter, the paper presents distinguishers making use of the rebound attack for up to 8 rounds of Keccak-f[1600] with a complexity of 2491.


M. Duan and X. Lai, Improved zero-sum distinguisher for full round Keccak-f permutation, Cryptology ePrint Archive Report 2011/023, 2011

The authors of this paper noted a property of the inverse of the non-linear function χ: while χ-1 has algebraic degree 3, the product of any two output bits also has degree 3. This allows to estimate the degree of the Keccak-f rounds more tightly and to extend the zero-sum distinguisher on Keccak-f[1600] to size 21575 for 24 rounds.


C. Boura, A. Canteaut and C. De Cannière, Higher-order differential properties of Keccak and Luffa [slides], Fast Software Encryption 2011

In this work, the authors present a new upper bounds for the algebraic degree of iterated permutations. While for a small number of rounds the algebraic degree increases exponentially with the number of rounds, for a large number of rounds the algebraic degree only converges exponentially to the maximum value (permutation width minus 1). This improves upon existing zero-sum distinguishers for several SHA-3 candidates. For Keccak-f, it allows extending the zero-sum distinguishers to the full 24-round version, although the size of the zero-sums is 21590 and the distinguisher does not extend to any other type of attack against Keccak.


C. Boura and A. Canteaut, Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256, Proceedings of SAC 2010, LNCS, Springer-Verlag, 2010

In this paper, Christina Boura and Anne Canteaut extend their zero-sum distinguishers to 20 rounds.


C. Boura and A. Canteaut, A zero-sum property for the Keccak-f permutation with 18 rounds, ISIT 2010

In this paper, Christina Boura and Anne Canteaut extend the zero-sum distinguisher of Aumasson and Meier to 18 rounds by analyzing the Walsh spectrum of the non-linear part and bounding the degree of the rounds more tightly.

The authors won the third prize for the best cryptanalysis.


J.-P. Aumasson and W. Meier, Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi, note presented at the CHES 2009 rump session, 2009

In this note, Jean-Philippe Aumasson and Willi Meier investigate a new kind of distinguishers called zero-sum distinguishers. In particular, they compute high-order derivatives of the rounds and the inverse rounds of Keccak-f. Starting from the middle, they obtain a set of values whose sum is zero and whose sum of images through reduced-round Keccak-f is also zero. This distinguisher is successful up to 16 rounds. The authors did not find a way to use this distinguisher against the Keccak sponge function, though.

The authors won the second prize for the best cryptanalysis.


J.-P. Aumasson and D. Khovratovich, First Analysis of Keccak, comment on the NIST Hash Competition, 2009

In this paper, Jean-Philippe Aumasson and Dmitry Khovratovich look at two possible distinguishers on reduced-round Keccak-f[1600]. First, cube testers are applied to detect non-ideal behavior in the algebraic description of the permutation. Second, the authors try to solve the constrained-input constrained-output (CICO) problem using automated algebraic techniques.

The authors received 25 bottles of Belgian trappist beer as the paper was awarded the first prize for the best cryptanalysis. It was presented by Dmitry Khovratovich at the rump session of Eurocrypt 2009 (Beer-recovery analysis).