SHA3
General  

Designers  Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. 
First published  2015 
Series  (SHA0), SHA1, SHA2, SHA3 
Certification  FIPS PUB 202 
Detail  
Digest sizes  arbitrary 
Structure  sponge construction 
Speed  12.5 cpb on Core 2 [c=1024, r=576]. 
SHA3 (Secure Hash Algorithm 3), a subset of the cryptographic primitive family Keccak (/ˈkɛtʃæk/, or /kɛtʃɑːk/),^{[1]}^{[2]}^{[3]} is a cryptographic hash function designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche, building upon RadioGatún. SHA3 is a member of the Secure Hash Algorithm family. The SHA3 standard was released by NIST on August 5, 2015.^{[4]}^{[5]} The reference implementation source code was dedicated to public domain via CC0 waiver.^{[6]}
Contents
History
The Keccak algorithm is the work of Guido Bertoni, Joan Daemen (who also codesigned the Rijndael cipher with Vincent Rijmen), Michael Peeters, and Gilles Van Assche. It is based on earlier hash function designs PANAMA and RadioGatún. PANAMA was designed by Daemen and Craig Clapp in 1998. RadioGatún, a successor of PANAMA, was designed by Daemen, Peeters, and Van Assche, and was presented at the NIST Hash Workshop in 2006.^{[7]}
In 2006 NIST started to organize the NIST hash function competition to create new hash standard, SHA3. SHA3 is not meant to replace SHA2, as no significant attack on SHA2 has been demonstrated. Because of the successful attacks on MD5 and SHA0 and theoretical attacks on SHA1,^{[8]} NIST perceived a need for an alternative, dissimilar cryptographic hash, which became SHA3.
After a setup period, admissions were to be submitted by the end of 2008. Keccak was accepted as one of the 51 candidates. In July 2009, 14 algorithms were selected for the second round. Keccak advanced to the last round in December 2010.^{[9]}
During the competition, entrants were permitted to "tweak" their algorithms to address issues that were discovered. Changes that have been made to Keccak are:^{[10]}^{[11]}
 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 below.
 The rate r was increased to the security limit, rather than rounding down to the nearest power of 2.
On October 2, 2012, Keccak was selected as the winner of the competition.^{[1]}
In 2014, the NIST published a draft FIPS 202 "SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions".^{[12]} FIPS 202 was approved on August 5, 2015.^{[13]}
On August 5, 2015 NIST announced that SHA3 had become a hashing standard.^{[14]}
Design
SHA3 uses the sponge construction,^{[15]}^{[16]} in which data is "absorbed" into the sponge, then the result is "squeezed" out. In the absorbing phase, message blocks are XORed into a subset of the state, which is then transformed as a whole. In the "squeeze" phase, output blocks are read from the same subset of the state, alternated with state transformations.
The size of the part written and read is called "rate", and the part that is untouched by input/output is called "capacity". The capacity determines the security of the scheme. The maximum security level is half the capacity.
In SHA3, the state consists of a 5 × 5 array of 64bit words, 1600 bits total. The authors claim 12.5 cycles per byte^{[17]} on an Intel Core 2 CPU. However, in hardware implementations, it is notably faster than all other finalists.^{[18]}
Keccak's authors have proposed additional, notyetstandardized uses for the function, including an authenticated encryption system and a "tree" hash for faster hashing on certain architectures.^{[19]} Keccak is also defined for smaller powerof2 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 (from w = 8, 200 bits, to w = 32, 800 bits) can be used in practical, lightweight applications.^{[20]}^{[21]}
The block permutation
This is defined for any poweroftwo word size, w = 2^{ℓ} bits. The main SHA3 submission uses 64bit words, ℓ = 6.
The state can be considered to be a 5 × 5 × w array of bits. Let a[i][ j][k] be bit (5i + j) × w + k of the input, using a littleendian bit numbering convention and rowmajor indexing. I.e. i selects the row, j the column, and k the bit.
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 subrounds, each individually very simple:
 θ
 Compute the parity of each of the 5w (320, when w = 64) 5bit columns, and exclusiveor that into two nearby columns in a regular pattern. To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ parity(a[0...4][ j−1][k]) ⊕ parity(a[0...4][ 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[0][0] 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+3 j] ← a[i][ j].
 χ
 Bitwise combine along rows, using a ← a ⊕ (¬b & c). To be precise, a[i][ j][k] ← a[i][ j][k] ⊕ ¬a[i][ j+1][k] & a[i][ j+2][k]. This is the only nonlinear operation in SHA3.
 ι
 Exclusiveor a round constant into one word of the state. To be precise, in round n, for 0 ≤ m ≤ ℓ, a[0][0][2^{m}−1] is exclusiveORed with bit m + 7n of a degree8 LFSR sequence. This breaks the symmetry that is preserved by the other subrounds.
Hashing variablelength messages
To ensure the message can be evenly divided into rbit blocks, padding is required. Keccak uses the 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 for the security proof to work for sponges of different rates, that is, different hash variants (multirate padding). Without it, different hash variants of the same short message would be the same up to truncation.
To compute a hash, initialize the state to 0, pad the input, and break it into rbit 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 desired number of bits n is squeezed. For the SHA3 instances, r is always greater than n, thus there is never a need for additional block permutations in the squeezing phase. The leading n bits of the state are the desired hash. However, arbitrary output length may be useful in applications such as optimal asymmetric encryption padding.
Instances
The NIST standard defines the following instances.
Keccak[capacity](M, d) is defined as the sponge construction using Keccakf[1600, capacity], message M and output length d. Note, that the appended postfixes are written as bit strings, not hexadecimal digits.
Instance  Definition 

SHA3224(M)  Keccak[448](M01, 224) 
SHA3256(M)  Keccak[512](M01, 256) 
SHA3384(M)  Keccak[768](M01, 384) 
SHA3512(M)  Keccak[1024](M01, 512) 
SHAKE128(M, d)  Keccak[256](M1111, d) 
SHAKE256(M, d)  Keccak[512](M1111, d) 
The SHA3 instances are the dropin replacements for SHA2, with identical security claims. SHAKE instances are so called XOF's, Extendable Output Functions. For example, SHAKE128(M, 256) can be used as a hash function with 128 bit overall security.
Note that all instances append some bits to the message. Since 10^{*}1 padding always adds at least two bits, in byte aligned libraries we always have six unused zero bits. Therefore, these appended extra bits never make the padded message longer.
NIST announcement controversy
In February 2013 at the RSA Conference, and then in August 2013 at CHES, NIST announced they would select different values for the capacity, i.e. the security parameter, for the SHA3 standard, compared to the submission.^{[22]}^{[23]} The changes caused some turmoil.
In September 2013, Daniel J. Bernstein suggested on the NIST hashforum mailing list^{[24]} to strengthen the security to the 576bit capacity that was originally proposed as the default Keccak.^{[25]} In late September, the Keccak team responded by stating that they proposed 128bit security by setting c = 256 as an option already in their SHA3 proposal.^{[26]} However, in the light of the negative response from the cryptographic community, they proposed raising the capacity to 512 bits for all instances.^{[27]}
In early October 2013, Bruce Schneier criticized NIST's 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.^{[28]}
Paul Crowley, a senior developer at an independent software development company, expressed his support of the decision, saying that Keccak is supposed to be tunable and there is no reason for different security levels within one primitive. He also added:
Yes, it’s a bit of a shame for the competition that they demanded a certain security level for entrants, then went to publish a standard with a different one. But there’s nothing that can be done to fix that now, except reopening the competition. Demanding that they stick to their mistake doesn’t improve things for anyone.^{[29]}
There was also some confusion that internal changes were made to Keccak. The Keccak team clarified this, stating that NIST's proposal for SHA3 is a subset of the Keccak family, for which one can generate test vectors using their reference code submitted to the contest, and that this proposal was the result of a series of discussions between them and the NIST hash team.^{[30]} Also, Bruce Schneier corrected his earlier statement, saying:
I misspoke when I wrote that NIST made "internal changes" to the algorithm. That was sloppy of me. The Keccak permutation remains unchanged. What NIST proposed was reducing the hash function's capacity in the name of performance. One of Keccak's nice features is that it's highly tunable.^{[28]}
In response to the controversy, in November 2013 John Kelsey of NIST proposed to go back to the original c = 2n proposal for all SHA2 dropin replacement instances.^{[31]} These changes were confirmed in the April 2014 draft.^{[32]} This proposal was implemented in the final release standard in August 2015.^{[4]}
Examples of SHA3 variants
Hash values are from ^{[33]}
SHA3224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
Changing a single bit results in each bit in the output to change with 50% probability, demonstrating an avalanche effect:
SHAKE128("The quick brown fox jumps over the lazy dog", 256) f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e SHAKE128("The quick brown fox jumps over the lazy dof", 256) 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c
Comparison of SHA functions
In the table below, internal state means the number of bits that are carried over to the next block.
Algorithm and variant  Output size (bits) 
Internal state size (bits) 
Block size (bits) 
Max message size (bits) 
Rounds  Operations  Security (bits) 
Example performance^{[35]} (MiB/s) 


MD5 (as reference)  128  128 (4 × 32) 
512  Unlimited^{[36]}  64  And, Xor, Rot, Add (mod 2^{32}), Or  <64 (collisions found) 
335  
SHA0  160  160 (5 × 32) 
512  2^{64} − 1  80  And, Xor, Rot, Add (mod 2^{32}), Or  <80 (collisions found) 
  
SHA1  160  160 (5 × 32) 
512  2^{64} − 1  80  <80 (theoretical attack^{[37]}) 
192  
SHA2  SHA224 SHA256 
224 256 
256 (8 × 32) 
512  2^{64} − 1  64  And, Xor, Rot, Add (mod 2^{32}), Or, Shr  112 128 
139 
SHA384 SHA512 SHA512/224 SHA512/256 
384 512 224 256 
512 (8 × 64) 
1024  2^{128} − 1  80  And, Xor, Rot, Add (mod 2^{64}), Or, Shr  192 256 112 128 
154  
SHA3  SHA3224 SHA3256 SHA3384 SHA3512 
224 256 384 512 
1600 (5 × 5 × 64) 
1152 1088 832 576 
Unlimited^{[38]}  24^{[39]}  And, Xor, Rot, Not  112 128 192 256 
 
SHAKE128 SHAKE256 
d (arbitrary) d (arbitrary) 
1344 1088 
min(d/2, 128) min(d/2, 256) 
 
References
 ↑ ^{1.0} ^{1.1} "NIST Selects Winner of Secure Hash Algorithm (SHA3) Competition". NIST. 20121002. Retrieved 20121002.
 ↑ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "The Keccak sponge function family: Specifications summary". Retrieved 20110511.
 ↑ "Keccak: The New SHA3 Encryption Standard". Dr. Dobbs.
 ↑ ^{4.0} ^{4.1} http://www.nist.gov/itl/csd/201508_sha3.cfm
 ↑ http://www.nist.gov/manuscriptpublicationsearch.cfm?pub_id=919061
 ↑ KeccakReferenceAndOptimized3.2.zip mainReference.c "The Keccak sponge function, designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. For more information, feedback or questions, please refer to our website: http://keccak.noekeon.org/Implementation by the designers, hereby denoted as "the implementer". To the extent possible under law, the implementer has waived all copyright and related or neighboring rights to the source code in this file. http://creativecommons.org/publicdomain/zero/1.0/"
 ↑ "The road from Panama to Keccak via RadioGatun" (PDF).
 ↑ Stevens, Marc. "Cryptanalysis of MD5 & SHA1" (PDF). Retrieved 28 January 2015.
 ↑ "NIST Computer Security Division  The SHA3 Cryptographic Hash Algorithm Competition, November 2007  October 2012".
 ↑ "Keccak parameter changes for round 2".
 ↑ "Simplifying Keccak's padding rule for round 3".
 ↑ "SHA3 standardization". NIST. Retrieved 20150416.
 ↑ National Institute of Standards and Technology (Aug 5, 2015). "Federal Information Processing Standards: PermutationBased Hash and ExtendableOutput Functions, etc.". Retrieved 5 Aug 2015.
 ↑ "Announcing Approval of Federal Information Processing Standard (FIPS) 202, SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions, and Revision of the Applicability Clause of FIPS 1804, Secure Hash Standard". 20150805.
 ↑ 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/Keccakimplementation3.2.pdf
 ↑ Guo, Xu; Huang, Sinan; Nazhandali, Leyla; Schaumont, Patrick (Aug 2010), "Fair and Comprehensive Performance Evaluation of 14 Second Round SHA3 ASIC Implementations" (PDF), NIST 2nd SHA3 Candidate Conference: 12, retrieved 20110218 Keccak is second only to Luffa, which did not advance to the final round.
 ↑ NIST, ThirdRound Report of the SHA3 Cryptographic Hash Algorithm Competition, sections 5.1.2.1 (mentioning "tree mode"), 6.2 ("other features", mentioning authenticated encryption), and 7 (saying "extras" may be standardized in the future)
 ↑ Daemen, Joan, CAESAR submission: Ketje v1 (PDF)
 ↑ Daemen, Joan, CAESAR submission: Keyak v1 (PDF)
 ↑ John Kelsey. "SHA3, Where We've Been, Where We're Going" (PDF). RSA Conference 2013.
 ↑ John Kelsey. "SHA3, Past, Present, and Future". CHES 2013.
 ↑ "NIST hash forum mailing list".
 ↑ "The Keccak SHA3 submission" (PDF). 20110114. Retrieved 20140208.
 ↑ "On 128bit security".
 ↑ "A concrete proposal".
 ↑ ^{28.0} ^{28.1} "Schneier on Security: Will Keccak = SHA3?".
 ↑ "LShift: Why I support the US Government making a cryptography standard weaker".
 ↑ "Yes, this is Keccak!".
 ↑ "Moving Forward with SHA3" (PDF).
 ↑ NIST Computer Security Division (CSD). "SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions" (PDF). NIST.
 ↑ "NIST.gov  Computer Security Division  Computer Security Resource Center".
 ↑ "Crypto++ 5.6.0 Benchmarks". Retrieved 20130613.
 ↑ Found on an AMD Opteron 8354 2.2 GHz processor running 64bit Linux^{[34]}
 ↑ "The MD5 MessageDigest Algorithm". Retrieved 20160418.
 ↑ "The SHAppening: freestart collisions for SHA1". Retrieved 20151105.
 ↑ "The Sponge Functions Corner". Retrieved 20160127.
 ↑ "The Keccak sponge function family". Retrieved 20160127.