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

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

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

• An improved implementation for AVR8 processors, with the Keccak-f[1600] permutation fully in assembly.
• The assembly implementation for ARM processors already introduced in version 2.2, converted to a syntax understood by GCC. (This implementation is optimized for Cortex-M3 specifically and requires Thumb and Thumb2 support.)

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

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

• An implementation for AVR8 processors, meant to be reasonably compact in terms of both code size and memory usage. (Again, we provide an API for giving partial input chunks, while removing the need of a message queue.)
• An implementation similar to the previous one, but using only pure C, as the basis for optimization on 8-bit processors in general.
• A simple yet optimized implementation in C using only 32-bit operations, using the bit interleaving technique.

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

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

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

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

• An assembly implementation for ARM processors, optimized for Cortex-M3 specifically—although at this point it is written in the syntax of RVCT's armcc/armasm, not yet in a syntax understood by GCC.
• A simple yet optimized implementation in C covering from Keccak-f[200] to Keccak-f[1600].
• An implementation in C meant to be reasonably compact in terms of both code size and memory usage. (E.g., we provide an API for giving partial input chunks, where these partial input chunks are XORed directly into the state of Keccak to remove the need of a separate message queue.)

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.

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

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

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

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

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

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

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

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

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

• graphic cards or GPU,
• embedded processors (e.g., ARM, Cell processor…),
• or any other analog/digital computing device.

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:

• fast implementations get more points;
• uncommon devices get more points.

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.

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