News feed (atom)
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 2c/2 (unless easier generically). This is similar to the approach of security strength used in NIST's SP 800-57.
- The security claim is disentangled from the output length. There is a minimum output length as a consequence of the chosen security strength level (i.e., to avoid generic birthday attacks), but it is not the other way around, namely, it is not the output length that determines the security strength level. For an illustration with the classical security requirements of hashing (i.e., collision and (second) preimage resistance), we refer to our interactive page.
- The instances proposed for SHA-3 make use of a single permutation for all security strengths. This cuts down implementation costs compared to hash function families making use of two (or more) primitives, like the SHA-2 family. And with the same permutation, one can make performance-security trade-offs by way of choosing the suitable appropriate capacity-rate pair.
Design and security
- Keccak has a thick safety margin. In [Keccak reference, Section 5.4], we estimate that the Keccak sponge function should stand by its security claim even if the number of rounds is almost divided by two (i.e., from 24 down to 13 in the case of Keccak-f[1600]).
- Keccak was scrutinized by third-party cryptanalysis. For more details, we refer to the cryptanalysis page.
- We showed that the Keccak-f permutations have provable lower bounds on the weight of differential trails.
- The design of the permutations follows the Matryoshka principle, where the security properties of the seven permutations are linked. The cryptanalysis of the smaller permutations, starting from the “toy” Keccak-f[25], is meaningful to the larger permutations, and vice-versa. In particular, differential and linear trails in one Keccak-f instance extend to symmetric trails in larger instances.
- The sponge and duplex constructions used by Keccak are provably secure against generic attacks. This covers also the joint use of multiple Keccak instances with different rate/capacity parameters.
- Unlike SHA-1 and SHA-2, Keccak does not have the length-extension weakness, hence does not need the HMAC nested construction. Instead, MAC computation can be performed by simply prepending the message with the key.
- From the mode down to the round function, our design choices are fairly different from those in the SHA-1 and SHA-2 hash functions or in the Advanced Encryption Standard (AES). Keccak therefore provides diversity with respect to existing standards.
Implementation
- Keccak excels in hardware performance, with speed/area trade-offs, and outperforms SHA-2 by an order of magnitude. See for instance the works of Gürkaynak et al., Gaj et al., Latif et al., Kavun et al., Kaps et al. and Jungk presented at the Third SHA-3 Candidate Conference.
- Keccak has overall good software performance. 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
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")andTupleHash("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 Liu1 and Jian Guo2 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
21 September 2016 — Ketje and Keyak for CAESAR round 3
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.
Ketje v2
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.
Keyak v2
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.
11 August 2016 — KangarooTwelve: fast hashing based on Keccak-p
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.
- Documentation
- Reference implementation in Python
- Optimized implementations, as part of the KCP
- Test vectors
15 July 2016 — Another 5-round collision found in our crypto challenge
We congratulate Jian Guo1, Meicheng Liu1,2, Ling Song1,2,3 and Kexin Qiao2,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
- 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
- University of Chinese Academy of Sciences, China
31 May 2016 — New solutions to collision challenges
We congratulate Jian Guo1, Meicheng Liu1,2, Ling Song1,2,3 and Kexin Qiao2,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
- 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
- University of Chinese Academy of Sciences, China
Contact Information
Email: keccak-at-noekeon-dot-org