View source for SHA-3

{{Short description|Set of cryptographic hash functions}}

{{Use American English|date=February 2020}}
{{Use mdy dates|date=February 2020}}

{{SHA-box}}
{{Infobox cryptographic hash function
| name           = SHA-3<br />(Keccak)
| image          =
| caption        =
<!-- General -->
| designers      = Guido Bertoni, [[Joan Daemen]], Michaël Peeters, and [[Gilles Van Assche|Gilles van Assche]].
| publish date = {{Start date and age|2016}}
| series         = ([[SHA-0]]), [[SHA-1]], [[SHA-2]], SHA-3
| derived from   =
| derived to     =
| related to     =
| certification  = [[Federal Information Processing Standard|FIPS]] PUB 202
<!-- Detail -->
| digest size    = arbitrary
| structure      = [[Sponge function|sponge construction]]
| speed          = 12.6 [[cycles per byte|cpb]] on a typical x86-64-based machine for Keccak-f[1600] plus XORing 1024 bits,<ref name="ksoftimpl"/> which roughly corresponds to SHA2-256.
| cryptanalysis  = Preimage attack on Keccak-512 reduced to 8 rounds, requiring 2<sup>511.5</sup> time and 2<sup>508</sup> memory.<ref>{{cite book |last1=Morawiecki |first1=Paweł |last2=Pieprzyk |first2=Josef |last3=Srebrny |first3=Marian |title=Fast Software Encryption |chapter=Rotational Cryptanalysis of Round-Reduced Keccak |editor1-last=Moriai |editor1-first=S |series=Fast Software Encryption Lecture Notes in Computer Science |date=2013 |volume=8424 |pages=241–262 |doi=10.1007/978-3-662-43933-3_13 |chapter-url=https://eprints.qut.edu.au/82454/2/__staffhome.qut.edu.au_staffgroupm%24_meaton_Desktop_Draft%20paper_Pieprzyk.pdf |language=en |url-status=live |archive-url=https://web.archive.org/web/20130108011253/https://eprint.iacr.org/2012/546.pdf |archive-date=2013-01-08 |access-date=2019-02-08 |isbn=978-3-662-43932-6 }}</ref>
Zero-sum distinguishers exist for the full 24-round Keccak-f[1600], though they cannot be used to attack the hash function itself<ref>{{cite web |url=https://keccak.team/files/Keccak-submission-3.pdf |title=The Keccak SHA-3 submission |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |last3=Peeters |first3=Michaël |last4=van Assche |first4=Giles |date=January 14, 2011 |website=keccak.team |url-status=live |archive-url=https://web.archive.org/web/20110819084908/http://keccak.noekeon.org/Keccak-submission-3.pdf |archive-date=August 19, 2011 |access-date=2023-03-27 }}</ref>
}}

'''SHA-3''' ('''Secure Hash Algorithm 3''') is the latest<ref>{{Cite web |last=Computer Security Division |first=Information Technology Laboratory |date=2017-01-04 |title=Hash Functions {{!}} CSRC {{!}} CSRC |url=https://csrc.nist.gov/projects/hash-functions |access-date=2024-04-19 |website=CSRC {{!}} NIST |language=EN-US}}</ref><!-- is there a source that says it is still the "latest" as of 2024?  If not, should change to "was the latest" ... "as of 2015", which is all the sources support --> member of the [[Secure Hash Algorithm]] family of standards, released by [[NIST]] on August 5, 2015.<ref name="nist.gov">{{cite web |url=https://csrc.nist.gov/projects/hash-functions |title=Hash Functions |date=2020-06-22 |publisher=[[NIST]] |access-date=2021-02-17}}</ref><ref name="fips202">{{Citation | mode=cs1 | id= Federal Information Processing Standard Publication 202 |url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf|title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions|author=((Information Technology Laboratory)) |publisher=[[National Institute of Standards and Technology]]|date=August 2015|doi=10.6028/NIST.FIPS.202|s2cid=64734386 |access-date=2020-02-29 }}</ref><ref>{{cite web|last=Dworkin|first=Morris J.|date=2015-08-04|title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions|url=https://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061|publisher=Federal Information Processing Standards (NIST FIPS)}}</ref> Although part of the same series of standards, SHA-3 is internally different from the [[MD5]]-like [[Davies-Meyer|structure]] of [[SHA-1]] and [[SHA-2]].

SHA-3 is a subset of the broader cryptographic primitive family '''Keccak''' ({{IPAc-en|ˈ|k|ɛ|tʃ|æ|k|}} or {{IPAc-en|ˈ|k|ɛ|tʃ|ɑː|k|}}),<ref name="nist" /><ref name="drdobbs">{{cite web|url=http://www.drdobbs.com/security/keccak-the-new-sha-3-encryption-standard/240154037|title=Keccak: The New SHA-3 Encryption Standard|last=Cruz|first=José R.C.|date=2013-05-07|website=Dr. Dobbs}}</ref> 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,<ref>{{cite web |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |last3=Peeters |first3=Michaël |last4=Van Assche |first4=Gilles |title=Keccak specifications summary |url=https://keccak.team/keccak_specs_summary.html |access-date=2023-03-27}}</ref><ref>{{Citation | mode=cs1 |url=https://nvlpubs.nist.gov/nistpubs/ir/2012/NIST.IR.7896.pdf|title=Third-Round Report of the SHA-3 Cryptographic Hash Algorithm Competition|date=November 2012|doi=10.6028/NIST.IR.7896|access-date=2020-02-29|last1=Chang|first1=Shu-jen|last2=Perlner|first2=Ray|last3=Burr|first3=William E.|last4=Sonmez Turan|first4=Meltem|last5=Kelsey|first5=John M.|last6=Paul|first6=Souradyuti|last7=Bassham|first7=Lawrence E.}} 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).</ref> and [[AEAD]] ciphers Keyak and Ketje.<ref name="ketje">{{Cite web|url=https://competitions.cr.yp.to/round1/ketjev1.pdf|title=CAESAR submission: Ketje v1|last1=Bertoni|first1=Guido|last2=Daemen|first2=Joan|date=2014-03-13|access-date=2020-02-29|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles|last5=Van Keer|first5=Ronny}}</ref><ref name="keyak">{{Cite web|url=https://competitions.cr.yp.to/round1/keyakv1.pdf|title=CAESAR submission: Keyak v1|last1=Bertoni|first1=Guido|last2=Daemen|first2=Joan|date=2014-03-13|access-date=2020-02-29|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles|last5=Van Keer|first5=Ronny}}</ref>

Keccak is based on a novel approach called [[Sponge function|sponge construction]].<ref name="sponge"/> Sponge construction is based on a wide random function or random [[Block cipher|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.

As of 2022, NIST does not plan to withdraw SHA-2 or remove it from the revised Secure Hash Standard.<ref>{{Cite web |last=Computer Security Division |first=Information Technology Laboratory |date=2022-12-14 |title=NIST Transitioning Away from SHA-1 for All Applications {{!}} CSRC |url=https://csrc.nist.gov/news/2022/nist-transitioning-away-from-sha-1-for-all-apps |access-date=2024-10-09 |website=CSRC {{!}} NIST |language=EN-US}}</ref> The purpose of SHA-3 is that it can be directly substituted for SHA-2 in current applications if necessary, and to significantly improve the robustness of NIST's overall hash algorithm toolkit.<ref name="FRnotice">{{cite web |title=Announcing Request for Candidate Algorithm Nominations for a New Cryptographic Hash Algorithm (SHA-3) Family [U.S. Federal Register Vol. 72 No. 212)] |url=http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf |date=November 2, 2007 |url-status=live |archive-url=https://web.archive.org/web/20110331175556/http://csrc.nist.gov/groups/ST/hash/documents/FR_Notice_Nov07.pdf |archive-date=March 31, 2011 |access-date=July 18, 2017 }}</ref>

For small message sizes, the creators of the Keccak algorithms and the SHA-3 functions suggest using the faster function [[#KangarooTwelve|KangarooTwelve]] with adjusted parameters and a new tree hashing mode without extra overhead.

==History==
The Keccak algorithm is the work of Guido Bertoni, [[Joan Daemen]] (who also co-designed the [[Rijndael]] cipher with [[Vincent Rijmen]]), Michaël 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.<ref>{{cite web|url=https://keccak.team/files/TheRoadFromPanamaToKeccak.pdf|title=The road from Panama to Keccak via RadioGatún|last1=Bertoni|first1=Guido|last2=Daemen|first2=Joan|last3=Peeters|first3=Michaël|last4=Van Assche|first4=Gilles|access-date=2023-03-27}}</ref> The [[reference implementation]] [[source code]] was dedicated to [[public domain]] via [[CC0]] [[waiver]].<ref>[https://keccak.team/obsolete/KeccakReferenceAndOptimized-3.2.zip KeccakReferenceAndOptimized-3.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{{dead link|date=April 2018 |bot=InternetArchiveBot |fix-attempted=yes }} 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. https://creativecommons.org/publicdomain/zero/1.0/"''</ref>

In 2006, [[NIST]] started to organize the [[NIST hash function competition]] to create a new hash standard, SHA-3. SHA-3 is not meant to replace [[SHA-2]], as no significant attack on SHA-2 has been publicly demonstrated {{Update inline|date=June 2023}}. Because of the successful attacks on [[MD5]], [[SHA-0]] and [[SHA-1]],<ref>{{cite web|url=https://shattered.io/static/shattered.pdf|title=The first collision for full SHA-1|last1=Stevens|first1=Marc|last2=Bursztein|first2=Elie|access-date=2017-02-23|last3=Karpman|first3=Pierre|last4=Albertini|first4=Ange|last5=Markov|first5=Yarik}}</ref><ref>{{cite web|last1=Leurent|first1=Gaëtan|last2=Peyrin|first2=Thomas|title= SHA-1 is a Shambles|url=https://sha-mbles.github.io/|access-date=8 January 2020}}</ref>
NIST perceived a need for an alternative, dissimilar cryptographic hash, which became SHA-3.

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.<ref>{{cite web|title=NIST Computer Security Division – The SHA-3 Cryptographic Hash Algorithm Competition, November 2007 – October 2012 |url=http://csrc.nist.gov/groups/ST/hash/sha-3/index.html|date=2017-01-04}}</ref>

During the competition, entrants were permitted to "tweak" their algorithms to address issues that were discovered. Changes that have been made to Keccak are:<ref>{{Cite web|url=https://keccak.team/2009/version_2.0.html|title=Keccak parameter changes for round 2|date=2009-09-22|website=Keccak Team|url-status=live|archive-url=https://web.archive.org/web/20171113003333/https://keccak.team/2009/version_2.0.html|archive-date=2017-11-13|access-date=2020-02-29}}</ref><ref>{{cite web|url=https://keccak.team/2011/version_3.0.html|title=Simplifying Keccak's padding rule for round 3|date=2011-01-17|website=Keccak Team|access-date=2023-03-27}}</ref>
* The number of [[Round (cryptography)|rounds]] was increased from {{nowrap|12 + ℓ}} to {{nowrap|12 + 2ℓ}} to be more conservative about security.
* The message padding was changed from a more complex scheme to the simple 10<sup>*</sup>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.<ref name="nist">{{cite web|url=https://www.nist.gov/itl/csd/sha-100212.cfm|title=NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition|date=2012-10-02|publisher=[[NIST]]|access-date=2012-10-02}}</ref>

In 2014, the NIST published a draft [[Federal Information Processing Standards|FIPS]] 202 "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions".<ref>{{cite web | url=http://csrc.nist.gov/groups/ST/hash/sha-3/sha-3_standardization.html | title=SHA-3 standardization | publisher=NIST | access-date=2015-04-16}}</ref> FIPS 202 was approved on August 5, 2015.<ref>{{cite web|url=https://federalregister.gov/a/2015-19181|title=Federal Information Processing Standards: Permutation-Based Hash and Extendable-Output Functions, etc.|author=National Institute of Standards and Technology|date=2015-08-05|access-date=2015-08-05}}</ref>

On August 5, 2015, NIST announced that SHA-3 had become a hashing standard.<ref>{{Cite news|url = https://www.federalregister.gov/articles/2015/08/05/2015-19181/announcing-approval-of-federal-information-processing-standard-fips-202-sha-3-standard|title = Announcing Approval of Federal Information Processing Standard (FIPS) 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, and Revision of the Applicability Clause of FIPS 180-4, Secure Hash Standard
 |date = 2015-08-05}}</ref>

===Weakening controversy===
In early 2013 NIST announced they would select different values for the "capacity", the overall strength vs. speed parameter, for the SHA-3 standard, compared to the submission.<ref name="rsa2013">{{cite web |author=Kelsey |first=John |title=SHA3, Where We've Been, Where We're Going |url=http://csrc.nist.gov/groups/ST/hash/sha-3/documents/burr_dimacs2013_presentation.pdf |publisher=RSA Conference 2013}}</ref><ref name="ches2013">{{cite web |author=Kelsey |first=John |title=SHA3, Past, Present, and Future |url=https://docs.google.com/file/d/0BzRYQSHuuMYOQXdHWkRiZXlURVE |publisher=CHES 2013}}</ref> The changes caused some turmoil.

The hash function competition called for hash functions at least as secure as the SHA-2 instances. It means that a ''d''-bit output should have ''d''/2-bit resistance to [[collision attack]]s and ''d''-bit resistance to [[preimage attack]]s, 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''/2-bit resistance to both collision and preimage attacks. To meet the original competition rules, Keccak's authors proposed {{nowrap|1=''c'' = 2''d''}}. The announced change was to accept the same ''d''/2-bit security for all forms of attack and standardize {{nowrap|1=''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 drop-in replacements with the same preimage resistance as SHA-2 any more; it would have been cut in half, making it vulnerable to advances in quantum computing, which effectively would cut it in half once more.<ref name=quantumsha3/>

In September 2013, [[Daniel J. Bernstein]] suggested on the [[NIST]] hash-forum mailing list<ref>{{cite web|title=NIST hash forum mailing list|url=http://csrc.nist.gov/groups/ST/hash/email_list.html|date=2017-01-04}}</ref> to strengthen the security to the 576-bit capacity that was originally proposed as the default Keccak, in addition to and not included in the SHA-3 specifications.<ref>{{cite web
| url=https://keccak.team/files/Keccak-submission-3.pdf
| title=The Keccak SHA-3 submission
| date=2011-01-14
| access-date=2023-03-27}}</ref> This would have provided at least a SHA3-224 and SHA3-256 with the same preimage resistance as their SHA-2 predecessors, but SHA3-384 and SHA3-512 would have had significantly less preimage resistance than their SHA-2 predecessors. In late September, the Keccak team responded by stating that they had proposed 128-bit security by setting {{nowrap|1=''c'' = 256}} as an option already in their SHA-3 proposal.<ref>{{cite web |title=On 128-bit security |url=https://keccak.team/2013/on_128bit_security.html |date=2013-10-02 |access-date=2023-03-27}}</ref> Although the reduced capacity was justifiable in their opinion, in the light of the negative response, they proposed raising the capacity to {{nowrap|1=''c'' = 512}} bits for all instances. This would be as much as any previous standard up to the 256-bit security level, while providing reasonable efficiency,<ref>{{cite web|url=https://keccak.team/2013/a_concrete_proposal.html|title=A concrete proposal|date=2013-10-02|access-date=2023-03-27}}</ref> but not the 384-/512-bit preimage resistance offered by SHA2-384 and SHA2-512. The authors stated 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:
{{blockquote|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.<ref name="schneier">{{cite web|title=Schneier on Security: Will Keccak = SHA-3? |url=https://www.schneier.com/blog/archives/2013/10/will_keccak_sha-3.html}}</ref>}} He later retracted his earlier statement, saying:
{{blockquote|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.<ref name="schneier" />}}

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:
{{blockquote|
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.<ref>{{cite web|title=LShift: Why I support the US Government making a cryptography standard weaker |url=http://www.lshift.net/blog/2013/10/01/why-i-support-the-us-government-making-a-cryptography-standard-weaker|last=Crowley|first=Paul|date=1 October 2013|url-status=usurped|archive-url=https://web.archive.org/web/20160324235504/http://www.lshift.net/blog/2013/10/01/why-i-support-the-us-government-making-a-cryptography-standard-weaker/|archive-date=24 March 2016}}</ref>}}

There was some confusion that internal changes may have been made to Keccak, which were cleared up by the original team, 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.<ref>{{cite web|title=Yes, this is Keccak! |url=https://keccak.team/2013/yes_this_is_keccak.html |date=2013-10-04 |access-date=2023-03-27}}</ref>

In response to the controversy, in November 2013 John Kelsey of NIST proposed to go back to the original {{nowrap|1=''c'' = 2''d''}} proposal for all SHA-2 drop-in replacement instances.<ref>{{cite web|title=Moving Forward with SHA-3|url=http://csrc.nist.gov/groups/ST/hash/sha-3/documents/kelsey-email-moving-forward-110113.pdf}}</ref> The reversion was confirmed in subsequent drafts<ref name="draft201404">{{cite web |url=http://csrc.nist.gov/publications/drafts/fips-202/fips_202_draft.pdf |title=SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions |publisher=NIST |author=NIST Computer Security Division (CSD)}}</ref> and in the final release.<ref name="nist.gov"/>

==Design==
[[Image:SpongeConstruction.svg|thumb|upright=1.35|right|alt=Illustration of the sponge construction |The sponge construction for hash functions. ''P<sub>i</sub>'' are input, ''Z<sub>i</sub>'' are hashed output. The unused "capacity" ''c'' should be twice the desired resistance to [[Collision attack|collision]] or [[preimage attack]]s.]]

SHA-3 uses the [[Sponge function|sponge construction]],<ref name="sponge">{{cite web |url=https://keccak.team/sponge_duplex.html |title=The sponge and duplex constructions |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |last3=Peeters |first3=Michaël |last4=van Assche |first4=Giles |access-date=2023-03-27}}</ref> in which data is "absorbed" into the sponge, then the result is "squeezed" out. In the absorbing phase, message blocks are [[Exclusive or|XOR]]ed into a subset of the state, which is then transformed as a whole using a [[pseudorandom permutation|permutation function]] (or [[pseudorandom function|transformation]]) <math>f</math>. In the "squeeze" phase, output blocks are read from the same subset of the state, alternated with the state transformation function <math>f</math>. The size of the part of the state that is written and read is called the "rate" (denoted <math>r</math>), and the size of the part that is untouched by input/output is called the "capacity" (denoted <math>c</math>). The capacity determines the security of the scheme. The maximum [[security level]] is half the capacity.

Given an input bit string <math>N</math>, a padding function <math>pad</math>, a permutation function <math>f</math> that operates on bit blocks of width <math>b</math>, a rate <math>r</math> and an output length <math>d</math>, we have capacity <math>c = b - r</math> and the sponge construction <math>Z = \text{sponge}[f,pad,r](N,d)</math>, yielding a bit string <math>Z</math> of length <math>d</math>, works as follows:<ref name="fips202"/>{{rp|18}}
* pad the input ''N'' using the pad function, yielding a padded bit string ''P'' with a length divisible by <math>r</math> (such that <math>n = \text{len}(P)/r</math> is an integer)
* break ''P'' into ''n'' consecutive ''r''-bit pieces ''P''<sub>0</sub>, ..., ''P''<sub>''n''−1</sub>
* initialize the state ''S'' to a string of ''b'' zero bits
* absorb the input into the state: for each block ''P''<sub>''i''</sub>:
** extend ''P''<sub>''i''</sub> at the end by a string of ''c'' zero bits, yielding one of length ''b''
** XOR that with ''S''
** apply the block permutation ''f'' to the result, yielding a new state ''S''
* initialize ''Z'' to be the empty string
* while the length of ''Z'' is less than ''d'':
** append the first ''r'' bits of ''S'' to ''Z''
** if ''Z'' is still less than ''d'' bits long, apply ''f'' to ''S'', yielding a new state ''S''
* truncate ''Z'' to ''d'' bits

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 attack]]s that SHA-2, SHA-1, MD5 and other hashes based on the [[Merkle–Damgård construction]] are susceptible to.

In SHA-3, the state ''S'' consists of a {{nowrap|5 × 5}} array of ''w''-bit words (with ''w'' = 64), ''b'' = 5 × 5 × ''w'' = 5 × 5 × 64 = 1600 bits total. Keccak is also defined for smaller power-of-2 word sizes ''w'' down to 1 bit (total state of 25 bits). Small state sizes can be used to test cryptanalytic attacks, and intermediate state sizes (from {{nowrap|1=''w'' = 8}}, 200 bits, to {{nowrap|1=''w'' = 32}}, 800 bits) can be used in practical, lightweight applications.<ref name="ketje"/><ref name="keyak"/>

For SHA3-224, SHA3-256, SHA3-384, and SHA3-512 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]].

==Padding==
To ensure the message can be evenly divided into ''r''-bit blocks, padding is required. SHA-3 uses the pattern 10...01 in its padding function: a 1 bit, followed by zero or more 0 bits (maximum {{math|''r'' − 1}}) and a final 1 bit.

The maximum of {{math|''r'' − 1}} zero bits occurs when the last message block is {{math|''r'' − 1}} bits long. Then another block is added after the initial 1 bit, containing {{math|''r'' − 1}} zero 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''.<ref name=fips202/>{{rp|5.1}} In this case, another block is added to the message, containing a 1 bit, followed by a block of {{math|''r'' − 2}} zero 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 (multi-rate 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 permutation==
The block transformation ''f'', which is Keccak-f[1600] for SHA-3, is a permutation that uses [[Bitwise operation#XOR|XOR]], [[Binary AND|AND]] and [[Binary NOT|NOT]] operations, and is designed for easy implementation in both software and hardware.

It is defined for any power-of-two [[Word (computer architecture)|word]] size, {{math|1=''w'' = 2<sup>''ℓ''</sup>}} bits. The main SHA-3 submission uses 64-bit words, {{math|1=''ℓ'' = 6}}.

The state can be considered to be a {{math|5 × 5 × ''w''}} array of bits. Let {{math|''a''[''i'']['' j''][''k'']}} be bit {{math|(5''i'' + ''j'') × ''w'' + ''k''}} of the input, using a [[little-endian]] bit numbering convention and [[row-major]] indexing.<!-- Note that this swaps the first two indexes relative to the description in the Keccak paper, which is column-major!--> I.e. {{mvar|i}} selects the row, {{mvar|j}} the column, and {{mvar|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 {{math|12 + 2''ℓ''}} rounds of five steps:
; {{mvar|θ}} (theta)
: Compute the [[Parity (mathematics)|parity]] of each of the {{math|5''w''}} (320, when {{math|1=''w'' = 64}}) 5-bit columns, and exclusive-or that into two nearby columns in a regular pattern. To be precise, {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''] ⊕ parity(a[0...4][''j''-1][''k'']) ⊕ parity(a[0...4][''j''+1][''k''−1])}}
; {{mvar|ρ}} (rho)
: [[Circular shift|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 {{math|0 ≤ ''t'' < 24}}, {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''−(''t''+1)(''t''+2)/2]}}, where <math>\begin{pmatrix} i \\ j \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 1 & 0 \end{pmatrix}^t \begin{pmatrix} 0 \\ 1 \end{pmatrix}</math>.
; {{mvar|π}} (pi)
: Permute the 25 words in a fixed pattern. {{math|''a''[3''i''+2''j''][''i''] ← ''a''['' i''][''j'']}}.
; {{mvar|χ}} (chi)
: Bitwise combine along rows, using {{math|''x'' ← ''x'' ⊕ (¬''y'' &amp; ''z'')}}. To be precise, {{math|''a''[''i'']['' j''][''k''] ← ''a''[''i'']['' j''][''k''] ⊕ (¬''a''[''i'']['' j''+''1''][''k''] &amp; ''a''[''i'']['' j''+''2''][''k''])}}. This is the only non-linear operation in SHA-3.
; {{mvar|ι}} (iota)
: Exclusive-or a round constant into one word of the state. To be precise, in round {{mvar|n}}, for {{math|0 ≤ ''m'' ≤ ''ℓ''}}, {{math|''a''[0][0][2<sup>''m''</sup>−1]}} is XORed with bit {{math|''m'' + 7''n''}} of a degree-8 [[LFSR]] sequence. This breaks the symmetry that is preserved by the other steps.

==Speed==
The speed of SHA-3 hashing of long messages is dominated by the computation of ''f'' = Keccak-f[1600] and XORing ''S'' with the extended ''P''<sub>i</sub>, an operation on ''b'' = 1600 bits. However, since the last ''c'' bits of the extended ''P''<sub>i</sub> are 0 anyway, and XOR with 0 is a NOP, it is sufficient to perform XOR operations only for ''r'' bits (''r'' = 1600 − 2 × 224 = 1152 bits for SHA3-224, 1088 bits for SHA3-256, 832 bits for SHA3-384 and 576 bits for SHA3-512). 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 Keccak-f[1600] plus XORing 1024 bits,<ref name="ksoftimpl">{{cite web |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |author2-link= Joan Daemen |last3=Peeters |first3=Michaël |last4=van Assche |first4=Gilles | author4-link= Gilles Van Assche |url=https://keccak.team/files/Keccak-implementation-3.2.pdf |title=Keccak implementation overview |date=2012-05-29 |page=25 |access-date=2023-03-27}}</ref> which roughly corresponds to SHA3-256:
*57.4 [[cycles per byte|cpb]] on IA-32, Intel Pentium 3<ref>"about 41 cycles/byte [...] represents a 40% speedup compared to an implementation using only 32-bit instructions". By formula <math>\frac1x\times 1.40 = \frac1{41}</math> we obtain <math>x=57.4</math></ref>
*41 cpb on IA-32+MMX, Intel Pentium 3
*20 cpb on IA-32+SSE, Intel Core 2 Duo or AMD Athlon 64
*12.6 cpb on a typical x86-64-based machine
*6–7 cpb on [[IA-64]]<ref name="ksoftimpl"/>
For the exact SHA3-256 on x86-64, Bernstein measures 11.7–12.25 cpb depending on the CPU.<ref>{{cite web|url=https://cr.yp.to/hash/sha3opt-20120104.pdf|title=Optimization failures in SHA-3 software|last=Bernstein|first=Daniel J.|date=2012-01-04|website=cr.yp.to|access-date=2020-02-29}}</ref>{{rp|7}} SHA-3 has been criticized for being slow on instruction set architectures (CPUs) which do not have instructions meant specially for computing Keccak functions faster – SHA2-512 is more than twice as fast as SHA3-512, and SHA-1 is more than three times as fast on an Intel Skylake processor clocked at 3.2&nbsp;GHz.<ref name=slow>{{cite web |url=https://keccak.team/2017/is_sha3_slow.html |title=Is SHA-3 slow? |date=2017-06-12 |access-date=2023-03-27}}</ref> The authors have reacted to this criticism by suggesting to use SHAKE128 and SHAKE256 instead of SHA3-256 and SHA3-512, at the expense of cutting the preimage resistance in half (but while keeping the collision resistance). With this, performance is on par with SHA2-256 and SHA2-512.

However, in [[Application-specific integrated circuit|hardware implementations]], SHA-3 is notably faster than all other finalists,<ref>{{Citation |title=Fair and Comprehensive Performance Evaluation of 14 Second Round SHA-3 ASIC Implementations |url=http://csrc.nist.gov/groups/ST/hash/sha-3/Round2/Aug2010/documents/papers/SCHAUMONT_SHA3.pdf |first1=Xu |last1=Guo |first2=Sinan |last2=Huang |first3=Leyla |last3=Nazhandali |first4=Patrick |last4=Schaumont |journal=NIST 2nd SHA-3 Candidate Conference |date=Aug 2010 |access-date=2011-02-18 |page=12}} Keccak is second only to Luffa, which did not advance to the final round.</ref> and also faster than SHA-2 and SHA-1.<ref name=slow/>

As of 2018, ARM's ARMv8<ref>ARM corporation, ARM architecture reference manual ARMv8, for ARMv8-A architecture profile, document ARM DDI 0487C.a (ID121917), https://www.arm.com</ref> architecture includes special instructions which enable Keccak algorithms to execute faster and IBM's [[z/Architecture]]<ref>http://publibfp.dhe.ibm.com/epubs/pdf/dz9zr011.pdf p. 672</ref> includes a complete implementation of SHA-3 and SHAKE in a single instruction. There have also been extension proposals for [[RISC-V]] to add Keccak-specific instructions.<ref>{{cite journal | url=https://ieeexplore.ieee.org/document/7918507 | doi=10.1109/TC.2017.2700795 | title=Vector Instruction Set Extensions for Efficient Computation of <sc>Keccak</sc> | date=2017 | last1=Rawat | first1=Hemendra | last2=Schaumont | first2=Patrick | journal=IEEE Transactions on Computers | volume=66 | issue=10 | pages=1778–1789 }}</ref>

==Instances==

The NIST standard defines the following instances, for message ''M'' and output length ''d'':<ref name=fips202/>{{rp|20,23}}

{| class="wikitable"
! rowspan="2" | Instance
! rowspan="2" | Output<br />size ''d''
! rowspan="2" | Rate ''r''<br />= block size
! rowspan="2" | Capacity ''c''
! rowspan="2" | Definition
! colspan="3" | Security strength in bits of resistance against
|-
! Collision !! Preimage !! 2nd preimage
|-
| SHA3-224(''M'') || 224 ||1152||448|| Keccak[448](''M'' {{pipe}}{{pipe}} 01, 224) || 112 || 224 || 224
|-
| SHA3-256(''M'') || 256 ||1088||512|| Keccak[512](''M'' {{pipe}}{{pipe}} 01, 256) || 128 || 256 || 256
|-
| SHA3-384(''M'') || 384 ||832||768|| Keccak[768](''M'' {{pipe}}{{pipe}} 01, 384) || 192 || 384 || 384
|-
| SHA3-512(''M'') || 512 ||576||1024|| Keccak[1024](''M'' {{pipe}}{{pipe}} 01, 512) || 256 || 512 || 512
|-
| SHAKE128(''M'', ''d'') || ''d'' || 1344||256||Keccak[256](''M'' {{pipe}}{{pipe}} 1111, ''d'') || min(''d''/2,128)||&ge;min(''d'',128)||min(''d'',128)
|-
| SHAKE256(''M'', ''d'') || ''d'' ||1088||512|| Keccak[512](''M'' {{pipe}}{{pipe}} 1111, ''d'') || min(''d''/2,256)||&ge;min(''d'',256)||min(''d'',256)
|}

With the following definitions
* Keccak[''c''](''N'', ''d'') = sponge[Keccak-f[1600], pad10<sup>*</sup>1, ''r''](''N'', ''d'')<ref name=fips202/>{{rp|20}} 
* Keccak-f[1600] = Keccak-p[1600, 24]<ref name=fips202/>{{rp|17}}
* ''c'' is the capacity
* ''r'' is the rate = 1600 − ''c''
* ''N'' is the input bit string

SHA-3 instances are drop-in replacements for SHA-2, intended to have identical security properties.

SHAKE will generate as many bits from its sponge as requested, thus being [[extendable-output function]]s (XOFs). For example, SHAKE128(M, 256) can be used as a hash function with a 256 character bitstream with 128-bit security strength. Arbitrarily large lengths can be used as pseudo-random number generators. Alternately, SHAKE256(M, 128) can be used as a hash function with a 128-bit length and 128-bit resistance.<ref name="fips202"/>

All instances append some bits to the message, the rightmost of which represent the [[Domain separation (cryptography)|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:<ref name="fips202"/><ref name="sakura">{{cite web|url=https://keccak.team/files/Sakura.pdf|title=Sakura: A Flexible Coding for Tree Hashing|date=2014|website=Keccak Team|access-date=2020-02-29}}</ref>

{| class="wikitable"
|-
! Suffix !! Meaning
|-
| style="text-align: right;" | ...0 || reserved for future use
|-
| style="text-align: right;" | 01 || SHA-3
|-
| style="text-align: right;" | ...11 || RawSHAKE
|-
| style="text-align: right;" | 1111 || SHAKE
|}

== Additional instances ==

In December 2016 [[NIST]] published a new document, NIST SP.800-185,<ref>[http://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-185.pdf SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash] {{PD-notice}}</ref> describing additional SHA-3-derived functions:

{| class="wikitable"
! Instance !! Description
|-
| cSHAKE128(''X'', ''L'', ''N'', ''S'') ||rowspan="2" |A version of SHAKE supporting explicit domain separation via customization parameters.
|-
| cSHAKE256(''X'', ''L'', ''N'', ''S'')
|-
| KMAC128(''K'', ''X'', ''L'', ''S'') ||rowspan="4" |A [[keyed hash function]] based on Keccak. Can also be used without a key as a regular hash function.
|-
| KMAC256(''K'', ''X'', ''L'', ''S'')
|-
| KMACXOF128(''K'', ''X'', ''L'', ''S'')
|-
| KMACXOF256(''K'', ''X'', ''L'', ''S'')
|-
| TupleHash128(''X'', ''L'', ''S'') ||rowspan="4" |A function for hashing [[tuple]]s of strings. The output of this function depends on both the contents and the sequence of input strings.
|-
| TupleHash256(''X'', ''L'', ''S'')
|-
| TupleHashXOF128(''X'', ''L'', ''S'')
|-
| TupleHashXOF256(''X'', ''L'', ''S'')
|-
| ParallelHash128(''X'', ''B'', ''L'', ''S'') ||rowspan="4" |A function designed to exploit parallelism in modern processors for faster hashing. Unlike KangarooTwelve, does not use reduced-round Keccak.
|-
| ParallelHash256(''X'', ''B'', ''L'', ''S'')
|-
| ParallelHashXOF128(''X'', ''B'', ''L'', ''S'')
|-
| {{nowrap|ParallelHashXOF256(''X'', ''B'', ''L'', ''S'')}}
|}
• X is the main input bit string. It may be of any length, including zero.

• L is an integer representing the requested output length in bits.

• N is a function-name bit string, used by NIST to define functions based on cSHAKE. When no function other than cSHAKE is desired, N is set to the empty string.

• S is a customization bit string. The user selects this string to define a variant of the function. When no customization is desired, S is set to the empty string.

• K is a key bit string of any length, including zero.

• B is the block size in bytes for parallel hashing. It may be any integer such that 0 < B < 2<sup>2040</sup>.

==Later developments==

=== KangarooTwelve ===

{{Infobox cryptographic hash function
| name           = KangarooTwelve
| image          =
| caption        =
<!-- General -->
| designers      = Guido Bertoni, [[Joan Daemen]], Michaël Peeters, [[Gilles Van Assche]], Ronny Van Keer, Benoît Viguier
| publish date = {{Start date and age|2016|08|10}}
| series         = 
| derived from   = Keccak
| derived to     =
| related to     =
| certification  = 
<!-- Detail -->
| digest size    = arbitrary
| structure      = [[Sponge function|sponge construction]] and tree hashing with kangaroo hopping
| rounds         = 12
| speed          = 0.51 [[cycles per byte|cpb]] on SkylakeX with AVX-512<ref>{{cite web|url=https://keccak.team/sw_performance.html|title=Software performance figures}}</ref>
| cryptanalysis  = Same as Keccak's
}}

In 2016 the same team that made the SHA-3 functions and the Keccak algorithm introduced faster reduced-rounds (reduced to 12 and 14 rounds, from the 24 in SHA-3) alternatives which can exploit the availability of parallel execution because of using [[Merkle tree|tree hashing]]: KangarooTwelve and MarsupilamiFourteen.<ref name="KangarooTwelveByKeccakTeam">{{cite web|url=https://keccak.team/kangarootwelve.html|title=Keccak Team: KangarooTwelve|publisher=Keccak Team}}</ref>

These functions differ from ParallelHash, the FIPS standardized Keccak-based parallelizable hash function, with regard to the parallelism, in that they are faster than ParallelHash for small message sizes.

The reduced number of rounds is justified by the huge cryptanalytic effort focused on Keccak which did not produce practical attacks on anything close to twelve-round Keccak. These higher-speed algorithms are not part of SHA-3 (as they are a later development), and thus are not FIPS compliant; but because they use the same Keccak permutation they are secure for as long as there are no attacks on SHA-3 reduced to 12 rounds.<ref name="KangarooTwelveByKeccakTeam"/>

KangarooTwelve is a higher-performance reduced-round (from 24 to 12 rounds) version of Keccak which claims to have 128 bits of security<ref name=KangarooTwelve>{{cite web|url=https://eprint.iacr.org/2016/770.pdf|publisher=[[International Association for Cryptologic Research]]|title=KangarooTwelve: fast hashing based on Keccak-p|year=2016}}</ref> while having performance as high as 0.55 [[cycles per byte]] on a [[Skylake (microarchitecture)|Skylake]] CPU.<ref name=KangarooTwelveSlides>{{cite web|url=https://keccak.team/files/K12atACNS.pdf|title=KangarooTwelve slides presented at ACNS 2018|publisher=Keccak Team}}</ref> This algorithm is an [[Internet Engineering Task Force|IETF]] [[Request for Comments|RFC]] draft.<ref>{{Cite news |title=draft-irtf-cfrg-kangarootwelve-00 – KangarooTwelve |newspaper=Ietf Datatracker |publisher=[[Internet Engineering Task Force|IETF]] |url=https://datatracker.ietf.org/doc/draft-irtf-cfrg-kangarootwelve/ |access-date=2020-01-17}}</ref>

MarsupilamiFourteen, a slight variation on KangarooTwelve, uses 14 rounds of the Keccak permutation and claims 256 bits of security. Note that 256-bit security is not more useful in practice than 128-bit security, but may be required by some standards.<ref name=KangarooTwelve /> 128 bits are already sufficient to defeat brute-force attacks on current hardware, so having 256-bit security does not add practical value, unless the user is worried about significant advancements in the speed of ''classical'' computers. For resistance against ''quantum'' computers, see below.

KangarooTwelve and MarsupilamiFourteen are Extendable-Output Functions, similar to SHAKE, therefore they generate closely related output for a common message with different output length (the longer output is an extension of the shorter output). Such property is not exhibited by hash functions such as SHA-3 or ParallelHash (except of XOF variants).<ref name="fips202" />

=== The Farfalle construction ===
In 2016, the Keccak team released a different construction called [[Farfalle construction]], and Kravatte, an instance of Farfalle using the Keccak-p permutation,<ref name="Kravatte">{{cite journal |last1=Bertoni |first1=Guido |last2=Daemen |first2=Joan |last3=Hoffert |first3=Seth |last4=Peeters |first4=Michaël |last5=Van Assche |first5=Gilles |last6=Van Keer |first6=Ronny |date=29 December 2016 |title=Farfalle: parallel permutation-based cryptography |url=https://eprint.iacr.org/2016/1188 |journal=Cryptology ePrint Archive}}</ref> as well as two authenticated encryption algorithms Kravatte-SANE and Kravatte-SANSE<ref name="KravatteSaneSanse">{{cite journal |url=https://eprint.iacr.org/2018/1012 |title=The authenticated encryption schemes Kravatte-SANE and Kravatte-SANSE |author=Guido Bertoni |author2=Joan Daemen |author3=Seth Hoffert |author4=Michaël Peeters |author5=Gilles Van Assche |author6=Ronny Van Keer |journal=Cryptology ePrint Archive |date=12 October 2018}}</ref>

=== Sakura tree hashing ===
RawSHAKE is the basis for the Sakura coding for tree hashing, which has not been standardized yet. Sakura uses a suffix of 1111 for single nodes, equivalent to SHAKE, and other generated suffixes depending on the shape of the tree.<ref name="sakura"/>{{rp|16}}

== Security against quantum attacks ==
There is a general result ([[Grover's algorithm]]) that quantum computers can perform a structured [[preimage attack]] in <math>\sqrt{2^d} = 2^{d/2}</math>, while a classical brute-force attack needs 2<sup>''d''</sup>. A structured preimage attack implies a second preimage attack<ref name=quantumsha3>{{cite web |url=http://cr.yp.to/hash/quantumsha3-20101112.pdf |title=Abstract|website=cr.yp.to}}</ref> and thus a [[collision attack]]. A quantum computer can also perform a [[birthday attack]], thus break collision resistance, in <math>\sqrt[3]{2^d} = 2^{d/3}</math><ref>{{cite book |title= Abstract|volume= 1380|pages= 163–169|doi= 10.1007/BFb0054319|chapter = Quantum cryptanalysis of hash and claw-free functions|series = Lecture Notes in Computer Science|year = 1998|last1 = Brassard|first1 = Gilles|last2= Høyer|first2= Peter|last3= Tapp|first3= Alain|isbn= 978-3-540-64275-6|arxiv= quant-ph/9705002|s2cid= 118940551}}</ref> (although that is disputed).<ref>{{cite web |url=http://cr.yp.to/hash/collisioncost-20090823.pdf |title= Cost Analysis |website=cr.yp.to}}</ref> Noting that the maximum strength can be <math>c/2</math>, this gives the following upper<ref>{{cite web |url=http://www.scottaaronson.com/papers/collision.pdf |title=Collision problem |website=scottaaronson.com}}</ref> bounds on the quantum security of SHA-3:

{| class="wikitable"
! rowspan="2" | Instance
! colspan="4" | Security strength in bits of resistance against
|-
! Collision<br />(Brassard et al.) !! Collision<br />(Bernstein) !! Preimage !! 2nd preimage
|-
| SHA3-224(''M'') || style="background: yellow;" | {{frac|74|2|3}} || 112 || 112 || 112
|-
| SHA3-256(''M'') || style="background: yellow;" | {{frac|85|1|3}} || 128 || 128 || 128
|-
| SHA3-384(''M'') || 128 || 192 || 192 || 192
|-
| SHA3-512(''M'') || {{frac|170|2|3}} || 256 || 256 || 256
|-
| SHAKE128(''M'', ''d'') 
| min(''d''/3,128)
| min(''d''/2,128)
| &ge;min(''d''/2,128)
| min(''d''/2,128)
|-
| SHAKE256(''M'', ''d'') || min(''d''/3,256)||min(''d''/2,256)||&ge;min(''d''/2,256)||min(''d''/2,256)
|}

It has been shown that the [[Merkle–Damgård construction]], as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant,<ref>{{cite web |url=https://eprint.iacr.org/2016/508.pdf |title=Paper |website=eprint.iacr.org|year=2016 }}</ref> but for the sponge construction used by SHA-3, the authors provide proofs only for the case when the block function ''f'' is not efficiently invertible; Keccak-f[1600], however, is efficiently invertible, and so their proof does not apply.<ref>{{cite web |url=https://eprint.iacr.org/2017/282.pdf|title= Abstract |website=eprint.iacr.org|year= 2017 }}</ref>{{original research inline|certain=y|date=July 2023}}

==Examples of SHA-3 variants==
The following hash values are from NIST.gov:<ref>{{cite web|title=NIST.gov – Computer Security Division – Computer Security Resource Center|url=http://csrc.nist.gov/groups/ST/toolkit/examples.html#aHashing|date=2016-12-29}}</ref>

 <span style="color: green;">SHA3-224("")</span>
 6b4e03423667dbb73b6e15454f0eb1abd4597f9a1b078e3f5b5a6bc7
 <span style="color: green;">SHA3-256("")</span>
 a7ffc6f8bf1ed76651c14756a061d662f580ff4de43b49fa82d80a4b80f8434a
 <span style="color: green;">SHA3-384("")</span>
 0c63a75b845e4f7d01107d852e4c2485c51a50aaaa94fc61995e71bbee983a2ac3713831264adb47fb6bd1e058d5f004
 <span style="color: green;">SHA3-512("")</span>
 a69f73cca23a9ac5c8b567dc185a756e97c982164fe25859e0d1dcc1475c80a615b2123af1f5f94c11e3e9402c3ac558f500199d95b6d3e301758586281dcd26
 <span style="color: green;">SHAKE128("", 256)</span>
 7f9c2ba4e88f827d616045507605853ed73b8093f6efbc88eb1a6eacfa66ef26
 <span style="color: green;">SHAKE256("", 512)</span>
 46b9dd2b0ba88d13233b3feb743eeb243fcd52ea62b81b82b50c27646ed5762fd75dc4ddd8c0f200cb05019d67b592f6fc821c49479ab48640292eacb3b7c4be

Changing a single bit causes each bit in the output to change with 50% probability, demonstrating an [[avalanche effect]]:

 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy dog", 256)</span>
 f4202e3c5852f9182a0430fd8144f0a74b95e7417ecae17db0f8cfeed0e3e66e
 <span style="color: green;">SHAKE128("The quick brown fox jumps over the lazy do<span style="color: red;">f</span>", 256)</span>
 853f4538be0db9621a6cea659a06c1107b1f83f02b13d18297bd39d7411cf10c

==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}}

Optimized implementation using [[AVX-512|AVX-512VL]] (i.e. from [[OpenSSL]], running on [[Skylake-X]] CPUs) of SHA3-256 do achieve about 6.4 cycles per byte for large messages,<ref>{{cite web |title=openssl/openssl – kecak1600-avx512vl.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-avx512vl.pl#L29 |access-date=2020-06-25 |website=GitHub |language=en}}</ref> and about 7.8 cycles per byte when using [[AVX2]] on [[Skylake (microarchitecture)|Skylake]] CPUs.<ref>{{cite web |date=November 2021 |title=openssl/openssl – keccak1600-avx2.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-avx2.pl#L115 |website=GitHub |language=en}}</ref> Performance on other x86, Power and ARM CPUs depending on instructions used, and exact CPU model varies from about 8 to 15 cycles per byte,<ref>{{cite web |title=openssl/openssl – keccak1600-x86_64.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-x86_64.pl |access-date=2020-06-25 |website=GitHub |language=en}}</ref><ref>{{cite web |date=November 2021 |title=openssl/openssl – keccak1600-armv8.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-armv8.pl |website=GitHub |language=en}}</ref><ref>{{cite web |title=openssl/openssl – keccak1600-ppc64.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-ppc64.pl#L30 |access-date=2020-06-25 |website=GitHub |language=en}}</ref> with some older x86 CPUs up to 25–40 cycles per byte.<ref>{{cite web |title=openssl/openssl – kccak1600-mmx.pl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-mmx.pl#L45 |access-date=2020-06-25 |website=GitHub |language=en}}</ref>

== Implementations ==
Below is a list of cryptography libraries that support SHA-3:

* [[Rust (programming language)|Rust's]] [https://docs.rs/sha3 sha3]
* [[Botan (programming library)|Botan]]
* [[Bouncy Castle (cryptography)|Bouncy Castle]]
* [[Crypto++]]
* [[Libgcrypt]]
* [[Nettle (cryptographic library)|Nettle]]
* [[OpenSSL]]
* [[wolfSSL]]
* [https://github.com/miracl/MIRACL MIRACL Cryptographic SDK]
* [[Go (programming language)|Golang's]] [https://godoc.org/golang.org/x/crypto/sha3 x/crypto/sha3]
* [https://codeberg.org/maandree/libkeccak libkeccak]

== Hardware acceleration ==
[[Apple A13]] ARMv8 six-core [[System on a chip|SoC]] CPU cores have support<ref>{{cite web |title=llvm/llvm-project – AArch64.td |url=https://github.com/llvm/llvm-project/blob/c35ed40f4f1bd8afd709c5342b36f33c7c5b0fbd/llvm/lib/Target/AArch64/AArch64.td#L724 |access-date=2020-06-24 |website=GitHub |language=en}}</ref> for accelerating SHA-3 (and SHA-512) using specialized instructions (EOR3, RAX1, XAR, BCAX) from ARMv8.2-SHA crypto extension set.<ref>{{cite web |title=ARMv8 – ARM – WikiChip |url=https://en.wikichip.org/wiki/arm/armv8#ARMv8_Extensions_and_Processor_Features |access-date=2020-06-24 |website=en.wikichip.org |language=en}}</ref>

Some software libraries use [[Single instruction, multiple data|vectorization]] facilities of CPUs to accelerate usage of SHA-3. For example, Crypto++ can use [[SSE2]] on x86 for accelerating SHA3,<ref>{{cite web |title=weidai11/cryptopp |url=https://github.com/weidai11/cryptopp/blob/master/keccak_simd.cpp#L83 |website=GitHub |access-date=2020-06-25 |language=en}}</ref> and [[OpenSSL]] can use [[MMX (instruction set)|MMX]], [[AVX-512]] or [[AVX-512VL]] on many x86 systems too.<ref>{{cite web |title=openssl/openssl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-avx512vl.pl |website=GitHub |access-date=2020-06-25 |language=en}}</ref> Also [[POWER8]] CPUs implement 2x64-bit vector rotate, defined in PowerISA 2.07, which can accelerate SHA-3 implementations.<ref>{{cite web |title=openssl/openssl |url=https://github.com/openssl/openssl/blob/33388b44b67145af2181b1e9528c381c8ea0d1b6/crypto/sha/asm/keccak1600-ppc64.pl#L20 |website=GitHub |date=November 2021 |language=en}}</ref> Most implementations for ARM do not use [[ARM architecture#Advanced SIMD (Neon)|Neon]] vector instructions as [[Single instruction, single data|scalar code]] is faster. ARM implementations can however be accelerated using [[ARMv8-A SVE|SVE]] and SVE2 vector instructions; these are available in the [[Fujitsu A64FX]] CPU for instance.<ref>{{cite web |title=apple/llvm-project – lib/Target/AArch64/AArch64SVEInstrInfo.td |url=https://github.com/apple/llvm-project/blob/apple/master/llvm/lib/Target/AArch64/AArch64SVEInstrInfo.td#L2389 |access-date=2020-06-25 |website=GitHub |language=en}}</ref>

The IBM [[z/Architecture]] supports SHA-3 since 2017 as part of the Message-Security-Assist Extension 6.<ref>IBM z/Architecture Principles of Operation, publication number SA22-7832.  See KIMD and KLMD instructions in Chapter 7.</ref> The processors support a complete implementation of the entire SHA-3 and SHAKE algorithms via the KIMD and KLMD instructions using a hardware assist engine built into each core.

== Usage in protocols ==
[[Ethereum]] uses the Keccak-256 hash function (as per version 3 of the winning entry to the SHA-3 contest by Bertoni et al., which is different from the final SHA-3 specification).{{sfn|Solomon|2019|p=62}}

==See also==
*[[Ethash]] – another Keccak-based hash

==References==
{{Reflist}}

== Sources ==
* {{cite book|last=Solomon|first=M.G.|title=Ethereum For Dummies|publisher=Wiley|year=2019|isbn=978-1-119-47411-1|url=https://books.google.com/books?id=tHOPDwAAQBAJ&pg=PA62|access-date=2024-11-20}}

==External links==
* [https://keccak.team/ The Keccak web site]
* [https://www.nist.gov/publications/sha-3-standard-permutation-based-hash-and-extendable-output-functions SHA-3 Standard]

{{Cryptography navbox | hash}}

[[Category:NIST hash function competition]]
[[Category:Public-domain software with source code]]
[[Category:Extendable-output functions]]