Sponge function

The sponge construction for hash functions. p_i are blocks of the input string, z_i are hashed output blocks.

In cryptography, a sponge function or sponge construction is a class of algorithms with finite internal state that take an input bit stream of any length and produce an output bit stream of any desired length. Sponge functions have both theoretical and practical uses. They can be used to model or implement most cryptographic primitives, including cryptographic hashes, message authentication codes, stream ciphers, block ciphers, and pseudo-random number generators.

Construction

A sponge function is built from of three components:

• a state memory, S, containing b bits,
• a function, f, of fixed length that permutes or transforms the state memory
• a padding function P

The state memory is divided into two sections, R of size r bits and C of size c = b - r bits. The parameter r is called the bitrate and c is the capacity.

The padding function appends enough bits to the input string so that the length of the padded input is a whole multiple of the bitrate, r. The padded input can thus be broken into r-bit blocks.

The sponge function operates as follows:

• The state S is initialized to zero
• The input string is padded
• The first r-bit block of padded input is XORed with R.
• S is replaced by f(S)
• The next r-bit block of padded input (if any) is XORed with R.
• S is replaced by f(S)
• …

The process is repeated until all the blocks of the padded input string are used up ("absorbed" in the sponge metaphor).

The sponge function output is now ready to be produced ("squeezed out") as follows

• The R portion of the state memory is the first r bits of output
• If more output bits are desired, S is replaced by f(S)
• The R portion of the state memory is the next r bits of output
• …

The process is repeated until the desired number of output bits are produced.

Note that input bits are never XORed into the C portion of the state memory, nor are any bits of C ever output directly. The extent to which C is altered by the input depends entirely on the transformation function f. In hash applications, resistance to collision or preimage attacks depends on C, and its size, the the "capacity" c, is typically twice the desired resistance level.

Applications

Sponge functions have both theoretical an practical uses. In theoretical cryptanalysis, a random sponge function is a sponge construction where f is a random permutation or transformation, as appropriate. Random sponge functions capture more of the practical limitations of cryptographic primitives than does the widely-used random oracle model, in particular the finite internal state.

The sponge construction can also be used to build practical cryptographic primitives. For example, the Keccak hash function is built as a sponge function. One size of Keccak, with a 1600-bit state, has been selected by NIST as the winner in the SHA-3 competition. The strength of Keccak derives from the intricate, multi-round permutation f that its authors developed.