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:

• Version 3.1 of the optimized implementations, containing examples of in-place implementations as well as an assembly version for the x86_64 architecture;
• Version 3.1 of the Keccak implementation overview document, with a new chapter specifically dedicated to optimization techniques;
• A new version of KeccakTools, with methods dedicated to the generation of C code chunks to help write optimized implementations.

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.

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.

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:

• The capacity is fixed to 160 bits: this implies a security level of 2⁸⁰ against generic collision search.
• The width b of Keccak-f[b] is in {200, 400, 800, 1600}: the width values that support the chosen capacity.
• The number of rounds n_r ranges from 1 to 12.

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

• generating a collision in the output truncated to 160 bits;
• generating a pre-image of an output truncated to 80 bits.

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.

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.

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.

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.

• We shortened and simplified the padding rule. The new padding rule is the pad10^*1 rule, which is suitable for a family of sponge functions sharing the same permutation with different rate-capacity pairs. It is simpler to describe and to implement than the previous padding rule. It is also more efficient, as it appends a minimum of 2 bits instead of 25. For long messages, the gain is negligible, but short messages can be 3 bytes longer for the same number of calls to Keccak-f. This aspect is especially relevant when using the duplex construction.
• We removed the diversifier parameter d. All the fixed-output-length candidates have different bitrates, which already provides diversification between them, hence making d redundant in this case. Diversification between functions using the same bitrate is still possible using more general mechanisms that we describe in our documentation.
• We removed the restriction on the bitrate r. Previously, the bitrate could only take values that are multiple of 8 bits. Now all the values between 1 and the permutation width are supported. Although a bitrate multiple of 8 bits is a natural choice to avoid undesirable intra-byte bit shuffling on the input blocks, schemes making use of the duplex construction can take advantage of this to propose round-sized input blocks to the application level and put frame bits in a few extra bits.

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

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

• The Keccak reference is the main document that specifies and analyzes the Keccak sponge function family.
• The Keccak SHA-3 submission is the entry document of the SHA-3 submission, with our proposals for the standard.
• Keccak implementation overview gives an overview of the implementation aspects, in software and hardware, with or without protection against side-channel attacks.
• Cryptographic sponge functions gathers our definitions and analysis related to the sponge construction, on which Keccak is based.

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