H(spl)ashing With A Sponge

So how do you implement an efficient hashing method on a device with limited capabilities? Well, one method is to use a Sponge function (as defined in SHA-3/Keccak):

With the sponge construction we use a fixed-length permutation (or transformation) and a padding rule. This construction thus takes a variable length input and map it to a variable-length output. The input is (Z2)* of any length and then converts it into (Z2)n, where n is defined as part of the process. Overall the method uses a finite-state machine process, and iterates through the states with the addition of the input data.

The sponge construction uses a function F which has a variable-length input and a defined output length. It operates on a fixed number of bits (b) — the width. The sponge construction then operates on a state of b=r+c bits. r is defined as the bitrate and c as the capacity.

Initially an input string is padded using a reversible padding rule (such as adding NULL characters), and then segmented into blocks of r bits. Next the b bits of the state are set to zero, and the sponge construction next defines:

• Absorbing phase. This is where the r-bit input blocks are X-ORed into…