SHA-3

SHA-3 is a cryptographic hash function and the newest addition to the SHA family. Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche created the algorithm with the name Keccak. In 2012 Keccak won the american SHA-3 contest organized by NIST. On the 5th of August 2015 it was standardised, allowing for an alternative to SHA-2 (which is still considered save).

General information

Hashing Algorithm

A hashing algorithm is a mathenmatical function that converts an input to a fixed-size output which is often refered as hash value or digest. Hashing is a crucial part of cyber security and widely used in data integrity, verification, cryptography and more.

Hashing algorithms are deterministic, meaning that the same input will always result in the same output. Another characteristic is that a small change in the input leads to significant changes in the hash. Further characteristics can be found under Hashing goals.

Hashing goals

SHA-3 like every other hashing algorithm pursues the same 5 goals.

• Compression: The algorithm must produce the same fixed length output regardless of the length of the input
• Efficient: It must be fast to calculate the function as it will be calculated a lot.
• Pre-image resistance: Knowing the algorithm and output it should be infeasable to calculate the input
• 2nd Pre-image resistance: Given an input and output of the algorithm, it should be infeasable to calculate a second input resulting in the same output
• Collision resistance: Finding 2 inputs giving the same output should be implausible

Hashing Process

Algorithms follow a simple 3 step process to calculate the hash.

• Pre-processing: The goal is to get the input in a way the algorithm can handle. This includes processes like padding or splitting the input into blocks
• Initialization: Initial variables and constants are set
• Execution: The actual hashing algorithm is executed

Calculation

Sponge construction

The Keccak algorithm is a so called sponge construction. It is called that, because it "absorbs" the input and then "squeezes" out the output.

The algorithm uses a 1600-bit array called state which it uses for the caluclations and which will contain the output afterwards. It is divided into 2 parts. The first one is called rate (r) and it will absorb the input. The second part is called capacity (c) and its only function is to make the algorithm more secure.

After the state is initialized, the input message is divided into parts that are as long as the rate. If needed, the last input block will be padded by adding a 1 and then fill it up with 0 to the needed length.

Sponge Construction model

The first input block is now XORed with the state. Afterwards the Keccak algorithm will be used on the state. Then the next block is XORed and the whole process repeats until all chunks are absorbed into the algorithm

Lastly the output is "squeezed" out. The first r bits of the state are taken as the hash value. If the output length is larger than r, the Keccak algorithm will be used again on the state and the next r bits are extraced. This process can repeat until the output length is reached.

Keccak-p permutation

This is the core component of the SHA-3 algorithm. It contains 5 different operations which are executed in order on the state array. To ensure the hashing goals, multiple rounds of the permutation are done in one call of the algorithm. The default for SHA-3 are 24 rounds, meaning that a single call will execute the Keccak-p permutation 24 times before it returns the state. Because of this, the number of rounds is usually an additional input parameter. The state is usually divided into a 5x5 matrix with 64 bits in each position.

Keccak-p permutation sequence

• Step 1, Theta: XOR each bit with a representative value derived from neighboring columns
• Step 2, Rho: Rotates each lane's bits by a specific offset based on its position
• Step 3, Pi: Rearranges the positions of the lanes
• Step 4, Chi: Applies a non-linear transformation to each row using bitwise operations
• Step 5, Iota: XOR with round-specific constants to prevent symmetry