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

News items

News feed (atom)

Is SHA-3 slow?

12 June 2017

In a recent post, Adam Langley complains that “SHA-3 is slow”. Similar comments appear from time to time on the web (see also David Wong's post). But what does it mean precisely? Let us dig into it.

Hardware and software

There are a couple of ambiguities in this statement. Let's start with the first one: where would it be “slow”?

Keccak, the winner of the SHA-3 competition, is blazing fast when implemented on dedicated (ASIC) or programmable (FPGA) hardware. Its throughput for a given circuit area is an order of magnitude higher than SHA-2 or any of the SHA-3 finalists. And if you care beyond plain speed, note that it also consumes much less energy per bit. In this sense, Keccak is a green cryptographic primitive.

Keccak has other implementation advantages, like efficient protections against side-channel attacks, but let's go to the point: what seems to be at stake is the speed in software.

Did you say “SHA-3”?

How come then, that SHA3-512 is slower than SHA-512 on modern processors? This brings up to the second ambiguity of the statement: what is “SHA-3”?

“SHA-3” initially refers to the target of the competition that NIST organized from 2008 to 2012, namely a new hash standard that would complement SHA-2 in case it is broken. Hence, the initially-intended outcome of the competition is a set of four functions called SHA3-224, SHA3-256, SHA3-384, and SHA3-512.

If “SHA-3” means these four functions, then indeed SHA3-512 is unnecessarily slowed down by an excessive security parameter. Due to an absurd rule in the competition, followed by a fierce controversy in 2013, the parameters of SHA3-512 are stuck at offering 512 bits of pre-image security, a nonsense for anyone who can compute powers of two.

It turned out that Keccak has more to offer than just the drop-in replacements for SHA-{224, 256, 384, 512}. In FIPS 202 (“the SHA-3 standard”), NIST also approves two extendable-output functions (XOFs) called SHAKE128 and SHAKE256. These generalize the traditional hashing paradigm by allowing any arbitrary output length and by being parameterized by their security strength, instead of their output length.

If the term “SHA-3” embraces the aforementioned XOFs, then SHAKE{128, 256} are on par with SHA-2 on common processors. But could “SHA-3” actually be super fast in software?

Parallelism

To answer this last question, let us go further down the standardization road. Recently, NIST released the SP 800-185 standard (“SHA-3 derived functions”), which proposes a framework for customizable functions, called cSHAKE, that generalize SHAKE{128, 256}. And, as an application of this framework, it approves the ParallelHash functions. These functions internally use a parallel mode of operation, which an implementation can exploit to speed-up the processing.

With these standard functions included, “SHA-3” can actually outperform SHA-2 and even SHA-1 (broken but usually considered fast) for long messages on modern processors.

Security and performance hand-in-hand

Of course, a cryptographic functions should carefully balance speed and security. Keccak makes use of sound design properties, like fast linear and differential propagation or purposely weak alignment, and it clearly stays away from the ARX (modular additions, rotations and exclusive or's) approach. What we understand of Keccak now made us wonder: aren't 24 rounds too much?

KangarooTwelve is a recently proposed variant of Keccak, in which the number of rounds has been reduced to 12—yet, with exactly the same round function, no tweak! It may seem like a drastic reduction, but it is in line with our proposed solution for authenticated encryption, Keyak, submitted to the CAESAR competition. And, more importantly, this wouldn't have been possible if Keccak hadn't had the chance of getting such a rather extensive scrutiny from cryptanalysis experts throughput the years—and to resist to them.

KangarooTwelve is defined on the “SHA-3” components from FIPS 202 and may please the aficionados of extreme software speed. But beware: with such speeds, the hard drive or the network connection has long become the bottleneck for most applications.

Speed measurements of various hash functions on Skylake

Gilles, Guido, Joan, Michaël and Ronny
Comments? Contact us via Twitter or send us an email!

New bounds on differential trails in Keccak-f

15 March 2017

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.

Announcing the Ketje cryptanalysis prize

6 March 2017

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.

First 6-round collision challenge solved

1 March 2017

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

NIST SP 800-185 officially released

23 December 2016

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.

First 4-round pre-image challenge solved

22 December 2016

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

Ketje and Keyak for CAESAR round 3

21 September 2016

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.

KangarooTwelve: fast hashing based on Keccak-p

11 August 2016

We propose a fast and secure arbitrary output-length hash function aiming at a higher speed than the FIPS 202's SHA-3 and SHAKE functions, while retaining their flexibility and basis of security. Furthermore, it can exploit a high degree of parallelism, whether using multiple cores or the single-instruction multiple-data (SIMD) instruction set of modern processors. On Intel's® Haswell and Skylake architectures, KangarooTwelve tops at less than 1.5 cycles/byte for long messages on a single core. Short messages also benefit from about a factor two speed-up compared to the fastest FIPS 202 instance SHAKE128.

Another 5-round collision found in our crypto challenge

15 July 2016

We congratulate Jian Guo1, Meicheng Liu1,2, Ling Song1,2,3 and Kexin Qiao2,3,1,4 for solving another 5-round collision challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!

They generated a collision for a Keccak variant with capacity 160 bits, calling the Keccak-f permutation with width 800 and 5 rounds.

This solution happens less than two months after their team published the solution for the 5-round collision challenge with width 1600. We are looking forward to seeing the details of this attack, how much it differs from their previous one and whether their method can be adapted for the two remaining collision challenges in the 5-round category.

  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. University of Chinese Academy of Sciences, China

New solutions to collision challenges

31 May 2016

We congratulate Jian Guo1, Meicheng Liu1,2, Ling Song1,2,3 and Kexin Qiao2,3,1,4 for being the first ones to solve a 5-round collision challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!

They generated a collision for a Keccak variant with capacity 160 bits, calling the Keccak-f permutation with width 1600 and 5 rounds.

Remarkably, this breakthrough came only one month after two members of the same team, Jian and Meicheng, generated the first 3-round pre-images in our contest. [More details…]

  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. University of Chinese Academy of Sciences, China

High-speed Keccak-FPH

12 May 2016

When implemented on ASICs or on FPGAs, Keccak is significantly more efficient than other primitives with a similar security level, and allows efficient protections against side-channel attacks. Another area where Keccak's performance shines is on processors that exploit parallelism.

Recently, the NIST posted on the hash forum two draft special publications SP 800-XXX including proposals for customized SHAKE instances (Cshake), pseudo-random functions (KMAC), hash functions taking multiple strings as input (TupleHash) and a parallelized hash mode (Fast Parallel Hash, or FPH).

We implemented FPH in the Keccak Code Package and measured the following speeds for long messages:

HaswellSkylake
Keccak-FPH1282.732.31
Keccak-FPH2563.412.88

Performance in cycles per byte (single core) on Intel® Core™ i5-4570 (Haswell) and i5-6500 (Skylake), both at 3.2GHz

Keccak-FPH beats the speed line drawn by the legacy algorithms MD5 and SHA-1, usually considered fast.

Our implementation exploits the AVX-2 256-bit SIMD instruction set.

New solutions to pre-image challenges

27 April 2016

We congratulate Jian Guo (Nanyang Technological University, Singapore) and Meicheng Liu (Nanyang Technological University, Singapore and State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China) for solving two 3-round pre-image challenges in the Keccak Crunchy Crypto Collision and Pre-image Contest!

Jian and Meicheng solved the 3-round pre-image challenges for widths 800 and 1600. There remains two others, i.e., those for widths 200 and 400, plus of course all the challenges with more rounds!!! [More details…]

Reorganized Keccak Code Package

16 March 2016

The Keccak Code Package (or KCP) contains different free and open-source implementations of Keccak and closely related variants such as Ketje and Keyak.

We reorganized it to make it easier to use and to develop in or on it. More specifically, the main changes are the following.

To sum up, the KCP contains:

Tweetable FIPS 202

19 August 2015

Very compact (or tweetable) implementations of Keccak, written by D. J. Bernstein, Peter Schwabe and Gilles, are now available. In their most compact form, the 6 instances of SHA-3 and SHAKE can fit in just 9 tweets.

Compact code implementing FIPS 202

We published a series of compact implementations, from the more readable one to the most compact one.

Dan presented the tweetable implementation at the rump session of Crypto 2015 [slides].

FIPS 202 is out: SHA-3 and Keccak beyond hashing

5 August 2015

NIST officially released the FIPS 202 standard. Although it represents the target of the SHA-3 competition for a fresh hash function, the new standard provides more than just a successor to SHA-2: It comes as a toolbox with all the necessary ingredients for defining other uses of Keccak. About 2.5 years after the SHA-3 competition concluded, we recap on what the FIPS 202 standard contains.

The purpose of the FIPS 202 standard is twofold: It gives all the definitions needed to specify Keccak-based functions and it approves the use of six specific instances. The document is written bottom-up, starting with the bit-level operations in the Keccak-p permutations, a generalization of the Keccak-f permutations with a parameterized number of rounds, then moving to the sponge construction and, building on it, the Keccak family of sponge functions, and finally specifying the approved instances:

Extendable ouput functions

The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash functions where the output length is not fixed but is potentially infinite. Concretely, XOFs can be used instead of complex constructions involving hash functions and counters such as MGF1. With RSA, this is of immediate benefit to full domain hashing, to RSA OAEP (Optimal Asymmetric Encryption Padding) and to RSA PSS (Probabilistic Signature Scheme). Other use cases are key derivation functions and stream ciphers.

Another important conceptual difference is that a XOF's security strength can be chosen (e.g., through Keccak's capacity value) and is not bound to its output length, as is traditionally the case for hash functions. This flexibility allows for better security-performance trade-offs. For instance, with a key derivation function, the length of the derived key material can greatly vary from one application to another, in a way that is in general not related to the required security strength.

Future plans

NIST expressed their intention to approve other modes of use of Keccak (or potentially other functions based on the Keccak-p permutations) as they are developed, by way of special publications in the NIST SP 800-XX series and referring to FIPS 202. At the SHA-3 2014 Workshop, NIST presented more details on the following topics:

Code package

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

The Keccak crunchy crypto contest re-opens

14 May 2014

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.

Practical complexity cube attacks

6 May 2014

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.

The FIPS 202 draft is available

8 April 2014

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.

KeccakTools moved to GitHub

8 February 2014

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.

Yes, this is Keccak!

4 October 2013

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:

A concrete proposal

2 October 2013

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.

On 128-bit security

2 October 2013

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

SUMMARY: Keccak instances with a capacity of 256 bits offer a generic security strength level of 128 bits against all generic attacks, including multi-target attacks. 2128 is an astronomical number and attacks with such complexities are expected to remain unreachable for decades to come.

Among other options, we have proposed instances with capacity c=256 as an option because they have a generic security strength of 128 bits. This means any single-stage (*) generic attack has an expected complexity of 2128 computations of Keccak-f, unless easier on a random oracle. This is such an astronomical amount of work that one may wonder why we would ever need more than 128 bits of security (see also Tune Keccak to your requirements).

In the discussions on SHA-3 we have seen some remarks on 128-bit security not being sufficient in the light of multi-target attacks. Multi-target attacks can be illustrated nicely with block ciphers.

If the application does not allow avoiding multi-targets, one can decide to use AES-192 or AES-256. The reason to use 192-bit or 256-bit keys is not because the security strength level 128 is too small, but because in the light of multi-target attacks, we need a block cipher with a key longer than 128 bits to offer a security strength level of 128 bits. Summarizing, AES-128, AES-192 and AES-256 have key lengths of 128, 192 and 256 bits, but this does not mean they offer a generic security strength of 128, 192 and 256 bits. This is not specific for AES, it is true for any block cipher. This is also not a problem. A protocol designer who understands these issues can easily build efficient protocols offering excellent generic security strengths.

Multi-target also applies to finding (first or second) pre-images. Finding one pre-image out of M 128-bit hashes only takes 2128/M hash computations.

So it is tempting to think that the 128-bit generic security strength of Keccak instances with 256-bit capacity will also degrade under multi-target attack. Fortunately, this is not the case, as the generic security strength level c/2 follows from the bound in our indifferentiability proof for the sponge construction. More specifically, the success probability of a generic attack on a sponge function is upper bounded by the sum of the attack probability of that attack on a random oracle plus the RO-differentiating advantage N2/2c+1. We have explained that in our Eurocrypt 2008 paper on Sponge indifferentiability and this was formalized by Elena Andreeva, Bart Mennink and Bart Preneel in Appendix B, Theorem 2 of their paper Security Reductions of the Second Round SHA-3 Candidates, and this is also true for multi-target attacks.

If one wants a hash function (any) that offers a generic security strength level of 128 bits against multi-target attacks with at most say 264 targets, then one must take the output length equal to 128+64=192 bits. For a sponge function, the capacity does not need to be increased to twice the output length; if we target a security strength level of 128 bits, c=256 is still sufficient.

So a 256-bit capacity offers a generic security strength level of 128 bits that is absolute and does not degenerate under multi-target attacks.

For the record, we as Keccak team proposed setting c=256 (and even a user-chosen capacity) as an option in our SHA-3 proposal: “If the user decides to lower the capacity to c=256, providing a claimed security level equivalent to that of AES-128, the performance will be 31% greater than for the default value c=576.” (See page 4 of The Keccak SHA-3 submission and page 3 of our Note on Keccak parameters and usage published in February 2010.) Furthermore, the option of c=256 was also presented at numerous occasions:

(*) See Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton, Advances in Cryptology - Eurocrypt 2011.

A software interface for Keccak

3 July 2013

We published a new note in which we propose an interface to Keccak at the level of the sponge and duplex constructions, and inside Keccak at the level of the Keccak-f permutation. The purpose is twofold.

As a concrete exercise, we adapted some implementations from the “Reference and optimized code in C” to the proposed interface and posted them in a new “Keccak Code Package”. For the optimized implementations, it appears that the impact on the throughput is negligible while it significantly improves development flexibility and simplicity.

Updated pages

3 June 2013

We added the slides of some recent presentations on this page.

Sakura: a flexible coding for tree hashing

3 June 2013

Recently, we released a paper on Sakura, a flexible, fairly general, coding for tree hash modes. The coding does not define a tree hash mode, but instead specifies a way to format the message blocks and chaining values into inputs to the underlying function for any topology, including sequential hashing. The main benefit is to avoid input clashes between different tree growing strategies, even before the hashing modes are defined, and to make the SHA-3 standard tree-hashing ready.

It expands on the concept of “universal” (now: flexible) hash tree coding that we presented at NIST on February 6 (see slides 55-59). The goal is to address tree hashing, as discussed by John Kelsey in his SHA3 presentation at the RSA conference last February.

All comments are welcome!

The Keccak crunchy crypto contest continues through end 2013

24 January 2013

In a previous announcement, we re-opened the Keccak Crunchy Crypto Collision and Pre-image contest until end 2012. As no new challenges were solved between March and December 2012, we decided to leave it open for another year, i.e., until end 2013.

The challenges remain the same. We suggest all interested people to subscribe to our mailing list, and solutions shall be sent to this mailing list, as detailed here, before December 31, 2013 at 23:59 GMT+1.

Updated home page

24 October 2012

We updated the home page of this site and added a picture of the Keccak Team.

NIST selects Keccak for SHA-3

3 October 2012

We are very proud to announce that NIST selected Keccak as the winner of the SHA-3 competition!

It was a pleasure to participate to the competition. Being confronted with ideas from a wide diversity of designs was especially exciting. Beyond the design itself, it was also very interesting to cover several domains, from cryptanalysis to software and hardware implementation aspects.

This success comes also with input from a large number of people and we would like to take this occasion to thank them. We start by thanking those who took the trouble to cryptanalyze Keccak and publish the results, in particular Jean-Philippe Aumasson, Dan Bernstein, Christina Boura, Anne Canteaut, Christophe De Cannière, Itai Dinur, Ming Duan, Alexandre Duc, Orr Dunkelman, Danilo Gligoroski, Jian Guo, Dmitry Khovratovich, Xuejia Lai, Joel Lathrop, Willi Meier, Paweł Morawiecki, María Naya-Plasencia, Rune Steinsmo Ødegård, Thomas Peyrin, Andrea Röck, Adi Shamir, Marian Srebrny and Lei Wei, as well as those who cryptanalyzed its predecessor RadioGatún and thereby gave us the motivation to improve it, namely, Charles Bouillaguet, Pierre-Alain Fouque, Thomas Fuhr, Dmitry Khovratovich and Thomas Peyrin. We thank Elena Andreeva, Bart Mennink, Bart Preneel and Marjan Škrobot for tackling the delicate task of bringing clarity in the soundness properties of the modes of use employed by the SHA-3 (semi-)finalists. In the implementation and benchmarking department, we would like to thank the very valuable software benchmarking initiatives eBASH, ran by Dan Bernstein and Tanja Lange for Ecrypt II, and XBX, ran by Christian Wenzel-Benner, Jens Gräf, John Pham and Jens-Peter Kaps; the several teams that performed hardware comparisons, in particular the teams led or represented by Abdulkadir Akın, Brian Baldwin, Kris Gaj, Frank Gurkaynak, Jens-Peter Kaps, Shin’ichiro Matsuo, Patrick Schaumont, François-Xavier Standaert and Stefan Tillich. Of the people who contributed to some specific implementation of Keccak, we would like to thank Nuray At, Renaud Bauvin, Begül Bilgin, Joppe Bos, Alfonso De Gregorio, Christopher Drost, Paul Fontaine, Julien Francq, Christian Hanser, Stefan Heyse and team, Gerhard Hoffmann, Elif Bilge Kavun, Paris Kitsos, Christos Koulamas, Kashif Latif and team, Daniel Otte, Thomas Pornin, George Provelengios, Markku-Juhani O. Saarinen, İsmail San, Nicolas Sklavos, Peter Schwabe, Guillaume Sevestre, Joachim Strömbergson, Tolga Yalcin, Bo-Yin Yang and Shang-Yi Yang. A special mention goes to Bernhard Jungk for his particularly inventive small footprint FGPA implementation and our dear ST colleague Ronny Van Keer for his impressive contribution to optimize Keccak on several CPUs. Keccak can be used in keyed modes and in circumstances where protection against differential power analysis (DPA) is important. In this respect we would like to thank Svetla Nikova, Vincent Rijmen and Martin Schläffer for proposing a method that achieves this and Nicolas Debande and Thanh-Ha Le for helping us analyze this method. We would like to thank the members of the other SHA-3 candidate teams and the participants of the workshops that took place in the last six years for the many interesting discussions, and we thank explicitly Dan Bernstein, Alex Biryukov, Andrej Bogdanov, Christophe De Cannière, Praveen Gauravaram, Sebastiaan Indesteeghe, Nuutti Kotivuori, Marko Krause, Tanja Lange, Pierre-Yvan Liardet, Stefan Lucks, Florian Mendel, Christian Rechberger, Francesco Regazzoni, Vincent Rijmen, Tom Ristenpart, Tom Shrimpton, Yannick Teglia and Elmar Tischhauser. Our thanks also go to the partners of the Ecrypt II Network of Excellence that greatly contributed to the SHA-3 process by providing a platform for keeping track of cryptanalysis of the SHA-3 candidates on the SHA-3 Zoo and bringing researchers together in a series of workshops, retreats and summer schools. Additionally, we thank Alex Biryukov, Stefan Lucks and Frederik Armknecht for organizing the ESC and Dagstuhl seminars that likewise stimulated interaction between cryptographers, as well as all the people we forgot to mention…

Of course we also insist on thanking our colleagues at ST Zaventem, Agrate and Rousset and NXP Haasrode for supporting us, more particularly our managers Yves Moulart, Armand Linkens, Bernard Kasser, Stefan De Troch, Lars Reger and Marc Vauclair, and for kindly sponsoring several hardware platforms that we used to evaluate Keccak. A major part of the effort that went into Keccak was funded by the Agentschap voor Innovatie door Wetenschap en Technologie (IWT), so we thank them for their trust and support. And last but not least, we want to thank the NIST team for organizing the SHA-3 competition and bringing it to a successful conclusion.

But the work is not completely done yet! For Keccak to achieve security assurance, it is vital that third-party cryptanalysis continues. So we invite all young and experienced cryptanalysts to ignore our security arguments and boldly attack Keccak as if your life depended on it. You can actually make some (symbolic) money by breaking open challenges in the Keccak Crunchy Crypto Contest.

Updated implementation overview

29 May 2012

We release version 3.2 of our document Keccak implementation overview, together with an updated implementation package. The differences with version 3.1 include slice-based implementations, comments on new software platforms, the mid-range hardware core and updates on the protections against side-channel attacks.

Updated version of KeccakTools available

25 April 2012

We release KeccakTools v3.3, a set of documented C++ classes that can help analyze Keccak. This new version is a major update, as it adds important classes and methods related to differential and linear cryptanalysis.

We used these classes and methods to obtain the results reported in the paper Differential propagation anaylsis of Keccak presented at FSE 2012 (also available as ePrint 2012/163). These include:

The complete list of features can be found here.

The Keccak crunchy crypto contest continues through end 2012

8 April 2012

Immediately after posting the results of the contest, we announce that the Keccak Crunchy Crypto Collision and Pre-image contest re-opens and continues through end 2012.

The challenges remain the same, although a few entries are closed to encourage new approaches. More specifically:

We suggest all interested people to subscribe to our mailing list, and solutions shall be sent to this mailing list, as detailed here, before before December 31, 2012 at 23:59 GMT+1.

Congratulations to the winners of the Keccak crunchy crypto contest

8 April 2012

We announced the winners of the Keccak Crunchy Crypto Collision and Pre-image contest during the Fast Software Encryption 2012 workshop.

The winners are:

We handed out the prizes to the winners during the presentation of the results. Paweł was not present, so we contacted him and arranged with him how to give him his prize.

Congratulations to all!

Readable C code for Keccak

27 February 2012

Markku-Juhani O. Saarinen posted an implementation of Keccak in C aimed at readability and clarity, as an alternative to our specifications summary. We appreciate Markku's support.

New Keccak mid-range core hardware implementation

13 February 2012

We released the VHDL code of a new mid-range core hardware implementation of Keccak.

The new implementation takes inspiration from the work of Bernhard Jungk and Jürgen Apfelbeck presented at ReConFig 2011. It cuts Keccak's state in typically 2 or 4 pieces, so naturally fitting between the fast core (1 piece) and Jungk and Apfelbeck's compact implementation (8 pieces). As a result, we get a circuit not as fast as the fast core but more compact.

The implementation is parametrized by Nb, which determines the amount of folding. With Nb=2, the Keccak-f[1600] permutation is computed in 74 clock cycles, and in 124 clock cycles with Nb=4. Higher values of Nb are possible, although not the main target of our new architecture.

We made some preliminary synthesis of this mid-range core and evaluated the corresponding throughput, with the same STM 130 nm technology used for the other implementations of Keccak. At 500MHz, we can reach a throughput of 5.6 Gbit/s in 28 kGE with Nb=2 or 3.6 Gbit/s in 22 kGE with Nb=4. As a comparison at the same frequency, the fast core processes 21.3 Gbit/s and requires 48 kGE. (In all cases, the throughput is for a rate of 1024 bits.)

We will report more data and a description of the architecture in an up-coming release of the Keccak implementation overview document.

New implementation techniques, packages and documentation

5 September 2011

We release a set of new implementation packages and documentation, which together describes and provides examples of optimization techniques for Keccak on various platforms. Among the implementation techniques is a new in-place processing of Keccak-f, which allows implementations that are both compact and efficient on microcontrollers and other constrained devices.

The released documents and packages include:

By applying in-place processing to the ARM Cortex-M3 (implementation by Ronny Van Keer), Keccak[] takes about 95 cycles/byte for long messages and uses less than 280 bytes of RAM on the stack, according to our measurements. This and other new implementations have been submitted to eBASH and XBX for independent benchmarking.

Keccak crunchy crypto contest: first solutions received!

6 August 2011

About 6 weeks after the launch of the Keccak Crunchy Crypto Collision and Pre-image contest, we have received the first solutions.

Last Friday, July 29, Paweł Morawiecki sent us 12 solutions: one for each 1-round and 2-round challenge, with the exception of those for Keccak-f[200]. Currently we owe 60€ to Paweł. If someone else solves the Keccak-f[200] challenges, this may still reduce to 52.5€.

Then Tuesday this week, August 2, a team consisting of Alexandre Duc, Jian Guo, Thomas Peyrin and Lei Wei sent us two solutions: a 1-round and a 2-round collision for Keccak-f[1600]. This is four days after we received solutions for the same parameters from Paweł, but due to our delay in communication there was no way for them to know that the challenges they were working on had already been submitted. For that reason we have decided to exceptionally award them a prize as if they were first: 15€ in total.

We congratulate Paweł and the Alexandre-Jian-Thomas-Lei team with their successes!

You can find the received solutions on the Keccak Crunchy Crypto Collision and Pre-image Contest webpage. Clicking on the solutions leads you to the emails received from the submitters, giving the concrete values and some background.

We created a mailing list dedicated to this contest. To speed up the communication of solutions, we suggest all interested people to subscribe to it by sending an empty mail to crunchy-subscribe -at- noekeon -dot- org and from now on solutions should be sent to crunchy -at- noekeon -dot- org.

Keccak Crunchy Crypto Collision and Pre-image Contest

16 June 2011

After four rounds of Keccak cryptanalysis prizes, we now take an initiative that solicits attacks relevant in a hash function setting: the Keccak Crunchy Crypto Collision and Pre-image Contest. In particular, we hand out money prizes for pre-images of published images and collisions for a set of reduced-round members of the Keccak family.

In total we present challenges for 48 reduced-round Keccak instances, namely Keccak[c=160, r=b-c] with b ≥ 200:

For each of these Keccak instances there are two challenges, so 96 in total:

We have released KeccakTools v3.1, which contains support for the validation of solutions (see file KeccakCrunchyContest.cpp).

Please visit the Keccak Crunchy Crypto Contest page for the contest rules and pre-image challenges.

On alignment in Keccak

20 May 2011

We wrote a paper, in which we investigate the ability to predict the propagation of truncated differences and linear masks in cryptographic primitives. We speak of strong alignment if this propagation is predictable and of weak alignment if the propagation is hard to predict. We show the relevance of alignment with respect to some types of cryptanalysis including the rebound attack. We give insight on the alignment in Keccak by reporting on a number of experiments we conducted. It appears that the propagation of differences or linear masks does not respect the row boundaries, hence Keccak has weak alignment.

This paper can be downloaded here and was presented today at the ECRYPT II Hash Workshop 2011 in Tallinn, Estonia.

Updated VHDL package

1 February 2011

We updated the VHDL package of Keccak to be compliant with its new padding rule. In fact, the VHDL code itself has not changed since version 2.0, as the underlying permutation was not modified. But we updated the testing program in C to be in line with the new padding rule and to support input messages of any bit length.

The new package can be downloaded here.

Simplifying Keccak's padding rule for round 3

17 January 2011

For the third round of the SHA-3 competition, we decided to shorten and simplify the padding rule used in Keccak. We also took the opportunity to provide a fresh new structure in our documentation, in particular for a clean split between general sponge-related aspects and Keccak-specific ones, and between implementation-related aspects and cryptographic ones.

We made the following changes to the Keccak specifications.

Note that no changes have been made to Keccak-f.

With this new version, we make the following documents available on our web page.

And obviously, the implementation packages have been updated and are available for download.

Keccak selected for the third (and final) SHA-3 round

11 December 2010

We are happy to announce that NIST selected Keccak as one of the five SHA-3 candidate algorithms to advance to the third (and final) round. The announcement has been made recently on the SHA-3 mailing list. Congratulations to the other nominees: BLAKE, Grøstl, JH and Skein!

Congratulations to the winners of the fourth cryptanalysis and Hex-Hot-Ticks prizes

7 December 2010

First, we are happy to announce that Dan Bernstein is the winner of the fourth Keccak cryptanalysis prize for his attack posted on NIST's hash forum Second preimages for 6 (7? (8??)) rounds of Keccak?. The attack exploits the low degree of Keccak-f's round function into a (second) preimage attack at the sponge function level and has been recently extended to 8 rounds, as suggested in the initial posting. We are currently arranging practical details with the winner to give him the awarded Belgian chocolates.

Second, we are also happy to announce that (in alphabetical order) Gerhard Hoffmann and Guillaume Sevestre are the ex aequo winners of the Hex-Hot-Ticks prize for the most interesting implementation of Keccak on exotic platforms. They will each receive a Himitsu-Bako secret box.

Congratulations to all of them!

Yet another optimized implementation package

27 November 2010

Version 2.4 of the optimized implementations is now available. It contains further implementations for small processors. Compared to the previous version, this package provides the following new implementations:

As before, these implementations have been submitted to eBASH and XBX for benchmarking.

New optimized implementation package

3 November 2010

Version 2.3 of the optimized implementations is now available.

This new version follows the same line of improvements as the previous one published in October, with contributions by both Ronny Van Keer, STMicroelectronics and ourselves. Compared to the previous version, this package provides the following new implementations:

A subset of these new variants and implementations has been submitted to eBASH and XBX.

New pages on our website

2 November 2010

We have re-organized some of the pages on this website. We provide a new page listing the hardware performance of Keccak on different technologies, a page dedicated solely to third-party cryptanalysis results, and a new page for general implementation aspects of our sponge function.

An implementation in Python

21 October 2010

Renaud Bauvin, STMicroelectronics, made an implementation of Keccak in Python, compatible with versions 2 and 3 of the language. It supports from Keccak-f[200] to Keccak-f[1600] and includes routines to check the test vectors. The package is available here.

New optimized implementation package

5 October 2010

Version 2.2 of the optimized implementations is now available.

Compared to the previous version, this package provides some new implementations, all written by Ronny Van Keer, STMicroelectronics, namely:

The new package also contains various improvements here and there, including a wider range of supported variants. A subset of these new variants and implementations has been submitted to eBASH.

14 September 2010

Marko Krause of the University of Oldenburg created animated illustrations of the Keccak specifications (in German). He also provides an implementation of Keccak[r+c=800] in Python. The source files are available here.

Extension of the fourth cryptanalysis and Hex-Hot-Ticks prizes

8 September 2010

In February, we announced the Hex-Hot-Ticks prize for the most interesting implementation of Keccak on exotic platforms and one month later the fourth prize for the best cryptanalysis to encourage third-party analysis of Keccak.

The fourth cryptanalysis prize consisted of a box of 600g of the finest Belgian pralines. We increase this now to 1200g. To be gentle on your liver, please consider submitting as a team or sharing the pralines with your relatives. :-)

The deadline of both prizes is extended to November 30, 2010. The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before Tuesday November 30, 2010 at 23:59 GMT+1.

New versions of the main document and of KeccakTools

19 June 2010

We release new versions of the Keccak main document and of KeccakTools.

Besides some restructuring and editorial improvements, Keccak main document v2.1 brings new contents, such as a complete new chapter specifically dedicated to differential and linear trail search, new cryptanalysis experiments and new hardware implementation results. Note that the specifications have not changed since the second-round submission.

At the same time, we release KeccakTools v2.1, a set of documented C++ classes that can help analyze Keccak-f. Compared to v2.0, the new version adds several important classes aimed at the linear and differential cryptanalysis of Keccak-f. Essentially, these classes provide ways to represent and process linear and differential trails and to extend them forwards or backwards. They also support the generation of equations for the conditions imposed by a differential trail on its pairs. As much as possible, linear and differential trails are considered on an equal footing, and most methods can be applied to both kinds of trails.

Deadline extension of the fourth cryptanalysis and Hex-Hot-Ticks prizes

17 June 2010

In February, we announced the Hex-Hot-Ticks prize for the most interesting implementation of Keccak on exotic platforms and one month later the fourth prize for the best cryptanalysis to encourage third-party analysis of Keccak. The deadline for both prizes was set to June 30, 2010.

However, as we planned to announce the winners during the rump session of the SHA-3 workshop in Santa Barbara on August 23-24, we have decided to extend the deadline to midnight August 20. This will allow the submission of results obtained during the summer, including the SAC workshop and the CHES and CRYPTO conferences.

The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before Friday August 20, 2010 at 23:59 PDT (GMT-7).

Fourth cryptanalysis prize

4 March 2010

We announce the fourth prize for the most interesting cryptanalysis of Keccak. The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before June 30, 2010 at 12:00 GMT+2.

The fourth prize consists of chocolate and more exactly of pralines from one of the finest Belgian chocolate craftsmen. The first Belgian praline has been made in 1912 by Jean Neuhaus, and since then the praline has become one of the most renowned quality products from Belgium. The prize consists of a box of 600g (the number of rounds times the number of lanes in Keccak) of the finest Belgian pralines.

Like for the previous prizes, who wins will be decided by consensus in the Keccak team, based internally on a system of points. Some hints:

We reserve the right to extend the deadline in the absence of interesting results or when we consider that the presented results are too small increments compared to known results.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Note on Keccak parameters and usage

25 February 2010

The Keccak sponge function family is characterized by three parameters: the bitrate r, the capacity c and the diversifier d. In the Keccak specifications we propose four instances that can be taken as functions for the four (fixed) output lengths NIST requires for SHA-3 and a variable-output-length instance, with default values for the parameters.

Whilst we are happy with our choice, there are other valid parameter choices that NIST or others may prefer. We publish a new note, in which we discuss our choice of parameters and other possible ways of using the Keccak family.

Congratulations to the winners of the third Keccak cryptanalysis prize

16 February 2010

We are happy to announce that Christina Boura and Anne Canteaut are the winners of the third Keccak cryptanalysis prize for their paper entitled A zero-sum property for the Keccak-f permutation with 18 rounds. We are currently arranging practical details with the winners to give them the awarded Lambic-based beers and book. Congratulations to them!

We will soon announce a new prize with a new deadline.

Hex-Hot-Ticks Keccak prize

2 February 2010

We are looking for implementations of Keccak on exotic platforms! We offer a prize for the most interesting implementation of Keccak on:

The prize consists in a Himitsu-Bako secret box.

Who wins the prize will be decided by consensus in the Keccak team. We will internally use a system of points. Some hints:

We give freedom in the way Keccak is used. It is allowed to implement, for instance, tree hashing or batch hashing (several messages hashed in parallel), instead of plain sequential hashing, to take advantage of parallel computing and get better performance.

The results and source code must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before June 30, 2010 at 12:00 GMT+2. No specific licensing condition is requested (pick up the one you like!). We reserve the right to extend this deadline in the absence of interesting results. Otherwise, the winner will be announced during the rump session of the second SHA-3 candidate conference in Santa Barbara.

Note on zero-sum distinguishers

16 January 2010

In September last year, Jean-Philippe Aumasson and Willi Meier introduced zero-sum distinguishers, a method to generate zero-sum structures for reduced-round versions of Keccak-f up to 16 rounds. Recently, Christina Boura and Anne Canteaut extended this to 18 rounds. (See the page on third-party cryptanalyis for references and more details.)

We publish a note, in which we give technical details and put these distinguishers into perspective. We also relate their existence to our decision to increase the number of rounds to 24, in line with the hermetic sponge strategy, in which we tolerate no structural distinguisher for the permutation used in the sponge construction.

Third cryptanalysis prize deadline extension

8 December 2009

In September, we announced the third prize for the best cryptanalysis on Keccak to encourage third-party analysis. As no submission has been received yet, we have decided to extend the deadline: the results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before Saturday February 13th, 2010 at 23:59 GMT+1 (i.e., before the carnival).

In addition to the bottles of Lambic-based beer, the prize also comes with a guide about Brussels' beers to better enjoy their special taste.

As always, we hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Tune Keccak to your requirements

12 November 2009

We provide a new page to help choose the best parameters of Keccak by specifying one's requirements in terms of collision and (second) preimage resistance. A simple application in JavaScript computes the optimal values of bitrate, capacity and output length. Have fun!

Optimized implementation updated

19 October 2009

Version 2.1 of the optimized implementation is now available. This version corrects some compilation problems with the Intel compiler and adds code specifically optimized for the case where r is 1088 bits.

Updated version of KeccakTools available

7 October 2009

We release KeccakTools v2.0, a set of C++ classes that can help analyze Keccak. Besides some minor improvements since v1.1, the default number of rounds of the Keccak-f permutation has been adapted to the new Keccak specifications.

As a reminder, KeccakTools currently supports:

The code is documented with comments in the Doxygen format. The documentation can also be browsed online.

Third cryptanalysis prize

30 September 2009

We announce the third prize for the most interesting cryptanalysis of Keccak. The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before December 5, 2009 at 23:59 GMT+1 (i.e., before Sinterklaas or Saint Nicolas).

The third prize consists of beer, like the first one. This time we offer Lambic beers that according to myth can only be brewed in the surroundings of Brussels thanks to wild yeast and mysterious bacteria that would not occur anywhere else. Anyway, the prize is a case with 24 (the new number of rounds in Keccak-f) bottles of Lambic-based beers from breweries such as Cantillon, Girardin, and 3 Fonteinen.

Like for the previous prizes, who wins will be decided by consensus in the Keccak team, based internally on a system of points. Some hints:

We reserve the right to extend the deadline in the absence of interesting results or when we consider that the presented results are too small increments compared to known results.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Keccak parameter changes for round 2

22 September 2009

For the second round of the SHA-3 competition, we decided to modify the parameters of Keccak. There are basically two changes: the modification of the rate and capacity values in the four fixed-output-length candidates for SHA-3 and the increase of the number of rounds in Keccak-f.

The increase in the rate was done for taking better advantage of the performance-security trade-offs that the Keccak sponge function allows.

The increase in the number of rounds is due to the distinguishers recently found by Jean-Philippe Aumasson and Willi Meier that work on reduced-round variants of Keccak-f[1600] up to 16 rounds. Although we think it is infeasible to exploit the 16-round distinguisher on Keccak-f when used in the sponge construction, we want the underlying permutation to have no structural distinguishers. This is the basis of our conservative design strategy: the hermetic sponge strategy (see the Keccak main document, Section 4.1.1).

Sticking to 18 rounds would not contradict this strategy but would leave a security margin of only 2 rounds against a distinguisher of Keccak-f. We think that the increase in the number of rounds actually increases the security margin with respect to distinguishers of and attacks against the Keccak sponge functions.

Finally, note that the modifications do not change the round function and therefore do not invalidate any past or ongoing cryptanalysis of Keccak.

The updated Keccak specifications (version 2) and main document (version 2.0) containing some new analysis can be found on this website.

Congratulations to the winners of the second Keccak cryptanalysis prize

9 September 2009

We are happy to announce that Jean-Philippe Aumasson and Willi Meier are the winners of the second Keccak cryptanalysis prize for their note entitled Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi. The awarded Bialetti coffee machine and its full travel set were handed over to Jean-Philippe yesterday at the rump session of CHES 2009 in Lausanne. Congratulations to them!

We will soon announce a new prize with a new deadline.

Optimized implementation updated

24 August 2009

Version 1.3 of the optimized implementation is now available. As the only change, this new version corrects a bug related to endianness. The bug specifically affected the 32-bit optimized version, using interleaving without tables, on big-endian architectures. Thanks to Joppe Bos for spotting and helping solve this problem!

NIST chooses 14 second-round candidates

28 July 2009

Last Friday, NIST announced the 14 candidates they chose for the second round of the SHA-3 competition. We are happy to say that Keccak is among them!

Second cryptanalysis prize deadline extension

3 July 2009

In May, we announced the second prize for the best cryptanalysis on Keccak to encourage third-party analysis. As no submission has been received yet, we have decided to extend the deadline: the results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before Monday August 31st, 2009 at 23:59 GMT+2.

The prize itself is also extended and now consists of the full travel set, including the Bialetti coffee machine, cups, spoons, a canister for sugar, some of the best Italian coffee and a case for easy carry to cryptographic conferences.

Again, we hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Third-party analysis and implementation page

13 June 2009

We provide a new page listing the third-party papers, studies and implementations related to Keccak in the scope of the SHA-3 contest or otherwise.

We plan on updating this page whenever needed.

Second cryptanalysis prize

14 May 2009

We announce the second prize for the most interesting cryptanalysis of Keccak. The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before June 30, 2009 at 23:59 GMT+2. We reserve the right to extend this deadline in the absence of interesting results.

This time, the prize is a Bialetti coffee machine of fine Italian design, plus a set of some of the best Italian coffee.

Like for the previous prize, who wins will be decided by consensus in the Keccak team, based internally on a system of points. Some hints:

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Congratulations to the winners of the first Keccak cryptanalysis prize

29 April 2009

We are happy to announce that Jean-Philippe Aumasson and Dmitry Khovratovich are the winners of the first Keccak cryptanalysis prize for their paper entitled First Analysis of Keccak. The case of beers was handed over to Dmitry yesterday at the rump session of Eurocrypt in Köln. Congratulations to them!

We will soon announce a new prize with a new deadline.

Updated documentation and implementation

23 April 2009

Version 1.2 of the main document and of the implementation are now available! In addition, a new version of KeccakTools is also available.

The changes include:

Note that the Keccak algorithm, specifications and test vectors have not changed since the initial NIST submission.

Keccak performance figures page

15 April 2009

We provide a new page listing the performance of Keccak on different platforms. The measurements come from eBASH, from which we have taken a small set of relevant figures: the performance of Keccak[r=1024,c=576] for small (≤ 124 bytes) and large messages, plus SHA-256 and SHA-512. The selected results come from machines with recent compilers (GCC ≥ 4.3, unless for ia64) and recent SUPERCOP versions (SUPERCOP ≥ 20090205). When several machines with the same processor meet the criteria, only one is shown.

We plan on updating this page on a regular basis.

Keccak implementations using SIMD instructions

6 April 2009

We submitted new implementations of Keccak to the eBASH project. In addition to the plain C 32-bit and 64-bit implementations previously submitted, the new variants take advantage of the 64-bit MMX or 128-bit SSE2 instructions of the AMD and Intel processors.

When used on the reference processor defined by NIST, restricted to 32-bit instructions, Keccak achieves about 15 cycles/byte using SSE2 (versus 26.5 cycles/byte in plain C, on x86 katana). When unrestricted, the reference processor allows Keccak to run at about 10 cycles/byte.

The MMX variants are useful for older x86 processors.

Cryptanalysis prize deadline extension

27 February 2009

Recently, we announced a prize for the best cryptanalysis on Keccak to encourage third-party analysis. As no submission has been received yet, we announce an extension of the deadline: the results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before Friday April 24, 2009 at 16:00 GMT+1.

The date is chosen to be right before Eurocrypt 2009. As said, we'll do our best to bring the case and the winners together, for instance at the Eurocrypt conference in Köln.

Compared to the original announcement, the prize now comprises 25 bottles of Belgian beer (instead of 24) so that there are as many bottles as lanes in Keccak-f.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

Cryptanalysis prize

23 January 2009

Inspired by Dan Bernstein's CubeHash prizes, we offer a prize for the most interesting Keccak cryptanalysis. The results must be publicly available on an URL that is sent to keccak -at- noekeon -dot- org before February 23, 2009 at 12:00 GMT+1. We reserve the right to extend this deadline in the absence of interesting results. Otherwise, the winner will be announced during the Rump session of the first SHA-3 candidate conference in Leuven.

Who wins the prize will be decided by consensus in the Keccak team. Similar to Dan Bernstein, we will use a system of points. Some hints:

We wanted to offer a prize which has a cultural dimension and is likely to appeal to the typical cryptanalyst. This forced us to the choice we have made. The prize is a case with 24 bottles of 33cl Trappist beers from all 6 recognized Trappist breweries in Belgium. It includes bottles of Westmalle Dubbel, Westmalle Tripel, Chimay bleue, Chimay rouge, Chimay blanche, Rochefort 8, Rochefort 10, Orval, Achel Blond, Achel Bruin and probably the most hard to get beer in the world: the mythical Westvleteren 12°.

In case there is a winner by the first SHA-3 candidate conference and she/he/they are present, we'll bring the case to Leuven and hand it over there. Otherwise, we'll do our best to bring the case and the winners together. Once the winner is known there is no hurry as the expiry dates on most of the bottles are years from now.

Introducing KeccakTools

22 January 2009

We make available KeccakTools v1.0, a set of C++ classes that can help analyze Keccak. KeccakTools provides the following features:

The code is documented with comments in the Doxygen format. The documentation can also be browsed online.

Since this is the first public release of KeccakTools, do not hesitate to report problems, e.g., in the compilation process (it has been tested with GCC 4.3 and Microsoft Visual C++ 2008 Express Edition), or things that are not clear in the documentation. All feedback and questions are welcome any time of course.

Updated documentation and implementation

13 January 2009

Version 1.1 of the main document and of the implementation are now available!

This version includes:

A change log in the appendix of the main document brings you directly to the changed sections.

Note that the Keccak algorithm, specifications and test vectors have not changed since the initial NIST submission.

Keccak submitted to eBASH

22 December 2008

We submitted Keccak to the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project and the first results are appearing.

eBASH measures the speed of hash functions on a wide variety of machines using a tool called SUPERCOP. The software reports the number of cycles necessary to hash messages of different sizes, from 8 to 4096 bytes, and extrapolates for longer messages. It benchmarks many SHA-3 candidates, as well as older hash functions as a comparison.

The first results confirm speeds that are close to 10 cycles/byte on the reference platform defined by NIST. More precisely, 10.14 cycles/byte are reported on the machine named "cobra" (Intel Core 2 Duo E4600) using the amd64 architecture and 31.52 cycles/byte when using only 32-bit x86 instructions (long messages, median).

Keccak news feed available

11 December 2008

Welcome to the Keccak page! This page is dedicated to the cryptographic hash function family called Keccak, which we submit as a SHA-3 candidate. You can already find the complete specification and main document, software and hardware implementations, test vectors and results of the Monte-Carlo tests.

Although the Keccak specifications are frozen, we are still working on it actively to improve the analysis and implementation. We plan to publish a new version of the main document to describe the latest state of the analysis. Also, we are working on an improved software implementation, which we will publish the results soon. So please come visit us to get the latest news on Keccak, or better yet, subscribe to the news feed to receive automatically these news in your newsfeed reader.