Sponge function
Sponge function or sponge construction is a class of algorithms with finite that take an input 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 many , including , , mask generation functions, , and .
Contents
Construction
A sponge function is built from 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: one of size r (the bitrate) and the other of size c (the capacity). These sections are denoted R and C respectively.
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.
Operation
The sponge function operates as follows:
- The state S is initialized to zero
- The input string is padded. This means the input p is transformed into blocks of r bits using the padding function P.
- R is XORed with the first r-bit block of padded input
- S is replaced by f(S)
- R is XORed with the next r-bit block of padded input (if any)
- 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 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. If the output length is not a multiple of r bits, it will be truncated.
Another metaphor describes the state memory as an “”, with input “poured into” the pool, and the transformation function referred to as “stirring the entropy pool”.
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 depends on C, and its size, the “capacity” c, is typically twice the desired resistance level.
Duplex construction
It is also possible to absorb and squeeze in an alternating fashion. This operation is called the duplex construction or duplexing. It can be the basis of a single pass authenticated encryption system.
- The state S is initialized to zero
- R is XORed with the first r-bit block of the input
- S is replaced by f(S)
- R is now the first r bits of the output.
- R is XORed with the next r-bit block of the input
- S is replaced by f(S)
- R is now the next r bits of the output.
- …
Overwrite mode
It is possible to omit the xor operations during absorption, while still maintaining the chosen .
The sponge construction can also be used to build practical cryptographic primitives. For example, Keccak is a cryptographic sponge with a 1600-bit state. It has been selected by as the winner in the . The strength of Keccak derives from the intricate, multi-round permutation f that its authors developed. The -redesign called refers to the sponge-construct to define the algorithm.
For another example, a sponge function can be used to build with associated data (AEAD).