The Keccak sponge function family

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

1STMicroelectronics
2Radboud University

2017-03-15
New bounds on differential trails in Keccak-f

2017-03-06
Announcing the Ketje cryptanalysis prize

2017-03-01
First 6-round collision challenge solved

2016-12-23
NIST SP 800-185 officially released

2016-12-22
First 4-round pre-image challenge solved

2016-09-21
Ketje and Keyak for CAESAR round 3

all news items…

News feed icon News feed (atom)

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

This page is dedicated to the cryptographic sponge function family called Keccak, which has become the FIPS 202 (SHA-3) standard.

Keccak in a nutshell

Keccak is a family of sponge functions. The sponge function is a generalization of the concept of cryptographic hash function with infinite output and can perform quasi all symmetric cryptographic functions, from hashing to pseudo-random number generation to authenticated encryption.

For a quick introduction, we propose a pseudo-code description of Keccak. The reference specification, analysis, reference and optimized code and test vectors for Keccak can be found in the file section.

As primitive used in the sponge construction, the Keccak instances call one of seven permutations named Keccak-f[b], with b=25, 50, 100, 200, 400, 800 or 1600. In the scope of the SHA-3 contest, we proposed the largest permutation, namely Keccak-f[1600], but smaller (or more “lightweight”) permutations can be used in constrained environments. Each permutation consists of the iteration of a simple round function, similar to a block cipher without a key schedule. The choice of operations is limited to bitwise XOR, AND and NOT and rotations. There is no need for table-lookups, arithmetic operations, or data-dependent rotations.

Keccak has a very different design philosophy from its predecessor RadioGatún. This is detailed in our paper presented at Dagstuhl in 2009.

Strengths of Keccak

Flexibility

Keccak inherits the flexibility of the sponge and duplex constructions.

Design and security

Implementation

Latest news

15 March 2017 — New bounds on differential trails in Keccak-f

In a joint work with Silvia Mella (STMicroelectronics and University of Milano), we propose a framework for bounding the weight of differential trails. We apply this on Keccak-f with widths of 200, 400, 800 and 1600 bits to show that no trail of weight less than 92 over 6 rounds exist in either of these Keccak-f instances. Should a 6-round differential trail be used as part of a collision attack, the ratio of complying pairs is thus guaranteed to be at most 2-92.

This work improves over our results of FSE 2012, both extending the coverage of differential trails both over the different Keccak-f widths and over a higher weight per round. In particular, Silvia was able to scan all 3-round trails up to weight 45. At 15 per round, and given the exponential growth of trail number per weight, this is a significant improvement over previous works.

Silvia presented her work at FSE 2017. The paper can be found here.

6 March 2017 — Announcing the Ketje cryptanalysis prize

We are happy to announce a new cryptanalysis prize! The subject of the stress-test is the authenticated encryption scheme Ketje.

We are particularly interested in attacks aiming at recovering the internal state, the secret key or at forging a MAC. Other attacks would be appreciated as well. Competitors have the freedom to increase the input rate of Ketje. The attack can be applied to any of the four instances of Ketje.

Who wins the prize will be decided by consensus in the Keccak team. Some hints:

The Ketje authenticated encryption scheme has already established such a solid reputation in Belgium that a beer was named after it. Unfortunately, it is already sold out since 2011. Instead, the winner will receive a selection of Belgian beers.

The attacks should be submitted to the crypto-competitions -at- googlegroups.com mailing list (with ketje -at- noekeon.org in CC) before January 31st, 2018.

1 March 2017 — First 6-round collision challenge solved

We congratulate Ling Song1,2,3, Guohong Liao4,1 and Jian Guo1 for solving the 6-round collision challenge on Keccak[r=1440, c=160].

The collision search took a computational effort of about 250 evaluations of the Keccak-f rounds. It follows an improvement of the technique previously used for solving the 5-round collision challenge in May last year (then solved by Jian Guo, Meicheng Liu, Ling Song and Kexin Qiao).

  1. Cryptanalysis Taskforce, Temasek Laboratories @ Nanyang Technological University, Singapore
  2. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China
  3. Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, China
  4. South China Normal University, China

23 December 2016 — NIST SP 800-185 officially released

NIST released the SP 800-185 standard with useful new functions based on Keccak: cSHAKE, KMAC, TupleHash and ParallelHash.

Yesterday, NIST published the SP 800-185 standard [PDF]. It contains the following new functions based on Keccak:

These new functions all support the 128-bit and 256-bit security strengths. They all consistently support domain separation through the user-chosen customization string input. And they all support variable ouput length in a natural way.

22 December 2016 — First 4-round pre-image challenge solved

We congratulate Meicheng Liu1 and Jian Guo2 for being the first ones to solve a 4-round pre-image challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!

They found a pre-image of a given 80-bit digest for Keccak[r=1440, c=160] reduced to its first 4 rounds. Up to now, only pre-image challenges up to 3 rounds had been solved.

  1. State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China
  2. Nanyang Technological University, Singapore

21 September 2016 — Ketje and Keyak for CAESAR round 3

Ketje and Keyak are authenticated encryption schemes based on Keccak-p. Both were accepted in round 3 of the CAESAR competition. We slightly modified Ketje (now v2) in a way that encourages cryptanalysis, while we kept Keyak unchanged (still v2) but updated and improved its documentation.

Ketje v2

Compared to Ketje v1, we now specify a different placement for the outer (input/output) part of the state. This is done by adding a change of coordinates (“twist”), so as to put the outer part on a diagonal and to limit its interaction with the preceding χ and following θ step mappings.

The motivation is to encourage cryptanalysis. Cryptanalysis usually starts by reducing the number of rounds to see at which point a given primitive becomes insecure. In the case of Ketje, one cannot decrease the step calls further than 1 round. Instead, a cryptanalyst can increase the rate to more than 2 lanes to determine at which point Ketje breaks. However, the lanes of the outer part are located in the same plane (i.e., same y coordinate) and contain the result of χ. The knowledge of too many lanes in the same plane could mean that χ is easily inverted on that part of the state. Also, we should not place the outer part on a sheet (i.e., same x coordinate) as this would help the adversary influence the parity computed in θ. Instead, the twist places the outer part on a diagonal.

We illustrate the usage of this twist with two new instances, Ketje Minor and Ketje Major, that have a rate of 4 lanes (instead of 2) and larger permutations (800 and 1600 bits).

The primary recommendation remains Ketje Sr. Both Ketje Jr and Ketje Sr keep their rate of 2 lanes and otherwise remain unchanged modulo the twist.

Keyak v2

Compared to round 2, River, Lake, Sea, Ocean and Lunar Keyak remain unchanged.

We nevertheless worked on improving the description of the Motorist mode of operation by simplifying the definition of the Piston, Engine and Motorist algorithms. We also updated the security rationale. These changes are available in version 2.2 of the documentation (see change log in Appendix A).

The definition of Motorist now restricts the tag length to the capacity. As pointed out by Seth Hoffert, a legitimate adversary could, in a session, submit a tag as next block of metadata. If the tag is as long as the rate, this allows the adversary to force the outer part to a constant value, hence increasing the multiplicity. This would not break Motorist but it would prevent it to reach near-capacity generic security.

all news items…

Contact Information

Email: keccak-at-noekeon-dot-org