This page is dedicated to the cryptographic sponge function family called Keccak, which has become the FIPS 202 (SHA-3) standard.

## Keccak in a nutshell

Keccak is a family of sponge functions. The *sponge function* is a generalization of the concept of cryptographic hash function with infinite output and can perform quasi all symmetric cryptographic functions, from hashing to pseudo-random number generation to authenticated encryption.

For a quick introduction, we propose a *pseudo-code* description of Keccak. The reference specification, analysis, reference and optimized code and test vectors for Keccak can be found in the file section.

As primitive used in the sponge construction, the Keccak instances call one of seven permutations named Keccak-*f*[*b*], with *b*=25, 50, 100, 200, 400, 800 or 1600. In the scope of the SHA-3 contest, we proposed the largest permutation, namely Keccak-*f*[1600], but smaller (or more “lightweight”) permutations can be used in constrained environments. Each permutation consists of the iteration of a simple round function, similar to a block cipher without a key schedule. The choice of operations is limited to bitwise XOR, AND and NOT and rotations. There is no need for table-lookups, arithmetic operations, or data-dependent rotations.

Keccak has a very different design philosophy from its predecessor RadioGatún. This is detailed in our paper presented at Dagstuhl in 2009.

## Strengths of Keccak

### Flexibility

Keccak inherits the flexibility of the sponge and duplex constructions.

- As a sponge function, Keccak has
**arbitrary output length**. This allows to simplify modes of use where dedicated constructions would be needed for fixed-output-length hash functions. It can be natively used for, e.g., hashing, full domain hashing, randomized hashing, stream encryption, MAC computation. In addition, the arbitrary output length makes it suitable for tree hashing. - As a duplex object, Keccak can be used in
**clean and efficient modes**as a reseedable pseudo-random bit generator and for authenticated encryption. Efficiency of duplexing comes from the**absence of output transformation**. - Keccak has a
**simple security claim**. One can target a given security strength level by means of choosing the appropriate capacity, i.e., for a given capacity*c*, Keccak is claimed to stand any attack up to complexity 2^{c/2}(unless easier generically). This is similar to the approach of*security strength*used in NIST's SP 800-57. - The security claim is
**disentangled from the output length**. There is a minimum output length as a consequence of the chosen security strength level (i.e., to avoid generic birthday attacks), but it is not the other way around, namely, it is not the output length that determines the security strength level. For an illustration with the classical security requirements of hashing (i.e., collision and (second) preimage resistance), we refer to our interactive page. - The instances proposed for SHA-3 make use of a
**single permutation**for all security strengths. This cuts down implementation costs compared to hash function families making use of two (or more) primitives, like the SHA-2 family. And with the same permutation, one can make**performance-security trade-offs**by way of choosing the suitable appropriate capacity-rate pair.

### Design and security

- Keccak has a
**thick safety margin**. In [Keccak reference, Section 5.4], we estimate that the Keccak sponge function should stand by its security claim even if the number of rounds is almost divided by two (i.e., from 24 down to 13 in the case of Keccak-*f*[1600]). - Keccak was scrutinized by
**third-party cryptanalysis**. For more details, we refer to the cryptanalysis page. - We showed that the Keccak-
*f*permutations have provable lower**bounds on the weight of differential trails**. - The design of the permutations follows the
**Matryoshka principle**, where the security properties of the seven permutations are linked. The cryptanalysis of the smaller permutations, starting from the “toy” Keccak-*f*[25], is meaningful to the larger permutations, and vice-versa. In particular, differential and linear trails in one Keccak-*f*instance extend to symmetric trails in larger instances. - The sponge and duplex constructions used by Keccak are
**provably secure against generic attacks**. This covers also the joint use of multiple Keccak instances with different rate/capacity parameters. - Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence
**does not need the HMAC nested construction**. Instead, MAC computation can be performed by simply prepending the message with the key. - From the mode down to the round function, our design choices are fairly different from those in the SHA-1 and SHA-2 hash functions or in the Advanced Encryption Standard (AES). Keccak therefore provides
**diversity with respect to existing standards**.

### Implementation

- Keccak excels in
**hardware performance**, with speed/area trade-offs, and outperforms SHA-2 by an order of magnitude. See for instance the works of Gürkaynak et al., Gaj et al., Latif et al., Kavun et al., Kaps et al. and Jungk presented at the Third SHA-3 Candidate Conference. - Keccak has overall
**good software performance**. It is faster than SHA-2 on modern PCs and shines when used in a mode exploiting parallelism. On AMD™ Bulldozer™, 128-bit and 256-bit security hashing tops at 4.8 and 5.9 cycles/byte, respectively. On Intel™ Sandy Bridge™, the same functions reach 5.4 and 6.9 cycles/byte. On constrained platforms, Keccak has moderate code size and RAM consumption requirements. - For modes involving a key, protecting the implementation against
**side-channel attacks**is wanted. The operations used in Keccak allow for**efficient countermeasures**against these attacks. Against cache-timing attacks, the most efficient implementations involve no table lookups. Against power analysis attacks and variants, countermeasures can take advantage of the quadratic round function.

## Latest news

### 12 June 2017 — Is SHA-3 slow?

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.

#### Hardware and software

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.

#### Did you say “SHA-3”?

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?

#### Parallelism

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.

#### Security and performance hand-in-hand

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

Gilles, Guido, Joan, Michaël and Ronny

Comments? Contact us via Twitter or send us an email!

### 15 March 2017 — New bounds on differential trails in Keccak-*f*

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.

### 6 March 2017 — Announcing the Ketje cryptanalysis prize

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

### 1 March 2017 — First 6-round collision challenge solved

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

### 23 December 2016 — NIST SP 800-185 officially released

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.

### 22 December 2016 — First 4-round pre-image challenge solved

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

## Contact Information

Email: `keccak`

*-at-*`noekeon`

*-dot-*`org`