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 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 s in them.

The message is first padded so that it can fit in exactly parts , each of size . The process of "absorption" is the following:

1. XOR (denoted ) the message-part with the register bit-by-bit

2. Scramble the whole register ( and ) altogether to produce a new state by applying The function needs to generate a pseudo-random permutation of the bits in

   

   Example permutation via f

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:

Sponge construction algorithm, inspired by Keccak's diagram

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