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:

- Nonce reuse resistance.
- If a nonce is present in the associated data, then a t-bit tag gives t-bit security.
- Thanks to frame bits, it collapses to a simple MAC if plaintext is not present.
- Thanks to frame bits, the associated data string is also optional (so for e.g. key wrapping, the mode is efficient).
- Both the key schedule and static associated data contribution can be precomputed and reused across multiple messages.
- Fully parallelizable in absorption of associated data and plaintext, expansion of keystream and encryption of plaintext.

Deck-SANSE wrap function, taking associated data *A* and plaintext *P*, and returning ciphertext *C* and tag *T*:

if|A| > 0and|P| > 0thenT← 0^t + F(P||010 ∘A||00)C←P+ F(T||110 ∘A||00)elseif|P| > 0thenT← 0^t + F(P||010)C←P+ F(T||110)elseT← 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:

*Cube-like Attack on Round-Reduced Initialization of Ketje Sr*, by Xiaoyang Dong, Zheng Li, Xiaoyun Wang and Ling Qin, presented at FSE 2017 and published in Volume 2017, Issue 1 of ToSC.*New MILP Modeling: Improved Conditional Cube Attacks to Keccak-based Constructions*, by Ling Song, Jian Guo and Danping Shi, available as Cryptology ePrint Archive Report 2017/1030.*State-recovery attacks on Modified Ketje Jr*, by Thomas Fuhr, Maria Naya-Plasencia and Yann Rotella, presented at FSE 2018 and published in Volume 2018, Issue 1 of ToSC.

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.

**Farfalle**is a new generic construction for building a pseudo-random function (PRF) exploiting the parallel evaluation of a cryptographic permutation. The PRF takes as input a key and a sequence of arbitrary-length data strings, and returns an arbitrary-length output. To an adversary not knowing the key, these output bits look like independent uniformly-drawn random bits. Farfalle can readily be used for stream encryption and MAC computation, and we define several modes for authenticated encryption on top of it.**Kravatte**is a high-speed instance of Farfalle based on Keccak-*p*[1600] permutations, claimed to resist against classical and quantum adversaries. Modes for authentication, encryption and authenticated encryption are defined accordingly.

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

- State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China

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:

- Innovative ideas are preferred over incremental results or the application of standard techniques.
- For attacks with innovation levels that are comparable, the earlier ones are favored.
- The smaller the rate (expressed in number of lanes) the better.
- Attacks with reduced-round versions are allowed but the closer to the CAESAR submission the better.
- “Nonce-misuse” results are accepted if presenting very innovative aspects.

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

- Cryptanalysis Taskforce, Temasek Laboratories @ Nanyang Technological University, Singapore
- State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China
- Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, China
- South China Normal University, China

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:

**cSHAKE**is a family of two extendable-output functions (cSHAKE128 and cSHAKE256) that generalize upon SHAKE128 and SHAKE256. It is used as a building block for KMAC, TupleHash and ParallelHash. The main difference with the SHAKEs lies in an*explicit domain separation mechanism*. In addition to the usual input string, the user can supply a function name and a customization string. The former is standardized by NIST to separate different standard functions, while the user is free to supply anything in the latter.**KMAC**is a*keyed hash function*or pseudo-random function (PRF) that can be used, e.g., to compute a message authentication code (MAC) or to derive a session key from a master key. It is more efficient than HMAC by removing the need for HMAC's nested construction.**TupleHash**is a hash function whose input domain is*any number of input strings*. The output depends on the exact sequence of strings, not just their concatenation. For instance,`TupleHash("a", "b", "c")`

,`TupleHash("a", "bc")`

,`TupleHash("abc")`

and`TupleHash("abc", "")`

all give unrelated outputs.**ParallelHash**is a hash function that can exploit the parallelism in modern processors by way of a tree hash mode. This*significantly speeds up*the hashing of long inputs. E.g., we reported speeds of 2.73 cycles/byte and 2.31 c/b on Haswell and Skylake processors, respectively. (These figures are based on the draft specifications, but we do not expect them to differ significantly for the final specifications.)

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.

- State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, China
- Nanyang Technological University, Singapore

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.

- Cryptanalysis Taskforce, Temasek Laboratories @ Nanyang Technological University, Singapore
- Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, China
- University of Chinese Academy of Sciences, China

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…]

- Cryptanalysis Taskforce, Temasek Laboratories @ Nanyang Technological University, Singapore
- Data Assurance and Communication Security Research Center, Chinese Academy of Sciences, China
- University of Chinese Academy of Sciences, China

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.

- The functions related to the permutations Keccak-
*f*and Keccak-*p*are name-separated and can therefore coexist. Consequently, the different instances of Keccak, Ketje and Keyak can be compiled together. - The user can create a library
.`libkeccak.a`

- The user can easily select code optimized for a given platform.
- The parallel implementations can either exploit SIMD instructions or, when unvailable, rely on serial (or less parallel) implementations.

To sum up, the KCP contains:

- The FIPS 202 instances SHAKE128, SHAKE256, and SHA3-224 to SHA3-512.
- All the Keccak[
*r*,*c*] sponge functions and duplex objects with*r*+*c*=200, 400, 800 or 1600. - The Ketje and Keyak (version 2) authenticated encryption schemes, including
- Ketje Jr, Ketje Sr, River Keyak, Lake Keyak, Sea Keyak, Ocean Keyak and Lunar Keyak.
- Reference and optimized implementations of the Keccak-
*f*[*b*] and Keccak-*p*[*b*] permutations, including - compact implementations in C;
- generically optimized code in C for 32 or 64-bit platforms;
- assembly-optimized code for AVR8, ARMv6M, ARMv7M and ARMv7A.
- Paralellized implementations of the permutations, exploiting 128-bit and 256-bit SIMD instruction sets (SSE, AVX, AVX2).

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.

- First, a readable and compact implementation of all the Keccak instances approved in the FIPS 202 standard, where we focused on clarity and on source-code compactness (excluding the comments), rather than on the performance. As much as possible, we used the same notation as in the specifications.
- Second, a more compact (but less readable) implementation, demonstrating that Keccak is conceptually simple.
- Third, a very compact implementation aimed at minimizing the number of tweets (i.e., lines of up to 140 characters each). With just 9 tweets, this means an average of 1.5 tweets per instance! As a comparison, SHA-512 alone takes about 27 tweets when extracted from TweetNaCl.

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:

- four SHA-2 drop-in replacements with fixed output length SHA3-224 to SHA3-512, and
- two future-oriented
*extendable-output functions*SHAKE128 and SHAKE256.

**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:

- parallelizable hashing,
- message authentication codes (MACs) and key derivation functions,
- authenticated encryption,
- generic domain separation mechanisms on top of these.

**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 have simplified the rules for the prizes. For all open challenges the first submission now simply receives 10 € multiplied by the number of rounds
*n*. The challenges that have been closed remain closed._{r} - We allow for some more flexibility in choosing the reduced-round versions of Keccak-
*f*. Previously, the*n*-round reduced-round version was fixed to the first_{r}*n*consecutive rounds. The submitters can now choose to take the last_{r}*n*consecutive rounds (as in the draft of FIPS 202) or any other_{r}*n*rounds, as long as they are consecutive._{r}

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.

- Keccak is a
**family**of sponge function instances, encompassing capacity values ranging from 0 to 1599 bits. All these instances are well-defined and so are their security claim. Our SHA-3 submission highlighted instances with capacities*c*=448, 512, 768 and 1024 for strictly meeting NIST's SHA-3 requirements on the SHA-2 drop-in replacement instances, plus a capacity of 576 for a variable-output-length instance. Nevertheless, the capacity is an explicitly tunable parameter, in the line of what NIST suggested in their SHA-3 call, and we therefore proposed in our SHA-3 submission document that the**capacity would be user-selectable**. - The
**capacity**is a parameter of the sponge construction (and of Keccak) that determines a particular**security strength level**, in the line of the levels defined in [NIST SP 800-57]. Namely, for a capacity*c*, the security strength level is*c*/2 bits and the sponge function is claimed to resist against all attacks up to 2^{c/2}, unless easier with a random oracle. As we make a clear security claim for each possible value of the capacity, a user knows what the expect and a cryptanalyst knows her target. Conversely, we provide a tool that helps determine the minimum capacity and output length given collision and pre-image resistance requirements. **The core of Keccak**, namely the Keccak-*f*permutations,**has not changed**since round 2 of the SHA-3 competition. When Keccak was selected for the 2^{nd}round, we increased the number of rounds to have a better safety margin (from 18 to 24 rounds for Keccak-*f*[1600]). The round function has not changed since the original submission in 2008.- Keccak is the result of using the sponge construction on top of the Keccak-
*f*permutations and applying the multi-rate padding to the input. Using multi-rate padding causes each member of the Keccak family (and in particular for each value of the capacity) to act as an**independent function**. - As a native feature, Keccak provides
**variable output length**, that is, the user can dynamically ask for as many output bits as desired (e.g., as a mask generating function such as MGF1).

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*=2*n* 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*=2*n* is also a waste of resources. For instance, Keccak[*c*=2*n*] 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.

*“128 bits of security are not enough in particular in the light of multi-target pre-image attacks.”*We addressed this specifically in a message to the NIST SHA-3 mailing list, we explained why this fear is unfounded and why the 128 bits of security do not degrade for multi-target pre-image attacks. And anyway the SHA-3 proposal includes functions with 256-bit security, which the user is free to choose as well.*“SHA3-256 does not provide 256-bit pre-image resistance.”*With*c*=256, this is correct indeed. We proposed to reduce the capacity of SHA3-256 to 256 bits to follow our security-strength oriented approach, which better addresses actual user requirements than the traditional way of inferring resistance of hash functions from the output length. Nevertheless, to avoid confusion for people expecting 256-bit resistance from SHA3-256, we made a 2^{nd}proposal that sets*c*=512 for all SHA-2 drop-in replacement instances, hence providing the traditional 256-bit pre-image resistance.*“There is no instance providing 512-bit pre-image resistance.”*Again, this is correct. The answer is similar to the previous point, except that our new proposal does not extend to capacities higher than*c*=512 bits, simply because claiming or relying on security strength levels above 256 bits is meaningless. Setting*c*=1024 would induce a significant performance loss, and there are no standard public-key parameters matching 512 bits of security. Also we believe that this security level was more a side-effect and not a security target in itself. All conventional hash functions that would aim at 256-bit collision resistance would automatically provide 512-bit preimage resistance. Keccak however is a different cryptographic object and SHA3-512 can safely provide a security strength of 256 bits against all attacks without the need to boost the security level beyond any meaning.*“Claiming a higher security level provides a safety margin.”*In the Keccak design philosophy, safety margin comes from the number of rounds in Keccak-*f*, whereas the security level comes from the selected capacity. We have designed Keccak so as to have a strong safety margin for all possible capacities. At this moment, this safety margin is very comfortable (4 to 5 rounds out of 24 are broken). Of course, the user can still increase the capacity to get a security level that is higher than the one he targets, and hence somehow artificially increase the safety margin. But, there is simply no need to do so. We also refer to Martin Schläffer's excellent summary, posted on the NIST hash-forum mailing list on October 1st, 2013 at 10:16 GMT+2 (thanks Martin!).

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:

- Jeff Trombly's excellent comments
- Martin's mail (the NIST hash-forum mailing list on October 1st, 2013 at 10:16 GMT+2)

Other references:

- NIST SHA-3 pages and the hash-forum mailing list
- Bruce Schneier on the subject (no, there was no “internal changes to the algorithm”)
- Slashdot thread on the subject (although, no, NIST didn't “cripple SHA-3”)
- CDT post (with many factual errors)
- And of course our pages on Keccak and on sponge functions

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

- Set the capacity of the SHA-2 drop-in replacements (i.e., SHA3-224 to SHA3-512) to
*c*=512. This guarantees the same claimed security properties as for the corresponding SHA-2 instances up to the 256-bit security level. (In particular, the pre-image resistance of SHA3-256 would be raised to 256 bits.) - Keep the SHAKEs as they are (i.e., SHAKE256 with
*c*=256 and SHAKE512 with*c*=512) and make them the primary choice for new applications of hash functions, for replacing mask generating functions (MGFs) and for those who wish to follow the security strength levels approach of [NIST SP 800-57].

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.

- Choose between SHAKE256 and SHAKE512. If the user can determine the required security level and it is 128 bits or smaller, choose SHAKE256. Otherwise (or if unsure), choose SHAKE512.
- Let the output length be determined by the application.

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.

**Single-target attack:**Say we have a 32-byte ciphertext*C*that is the result of applying AES-128 in ECB mode on a known plaintext with some unknown key*K*. Then*K*can be found by exhaustive key search: enciphering*P*by all possible values*K*until*C*appears. The right key will be hit after about 2^{127}trials and so the security strength is around 128 bits. This is the security strength the layman typically expects when using AES-128.**Multi-target attack:**Say we now have*M*ciphertexts*C*obtained by enciphering the same plaintext_{i}*P*with*M*different keys*K*. And assume the attacker is satisfied if he can find at least one key_{i}*K*. Then if he applies exhaustive key search, the expected number of trials is 2_{i}^{128}/M. So the security strength is reduced to 128-log_{2}(*M*). If*M*is very large, this can reduce the security strength quite a lot. E.g.,*M*= 2^{40}reduces the time complexity to only 2^{88}. This is still a huge number, but it can no longer be dismissed as science-fiction. Among cryptographers this security degeneration is well-known and there are methods of avoiding this, such as salting, enciphering in CBC mode with random IVs etc.

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

- see slide 5 of our presentation
*1001 ways to implement Keccak*at the Third SHA-3 Conference; - see slides 13 and 22 of our presentation at FOSDEM 2013;
- see slide 48 of our presentation to NIST in February 2013.

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

- First, it allows users of Keccak making best use of its flexibility. As focused on by the SHA-3 contest, Keccak is sometimes viewed solely as a hash function and some implementations are inherently restricted to the traditional fixed-output-length instances. Instead, the proposed interface reflects the features of the sponge and duplex constructions, from the arbitrary output length to the flexibility of choosing security-speed trade-offs.
- Second, it simplifies the set of optimized implementations on different platforms. Nearly all the processing of Keccak takes place in the evaluation of the Keccak-
*f*permutation as well as in adding (using bitwise addition of vectors in GF(2)) input data into the state and extracting output data from it. The interface helps isolate the part that needs to be most optimized, while the rest of the code can remain generic. If they share the same interface, optimized implementations can be interchanged and a developer can select the best one for a given platform.

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 exhaustive forward and backward extension of trails up to a given weight and given number of rounds;
- related to θ:
- the representation of column parities in runs;
- lower bounding the weight of any 2-round trail core with a given parity;
- the exhaustive generation of 2-round trail cores with a given parity;
- the exhaustive generation of 2-round trail cores with a small number of active rows;
- the exhaustive generation of 3-round trail cores in the kernel up to a given weight:
- the generation of knots and chains between knots;
- the generation of vortices and their combination with knots and chains;
- the implementation of a lower bound on the weight while adding knots, chains and vortices to limit the search.

The complete list of features can be found here.

We announced the winners of the Keccak Crunchy Crypto Collision and Pre-image contest during the Fast Software Encryption 2012 workshop.

The winners are:

**Paweł Morawiecki**for solving the preimage and collision challenges on 1 and 2 rounds, for all instances except Keccak[*r*= 40,*c*= 160];**Alexandre Duc, Jian Guo, Thomas Peyrin and Lei Wei**for independently and simultaneously solving the collision challenges on 1 and 2 rounds of Keccak[*r*= 1440,*c*= 160];**Itai Dinur, Orr Dunkelman and Adi Shamir**for finding collisions on Keccak[*r*= 1440,*c*= 160] with 3 and 4 rounds.

We handed out the prizes to the winners during the presentation of the results. Paweł was not present, so we contacted him and arranged with him how to give him his prize.

**Congratulations to all!**

Immediately after posting the results of the contest, we announce that the Keccak Crunchy Crypto Collision and Pre-image contest re-opens and continues through end 2012.

The challenges remain the same, although a few entries are closed to encourage new approaches. More specifically:

- All the collision and pre-image challenges for Keccak[
*r*= 40,*c*= 160] remain open, from 1 to 12 rounds, as none of these were solved. - For the other instances, pre-image challenges start from 3 rounds and collision challenges from 5 rounds. The only unsolved challenges that are closed are 3- and 4-round collisions, which can likely be solved by a straightforward application of the techniques of Itai Dinur, Orr Dunkelman and Adi Shamir.

We suggest all interested people to subscribe to our mailing list, and solutions shall be sent to this mailing list, as detailed here, before **before December 31, 2012** at 23:59 GMT+1.

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:

- Version 3.1 of the optimized implementations, containing examples of in-place implementations as well as an assembly version for the x86_64 architecture;
- Version 3.1 of the
*Keccak implementation overview*document, with a new chapter specifically dedicated to optimization techniques; - A new version of KeccakTools, with methods dedicated to the generation of C code chunks to help write optimized implementations.

By applying in-place processing to the ARM Cortex-M3 (implementation by Ronny Van Keer), Keccak[] takes about 95 cycles/byte for long messages and uses less than 280 bytes of RAM on the stack, according to our measurements. This and other new implementations have been submitted to eBASH and XBX for independent benchmarking.

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:

- The capacity is fixed to 160 bits: this implies a security level of 2
^{80}against generic collision search. - The width
*b*of Keccak-*f*[*b*] is in {200, 400, 800, 1600}: the width values that support the chosen capacity. - The number of rounds
*n*ranges from 1 to 12._{r}

For each of these Keccak instances there are two challenges, so 96 in total:

- generating a collision in the output truncated to 160 bits;
- generating a pre-image of an output truncated to 80 bits.

We have released **KeccakTools v3.1**, which contains support for the validation of solutions (see file `KeccakCrunchyContest.cpp`

).

Please visit the Keccak Crunchy Crypto Contest page for the contest rules and pre-image challenges.

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.

**We shortened and simplified the padding rule.**The new padding rule is the pad10^{*}1 rule, which is suitable for a family of sponge functions sharing the same permutation with different rate-capacity pairs. It is simpler to describe and to implement than the previous padding rule. It is also more efficient, as it appends a minimum of 2 bits instead of 25. For long messages, the gain is negligible, but short messages can be 3 bytes longer for the same number of calls to Keccak-*f*. This aspect is especially relevant when using the duplex construction.**We removed the diversifier parameter**All the fixed-output-length candidates have different bitrates, which already provides diversification between them, hence making*d*.*d*redundant in this case. Diversification between functions using the same bitrate is still possible using more general mechanisms that we describe in our documentation.**We removed the restriction on the bitrate**Previously, the bitrate could only take values that are multiple of 8 bits. Now all the values between 1 and the permutation width are supported. Although a bitrate multiple of 8 bits is a natural choice to avoid undesirable intra-byte bit shuffling on the input blocks, schemes making use of the duplex construction can take advantage of this to propose round-sized input blocks to the application level and put frame bits in a few extra bits.*r*.

Note that no changes have been made to Keccak-*f*.

With this new version, we make the following documents available on our web page.

*The Keccak reference*is the main document that specifies and analyzes the Keccak sponge function family.*The Keccak SHA-3 submission*is the entry document of the SHA-3 submission, with our proposals for the standard.*Keccak implementation overview*gives an overview of the implementation aspects, in software and hardware, with or without protection against side-channel attacks.*Cryptographic sponge functions*gathers our definitions and analysis related to the sponge construction, on which Keccak is based.

And obviously, the implementation packages have been updated and are available for download.

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.

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

*Congratulations to all of them!*

Version 2.4 of the optimized implementations is now available. It contains further implementations for small processors. Compared to the previous version, this package provides the following new implementations:

- An improved implementation for AVR8 processors, with the Keccak-
*f*[1600] permutation fully in assembly. - The assembly implementation for ARM processors already introduced in version 2.2, converted to a syntax understood by GCC. (This implementation is optimized for Cortex-M3 specifically and requires Thumb and Thumb2 support.)

As before, these implementations have been submitted to eBASH and XBX for benchmarking.

Version 2.3 of the optimized implementations is now available.

This new version follows the same line of improvements as the previous one published in October, with contributions by both Ronny Van Keer, STMicroelectronics and ourselves. Compared to the previous version, this package provides the following new implementations:

- An implementation for AVR8 processors, meant to be reasonably compact in terms of both code size and memory usage. (Again, we provide an API for giving partial input chunks, while removing the need of a message queue.)
- An implementation similar to the previous one, but using only pure C, as the basis for optimization on 8-bit processors in general.
- A simple yet optimized implementation in C using only 32-bit operations, using the
*bit interleaving*technique.

A subset of these new variants and implementations has been submitted to eBASH and XBX.

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:

- An assembly implementation for ARM processors, optimized for Cortex-M3 specifically—although at this point it is written in the syntax of RVCT's armcc/armasm, not yet in a syntax understood by GCC.
- A simple yet optimized implementation in C covering from Keccak-
*f*[200] to Keccak-*f*[1600]. - An implementation in C meant to be reasonably compact in terms of both code size and memory usage. (E.g., we provide an API for giving partial input chunks, where these partial input chunks are XORed directly into the state of Keccak to remove the need of a separate message queue.)

The new package also contains various improvements here and there, including a wider range of supported variants. A subset of these new variants and implementations has been submitted to eBASH.

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:

- Innovative ideas get more points than incremental results or applying standard techniques;
- For attacks with innovations that are comparable, the earlier ones get more points;
- Cryptanalysis or attack techniques applicable to a wider range of valid parameters
*r*,*c*get more points (see the specifications for the definition of valid parameters);- Larger Keccak-
*f*width gets more points; - Larger capacity gets more points;

- Larger Keccak-
- Attacks on reduced-round versions are allowed but more rounds get more points;
- For the same number of rounds, a distinguisher or attack on the Keccak sponge function gets more points than a distinguisher on Keccak-
*f*only.

We reserve the right to extend the deadline in the absence of interesting results or when we consider that the presented results are too small increments compared to known results.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

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.

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:

- graphic cards or GPU,
- embedded processors (e.g., ARM, Cell processor…),
- or any other analog/digital computing device.

The prize consists in a Himitsu-Bako secret box.

Who wins the prize will be decided by consensus in the Keccak team. We will internally use a system of points. Some hints:

- fast implementations get more points;
- uncommon devices get more points.

We give freedom in the way Keccak is used. It is allowed to implement, for instance, tree hashing or batch hashing (several messages hashed in parallel), instead of plain sequential hashing, to take advantage of parallel computing and get better performance.

The results and source code must be publicly available on an URL that is sent to `keccak`

*-at-* `noekeon`

*-dot-* `org`

**before June 30, 2010** at 12:00 GMT+2. No specific licensing condition is requested (pick up the one you like!). We reserve the right to extend this deadline in the absence of interesting results. Otherwise, the winner will be announced during the rump session of the second SHA-3 candidate conference in Santa Barbara.

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 implementation of the seven Keccak-
*f*permutations, from Keccak-*f*[25] to Keccak-*f*[1600], possibly with a specified number of rounds; - the implementation of the
*inverses*of the seven Keccak-*f*permutations; - the generation of look-up tables for Keccak-
*f*[25]; - the generation of GF(2) equations of the round functions and step mappings in the Keccak-
*f*'s and their inverses; - the generation of optimized C code for the round functions, including lane complementing and bit interleaving techniques;
- the implementation of the sponge construction using any transformation or permutation, and of the Keccak sponge function family.

The code is documented with comments in the Doxygen format. The documentation can also be browsed online.

We announce the third prize for the most interesting cryptanalysis of Keccak. The results must be publicly available on an URL that is sent to `keccak`

*-at-* `noekeon`

*-dot-* `org`

**before December 5, 2009** at 23:59 GMT+1 (i.e., before Sinterklaas or Saint Nicolas).

The third prize consists of beer, like the first one. This time we offer Lambic beers that according to myth can only be brewed in the surroundings of Brussels thanks to wild yeast and mysterious bacteria that would not occur anywhere else. Anyway, the prize is a case with 24 (the new number of rounds in Keccak-*f*) bottles of Lambic-based beers from breweries such as Cantillon, Girardin, and 3 Fonteinen.

Like for the previous prizes, who wins will be decided by consensus in the Keccak team, based internally on a system of points. Some hints:

- Innovative ideas get more points than incremental results or applying standard techniques;
- For attacks with innovations that are comparable, the earlier ones get more points;
- Cryptanalysis or attack techniques applicable to a wider range of valid parameters
*r*,*c*get more points (see the specifications for the definition of valid parameters);- Larger Keccak-
*f*width gets more points; - Larger capacity gets more points;

- Larger Keccak-
- Attacks on reduced-round versions are allowed but more rounds get more points;
- For the same number of rounds, a distinguisher or attack on the Keccak sponge function gets more points than a distinguisher on Keccak-
*f*only.

We reserve the right to extend the deadline in the absence of interesting results or when we consider that the presented results are too small increments compared to known results.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

For the second round of the SHA-3 competition, we decided to modify the parameters of Keccak. There are basically two changes: the modification of the rate and capacity values in the four fixed-output-length candidates for SHA-3 and the increase of the number of rounds in Keccak-*f*.

- In the case of fixed-output-length candidates, we increased the rate
*r*to set the capacity*c*to twice the output length value. - We increased the number of rounds of Keccak-
*f*from 12+*l*to 12+2*l*(from 18 to 24 rounds for Keccak-*f*[1600]).

The increase in the rate was done for taking better advantage of the performance-security trade-offs that the Keccak sponge function allows.

The increase in the number of rounds is due to the distinguishers recently found by Jean-Philippe Aumasson and Willi Meier that work on reduced-round variants of Keccak-*f*[1600] up to 16 rounds. Although we think it is infeasible to exploit the 16-round distinguisher on Keccak-*f* when used in the sponge construction, we want the underlying permutation to have no structural distinguishers. This is the basis of our conservative design strategy: the hermetic sponge strategy (see the Keccak main document, Section 4.1.1).

Sticking to 18 rounds would not contradict this strategy but would leave a security margin of only 2 rounds against a distinguisher of Keccak-*f*. We think that the increase in the number of rounds actually increases the security margin with respect to distinguishers of and attacks against the Keccak sponge functions.

Finally, note that the modifications do not change the round function and therefore do not invalidate any past or ongoing cryptanalysis of Keccak.

The updated Keccak specifications (version 2) and main document (version 2.0) containing some new analysis can be found on this website.

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.

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:

- Innovative ideas get more points than incremental results or applying standard techniques;
- For attacks with innovations that are comparable, the earlier ones get more points;
- Cryptanalysis or attack techniques applicable to a wider range of valid parameters
*r*,*c*get more points (see the specifications for the definition of valid parameters); - Larger Keccak-
*f*width gets more points; - Larger capacity gets more points;
- Attacks on reduced-round versions are allowed but more rounds get more points.

We hope analyzing Keccak is a fun and interesting challenge, and we appreciate any submitted work!

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:

- A new optimized implementation using SIMD instructions is available.
- In the main document, we added a 2-page specifications summary, more explanations on difference propagation and correlation properties of χ, ANF tests also on the inverse of Keccak-
*f*and new software performance results in general and regarding SIMD instructions in particular. (A change log in the appendix of the main document brings you directly to the changed sections.) - The new version of KeccakTools is able to generate the source code of the new optimized implementation.

Note that the Keccak algorithm, specifications and test vectors have **not** changed since the initial NIST submission.

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:

- Innovative ideas get more points than incremental results or applying standard techniques;
- For attacks with innovations that are comparable, the earlier ones get more points;
- Cryptanalysis or attack techniques applicable to a wider range of valid parameters
*r*,*c*get more points (see the specifications for the definition of valid parameters); - Larger Keccak-
*f*width gets more points; - Larger capacity gets more points;
- Attacks on reduced-round versions are allowed but more rounds get more points.

We wanted to offer a prize which has a cultural dimension and is likely to appeal to the typical cryptanalyst. This forced us to the choice we have made. The prize is a case with 24 bottles of 33cl Trappist beers from all 6 recognized Trappist breweries in Belgium. It includes bottles of Westmalle Dubbel, Westmalle Tripel, Chimay bleue, Chimay rouge, Chimay blanche, Rochefort 8, Rochefort 10, Orval, Achel Blond, Achel Bruin and probably the most hard to get beer in the world: the mythical Westvleteren 12°.

In case there is a winner by the first SHA-3 candidate conference and she/he/they are present, we'll bring the case to Leuven and hand it over there. Otherwise, we'll do our best to bring the case and the winners together. Once the winner is known there is no hurry as the expiry dates on most of the bottles are years from now.

We make available KeccakTools v1.0, a set of C++ classes that can help analyze Keccak. KeccakTools provides the following features:

- the implementation of the seven Keccak-
*f*permutations, from Keccak-*f*[25] to Keccak-*f*[1600], possibly with a specified number of rounds; - the implementation of the
*inverses*of the seven Keccak-*f*permutations; - the generation of look-up tables for Keccak-
*f*[25]; - the generation of GF(2) equations of the round functions and step mappings in the Keccak-
*f*'s and their inverses; - the generation of optimized C code for the round functions, including lane complementing and bit interleaving techniques;
- the implementation of the sponge construction using any transformation or permutation, and of the Keccak sponge function family.

The code is documented with comments in the Doxygen format. The documentation can also be browsed online.

Since this is the first public release of KeccakTools, do not hesitate to report problems, e.g., in the compilation process (it has been tested with GCC 4.3 and Microsoft Visual C++ 2008 Express Edition), or things that are not clear in the documentation. All feedback and questions are welcome any time of course.

Version 1.1 of the main document and of the implementation are now available!

This version includes:

- Additional usage modes on top of Keccak, including the possibility to do tree and parallel hashing;
- Improved optimized software implementations, using new techniques to reduce the number of NOT instructions and to use only 32-bit rotations on 32-bit platforms;
- New hardware implementations, with better performance and code suitable for FPGAs, considering the work published by Joachim Strömbergson.

A change log in the appendix of the main document brings you directly to the changed sections.

Note that the Keccak algorithm, specifications and test vectors have **not** changed since the initial NIST submission.

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.