Sponge function
In
Construction
A sponge function is built from three components:[2]
- a state memory, S, containing b bits,
- a function
- a padding function P
S is divided into two sections: one of size r (the bitrate) and the remaining part of size c (the capacity). These sections are denoted R and C respectively.
f produces a pseudorandom permutation of the states from S.
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 of r bits.
Operation
The sponge function "absorbs" (in the
- S is initialized to zero
- for each r-bit block B of P(string)
- R is replaced with R XOR B (using bitwise XOR)
- S is replaced by f(S)
The sponge function output is now ready to be produced ("squeezed out") as follows:
- repeat
- output the R portion of S
- S is replaced by f(S) unless output is full
If less than r bits remain to be output, then R will be truncated (only part of R will be output).
Another metaphor describes the state memory as an "
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 "capacity" c) is typically twice the desired resistance level.
Duplex construction
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.
- The state S is initialized to zero
- for each r-bit block B of the input
- R is XORed with B
- S is replaced by f(S)
- R is now an output block of size r bits.
Overwrite mode
It is possible to omit the XOR operations during absorption, while still maintaining the chosen security level.[1] In this mode, in the absorbing phase, the next block of the input overwrites the R part of the state. This allows keeping a smaller state between the steps. Since the R part will be overwritten anyway, it can be discarded in advance, only the C part must be kept.
Applications
Sponge functions have both theoretical and 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.[4]
The sponge construction can also be used to build practical cryptographic primitives. For example,
For other examples, a sponge function can be used to build
References
- ^ a b c Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "Duplexing the Sponge: Single-Pass Authenticated Encryption and Other Applications" (PDF). Retrieved 2023-03-27.
- ^ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "The sponge and duplex constructions". Retrieved 2023-03-27.
- ^ a b Rivest, Ron; Schuldt, Jacob (2014-10-27). "Spritz – a spongy RC4-like stream cipher and hash function" (PDF). Retrieved 2014-12-29.
- ^ Bertoni, Guido; Daemen, Joan; Peeters, Michaël; van Assche, Giles. "On the Indifferentiability of the Sponge Construction" (PDF). Retrieved March 27, 2023.
- NIST. Retrieved 4 October 2012.
- .