News feed (atom)
This page is dedicated to the cryptographic hash function family called Keccak, which we submit as a SHA-3 candidate.
The reference specification, analysis, reference and optimized code and test vectors for Keccak can be found in the file section.
For a quick introduction, a pseudo-code description of Keccak is given here.
Keccak in a nutshell
Keccak makes use of the sponge construction and is hence a sponge function family.
The design philosophy of Keccak is the hermetic sponge strategy. It uses the sponge construction for having provable security against all generic attacks. It calls a permutation that should not have structural properties with the exception of a compact description. By structural properties we mean properties that a typical random permutation does not have.
Keccak can be considered as a successor of RadioGatún. However, it has a very different design philosophy. The transformation applied to the state of RadioGatún in between the insertion of input blocks or extraction of output blocks is a simple round function. This round function has algebraic degree two and thus does not attempt to be free of structural properties. Therefore, unlike Keccak, RadioGatún requires blank rounds. Moreover, RadioGatún is not a sponge function as its iteration mode does not follow the sponge construction.
The permutation Keccak-f has the following properties:
- It consists of the iteration of a simple round function, similar to a block cipher without a key schedule.
- The nominal version of Keccak-f operates on a 1600-bit state. There are 6 other state widths, though: 25, 50, …, 800.
- The choice of operations is limited to bitwise XOR, AND and NOT and rotations. There is no need for table-lookups, arithmetic operations, or data-dependent rotations.
About the performance of Keccak:
- In software, Keccak[] takes about 13 cycles per byte on the reference platform defined by NIST.
- In hardware, it is fast and compact, with area/speed trade-offs.
- It is suitable for DPA-resistant implementations both in hardware and software.
Keccak can be used for:
- keyed or randomized modes simply by prepending a key or salt to the input message;
- generating infinite outputs, making it suitable as a stream cipher or mask generating function.
In these cases, the usage of the sponge construction allows for modes that are provably secure against generic attacks.
Finally, Keccak is flexible. Using the same Keccak-f permutation, different combinations of bitrate and capacity allow for a security/speed trade-off.
Latest news
5 September 2011 — New implementation techniques, packages and documentation
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.
6 August 2011 — Keccak crunchy crypto contest: first solutions received!
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.
16 June 2011 — Keccak Crunchy Crypto Collision and Pre-image Contest
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 280 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 nr 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.
20 May 2011 — On alignment in Keccak
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.
1 February 2011 — Updated VHDL package
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.
Contact Information
Email: keccak-at-noekeon-dot-org