Secure Hash Function -3 (SHA-3)

 NIST announced in 2007 a competition to produce the next generation NIST hash function, to be called SHA-3. 

1. The Sponge Construction : 

The sponge function takes an input message and partitions it into fixed size blocks. Each block is processed in turn with output of each iteration fed into the next iteration, finally producing an output block. 

The sponge function is defined by three parameters : 

f = the internal function used to process each input block. 

r = the size in bits of the input blocks, called the bitrate. 

pad = the padding algorithm. 

The sponge function always both variable length input and output, making it a flexible structure that can be used for a hash function (fixed length output), a pseudorandom number generator (fixed length input), and other cryptographic functions (as shown in Fig. 1). 

An input message of n  bits is partitioned into k fixed size blocks of r bits each. If necessary, the message is padded to achieve a length that is an integer multiple of r bits. so the resulting blocks Po, P1, P2, ...., Pk-1, with n = k x r. The sponge specification proposes two padding schemes : 

A. Simple Padding : It is denoted by pad10*, appends a single bit 1 followed by the minimum number of bits 0 such that the length of the result is a multiple of the block length.

B. Multirate Padding : It is denoted by pad10*1, appends a single bit 1 followed by the minimum number of bits 0 followed by a single bit 1 such that the length of the result is a multiple of the block length. This is the simplest padding because that allows secure use of the same f with different rates r. 

After processing all of the blocks, the sponge function generates a sequence of output blocks Z0, Z1,Z2,---Zj-1. The number of output blocks generated is determined by the number of output bits desired. If the desired output is L bits, then j blocks are produced, such that (j-1) x r < L <= j x r. 

Fig. 1 : Sponge Function Input and Output

Figure 2 describes the sponge construction. State variable s of b = r + c bits, which is initialized to all zeros and modified at each iteration. The value r is called the birate. This value is the block size used to partition the input message. The larger the value of r, the greater the rate at which message bits are processed by the sponge  construction. The value of c is referred to as the capacity. The capacity is a measure of the achievable complexity of the sponge construction and therefore the achievable level of security. 

Note 1 : A given implementation can trade claimed security for speed by increasing the capacity 'c' and decreasing the birate 'r' accordingly, or vice-versa. The default values for keccak are c = 1024 bits, r = 576 bits therefore b = 1600 bits. 

Fig. 2: Sponge Construction

The sponge construction consists of two phases : 

A. Absorbing Phase : For each iteration the input block to be processed is padded with zeros to extend its length from the bits to 'b' bits. Then, the bitwise X-OR of the extended message block and 's' is formed to create a b-bit input to the iteration function f. The output of the function is the value of s for the next iteration function f. 

B. Squeezing Phase : If the desired output length 'L' satisfies L<=b, then at the completion of absorbing phase, the first 'L' bits of 's' are returned and the sponge construction terminate. Otherwise, the sponge construction enters Z0. Then the value of 's' is updated with repeated executions of 'f'; and at each iteration, the first 'L' bits of 's' are retained on block Zi and concatenated with previously generated blocks. The process continues through (j-1) iterations until we have (j-1) x r x l <j x r. At this point the first 'L' bits of the concatenated block 'y' are returned. 

2. The SHA-3 Iteration Function F :

Now it's time to study about Keccak function😁. f takes an input 1600 bit variable s consisting of r bits, corresponds the message block size followed by c bits, referred to as the capacity. 

For internal, processing within f, the input state variable s is organized as a 5 x 5 x 64 array a. The 64-bit units are referred to as lanes. Generally use notation for individual bit with state array is a[x, y, z].

When we more concern about operation that affects entire lanes, we designated the 5 x 5 matrix as L[x, y], where each entry in 'L' is a 64 bit lane. 

Fig. 3: SHA-3 State Matrix

The mapping between the bits of s and these of a is : 

    s[64(5y + x) + z] = a[x, y, z]

2.1 The structure of f : The function takes as input the 1600 bit state variable and converts it into a 5 x 5 matrix of 64 bit lanes. The matrix then passes through 24 rounds of processing. 

The application of the five steps can be expressed as the composition of functions 

    R = ioXoπoρoθo

Fig. 4: SHA-3 Iteration Function f

The operation on lanes in the specification are limited to bitwise Boolean operations (XOR, AND, NOT) and rotations. There is no need for table lookups, arithmetic operations, or data dependent rotations. Thus, SHA-3 is easily and efficiently implemented in either Hardware and software. Table 1 describes the operation of five steps

Note 2 : Keccak Parameters : state 25.2^(L) , L = {0, 1, 2, 3, 4, 5, 6}

b = {25, 50, 100, 200, 400, 800, 1600}

# Rounds Nr = 12 + 2L, for SHA-3 = 12 + 2(6) = 24

Table 1 : Step Function in SHA-3

Function	Type	Description
θ	Substitution	New value of each bit in each word depends on its current value and on one bit in each word of preceding column and one bit of each word in succeeding column.
ρ	Permutation	The bits of each word are permutated using a circular bit shift. W[0, 0] is not affect.
π	Permutation	Words are permutated in the 5 x 5 matrix. W[0,0] is not affected.
X	Substitution	New value of each bit in each word depends on its current value and on one bit in the next word in the same row and one bit in the second next word in the same row.
i	Substitution	W[0,0] is updated by XOR with a round constant.

A. Theta Step Function  : 

In case of Theta step function each of the 1600 state bits are replaced by the XOR sum 11 bits. 

Here, the summation is Bitwise XOR. First, define the bitwise XOR of the lanes in column x as :

Consider lane L[x,y] in column x and row y. The first summation in equation performs a bitwise xor of the lanes in column (x-1) mod 4 to form the 64 bit lane c[x-1]. The second summation performs a bitwise xor of the lanes in column (x+1) mod 4, and then rotates the bits within the 64 bit lane so taht the bit in position z is mapped into position z+1 mod 64. This forms the lane ROT(c[x+1],1).

    L[X,Y] <--- L[x,y] xor c[x-1] xor ROT(c[x+1],1)

Fig. 5: Theta step Function

B. Rho Step Function : 
The below equations defines the functioning of Rho function in very detail. 

C. Pi Step Function :

Please see the below equation for better understanding. 😉 

Fig. 6: Pi step Function

D. CHI Step Function : 

The chi function can be defined using below equation. 

The chi function operates to update each bit based on its current value and the value of the corresponding bit position in the next two lanes in the same row. The operation is more clearly seen if we consider a single bit a[x,y,z] and write out the Boolean expression. 

The below figure (as shown in Fig. 7) shows the operation of chi step function. This is the only one of the step functions that is a nonlinear mapping. Without it, the SHA-3 round function would be linear. 

Fig. 7: Chi step Function

E. Iota Step Function :

The iota function is defined as below : 

The function combines as an array element with a round constant that differs for each round. The round constant is applied only to the first lane of the internal state array. We express this as follows : 

Table 2 lists the 24, 64-bit round constant. Note that the hamming weight, or number of 1 bits in the round constant ranges from 1 to 6. Most of the bit positions are zero and thus do not change the corresponding bits in L[0,0]. If we take the cumulative OR of all 24 rounds constants we get

    RC[0] OR RC[1] OR ------OR RC[23] = 800000008000808B

Thus only 7 bit position are active and can affect the value of L[0,0]. of course, from round to round, the permutation and substitution propagate the effect of the iota function to all of the lanes and all of the bit positions in the matrix. It is easily seen that the disruption diffuses through theta and chi to ll lanes of the state after a single round. 

Table 2 : Round Constant in SHA-3                         

********************************************************************************************************************