# News archives 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!

• 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!

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

• 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 implementation of the seven Keccak-f permutations, from Keccak-f[25] to Keccak-f[1600], possibly with a specified number of rounds;
• the implementation of the inverses of the seven Keccak-f permutations;
• the generation of look-up tables for Keccak-f[25];
• the generation of GF(2) equations of the round functions and step mappings in the Keccak-f's and their inverses;
• the generation of optimized C code for the round functions, including lane complementing and bit interleaving techniques;
• the implementation of the sponge construction using any transformation or permutation, and of the Keccak sponge function family.

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

• 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:

• Innovative ideas get more points than incremental results or applying standard techniques;
• For attacks with innovations that are comparable, the earlier ones get more points;
• Cryptanalysis or attack techniques applicable to a wider range of valid parameters r, c get more points (see the specifications for the definition of valid parameters);
• Larger Keccak-f width gets more points;
• Larger capacity gets more points;
• Attacks on reduced-round versions are allowed but more rounds get more points;
• For the same number of rounds, a distinguisher or attack on the Keccak sponge function gets more points than a distinguisher on Keccak-f only.

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!

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

• In the case of fixed-output-length candidates, we increased the rate r to set the capacity c to twice the output length value.
• We increased the number of rounds of Keccak-f from 12+l to 12+2l (from 18 to 24 rounds for Keccak-f[1600]).

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.

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

• 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!

• 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!

• 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!

• 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 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:

• Innovative ideas get more points than incremental results or applying standard techniques;
• For attacks with innovations that are comparable, the earlier ones get more points;
• Cryptanalysis or attack techniques applicable to a wider range of valid parameters r, c get more points (see the specifications for the definition of valid parameters);
• Larger Keccak-f width gets more points;
• Larger capacity gets more points;
• Attacks on reduced-round versions are allowed but more rounds get more points.

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

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

• 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:

• A new optimized implementation using SIMD instructions is available.
• In the main document, we added a 2-page specifications summary, more explanations on difference propagation and correlation properties of χ, ANF tests also on the inverse of Keccak-f and new software performance results in general and regarding SIMD instructions in particular. (A change log in the appendix of the main document brings you directly to the changed sections.)
• The new version of KeccakTools is able to generate the source code of the new optimized implementation.

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

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

• 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!

• 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:

• Innovative ideas get more points than incremental results or applying standard techniques;
• For attacks with innovations that are comparable, the earlier ones get more points;
• Cryptanalysis or attack techniques applicable to a wider range of valid parameters r, c get more points (see the specifications for the definition of valid parameters);
• Larger Keccak-f width gets more points;
• Larger capacity gets more points;
• Attacks on reduced-round versions are allowed but more rounds get more points.

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.

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

• the implementation of the seven Keccak-f permutations, from Keccak-f[25] to Keccak-f[1600], possibly with a specified number of rounds;
• the implementation of the inverses of the seven Keccak-f permutations;
• the generation of look-up tables for Keccak-f[25];
• the generation of GF(2) equations of the round functions and step mappings in the Keccak-f's and their inverses;
• the generation of optimized C code for the round functions, including lane complementing and bit interleaving techniques;
• the implementation of the sponge construction using any transformation or permutation, and of the Keccak sponge function family.

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.

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

This version includes:

• Additional usage modes on top of Keccak, including the possibility to do tree and parallel hashing;
• Improved optimized software implementations, using new techniques to reduce the number of NOT instructions and to use only 32-bit rotations on 32-bit platforms;
• New hardware implementations, with better performance and code suitable for FPGAs, considering the work published by Joachim Strömbergson.

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.