# Generic Attacks on Double Block Length Sponge Hashing

Gaëtan Leurent, César Mathéus

► To cite this version:

Gaëtan Leurent, César Mathéus. Generic Attacks on Double Block Length Sponge Hashing. IACR Transactions on Symmetric Cryptology, 2025, 2025 (4), pp.262-283. 10.46586/tosc.v2025.i4.262-283. hal-05517858

HAL Id: hal-05517858

https://inria.hal.science/hal-05517858v1

Submitted on 18 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Generic Attacks on Double Block Length
Sponge Hashing

Gaëtan Leurent and César Mathéus

INRIA Paris, France

gaetan.leurent@inria.fr, cesar.matheus@telecom-paris.fr

**Abstract.** The sponge construction is one of the main modes of operation for hash functions. Using a permutation of width $b = r + c$, the sponge construction with rate $r$ and capacity $c$ is indifferentiable up to $\Omega(2^{c/2})$ permutation calls. In this paper we study variants of the sponge construction that use two permutations in parallel in order to increase the state size: the XOR combiner, and the double sponge construction of Lefevre and Mennink. We focus on the indifferentiability security, and we obtain new distinguishers on these constructions based on a variant of the 4-sum problem that we denote the multiple 4-sum problem.

First, we show that the XOR combiner does not increase the indifferentiability bound when applied to sponge hash functions, with a tight generic attack with complexity $\tilde{O}(2^{b/2})$. This improves over folklore results that require $\tilde{O}(2^{b/2})$ operations to find internal state collisions, and justifies the more involved double sponge construction. Indeed, by mixing the two internal states after every permutation call, the double sponge achieves security beyond the birthday bound, with a security proof up to $\Omega(2^{2c/3})$ permutation calls. However, the proof is not tight: the best generic attack has complexity $O(2^{c+r/2})$, and Lefevre and Mennink show a simulator-specific attack with complexity $O(2^{2c/3+r/3})$. We reduce this gap by showing a dedicated attack against the double sponge, with complexity $O(2^c)$ in general, and $O(\max(2^{3c/4}, 2^{c-r/3}))$ with the specific mixing matrix used by Lefevre and Mennink. In particular, we observe that the complexity of our attack decreases with $r$ (for a fixed $c$), while previous attacks have a complexity that increases with $r$.

**Keywords:** Generic attacks · Distinguisher · Hash function · Combiners · Sponge

## 1 Introduction

Hash functions are central tools in symmetric cryptography, with many use cases such as digital signatures, MAC constructions, data integrity, or password hashing. Unlike most cryptographic constructions, hash functions do not use a secret key; they are therefore public functions, which leads to challenges in properly defining security for a hash function.

**Hash Function Security.** A hash function takes an arbitrarily long bit string as input and outputs a fixed-length bit string:

$$ \mathcal{H} : \{0, 1\}^* \rightarrow \{0, 1\}^n. $$

Ideally, a cryptographic hash function is expected to behave like a random function. In particular, it should resist collisions, preimages and second preimages which can be informally described as follows:

**Collision resistance:** Given a hash construction $\mathcal{H}$, it should be hard to find two messages $M_0 \neq M_1$ with $\mathcal{H}(M_0) = \mathcal{H}(M_1)$;

<figure><img src="image_2.png" /></figure>
**Preimage resistance:** Given $\mathcal{H}$ and a target hash value $\bar{H}$, it should be hard to find $M$ with $\mathcal{H}(M) = \bar{H}$;

**Second-preimage resistance:** Given $\mathcal{H}$ and a message $M_0$, it should be hard to find $M_1 \neq M_0$ with $\mathcal{H}(M_1) = \mathcal{H}(M_0)$.

In this context, hard means computationally hard. That is, the probability of finding a collision, a preimage or a second preimage should be negligible for every polynomial-time adversary $\mathcal{A}$.

More generally, any property that can be shown on a given hash function, but that would occur with low probability on a truly random oracle (a distinguisher) is considered an attack. This indifferentiability framework [MRH04, CDMP05] is way to formalize this notion, and to prove the security of hash function constructions under the assumption that the inner primitive is ideal.

**Iterated Hash Functions.** In practice, hash function are designed as sequences of calls to a primitive over a fixed-size bit string called the internal state. The way these operations are orchestrated is called a mode of operation, and these are typically iterated hash functions. The two most widely used mode are the Merkle-Damgård mode [Dam90, Mer90], iterating a compression function with $n$-bit output, and the sponge construction [BDPV08], iterating a cryptographic permutation on $b = r + c$ bits ($c$ denotes the capacity and $r$ the rate). In particular, the internal state of a Merkle-Damgård hash function is $n$ bits wide (the same as the output size), while the internal state of the sponge is $b$ bits wide. These modes underlie SHA-2 and SHA-3 respectively.

When the inner primitive is assumed to be ideal, security properties of the mode of operation can be proven, either with security reduction (e.g. for the preimage or collision resistance of Merkle-Damgård), or with an indifferentiability proof (e.g. for the sponge [BDPV08]). On the other hand, generic attacks are attacks that target the mode of operation without using any weakness of the inner primitive; they give upper bounds on the achievable security. In Table 1, we show a quick overview or the available proofs and attacks for several hash function modes. In many cases the best known attack matches the proof (up to polynomial factors), but there are important cases where a gap remains.

The security of hash functions is tightly linked to the size of their inner primitive. Indeed, thanks to the birthday paradox, an attacker can find a collision in the internal state after $2^{n/2}$ operations for a Merkle-Damgård hash function, or $2^{c/2}$ operations for a sponge. This implies various distinguishers with the same complexity (collision extension, multi-collision, ...). This motivates constructions to increase the state size while keeping the same inner primitive.

**Combiners.** A generic way to increase the state size is to use two independent hash functions in parallel, and to combine their output. There are two classical constructions, given two $n$-bit hash functions $\mathcal{H}_1$ and $\mathcal{H}_2$:

**The XOR combiner** computes $\mathcal{H}(M) = \mathcal{H}_1(M) \oplus \mathcal{H}_2(M)$ (with an $n$-bit output);

**The concatenation combiner** computes $\mathcal{H}(M) = \mathcal{H}_1(M) \parallel \mathcal{H}_2(M)$ (with a $2n$-bit output);

As a concrete example, TLS versions 1.0 and 1.1 used the XOR combiner with **HMAC-MD5** and **HMAC-SHA1**, in order to protect against potential attacks against one of them.

This type of combiner has been widely studied with two Merkle-Damgård hash functions. In a seminal work [Jou04], Joux introduced the multi-collision technique, and demonstrated collision attacks with complexity $\tilde{O}(2^{n/2})$ on the XOR and concatenation combiner, and a preimage attack with complexity $O(2^n)$ on the concatenation combiner. This shows that the XOR and the concatenation of two Merkle-Damgård hash functions do not increase the
<caption>**Table 1:** Security level of various hash function constructions and combiners: Merkle-Damgård (MD), sponge, XOR and concatenation combiners, and double sponge. Lower bounds correspond to security proofs, while upper bounds correspond to generic attacks. We consider hash functions with *n*-bit output (2*n*-bit for the concatenation combiner), an *n*-bit state for Merkle-Damgård, and a *c*-bit capacity and *r*-bit rate for the sponge (with a permutation width *b* = *r* + *c*).</caption>

All bounds ignore polynomial factors, and new results are in bold.

<table><thead><tr><th rowspan="2">Construction</th><th colspan="2">Collision</th><th colspan="2">Indifferentiability</th></tr><tr><th>lower bound</th><th>upper bound</th><th>lower bound</th><th>upper bound</th></tr></thead><tbody><tr><td>Merkle-Damgård</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [CDMP05]</td><td>2<sup>n/2</sup></td></tr><tr><td>MD || MD</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [Jou04]</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [Jou04]</td></tr><tr><td>MD ⊕ MD</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [Jou04]</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [Jou04]</td></tr><tr><td>Sponge</td><td>2<sup>min(c/2,n/2)</sup></td><td>2<sup>min(c/2,n/2)</sup></td><td>2<sup>c/2</sup> [BDPV08]</td><td>2<sup>c/2</sup></td></tr><tr><td>Sponge || Sponge</td><td>2<sup>c/2</sup></td><td>2<sup>b/2</sup></td><td>2<sup>c/2</sup></td><td>2<sup>c/2</sup></td></tr><tr><td>Sponge ⊕ Sponge</td><td>2<sup>c/2</sup></td><td>2<sup>b/2</sup></td><td>2<sup>c/2</sup></td><td>2<sup>c/2</sup></td></tr><tr><td>Double sponge</td><td>2<sup>2c/3</sup> [LM24]</td><td>2<sup>c+r/2</sup></td><td>2<sup>2c/3</sup> [LM24]</td><td>2<sup>max(3c/4,c-r/3)</sup></td></tr></tbody></table>

security. Later, a series of works [LW15, Din16, BWGG17, BDG$^+$20, BBLS24] established that the XOR combiner actually reduces the security against preimage attack; the best known preimage attack on the XOR of two Merkle-Damgård hash functions has complexity $\tilde{O}(2^{3n/5})$, while no generic preimage attack faster than $2^n$ is known on a single Merkle-Damgård hash function$^1$.

The case of sponge-based constructions has received much less attention. This is likely because the security of a sponge can be increased by adjusting the capacity without changing the internal permutation (as long as $c < b$). However, if combiners can increase the security beyond $2^{c/2}$, there might be parameters where this provides a better efficiency than a single sponge for the same security$^2$. This motivates the study of combiners for sponge-based hash functions.

**Double Block Length Constructions.** Instead of combining hash functions as black boxes, better results can be obtained by designing a mode of operation with two (or more) parallel states that are updated and mixed with several inner primitives. This has been widely studied for compression function-based constructions, starting with the MDC-2 and MDC-4 constructions [MS88]. More recently, Lefevre and Mennink introduced the double sponge construction [LM24], based on two permutations. They proved security beyond the birthday bound, up to roughly $2^{2c/3}$ permutation calls. In particular, this construction is more efficient than a single sponge when the required security level is higher than $2b/5$.

## 1.1 Our Results

In this paper, we study the security of sponge-based hash function modes that use two permutation calls in parallel. We focus on the XOR combiner with two sponges and the double sponge construction, and we obtain new generic attacks improving the state of the art.

Instead of using pairs of internal states that collide, we consider quadruples of internal states that sum to zero. When such a quadruple has some extra structure, we obtain several related quadruples of messages $(x_i, y_i, z_i, w_i)$ such that the corresponding outputs sum to

<footnote>$^1$However, there are faster second-preimage attacks when the target message is long [KS05]</footnote>

<footnote>$^2$In particular, this is the case for the double sponge</footnote>
<figure><img src="image_3.png" /><figcaption>**Figure 1:** Indifferentiability bounds of the double sponge, with fixed $b$ (left) and with fixed $c$ (right).</figcaption></figure>

zero ($H(x_i) \oplus H(y_i) \oplus H(z_i) \oplus H(w_i) = 0$). We consider this property as a generalized 4-sum, and we prove that it is hard to obtain messages with such relations on a random oracle. Therefore, constructing these messages for a concrete construction is a distinguisher. When describing our attacks we include polynomial factors in the complexity analysis; however, when assessing the gap between attacks and security proofs, we only compare the exponential factors.

On the XOR combiner, we obtain a generalized 4-sum with $\tilde{O}(2^{c/2})$ operations, matching the indifferentiability proof. Therefore, we obtain the tight indifferentiability security of the XOR of two sponges. As far as we can tell the best distinguisher known previously had a complexity in the order of $2^{b/2}$.

On the double sponge, we obtain a first attack with complexity $\tilde{O}(2^c)$, for any instantiation of the double sponge. The double sponge uses a $2 \times 2$ MDS matrix MIX to mix the inner state after each iteration, and we show an improved attack for some choices of MIX, including the specific choice in [LM24], with complexity $\tilde{O}(2^{3c/4})$ when $r \ge 3c/4$, and $\tilde{O}(2^{c-r/3})$ otherwise. This reduces the gap between the security proof of the double sponge (up to $\tilde{O}(2^{2c/3})$ permutation calls) and the previously known attacks (a simple collision attack with complexity $\tilde{O}(2^{c+r/2})$, and a simulator-specific$^3$ attack with complexity $2^{2c/3+r/3}$). Figure 1 shows how our new attack compare with previous results.

## 2 Sponge-based Hash Functions

The sponge construction [BDPA07] is an iterated construction for building a hash function $H$ with variable-length input and arbitrary output length based on a fixed-length

<footnote>$^3$ This is an attack against the simulator used in the indifferentiability proof of [LM24], but does not rule out the possibility of a better proof with a different simulator.</footnote>
permutation (or transformation) P operating on a fixed number b of bits. Here b is called the width. The sponge construction operates on a state of b = r + c bits. The value r is called the rate and the value c the capacity. The operation of the sponge construction is described in Algorithm 1 and Figure 2.

We summarize the main notation used in this paper in Table 2. In particular, we use the notation $S_H(m_1 || \dots || m_k)$ to denote the state after absorbing and processing the message $m_1 || \dots || m_k$, and $S_H^*(m_1 || \dots || m_k)$ to denote the state after absorbing and processing the message $m_1 || \dots || m_{k-1}$, and just after absorbing $m_k$. With this notation, the absorbing phase can be written recursively, with M a multiple-block message, and m a single-block message:

$$S_H(\epsilon) = IV \qquad S_H^*(M \parallel m) = S_H(M) \oplus (m \parallel 0^c) \qquad S_H(M) = P(S_H^*(M)).$$

We also use $\mathcal{C}(X)$ and $\mathcal{R}(X)$ to denote respectively the inner part (capacity) and the outer part (rate) of a sponge state X.

Note that the sponge construction, when instantiated with a random permutation P, has been proven indifferentiable from a random oracle up to $O(2^{c/2})$ calls to P [BDPV08]. This bound is tight, i.e., generic attacks reaching these bounds in terms of queries to P have been established. Moreover, tight bounds are also known for the main security notions, in the order of $min(2^{c/2}, 2^{n/2})$ for collisions, $min(2^{c/2}, 2^n)$ for second preimages and $min(max(2^{c/2}, 2^{n-r}), 2^n)$ for preimages [LM22].

Usually, the sponge construction and its variants are associated with a padding rule used to handle messages whose length is not a multiple of the rate. For simplicity, and without significant impact on our results, we will restrict ourselves to messages whose lengths are always multiples of the rate and ignore the padding rule.

## 2.1 Sponge Combiners

Hash function combiners have been proposed as a way to increase the security over a single hash function. When combining two sponges, the internal state is composed of two b-bit states, and the absorption phase updates them independently. We consider two sponge constructions $\mathcal{H}_1$ and $\mathcal{H}_2$ defined over the same parameters $b = r + c$, instantiated with two different b-bit random permutations, respectively $P_1$ and $P_2$.

**The XOR Combiner.** We define the XOR combiner as the hash function $\mathcal{H} : \{0, 1\}^* \rightarrow \{0, 1\}^n$ such that

$$\mathcal{H}(M) = \mathcal{H}_1(M) \oplus \mathcal{H}_2(M).$$

The XOR combiner is represented by Figure 3.

**The Concatenation Combiner.** Similarly, we define the concatenation combiner as the hash function $\mathcal{H} : \{0, 1\}^* \rightarrow \{0, 1\}^n$ such that

$$\mathcal{H}(M) = \mathcal{H}_1(M) \parallel \mathcal{H}_2(M).$$

**Security.** The concatenation combiner is robust for collision resistance: if at least one of the combined hash functions is secure against collision attacks, then the combiner is secure. On the other hand, the XOR combiner is robust for the PRF property: if at least one of the functions is a PRF, then the combination is a PRF.

However, in this paper, we focus on indifferentiability results. It is known that the XOR combiner and the concatenation combiner preserve the indifferentiability security of the initial functions if they are both indifferentiable and independent$^4$. However, we

<footnote>$^4$See for instance [Leh10, page 13] or [DFG$^+$23, page 516] for the XOR combiner.</footnote>
<table><caption>**Table 2:** Main notation used the paper.</caption><thead><tr><th>Notation</th><th>Description</th></tr></thead><tbody><tr><td>F<sub>2<sup>b</sup></sub></td><td>finite field of size 2<sup>b</sup></td></tr><tr><td>H<sub>1</sub>, H<sub>2</sub></td><td>Two sponge hash functions</td></tr><tr><td>P<sub>1</sub>, P<sub>2</sub></td><td>internal permutations used in H<sub>1</sub> and H<sub>2</sub> respectively</td></tr><tr><td>IV<sub>1</sub>, IV<sub>2</sub></td><td>initialization vectors for H<sub>1</sub> and H<sub>2</sub> respectively</td></tr><tr><td>r</td><td>rate of H<sub>1</sub> and H<sub>2</sub> (size of the message absorbed)</td></tr><tr><td>c</td><td>capacity of H<sub>1</sub> and H<sub>2</sub> (size of the hidden part of the state)</td></tr><tr><td>b</td><td>permutation with of P<sub>1</sub> and P<sub>2</sub> (b = r + c)</td></tr><tr><td>S<sub>H</sub>(m<sub>1</sub> || ... || m<sub>k</sub>)</td><td>state after absorbing/processing m<sub>1</sub>, ..., m<sub>k</sub></td></tr><tr><td>S<sup>*</sup><sub>H</sub>(m<sub>1</sub> || ... || m<sub>k</sub>)</td><td>state after absorbing/processing m<sub>1</sub>, ..., m<sub>k-1</sub> and absorbing m<sub>k</sub></td></tr><tr><td>C(X)</td><td>capacity part of internal state X</td></tr><tr><td>R(X)</td><td>rate part of internal state X</td></tr><tr><td>Trunc<sub>t</sub>(X)</td><td>the first t bits of X</td></tr></tbody></table>

**Algorithm 1** The sponge construction. The algorithm takes as input the message to hash $M$ and the number of bits of the stream to extract $n$. $IV \in \{0, 1\}^b$ is a fixed initialization vector.

1: **function** SPONGE<sup>*P*</sup>(M, n){0, 1}<sup>*</sup> × $\mathbb{N}$ → {0, 1}<sup>*</sup>
/* The state S is initialized and the message is split into r-bit blocks */

2: $S \leftarrow IV$

3: $m_1 \parallel \cdots \parallel m_k \leftarrow M$

/* Absorbing phase */

4: **for** i = 1, ..., k **do**

5: $S \leftarrow P(S \oplus (m_i \parallel 0^c))$

6: **end for**

/* Squeezing phase */

7: **for** i = 1, ..., ⌈n/r⌋ **do**

8: $z_i \leftarrow \mathcal{R}(S)$

9: $S \leftarrow P(S)$

10: **end for**

11: **return** ($z_1 \parallel \cdots \parallel z_{\lfloor n/r \rfloor}$) [0 : n]

12: **end function**

**Algorithm 2** The double sponge construction based on $P := (P_1, P_2)$. $IV_1$ and $IV_2$ are two fixed initialization vectors.

function DOUBLESPONGE<sup>*P*</sup>(M, n){0, 1}<sup>*</sup> × $\mathbb{N}$ → {0, 1}<sup>*</sup>

/* The state is initialized and the message is split into r-bit blocks */

($S_1, S_2$) ← (IV<sub>1</sub>, IV<sub>2</sub>)

$m_1 \parallel \cdots \parallel m_k \leftarrow M$

/* Absorbing phase */

for i = 1, ..., k **do**

($S_1, S_2$) ← MIX($P_1(S_1 \oplus (m_i \parallel 0^c))$, $P_2(S_2 \oplus (m_i \parallel 0^c))$)

end for

/* Squeezing phase */

for i = 1, ..., ⌈n/r⌋ **do**

$z_i \leftarrow \mathcal{R}(S_1)$

($S_1, S_2$) ← MIX($P_1(S_1)$, $P_2(S_2)$)

end for

return ($z_1 \parallel \cdots \parallel z_{\lfloor n/r \rfloor}$) [0 : n]

end function
didn't find a full proof in the literature; therefore we give a proof of the indifferentiability of the XOR of two sponges in Appendix A.

Moreover, the XOR combiner is robust for indifferentiability, but the concatenation combiner is not robust (if one of the functions is biased, this is detected in the concatenation, and any distinguisher on a single hash function can be directly applied to distinguish the concatenation).

## 2.2 The Double Sponge

The double sponge is a construction proposed by Mennink and Lefevre [LM24], whose main feature is, for certain parameter regimes, achieving security beyond the birthday bound.

Like a standard sponge construction, the double sponge consists of an absorption phase and a squeezing phase. Like a sponge combiner, the internal state is composed of two b-bit states, but the two states are mixed during the absorption phase, instead of being updated independently. More precisely, after each application of the permutations $P_1$ and $P_2$, the two internal states are multiplied by a $2 \times 2$ MDS matrix over $\mathbb{F}_{2^b}$, called MIX, defined as follows:

$$ \text{MIX} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}. $$

During the squeezing phase, only the first state is squeezed, as in a single sponge construction. Algorithm 2 defines the double sponge, and Figure 4 illustrates its operation.

**Security.** Lefevre and Mennink proved that the double sponge construction is secure up to $\Omega(2^{2c/3})$ permutation calls, within the indifferentiability framework. They also propose attack on the construction, but the attack do not match the bound of the proof:

* First they describe a simple attack with $O(2^{c+r/2})$ queries, leading to a collision in the internal state.

* They also propose an attack against the specific simulator used in their security proof, with $O(2^{2c/3+r/3})$ queries. This shows that the simulator used in their proof cannot achieve security higher than $2^{2c/3+r/3}$, but it is not an attack against the double sponge (it does not rule out the possibility of a better proof with a different simulator).

In particular, the indifferentiability bound is not tight. The structure of the indifferentiability proof even led the authors to conjecture that the real bound may in the order of $2^{2c/3+r/3}$ rather than in the order of $2^{2c/3}$.

**Notation.** The state of the double sponge can be seen as two sponge states with matching rate and capacity parameters. Given a double sponge state $S$, we use $[S]_1$ and $[S]_2$ to denote the two corresponding sponge states.

## 3 Indifferentiability and Distinguishers

We briefly introduce the indifferentiability framework, that is used for security proofs of sponge-based hash functions, and some techniques to build distinguishers.
<figure><img src="image_4.png" /><figcaption>**Figure 2:** The sponge construction.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Figure 3:** The XOR combiner of two sponges.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Figure 4:** The double sponge construction.</figcaption></figure>
## 3.1 Indistinguishability

In order to define the security of a cryptographic system $S_0$, we define an idealized object $S_1$ with the same interface, and we argue that it is hard to distinguish the two systems. This corresponds to the notion of indistinguishability. More formally, we consider an adversary $\mathcal{A}$ interacting with $S_i$ where $i$ is drawn at random from $\{0, 1\}$. He is allowed to perform at most $q$ queries and it tries to guess the system it has interacted with. The advantage of $\mathcal{A}$ in the indistinguishability game is defined as:

$$ \mathrm{Adv}_{\mathrm{ind}}^{S_0, S_1}(\mathcal{A}) = |\mathrm{Pr}[\mathcal{A}^{S_0} = 1] - \mathrm{Pr}[\mathcal{A}^{S_1} = 1]|. $$

If we can prove that the advantage is small for any adversary $\mathcal{A}$ making at most $q$ queries, then the system $S_0$ is secure up to $q$ queries.

However, this notion does not directly apply in the context of hash functions, because these are public objects without components that remain secret from the distinguisher such as a key. Therefore, it is easy to distinguish a concrete hash function from an ideal object.

## 3.2 Indifferentiability

Indifferentiability represents a specific type of distinguishing game, where the adversary interacts with a keyless primitive. This notion formalizes how difficult it is to distinguish a real hash function from an ideal object, a random oracle. This concept was first introduced by Maurer et al. [MRH04]. It was later refined in the context of hash functions by Coron et al. [CDMP05].

Consider a mode of operation for a hash function $\mathcal{H}^P$ using a random permutation $P$. In order to prove the security of $\mathcal{H}^P$ in this framework, we define a simulator $S^{\mathcal{RO}} := (S_{\mathrm{fwd}}, S_{\mathrm{inv}})^{\mathcal{RO}}$ such that it is hard for an adversary to distinguish whether he interacts with $\mathcal{H}^P$ and $(P, P^{-1})$ or with a random oracle $\mathcal{RO}$ and the simulator. The simulator, must define $S_{\mathrm{fwd}}$ and $S_{\mathrm{inv}}$ to have the same domain as $P$, and can make queries (at most $q$) to the oracle $\mathcal{RO}$, in order to maintain consistency between his answers and the random oracle. This definition captures that both the hash function and the inner primitive are public, and therefore the adversary has access to them.

Let $\mathcal{A}$ represent an adversary which is allowed to make at most $q_H$ construction queries and $q_P$ primitive queries. The indifferentiability advantage of $\mathcal{A}$ with respect to the simulator $S$ is expressed as follows:

$$ \mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}^P, S^{\mathcal{RO}}}(\mathcal{A}) = \mathrm{Adv}_{\mathrm{ind}}^{[\mathcal{H}^P, (P, P^{-1})], [\mathcal{RO}, (S^{\mathcal{RO}})]}(\mathcal{A}). $$

On one side a generic attacks such as a collision or a preimage generally gives an upper bound of the security achievable by a mode of operation. On the other hand, one can build simulators $S$ tailored to guarantee a negligible advantage for any adversary in the indifferentiability game, which gives then a security lower bound for the construction.

## 3.3 Multiple 4-sum Distinguishers

A way to distinguish a concrete hash construction from a random oracle is to leverage the inner structure of the construction to exhibit a specific behavior that is very unlikely to occur in a random oracle. A classical approach is to construct an inner-state collision. We found that stronger results can be obtained using a generalization of collisions, namely the 4-sum problem. We define a large class of problems related to 4-sum and show how they can be used to provide an upper bound on the indifferentiability advantage; in other words, such events are unlikely to happen on random oracles and hence can be used as distinguishers. We take inspiration from the generalized birthday problem first defined by Wagner and present his original definition of the generalized birthday problem:
**Definition 1** (The k-sum problem [Wag02]). Given k lists $L_1, \dots, L_k$ of elements drawn uniformly and independently at random from $\{0, 1\}^n$, find $x_1 \in L_1, \dots, x_k \in L_k$ such that

$$x_1 \oplus x_2 \oplus \dots \oplus x_k = 0.$$

We define a variant of this problem in the case where $k = 4$, where the problem is defined by a function instead of lists, and the goal is to find multiple related solutions to the 4-sum problem. We denote this variant as the multiple 4-sum problem:

**Definition 2** (The multiple 4-sum problem). Let $\mathcal{H}$ be a hash function with $n$-bit output, $\lambda$ a positive integer, and $\{\varphi_i : \{0, 1\}^* \to \{0, 1\}^*\}_{0 \le i < \lambda}$ a finite family of $\lambda$ injective functions satisfying the following condition to avoid redundancy:

$$\forall x \in \{0, 1\}^*, \forall i \neq j, \varphi_i(x) \neq \varphi_j(x). \qquad (1)$$

The generalized 4-sum problem consists of finding a quadruple of distinct values $\{x, y, w, z\}$ such that:

$$\forall i \in \{0, 1, \dots, \lambda - 1\}, \quad \mathcal{H}(\varphi_i(x)) \oplus \mathcal{H}(\varphi_i(y)) \oplus \mathcal{H}(\varphi_i(w)) \oplus \mathcal{H}(\varphi_i(z)) = 0. \quad (2)$$

This definition captures different variants of multiple 4-sums, depending on the functions $\varphi_i$, where $\lambda$ represents the number of different 4-sums. We can also define partial 4-sums by defining a truncated function $\mathcal{H}$.

**Difficulty of Finding Multiple 4-sums.** In order to use multiple 4-sums as hash function distinguishers, we must show that it is hard to obtain a multiple 4-sum for a random oracle. More precisely, we try to bound the probability that there exists at least one quadruple of distinct messages $(x, y, w, z)$ satisfying (2) after making $q$ queries to $\mathcal{H}$, when $\mathcal{H}$ is a random oracle. From the definition of a random oracle, each distinct input is mapped independently and uniformly to a bit string of length $n$.

Let us consider a fixed (unordered) quadruple $(x, y, w, z)$. If all the $\lambda$ constraints of (2) are independent, then the quadruple has probability $2^{-\lambda n}$ of being a solution to the multiple 4-sum problem. However, the constraints are not independent in general; for example equation $i$ and $j$ are equivalent if $\varphi_i$ and $\varphi_j$ satisfy:

$$\varphi_i(x) = \varphi_j(y) \qquad \varphi_i(z) = \varphi_j(w) \qquad \varphi_i(y) = \varphi_j(x) \qquad \varphi_i(w) = \varphi_j(z).$$

In order to bound the probability of $(x, y, w, z)$ to satisfy (2), we consider a subset of indices $J \subset \{0 \dots \lambda - 1\}$ such that the corresponding conditions are independent. More precisely, we show that there exist a large set $J$ such that:

$$\forall i, j \in J, i \neq j, \forall u, v \in \{x, y, w, z\}, u \neq v : \varphi_i(u) \neq \varphi_j(v).$$

For a fixed index $i$ and a pair of elements $(u, v) \in \{x, y, w, z\}$, of the quadruple $(u \neq v)$, there is at most one index $j$ such that $\varphi_i(u) = \varphi_j(v)$, because the functions $\varphi_i$ are injective and must satisfy condition (1). Consequently, for a fixed $i$, there are at most 12 indices $j \neq i$ such that $\varphi_i(\{x, y, w, z\}) \cap \varphi_j(\{x, y, w, z\}) \neq \emptyset$, one for each ordered pair $(u, v) \in \{x, y, w, z\}$.

Therefore, using a simple greedy algorithm, we obtain a set $J$ as previously defined such that $|J| \ge \lceil \lambda/13 \rceil$. Since the constraints in $J$ are independent, the probability that a fixed quadruple satisfies all the constraints is at most $2^{-n|J|} \le 2^{-n \cdot \lceil \lambda/13 \rceil}$.

To conclude, we observe that an adversary making $q$ queries to $\mathcal{H}$ can construct at most $\binom{\lambda q}{4}$ quadruples $(x, y, z, w)$ such that at least one quadruple $(\varphi_i(x), \varphi_i(y), \varphi_i(z), \varphi_i(w))$ is included in the queries (checking only one condition is sufficient to rule out a wrong
quartet). Therefore, we have the following upper bound on the average number of solutions after $q$ queries, denoted as $X$:

$$ \mathbb{E}[X] \le \left(\frac{\lambda q}{4}\right) \cdot 2^{-n \cdot \lceil \lambda/13 \rceil} \le \frac{(\lambda q)^4}{24} \cdot 2^{-n \cdot \lceil \lambda/13 \rceil}. $$

From Markov's inequality we can upper bound the probability that the number of solutions is at least one:

$$ P[X \ge 1] \le \mathbb{E}[X] \le \frac{(\lambda q)^4}{24} \cdot 2^{-n \cdot \lceil \lambda/13 \rceil}. \quad (3) $$

Since this probability decreases exponentially with $\lambda$ and $n$, the multiple 4-sum problem is hard for large values of $\lambda$ or $n$.

# 4 Previous Attacks on Double Block Length Sponge Hashing

We first review known collision attacks against double block length sponge-based hash functions.

## 4.1 Collision Attack Based on the Birthday Paradox

We consider a hash function with two parallel calls to a $b$-bit permutation; the internal state has size $2b$ bits and we assume that a message of $r$ bits is absorbed after each iteration. This covers both the hash combiners (without any mixing between the two internal state), and the double sponge (with a linear mixing of the internal states with the MIX operation).

The direct application of the birthday paradox gives a simple attack against sponge-based hash function. Assuming a state size of $2b$ bits and a rate of $r$ bits, we expect to find two states with a difference that can be erased by inserting a well-chosen message with non-negligible probability after processing $O(2^{b-r/2}) = O(2^{c+r/2})$ distinct messages. This leads to a full state collision, and it is the best known generic attack against the double sponge construction.

For concreteness, we describe the attack in detail in the case of a combiner using two sponges $H_1$ and $H_2$:

1. Consider $2^{c+r/2}$ distinct messages $M_i$, and compute the state after absorbing them. Look for a pair of messages $(M_i, M_j)$ such that:

$$ \begin{aligned} C(S_{H_1}(M_j)) &= C(S_{H_1}(M_i)) \\ C(S_{H_2}(M_j)) &= C(S_{H_2}(M_i)) \\ \mathcal{R}(S_{H_1}(M_i)) \oplus \mathcal{R}(S_{H_2}(M_i)) &= \mathcal{R}(S_{H_1}(M_j)) \oplus \mathcal{R}(S_{H_2}(M_j)). \end{aligned} $$

Since this is a $2c+r$-bit condition, there is a non-negligible probability to find such a pair.

2. Use an additional message block to correct the remaining differences between $S_H(M_i)$ and $S_H(M_j)$. For instance use message blocks $\mathcal{R}(S_{H_1}(M_i))$ and $\mathcal{R}(S_{H_2}(M_j))$ to obtain the following states after absorption:

$$ \begin{aligned} S_{H_1}^*(M_i \parallel \mathcal{R}(S_{H_1}(M_i))) &= 0^r \parallel \mathcal{C}(S_{H_1}(M_i)) \\ S_{H_1}^*(M_j \parallel \mathcal{R}(S_{H_1}(M_j))) &= 0^r \parallel \mathcal{C}(S_{H_1}(M_j)) \\ S_{H_2}^*(M_i \parallel \mathcal{R}(S_{H_1}(M_i))) &= (\mathcal{R}(S_{H_2}(M_i)) \oplus \mathcal{R}(S_{H_1}(M_i))) \parallel \mathcal{C}(S_{H_2}(M_i)) \\ S_{H_2}^*(M_j \parallel \mathcal{R}(S_{H_1}(M_j))) &= (\mathcal{R}(S_{H_2}(M_j)) \oplus \mathcal{R}(S_{H_1}(M_j))) \parallel \mathcal{C}(S_{H_2}(M_j)). \end{aligned} $$

Given the constraints of Step 1, this is a full state collision.
<figure><img src="image_7.png" /><figcaption>Figure 5: Multicollision against the sponge construction.</figcaption></figure>

## 4.2 Collision Attack Based on Multicollisions

The multicollision technique was proposed by Joux [Jou04] in order to attack the combination of two hash functions $H_1$ and $H_2$. The main idea is to build a large set of different messages that all lead to the same state in $H_1$. If the number of these messages is sufficiently large, a pair of them might also collide in $H_2$, thereby producing a full state collision. This technique is very efficient on Merkle-Damgård hash functions, leading to collision for the concatenation and XOR combiner with complexity $\tilde{O}(2^{n/2})$ (with $n$ the state size of $H_1$ and $H_2$), almost matching the cost of finding a collision on a single Merkle-Damgård construction. We now use the same technique to build a collision against the XOR of two sponge constructions.

**Multicollision for a Sponge Hash Function.** The multicollision technique of Joux directly translates to a sponge hash function $H_1$. After processing $O(2^{c/2})$ distinct messages, there is a high probability to find two messages $m_1$ and $m'_1$, such that $C(S_{H_1}(m_1)) = C(S_{H_1}(m'_1))$. Using an additional message block to compensate the difference in the rate, we obtain a full state collision; for instance we can use $r_1 = R(S_{H_1}(m_1))$, $r'_1 = R(S_{H_1}(m'_1))$ to obtain $S_{H_1}^*(m_1 \parallel r_1) = S_{H_1}^*(m'_1 \parallel r'_1)$.

Next, we repeat this procedure starting from state $S_{H_1}(m_1 \parallel r_1)$. We obtain two messages $m_2 \parallel r_2$ and $m'_2 \parallel r'_2$ such that $S_{H_1}^*(m_1 \parallel r_1 \parallel m_2 \parallel r_2) = S_{H_1}^*(m_1 \parallel r_1 \parallel m'_2 \parallel r'_2)$. Since we already have a state collision after absorption of $m_1 \parallel r_1$ and $m'_1 \parallel r'_1$, the following equalities hold:

$$S_{H_1}^*(m_1 \parallel r_1 \parallel m_2 \parallel r_2) = S_{H_1}^*(m_1 \parallel r_1 \parallel m'_2 \parallel r'_2) = S_{H_1}^*(m'_1 \parallel r'_1 \parallel m_2 \parallel r_2) = S_{H_1}^*(m'_1 \parallel r'_1 \parallel m'_2 \parallel r'_2).$$

Hence, after two iterations of this procedure, we find four messages leading to the same internal state (and the same hash value). In general, after $t$ iterations, $2^t$ colliding messages are obtained. An illustration of a multicollision is depicted in Figure 5.

**Breaking Sponge Combiners.** We use multicollision to find full state collisions for two parallel sponges $H_1$ and $H_2$:

1. Build a $2^{b/2}$-multicollision for $H_1$ and denote the set of messages as $M$.

2. Evaluate $H_2$ on all messages in $M$. There is a non-negligible probability of finding a collision, i.e., two elements $m_i, m_j \in M$ such that

$$S_{H_2}(m_j) = S_{H_2}(m_i).$$

Since $m_i$ and $m_j$ are constructed to collide on the state $H_1$, we obtain a collision simultaneously on the of $H_1$ and $H_2$.

**Complexity.** Step 1 requires $O(b \cdot 2^{c/2})$ operations, and step 2 requires $O(2^{b/2})$ operations, assuming that $c/r$ is a small constant$^5$. Therefore we obtain full state collisions for two parallel sponges with complexity $O(b \cdot 2^{c/2} + 2^{b/2})$.

<footnote>$^5$If $r \ll c$ then each message $m_i$ has a large number of blocks, and this adds a factor $c/r$ in the complexity of Step 2.</footnote>
Interestingly, there is a gap between the cost of finding a state collision for a single sponge ($O(2^{c/2})$) and the cost of finding a collision for two parallel sponges ($\tilde{O}(2^{b/2})$), as opposed to the situation with Merkle-Damgård hash functions. This difference arises because the security of Merkle-Damgård depends on the entire inner state size, whereas a sponge's security relies only on its capacity, a subset of the state. In a single sponge, the adversary controls the rate part of the state, because he can XOR an arbitrary block after each iteration. In contrast, with two parallel sponges, the same message block is XORed into both states; this reduces the attacker's control over these parts of the states, and it seems that the rate contributes to the security.

# 5 Tight Indifferentiability of the XOR of two Sponges

The best known collision attack on the XOR of two sponges has a higher complexity than for a single sponge. As far as we know, this is the best known distinguishing attack on the XOR of two sponges. In this section we describe a new distinguisher based on the multiple 4-sum problem with complexity $O(2^{c/2})$.

Since the XOR of two sponges is indifferentiable from a random oracle up to $\Omega(2^{c/2})$ queries (as mentioned in Section 2.1), this establishes a tight indifferentiability bound (up to polynomial factors) in the order of $\Theta(2^{c/2})$. In particular, this matches the indifferentiability of a single sponge, showing that the XOR combiner does not increase the security, even though previous attacks had a complexity increasing with $r$.

## 5.1 Building a 4-sum on the XOR of two Sponges

We consider the XOR of two sponges $\mathcal{H} := \mathcal{H}_1 \oplus \mathcal{H}_2$. Our strategy is to build four messages that lead to a 4-sum both in $\mathcal{H}_1$ and in $\mathcal{H}_2$, hence leading to a 4-sum over $\mathcal{H}$ (using the linearity of the XOR combiner). We use the following procedure:

**First Step.** Build a $2^{c/2}$ multicollision $\mathcal{M} = \{m_1, ..., m_{2^{c/2}}\}$ on $\mathcal{H}_1$. We have that for all $m_i, m_j \in \mathcal{M}$, the inner state of $\mathcal{H}_1$ after absorption of $m_i$ and $m_j$, $S_{\mathcal{H}_1}(m_i)$ and $S_{\mathcal{H}_1}(m_j)$, are equal. As a consequence, for any suffixes $s_1, s_2 \in \{0, 1\}^r$, the following system holds:

$$ \begin{cases} S_{\mathcal{H}_1}(m_i \parallel s_1) = S_{\mathcal{H}_1}(m_j \parallel s_1) \\ S_{\mathcal{H}_1}(m_i \parallel s_2) = S_{\mathcal{H}_1}(m_j \parallel s_2). \end{cases} $$

This system implies a 4-sum in $\mathcal{H}_1$ with messages $(m_i \parallel s_1, m_i \parallel s_2, m_j \parallel s_1, m_j \parallel s_2)$. By carefully choosing $m_i, m_j, s_1$ and $s_2$ we will obtain a 4-sum in $\mathcal{H}_2$ as well.

**Second Step.** We consider the internal state of $\mathcal{H}_2$ after absorbing respectively $m_i$ and $m_j : S_{\mathcal{H}_2}(m_i)$ and $S_{\mathcal{H}_2}(m_j)$. Since $|\mathcal{M}| = 2^{c/2}$, we expect to find $i \neq j$ such that $C(S_{\mathcal{H}_2}(m_i)) = C(S_{\mathcal{H}_2}(m_j))$ with non-negligible probability. We use $s_1$ and $s_2$ to correct differences in the rate part of the state; that translates to the following system:

$$ \begin{cases} S_{\mathcal{H}_2}^*(m_i \parallel s_1) = S_{\mathcal{H}_2}(m_i) \oplus (s_1 \parallel 0^c) = S_{\mathcal{H}_2}(m_j) \oplus (s_2 \parallel 0^c) = S_{\mathcal{H}_2}^*(m_j \parallel s_2) \\ S_{\mathcal{H}_2}^*(m_i \parallel s_2) = S_{\mathcal{H}_2}(m_i) \oplus (s_2 \parallel 0^c) = S_{\mathcal{H}_2}(m_j) \oplus (s_1 \parallel 0^c) = S_{\mathcal{H}_2}^*(m_j \parallel s_1). \end{cases} $$

Note that the two equations are equivalent and simplify to $s_1 \oplus s_2 = \mathcal{R}(S_{\mathcal{H}_2}(m_i)) \oplus \mathcal{R}(S_{\mathcal{H}_2}(m_j))$. The system admits $2^r$ solutions $(s_1, s_2)$, for example, $s_1 = \mathcal{R}(S_{\mathcal{H}_2}(m_i))$, $s_2 = \mathcal{R}(S_{\mathcal{H}_2}(m_j))$. We obtain a quadruple $(m_i \parallel s_1, m_i \parallel s_2, m_j \parallel s_1, m_j \parallel s_2)$ that is simultaneously a 4-sum in $\mathcal{H}_1$ and in $\mathcal{H}_2$. Therefore, this is also a 4-sum in $\mathcal{H}$.
**Complexity analysis.** The first step requires $O(c \cdot 2^{c/2})$ operations to build the multicollision. The second step also has a complexity in $\tilde{O}(c \cdot 2^{c/2})$ (e.g. by sorting the set to locate collisions). The overall cost of building a 4-sum on the XOR of two sponge constructions is $O(c \cdot 2^{c/2})$.

If the output size $n$ of $\mathcal{H}$ is large, then finding a single 4-sum is already a hard problem. Indeed, from Section 3.3, we know that after making $q$ queries, the probability that there exist at least one 4-sum can be upper bounded by $q^{42-2^{-n}/24}$ (taking $\lambda = 1$ in (3)). Therefore when $n \gg 2c$ the probability of finding a 4-sum with $\tilde{O}(2^{c/2})$ queries is negligible, and our attack is a distinguisher with high probability.

## 5.2 Multiple 4-sum Distinguisher on the XOR of two Sponges

We observe the previous algorithm can be extended to provide a solution to a multiple 4-sum problem. Indeed, we obtain a quadruple of messages with pairwise collisions in $\mathcal{H}_1$ and $\mathcal{H}_2$:

$$S_{\mathcal{H}_1}(m_i \parallel s_1) = S_{\mathcal{H}_1}(m_j \parallel s_1)$$

$$S_{\mathcal{H}_2}(m_i \parallel s_1) = S_{\mathcal{H}_2}(m_j \parallel s_2)$$

$$S_{\mathcal{H}_1}(m_i \parallel s_2) = S_{\mathcal{H}_1}(m_j \parallel s_2)$$

$$S_{\mathcal{H}_2}(m_i \parallel s_2) = S_{\mathcal{H}_2}(m_j \parallel s_1)$$

This structure of pairwise collisions is similar to the structure used in attacks on double-block MAC algorithm [LNS18].

We use the collision extension property: when two messages $m, m'$ lead to a state collision $S_{\mathcal{H}_1}(m) = S_{\mathcal{H}_1}(m')$, then adding the same suffix $\sigma$ to both $m$ and $m'$ doesn't break the collision, that is we always have $S_{\mathcal{H}_1}(m \parallel \sigma) = S_{\mathcal{H}_1}(m' \parallel \sigma)$. In particular, we have for any $\sigma$:

$$S_{\mathcal{H}_1}(m_i \parallel s_1 \parallel \sigma) = S_{\mathcal{H}_1}(m_j \parallel s_1 \parallel \sigma)$$

$$S_{\mathcal{H}_2}(m_i \parallel s_1 \parallel \sigma) = S_{\mathcal{H}_2}(m_j \parallel s_2 \parallel \sigma)$$

$$S_{\mathcal{H}_1}(m_i \parallel s_2 \parallel \sigma) = S_{\mathcal{H}_1}(m_j \parallel s_2 \parallel \sigma)$$

$$S_{\mathcal{H}_2}(m_i \parallel s_2 \parallel \sigma) = S_{\mathcal{H}_2}(m_j \parallel s_1 \parallel \sigma),$$

which implies that $(m_i \parallel s_1 \parallel \sigma, m_i \parallel s_2 \parallel \sigma, m_j \parallel s_1 \parallel \sigma, m_j \parallel s_2 \parallel \sigma)$ is a 4-sum for $\mathcal{H}$:

$$\mathcal{H}(m_i \parallel s_1 \parallel \sigma) \oplus \mathcal{H}(m_i \parallel s_2 \parallel \sigma) \oplus \mathcal{H}(m_j \parallel s_1 \parallel \sigma) \oplus \mathcal{H}(m_j \parallel s_2 \parallel \sigma) = 0.$$

Therefore we obtain a multiple 4-sum of arbitrary size $\lambda$ with the family of functions $\{\varphi_i\}_{i \in \mathbb{N}}$ defined as:

$$\varphi_i : \{0,1\}^* \to \{0,1\}^*, \quad x \mapsto x \parallel i.$$

Recall that the probability for an adversary performing $q$ queries to find at least one solution to an instance of the multiple 4-sum problem can be upper bounded by $(\lambda q)^{42-2^{-n} \cdot [\lambda/13]}/24$ from (3). In particular the probability of finding a multiple 4-sum with $\tilde{O}(2^{c/2})$ queries is negligible when $\lambda \gg 26c/n$, and we obtain a distinguisher with high probability for any fixed $n$, by choosing such a $\lambda$.

## 6 Analysis of the Double Sponge Construction

We now introduce multiple 4-sum distinguishers for the double sponge, using similar techniques as on the XOR combiner. Let $\mathcal{H}$ be a double sponge construction with permutations of width $b$ and rate $r$. Without loss of generality, we assume $n < r$ so that the squeezing phase does not apply any permutation. This means that the 4-sum condition is weaker than in the previous section, and it will require extra care in the section dedicated to the construction of the distinguisher.
## 6.1 Building a 4-sum on the Double Sponge

We first show how to build a 4-sum on the first $r$ bits of the output after $O(2^c)$ operations in the general case. Later, we will see that for specific choices of parameters $r$ and $c$, and also for specific choices of coefficients for the MIX operator, this cost can be reduced down to $O(2^{3c/4})$ operations.

The internal state of the double sponge is composed of two halves, each of $b$ bits, structured like a sponge internal state, with a rate and a capacity. We denote the two halves of a 2b-bit state $S$ as $S_1$ and $S_2$. Let $m, m'$ be two distinct messages, we denote the state of $\mathcal{H}$ after absorption of $m$ and $m'$ as $A$ and $B$:

$$S_{\mathcal{H}}(m) := (A_1, A_2) \qquad S_{\mathcal{H}}(m') := (B_1, B_2).$$

Let $x, y, z$ and $w$ be 4 message blocks. We consider a quadruple of messages ($m \parallel x, m' \parallel y, m \parallel z, m' \parallel w$), and the corresponding states after absorbing them:

$$ \begin{aligned} S_{\mathcal{H}}^*(m \parallel x) &= (A_1 \oplus (x \parallel 0^c), A_2 \oplus (x \parallel 0^c)) & S_{\mathcal{H}}^*(m' \parallel y) &= (B_1 \oplus (y \parallel 0^c), B_2 \oplus (y \parallel 0^c)) \\ S_{\mathcal{H}}^*(m \parallel z) &= (A_1 \oplus (z \parallel 0^c), A_2 \oplus (z \parallel 0^c)) & S_{\mathcal{H}}^*(m' \parallel w) &= (B_1 \oplus (w \parallel 0^c), B_2 \oplus (w \parallel 0^c)). \end{aligned} $$

Our goal is to choose $x, y, z$ and $w$ so that the four states above follow a specific structure that translates into pairwise equalities over both halves of the states just after XORing the last message block, similar to our attack on the XOR combiner:

$$ \left\{ \begin{array}{l} [S_{\mathcal{H}}^*(m \parallel x)]_1 = [S_{\mathcal{H}}^*(m' \parallel w)]_1 \quad [S_{\mathcal{H}}^*(m \parallel x)]_2 = [S_{\mathcal{H}}^*(m' \parallel y)]_2 \\ [S_{\mathcal{H}}^*(m \parallel z)]_1 = [S_{\mathcal{H}}^*(m' \parallel y)]_1 \quad [S_{\mathcal{H}}^*(m \parallel z)]_2 = [S_{\mathcal{H}}^*(m' \parallel w)]_2 \\ \iff \left\{ \begin{array}{l} A_1 \oplus (x \parallel 0^c) = B_1 \oplus (w \parallel 0^c) \quad A_2 \oplus (x \parallel 0^c) = B_2 \oplus (y \parallel 0^c) \\ A_1 \oplus (z \parallel 0^c) = B_1 \oplus (y \parallel 0^c) \quad A_2 \oplus (z \parallel 0^c) = B_2 \oplus (w \parallel 0^c). \end{array} \right. \end{array} \right. \quad (4) $$

The equalities in this system apply to half-states of $b$ bits. Note that $x, y, w$, and $z$ can only affect the first $r$ outer bits of each of these half-states. Therefore, for the system to be solvable, a preliminary condition must be satisfied on the remaining $c$ bits of these states. This condition can be written as follows:

$$ \left\{ \begin{array}{l} C(A_1) = C(B_1) \\ C(A_2) = C(B_2). \end{array} \right. \qquad (5) $$

Assuming that (5) holds — a point that will be examined at the end of this section — the system in (4) is equivalent to the following one applying to $r$-bit variables,

$$ \left\{ \begin{array}{l} x \oplus w = \mathcal{R}(A_1 \oplus B_1) \quad x \oplus y = \mathcal{R}(A_2 \oplus B_2) \\ z \oplus y = \mathcal{R}(A_1 \oplus B_1) \quad z \oplus w = \mathcal{R}(A_2 \oplus B_2). \end{array} \right. $$

We observe that the system is of rank 3 over $\mathbb{F}_{2^r}$, and has the following $2^r$ solutions $(x_i, y_i, w_i, z_i)$ for $i \in \mathbb{F}_{2^r}$:

$$ \left\{ \begin{array}{l} x_i = \mathcal{R}(A_1 \oplus A_2) \oplus i \quad y_i = \mathcal{R}(B_2 \oplus A_1) \oplus i \\ z_i = \mathcal{R}(B_1 \oplus B_2) \oplus i \quad w_i = \mathcal{R}(B_1 \oplus A_2) \oplus i. \end{array} \right. $$

Taking any solution of this system, we obtain a quadruple of messages such that the states after absorbing them have pairwise collisions of the half states, as seen in (4). This is a special case of a 4-sum in the internal state. Moreover, the pairwise collisions are preserved through the $P_1$ and $P_2$ permutations, so that we still have a 4-sum. Finally, the 4-sum is preserved by the MIX operation because it is linear. Therefore, we obtain a 4-sum in the states $S_{\mathcal{H}}(m \parallel x_i)$, $S_{\mathcal{H}}(m' \parallel y_i)$, $S_{\mathcal{H}}(m \parallel z_i)$, $S_{\mathcal{H}}(m' \parallel w_i)$, and this directly implies a 4-sum in the output (assuming $n < r$):

$$ \mathcal{H}(m \parallel x_i) \oplus \mathcal{H}(m' \parallel y_i) \oplus \mathcal{H}(m' \parallel w_i) \oplus \mathcal{H}(m \parallel z_i) = 0. $$

To summarize, we obtain $2^r$ distinct 4-sums on the double sponge construction as soon as the equations in (5) are verified.
## 6.2 Finding a Pair of States Satisfying Condition (5)

We now study how to construct two messages, $m$ and $m'$, such that condition (5) is satisfied.

### 6.2.1 Generic Case

The system expresses two constraints that fix random values over $c$ bits to zero. Therefore after processing $q$ distinct messages, there is a probability of $q^2 \cdot 2^{-2c-1}$ to find two messages $m$ and $m'$ that satisfy equation (5). Hence, we can build a multiple 4-collision with constant probability with $O(2^c)$ operations.

### 6.2.2 Improved attack for a Low-Diffusion MIX Operator and a Large Rate

While the generic analysis is applicable to any choice of the MIX operator$^6$, we now consider the specific MIX operator as defined in the double sponge proposal [LM24]:

$$ \text{MIX} = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}. $$

We observe that this choice of MIX operator provides very limited diffusion between the rate part and the capacity part of the state. More precisely, the element denoted as $2$ in $\mathbb{F}_{2^b}$ corresponds to the polynomial $X$ in the polynomial representation. Therefore, multiplication by $2$ is a bit-shift of the value by one position towards the most significant bit, followed by a reduction if the most significant bit was set. In particular, there is a single bit of mixing between the rate part and capacity part of the state; if we consider two $b$-bit states $X$ and $Y$, such that $C(X) = C(Y)$ and $X[b-1] = Y[b-1]$, then this implies $C(2 \cdot X) = C(2 \cdot Y)$.

In order to use this property, we denote the state before the MIX operation when processing $m$ (respectively $m'$) as $X$ (respectively $Y$), such that $\text{MIX}(X_1, X_2) = (A_1, A_2)$ and $\text{MIX}(Y_1, Y_2) = (B_1, B_2)$. That is:

$$ \begin{cases} (A_1, A_2) = (X_1 \oplus 2X_2, 2X_1 \oplus X_2) \\ (B_1, B_2) = (Y_1 \oplus 2Y_2, 2Y_1 \oplus Y_2). \end{cases} $$

Using this definition, equation (5) can be written as follow:

$$ \begin{cases} C(X_1 \oplus Y_1) = C((2X_2) \oplus (2Y_2)) \\ C(X_2 \oplus Y_2) = C((2X_1) \oplus (2Y_1)). \end{cases} $$

Following the previous discussion, the following condition is sufficient to ensure equation (5).

$$ \left\{ \begin{array}{l} C(X_1) = C(Y_1) \\ X_1[b-1] = Y_1[b-1] \quad X_2[b-1] = Y_2[b-1]. \end{array} \right. \qquad (6) $$

We replace a $2c$-bit condition after the MIX operation by a $2c+2$-bit condition before the MIX operation.

We propose an efficient algorithm to find pairs of states satisfying condition (6) when $r > 3c/4$. The idea of the algorithm is to construct many messages such that $C(X_1)$ (the capacity part of the first half of the state before the MIX operation) is fixed to zero. In particular, any pair of two such states $(X, Y)$ satisfies $C(X_1) = C(Y_1)$. We build those messages with a meet-in-the-middle approach, corresponding to the first three steps in the following description (depicted by Figure 6).

<footnote>$^6$The design rationale of the double sponge requires MIX to be a $2 \times 2$ MDS matrix such that the two coefficients in each row are not equal.</footnote>
1. **Forward Step:** Consider $2^{3c/4}$ messages $m_0^i$ and compute the 2b-bit inner state after absorption of $m_0^i$. Store the messages in a list indexed by $C([S_H(m_0^i)]_1)$ (the capacity part of the first half of the states).

2. **Backward Step:** Consider $2^{3c/4}$ b-bit states $X_1^j$ with $C(X_1^j) = 0$ and compute $P_1^{-1}(X_1^j)$. Store the states in a list indexed by $C(P_1^{-1}(X_1^j))$.

3. **Meeting Step:** Find matches between the two lists, that is pairs $(i, j)$ such that $C([S_H(m_0^i)]_1) = C(P_1^{-1}(X_1^j))$. From each match, we construct a two-block message $m_0^i \| m_1$, with $m_1 = R([S_H(m_0^i)]_1) \oplus R(P_1^{-1}(X_1^j))$ such that $P_1([S_H^*(m_0^i \| m_1)]_1) = X_1^j$. Since we are matching two lists of size $2^{3c/4}$ with a c-bit condition, we expect $2^{c/2}$ matches.

4. **Collision Step:** We have obtained $2^{c/2}$ messages $M^i$; we denote the corresponding state after the permutation as $X_1^i, X_2^i$:

$$X_1^i = P_1([S_H^*(M^i)]_1) \qquad X_2^i = P_2([S_H^*(M^i)]_2).$$

By construction we have $C(X_1^i) = 0$, hence $\forall i, j : C(X_1^i) = C(X_1^j)$. In order to satisfy (6), we look for a pair of messages $M^i, M^j$ such that:

$$C(X_2^i) = C(X_2^j) \qquad X_1^i[b-1] = X_1^j[b-1] \qquad X_2^i[b-1] = X_2^j[b-1].$$

Since this is a c + 2-bit condition, there is a constant probability that a solution exists.

**Complexity Analysis.** Step 1 and 2 and 3 requires $O(2^{3c/4})$ operations (using hash tables to sort the lists), while step 4 only requires $O(2^{c/2})$ operations.

Finally, we obtain a multiple 4-sum with complexity $O(2^{3c/4})$ when $r \ge 3c/4$, leveraging the behavior of multiplication by 2 over $F_{2^b}$. In particular, this indicates that the choice of the MIX operation has an impact on the security of the double sponge besides the conditions identified by Mennink and Lefevre. This improvement would not be possible if the MIX matrix was chosen with coefficients that mix strongly the rate part and the capacity part of the states.

### 6.2.3 Improved attack for a Low-Diffusion MIX Operator and a Small Rate

When the rate is small relative to the capacity ($r \le 3c/4$), it is still possible to find a pair of states that verify (6) with complexity below $O(2^c)$. We follow the same procedure with several adjustments, where $X[a : b]$ denotes the bits of state X from index a (included) to index b (excluded):

1. **Forward Step:** This step remains the same as before. Process $2^t$ random messages $m^i$ (potentially with several blocks) from the IV. The parameter $t$ will be set later in order to minimize the overall complexity.

Store the messages in a list indexed by $C([S_H(m^i)]_1)$.

2. **Backward Step:** Instead of fixing the full capacity of $X_1^j$ to zero, we only fix $b-u$ bits to zero, with $u$ a parameter to be optimized ($u \ge r$). Hence, we consider $2^u$ b-bit states $X_1^j$ with $X_1^j[0 : b - u] = 0$, and store the states in a list indexed by $C(P_1^{-1}(X_1^j))$.

3. **Meeting Step:** We obtain $2^{t+u-c}$ matches, corresponding to messages $M^i$ such that $X_1^i[0 : b - u] = 0$.
4. **Collision Step:** We are left with a $2c - (b - u) + 2 = c - r + u + 2$-bit condition to satisfy. In order to obtain a solution with constant probability we need $c - r + u + 2 \approx 2(t + u - c)$.

**Complexity Analysis.** The complexity of the procedure is $O(\max(2^t, 2^u, 2^{t+u-c}))$, with the constraint that $c - r + u + 2 \approx 2(t + u - c)$. The optimal complexity is obtained when $t = u = c - r/3$, with complexity $O(2^{c-r/3})$.

The full procedure (including both the small $r$ and large $r$ cases) is described as Algorithm 3.

## 6.3 Multiple 4-sum Distinguisher on the Double Sponge

As in the case of the XOR of two sponges, we observe that the previous algorithms provide a solution to a multiple 4-sum problem. Indeed, with complexity at most $O(2^c)$, we obtain a quadruple of messages $(x, y, w, z)$ such that for any integer $i < 2^r$:

$$ \mathcal{H}(x \oplus (0 \| i)) \oplus \mathcal{H}(y \oplus (0 \| i)) \oplus \mathcal{H}(w \oplus (0 \| i)) \oplus \mathcal{H}(z \oplus (0 \| i)) = 0. $$

Therefore, we define a multiple 4-sum problem with the following $\lambda = 2^r$ functions:

$$ \varphi_i : \{0,1\}^{\ge r} \to \{0,1\}^*, x \mapsto x \oplus (0^{|x|-r} \| i). $$

The probability to find a solution to the multiple 4-sum problem with fewer than $q$ queries can be upper bounded by $(\lambda q)^{42^{-n \cdot [\lambda/13]}}/24$ from (3). With $q = 2^c$, $\lambda = 2^r$ and $n = r$, we obtain a bound of $2^{4c+4r-r \cdot [2^r/13]}/24$. In particular the probability of finding a multiple 4-sum with $O(2^c)$ queries is negligible when $c \ll r \cdot 2^r/52$.

The right-hand side of this expression grows exponentially with $r$. Hence and we obtain a distinguisher with high probability for most practical parameters of the double sponge (e.g. when $r \ge 16$ and $c \le 2^{14}$).

## 7 Conclusion

In this work we introduced new distinguishers based on the multiple 4-sum problem on double block length sponge hashing.

First, we analyzed the security of combining two sponge constructions via a XOR of their outputs. Our key result is a 4-sum attack requiring only $O(c 2^{c/2})$ operations. This is the same bound as for a single sponge up to polynomial factors $(2^{c/2})$, and we obtain a tight indifferentiability bound for the XOR of two sponges (up to polynomial factors).

Then, we described a similar 4-sum technique to obtain a distinguisher on the double sponge with complexity $O(2^c)$ in general, and $O(\max(2^{3c/4}, 2^{c-r/3}))$ when using the specific MIX operator proposed in [LM24]. This significantly improves the best previous distinguisher with complexity $O(2^{c+r/2})$, making a step towards closing the security gap of this construction. In particular, we obtain the first attack whose complexity decreases with $r$, hinting that the actual security is unlikely to increase with $r$.

While we improve the understanding of these constructions by reducing the gap between proofs and attacks, several questions remain open. On the double sponge, we still do not have a tight indifferentiability bound. On the XOR of two sponges, even though we have a tight indifferentiability bound, the best collision and second-preimage attacks have complexity $O(2^{b/2})$ using the multicollision technique, leaving a gap with the indifferentiability bound of $2^{c/2}$. We leave those gaps open for future work.
<figure><img src="image_8.png" /><figcaption>**Figure 6:** Meet-in-the-middle phase of the 4-sum attack.</figcaption></figure>

**Algorithm 3** Double sponge meet-in-the-middle.

1: **Output:** $M, M'$ s.t. $\mathcal{C}([S_H(M)]_1) = \mathcal{C}([S_H(M')]_1)$ and $\mathcal{C}([S_H(M)]_2) = \mathcal{C}([S_H(M')]_2)$
2: **if** $r \le 3c/4$ **then**
3: &nbsp;&nbsp;&nbsp;&nbsp;$t \leftarrow c - r/3$, $u \leftarrow c - r/3$,
4: &nbsp;&nbsp;&nbsp;&nbsp;**else**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$t \leftarrow 3c/4$, $u \leftarrow 3c/4$,
6: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
7: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{L}_{\text{fw}} \leftarrow []$, $\mathcal{L}_{\text{bw}} \leftarrow []$, $\mathcal{M} \leftarrow []$
8: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 0$ to $2^t - 1$ **do**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$m \leftarrow [i]$
10: &nbsp;&nbsp;&nbsp;&nbsp;11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{L}_{\text{fw}}[\mathcal{C}(S_1)] \leftarrow m$
12: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
13: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = 0$ to $2^u - 1$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$X_1 \leftarrow j \parallel 0^{b-u}$
15: &nbsp;&nbsp;&nbsp;&nbsp;16: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$U_1 \leftarrow P_1^{-1}(X_1)$
17: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
18: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $k \in \text{KEYS}(\mathcal{L}_{\text{fw}})$ **do**
19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$m \leftarrow \mathcal{L}_{\text{fw}}[k]$ &nbsp;&nbsp;&nbsp;&nbsp;**▷ Meeting Step (match on c bits)**
20: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $X_1 \in \mathcal{L}_{\text{bw}}[k]$ **do**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$m_1 \leftarrow \mathcal{R}([S_H(m)]_1) \oplus \mathcal{R}(P_1^{-1}(X_1))$
22: &nbsp;&nbsp;&nbsp;&nbsp;23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(U_1, U_2) \leftarrow S_H^*(m \parallel m_1)$
24: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
25: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
26: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
27: &nbsp;&nbsp;&nbsp;&nbsp;**for all** $k \in \text{KEYS}(\mathcal{M})$ **do**
28: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $|\mathcal{M}[k]| \ge 2$ **then**
29: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $(\mathcal{M}[k][0], \mathcal{M}[k][1])$
30: &nbsp;&nbsp;&nbsp;&nbsp;**end if**
31: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
&nbsp;&nbsp;&nbsp;&nbsp;**▷ Forward Step**
&nbsp;&nbsp;&nbsp;&nbsp;**▷ Backward Step**
&nbsp;&nbsp;&nbsp;&nbsp;**▷ Collision Step**
References

[BBLS24] Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, and André Schrottenloher. Improving generic attacks using exceptional functions. In Leonid Reyzin and Douglas Stebila, editors, *CRYPTO 2024, Part IV*, volume 14923 of LNCS, pages 105–138. Springer, Cham, August 2024. doi:10.1007/978-3-031-68385-5_4.

[BDG+20] Zhenzhen Bao, Itai Dinur, Jian Guo, Gaëtan Leurent, and Lei Wang. Generic attacks on hash combiners. *Journal of Cryptology*, 33(3):742–823, July 2020. doi:10.1007/s00145-019-09328-w.

[BDPA07] G.M. Bertoni, Joan Daemen, Michael Peeters, and Gilles Assche. Sponge functions. *ECRYPT Hash Workshop 2007*, 01 2007.

[BDPV08] Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche. On the indifferentiability of the sponge construction. In Nigel P. Smart, editor, *EUROCRYPT 2008*, volume 4965 of LNCS, pages 181–197. Springer, Berlin, Heidelberg, April 2008. doi:10.1007/978-3-540-78967-3_11.

[BWGG17] Zhenzhen Bao, Lei Wang, Jian Guo, and Dawu Gu. Functional graph revisited: Updates on (second) preimage attacks on hash combiners. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part II*, volume 10402 of LNCS, pages 404–427. Springer, Cham, August 2017. doi:10.1007/978-3-319-63715-0_14.

[CDMP05] Jean-Sébastien Coron, Yevgeniy Dodis, Cécile Malinaud, and Prashant Puniya. Merkle-Damgård revisited: How to construct a hash function. In Victor Shoup, editor, *CRYPTO 2005*, volume 3621 of LNCS, pages 430–448. Springer, Berlin, Heidelberg, August 2005. doi:10.1007/11535218_26.

[Dam90] Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, *CRYPTO '89*, volume 435 of LNCS, pages 416–427. Springer, New York, August 1990. doi:10.1007/0-387-34805-0_39.

[DFG+23] Yevgeniy Dodis, Niels Ferguson, Eli Goldin, Peter Hall, and Krzysztof Pietrzak. Random oracle combiners: Breaking the concatenation barrier for collision-resistance. In Helena Handschuh and Anna Lysyanskaya, editors, *CRYPTO 2023, Part II*, volume 14082 of LNCS, pages 514–546. Springer, Cham, August 2023. doi:10.1007/978-3-031-38545-2_17.

[Din16] Itai Dinur. New attacks on the concatenation and XOR hash combiners. In Marc Fischlin and Jean-Sébastien Coron, editors, *EUROCRYPT 2016, Part I*, volume 9665 of LNCS, pages 484–508. Springer, Berlin, Heidelberg, May 2016. doi:10.1007/978-3-662-49890-3_19.

[Jou04] Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded constructions. In Matthew Franklin, editor, *CRYPTO 2004*, volume 3152 of LNCS, pages 306–316. Springer, Berlin, Heidelberg, August 2004. doi:10.1007/978-3-540-28628-8_19.

[KS05] John Kelsey and Bruce Schneier. Second preimages on n-bit hash functions for much less than 2n work. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 474–490. Springer, Berlin, Heidelberg, May 2005. doi:10.1007/11426639_28.
[Leh10] Anja Lehmann. *On the security of hash function combiners*. PhD thesis, Darmstadt University of Technology, 2010. URL: http://tuprints.ulb.tu-darmstadt.de/2094/.

[LM22] Charlotte Lefevre and Bart Mennink. Tight preimage resistance of the sponge construction. In Yevgeniy Dodis and Thomas Shrimpton, editors, *CRYPTO 2022, Part IV*, volume 13510 of LNCS, pages 185–204. Springer, Cham, August 2022. doi:10.1007/978-3-031-15985-5_7.

[LM24] Charlotte Lefevre and Bart Mennink. Permutation-based hashing beyond the birthday bound. *IACR Trans. Symm. Cryptol.*, 2024(1):71–113, 2024. doi:10.46586/tosc.v2024.i1.71-113.

[LNS18] Gaëtan Leurent, Mridul Nandi, and Ferdinand Sibleyras. Generic attacks against beyond-birthday-bound MACs. In Hovav Shacham and Alexandra Boldyreva, editors, *CRYPTO 2018, Part I*, volume 10991 of LNCS, pages 306–336. Springer, Cham, August 2018. doi:10.1007/978-3-319-96884-1_11.

[LW15] Gaëtan Leurent and Lei Wang. The sum can be weaker than each part. In Elisabeth Oswald and Marc Fischlin, editors, *EUROCRYPT 2015, Part I*, volume 9056 of LNCS, pages 345–367. Springer, Berlin, Heidelberg, April 2015. doi:10.1007/978-3-662-46800-5_14.

[Mer90] Ralph C. Merkle. A certified digital signature. In Gilles Brassard, editor, *CRYPTO '89*, volume 435 of LNCS, pages 218–238. Springer, New York, August 1990. doi:10.1007/0-387-34805-0_21.

[MRH04] Ueli M. Maurer, Renato Renner, and Clemens Holenstein. Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In Moni Naor, editor, *TCC 2004*, volume 2951 of LNCS, pages 21–39. Springer, Berlin, Heidelberg, February 2004. doi:10.1007/978-3-540-24638-1_2.

[MS88] Carl H Meyer and Michael Schilling. Secure program load with manipulation detection code. In *Proc. Securicom*, volume 88, pages 111–130, 1988.

[Wag02] David Wagner. A generalized birthday problem. In Moti Yung, editor, *CRYPTO 2002*, volume 2442 of LNCS, pages 288–303. Springer, Berlin, Heidelberg, August 2002. doi:10.1007/3-540-45708-9_19.

A Indifferentiability of the XOR of Two Sponges

**Lemma 1.** Let $\mathcal{H} := \mathcal{H}_1 \oplus \mathcal{H}_2$, where $\mathcal{H}_1$ and $\mathcal{H}_2$ are two sponge constructions based on two permutations $P_1$ and $P_2$, each working on $b = r + c$ bits.

Then $\mathcal{H}$ is indifferentiable from a random oracle up to $O(2^{c/2})$ queries to $P_1$ and $P_2$.

*Proof.* The strategy is to show that if an adversary can distinguish $\mathcal{H}^{P_1,P_2}$ from a random oracle, then the same adversary can also distinguish, for instance, $\mathcal{H}_1^{P_1}$ from a random oracle. Since a single sponge construction, such as $\mathcal{H}_1^{P_1}$, is known to be tightly indifferentiable from a random oracle up to $O(2^{c/2})$ permutation queries [BDPV08], it follows that the initial adversary cannot do better. Hence, $\mathcal{H}^{P_1,P_2}$ cannot be distinguished from a random oracle using fewer than $O(2^{c/2})$ permutation queries.

Suppose $\mathcal{A}$ is an adversary that distinguishes $(\mathcal{H}^{P_1,P_2}, (P_1, P_2))$ from $(\mathcal{RO}, \mathcal{S}^{\mathcal{RO}})$ after $q$ permutation queries, where $\mathcal{S}^{\mathcal{RO}}$ is any simulator.

We can then construct another adversary, $\mathcal{A}'$, that distinguishes the single sponge construction $\mathcal{H}_1^{P_1}$ from a random oracle $\mathcal{RO}'$ after $q$ queries to $P_1$. The construction of $\mathcal{A}'$
is described in Algorithm 4. Essentially, $\mathcal{A}'$ internally simulates $\mathcal{H}_2$ and forwards all $\mathcal{H}_1$ interactions to the single sponge oracle. Whenever $\mathcal{A}$ queries $\mathcal{H}$, $\mathcal{A}'$ returns the XOR of the response from the single sponge and the simulated $\mathcal{H}_2$ to maintain consistency.

Since $\mathcal{A}'$ cannot distinguish $\mathcal{H}_1^{P_1}$ from a random oracle using fewer than $\mathcal{O}(2^{c/2})$ queries, neither can $\mathcal{A}$ distinguish $\mathcal{H}^{P_1,P_2}$ from a random oracle. This completes the proof.

**Algorithm 4** Adversary $\mathcal{A}'$ to distinguish $\mathcal{H}_1^{P_1}$ from $\mathcal{RO}'$

**Require:** Input $(h, p)$, either $(\mathcal{H}_1^{P_1}, P_1)$ or $(\mathcal{RO}', (\mathcal{S}'^{\mathcal{RO}'}))$

**Ensure:** 1 if the pair is $(\mathcal{H}_1^{P_1}, P_1)$, 0 otherwise

1: Select a random permutation $P$ over $b$ bits

2: Define $\mathcal{H}_2^P$ as the sponge construction based on $P$

3: Run $\mathcal{A}$ on inputs $(h \oplus \mathcal{H}_2^P, (p, P))$

4: Return the output of $\mathcal{A}$

Let $\mathcal{S}'$ be a simulator that mimics the behavior of a permutation for the sponge construction. From this simulator we can build the simulator $\mathcal{S}$, described in Algorithm 5, that interacts with $\mathcal{A}$ in the initial game, where $\mathcal{S}$ is supposed to offer a similar behavior to a pair of permutations $(P_1, P_2)$ used in the XOR combiner. By definition of the distinguishing game, $\mathcal{S}$ is given access to a random oracle $\mathcal{RO}$. We now study the advantage of each

**Algorithm 5** Simulator $\mathcal{S}$ for the indifferentiability game of $\mathcal{A}$

**Require:** Input $(x, y) \in \{(0, 1)^b\}^2$

**Ensure:** Two elements of $\{0, 1\}^b$

1: **if** first call to $\mathcal{S}$ **then**

2: Select a random permutation $P$ over $b$ bits

3: **end if**

4: Define $\mathcal{H}_2^P$ as the sponge construction based on $P$

5: Run $\mathcal{S}'$ on input $x$ with oracle access to $\mathcal{RO} \oplus \mathcal{H}_2^P$ ▷ Gives $\mathcal{S}'(x)$

6: Return $(\mathcal{S}'(x), P(y))$

adversary in its respective game. Note that if $(h, p) = (\mathcal{H}^{P_1}, P_1)$, then the third step of $\mathcal{A}'$ corresponds to a call of $\mathcal{A}$ on $(\mathcal{H}^{P_1,P_2}, (P_1, P_2))$. Otherwise, if $(h, p) = (\mathcal{RO}', \mathcal{S}'^{\mathcal{RO}'})$, then the third step of $\mathcal{A}'$ becomes a call to $\mathcal{A}$ on $(\mathcal{RO}, \mathcal{S}^{\mathcal{RO}})$, where $\mathcal{RO} := \mathcal{RO}' \oplus \mathcal{H}_2^P$.

Since the simulator $\mathcal{S}$ relies only on the performance of $\mathcal{S}'$, both adversaries reach the same advantage in their respective games. In other words, when both $\mathcal{A}$ and $\mathcal{A}'$ are allowed to perform $q$ queries, we have:

$$ \mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}^{P_1,P_2}, \mathcal{S}^{\mathcal{RO}}}(\mathcal{A}) = \mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}_1^{P_1}, \mathcal{S}'^{\mathcal{RO}'}}(\mathcal{A}'). \quad (7) $$

But we know that a single sponge achieves tight indifferentiability up to $\mathcal{O}(2^{c/2})$ queries. More formally, from [BDPV08] we know that there exists a version of $\mathcal{S}'$ that achieves the following upper bound

$$ \mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}^{P_1}, \mathcal{S}'^{\mathcal{RO}}}(\mathcal{A}') \le \frac{q^2}{2^c}. \quad (8) $$

Combining (7) and (8) we have that the XOR combiner is indifferentiable from a random oracle up to $\mathcal{O}(2^{c/2})$ queries. $\square$