SHA-3

SHA-3 is a subset of the broader cryptographic primitive family Keccak (/ˈkɛtʃæk/ or /ˈkɛtʃɑːk/),[8][9] 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,[10][11] and AEAD ciphers Keyak and Ketje.

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

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

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.

RadioGatún, a successor of PANAMA, was designed by Daemen, Peeters, and Van Assche, and was presented at the NIST Hash Workshop in 2006.

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

The announced change was to accept the same d/2-bit 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.

[29] In September 2013, Daniel J. Bernstein suggested on the NIST hash-forum mailing list[30] 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.

This would be as much as any previous standard up to the 256-bit security level, while providing reasonable efficiency,[33] but not the 384-/512-bit preimage resistance offered by SHA2-384 and SHA2-512.

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.

[34] He later retracted his earlier statement, saying: I misspoke when I wrote that NIST made "internal changes" to the algorithm.

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.

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

[12][13] 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.

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.

The block transformation f, which is Keccak-f[1600] for SHA-3, is a permutation that uses XOR, AND and NOT operations, and is designed for easy implementation in both software and hardware.

The basic block permutation function consists of 12 + 2ℓ rounds of five steps: 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 Pi, an operation on b = 1600 bits.

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,[1] which roughly corresponds to SHA3-256: For the exact SHA3-256 on x86-64, Bernstein measures 11.7–12.25 cpb depending on the CPU.

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 tree hashing: KangarooTwelve and MarsupilamiFourteen.

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.

[49] KangarooTwelve is a higher-performance reduced-round (from 24 to 12 rounds) version of Keccak which claims to have 128 bits of security[50] while having performance as high as 0.55 cycles per byte on a Skylake CPU.

[52] MarsupilamiFourteen, a slight variation on KangarooTwelve, uses 14 rounds of the Keccak permutation and claims 256 bits of security.

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

[6] In 2016, the Keccak team released a different construction called Farfalle construction, and Kravatte, an instance of Farfalle using the Keccak-p permutation,[53] as well as two authenticated encryption algorithms Kravatte-SANE and Kravatte-SANSE[54] RawSHAKE is the basis for the Sakura coding for tree hashing, which has not been standardized yet.

[46]: 16 There is a general result (Grover's algorithm) that quantum computers can perform a structured preimage attack in

, this gives the following upper[57] bounds on the quantum security of SHA-3: It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant,[58] 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.

ARM implementations can however be accelerated using SVE and SVE2 vector instructions; these are available in the Fujitsu A64FX CPU for instance.

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

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).