SHA-3
SHA-3 (Secure Hash Algorithm Version 3), also called Keccak, is a unidirectional function for generating digital prints of the selected length (the standard accepts 224, 256, 384 or 512 bits) from input data of any size, developed by a group of authors led by Yoan Dimen in 2008 and adopted in 2015 as the new FIPS standard. The algorithm works by means of the mixing function with compression to the selected size “cryptographic sponge“.
The original Keccak algorithm has many configurable parameters (data block size, algorithm state size, number of rounds in the f function, etc.) in order to provide an optimal ratio of cryptographic stability and performance for application on the selected platform. The version of SHA-3 algorithm has several differences from the original keccak algorithm:
- slow modes c=768 and c=1024 are discarded
- simplified algorithm of filling
- introduced” functions with an extended result “(XOF, Extendable Output Functions) SHAKE128 and SHAKE256, for which the hash message was necessary to Supplement the” suffix ” of 2 or 4 bits, depending on the type of function.
The reference implementation source code was dedicated to public domain via CC0 waiver. Although part of the same series of standards, SHA-3 is internally quite different from the MD5-like structure of SHA-1 and SHA-2.
Contents
Keccak algorithm
The Keccak algorithm is the work of Guido Bertoni, Joan Daemen (who also co-designed the Rijndael cipher with Vincent Rijmen), Michael Peeters, and Gilles Van Assche. It is based on earlier hash function designs PANAMA and RadioGatún. PANAMA was designed by Daemen and Craig Clapp in 1998. RadioGatún, a successor of PANAMA, was designed by Daemen, Peeters, and Van Assche, and was presented at the NIST Hash Workshop in 2006[1].
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 demonstrated. Because of the successful attacks on MD5, SHA-0 and SHA-1, 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.
The authors of Keccak came up with a simple (if you understand) scheme, the so-called sponge function. Inside this “sponge” there is a state(1600 bit size for SHA-3), to which one and the same function is applied on each round, which implements pseudo-random permutation. That is, it is essentially a Keyless block cipher with a block size of 1600 bits. And if we fill the state with zeros, perform 10 rounds (10 times we apply their function f) in one direction, and then the same amount in the opposite direction(with the function, inverse f), then we get zeros again.
To cache a string, you must first break it into pieces of a certain size and on each round of it you should not mix them to all 1600 bit state, but only to its beginning of size r. Here perishing I’ll insert the contestant the most picture, now she makes sense. On each round, the next piece of the string is mixed only to a part of the state, while the pseudo-random permutation f handles the whole state, thus smeating the string by state and making it dependent on the whole string.
This is the so-called “absorption”stage. And now it is clear why it is so called. To get the actual hash, we continue to apply the permutation function f to the state, and at each stage copy only a piece of size r from it until we get the hash of the required length. This so-called sponge “squeezing”.
SHA-3 ASIC
SHA-3 runs well on ASICs and miners see this as a strategic advantage. The Keccak team asserts “Its throughput for a given circuit area is an order of magnitude higher than SHA-2 or any of the SHA-3 finalists. And if you care beyond plain speed, note that it also consumes much less energy per bit. In this sense, Keccak is a green cryptographic primitive.” To the best of their knowledge ASICs for SHA-3 are not yet widely available. Security is the top concern and greater network hashrate means a much harder target for malefactors. Hashes that are memory-intensive, or use other means to diminish the advantage of specialized hardware, make for networks that are easier to overthrow. Thus, it did not make sense to deliberately choose an inefficient hash. SHA-3 offers more security, for less power; a winning combination.
It is also unclear as to whether or not ASICs actually contribute to network centralization. The debate on this point over Bitcoin subsided years ago, and several hashes used by other cryptocurrencies have had ASICs developed without the same issue being raised; Scrypt and X11. The view is that the token distribution function has more to do with that than anything else. To address this we’ve implemented a special algorithm for calculating the reward of each block.
Finally, SHA-3 appears to have the best resistance to quantum computing based attacks. This is still a subject of much contention but recent research should alleviate these concerns. A team at the University of Waterloo studied how well SHA-2 and SHA-3 were able to resist a pre-image attack using Grover’s quantum search algorithm. SHA-3 did very well[2].
The SHA-3 (Keccak) scheme consists of two stages:
Absorbing (absorption). The original message M is subjected to mnogoraundovaya the permutation f.
Squeezing (pressing). The output of the resulting permutations of the value z.
The function of Keccak consists of the following:
Keccak[r,c](M) { Initialization and padding for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = 0; P = M || 0x01 || 0x00 || … || 0x00; P = P xor (0x00 || … || 0x00 || 0x80); //Absorbing phase forall block Pi in P for(int x=0; x<5; x++) for(int y=0; y<5; y++) S[x,y] = S[x,y] xor Pi[x+5*y]; S = Keccak-f[r+c](S); //Squeezing phase Z = empty string; do { for(int x=0; x<5; x++) for(int y=0; y<5; y++) if((x+5y)<r/w) Z = Z || S[x,y]; S = Keccak-f[r+c](S) } while output is requested return Z; } - The Absorbing step calculates the hash value.
- And at the
stage of Squeezing the output of the results until the required hash length is reached.
There absorbing is function:
Keccak-f[b](A) { forall i in 0…nr-1 A = Round[b](A, RC[i]) return A } Here b is the value of the selected function (default is 1600).
- And the Round () function is a pseudo-random permutation applied on each round. The number of rounds “‘ nr ‘” is calculated from the values of r and c.
The operations performed on each round represent the following function:
Round[b](A,RC) { θ step for(int x=0; x<5; x++) C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4]; for(int x=0; x<5; x++) D[x] = C[x-1] xor rot(C[x+1],1); for(int x=0; x<5; x++) A[x,y] = A[x,y] xor D[x]; ρ and π steps for(int x=0; x<5; x++) for(int y=0; y<5; y++) B[y,2*x+3*y] = rot(A[x,y], r[x,y]);
χ step for(int x=0; x<5; x++) for(int y=0; y<5; y++) A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]);
ι step A[0,0] = A[0,0] xor RC
return A }
There are 4 steps on each of which a number of logical actions are performed on the incoming data.
Here, the function rot (X,n) denotes the cyclic shift of the x element by n positions.
The R [] array is a predefined set of values that specifies how many bytes to shift on each round:
An RC array is a set of constants that are also predefined:
Twitter
Telegram
