The Keccak sponge function family

Guido Bertoni¹, Joan Daemen¹, Michaël Peeters² and Gilles Van Assche¹

¹STMicroelectronics

²NXP Semiconductors

News items

News feed (atom)

Updated pages

3 June 2013

We added the slides of recent presentations on this page.

Sakura: a flexible coding for tree hashing

3 June 2013

Recently, we released a paper on Sakura, a flexible, fairly general, coding for tree hash modes. The coding does not define a tree hash mode, but instead specifies a way to format the message blocks and chaining values into inputs to the underlying function for any topology, including sequential hashing. The main benefit is to avoid input clashes between different tree growing strategies, even before the hashing modes are defined, and to make the SHA-3 standard tree-hashing ready.

It expands on the concept of “universal” (now: flexible) hash tree coding that we presented at NIST on February 6 (see slides 55-59). The goal is to address tree hashing, as discussed by John Kelsey in his SHA3 presentation at the RSA conference last February.

All comments are welcome!

The Keccak crunchy crypto contest continues through end 2013

24 January 2013

In a previous announcement, we re-opened the Keccak Crunchy Crypto Collision and Pre-image contest until end 2012. As no new challenges were solved between March and December 2012, we decided to leave it open for another year, i.e., until end 2013.

The challenges remain the same. We suggest all interested people to subscribe to our mailing list, and solutions shall be sent to this mailing list, as detailed here, before December 31, 2013 at 23:59 GMT+1.

Updated home page

24 October 2012

We updated the home page of this site and added a picture of the Keccak Team.

NIST selects Keccak for SHA-3

3 October 2012

We are very proud to announce that NIST selected Keccak as the winner of the SHA-3 competition!

It was a pleasure to participate to the competition. Being confronted with ideas from a wide diversity of designs was especially exciting. Beyond the design itself, it was also very interesting to cover several domains, from cryptanalysis to software and hardware implementation aspects.

This success comes also with input from a large number of people and we would like to take this occasion to thank them. We start by thanking those who took the trouble to cryptanalyze Keccak and publish the results, in particular Jean-Philippe Aumasson, Dan Bernstein, Christina Boura, Anne Canteaut, Christophe De Cannière, Itai Dinur, Ming Duan, Alexandre Duc, Orr Dunkelman, Danilo Gligoroski, Jian Guo, Dmitry Khovratovich, Xuejia Lai, Joel Lathrop, Willi Meier, Paweł Morawiecki, María Naya-Plasencia, Rune Steinsmo Ødegård, Thomas Peyrin, Andrea Röck, Adi Shamir, Marian Srebrny and Lei Wei, as well as those who cryptanalyzed its predecessor RadioGatún and thereby gave us the motivation to improve it, namely, Charles Bouillaguet, Pierre-Alain Fouque, Thomas Fuhr, Dmitry Khovratovich and Thomas Peyrin. We thank Elena Andreeva, Bart Mennink, Bart Preneel and Marjan Škrobot for tackling the delicate task of bringing clarity in the soundness properties of the modes of use employed by the SHA-3 (semi-)finalists. In the implementation and benchmarking department, we would like to thank the very valuable software benchmarking initiatives eBASH, ran by Dan Bernstein and Tanja Lange for Ecrypt II, and XBX, ran by Christian Wenzel-Benner, Jens Gräf, John Pham and Jens-Peter Kaps; the several teams that performed hardware comparisons, in particular the teams led or represented by Abdulkadir Akın, Brian Baldwin, Kris Gaj, Frank Gurkaynak, Jens-Peter Kaps, Shin’ichiro Matsuo, Patrick Schaumont, François-Xavier Standaert and Stefan Tillich. Of the people who contributed to some specific implementation of Keccak, we would like to thank Nuray At, Renaud Bauvin, Begül Bilgin, Joppe Bos, Alfonso De Gregorio, Christopher Drost, Paul Fontaine, Julien Francq, Christian Hanser, Stefan Heyse and team, Gerhard Hoffmann, Elif Bilge Kavun, Paris Kitsos, Christos Koulamas, Kashif Latif and team, Daniel Otte, Thomas Pornin, George Provelengios, Markku-Juhani O. Saarinen, İsmail San, Nicolas Sklavos, Peter Schwabe, Guillaume Sevestre, Joachim Strömbergson, Tolga Yalcin, Bo-Yin Yang and Shang-Yi Yang. A special mention goes to Bernhard Jungk for his particularly inventive small footprint FGPA implementation and our dear ST colleague Ronny Van Keer for his impressive contribution to optimize Keccak on several CPUs. Keccak can be used in keyed modes and in circumstances where protection against differential power analysis (DPA) is important. In this respect we would like to thank Svetla Nikova, Vincent Rijmen and Martin Schläffer for proposing a method that achieves this and Nicolas Debande and Thanh-Ha Le for helping us analyze this method. We would like to thank the members of the other SHA-3 candidate teams and the participants of the workshops that took place in the last six years for the many interesting discussions, and we thank explicitly Dan Bernstein, Alex Biryukov, Andrej Bogdanov, Christophe De Cannière, Praveen Gauravaram, Sebastiaan Indesteeghe, Nuutti Kotivuori, Marko Krause, Tanja Lange, Pierre-Yvan Liardet, Stefan Lucks, Florian Mendel, Christian Rechberger, Francesco Regazzoni, Vincent Rijmen, Tom Ristenpart, Tom Shrimpton, Yannick Teglia and Elmar Tischhauser. Our thanks also go to the partners of the Ecrypt II Network of Excellence that greatly contributed to the SHA-3 process by providing a platform for keeping track of cryptanalysis of the SHA-3 candidates on the SHA-3 Zoo and bringing researchers together in a series of workshops, retreats and summer schools. Additionally, we thank Alex Biryukov, Stefan Lucks and Frederik Armknecht for organizing the ESC and Dagstuhl seminars that likewise stimulated interaction between cryptographers, as well as all the people we forgot to mention…

Of course we also insist on thanking our colleagues at ST Zaventem, Agrate and Rousset and NXP Haasrode for supporting us, more particularly our managers Yves Moulart, Armand Linkens, Bernard Kasser, Stefan De Troch, Lars Reger and Marc Vauclair, and for kindly sponsoring several hardware platforms that we used to evaluate Keccak. A major part of the effort that went into Keccak was funded by the Agentschap voor Innovatie door Wetenschap en Technologie (IWT), so we thank them for their trust and support. And last but not least, we want to thank the NIST team for organizing the SHA-3 competition and bringing it to a successful conclusion.

But the work is not completely done yet! For Keccak to achieve security assurance, it is vital that third-party cryptanalysis continues. So we invite all young and experienced cryptanalysts to ignore our security arguments and boldly attack Keccak as if your life depended on it. You can actually make some (symbolic) money by breaking open challenges in the Keccak Crunchy Crypto Contest.

Updated implementation overview

29 May 2012

We release version 3.2 of our document Keccak implementation overview, together with an updated implementation package. The differences with version 3.1 include slice-based implementations, comments on new software platforms, the mid-range hardware core and updates on the protections against side-channel attacks.

Updated version of KeccakTools available

25 April 2012

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.

The Keccak crunchy crypto contest continues through end 2012

8 April 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.

Congratulations to the winners of the Keccak crunchy crypto contest

8 April 2012

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!

Readable C code for Keccak

27 February 2012

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.

New Keccak mid-range core hardware implementation

13 February 2012

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.

New implementation techniques, packages and documentation

5 September 2011

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.

Keccak crunchy crypto contest: first solutions received!

6 August 2011

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.

Keccak Crunchy Crypto Collision and Pre-image Contest

16 June 2011

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.

On alignment in Keccak

20 May 2011

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.

Updated VHDL package

1 February 2011

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.

Simplifying Keccak's padding rule for round 3

17 January 2011

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.

Keccak selected for the third (and final) SHA-3 round

11 December 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!

Congratulations to the winners of the fourth cryptanalysis and Hex-Hot-Ticks prizes

7 December 2010

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.

• Gerhard Hoffmann wrote an implementation of Keccak[] on a NVIDIA graphics processing unit using the Compute Unified Device Architecture (CUDA). His source code comprises a batch execution of Keccak[] and an experimental implementation of the tree hashing mode using leaf interleaving defined in Section 4.4 of the main document v2.1.
• Guillaume Sevestre implemented a tree hashing mode on top of Keccak[r=256,c=544] on a NVIDIA graphics processing unit, also using CUDA. His source code contains two variants of his tree hashing mode and a parallel stream cipher.

Congratulations to all of them!

Yet another optimized implementation package

27 November 2010

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.

New optimized implementation package

3 November 2010

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.

New pages on our website

2 November 2010

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.

An implementation in Python

21 October 2010

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.

New optimized implementation package

5 October 2010

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.

The specifications, animated!

14 September 2010

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.

Extension of the fourth cryptanalysis and Hex-Hot-Ticks prizes

8 September 2010

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.

New versions of the main document and of KeccakTools

19 June 2010

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.

Deadline extension of the fourth cryptanalysis and Hex-Hot-Ticks prizes

17 June 2010

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

Fourth cryptanalysis prize

4 March 2010

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!

Note on Keccak parameters and usage

25 February 2010

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.

Congratulations to the winners of the third Keccak cryptanalysis prize

16 February 2010

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.

Hex-Hot-Ticks Keccak prize

2 February 2010

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.

Note on zero-sum distinguishers

16 January 2010

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.

Third cryptanalysis prize deadline extension

8 December 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!

Tune Keccak to your requirements

12 November 2009

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!

Optimized implementation updated

19 October 2009

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.

Updated version of KeccakTools available

7 October 2009

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.

Third cryptanalysis prize

30 September 2009

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!

Keccak parameter changes for round 2

22 September 2009

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.

Congratulations to the winners of the second Keccak cryptanalysis prize

9 September 2009

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.

Optimized implementation updated

24 August 2009

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!

NIST chooses 14 second-round candidates

28 July 2009

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!

Second cryptanalysis prize deadline extension

3 July 2009

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!

Third-party analysis and implementation page

13 June 2009

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 plan on updating this page whenever needed.

Second cryptanalysis prize

14 May 2009

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!

Congratulations to the winners of the first Keccak cryptanalysis prize

29 April 2009

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.

Updated documentation and implementation

23 April 2009

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.

Keccak performance figures page

15 April 2009

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 plan on updating this page on a regular basis.

Keccak implementations using SIMD instructions

6 April 2009

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.

Cryptanalysis prize deadline extension

27 February 2009

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!

Cryptanalysis prize

23 January 2009

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.

Introducing KeccakTools

22 January 2009

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.

Updated documentation and implementation

13 January 2009

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.

Keccak submitted to eBASH

22 December 2008

We submitted Keccak to the ECRYPT Benchmarking of All Submitted Hashes (eBASH) project and the first results are appearing.

eBASH measures the speed of hash functions on a wide variety of machines using a tool called SUPERCOP. The software reports the number of cycles necessary to hash messages of different sizes, from 8 to 4096 bytes, and extrapolates for longer messages. It benchmarks many SHA-3 candidates, as well as older hash functions as a comparison.

The first results confirm speeds that are close to 10 cycles/byte on the reference platform defined by NIST. More precisely, 10.14 cycles/byte are reported on the machine named "cobra" (Intel Core 2 Duo E4600) using the amd64 architecture and 31.52 cycles/byte when using only 32-bit x86 instructions (long messages, median).

Keccak news feed available

11 December 2008

Welcome to the Keccak page! This page is dedicated to the cryptographic hash function family called Keccak, which we submit as a SHA-3 candidate. You can already find the complete specification and main document, software and hardware implementations, test vectors and results of the Monte-Carlo tests.

Although the Keccak specifications are frozen, we are still working on it actively to improve the analysis and implementation. We plan to publish a new version of the main document to describe the latest state of the analysis. Also, we are working on an improved software implementation, which we will publish the results soon. So please come visit us to get the latest news on Keccak, or better yet, subscribe to the news feed to receive automatically these news in your newsfeed reader.

Unless otherwise specified, the contents and files within the domain keccak.noekeon.org are © 2008-2013 Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche.

Last updated: 2013-06-03