World Library  
Flag as Inappropriate
Email this Article


Article Id: WHEBN0020394543
Reproduction Date:

Title: Sha-3  
Author: World Heritage Encyclopedia
Language: English
Subject: Comparison of cryptographic hash functions, SHA-1, NIST hash function competition, Panama (cryptography), Length extension attack
Collection: Nist Hash Function Competition
Publisher: World Heritage Encyclopedia


Designers Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche.
Certification SHA-3 winner
Digest sizes arbitrary
Structure sponge construction
Speed 12.5 cpb on Core 2 [r=1024,c=576].

SHA-3, a subset of the cryptographic primitive family Keccak (, or ),[3][4] is a cryptographic hash function designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche, building upon RadioGatún.


  • History 1
  • Design 2
  • The block permutation 3
  • Hashing variable-length messages 4
  • Tweaks 5
  • NIST announcement controversy 6
  • Examples of SHA-3 and Keccak variants 7
  • Comparison of SHA functions 8
  • References 9
  • External links 10


On October 2, 2012, Keccak was selected as the winner of the NIST hash function competition.[3] 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 and SHA-0 and theoretical attacks on SHA-1 and SHA-2,[5] NIST perceived a need for an alternative, dissimilar cryptographic hash, which became SHA-3.

In 2014 the NIST has published a draft FIPS 202 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions". The standardization process is in progress as of November 2014.[6]


SHA-3 uses the sponge construction[7][8] in which message blocks are XORed into a subset of the state, which is then transformed as a whole. 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[9] on an Intel Core 2 CPU. However, in hardware implementations it is notably faster than all other finalists.[10]

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.[11] 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 (from w = 8, 200 bits, to w = 32, 800 bits) can be used in practical, lightweight applications.[12][13]

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 (5i + j) × w + k of the input, using a little-endian bit numbering 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 5w (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] ← 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[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 \begin{pmatrix} i \\ j \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix}.
Permute the 25 words in a fixed pattern. a[j][2i+3j] ← a[i][j]
Bitwise combine along rows, using aa ⊕ (¬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 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[0][0][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

Illustration of the sponge construction
The sponge construction for hash functions. pi are input, zi are hashed output. The unused "capacity" c should be twice the desired resistance to collision or preimage attacks.

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 = 25wr 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. In April 2014, NIST published a draft that confirms these values.[1]

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"). The current draft includes adding bits 01 to the message before the applying the padding.[1] This provides domain separation from the SHAKEs, the other sponge modes included in the draft. For byte granularity data, this never increases the message size, since we have six unused bits anyways.

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 were permitted to "tweak" their algorithms to address issues that were discovered. Changes that have been made to Keccak are:[14][15]

  • 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 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 SHA-3 standard, compared to the submission.[16][17] The changes caused some turmoil.

In September 2013, on the NIST hash-forum mailing list,[18] Daniel J. Bernstein suggested strengthening the security to the 576-bit capacity that was originally proposed as the default Keccak.[19] In late September, the Keccak team responded by stating that they proposed 128-bit security by setting c=256 as an option already in their SHA-3 proposal.[20] But in the light of the uproar in the cryptographic community, they proposed raising the capacity to 512 bits for all instances.[21]

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.[22]

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 re-opening the competition. Demanding that they stick to their mistake doesn’t improve things for anyone.[23]

There was also some confusion that internal changes were made to Keccak. The Keccak team clarified this, stating that NIST's proposal for SHA-3 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.[24] 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.[22]

In November 2013, in the light of the uproar in the cryptographic community, John Kelsey of NIST proposed to go back to the original c=2n proposal for all SHA-2 drop-in replacement instances.[25] These changes were confirmed in the April, 2014 draft.[1]

Examples of SHA-3 and Keccak variants

Hash values of empty string. Actual parameters other than digest size are the same as the submission to NIST.

  • For SHA3-n and Keccak-n, where n is 224, 256, 384, or 512 and is the output length.
  • For SHA3-n, an additional two bits 01 are appended to the message before padding.
  • As mentioned above, capacity is set to double the output length, per the submission to NIST.
  • Rate is set to 1600 bits minus capacity (rate plus capacity must always equal state size, so specifying any two implies the third).
  • The digest is encoded as a hexadecimal string.
0x f71837502ba8e10837bdd8d365adb85591895602fc552b48b7390abd
0x c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470
0x 2c23146a63a29acf99e73b88f8c24eaa7dc60aa771780ccc006afbfa8fe2479b2dd2b21362337441ac12b515911957ff
0x 0eab42de4c3ceb9235fc91acffe746b29c29a8c366b7c60e4e67c466f36a4304c00fa9caf9d87976ba469bcbe06713b435f091ef2769fb160cdab33d3670680e
0x 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
0x a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
0x 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
0x a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26

Even a small change in the message will (with overwhelming probability) result in a mostly different hash, demonstrating the avalanche effect. For example, the RHASH implementation has published the following outputs with inputs differing only in a period:[26]

Using RHash implementation
SHA3-256("The quick brown fox jumps over the lazy dog")
0x 69070dda01975c8c120c3aada1b282394e7f032fa9cf32f4cb2259a0897dfc04
SHA3-256("The quick brown fox jumps over the lazy dog.")
0x a80f839cd4f83f6c3dafc87feae470045e4eb0d366397d5c6ce34ba1739f734d

The RHash Implementation is not the same as either the final SHA3 submission, nor is it like the FIPS 202 draft from April. RHash does not use the same bit order when absorbing bits. It does still match the same result published by NIST for the empty string case, because no bits are absorbed on an empty string. The final SHA3 submission for Keccak appends a 1 bit directly to start padding, while both the FIPS 202 draft and the RHash implementation use three bits "011" at the end of the message to begin padding.[27]

SHA-3 also includes two variable length Extendable-Output Functions, SHAKE128 and SHAKE256, with the numerical component determining their expected security level. These differ in both their capacity and padding rules. The capacity for SHAKE128 is 256 bits, and for SHAKE256 is 512 bits. An additional four bits 1111 are appended to the message before padding, and the output is truncated to the desired length. The first two appended bits are to differentiate SHAKE from SHA3-n, last two appended bits are for the Sakura coding scheme, and will be different for future tree hashing extensions of SHA-3.

Comparison of SHA functions

In the table below, internal state means the number of bits that are carried over to the next block.

Comparison of SHA functions []
Algorithm and variant Output size
Internal state size
Block size
Max message size
Rounds Operations Security
Example Performance[29]
MD5 (as reference) 128 128
(4× 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
(collisions found)
SHA-0 160 160
(5× 32)
512 264 − 1 80 And, Xor, Rot,
Add (mod 232),
(collisions found)
SHA-1 160 160
(5× 32)
512 264 − 1 80 <80
(theoretical attack[30] in 261)
SHA-2 SHA-224
(8× 32)
512 264 − 1 64 And, Xor, Rot,
Add (mod 232),
Or, Shr
(8× 64)
1024 2128 − 1 80 192
SHA-3 SHA3-224
(5×5× 64)
24 And, Xor, Rot,
d (arbitrary)
d (arbitrary)
min (d/2, 128)
min (d/2, 256)


  1. ^ a b c d e NIST Computer Security Division (CSD). "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions". NIST. 
  2. ^ "Tentative SHA-3 standard (FIPS XXX) development timeline".  
  3. ^ a b "NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition".  
  4. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "The Keccak sponge function family: Specifications summary". Retrieved 2011-05-11. 
  5. ^ Cryptographic hash function - WorldHeritage's Page on Cryptographic Hashes
  6. ^ "SHA-3 standardization". NIST. Retrieved 2014-11-03. 
  7. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "Sponge Functions". Ecrypt Hash Workshop 2007. 
  8. ^ Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. "On the Indifferentiability of the Sponge Construction". EuroCrypt 2008. 
  9. ^ Keccak implementation overview Version 3.2
  10. ^ 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.
  11. ^ NIST, Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition, sections (mentioning "tree mode"), 6.2 ("other features", mentioning authenticated encryption), and 7 (saying "extras" may be standardized in the future)
  12. ^ Daemen, Joan, CAESAR submission: Ketje v1 
  13. ^ Daemen, Joan, CAESAR submission: Keyak v1 
  14. ^ "Keccak parameter changes for round 2". 
  15. ^ "Simplifying Keccak's padding rule for round 3". 
  16. ^ John Kelsey. "SHA3, Where We've Been, Where We're Going". RSA Conference 2013. 
  17. ^ John Kelsey. "SHA3, Past, Present, and Future". CHES 2013. 
  18. ^ "NIST hash forum mailing list". 
  19. ^ "The Keccak SHA-3 submission" ( 
  20. ^ "On 128-bit security". 
  21. ^ "A concrete proposal". 
  22. ^ a b "Schneier on Security: Will Keccak = SHA-3?". 
  23. ^ "LShift: Why I support the US Government making a cryptography standard weaker". 
  24. ^ "Yes, this is Keccak!". 
  25. ^ "Moving Forward with SHA-3". 
  26. ^ "RHash Implementation". GitHub. 
  27. ^ Bertoni, Guido; Daemen, Joan; Peeters, Miachel; Van Assche, Gilles. "SHA3 Submission Documentation". 
  28. ^ "Crypto++ 5.6.0 Benchmarks". Retrieved 2013-06-13. 
  29. ^ Found on an AMD Opteron 8354 2.2 GHz processor running 64-bit Linux[28]
  30. ^ "Cryptanalysis of MD5 & SHA-1" (PDF). Retrieved 2013-04-25. 

External links

  • The Keccak web site
  • A Cryptol implementation of Keccak
  • A Java 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
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.