- As of May 2013[update], NIST has not yet updated the Secure Hash Standard (SHS) for SHA-3. The content of this article is subject to change once the final standard is published (draft expected 2013 Q3, final by 2014 Q2).
|Designers||Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.|
|Speed||12.5 cpb on Core 2 [r=1024,c=576].|
On October 2, 2012, Keccak was selected as the winner of the NIST hash function competition. SHA-3 is not meant to replace SHA-2, as no significant attack on SHA-2 has been demonstrated. Because of the successful attacks on MD5, SHA-0 and theoretical attacks on SHA-1, NIST perceived a need for an alternative, dissimilar cryptographic hash, which became SHA-3.
SHA-3 uses the sponge construction in which message blocks are XORed into the initial bits of the state, which is then invertibly permuted. In the version used in SHA-3, the state consists of a 5×5 array of 64-bit words, 1600 bits total. The authors claim 12.5 cycles per byte on an Intel Core 2 CPU. However, in hardware implementations it is notably faster than all other finalists.
Keccak's authors have proposed additional, not-yet-standardized uses for the function, including an authenticated encryption system and a "tree" hash for faster hashing on certain architectures. Keccak is also defined for smaller power-of-2 word sizes w down to 1 bit (25 bits total state). Small state sizes can be used to test cryptanalytic attacks, and intermediate state sizes (e.g., from w=4, 100 bits, to w=32, 800 bits) could potentially provide practical, lightweight alternatives.
The block permutation
This is defined for any power-of-two word size, w = 2ℓ bits. The main SHA-3 submission uses 64-bit words, ℓ = 6.
The state can be considered to be a 5×5×w array of bits. Let a[i][j][k] be bit (i×5 + j)×w + k of the input, using a little-endian convention. Index arithmetic is performed modulo 5 for the first two dimensions and modulo w for the third.
The basic block permutation function consists of 12+2ℓ iterations of five sub-rounds, each individually very simple:
- Compute the parity of each of the 5×w (320, when w = 64) 5-bit columns, and exclusive-or that into two nearby columns in a regular pattern. To be precise, a[i][j][k] ⊕= parity(a[i][j−1][k]) ⊕ parity(a[i][j+1][k−1])
- Bitwise rotate each of the 25 words by a different triangular number 0, 1, 3, 6, 10, 15, .... To be precise, a is not rotated, and for all 0≤t<24, a[i][j][k] = a[i][j][k−(t+1)(t+2)/2], where .
- Permute the 25 words in a fixed pattern. a[j][2i+3j] = a[i][j]
- Bitwise combine along rows, using a = a ⊕ (¬b & c). To be precise, a[i][j][k] ⊕= ¬a[i][j+1][k] & a[i][j+2][k]. This is the only non-linear operation in SHA-3.
- Exclusive-or a round constant into one word of the state. To be precise, in round n, for 0≤m≤ℓ, a[2m−1] is exclusive-ORed with bit m+7n of a degree-8 LFSR sequence. This breaks the symmetry that is preserved by the other sub-rounds.
Hashing variable-length messages
SHA-3 uses the "sponge construction", where input is "absorbed" into the hash state at a given rate, then an output hash is "squeezed" from it at the same rate.
To absorb r bits of data, the data is XORed into the leading bits of the state, and the block permutation is applied. To squeeze, the first r bits of the state are produced as output, and the block permutation is applied if additional output is desired.
Central to this is the "capacity" of the hash function, which is the c=25w−r state bits that are not touched by input or output. This can be adjusted based on security requirements, but the SHA-3 proposal sets a conservative c=2n, where n is the size of the output hash. Thus r, the number of message bits processed per block permutation, depends on the output hash size. The NIST submission sets the rate r as 1152, 1088, 832, or 576 (144, 136, 104 and 72 bytes) for 224, 256, 384 and 512-bit hash sizes, respectively. At CHES 2013, John Kelsey of NIST announced that the capacity is likely to be lowered to 256 bit for the 224 and 256 bit variants, and 512 bit for the 384 and 512 bit variants. Thus, the preimage and collision resistances would be set to the same. The 224/384 bit variants would be truncated versions of the 256/512 variants, similarly to the SHA2 family. NIST also considers standardizing other usage modes of Keccak.
To ensure the message can be evenly divided into r-bit blocks, padding is required. The submission proposes the bit pattern 10*1: a 1 bit, zero or more 0 bits (maximum r−1), and a final 1 bit. The final 1 bit is required because the sponge construction security proof requires that the rate is encoded in the final block ("multi rate padding"). This padding might be changed in the final SHA-3 standard to match the padding of Sakura, a tree hashing scheme proposed by the Keccak authors.
To compute a hash, initialize the state to 0, pad the input, and break it into r-bit pieces. Absorb the input into the state; that is, for each piece, XOR it into the state and then apply the block permutation.
After the final block permutation, the leading n bits of the state are the desired hash. Because r is always greater than n, there is actually never a need for additional block permutations in the squeezing phase. However, arbitrary output length may be useful in applications such as optimal asymmetric encryption padding. In this case, n is a security parameter rather than the output size.
Although not part of the SHA-3 competition requirements, smaller variants of the block permutation can be used, for hash output sizes up to half their state size, if the rate r is limited appropriately. For example, a 256-bit hash can be computed using 25 32-bit words if r = 800−2×256 = 288 (36 bytes per iteration).
Throughout the NIST hash function competition, entrants are permitted to "tweak" their algorithms to address issues that are discovered. Changes that have been made to Keccak are:
- The number of rounds was increased from 12+ℓ to 12+2ℓ to be more conservative about security.
- The message padding was changed from a more complex scheme to the simple 10*1 pattern described above.
- The rate r was increased to the security limit, rather than rounding down to the nearest power of 2.
NIST announcement controversy
In August 2013, NIST announced changes in the security parameters for the SHA-3 standard, compared to the submission. The changes caused some turmoil.
Bruce Schneier criticized the decision on the basis of its possible detrimental effects on the acceptance of the algorithm, saying
There is too much mistrust in the air. NIST risks publishing an algorithm that no one will trust and no one (except those forced) will use.
The Keccak team responded by expressing agreement with the new parametrization, stating that the NIST proposal is a result of a series of discussions between them and the NIST hash team. But in the light of the uproar in the cryptographic community, they proposed raising the capacity to 512 bits for all instances.
Examples of SHA-3 (Keccak) variants
Note: Pending the standardization of SHA-3, there is no specification of particular SHA-3 functions yet. The values provided reflect to the NIST submission parameters, and are likely to be changed.
Hash values of empty string. Actual parameters to be passed to the Keccak function (which expects 5 parameters) in order to achieve these outputs are as follows:
- For Keccak-n, where n is 224, 256, 384, or 512, n is the output length.
- As mentioned above, capacity is set to double the output length, per the submission to NIST.
- Since the submission was based on a state size of 1600 bits, rate is set to 1600 minus capacity (rate plus capacity must always equal state size, so specifying any two implies the third).
- The message is encoded as a hexadecimal string.
- The message length is four times the length of the hexadecimal string.
Keccak-224("") 0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd Keccak-256("") 0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470 Keccak-384("") 0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff Keccak-512("") 0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e
Even a small change in the message will (with overwhelming probability) result in a mostly different hash, owing to the avalanche effect. For example, adding a period to the end of the sentence:
Keccak-224("The quick brown fox jumps over the lazy dog") 0x 310aee6b30c47350576ac2873fa89fd190cdc488442f3ef654cf23fe Keccak-224("The quick brown fox jumps over the lazy dog.") 0x c59d4eaeac728671c635ff645014e2afa935bebffdb5fbd207ffdeab
Keccak-256("The quick brown fox jumps over the lazy dog") 0x 4d741b6f1eb29cb2a9b9911c82f56fa8d73b04959d3d9d222895df6c0b28aa15 Keccak-256("The quick brown fox jumps over the lazy dog.") 0x 578951e24efd62a3d63a86f7cd19aaa53c898fe287d2552133220370240b572d
Keccak-384("The quick brown fox jumps over the lazy dog") 0x 283990fa9d5fb731d786c5bbee94ea4db4910f18c62c03d173fc0a5e494422e8a0b3da7574dae7fa0baf005e504063b3 Keccak-384("The quick brown fox jumps over the lazy dog.") 0x 9ad8e17325408eddb6edee6147f13856ad819bb7532668b605a24a2d958f88bd5c169e56dc4b2f89ffd325f6006d820b
Keccak-512("The quick brown fox jumps over the lazy dog") 0x d135bb84d0439dbac432247ee573a23ea7d3c9deb2a968eb31d47c4fb45f1ef4422d6c531b5b9bd6f449ebcc449ea94d0a8f05f62130fda612da53c79659f609 Keccak-512("The quick brown fox jumps over the lazy dog.") 0x ab7192d2b11f51c7dd744e7b3441febf397ca07bf812cceae122ca4ded6387889064f8db9230f173f6d1ab6e24b6e50f065b039f799f5592360a6558eb52d760
- "Tentative SHA-3 standard (FIPS XXX) development timeline". NIST. Retrieved 2013-05-27.
- "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition". NIST. Retrieved 2012-10-02.
- Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "The Keccak sponge function family: Specifications summary". Retrieved 2011-05-11.
- Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "Sponge Functions". Ecrypt Hash Workshop 2007.
- Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "On the Indifferentiability of the Sponge Construction". EuroCrypt 2008.
- Keccak implementation overview Version 3.2 http://keccak.noekeon.org/Keccak-implementation-3.2.pdf
- Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick (Aug. 2010), "Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations", NIST 2nd SHA-3 Candidate Conference: 12, retrieved 2011-02-18 Keccak is second only to Luffa, which did not advance to the final round.
- NIST, Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition, sections 22.214.171.124 (mentioning "tree mode"), 6.2 ("other features", mentioning authenticated encryption), and 7 (saying "extras" may be standardized in the future)
- John Kelsey. "SHA3, Past, Present, and Future". CHES 2013.
- "Keccak parameter changes for round 2".
- "Simplifying Keccak's padding rule for round 3".
- "Schneier on Security: Will Keccak = SHA-3?".
- "Yes, this is Keccak!".
- "A concrete proposal".
- The Keccak web site
- A Java implementation of Keccak
- A Cryptol implementation of Keccak
- VHDL source code developed by the Cryptographic Engineering Research Group (CERG) at George Mason University
- Erlang NIF implementation based on the NIST reference code
- Keccak implemented in PureBasic