Keccak Function

0
24

SHA is a family of cryptographic hash functions designed by NSA but SHA-0,SHA-1 were vulnerable to attacks because of which in 2007, NIST announced a competition to determine SHA-3. Keccak team was the winner of the competition in 2012. In 2014, NIST made some changes in keccak submission and published FIPS 202 (Federal Information Processing Standards) and it became the official SHA3 in 2015.

Other uses of Keccak apart from Cryptographic hash function are authentication, encryption and pseudo-random number generation. Ethereum is also using the same Keccak algorithm but its protocol is using a version of the algorithm.

Keccak function is based on sponge function. Sponge function basically provides a particular way to generalize hash functions. It is a function whose input is a variable sized length string and output is a variable length based on fixed length permutation. Sponge construction consists of some of the terms.

Figure 1: Sponge Construction

Here,

r: rate {Size of part of state which is written and read}

b: width of bit blocks {Calculated by (5 x 5 x w) where w=pow(2,l). Here we have taken l=6 which makes b=1600}

c: capacity = b-r {Size of part of state untouched by input and output}

d: Length of output string

N: Length of input string

f: Permutation function(Absorbing phase), State transformation function(Squeezing phase)

Z: bit string (which will combine to form output string of length d)

Z=sponge[f,pad,r](N,d)

S: State which comprises of b bits and is made of r and c

Steps to get the output:

In the absorbing phase:

  1. Let the input string be N. Pad the input using the padding function and denote the result as P . We will pad the input to the length where we get the length of P as n where n = length(P)/r gets the result as an integer.

Here the padding function is 10*1 pattern i.e. something like 1000…01 where the length of the padding function can vary from 0 to (r-1).

2. Now break the P into n consecutive pieces. Denote these Strings as P(0), P(1), …,P(N-1).

3. Now we initialize the state S to a string of b ‘0’ bits. In this case it will be 1600 bits.

4. Now for each P(i):

I. Add c number of ‘0’ bits to P(i) so that the final length of P(i) is b.

II. XOR( P(i),S ).

III. Apply block permutation function to step II. The result is S(new).

Moving to the squeezing phase:

5. Initialize an empty string Z.

6. While length(Z)<d:

I. Append 1st r bits of S to Z.

II. If Z<d bits then apply f to S. The result is now Snew.

7. Truncate Z to d bits.

Now coming to what is happening inside the permutation blocks. Here the function used is f= Keccak-f[1600] for SHA3. It uses permutation whoch consists AND,NOT and XOR operations. The state is an array of 5x5xw bits where w is defined as w=power(2,l). Here as we are using l=6,hence w=1600. So, we are using 1600 bits as length of input S. Let a[i][ j][k] be bit (5i + j) × w + k of the input. This block permutation function uses 12+2l rounds of five steps. The five steps are θ (theta), ρ (rho), π (pi), χ (chi) and ι (iota).

Conclusion

The changes made to the original Keccak algorithm includes the padding change which allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs.

Happy Learning :)


Keccak Function was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.