In the context of cryptographic hash functions, sponge functions provide a particular way to generalize hash functions to more general functions whose output length is arbitrary. Based on the sponge construction defined below, they model in a very simple way the finite memory any concrete construction has access to.
- We have shown that a random sponge function is as strong as a random oracle, except for the effects induced by the finite memory. This model can thus be used as an alternative to the random oracle model for expressing security claims.
- In addition, a concrete design method can adopt the sponge construction, providing many interesting properties of sponge functions.
The sponge construction
The sponge construction is a simple iterated construction for building a function F with variable-length input and arbitrary output length based on a fixed-length transformation (or permutation) f operating on a fixed number b of bits. Here b is called the width.
The sponge construction (larger)
The sponge construction operates on a state of b=r+c bits. The value r is called the bitrate and the value c the capacity.
First, all the bits of the state are initialized to zero. The input message is padded and cut into blocks of r bits. The sponge construction then proceeds in two phases: the absorbing phase followed by the squeezing phase.
- In the absorbing phase, the r-bit input message blocks are xored into the first r bits of the state, interleaved with applications of the function f. When all message blocks are processed, the sponge construction switches to the squeezing phase.
- In the squeezing phase, the first r bits of the state are returned as output blocks, interleaved with applications of the function f. The number of output blocks is chosen at will by the user.
The last c bits of the state are never directly affected by the input blocks and are never output during the squeezing phase. The capacity c actually determines the attainable security level of the construction.
To assess the security of the construction, we use the indifferentiability framework introduced by Maurer, Renner and Holenstein [3]. In [2] we prove that the success probability of differentiating a sponge construction calling a random permutation or transformation from a random oracle is upper bounded by 1 - exp(-N22-(c+1)) with N the number of calls to f or its inverse. If N ≪ 2c/2 this bound simplifies to N22-(c+1). This results in a lower bound √π 2c/2 for the expected complexity of a successful differentiating attack. In the remainder we call this expected complexity resistance level and approximate it by the simpler expression 2c/2. These bounds hold independently of the output length. For example, finding collisions for output lengths shorter than c bits has for a random sponge the same expected complexity as for a random oracle.
On the sponge terminology
The terms sponge function and sponge construction refer to concepts precisely defined in [1] and [2]. After their introduction, these terms have been quickly adopted by the cryptographic community, but they are sometimes used incorrectly, e.g., to indicate any mode calling a permutation rather than a compression function, any mode supporting variable-length output or even streaming modes. We reserve the usage of the term sponge construction to the particular way defined in [1] and [2] to use a fixed-length transformation or permutation for building a function that maps inputs of any length to arbitrary-length outputs, and the term sponge functions for functions that are built using the sponge construction. For other constructions or functions that share similarities, we suggest to make the distinction clear by using phrases such as sponge-like or variant of.
For instance, RadioGatún is not a sponge function.
A reference model for security claims
Traditionally, hash function users expect a security level that matches its output length n: 2n/2 for collision-resistance and 2n for (second) preimage resistance. Our design RadioGatún provided an infinite output to be truncated at the desired output length, so its claimed security level could not be expressed using the output length. Hence, we needed an appropriate way to express security claims, preferably as a reference model, not just a list of attacks and their claimed complexity. This question triggered the introduction and analysis of random sponges.
A random sponge is a sponge construction calling a random permutation or transformation. As detailed in [1], a random sponge can serve as a reference model for expressing compact security claims 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.
The flat sponge claim
Claiming the security of a concrete function with regard to a random sponge as a model means comparing the success probability of an attack on the concrete function against that on the model. Such a success probability depends on the nature of the attack considered and on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the indifferentiability result, which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity cclaim.
Flat sponge claim with capacity cclaim: the success probability of any attack should be smaller than or equal to the maximum of that for a random oracle and of 1-exp(-N22-(cclaim+1)), with N the number of calls to the underlying function (or its inverse).
For the classical security requirements of hash functions, this translates into the following:
- Collision resistance: if the output length is n ≤ cclaim, the collision resistance level is 2n/2. If the output length is n ≥ cclaim, the resistance level is 2cclaim/2.
- (Second) preimage resistance: If the output length is n ≤ cclaim/2, the (second) preimage resistance level is 2n. If the output length is n ≥ cclaim/2, the resistance level is 2cclaim/2.
The flat sponge claim covers not only the classical security requirements above, it also covers all current and future attacks, by comparison of their success probabilities to that on a random oracle. Instead of making a list of claims for each kind of attack, one can more easily address all of them at once.
Note that we exclude weaknesses due to the mere fact that the function or its internal components can be described compactly and can be efficiently executed, e.g., the so-called random oracle implementation impossibility.
As explained in our paper [1], the flat sponge claim is suited for expressing the security claim for iterated hash functions with variable output length, but it can equally be used for fixed-output-length iterated hash functions and even stream ciphers by explicitly adding limitations on the output and/or input sizes. The flat sponge claim can be used for any hash function, as it addresses externally-visible properties and does not imply that the sponge construction is used internally.
Both RadioGatún and Keccak make use of the flat sponge claim (although RadioGatún is not a sponge function).
A design method
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 hermetic sponge strategy
The hermetic sponge strategy consists in adopting the sponge construction and building an underlying permutation f that should not have any structural distinguishers.
In this approach, one designs a permutation f on b=r+c bits and uses it in the sponge construction to build the sponge function F. In addition, one makes a flat sponge claim on F with a claimed capacity equal to the capacity used in the sponge construction, namely cclaim=c. In other words, the claim states that the best attacks on F must be generic attacks. Hence, cclaim=c means that any attack on F with expected complexity below 2c/2 implies a structural distinguisher on f, and the design of the permutation must therefore avoid such distinguishers.
In the hermetic sponge strategy, the capacity determines the claimed level of security, and one can trade claimed security for speed by increasing the capacity c and decreasing the bitrate r accordingly, or vice-versa.
Note that a structural distinguisher on f does not necessarily imply an exploitable weakness for F. Still, the demonstration of a structural distinguisher for f compromises the hermetic sponge strategy. The hermetic sponge strategy is thus conservative: it tolerates no structural distinguishers for f, whether exploitable or not in an attack against F, and as such provides a security margin.
We have applied the hermetic sponge strategy to our design Keccak.
Advantages
The sponge construction provides the following unique combination of advantages:
- Variable-length output: it can generate outputs of any length and hence a single function can be used for different output lengths.
- Permutation-based: the underlying function f can be a permutation rather than a compression function or a block cipher. Designing a suitable permutation is easier than designing a suitable compression function or block cipher.
- Security against generic attacks: thanks to the indifferentiability proof, the success probability of any generic attack is equal to that of the same attack applied to a random oracle lower bounded by N22-(c+1) with N the number of calls to f or f-1.
In addition, a sponge function designed using the hermetic sponge strategy has the following advantages:
- Flexibility: users may make their own speed/security trade-off just by selecting the adequate bitrate/capacity values while using the same permutation (or transformation).
- Functionality: thanks to its long outputs and proven security bounds with respect to generic attacks, a sponge function can be used in a straightforward way as a MAC function, stream cipher, deterministic pseudorandom bit generator and mask generating function.
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.
[3] U. Maurer, R. Renner, and C. Holenstein, Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, TCC 2004.
Contact Information
Email: sponge -at- noekeon -dot- org