Incryptography, asponge function orsponge construction is any of a class ofalgorithms with finiteinternal state that take an inputbit 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 manycryptographic primitives, includingcryptographic hashes,message authentication codes,mask generation functions,stream ciphers,pseudo-random number generators, andauthenticated encryption.[1]
A sponge function is built from three components:[2]
S is divided into two sections: one of sizer (the bitrate) and the remaining part of sizec (the capacity). These sections are denotedR andC respectively.
f produces apseudorandom permutation of the states fromS.
P appends enough bits to the input string so that the length of the padded input is a whole multiple of the bitrate,r. This means the input is segmented into blocks ofr bits.
The sponge function "absorbs" (in thesponge metaphor) all blocks of a padded input string as follows:
The sponge function output is now ready to be produced ("squeezed out") as follows:
If less thanr bits remain to be output, thenR will be truncated (only part ofR will be output).
Another metaphor describes the state memory as an "entropy pool", with input "poured into" the pool, and the transformation function referred to as "stirring the entropy pool".[3]
Note that input bits are never XORed into theC portion of the state memory, nor are any bits ofC ever output directly. The extent to whichC is altered by the input depends entirely on the transformation functionf. In hash applications, resistance tocollision orpreimage attacks depends onC, and its size (the "capacity"c) is typically twice the desired resistance level.
It is also possible to absorb and squeeze in an alternating fashion.[1] This operation is called the duplex construction or duplexing. It can be the basis of a single pass authenticated encryption system. This have also been used as an efficient variant of theFiat-Shamir transformation for some protocols.[4]
It is possible to omit the XOR operations during absorption, while still maintaining the chosensecurity level.[1] In this mode, in the absorbing phase, the next block of the input overwrites theR part of the state. This allows keeping a smaller state between the steps. Since theR part will be overwritten anyway, it can be discarded in advance, only theC part must be kept.
Sponge functions have both theoretical and practical uses. In theoretical cryptanalysis, arandom sponge function is a sponge construction wheref is a random permutation or transformation, as appropriate. Random sponge functions capture more of the practical limitations of cryptographic primitives than does the widely usedrandom oracle model, in particular the finite internal state.[5]
The sponge construction can also be used to build practical cryptographic primitives. For example, theKeccak cryptographic sponge with a 1600-bit state has been selected byNIST as the winner in theSHA-3 competition. The strength of Keccak derives from the intricate, multi-round permutationf that its authors developed.[6] TheRC4-redesign calledSpritz refers to the sponge-construct to define the algorithm.
For other examples, a sponge function can be used to buildauthenticated encryption with associated data (AEAD),[3] as well aspassword hashing schemes.[7]
