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
25 April 2012 — Updated version of KeccakTools available
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 exhaustive forward and backward extension of trails up to a given weight and given number of rounds;
- related to θ:
- the representation of column parities in runs;
- lower bounding the weight of any 2-round trail core with a given parity;
- the exhaustive generation of 2-round trail cores with a given parity;
- the exhaustive generation of 2-round trail cores with a small number of active rows;
- the exhaustive generation of 3-round trail cores in the kernel up to a given weight:
- the generation of knots and chains between knots;
- the generation of vortices and their combination with knots and chains;
- the implementation of a lower bound on the weight while adding knots, chains and vortices to limit the search.
The complete list of features can be found here.
8 April 2012 — The Keccak crunchy crypto contest continues through end 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:
- All the collision and pre-image challenges for Keccak[r = 40, c = 160] remain open, from 1 to 12 rounds, as none of these were solved.
- For the other instances, pre-image challenges start from 3 rounds and collision challenges from 5 rounds. The only unsolved challenges that are closed are 3- and 4-round collisions, which can likely be solved by a straightforward application of the techniques of Itai Dinur, Orr Dunkelman and Adi Shamir.
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.
8 April 2012 — Congratulations to the winners of the Keccak crunchy crypto contest
We announced the winners of the Keccak Crunchy Crypto Collision and Pre-image contest during the Fast Software Encryption 2012 workshop.
The winners are:
- Paweł Morawiecki for solving the preimage and collision challenges on 1 and 2 rounds, for all instances except Keccak[r = 40, c = 160];
- Alexandre Duc, Jian Guo, Thomas Peyrin and Lei Wei for independently and simultaneously solving the collision challenges on 1 and 2 rounds of Keccak[r = 1440, c = 160];
- Itai Dinur, Orr Dunkelman and Adi Shamir for finding collisions on Keccak[r = 1440, c = 160] with 3 and 4 rounds.
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!
27 February 2012 — Readable C code for Keccak
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.
13 February 2012 — New Keccak mid-range core hardware implementation
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.
Contact Information
Email: keccak-at-noekeon-dot-org