Started in June 2011, the Crunchy Contest proposes concrete collision and pre-images challenges based on reduced-round Keccak. After about 13 years, it is still active and the recent months have seen new challenges being solved. Hence, we would like to congratulate the authors of the latest solutions:
We congratulate Xiaoen Lin^{1}, Hongbo Yu^{1}, Zhengrong Lu^{1} and Yantian Shen^{1} for solving the 2-round pre-image challenge on Keccak[r=40, c=160].
The previous pre-image challenge on the 200-bit version was solved on 1 round by Joan Boyar and Rene Peralta in 2013. This present challenge was solved by combining linear structures and symmetries within the lanes and exploiting sparsity of the round constants.
Furthermore, we congratulate Xiaoen Lin^{1}, Hongbo Yu^{1}, Congming Wei^{2}, Le He^{3} and Chongxu Ren^{1} for solving the 4-round pre-image challenge on Keccak[r=640, c=160].
The previous pre-image challenge on the 800-bit version was solved on 3 rounds by Jian Guo and Meicheng Liu in 2017. The solution to the present challenge was made possible by a number of optimizations related to linear structures and made use of mixed-integer linear programming (MILP). The team reports a total complexity of 2^{60.9} 4-round Keccak-f calls.
Finally, we congratulate Andreas Westfeld^{4} for solving the 2-round collision challenge on Keccak[r=40, c=160].
The previous collision challenge on the 200-bit version was solved on 1 round by Roman Walch and Maria Eichlseder in September 2017. The solution to the present challenge targets the rounds 3 and 4 specifically, as it exploits the round constant that is zero for i_{r}=3 in the 200-bit version.
Looking back at 2022, we further improved the bounds of differential and linear trails in Xoodoo. In the article Tighter trail bounds for Xoodoo available on the IACR Cryptology ePrint Archive, we report on the outcome of our new trail scan effort. The importance of trail bounds is not to be repeated; instead we refer to last year's news item for a discussion. As you can see in the table below, the lower bounds have been quite significantly improved.
Next to a description of the optimizations in our trail search code that allowed us to improve the bounds, in the article we also report on a set of trails that are extendable to an arbitrary number of rounds and as such provide upper bounds for the minimum weight of trails. We summarize the new lower and upper bounds for the weight of trails in the table below. The bounds are the same for differential and linear trails.
# rounds | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 |
---|---|---|---|---|---|---|---|---|---|
Lower bounds | 2 | 8 | 36 | 80 | 98 | 132 | 176 | 220 | 264 |
Upper bounds | 2 | 8 | 36 | 80 | 120 | 168 | 288 | 440 | 624 |
Currently, the vast majority of symmetric-key cryptographic schemes are built as modes of block ciphers. What would cryptography look like if it was built around another primitive? In this note, we explain our approach to authentication, encryption and authenticated encryption using a primitive type that we call deck functions. For more details, we invite you to watch our presentation All on deck! at RWC 2020, read our paper Jammin' on the deck or see its presentation at Asiacrypt 2022.
A deck function stands for doubly extendable keyed cryptographic function. It is not a construction like sponge or farfalle; instead, a deck function is a primitive type, the same concept as a block cipher. A primitive type abstractly defines a functional and security interface to modes, where the latter can be specified and proven secure independent of the details of the underlying primitive.
In a nutshell, a deck function is a function that, when keyed with a secret key, is hard to distinguish from a random oracle. Instead, a block cipher is a function that, when keyed with a secret key, is hard to distinguish from a random permutation. While the latter is called (S)PRP security, the security concept for a deck function is called PRF security, i.e., taking a key and a string as input, it outputs seemingly random bits for an adversary who does not know the key.
Yet, to qualify as a deck function, it must satisfy some additional requirements. First, the data input takes the form of a sequence of binary strings instead of a single one, and the output depends on the sequence and not just the concatenation of input strings. Then, a deck function must implement efficient incrementality properties. Specifically, both the input and the output are extendable: By keeping state, appending an extra string to the input sequence costs only the processing of this extra string. Similarly, like an extendable output function (XOF), asking for more output bits should be efficient.
A construction for building deck functions is farfalle, of which Kravatte and Xoofff are instances.
However, there is nothing that prevents from building deck function differently, in the same way that there are multiple ways to build a block cipher: A wide design space is waiting to be explored!
Like for block ciphers, we can define deck function modes of use for authentication, encryption and various kinds of authenticated encryption (AE). For instance, in our paper, we describe five modes with different robustness properties. Four of these modes are variations around a Feistel network structure, with a consistent and unified approach. This Feistel network has two mandatory central rounds and two optional outer rounds. The central rounds provide AE with nonce-misuse robustness, while the optional round at the beginning reduces the ciphertext expansion and the optional round at the end adds resistance against release of unverified plaintext (RUP).
Building AE schemes with such properties is not new and can be done based on block ciphers, but in the case of deck functions, the modes become really simple and natural. Passing a sequence of input strings and supporting incremental inputs are key ingredients in this simplicity, see for instance Seth's article on modes and his recent paper Nonce-encrypting AEAD Modes with Farfalle.
It is true that with deck functions we move the burden of dealing with variable input and output lengths from the mode to the primitive. It turns out that this allows more efficient schemes. Traditionally, block cipher-based modes rely on their (S)PRP security, and achieving a solid level of (S)PRP security comes at the price of a relatively large number of rounds. On the other hand, building a variable-input-length function that targets PRF security using the same building blocks can be done more efficiently when the reductionist security argument is dropped. Think about how much faster Pelican-MAC is compared to AES-CMAC: The former needs 4 rounds per 128 bits of input when the latter needs 10!
Their incrementality properties are particularly well suited for uses of AE that go beyond the encryption and/or authentication of individual messages. In particular, processing streams of data, with intermediate tags, and bi-directional communications benefit from simpler modes.
In this context, a session deals with the authentication of sequences of messages, preventing an attacker from reshuffling messages. Ensuring that a message is authenticated in the context of previously sent messages comes essentially for free thanks to the incrementality properties of deck functions. Another interesting use case is the transmission of long messages to low-end devices, where intermediate tags can authenticate the message in an incremental way.
It depends on what you want to do.
If you are implementing a new protocol, note that Kravatte and Xoofff are supported in the XKCP and in a few other places. Currently, Xoofff has our preference because of its efficiency on a wide range of platforms, from the low-end processors as used in embedded devices to the high-end server processors. On the ARM™ Cortex-M0 and -M3, Xoofff outperforms AES-based schemes by a factor 4 or 5, and with AVX-512 instructions it runs faster than AES-based schemes even with the dedicated AES instructions!
If you are interested in modes and in proving their security, you may want to adapt existing modes with interesting properties to deck functions and see if the deck function interface makes them simpler. If you are a cryptographic designer, maybe your favorite design approach can be applied to build a deck function. And if you are interested in cryptanalysis, you may want to have a critical look at farfalle, our schemes and possibly new deck functions.
The possibilities are endless!
Making sure that our primitives are not susceptible to differential or linear cryptanalysis has been a constant target for us. In this scope, differential and linear trails specify how differences or linear masks propagate through the rounds, so we want to ensure that the only trails that exist are those that are too costly to exploit. Concretely, we are looking for lower bounds on the weight of trails, for a given number of rounds. The higher the weight, the greater the data and/or computation complexity of attacks based on them, so simply put, if no trail of low weight exist, then we are safe.
Bounds on trails do not give guarantees of security, but they can help determine the resistance against some specific attacks. For instance, in the Farfalle construction (used by Xoofff and Kravatte), the expected data complexity to generate internal collisions is directly linked to bounds on the weight of differential trails, see Section 6.3.2 of [Daemen et al., The design of Xoodoo and Xoofff, ToSC 2018].
Bounds on trails do not give guarantees of security as differential and linear attacks are broader than just exploiting trails. For instance, a differential over several rounds (i.e., specifying only the input and output differences) can span many differential trails (i.e., take many different internal differences); this effect is called clustering. Nevertheless, the design strategy of Xoodoo, similar to that of Keccak, is unaligned, and this helps reduce clustering. We studied this and other effects in our recent paper [Bordes et al., Thinking Outside the Superbox, CRYPTO 2021].
Proving lower bounds on trails in unaligned primitives requires the computer-aided exploration of all possible trails. The publication of Xoodoo came with our initial bounds, and we further improved them and reported them in the documentation of Xoodyak. Recently, we revived this effort and further extended our complete search for all 3-round trails up to weight 52 (instead of 50), allowing us to prove that a 6-round trail has weight at least 108 (instead of 104). This is the case for both differential and linear trails.
The completeness of the search for all 3-round trails is now confirmed up to weight 50 thanks to an independent search effort based on SAT solvers, XoodooSat, implemented by Huina Li and Weidong Qiu of Shanghai Jiao Tong University. Actually, they reported to us that two trails of weight 48 were missing, and this was caused by a bug in our program XooTools. After fixing it, we could confirm that XooTools and XoodooSat had produced exactly the same set of trails, independently!
To conclude, we summarize our current trail bounds in Xoodoo in the following table.
# rounds | 1 | 2 | 3 | 4 | 5 | 6 | 8 | 10 | 12 |
---|---|---|---|---|---|---|---|---|---|
Differential trails | 2 | 8 | 36 | 74 | 94 | 108 | 148 | 188 | 222 |
Linear trails | 2 | 8 | 36 | 74 | 94 | 108 | 148 | 188 | 222 |
We often receive questions as to whether Deck-SANSE can be used in a stateless way; that is, for a single message. A common use case for this is a UDP-based VPN. In such an application, sessions are not feasible due to the lossy/unordered nature of UDP. Thanks to its versatility, Deck-SANSE can be used in such applications with virtually no overhead. Deck-SANSE provides the following features:
Deck-SANSE wrap function, taking associated data A and plaintext P, and returning ciphertext C and tag T:
if |A| > 0 and |P| > 0 then T ← 0^t + F(P||010 ∘ A||00) C ← P + F(T||110 ∘ A||00) else if |P| > 0 then T ← 0^t + F(P||010) C ← P + F(T||110) else T ← 0^t + F(A||00) return (C,T)
We released the specifications of two authenticated encryption schemes built on top of Kravatte, namely Kravatte-SANE and Kravatte-SANSE, replacing Kravatte-SAE and Kravatte-SIV, respectively.
The Kravatte-SANE and Kravatte-SANSE schemes both support sessions. Often, one does not only want to protect a single message, but rather a session where multiple messages are exchanged, such as in the Transport Layer Security (TLS) or the Secure Shell (SSH) protocols. Each tag authenticates all messages already sent so far in the session. Examples of session-supporting authenticated encryption schemes include Ketje and Keyak.
The SANE and SANSE variants differ in their robustness with respect to nonce misuse. The former relies on user-provided nonces (one per session) for confidentiality, while the latter is more robust against nonce misuse and realizes this by using the SIV mechanism. Note that we also specify a tweakable block cipher on top of Kravatte in the original article on Farfalle.
Kravatte-SANE and Kravatte-SANSE fix and obsolete Kravatte-SAE and Kravatte-SIV, respectively. Ted Krovetz pointed out a flaw in the Farfalle-SIV mode and we subsequently found one in Farfalle-SAE. The flaw in Farfalle-SAE is related to sequences of messages with empty plaintexts and/or metadata, while that of Farfalle-SIV follows from the lack of separation between the tag and the keystream generation. (More details can be found in the Xoodoo cookbook, Sections 4.1 and 5.1.)
The performance of the new schemes is identical to that of their obsoleted counterparts. Thanks to the high level of parallelism of Kravatte, the SANE and SANSE schemes have excellent software speeds. Optimized code can be found in the extended Keccak code package.
At the rump session of FSE 2018 that took place last week in Brugge, Belgium, we announced the outcome of the Ketje cryptanalysis prize.
There were three submissions:
The first two submissions push the boundaries of cube attacks, or more generally, higher-order differential cryptanalysis of round-reduced Keccak-f. In Ketje, these attacks always target the initialization phase that applies Keccak-p[n_{r}=12] to the concatenation of a key and a nonce. The algebraic degree of Keccak-p[n_{r}], for a small number of rounds, is d=2^{nr}, so a straightforward higher-order differential attack would require a data complexity of 2^{d} chosen input blocks (e.g., for n_{r}=6 rounds, the degree is d=64 and the straightforward data complexity is 2^{64}). By applying some sophisticated tricks, one can peel off one or two rounds resulting in much lower data complexities. The first two submissions achieve this by exploiting specific propagation properties of the round function.
The third submission is the first to attack the encryption/decryption phase of Ketje Jr. In this phase, a known-plaintext attacker gets the value of the first r=16 bits of the state for every round of Keccak-f. Information-theoretically n=200/16=12.5 such blocks would be sufficient to break Ketje by state recovery, but the computational difficulty increases quickly with n. This submission investigates weakened versions of Ketje Jr with increased rates: r=32 and r=40 bits and break the security claim. The attacks confirm that the tweak between Ketje v1 and Ketje v2 results in an increase in safety margin.
These three attacks add to the already substantial amount of cryptanalysis of the Keccak-f permutation in a keyed setting. They enforce the positions of Ketje (and Keyak) as being among the most cryptanalyzed authenticated ciphers.
Given these nice results, we decided to award all three submissions. For practical reasons, the contestants of the first two entries got Belgian chocolates, while those of the latter received Belgian beer.
Everyone's a winner in this contest. Congratulations to all!
We are glad to announce the final version of the Farfalle construction and of the Kravatte pseudo-random function and encryption schemes.
First published in late 2016 on IACR ePrint, an update of our paper Farfalle: parallel permutation-based cryptography was accepted at the journal Transactions on Symmetric Cryptography (ToSC). We will present it at the yearly Fast Software Encryption (FSE) conference in Brugge, Belgium, in March 2018.
In the last couple of months, we applied some changes to both Farfalle and Kravatte^{1}. This was due to prompt third-party cryptanalysis by different researchers. First Ling Song and Jian Guo contacted us with a key recovery cube attack on the (full) previous version of Kravatte. Then a second team of cryptanalysts (who wish to stay anonymous at this point, as their paper is under submission) sent us the description of even more powerful attacks targeting the expansion layer specifically. Consequently, we modified Kravatte by taking 6 rounds for all four permutation instances. And to counteract the attacks of the second team, we made a more fundamental change by adopting a non-linear rolling function in the expansion layer. We realize that switching from a linear rolling function to a non-linear one is a change in philosophy, and we discuss it in the paper.
The optimized code in the KCP and the reference implementation in KeccakTools are in sync.
^{1}To distinguish the latest version of Kravatte from the previous one, we call it Kravatte Achouffe.
If SHA-2 is not broken, why would one switch to SHA-3 and not just stay with SHA-2? In this post, we highlight another argument why Keccak/SHA-3 is a better choice than SHA-2, namely openness, in analogy with open-source versus closed-source in software development and deployment.
Software has two sides: its executable and its source code. The former is used as a black box by the users, while the latter is of interest to developers who want to extend it, to understand its inner workings or to make sure there is no obvious malicious code. As an analogy, we see the specification of the cryptographic primitive, mode or algorithm in a (proposed) cryptographic standard as the counterpart of the software executable: It allows everyone to include the cryptographic object, as is, in his/her project. The counterpart of the source code in cryptography would be the design rationale, preliminary cryptanalysis and evidence of extensive third-party cryptanalysis: These are the elements that give insight into the inner workings and ultimately trust.
The transition of cryptography from a proprietary activity to a scientific one in the last 50 years can be seen as a move from closed-source to open-source in this analogy. Surprisingly, there are exceptions and we still see closed-source cryptography today.
The SHA-1 and SHA-2 NIST standard hash functions were designed behind closed doors at NSA. The standards were put forward in 1995 and 2001 respectively, without public scrutiny of any significance, despite the fact that at time of publication there was already a considerable cryptographic community doing active research on this subject. Even the 2015 update of FIPS 180, the standard that specifies SHA-2, does not contain, nor refer to, a design rationale.
In contrast, SHA-3 is the result of an open call of NIST to the cryptographic community for hash function proposals. There was no restriction on who could participate, so submissions were open in the broadest possible sense. Every submitted candidate algorithm had to contain a description, a design rationale and preliminary cryptanalysis. The authors of the 64 submissions included the majority of people active in open symmetric crypto research at the time. NIST solicited the symmetric crypto community for performing and publishing research in cryptanalysis, implementations, proofs and comparisons of the candidates and based its decision on the results. After a three-round process involving hundreds of people in the community for several years, NIST finally announced that Keccak was selected to become the SHA-3 standard.
The open effort of the symmetric crypto community did not stop there. Since then, Keccak has remained under public scrutiny and new papers appear regularly. Paper after paper confirms the large safety margin of Keccak. What is important, is that these papers reach a high degree of sophistication as research can start from the preliminary cryptanalysis that we provided in our SHA-3 submission document.
It is true that cryptanalysis of MD5, SHA-1 and SHA-2 has also reached a high degree of sophistication. However, this took longer to develop due to the absence of rationale and preliminary cryptanalysis, but also due to the adoption of the ARX design methodology.
SHA-2 is essentially a security patch of SHA-1 while SHA-3 is its open-source alternative, much in the same way that Triple-DES is a security patch for DES and AES the open-source alternative. In retrospect, even if Triple-DES is not broken, would you still recommend not to switch to AES?
If SHA-2 is not broken, why would one switch to SHA-3 and not just stay with SHA-2? There are several arguments why Keccak/SHA-3 is a better choice than SHA-2. In this post, we come back on a particular design choice of Keccak and explain why Keccak is not ARX, unlike SHA-2.
We specified Keccak at the bit-level using only transpositions, bit-level additions and multiplications (in GF(2)). We arranged these operations to allow efficient software implementations using fixed sequences of bitwise Boolean instructions and (cyclic) shifts. In contrast, many designers specify their primitives directly in pseudocode similarly including bitwise Boolean instructions and (cyclic) shifts, but on top of that also additions. These additions are modulo 2^{n} with n a popular CPU word length such as 8, 32 or 64. Such primitives are dubbed ARX that stands for “addition, rotation and exclusive-or (XOR)”. The ARX approach is widespread and adopted by popular designs MD4, MD5, SHA-1, SHA-2, Salsa, ChaCha, Blake(2) and Skein.
So why isn't Keccak following the ARX road? We give some arguments in the following paragraphs.
One of the main selling points of ARX is its efficiency in software: Addition, rotation and XOR usually only take a single CPU cycle. For addition, this is not trivial because the carry bits may need to propagate from the least to the most significant bit of a word. Processor vendors have gone through huge efforts to make additions fast, and ARX primitives take advantage of this in a smart way. When trying to speed up ARX primitives by using dedicated hardware, not so much can be gained, unlike in bit-oriented primitives as Keccak. Furthermore, the designer of an adder must choose between complexity (area, consumption) or gate delay (latency): It is either compact or fast, but not at the same time. A bitwise Boolean XOR (or AND, OR, NOT) does not have this trade-off: It simply take a single XOR per bit and has a gate delay of a single binary XOR (or AND, OR, NOT) circuit. So the inherent computational cost of additions is a factor 3 to 5 higher than that of bitwise Boolean operations.
But even software ARX gets into trouble when protection against power or electromagnetic analysis is a threat. Effective protection at primitive level requires masking, namely, where each sensitive variable is represented as the sum of two (or more) shares and where the operations are performed on the shares separately. For bitwise Boolean operations and (cyclic) shifts, this sum must be understood bitwise (XOR), and for addition the sum must be modulo 2^{n}. The trouble is that ARX primitives require many computationally intensive conversions between the two types of masking.
The cryptographic strength of ARX comes from the fact that addition is not associative with rotation or XOR. However, it is very hard to estimate the security of such primitives. We give some examples to illustrate this. For MD5, it took almost 15 years to be broken while the collision attacks that have finally been found can be mounted almost by hand. For SHA-1, it took 10 years to convert the theoretical attacks of around 2006 into a real collision. More recently, at the FSE 2017 conference in Tokyo, some attacks on Salsa and ChaCha were presented, which in retrospect look trivial but that remained undiscovered for many years.
Nowadays, when a new cryptographic primitive is published, one expects arguments on why it would provide resistance against differential and linear cryptanalysis. Evaluating this resistance implies investigating propagation of difference patterns and linear masks through the round function. In ARX designs, the mere description of such difference propagation is complicated, and the study of linear mask propagation has only barely started, more than 25 years after the publication of MD5.
A probable reason for this is that (crypt)analyzing ARX, despite its merits, is relatively unrewarding in terms of scientific publications: It does not lend itself to a clean mathematical description and usually amounts to hard and ad-hoc programming work. A substantial part of the cryptographic community is therefore reluctant to spend their time trying to cryptanalyze ARX designs. We feel that the cryptanalysis of more structured designs such as Rijndael/AES or Keccak/SHA-3 leads to publications that provide more insight.
But if ARX is really so bad, why are there so many primitives from prominent cryptographers using it? Actually, the most recent hash function in Ronald L. Rivest's MD series, the SHA-3 candidate MD6, made use of only bitwise Boolean instructions and shifts. More recently, a large team including Salsa and ChaCha designer Daniel J. Bernstein published the non-ARX permutation Gimli. Gimli in turn refers to NORX for its design approach, a CAESAR candidate proposed by a team including Jean-Philippe Aumasson and whose name stems from a rather explicit “NO(T A)RX”. Actually, they are moving in the direction where Keccak and its predecessors (e.g., RadioGatún, Noekeon, BaseKing) always were.
So, maybe better skip ARX?
We congratulate Yao Sun^{1} and Ting Li^{1} for solving the 3-round pre-image challenge on Keccak[r=240, c=160].
The previous pre-image challenge on the 400-bit version was solved on 2 rounds by Paweł Morawiecki in 2011. This present challenge was solved by combining brute-force and algebraic techniques. It took 5 days with eight GPU cards (nvidia 1080Ti).
We are happy to announce that we moved the contents from {keccak, sponge, ketje, keyak}.noekeon.org
to our new domain keccak.team
. Many thanks to Benoit Viguier for designing the engine behind these new pages!
We hope that you will enjoy the refreshed look. Do not hesitate to contact us if you see something incorrect or missing.
In a recent post, Adam Langley complains that “SHA-3 is slow”. Similar comments appear from time to time on the web (see also David Wong's post). But what does it mean precisely? Let us dig into it.
There are a couple of ambiguities in this statement. Let's start with the first one: where would it be “slow”?
Keccak, the winner of the SHA-3 competition, is blazing fast when implemented on dedicated (ASIC) or programmable (FPGA) hardware. Its throughput for a given circuit area is an order of magnitude higher than SHA-2 or any of the SHA-3 finalists. And if you care beyond plain speed, note that it also consumes much less energy per bit. In this sense, Keccak is a green cryptographic primitive.
Keccak has other implementation advantages, like efficient protections against side-channel attacks, but let's go to the point: what seems to be at stake is the speed in software.
How come then, that SHA3-512 is slower than SHA-512 on modern processors? This brings up to the second ambiguity of the statement: what is “SHA-3”?
“SHA-3” initially refers to the target of the competition that NIST organized from 2008 to 2012, namely a new hash standard that would complement SHA-2 in case it is broken. Hence, the initially-intended outcome of the competition is a set of four functions called SHA3-224, SHA3-256, SHA3-384, and SHA3-512.
If “SHA-3” means these four functions, then indeed SHA3-512 is unnecessarily slowed down by an excessive security parameter. Due to an absurd rule in the competition, followed by a fierce controversy in 2013, the parameters of SHA3-512 are stuck at offering 512 bits of pre-image security, a nonsense for anyone who can compute powers of two.
It turned out that Keccak has more to offer than just the drop-in replacements for SHA-{224, 256, 384, 512}. In FIPS 202 (“the SHA-3 standard”), NIST also approves two extendable-output functions (XOFs) called SHAKE128 and SHAKE256. These generalize the traditional hashing paradigm by allowing any arbitrary output length and by being parameterized by their security strength, instead of their output length.
If the term “SHA-3” embraces the aforementioned XOFs, then SHAKE{128, 256} are on par with SHA-2 on common processors. But could “SHA-3” actually be super fast in software?
To answer this last question, let us go further down the standardization road. Recently, NIST released the SP 800-185 standard (“SHA-3 derived functions”), which proposes a framework for customizable functions, called cSHAKE, that generalize SHAKE{128, 256}. And, as an application of this framework, it approves the ParallelHash functions. These functions internally use a parallel mode of operation, which an implementation can exploit to speed-up the processing.
With these standard functions included, “SHA-3” can actually outperform SHA-2 and even SHA-1 (broken but usually considered fast) for long messages on modern processors.
Of course, a cryptographic functions should carefully balance speed and security. Keccak makes use of sound design properties, like fast linear and differential propagation or purposely weak alignment, and it clearly stays away from the ARX (modular additions, rotations and exclusive or's) approach. What we understand of Keccak now made us wonder: aren't 24 rounds too much?
KangarooTwelve is a recently proposed variant of Keccak, in which the number of rounds has been reduced to 12—yet, with exactly the same round function, no tweak! It may seem like a drastic reduction, but it is in line with our proposed solution for authenticated encryption, Keyak, submitted to the CAESAR competition. And, more importantly, this wouldn't have been possible if Keccak hadn't had the chance of getting such a rather extensive scrutiny from cryptanalysis experts throughout the years—and to resist to them.
KangarooTwelve is defined on the “SHA-3” components from FIPS 202 and may please the aficionados of extreme software speed. But beware: with such speeds, the hard drive or the network connection has long become the bottleneck for most applications.
In a joint work with Silvia Mella (STMicroelectronics and University of Milano), we propose a framework for bounding the weight of differential trails. We apply this on Keccak-f with widths of 200, 400, 800 and 1600 bits to show that no trail of weight less than 92 over 6 rounds exist in either of these Keccak-f instances. Should a 6-round differential trail be used as part of a collision attack, the ratio of complying pairs is thus guaranteed to be at most 2^{-92}.
This work improves over our results of FSE 2012, both extending the coverage of differential trails both over the different Keccak-f widths and over a higher weight per round. In particular, Silvia was able to scan all 3-round trails up to weight 45. At 15 per round, and given the exponential growth of trail number per weight, this is a significant improvement over previous works.
Silvia presented her work at FSE 2017. The paper can be found here.
We are happy to announce a new cryptanalysis prize! The subject of the stress-test is the authenticated encryption scheme Ketje.
We are particularly interested in attacks aiming at recovering the internal state, the secret key or at forging a MAC. Other attacks would be appreciated as well. Competitors have the freedom to increase the input rate of Ketje. The attack can be applied to any of the four instances of Ketje.
Who wins the prize will be decided by consensus in the Keccak team. Some hints:
The Ketje authenticated encryption scheme has already established such a solid reputation in Belgium that a beer was named after it. Unfortunately, it is already sold out since 2011. Instead, the winner will receive a selection of Belgian beers.
The attacks should be submitted to the crypto-competitions
-at- googlegroups.com
mailing list (with ketje
-at- noekeon.org
in CC) before January 31st, 2018.
We congratulate Ling Song^{1,2,3}, Guohong Liao^{4,1} and Jian Guo^{1} for solving the 6-round collision challenge on Keccak[r=1440, c=160].
The collision search took a computational effort of about 2^{50} evaluations of the Keccak-f rounds. It follows an improvement of the technique previously used for solving the 5-round collision challenge in May last year (then solved by Jian Guo, Meicheng Liu, Ling Song and Kexin Qiao).
NIST released the SP 800-185 standard with useful new functions based on Keccak: cSHAKE, KMAC, TupleHash and ParallelHash.
Yesterday, NIST published the SP 800-185 standard [PDF]. It contains the following new functions based on Keccak:
TupleHash("a", "b", "c")
, TupleHash("a", "bc")
, TupleHash("abc")
and TupleHash("abc", "")
all give unrelated outputs.These new functions all support the 128-bit and 256-bit security strengths. They all consistently support domain separation through the user-chosen customization string input. And they all support variable ouput length in a natural way.
We congratulate Meicheng Liu^{1} and Jian Guo^{2} for being the first ones to solve a 4-round pre-image challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!
They found a pre-image of a given 80-bit digest for Keccak[r=1440, c=160] reduced to its first 4 rounds. Up to now, only pre-image challenges up to 3 rounds had been solved.
Ketje and Keyak are authenticated encryption schemes based on Keccak-p. Both were accepted in round 3 of the CAESAR competition. We slightly modified Ketje (now v2) in a way that encourages cryptanalysis, while we kept Keyak unchanged (still v2) but updated and improved its documentation.
Compared to Ketje v1, we now specify a different placement for the outer (input/output) part of the state. This is done by adding a change of coordinates (“twist”), so as to put the outer part on a diagonal and to limit its interaction with the preceding χ and following θ step mappings.
The motivation is to encourage cryptanalysis. Cryptanalysis usually starts by reducing the number of rounds to see at which point a given primitive becomes insecure. In the case of Ketje, one cannot decrease the step calls further than 1 round. Instead, a cryptanalyst can increase the rate to more than 2 lanes to determine at which point Ketje breaks. However, the lanes of the outer part are located in the same plane (i.e., same y coordinate) and contain the result of χ. The knowledge of too many lanes in the same plane could mean that χ is easily inverted on that part of the state. Also, we should not place the outer part on a sheet (i.e., same x coordinate) as this would help the adversary influence the parity computed in θ. Instead, the twist places the outer part on a diagonal.
We illustrate the usage of this twist with two new instances, Ketje Minor and Ketje Major, that have a rate of 4 lanes (instead of 2) and larger permutations (800 and 1600 bits).
The primary recommendation remains Ketje Sr. Both Ketje Jr and Ketje Sr keep their rate of 2 lanes and otherwise remain unchanged modulo the twist.
Compared to round 2, River, Lake, Sea, Ocean and Lunar Keyak remain unchanged.
We nevertheless worked on improving the description of the Motorist mode of operation by simplifying the definition of the Piston, Engine and Motorist algorithms. We also updated the security rationale. These changes are available in version 2.2 of the documentation (see change log in Appendix A).
The definition of Motorist now restricts the tag length to the capacity. As pointed out by Seth Hoffert, a legitimate adversary could, in a session, submit a tag as next block of metadata. If the tag is as long as the rate, this allows the adversary to force the outer part to a constant value, hence increasing the multiplicity. This would not break Motorist but it would prevent it to reach near-capacity generic security.
We propose a fast and secure arbitrary output-length hash function aiming at a higher speed than the FIPS 202's SHA-3 and SHAKE functions, while retaining their flexibility and basis of security. Furthermore, it can exploit a high degree of parallelism, whether using multiple cores or the single-instruction multiple-data (SIMD) instruction set of modern processors. On Intel's® Haswell and Skylake architectures, KangarooTwelve tops at less than 1.5 cycles/byte for long messages on a single core. Short messages also benefit from about a factor two speed-up compared to the fastest FIPS 202 instance SHAKE128.
We congratulate Jian Guo^{1}, Meicheng Liu^{1,2}, Ling Song^{1,2,3} and Kexin Qiao^{2,3,1,4} for solving another 5-round collision challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!
They generated a collision for a Keccak variant with capacity 160 bits, calling the Keccak-f permutation with width 800 and 5 rounds.
This solution happens less than two months after their team published the solution for the 5-round collision challenge with width 1600. We are looking forward to seeing the details of this attack, how much it differs from their previous one and whether their method can be adapted for the two remaining collision challenges in the 5-round category.
We congratulate Jian Guo^{1}, Meicheng Liu^{1,2}, Ling Song^{1,2,3} and Kexin Qiao^{2,3,1,4} for being the first ones to solve a 5-round collision challenge in the Keccak Crunchy Crypto Collision and Pre-image Contest!
They generated a collision for a Keccak variant with capacity 160 bits, calling the Keccak-f permutation with width 1600 and 5 rounds.
Remarkably, this breakthrough came only one month after two members of the same team, Jian and Meicheng, generated the first 3-round pre-images in our contest. [More details…]
When implemented on ASICs or on FPGAs, Keccak is significantly more efficient than other primitives with a similar security level, and allows efficient protections against side-channel attacks. Another area where Keccak's performance shines is on processors that exploit parallelism.
Recently, the NIST posted on the hash forum two draft special publications SP 800-XXX including proposals for customized SHAKE instances (Cshake), pseudo-random functions (KMAC), hash functions taking multiple strings as input (TupleHash) and a parallelized hash mode (Fast Parallel Hash, or FPH).
We implemented FPH in the Keccak Code Package and measured the following speeds for long messages:
Haswell | Skylake | |
---|---|---|
Keccak-FPH128 | 2.73 | 2.31 |
Keccak-FPH256 | 3.41 | 2.88 |
Keccak-FPH beats the speed line drawn by the legacy algorithms MD5 and SHA-1, usually considered fast.
Our implementation exploits the AVX-2 256-bit SIMD instruction set.
We congratulate Jian Guo (Nanyang Technological University, Singapore) and Meicheng Liu (Nanyang Technological University, Singapore and State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China) for solving two 3-round pre-image challenges in the Keccak Crunchy Crypto Collision and Pre-image Contest!
Jian and Meicheng solved the 3-round pre-image challenges for widths 800 and 1600. There remains two others, i.e., those for widths 200 and 400, plus of course all the challenges with more rounds!!! [More details…]
The Keccak Code Package (or KCP) contains different free and open-source implementations of Keccak and closely related variants such as Ketje and Keyak.
We reorganized it to make it easier to use and to develop in or on it. More specifically, the main changes are the following.
libkeccak.a
.To sum up, the KCP contains:
Very compact (or tweetable) implementations of Keccak, written by D. J. Bernstein, Peter Schwabe and Gilles, are now available. In their most compact form, the 6 instances of SHA-3 and SHAKE can fit in just 9 tweets.
We published a series of compact implementations, from the more readable one to the most compact one.
Dan presented the tweetable implementation at the rump session of Crypto 2015 [slides].
NIST officially released the FIPS 202 standard. Although it represents the target of the SHA-3 competition for a fresh hash function, the new standard provides more than just a successor to SHA-2: It comes as a toolbox with all the necessary ingredients for defining other uses of Keccak. About 2.5 years after the SHA-3 competition concluded, we recap on what the FIPS 202 standard contains.
The purpose of the FIPS 202 standard is twofold: It gives all the definitions needed to specify Keccak-based functions and it approves the use of six specific instances. The document is written bottom-up, starting with the bit-level operations in the Keccak-p permutations, a generalization of the Keccak-f permutations with a parameterized number of rounds, then moving to the sponge construction and, building on it, the Keccak family of sponge functions, and finally specifying the approved instances:
Extendable ouput functions
The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash functions where the output length is not fixed but is potentially infinite. Concretely, XOFs can be used instead of complex constructions involving hash functions and counters such as MGF1. With RSA, this is of immediate benefit to full domain hashing, to RSA OAEP (Optimal Asymmetric Encryption Padding) and to RSA PSS (Probabilistic Signature Scheme). Other use cases are key derivation functions and stream ciphers.
Another important conceptual difference is that a XOF's security strength can be chosen (e.g., through Keccak's capacity value) and is not bound to its output length, as is traditionally the case for hash functions. This flexibility allows for better security-performance trade-offs. For instance, with a key derivation function, the length of the derived key material can greatly vary from one application to another, in a way that is in general not related to the required security strength.
Future plans
NIST expressed their intention to approve other modes of use of Keccak (or potentially other functions based on the Keccak-p permutations) as they are developed, by way of special publications in the NIST SP 800-XX series and referring to FIPS 202. At the SHA-3 2014 Workshop, NIST presented more details on the following topics:
Code package
The latest version of the Keccak Code Package is in line with the standard and contains test vectors for the six aforementioned instances.
We are happy to announce that from today the Keccak Crunchy Crypto Collision and Pre-image Contest re-opens without limit of time.
There are two minor changes.
We refer to Keccak Crunchy Crypto Collision and Pre-image Contest for more details.
Recently, Itai Dinur, Paweł Morawiecki, Josef Pieprzyk, Marian Srebrny and Michał Straus published new attacks on keyed instances of Keccak, i.e., when it is used as a stream cipher or to compute a message authentication code (MAC). The attacks are cube attacks that exploit the low algebraic degree of a primitive and have a data complexity of the order of 2^{n} if this degree is n. Since the round function has algebraic degree 2, the attacks can be applied on 5 or 6 rounds of Keccak-f with a practical complexity.
These attacks are the first ones with practical complexity to reach 6 rounds. Looking at more theoretical complexities, these attacks can most probably reach a few more rounds.
Last Friday, NIST released the draft of the FIPS 202 standard. It proposes six instances: the four SHA-2 drop-in replacements with fixed output length SHA3-224 to SHA3-512, and the two future-oriented extendable-output functions SHAKE128 and SHAKE256.
The latest version of the Keccak Code Package is in line with the draft and contains test vectors for the six aforementioned instances.
Recently, we decided to move KeccakTools to GitHub. This allows easier updates as well as an easier integration of potential contributions from others.
As a reminder, KeccakTools is a set of documented C++ classes that can help analyze Keccak. It also contains the best differential and linear trails we found in the various Keccak-f instances.
SUMMARY: NIST's current proposal for SHA-3 is a subset of the Keccak family, and one can generate test vectors for that proposal using our reference code submitted to the contest.
In the end, it will be NIST's decision on what exactly will be standardized for SHA-3, but we would like, as the Keccak team, to take the opportunity to remind some facts about Keccak and give some opinion on the future SHA-3 standard.
NIST's current proposal for SHA-3, namely the one presented by John Kelsey at CHES 2013 in August, is a subset of the Keccak family. More concretely, one can generate the test vectors for that proposal using the Keccak reference code (version 3.0 and later, January 2011). This alone shows that the proposal cannot contain internal changes to the algorithm.
We did not suggest NIST to make any change to the Keccak components, namely the Keccak-f permutations, the sponge construction and the multi-rate padding, and we are not aware of any plans that NIST would do so. However, the future standard will not include the entire Keccak family but will select only specific instances of Keccak (i.e., with specific capacities), similarly to the block and key lengths of AES being a subset of those of Rijndael. Moreover, it will append some parameter-dependent suffix to the input prior to processing (see below) and fix the output length (for the SHA-2 drop-in replacements) or keep it variable (for the SHAKEs).
Here are further comments on these choices.
In Sakura, we propose to append some suffix to the input message, before applying Keccak. This is sometimes presented as a change in Keccak's padding rule because adding such a suffix can be implemented together with the padding, but technically this is still on top of the original multi-rate padding.
The suffixes serve two purposes. The first is domain separation between the different SHA-3 instances, to make them behave as independent functions (even if they share the same capacity). The second is to accomodate tree hashing in the future in such a way that domain separation is preserved.
The security is not reduced by adding these suffixes, as this is only restricting the input space compared to the original Keccak. If there is no security problem on Keccak(M), there is no security problem on Keccak(M|suffix), as the latter is included in the former.
Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing, keystream generation and any protocol making use of a mask generating function. In its current proposal, NIST plans on standardizing two instances: SHAKE256 and SHAKE512, with capacity c=256 and c=512 and therefore security strength levels of 128 and 256 bits, respectively.
The traditional fixed output-length instances acting as SHA-2 drop-in replacement (SHA3-xxx) are obtained from truncating Keccak instances at the given output length.
The capacity of the SHAKEs is given above and we now focus on the SHA-2 drop-in replacement instances with fixed output length n, with n in {224, 256, 384, 512}.
The SHA-3 requirements asked for a spectrum of resistance levels depending on the attack: n/2 for collision, n for first pre-image and n-k for second pre-image (with 2^{k} the length of the first message). To meet the requirements and avoid being disqualified, we set c=2n so as to match the n-bit pre-image resistance level, and the requirements on other attacks followed automatically as they were lower. However, setting c=2n is also a waste of resources. For instance, Keccak[c=2n] before truncation provides n-bit collision resistance (in fact n-bit resistance against everything), but after truncation to n bits of output it drops to n/2-bit collision resistance.
Instead, adjusting the capacity to meet the security strength levels of [NIST SP 800-57] gives better security-performance trade-offs. In this approach, one aims at building a protocol or a system with one consistent security target, i.e., where components are chosen with matching security strength levels. The security strength level is defined by the resistance to the strongest possible attack, i.e., (internal) collisions so that, e.g., SHA-256 is at 128 bits for digital signatures and hash-only applications. Hence, setting c=n simply puts SHA3-n at the n/2-bit security level.
Among the Keccak family, NIST decided to propose instances with capacities of c=256 for n=224 or 256, and c=512 bits for n=384 or 512. This proposal is the result of discussions between the NIST hash team and us, when we visited them in February and afterwards via mail. It was then publically presented by John Kelsey at CT-RSA later in February and posted on the NIST hash-forum mailing list soon after. It was then presented at several occasions, including Eurocrypt 2013, CHES 2013 at UCSB, etc.
The corresponding two security strength levels are 128 bits, which is rock-solid, and an extremely high 256 bits (e.g., corresponding to RSA keys of 15360 bits [NIST SP 800-57]).
Finally, we now comment on some criticism we saw in the discussions on the NIST hash-forum mailing list.
As explained in our new proposal, we think the SHA-3 standard should emphasize the SHAKE functions. The SHA-3 user would keep the choice between lean SHAKE256 with its rock-solid security strength level and the heavier SHAKE512 with its extremely high security strength level. In implementations, the bulk of the code or circuit is dedicated to the Keccak-f[1600] permutation and from our experience supporting multiple rates can be done at very small cost.
Recommended reading from third parties:
Other references:
This article is a copy of a message we posted on the NIST hash-forum mailing list on September 30, 2013.
SUMMARY: In the SHA-3 standard, we propose to set the capacity of all four SHA-2 drop-in replacements to 512 bits, and to make SHAKE256 and SHAKE512 the primary choice.
Technically, we think that NIST's current proposal is fine. As said in our previous post, we have proposed to reduce the capacities of the SHA-3 hash functions at numerous occasions, including during our last visit to NIST in February. Nevertheless, in the light of the current discussions and to improve public acceptance, we think it would be indeed better to change plans. For us, the best option would be the following (taking inspiration from different other proposals).
For the SHAKEs, we think it would be good to include in the standard a short procedure for replacing a hash function or MGF based on SHA-1 or SHA-2. For instance, if there is only one to be replaced, here is a sketch.
We have seen proposals for keeping instances with c=1024 in SHA-3. We think that claiming or relying on security strength levels above 256 bits is meaningless and that c=1024 would induce a significant performance loss, which should be avoided.
This proposal means that SHA-3 standard will offer drop-in primitives with the same security level as SHA-2 (modulo the comment on c=1024), but also gives protocol and product designers the possibility to use SHAKE256, which is more efficient and is in practice not less secure than SHAKE512 or the drop-ins.
This article is a copy of a message we posted on the NIST hash-forum mailing list on September 30, 2013.
SUMMARY: Keccak instances with a capacity of 256 bits offer a generic security strength level of 128 bits against all generic attacks, including multi-target attacks. 2^{128} is an astronomical number and attacks with such complexities are expected to remain unreachable for decades to come.
Among other options, we have proposed instances with capacity c=256 as an option because they have a generic security strength of 128 bits. This means any single-stage (*) generic attack has an expected complexity of 2^{128} computations of Keccak-f, unless easier on a random oracle. This is such an astronomical amount of work that one may wonder why we would ever need more than 128 bits of security (see also Tune Keccak to your requirements).
In the discussions on SHA-3 we have seen some remarks on 128-bit security not being sufficient in the light of multi-target attacks. Multi-target attacks can be illustrated nicely with block ciphers.
If the application does not allow avoiding multi-targets, one can decide to use AES-192 or AES-256. The reason to use 192-bit or 256-bit keys is not because the security strength level 128 is too small, but because in the light of multi-target attacks, we need a block cipher with a key longer than 128 bits to offer a security strength level of 128 bits. Summarizing, AES-128, AES-192 and AES-256 have key lengths of 128, 192 and 256 bits, but this does not mean they offer a generic security strength of 128, 192 and 256 bits. This is not specific for AES, it is true for any block cipher. This is also not a problem. A protocol designer who understands these issues can easily build efficient protocols offering excellent generic security strengths.
Multi-target also applies to finding (first or second) pre-images. Finding one pre-image out of M 128-bit hashes only takes 2^{128}/M hash computations.
So it is tempting to think that the 128-bit generic security strength of Keccak instances with 256-bit capacity will also degrade under multi-target attack. Fortunately, this is not the case, as the generic security strength level c/2 follows from the bound in our indifferentiability proof for the sponge construction. More specifically, the success probability of a generic attack on a sponge function is upper bounded by the sum of the attack probability of that attack on a random oracle plus the RO-differentiating advantage N^{2}/2^{c+1}. We have explained that in our Eurocrypt 2008 paper on Sponge indifferentiability and this was formalized by Elena Andreeva, Bart Mennink and Bart Preneel in Appendix B, Theorem 2 of their paper Security Reductions of the Second Round SHA-3 Candidates, and this is also true for multi-target attacks.
If one wants a hash function (any) that offers a generic security strength level of 128 bits against multi-target attacks with at most say 2^{64} targets, then one must take the output length equal to 128+64=192 bits. For a sponge function, the capacity does not need to be increased to twice the output length; if we target a security strength level of 128 bits, c=256 is still sufficient.
So a 256-bit capacity offers a generic security strength level of 128 bits that is absolute and does not degenerate under multi-target attacks.
For the record, we as Keccak team proposed setting c=256 (and even a user-chosen capacity) as an option in our SHA-3 proposal: “If the user decides to lower the capacity to c=256, providing a claimed security level equivalent to that of AES-128, the performance will be 31% greater than for the default value c=576.” (See page 4 of The Keccak SHA-3 submission and page 3 of our Note on Keccak parameters and usage published in February 2010.) Furthermore, the option of c=256 was also presented at numerous occasions:
(*) See Thomas Ristenpart, Hovav Shacham, and Thomas Shrimpton, Advances in Cryptology - Eurocrypt 2011.
We published a new note in which we propose an interface to Keccak at the level of the sponge and duplex constructions, and inside Keccak at the level of the Keccak-f permutation. The purpose is twofold.
As a concrete exercise, we adapted some implementations from the “Reference and optimized code in C” to the proposed interface and posted them in a new “Keccak Code Package”. For the optimized implementations, it appears that the impact on the throughput is negligible while it significantly improves development flexibility and simplicity.
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!
We added the slides of some recent presentations on this page.
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.
We updated the home page of this site and added a picture of the Keccak Team.
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.
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.
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 complete list of features can be found here.
We announced the winners of the Keccak Crunchy Crypto Collision and Pre-image contest during the Fast Software Encryption 2012 workshop.
The winners are:
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!
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:
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.
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.
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.
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:
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:
For each of these Keccak instances there are two challenges, so 96 in total:
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.
Note that no changes have been made to Keccak-f.
With this new version, we make the following documents available on our web page.
And obviously, the implementation packages have been updated and are available for download.
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!
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.
Congratulations to all of them!
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:
As before, these implementations have been submitted to eBASH and XBX for benchmarking.
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:
A subset of these new variants and implementations has been submitted to eBASH and XBX.
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.
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:
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.
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.
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.
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.
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).
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:
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!
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.
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.
We are looking for implementations of Keccak on exotic platforms! We offer a prize for the most interesting implementation of Keccak on:
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:
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.
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.
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!
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!
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.
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 code is documented with comments in the Doxygen format. The documentation can also be browsed online.
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:
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!
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.
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.
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.
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!
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!
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!
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.
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:
We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!
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.
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:
Note that the Keccak algorithm, specifications and test vectors have not changed since the initial NIST submission.
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.
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.
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!
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:
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.
We make available KeccakTools v1.0, a set of C++ classes that can help analyze Keccak. KeccakTools provides the following features:
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.
Version 1.1 of the main document and of the implementation are now available!
This version includes:
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.
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).
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.