The Keccak sponge function family

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

1STMicroelectronics

2NXP Semiconductors

2014-05-14
The Keccak crunchy crypto contest re-opens

2014-05-06
Practical complexity cube attacks

2014-04-08
The FIPS 202 draft is available

2014-02-08
KeccakTools moved to GitHub

2013-10-04
Yes, this is Keccak!

2013-10-02
A concrete proposal

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 been selected by NIST to become the new SHA-3 standard. The draft of the standard (FIPS 202) is available for reading.

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

14 May 2014 — The Keccak crunchy crypto contest re-opens

We are happy to announce that from today the Keccak Crunchy Crypto Collision and Pre-image Contest re-opens without limit of time.

There are two minor changes.

We refer to Keccak Crunchy Crypto Collision and Pre-image Contest for more details.

6 May 2014 — Practical complexity cube attacks

Recently, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus published new attacks on keyed instances of Keccak, i.e., when it is used as a stream cipher or to compute a message authentication code (MAC). The attacks are cube attacks that exploit the low algebraic degree of a primitive and have a data complexity of the order of 2n if this degree is n. Since the round function has algebraic degree 2, the attacks can be applied on 5 or 6 rounds of Keccak-f with a practical complexity.

These attacks are the first ones with practical complexity to reach 6 rounds. Looking at more theoretical complexities, these attacks can most probably reach a few more rounds.

8 April 2014 — The FIPS 202 draft is available

Last Friday, NIST released the draft of the FIPS 202 standard. It proposes six instances: the four SHA-2 drop-in replacements with fixed output length SHA3-224 to SHA3-512, and the two future-oriented extendable-output functions SHAKE128 and SHAKE256.

The latest version of the Keccak Code Package is in line with the draft and contains test vectors for the six aforementioned instances.

8 February 2014 — KeccakTools moved to GitHub

Recently, we decided to move KeccakTools to GitHub. This allows easier updates as well as an easier integration of potential contributions from others.

As a reminder, KeccakTools is a set of documented C++ classes that can help analyze Keccak. It also contains the best differential and linear trails we found in the various Keccak-f instances.

4 October 2013 — Yes, this is Keccak!

SUMMARY: NIST's current proposal for SHA-3 is a subset of the Keccak family, and one can generate test vectors for that proposal using our reference code submitted to the contest.

In the end, it will be NIST's decision on what exactly will be standardized for SHA-3, but we would like, as the Keccak team, to take the opportunity to remind some facts about Keccak and give some opinion on the future SHA-3 standard.

First some reminders on Keccak

Keccak in the SHA-3 standard

NIST's current proposal for SHA-3, namely the one presented by John Kelsey at CHES 2013 in August, is a subset of the Keccak family. More concretely, one can generate the test vectors for that proposal using the Keccak reference code (version 3.0 and later, January 2011). This alone shows that the proposal cannot contain internal changes to the algorithm.

We did not suggest NIST to make any change to the Keccak components, namely the Keccak-f permutations, the sponge construction and the multi-rate padding, and we are not aware of any plans that NIST would do so. However, the future standard will not include the entire Keccak family but will select only specific instances of Keccak (i.e., with specific capacities), similarly to the block and key lengths of AES being a subset of those of Rijndael. Moreover, it will append some parameter-dependent suffix to the input prior to processing (see below) and fix the output length (for the SHA-2 drop-in replacements) or keep it variable (for the SHAKEs).

Here are further comments on these choices.

First, about suffixes (sometimes referred to as padding).

In Sakura, we propose to append some suffix to the input message, before applying Keccak. This is sometimes presented as a change in Keccak's padding rule because adding such a suffix can be implemented together with the padding, but technically this is still on top of the original multi-rate padding.

The suffixes serve two purposes. The first is domain separation between the different SHA-3 instances, to make them behave as independent functions (even if they share the same capacity). The second is to accomodate tree hashing in the future in such a way that domain separation is preserved.

The security is not reduced by adding these suffixes, as this is only restricting the input space compared to the original Keccak. If there is no security problem on Keccak(M), there is no security problem on Keccak(M|suffix), as the latter is included in the former.

Second, about the output length.

Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing, keystream generation and any protocol making use of a mask generating function. In its current proposal, NIST plans on standardizing two instances: SHAKE256 and SHAKE512, with capacity c=256 and c=512 and therefore security strength levels of 128 and 256 bits, respectively.

The traditional fixed output-length instances acting as SHA-2 drop-in replacement (SHA3-xxx) are obtained from truncating Keccak instances at the given output length.

Third, about the proposed instances and their capacities.

The capacity of the SHAKEs is given above and we now focus on the SHA-2 drop-in replacement instances with fixed output length n, with n in {224, 256, 384, 512}.

The SHA-3 requirements asked for a spectrum of resistance levels depending on the attack: n/2 for collision, n for first pre-image and n-k for second pre-image (with 2k the length of the first message). To meet the requirements and avoid being disqualified, we set c=2n so as to match the n-bit pre-image resistance level, and the requirements on other attacks followed automatically as they were lower. However, setting c=2n is also a waste of resources. For instance, Keccak[c=2n] before truncation provides n-bit collision resistance (in fact n-bit resistance against everything), but after truncation to n bits of output it drops to n/2-bit collision resistance.

Instead, adjusting the capacity to meet the security strength levels of [NIST SP 800-57] gives better security-performance trade-offs. In this approach, one aims at building a protocol or a system with one consistent security target, i.e., where components are chosen with matching security strength levels. The security strength level is defined by the resistance to the strongest possible attack, i.e., (internal) collisions so that, e.g., SHA-256 is at 128 bits for digital signatures and hash-only applications. Hence, setting c=n simply puts SHA3-n at the n/2-bit security level.

Among the Keccak family, NIST decided to propose instances with capacities of c=256 for n=224 or 256, and c=512 bits for n=384 or 512. This proposal is the result of discussions between the NIST hash team and us, when we visited them in February and afterwards via mail. It was then publically presented by John Kelsey at CT-RSA later in February and posted on the NIST hash-forum mailing list soon after. It was then presented at several occasions, including Eurocrypt 2013, CHES 2013 at UCSB, etc.

The corresponding two security strength levels are 128 bits, which is rock-solid, and an extremely high 256 bits (e.g., corresponding to RSA keys of 15360 bits [NIST SP 800-57]).

Comments on some of the criticism

Finally, we now comment on some criticism we saw in the discussions on the NIST hash-forum mailing list.

As explained in our new proposal, we think the SHA-3 standard should emphasize the SHAKE functions. The SHA-3 user would keep the choice between lean SHAKE256 with its rock-solid security strength level and the heavier SHAKE512 with its extremely high security strength level. In implementations, the bulk of the code or circuit is dedicated to the Keccak-f[1600] permutation and from our experience supporting multiple rates can be done at very small cost.

References

Recommended reading from third parties:

Other references:

2 October 2013 — A concrete proposal

This article is a copy of a message we posted on the NIST hash-forum mailing list on September 30, 2013.

SUMMARY: In the SHA-3 standard, we propose to set the capacity of all four SHA-2 drop-in replacements to 512 bits, and to make SHAKE256 and SHAKE512 the primary choice.

Technically, we think that NIST's current proposal is fine. As said in our previous post, we have proposed to reduce the capacities of the SHA-3 hash functions at numerous occasions, including during our last visit to NIST in February. Nevertheless, in the light of the current discussions and to improve public acceptance, we think it would be indeed better to change plans. For us, the best option would be the following (taking inspiration from different other proposals).

For the SHAKEs, we think it would be good to include in the standard a short procedure for replacing a hash function or MGF based on SHA-1 or SHA-2. For instance, if there is only one to be replaced, here is a sketch.

  1. Choose between SHAKE256 and SHAKE512. If the user can determine the required security level and it is 128 bits or smaller, choose SHAKE256. Otherwise (or if unsure), choose SHAKE512.
  2. Let the output length be determined by the application.

We have seen proposals for keeping instances with c=1024 in SHA-3. We think that claiming or relying on security strength levels above 256 bits is meaningless and that c=1024 would induce a significant performance loss, which should be avoided.

This proposal means that SHA-3 standard will offer drop-in primitives with the same security level as SHA-2 (modulo the comment on c=1024), but also gives protocol and product designers the possibility to use SHAKE256, which is more efficient and is in practice not less secure than SHAKE512 or the drop-ins.

all news items…

Contact Information

Email: keccak-at-noekeon-dot-org