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 third-party cryptanalysis results on Keccak. It discusses the publications listed on the Keccak page of the SHA-3 Zoo, maintained in the context of the ECRYPT II Network of excellence, as well as preliminary results not published there (yet).

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

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.

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.

C. Boura and A. Canteaut, A zero-sum property for the Keccak-f permutation with 18 rounds, comment on the NIST Hash Competition, 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.

We discuss the zero-sum distinguishers in the following note.

Note on zero-sum distinguishers of Keccak-f, comment on the NIST Hash Competition, 2010

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.

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.

C. Boura, A. Canteaut and C. De Cannière, Beware of optimistic weather forecast, Presented at the rump session of Crypto 2010

In the presentation Christophe De Cannière presented 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. The authors told us that the size of the zero-sums would be 21590. We decided not the increase the number of rounds in Keccak-f for the following two reasons. First, the minimum workload to observe the distinguisher is about 21590 calls to Keccak-f. This is way above the claimed distinguishing workload for Keccak for even the highest possible capacity value c = 1592, namely 2796. Second, the distinguisher is of a very weak kind and there appears to be no way it can be used in a distinguishing (or any other type of) attack against Keccak.

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

This paper describes the theory behind and the details of the zero-sum distinguishers announced at the rump session of Crypto 2010.

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.

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.

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

I. Dinur, O. Dunkelman and A. Shamir, New attacks on Keccak-224 and Keccak-256, Fast Software Encryption 2012

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.

P. Morawiecki, J. Pieprzyk and M. Srebrny, Rotational cryptanalysis of round-reduced Keccak, Cryptology ePrint Archive Report 2012/546, 2012

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

Finally, the Crunchy Crypto Collision and Pre-image Contest also contains third-party cryptanalysis results.