News feed (atom)
This page is dedicated to the cryptographic sponge function family called Keccak, which has been selected by NIST to become the new SHA-3 standard.
Keccak in a nutshell
Keccak is a family of sponge functions. The sponge function is a generalization of the concept of cryptographic hash function with infinite output and can perform quasi all symmetric cryptographic functions, from hashing to pseudo-random number generation to authenticated encryption.
For a quick introduction, we propose a pseudo-code description of Keccak. The reference specification, analysis, reference and optimized code and test vectors for Keccak can be found in the file section.
As primitive used in the sponge construction, the Keccak instances call one of seven permutations named Keccak-f[b], with b=25, 50, 100, 200, 400, 800 or 1600. In the scope of the SHA-3 contest, we proposed the largest permutation, namely Keccak-f[1600], but smaller (or more “lightweight”) permutations can be used in constrained environments. Each permutation consists of the iteration of a simple round function, similar to a block cipher without a key schedule. 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.
Keccak has a very different design philosophy from its predecessor RadioGatún. This is detailed in our paper presented at Dagstuhl in 2009.
Strengths of Keccak
Flexibility
Keccak inherits the flexibility of the sponge and duplex constructions.
- As a sponge function, Keccak has arbitrary output length. This allows to simplify modes of use where dedicated constructions would be needed for fixed-output-length hash functions. It can be natively used for, e.g., hashing, full domain hashing, randomized hashing, stream encryption, MAC computation. In addition, the arbitrary output length makes it suitable for tree hashing.
- As a duplex object, Keccak can be used in clean and efficient modes as a reseedable pseudo-random bit generator and for authenticated encryption. Efficiency of duplexing comes from the absence of output transformation.
- Keccak has a simple security claim. One can target a given security strength level by means of choosing the appropriate capacity, i.e., for a given capacity c, Keccak is claimed to stand any attack up to complexity 2c/2 (unless easier generically). This is similar to the approach of security strength used in NIST's SP 800-57.
- The security claim is disentangled from the output length. There is a minimum output length as a consequence of the chosen security strength level (i.e., to avoid generic birthday attacks), but it is not the other way around, namely, it is not the output length that determines the security strength level. For an illustration with the classical security requirements of hashing (i.e., collision and (second) preimage resistance), we refer to our interactive page.
- The instances proposed for SHA-3 make use of a single permutation for all security strengths. This cuts down implementation costs compared to hash function families making use of two (or more) primitives, like the SHA-2 family. And with the same permutation, one can make performance-security trade-offs by way of choosing the suitable appropriate capacity-rate pair.
Design and security
- Keccak has a thick safety margin. In [Keccak reference, Section 5.4], we estimate that the Keccak sponge function should stand by its security claim even if the number of rounds is almost divided by two (i.e., from 24 down to 13 in the case of Keccak-f[1600]).
- Keccak was scrutinized by third-party cryptanalysis. For more details, we refer to the cryptanalysis page.
- We showed that the Keccak-f permutations have provable lower bounds on the weight of differential trails.
- The design of the permutations follows the Matryoshka principle, where the security properties of the seven permutations are linked. The cryptanalysis of the smaller permutations, starting from the “toy” Keccak-f[25], is meaningful to the larger permutations, and vice-versa. In particular, differential and linear trails in one Keccak-f instance extend to symmetric trails in larger instances.
- The sponge and duplex constructions used by Keccak are provably secure against generic attacks. This covers also the joint use of multiple Keccak instances with different rate/capacity parameters.
- Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
- From the mode down to the round function, our design choices are fairly different from those in the SHA-1 and SHA-2 hash functions or in the Advanced Encryption Standard (AES). Keccak therefore provides diversity with respect to existing standards.
Implementation
- Keccak excels in hardware performance, with speed/area trade-offs, and outperforms SHA-2 by an order of magnitude. See for instance the works of Gürkaynak et al., Gaj et al., Latif et al., Kavun et al., Kaps et al. and Jungk presented at the Third SHA-3 Candidate Conference.
- Keccak has overall good software performance. Although one could say that the SHA-3 finalists BLAKE and Skein have better software performance on PC, Keccak shines when used in a mode exploiting parallelism. On AMD™ Bulldozer™, 128-bit and 256-bit security hashing tops at 4.8 and 5.9 cycles/byte, respectively. On Intel™ Sandy Bridge™, the same functions reach 5.4 and 6.9 cycles/byte. On constrained platforms, Keccak has moderate code size and RAM consumption requirements.
- For modes involving a key, protecting the implementation against side-channel attacks is wanted. The operations used in Keccak allow for efficient countermeasures against these attacks. Against cache-timing attacks, the most efficient implementations involve no table lookups. Against power analysis attacks and variants, countermeasures can take advantage of the quadratic round function.
Latest news
24 January 2013 — The Keccak crunchy crypto contest continues through end 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.
24 October 2012 — Updated home page
We updated the home page of this site and added a picture of the Keccak Team.
3 October 2012 — NIST selects Keccak for SHA-3
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.
29 May 2012 — Updated implementation overview
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.
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.
Contact Information
Email: keccak-at-noekeon-dot-org