Introduction
A random sponge is a cryptographic model for iterated hash functions and stream ciphers. It is similar to the random oracle model, with the particularity that it explicitly takes into account the consequences of having a finite state in iterated hash functions or stream ciphers.
As detailed in our paper [1], the random sponge can serve as a reference model for expressing compact security claims for hash functions and stream ciphers.
The sponge construction, on which random sponges are based, is a simple iterated construction based on a transformation (or permutation) f. The sponge construction has a finite state. It has two phases: the absorbing phase followed by the squeezing phase. In the absorbing phase, the input message blocks are xored into part of the state, interleaved with applications of the f function. In the squeezing phase, output blocks can be extracted from part of the state, interleaved with applications of the f function.
When f is a random transformation (or permutation), the random sponge cannot be distinguished from a random oracle, unless there is a collision in the c internal bits of the sponge's state that cannot be seen nor controlled from the outside. Furthermore, it can be proven that generic attacks on a random sponge are as hard as on a random oracle, up to a limit of about 2c/2 in complexity. Please refer to our indifferentiability paper [2] for more details.
As it allows variable-length input and variable-length output, the sponge construction can be used as a clean and efficient alternative to the Merkle-Damgård construction to build concrete hash functions or stream ciphers.
The sponge construction (larger)
References
[1] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Sponge Functions, Ecrypt Hash Workshop 2007.
[2] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, On the Indifferentiability of the Sponge Construction, EuroCrypt 2008, to appear.
Contact Information
Email: sponge -at- noekeon -dot- org