SquarePants Sponge Hashing

In 2007, the NIST (National Institue of Standards and Technology) announced a Cryptographic Hash Algorithm Competition, with the winner being awarded the grant to be standardized as the new SHA-3. It ended in 2012 with $$K​ECCAK being announced as the winner.

The function uses a sponge construction, but what the hell is even this thing? Let’s take a look!

We have a message $𝑀$ as our input and the final hash $𝐻$. We then have two “registers”: $𝑟$ and $𝑐$, which both make up our state $𝑠$. These two are initialized with $0$s in them.

The message $𝑀$ is first padded so that it can fit in exactly $𝑘\in \mathbb{N}$ parts ${𝑚}_{𝑖}$, each of size $𝑟$. The process of “absorption” is the following:

1. XOR (denoted $\oplus$) the message-part ${𝑚}_{𝑖}$ with the register $𝑟$ bit-by-bit

2. Scramble the whole register $𝑠$ ($𝑟$ and $𝑐$) altogether to produce a new state ${𝑠}^{\prime }$ by applying $𝑓$ The function $𝑓$ needs to generate a pseudo-random permutation of the bits in $𝑠$

3. Pass on the state to the next iteration

We can now “squeeze” our sponge to extract the hash from it, by applying $𝑓$ again and taking a small chunk ${ℎ}_{𝑖}$ ($𝑟$ bits) over and over until we have enough for our desired output length.

This whole process can be described with the following diagram:

This whole process can also be modified to fit streaming needs, by combining both absorption and squeezing steps at each iteration.