This page uses content from Wikipedia and is licensed under CC BYSA.
Secure Hash Algorithm  

Concepts  
hash functions · SHA · DSA  
Main standards  
SHA0 · SHA1 · SHA2 · 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 
Rounds  24 
Speed  12.6 cpb on a typical x8664based machine for Keccakf[1600] plus XORing 1024 bits,^{[1]} which roughly corresponds to SHA3256. 
Best public cryptanalysis  
Preimage attack on Keccak512 reduced to 8 rounds, requiring 2^{511.5} time and 2^{508} memory^{[2]} Zerosum distinguishers exist for the full 24round Keccakf[1600], though they cannot be used to attack the hash function itself^{[3]} 
SHA3 (Secure Hash Algorithm 3) is the latest member of the Secure Hash Algorithm family of standards, released by NIST on August 5, 2015.^{[4]}^{[5]} The reference implementation source code was dedicated to public domain via CC0 waiver.^{[6]} Although part of the same series of standards, SHA3 is internally quite different from the MD5like structure of SHA1 and SHA2.
SHA3 is a subset of the broader cryptographic primitive family Keccak (/ˈkɛtʃæk/, or /ˈkɛtʃɑːk/),^{[7]}^{[8]} designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche, building upon RadioGatún. Keccak's authors have proposed additional uses for the function, not (yet) standardized by NIST, including a stream cipher, an authenticated encryption system, a "tree" hashing scheme for faster hashing on certain architectures,^{[9]}^{[10]} and AEAD ciphers Keyak and Ketje.^{[11]}^{[12]}
Keccak is based on a novel approach called sponge construction.^{[13]} Sponge construction is based on a wide random function or random permutation, and allows inputting ("absorbing" in sponge terminology) any amount of data, and outputting ("squeezing") any amount of data, while acting as a pseudorandom function with regard to all previous inputs. This leads to great flexibility.
NIST does not currently plan to withdraw SHA2 or remove it from the revised Secure Hash Standard. The purpose of SHA3 is that it can be directly substituted for SHA2 in current applications if necessary, and to significantly improve the robustness of NIST's overall hash algorithm toolkit.^{[14]}
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.^{[15]}
In 2006 NIST started to organize the NIST hash function competition to create a 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, SHA0 and SHA1,^{[16]} 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.^{[17]}
During the competition, entrants were permitted to "tweak" their algorithms to address issues that were discovered. Changes that have been made to Keccak are:^{[18]}^{[19]}
On October 2, 2012, Keccak was selected as the winner of the competition.^{[7]}
In 2014, the NIST published a draft FIPS 202 "SHA3 Standard: PermutationBased Hash and ExtendableOutput Functions".^{[20]} FIPS 202 was approved on August 5, 2015.^{[21]}
On August 5, 2015 NIST announced that SHA3 had become a hashing standard.^{[22]}
SHA3 uses the sponge construction,^{[13]}^{[23]} 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 using a permutation function f. In the "squeeze" phase, output blocks are read from the same subset of the state, alternated with the state transformation function f. The size of the part of the state that is written and read is called the "rate" (denoted r), and the size of the part that is untouched by input/output is called the "capacity" (denoted c). The capacity determines the security of the scheme. The maximum security level is half the capacity.
Given an input bit string N, a padding function pad, a permutation function f that operates on bit blocks of width b, a rate r and an output length d, we have capacity c = b − r and the sponge construction Z = sponge[f,pad,r](N,d), yielding a bit string Z of length d, works as follows:^{[24]}^{:18}
The fact that the internal state S contains c additional bits of information in addition to what is output to Z prevents the length extension attacks that SHA2, SHA1, MD5 and other hashes based on the Merkle–Damgård construction are susceptible to.
In SHA3, the state S consists of a 5 × 5 array of w = 64bit words, b = 5 × 5 × w = 5 × 5 × 64 = 1600 bits total. 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.^{[11]}^{[12]}
For SHA3224, SHA3256, SHA3384, and SHA3512 instances, r is greater than d, so there is no need for additional block permutations in the squeezing phase; the leading d bits of the state are the desired hash. However, SHAKE128 and SHAKE256 allow an arbitrary output length, which is useful in applications such as optimal asymmetric encryption padding.
To ensure the message can be evenly divided into rbit blocks, padding is required. SHA3 uses the pattern 10^{*}1 in its padding function: a 1 bit, followed by zero or more 0 bits (maximum r − 1) and a final 1 bit.
The maximum of r − 1 0 bits occurs when the last message block is r − 1 bits long. Then another block is added after the initial 1 bit, containing r − 1 0 bits before the final 1 bit.
The two 1 bits will be added even if the length of the message is already divisible by r.^{[24]}^{:5.1} In this case, another block is added to the message, containing a 1 bit, followed by a block of r − 2 0 bits and another 1 bit. This is necessary so that a message with length divisible by r ending in something that looks like padding does not produce the same hash as the message with those bits removed.
The initial 1 bit is required so messages differing only in a few additional 0 bits at the end do not produce the same hash.
The position of the final 1 bit indicates which rate r was used (multirate padding), which is required for the security proof to work for different hash variants. Without it, different hash variants of the same short message would be the same up to truncation.
The block transformation f, which is Keccakf[1600] for SHA3, is a permutation that uses xor, and and not operations, and is designed for easy implementation in both software and hardware.
It 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ℓ rounds of five steps, each individually very simple:
The speed of SHA3 hashing of long messages is dominated by the computation of f = Keccakf[1600] and XORing S with the extended P_{i}, an operation on b = 1600 bits. However, since the last c bits of the extended P_{i} are 0 anyway, and XOR with 0 is a noop, it is sufficient to perform XOR operations only for r bits (r = 1600 − 2 × 224 = 1152 bits for SHA3224, 1088 bits for SHA3256, 832 bits for SHA3384 and 576 bits for SHA3512). The lower r is (and, conversely, the higher c = b − r = 1600 − r), the less efficient but more secure the hashing becomes since fewer bits of the message can be XORed into the state (a quick operation) before each application of the computationally expensive f. The authors report the following speeds for software implementations of Keccakf[1600] plus XORing 1024 bits,^{[1]} which roughly corresponds to SHA3256:
For the exact SHA3256 on x8664, Bernstein measures 11.7–12.25 cpb depending on the CPU.^{[26]}^{:7} SHA3 has been criticized for being slow in software – SHA2512 is more than twice as fast as SHA3512 and SHA1 is more than three times as fast on an Intel Skylake processor clocked at 3.2 GHz.^{[27]} The authors have reacted to this criticism by suggesting to use SHAKE128 and SHAKE256 instead of SHA3256 and SHA3512, at the expense of cutting the preimage resistance in half (but while keeping the collision resistance). With this, performance is on par with SHA2256 and SHA2512. To further increase speed, the authors suggest using KangarooTwelve, a variant of Keccak with half the number of rounds (trading safety margin for speed) and using parallelizable tree hashing to exploit the availability of parallelism in the processor.
However, in hardware implementations, SHA3 is notably faster than all other finalists,^{[28]} and also faster than SHA2 and SHA1.^{[27]}
The NIST standard defines the following instances, for message M and output length d:^{[24]}^{:20,23}
Instance  Output size d 
rate r = block size 
capacity c  Definition  Security Strengths in Bits  

Collision  Preimage  2nd Preimage  
SHA3224(M)  224  1152  448  Keccak[448](M  01, 224)  112  224  224 
SHA3256(M)  256  1088  512  Keccak[512](M  01, 256)  128  256  256 
SHA3384(M)  384  832  768  Keccak[768](M  01, 384)  192  384  384 
SHA3512(M)  512  576  1024  Keccak[1024](M  01, 512)  256  512  512 
SHAKE128(M, d)  d  1344  256  Keccak[256](M  1111, d)  min(d/2,128)  ≥min(d,128)  min(d,128) 
SHAKE256(M, d)  d  1088  512  Keccak[512](M  1111, d)  min(d/2,256)  ≥min(d,256)  min(d,256) 
With the following definitions
Note that the appended postfixes are written as bit strings, not hexadecimal digits.
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 a 256 bit length and 128 bit overall security.
Note that all instances append some bits to the message, the rightmost of which represent the domain separation suffix. The purpose of this is to ensure that it is not possible to construct messages that produce the same hash output for different applications of the Keccak hash function. The following domain separation suffixes exist:^{[24]}^{[29]}
Suffix  Meaning 

...0  reserved for future use 
01  SHA3 
...11  RawSHAKE 
RawSHAKE is the basis for the Sakura coding for tree hashing, which has not been standardized yet. However, the SHAKE suffix has been carefully chosen so that it is forward compatible with Sakura. Sakura appends 0 for a chaining hop or 1 for a message, then 10^{*}0 for a nonfinal (inner) node or 1 for a final node, before it applies RawSHAKE. Sequential hashing corresponds to a hop tree with a single message node, which means that 11 is appended to the message before RawSHAKE is applied. Thus, the SHAKE XOFs append 1111 to the message, i.e., 1 for message, 1 for final node, and 11 for the RawSHAKE domain separation suffix.^{[29]}^{:16}
Since 10^{*}1 padding always adds at least two bits, in byte aligned libraries there are always six unused zero bits. Therefore, these appended extra bits never make the padded message longer.
There is a general result (Grover's algorithm) that quantum computers can perform a structured preimage attack in √2^{d} = 2^{d/2}, while a classical bruteforce attack needs 2^{d}. A structured preimage attack implies a second preimage attack^{[30]} and thus a collision attack. A quantum computer can also perform a birthday attack, thus break collision resistance, in ^{3}√2^{d} = 2^{d/3}^{[31]} (although that is disputed^{[32]}). Noting that the maximum strength can be c/2, this gives the following upper^{[33]} bounds on the quantum security of SHA3:
Instance  Security Strengths in Bits  

Collision (Brassard et al.) 
Collision (Bernstein) 
Preimage  2nd Preimage  
SHA3224(M)  74⅔  112  112  112 
SHA3256(M)  85⅓  128  128  128 
SHA3384(M)  128  192  192  192 
SHA3512(M)  170⅔  256  256  256 
SHAKE128(M, d)  min(d/3,128)  min(d/2,128)  ≥min(d/2,128)  min(d/2,128) 
SHAKE256(M, d)  min(d/3,256)  min(d/2,256)  ≥min(d/2,256)  min(d/2,256) 
It has been shown that the Merkle–Damgård construction, as used by SHA2, is collapsing and, by consequence, quantum collisionresistant,^{[34]} but for the sponge construction used by SHA3, the authors provide proofs only for the case that the block function f is not efficiently invertible; Keccakf[1600], however, is efficiently invertible, and so their proof does not apply.^{[35]}
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.^{[36]}^{[37]} The changes caused some turmoil.
The hash function competition called for hash functions at least as secure as the SHA2 instances. It means that a dbit output should have d/2bit resistance to collision attacks and dbit resistance to preimage attacks, the maximum achievable for d bits of output. Keccak's security proof allows an adjustable level of security based on a "capacity" c, providing c/2bit resistance to both collision and preimage attacks. To meet the original competition rules, Keccak's authors proposed c=2d. The announced change was to accept the same d/2bit security for all forms of attack and standardize c=d. This would have sped up Keccak by allowing an additional d bits of input to be hashed each iteration. However, the hash functions would not have been dropin replacements with the same preimage resistance as SHA2 anymore; it would have been cut in half, making it vulnerable to advances in quantum computing, which effectively would cut it in half once more.^{[30]}
In September 2013, Daniel J. Bernstein suggested on the NIST hashforum mailing list^{[38]} to strengthen the security to the 576bit capacity that was originally proposed as the default Keccak, in addition to and not included in the SHA3 specifications.^{[39]} This would have provided at least a SHA3224 and SHA3256 with the same preimage resistance as their SHA2 predecessors, but SHA3384 and SHA3512 would have had significantly less preimage resistance than theirs. In late September, the Keccak team responded by stating that they had proposed 128bit security by setting c = 256 as an option already in their SHA3 proposal.^{[40]} Although the reduced capacity was justifiable in their opinion, in the light of the negative response, they proposed raising the capacity to c = 512 bits for all instances. This would be as much as any previous standard up to the 256bit security level, while providing reasonable efficiency,^{[41]} but not the 384/512 bit preimage resistance offered by SHA2384/512. The authors tried to justify that with the claim that "claiming or relying on security strength levels above 256 bits is meaningless."
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.^{[42]}
Paul Crowley, a cryptographer and 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.^{[43]}
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.^{[44]} 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.^{[42]}
In response to the controversy, in November 2013 John Kelsey of NIST proposed to go back to the original c = 2d proposal for all SHA2 dropin replacement instances.^{[45]} These changes were confirmed in the April 2014 draft.^{[46]} This proposal was implemented in the final release standard in August 2015.^{[4]}
The reducedcapacity forms were published as SHAKE128 and SHAKE256, where the number indicates the security level and the number of bits of output is variable, but should be twice as large as the required collision resistance.
The following hash values are from NIST.gov:^{[47]}
SHA3224("") 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7 SHA3256("") a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a SHA3384("") 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004 SHA3512("") a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26 SHAKE128("", 256) 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26 SHAKE256("", 512) 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be
Changing a single bit causes 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
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 (Info) 
Capacity against length extension attacks 
Performance on Skylake (median cpb)^{[48]}  First Published  

long messages  8 bytes  
MD5 (as reference)  128  128 (4 × 32) 
512  Unlimited^{[49]}  64  And, Xor, Rot, Add (mod 2^{32}), Or  <64 (collisions found) 
0  4.99  55.00  1992  
SHA0  160  160 (5 × 32) 
512  2^{64} − 1  80  And, Xor, Rot, Add (mod 2^{32}), Or  <34 (collisions found) 
0  ≈ SHA1  ≈ SHA1  1993  
SHA1  <63 (collisions found^{[50]}) 
3.47  52.00  1995  
SHA2  SHA224 SHA256 
224 256 
256 (8 × 32) 
512  2^{64} − 1  64  And, Xor, Rot, Add (mod 2^{32}), Or, Shr  112 128 
32 0 
7.62 7.63 
84.50 85.25 
2004 2001 
SHA384 SHA512 
384 512 
512 (8 × 64) 
1024  2^{128} − 1  80  And, Xor, Rot, Add (mod 2^{64}), Or, Shr  192 256 
128 (≤ 384) 0 
5.12 5.06 
135.75 135.50 

SHA512/224 SHA512/256 
224 256 
112 128 
288 256 
≈ SHA384  ≈ SHA384  
SHA3  SHA3224 SHA3256 SHA3384 SHA3512 
224 256 384 512 
1600 (5 × 5 × 64) 
1152 1088 832 576 
Unlimited^{[51]}  24^{[52]}  And, Xor, Rot, Not  112 128 192 256 
448 512 768 1024 
8.12 8.59 11.06 15.88 
154.25 155.50 164.00 164.00 
2015 
SHAKE128 SHAKE256 
d (arbitrary) d (arbitrary) 
1344 1088 
min(d/2, 128) min(d/2, 256) 
256 512 
7.08 8.59 
155.25 155.50 
In the unlikely event that b is greater than 2^64, then only the loworder 64 bits of b are used.