SHA-3

SHA-3 (Keccak)
developer	Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche
Released	January 2011 (3rd version)
Derived from	RadioGatún (predecessor)
Certification	NIST SHA-3 standard
Length of the hash value (bit)	depending on the version 224, 256, 384, 512 or any
construction	Sponge construction
Round	24 (12 + 2ℓ, in SHA-3 is ℓ = 6)
Best known cryptanalysis
second preimage attack by Daniel J. Bernstein on 6 of 24 rounds of SHA3-512 2 506 function calls and space complexity 2 176 or 8 rounds with 2 511.5 calls and 2 508 square

SHA-3 is a cryptographic hash function that was developed by Guido Bertoni, Joan Daemen , Michaël Peeters and Gilles Van Assche under the name Keccak [ kɛtʃak ]. Keccak won the SHA-3 competition organized by the US NIST in 2012 and was standardized on August 5, 2015 as an alternative to SHA-2 .

Cryptographic hash functions are used, for example, for the secure storage of passwords and for digital signing . SHA-3 is the newest and most secure hash function in the SHA series .

history

In 2004 there were several breakthroughs in attacks against hash functions such as MD5 (practical collisions) and SHA-1 (theoretical collision with great effort), which were widely used at the time . Among other things, fundamental weaknesses of the Merkle-Damgård construction were found, which reduce the computational effort for certain attack scenarios (although not necessarily to the extent that the attack would be practically feasible). The SHA-2 family does exist, against which there have so far been no practice-relevant attacks, but these functions - like their predecessors MD4 , MD5 and SHA-1 - are Merkle-Damgård constructions with Davies-Meyer compression functions. It was feared that attacks on these precursors could be modified to attacks against SHA-2. If SHA-2 should also prove to be endangered or insecure, there would be no standardized cryptological hash function recognized as being secure. Therefore, it was decided to create a new standard that takes current research into account and is more future-proof than SHA-2.

Similar to the selection of AES ( Advanced Encryption Standard ) block encryption , NIST held a competition from November 2007 to October 2012. The hash functions submitted were required to hash messages up to an upper limit of at least bits and to support at least the four hash lengths 224, 256, 384 and 512 bits. The participating teams of cryptographers submitted 64 hash functions, 51 of which met the entry requirements and were accepted for round 1. After analyzing the security and performance in an open evaluation process in which cryptologists from all over the world took part, 14 candidates were selected for round two. ${\displaystyle 2^{64}-1}$

In each round of the competition, participants were allowed to make changes to their algorithms in order to react to the results of the analyzes. In the case of Keccak, the number of rounds of the permutation function has been increased from 18 to 24 for a greater safety margin and the length of the message blocks for some of the variants has been increased, thereby improving efficiency.

In December 2010 the five finalists were announced: BLAKE , Grøstl , JH , Keccak and Skein . Keccak was declared the winner on October 2, 2012 and has since been referred to as SHA-3.

SHA-3 has a high cryptographic security reserve and can also be implemented efficiently in hardware. The simple and elegant structure, which facilitates the cryptanalysis , is also advantageous . One point of criticism, however, is that the performance of the software implementation is rather low compared to the other finalists. The allegation has been made that NIST is paying too much attention to implementations in hardware.

functionality

Representation of the sponge construction

SHA-3 is a so-called sponge construction. A state vector of bits "absorbs" the message in blocks, which is then divided into blocks of bits. With each block, bits of the state vector are changed, after which the data in the state vector are mixed by a permutation function. This is a bijective mapping , it permutes the possible states of the vector in a pseudo-random way. ${\displaystyle b}$ ${\displaystyle r<b}$ ${\displaystyle r}$ ${\displaystyle f:\{0,1\}^{b}\rightarrow \{0,1\}^{b}}$ ${\displaystyle 2^{b}}$

Keccak uses a state vector initialized with 0 consisting of 25 words with each bit . The value is a parameter of the procedure. The state vector is thus bit long. The second parameter is the bit length of the desired hash value. In the variants submitted to the SHA-3 competition, and thus , and the length of the hash value is or . ${\displaystyle 2^{l}}$ ${\displaystyle l\in \{0,1,\ldots ,6\}}$ ${\displaystyle b=25\cdot 2^{l}}$ ${\displaystyle n}$ ${\displaystyle l=6}$ ${\displaystyle b=1600}$ ${\displaystyle n=224,256,384}$ ${\displaystyle 512}$

The message is lengthened to a multiple of bits by adding an end piece and then divided into blocks of length bits, with the third parameter of the method. The competition variants are each . The attached tail is made to bits having the value 0, which are framed by 1 bits: . The first 1-bit identifies the end of the message so that messages that only differ in terms of the number of 0-bits at the end are still different after the extension. The 1-bit at the end ensures that the variants with different hash lengths behave like completely different hash functions. It marks the end of the last block and is always in a different position since the message block length depends on the hash length. It therefore has different effects on the hash process. Otherwise, two (identical or different) messages could result in hash values, one of which is a starting part of the other. ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r=b-2n}$ ${\displaystyle 0}$ ${\displaystyle r-1}$ ${\displaystyle 100\ldots 01}$

The message blocks are now incorporated into the state vector one after the other. Each block is bit-by-bit XOR- linked with the bit of the state vector , and then the possible states of the state vector are permuted , which is done in a similar way to block encryption (with constant key). To do this, a round function is sometimes applied to the state vector (in the case of SHA-3, that is, times). This is designed according to the cryptological principles of confusion and diffusion and ensures that the permutation function completely mixes the state vector several times and changes it chaotically. ${\displaystyle r}$ ${\displaystyle 2^{b}}$ ${\displaystyle 12+2l}$ ${\displaystyle 24}$

After the last block has been incorporated, bits of the status vector are read out as a hash value, if is. Otherwise, the bits of the hash value are taken in several steps, a maximum of bits in each step, and in between the values ​​of the state vector are permuted as above. The overall process at a glance with the original message ( denotes the first bits of ): ${\displaystyle n}$ ${\displaystyle n\leq r}$ ${\displaystyle r}$ ${\displaystyle m}$ ${\displaystyle \operatorname {trunc} (x,n)}$ ${\displaystyle n}$ ${\displaystyle x}$

${\displaystyle m\,\|\,10^{j}1=m_{1}\,\|\,m_{2}\,\|\,\cdots \,\|\,m_{k};\quad |m_{i}|=r,\,j<r}$

${\displaystyle s_{0}=0^{b}}$

${\displaystyle s_{i}=f(s_{i-1}\oplus (m_{i}\,\|\,0^{b-r}));\quad i=1,2,\cdots ,k}$

${\displaystyle h=\operatorname {trunc} (s_{k},r)\,\|\,\operatorname {trunc} (f(s_{k}),r)\,\|\,\operatorname {trunc} (f(f(s_{k})),r)\,\|\,\cdots }$

${\displaystyle hash=\operatorname {trunc} (h,n)}$

The value is the so-called capacity, the size of the part of the state vector that remains unaffected when XORing with the message blocks and when the hash value is extracted. It can be proven that in sponge constructions with hash length bits, the security against collision attacks is bits and against archetype attacks , provided that the permutation of the state values cannot be distinguished from a random permutation . In order to be conservative with regard to security, the developers have set the capacity to twice the length of the hash value ( ), which achieves the highest possible security against any attack for a given (because of the birthday paradox , the security against collision attacks cannot be higher than Bit be). ${\displaystyle c=b-r}$ ${\displaystyle n}$ ${\displaystyle \min(n/2,c/2)}$ ${\displaystyle \min(n,c/2)}$ ${\displaystyle c=2n}$ ${\displaystyle n}$ ${\displaystyle n/2}$

Lap function

The round function consists of five successive operations, which were designated by the inventors with Greek letters . The words of the state vector are denoted by, by , and are each the new state vector after each operation. All indices are taken modulo 5 ( is ). means the bitwise XOR, bitwise negation , bitwise AND operation and a the bit rotation of order bit positions to higher-end. ${\displaystyle a_{i,j}}$ ${\displaystyle i,j\in \{0,1,2,3,4\}}$ ${\displaystyle {\overline {a}}_{i,j}}$ ${\displaystyle a_{2,-1}}$ ${\displaystyle a_{2,4}}$ ${\displaystyle \oplus }$ ${\displaystyle \neg }$ ${\displaystyle \&}$ ${\displaystyle \lll w}$ ${\displaystyle a}$ ${\displaystyle w}$

${\displaystyle \theta }$(Theta): linear mixing operation: XORing the parity bits of each 5-word column with the words of the neighboring columns

${\displaystyle p_{j}\,\leftarrow \,a_{0,j}\oplus a_{1,j}\oplus a_{2,j}\oplus a_{3,j}\oplus a_{4,j}}$

${\displaystyle {\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\oplus p_{j-1}\oplus (p_{j+1}\lll 1)}$

${\displaystyle \rho }$ (Rho): Rotate words of the state vector

${\displaystyle {\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\lll (w_{i,j}\,{\bmod {\,}}2^{l});\;w_{0,0}=0;\;w_{i,j}={\frac {(t+1)(t+2)}{2}};\;t\in \{0,\dots ,23\};}$

the indices result from the matrix equation ${\displaystyle i,j}$ ${\displaystyle {\binom {i}{j}}={\begin{pmatrix}3&2\\1&0\end{pmatrix}}^{t}\cdot {\binom {0}{1}}}$

${\displaystyle \pi }$ (Pi): Permute words of the state vector

${\displaystyle {\overline {a}}_{3i+2j,i}\,\leftarrow \,a_{i,j}}$

${\displaystyle \chi }$ (Chi): nonlinear operation

${\displaystyle {\overline {a}}_{i,j}\,\leftarrow \,a_{i,j}\oplus (\neg a_{i,j+1}\;\&\;a_{i,j+2})}$

${\displaystyle \iota }$(Iota): XORing the word with a round-dependent constant ${\displaystyle a_{0,0}}$

${\displaystyle {\overline {a}}_{0,0}\,\leftarrow \,a_{0,0}\oplus C_{r};\;r=0,1,\dots ,11+2l}$

The bit at position (with ) in is given by bits of the bit sequence which is generated by the following LFSR shown here in C (the remaining bits in the are 0): ${\displaystyle 2^{m}-1}$ ${\displaystyle 0\leq m<7}$ ${\displaystyle C_{r}}$ ${\displaystyle 7r+m}$ ${\displaystyle C_{r}}$

	unsigned lfsr() {
		static unsigned r = 1;
		unsigned b = r & 1;
		r <<= 1;
		if (r & 0x100) r ^= 0x171;
		return b;
	}

When a message block is accepted, the first 64 bits are XOR-linked in ascending order, i.e. the first bit with the least significant in . Then the following message bits are also adopted. The hash value is also taken at the end . ${\displaystyle a_{0,0}}$ ${\displaystyle a_{0,0}}$ ${\displaystyle a_{0,1},a_{0,2},\cdots ,a_{1,0},\cdots }$ ${\displaystyle a_{0,0},a_{0,1},\cdots }$

standardization

The NIST employee John Kelsey suggested in August 2013 at the “Workshop on Cryptographic Hardware and Embedded Systems 2013” ​​(CHES 2013) that only the two security levels 128 bit and 256 bit should be standardized. The capacity c should be reduced to 256 bits for the smaller variants SHA3-224 and SHA3-256 and to 512 bits for the two larger ones. This improves the execution speed because the message block length r is correspondingly larger and the number of message blocks to be processed is smaller. An archetype attack would still be at least as difficult as a collision attack, on which the change would have no effect.

Some researchers criticized this reduction in security and criticized the process of subsequently changing the winner of the competition so that it would no longer be the originally investigated algorithm. The Keccak authors, on the other hand, defended the proposed changes.

In response to the criticism, NIST decided against reducing the capacity of the four variants SHA3-224 to SHA3-512. This is ultimately unnecessary because the variants SHAKE128 and SHAKE256 have also been standardized with 256 or 512 bit capacity. With the exception of the hash length that can be freely selected by the user, they correspond to the proposed capacity-reduced versions and thus offer the same efficiency.

default

In August 2015, NIST standardized the following versions of SHA3 (all information in bits):

Surname	Hash length	Message block length r	Capacity c = 1600-r	Safety (collision)	Security (archetype)	Padding scheme
SHA3-224	224	1152	448	112	224	0110 * 1
SHA3-256	256	1088	512	128	256
SHA3-384	384	832	768	192	384
SHA3-512	512	576	1024	256	512
SHAKE128	variable (n)	1344	256	min (n / 2, 128)	min (n, 128)	111110 * 1
SHAKE256	variable (n)	1088	512	min (n / 2, 256)	min (n, 256)

The variants SHAKE128 and SHAKE256 are so-called extendable output functions (XOFs; functions with extendable output ). The length of the hash value is not fixed in advance, but any number of hash data can be extracted after the message has been incorporated into the data block. After every 1344 or 1088 bits are taken, the data block is permuted again, as described above. These variants work as cryptographically secure pseudo random number generators , with the hashed message as the seed.

So that the SHA3 and SHAKE variants have different hashes, the scheme with which the messages are expanded has been changed. With SHA3, the bit sequence 011 is appended and with SHAKE, however, 11111, before being padded with 0 bits and a 1 bit added at the end. This achieves a domain separation: After the expansion, you can see in the message in which of the two ways it was expanded. Two messages that are expanded in different ways then differ in each case. When choosing these padding methods, consideration was given to a later standardization of further hash processes based on Keccak (e.g. tree hash processes ).

This padding change has no effect on the efficiency if the message consists of whole bytes, which is almost always the case in practice. The message block length r is also a multiple of eight, and thus also the number of free bits in the last block. Either another message block has to be added for the padding bits anyway, or at least one byte is free in the last block that can completely accommodate the padding bits. Compared to the original Keccak padding, the number of message blocks does not increase in any case.

In December 2016, the NIST published a document in which other hash processes derived from SHA-3 are described. These are available in two versions, with 256 bit and 512 bit capacity:

• cSHAKE: enables explicit domain separation through an additionally entered string
• KMAC: Variant for Keyed-Hash Message Authentication
• KMACXOF: XOF version of KMAC with hash output that can be expanded as required (according to SHAKE)
• TupleHash and TupleHashXOF: hashes tuples with any number of strings, whereby different tuples are hashed differently, e.g. B. also ("ab", "c") and ("a", "bc") and ("a", "bc", "")
• ParallelHash and ParallelHashXOF: designed to better support the parallel computing capabilities of modern CPUs

Other variants

The developers at Keccak have also presented two tree hash processes called KangarooTwelve and MarsupilamiFourteen , which work with a permutation function reduced to 12 and 14 rounds, compared to 24 rounds for the other variants. In this way, they use Keccak's large safety reserve to improve efficiency.

safety

SHA-3 has a very high safety margin. The best known cryptanalysis can only break a version of SHA3-512 reduced to 8 (of 24) rounds, and that only with a completely unrealistic overhead of function calls and a storage space of . This is only 1.4 times more efficient than a brute force attack . ${\displaystyle 2^{511,5}}$ ${\displaystyle 2^{508}}$

It is possible to distinguish the state permutation with the full number of 24 rounds from a random permutation, but this requires, for example, function calls. This does not result in an attack on SHA-3 itself. ${\displaystyle 2^{1575}}$

Because only a part of the 1600 status bits is output (reduced by the capacity), SHA-3 is immune to an expansion attack in which the hash value of an unknown message that has been expanded is determined with knowledge of its hash value . ${\displaystyle h(N\,\|\,x)}$ ${\displaystyle x}$ ${\displaystyle N}$ ${\displaystyle h(N)}$

Web links

• Keccak's website
• The SHA-3 Zoo
• SHA-3 at NIST
• Specifications on the Keccak website

Individual evidence

1. ^ NIST's Policy on Hash Functions. NIST , Sep 28, 2012; archived from the original on June 9, 2011 ; accessed on March 28, 2013 (English).  
2. ^ SHA-3 Project. NIST , accessed August 10, 2020 . 
3. ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST , October 2, 2012, accessed October 3, 2012 . 
4. ↑ Mourad Gouicem: Comparison of seven SHA-3 candidates software implementations on smart cards. (PDF) October 2010, accessed on February 14, 2014 . 
5. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak sponge function family. January 27, 2011, accessed October 3, 2012 . 
6. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: The Keccak reference. January 14, 2011, accessed August 2, 2020 . 
7. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles van Assche: Cryptographic sponge functions. January 14, 2011, accessed on August 26, 2020 . 
8. ↑ Jon Kelsey: SHA3 Past, Present, and Future. Retrieved October 6, 2013 .  
9. ↑ John Kelsey, Bill Burr: SHA3, Where we've been, Where we're going. May 1, 2013, accessed July 18, 2020 .  
10. ↑ Fabian Scherschel: Cryptography: NIST allegedly wants to reduce the security of SHA-3. In: heise online. September 30, 2013, accessed September 30, 2013 . 
11. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche: Yes, this is Keccak! October 4, 2013, accessed July 18, 2020 .  
12. ↑ John Kelsey: Moving Forward with SHA-3. November 1, 2013, accessed July 18, 2020 .  
13. ↑ NIST Computer Security Division (CSD): SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. DRAFT FIPS PUB 202nd NIST, May 2014, accessed July 18, 2020 .  
14. ↑ http://www.nist.gov/itl/csd/201508_sha3.cfm
15. ↑ SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. FIPS PUB 202. National Institute of Standards and Technology (NIST), August 2015, accessed January 8, 2018 .  
16. ↑ John Kelsey, Shu-jen Chang, Ray Perlner: SHA-3 Derived Functions: cSHAKE, KMAC, TupleHash and ParallelHash. NIST Special Publication 800-185. NIST, October 2016, accessed July 15, 2020 .  
17. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche, Ronny Van Keer, Benoit Viguier: KangarooTwelve: fast hashing based on Keccak-p. Retrieved July 16, 2020 .  
18. ^ Daniel J. Bernstein: Second preimages for 6 (7? (8 ??)) rounds of Keccak? In: NIST mailing list. 2010, accessed on July 15, 2020 . 
19. ↑ Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles van Assche: The Keccak SHA-3 submission. January 14, 2011, accessed July 15, 2020 .