Internship Report -MPRI M2 Generic Attacks on
Sponge Based Hash Combiners

César Mathéus

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

To cite this version:

César Mathéus. Internship Report -MPRI M2 Generic Attacks on Sponge Based Hash Combiners. Computer Science [cs]. 2025. hal-05518009

HAL Id: hal-05518009

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

Submitted on 19 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_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Internship Report - MPRI M2
Generic Attacks on Sponge Based Hash Combiners

César Mathéus supervised by Gaëtan Leurent, INRIA Paris, EPI Cosmiq

11/07/2025

**General context**

In cryptography, hash functions play a central role, for instance as tools in protocols ensuring data integrity, digital signatures, or password storage. A hash function takes an arbitrarily long bit string as input and outputs a fixed-length bit string. Unlike symmetric and asymmetric encryption algorithms, 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.

For cryptographic purposes, hash functions must balance security and efficiency. The most common approach is to design hash functions 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.

Generic attacks refer to procedures or algorithms that target the mode of operation rather than the specific inner primitive. In this report, we describe generic attacks that we developed against a particular mode of operation.

**Research problem**

We study two modes of operation that exhibit structural similarities. Both are based on the well-known and well-studied Sponge construction. It operates on a state of size $b = r+c$ bits, where the rate $r$ governs efficiency and the capacity $c$ governs security. The sponge construction is proven to be tightly secure up to $O(2^{c/2})$ calls to its internal permutation.

The first construction we studied consists of XORing the outputs of two sponge functions. The second is a recent design published in the journal Transactions on Symmetric Cryptography (ToSC) in 2024, known as the Double Sponge construction.

While the XOR of two iterated hash functions has been extensively studied in the case of the Merkle – Damgård construction, the case of sponge-based constructions has received much less attention. This is likely because alternative methods exist to increase the security of a single sponge construction. However, such methods often reduce overall efficiency, which is less of a concern with the XOR combiner. This motivated us to study the XOR combiner on its own.

Yet, ultimately, our goal was to study the Double Sponge construction which was introduced together with both lower and upper bounds on its security. However, these bounds do not match, and therefore the security of the construction remains untight. Because the XOR combiner and the Double Sponge share some structural similarities, we hoped they might also share structural weaknesses. This further motivated our work on the XOR combiner, as it remains a simpler construction to analyze.
## Your contribution

We obtained results for both constructions. For the XOR combiner, we show that it is roughly as secure as a single sponge construction, within the usual framework for proving security in this context—namely, the indifferentiability framework.

We proved that the XOR combiner is indifferentiable from a random oracle up to $\Omega(2^{c/2})$ permutation calls, which matches the bound of a single sponge. We also developed a generic attack using message quadruples (instead of pairs) to produce 4-sums. This attack requires $O(c2^{c/2})$ operations, which matches the lower bound up to logarithmic factors and suggests that the XOR combiner is no more secure than a single sponge.

As we hoped, we were able to transfer this technique to the Double Sponge construction. Previously, its lower and upper security bounds were $\tilde{\Omega}(2^{2c/3})$ and $\tilde{O}(2^{c+r/2})$, respectively.

By adapting our message-quadruple collision approach, we managed to reduce the exponential factor of the upper bound to $\tilde{O}(2^c)$ in the general setting, and even down to $\tilde{O}(2^{3c/4})$ in some scenarios. Although the security gap is not yet closed, this improvement deviates from what the authors originally conjectured. In particular, they expected the lower bound could be raised and would depend on the parameter $r$. Our new upper bound shows that this unlikely that the security increases with $r$.

## Arguments supporting its validity

We provide proofs for our results. These are based on the indifferentiability framework, which is widely used to analyze the security of hash function constructions. We also implemented the aforementioned attacks and observed that, for feasible parameters, the practical complexity matched our theoretical predictions.

## Summary and future work

We are confident in both the relevance and the correctness of our results and plan to submit them to the next edition of ToSC, the journal in which the Double Sponge was originally published.

We believe that our attacks on the Double Sponge can be further improved. However, improving the lower bound appears to be a tedious task, as even the original authors pointed out. It may also be interesting to study how these bounds behave in a security model featuring quantum adversaries. Quantum cryptanalysis is currently a trending topic, and it is possible that new algorithms could achieve significant speed-ups in this context.

## Acknowledgments

I would like to express my deepest gratitude to my internship supervisor, Gaëtan Leurent, for his exceptional guidance and support throughout my internship. His patience, availability, and insightful feedback have been invaluable to my learning experience, and I especially appreciated the clarity of his advice and the way he encouraged me to improve and give my best. I would also like to warmly thank the COSMIQ team at Inria for their very kind welcome, and in particular Anne Canteaut, who gave me the opportunity to meet my supervisor.
# 1 Introduction

Secure hash function design is central in symmetric cryptography. Most practical hash functions use an iterative structure based on an internal function or permutation repeated multiple times. Security depends on both this primitive and its mode of operation.

Two main modes exist: Merkle-Damgård [Dam90], iterating a compression function, and the sponge construction [BDPV08], iterating a permutation on $b = r + c$ bits. These underlie SHA-2 and SHA-3 respectively.

During this internship, we focused on studying the security of combining two sponge constructions via XOR (the sum). While the sum of two Merkle-Damgård constructions is well-studied [Jou04, LW15, Din16, LNS18, BDG$^+$20], no similar results exist for sponges. We also analyze the double sponge [LM24], introduced in 2024, which offers security beyond the birthday bound for some parameters.

## 1.1 Our Contribution

First, we show that using at most $\tilde{O}(2^{c/2})$ primitive queries, it is possible to build a quadruple of messages such that their images under the XOR of two sponge constructions sum to 0. We then show that this procedure can be used to differentiate the construction from a random oracle. We complement this with a matching security proof showing indifferentiability of the construction from a random oracle up to $\tilde{\Omega}(2^{c/2})$ permutation calls. Up to logarithmic factors those bounds match the security upper and lower bound of a single sponge construction. In consequence we prove that the sum of two sponge construction is as secure as a single sponge.

Second, we extend this technique to the double sponge, which resists attacks up to $\tilde{\Omega}(2^{2c/3})$ permutation calls, while the best known attack requires $\tilde{O}(2^{c+r/2})$. Our variant collision attack requires $\tilde{O}(2^c)$ calls generally. Moreover, the double sponge relies on the application of a $2 \times 2$ MDS matrix to its inner state at each iteration and we show that for specific choices of matrices, such as the one chosen in the redaction of [LM24] the cost of this attack can be reduced down to $\tilde{O}(2^{3c/4})$ when $r \ge 3c/4$, and $\tilde{O}(2^{c-r/3})$ otherwise, improving the previous bound.

# 2 Preliminaries

We usually state the meaning of notations used in this report. We also made a notation summary available in Sect A.

## 2.1 Basic Security Notions

**Definition 2.1 (Hash function).** We define as a hash function any function of the form $\mathcal{H} : \{0,1\}^* \rightarrow \{0,1\}^n$.

Ideally, a cryptographic hash function is expected to behave like a random function. This is a concept captured by the indifferentiability framework [MRH04]. In particular a hash function should resist collisions, preimages and second preimages which can be informally described as follow :

**Definition 2.2 (Basic security notions).**

* **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)$.

* **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}$.

These concepts provide the most common examples of types of attacks that can be mounted against a hash function. More generally, any procedure that reveals a phenomenon which would occur with low probability on a truly random oracle can be considered an attack. This can be formalized using the indifferentiability framework, for which we provide the main definitions.

In Table 1, we give a brief summary of currently known collision, preimage and second-preimage resistance of the Merkle-Damgård construction, the sponge, the sum of two Merkle Damgård and an ideal hash function modeled as a random oracle. When analyzing the generic security of iterated hash constructions

<table><caption>Table 1: Best known classical generic attacks, i.e., security upper bounds, on various hash functions including the ideal random oracle.</caption><thead><tr><th>Construction</th><th>Security lower bound</th><th>Collision</th><th>Preimage</th><th>Source</th></tr></thead><tbody><tr><td>Merkle-Damgård (n-bit state)</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>n</sup></td><td>[CDMP05, KS05]</td></tr><tr><td>Sponge (n-bit output, capacity c)</td><td>2<sup>c/2</sup></td><td>2<sup>min(c/2, n/2)</sup></td><td>2<sup>min(c/2, n/2)</sup></td><td>[AMP11, LM22]</td></tr><tr><td>XOR of two MD (n-bit state)</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup></td><td>2<sup>3n/5</sup></td><td>[Jou04, BHBLS24]</td></tr><tr><td>Random Oracle (n-bit output)</td><td>-</td><td>2<sup>n/2</sup></td><td>2<sup>n</sup></td><td>Standard bounds</td></tr></tbody></table>

such as the Merkle-Damgård or the sponge construction we very frequently make use of a particular phenomenon: the birthday paradox. Indeed for instance the most efficient way to build a collision in such constructions is to use several messages to build a large amount of different internal states and look among them for a pair of identical states. When $n$ is the size in bits of each state and $q$ is the number of states that are generated, the birthday paradox indicates that there is a non-negligible probability of finding a collision when $q \approx 2^{n/2}$. Note that in the rest of this report, for ease of notation, we will always follow the same approach that is giving approximations that specific events, such as collisions, have a non negligible probability of occurring.

## 2.2 The Indifferentiability Framework

### 2.2.1 Indistinguishability

Let $S_0, S_1$ be two systems. An adversary $\mathcal{A}$ interacts with $S_k$ where $k$ is drawn at random from $\{0, 1\}$. The distinguisher is allowed to perform at most $q$ queries stored in a query history and it tries to guess the system it has interacted with. The advantage of $\mathcal{A}$ in the so called 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]|. \qquad (1) $$

Note that the supremum of the set of $\mathrm{Adv}_{\mathrm{ind}}^{S_0, S_1}(\mathcal{A})$ for all adversaries $\mathcal{A}$ making at most $q$ queries is written $\mathrm{Adv}_{\mathrm{ind}}^{S_0, S_1}(q)$.

### 2.2.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. Usually, designers aim at building hash functions that are computationally hard to distinguish from a random oracle for them to be considered secure. 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 hash function $\mathcal{H}^P$ that utilizes an invertible ideal primitive $P$ and a random oracle $\mathcal{RO}$ which shares the same domain and co-domain as $\mathcal{H}$. Let $S^{\mathcal{RO}} := (S_{\text{fwd}}, S_{\text{inv}})^{\mathcal{RO}}$ be a simulator, with the restriction of making no more than $q$ queries to the oracle $\mathcal{RO}$ such that both $S_{\text{fwd}}$ and $S_{\text{inv}}$ have the same domain as $P$. Let $\mathcal{A}$ represent an adversary which is allowed to make at most $q_{\mathcal{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}). \quad (2) $$

The underlying idea of indistinguishability is that if two systems, $S_0$ and $S_1$, cannot be distinguished from one another, then they exhibit similar behavior. This notion becomes particularly meaningful when $S_0$ represents a concrete cryptographic construction and $S_1$ an idealized object. However, traditional indistinguishability does not directly apply in the context of hash functions, as these are public objects without components that remain secret from the distinguisher such as a key. In consequence, the indifferentiability framework offers a means to analyze the security of a public construction or mode of operation under the assumption that its underlying primitive behaves like an ideal object. The distinguisher is supposed to have access to this ideal inner primitive. Hence to mimic the same interface on both sides, it is required to build an object that behaves like this ideal primitive on the side of the random oracle $\mathcal{RO}$. This is the role played by the simulator $S^{\mathcal{RO}}$. Note that the supremum of the set of $\mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}^P, S^{\mathcal{RO}}}(\mathcal{A})$ for all adversaries $\mathcal{A}$ making at most $q_{\mathcal{H}}$ construction queries and $q_P$ primitive queries is written $\mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}^P, S^{\mathcal{RO}}}(q_{\mathcal{H}}, q_P)$. On one side a generic attack such as a collision or a preimage generally gives an upper bound of the security achievable by a construction. 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. We summarized in Table 2 various known security bounds for hash constructions.

<table><caption>Table 2: Generic indifferentiability bounds of various constructions.</caption><thead><tr><th rowspan="2">Construction</th><th colspan="2">Indifferentiability</th></tr><tr><th>Lower Bound</th><th>Upper Bound</th></tr></thead><tbody><tr><td>Merkle-Damgård (n-bit state)</td><td>2<sup>n/2</sup> [CDMP05]</td><td>2<sup>n/2</sup> [CDMP05]</td></tr><tr><td>Sponge (n-bit output, capacity c)</td><td>2<sup>c/2</sup> [BDPV08]</td><td>2<sup>c/2</sup> [BDPV08]</td></tr><tr><td>XOR of two MD (n-bit state)</td><td>2<sup>n/2</sup></td><td>2<sup>n/2</sup> [Jou04]</td></tr><tr><td>XOR of two Sponges (capacity c)</td><td>2<sup>c/2</sup> [this work]</td><td>2<sup>c/2</sup> [this work]</td></tr><tr><td>the Double Sponge (capacity c)</td><td>2<sup>2c/3</sup> [LM24]</td><td>max(2<sup>3c/4</sup>, 2<sup>c-r/3</sup>) [this work]</td></tr></tbody></table>

### 2.2.3 How to use unlikely events to differentiate

A way to distinguish a 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 to distinguish them. We take inspiration from the generalized birthday problem first defined by David Wagner and present his original definition of the generalized birthday problem:

[Wag02] **Problem 2.** 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. $$
From this definition in the case where $k = 4$, we formulate what we call the multiple 4-sum problem.

**Definition 2.3** (The multiple 4-sum problem). Let $\mathcal{H}$ be a iterated hash function, $\alpha, \beta$ be positive integers and $\{\varphi_i : \{0, 1\}^* \to \{0, 1\}^*\}_{0 \le i < \alpha}$ a finite family of injective functions two by two different. The generalized 4-sum problem consists of finding a quadruple of distinct messages $\{x, y, w, z\}$ such that:

$$ \forall i \in \{0, 1, \dots, \alpha - 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)) \stackrel{\beta}{=} 0. \qquad (3) $$

with the following condition to avoid redundancy in the outputs of the functions $\varphi_i$:

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

This definition has the benefit of concisely describing different variants of 4-sums, such as the one we will discuss in the following sections. In terms of design rationale, the parameter $\alpha$ represents the number of different 4-sums, while $\beta$ corresponds to the length of the output on which the four messages are expected to collide. Hence, it allows the study of the behavior of partial collisions.

From the definition of a random oracle, each message is mapped independently and uniformly to a bit string of length at least $\beta$. We are interested in the probability that there exists at least one 4-tuple of distinct messages $(x, y, w, z)$ among the $q$ queried ones such that equations (3) are all satisfied. For such a 4-tuple to be a solution, it must satisfy each of the $\alpha$ independent $\beta$-bit constraints. Consequently, a fixed 4-tuple has probability $2^{-\alpha\beta}$ of being a solution to the multiple 4-sum problem.

Note that various phenomenon play in favor of the adversary. First there may exists $x \neq y \in \{0, 1\}^*$ and $i \neq j$ such that $\varphi_i(x) = \varphi_j(y)$. Such structure may be used by the adversary to reduce the average amount of queries needed to detect a 4-sum. Furthermore the $\varphi_i$ may displays extra structure, for example if:

$$ \left\{ \begin{array}{ll} \varphi_i(x) = \varphi_j(y) & \varphi_i(z) = \varphi_j(w) \\ \varphi_i(y) = \varphi_j(x) & \varphi_i(w) = \varphi_j(z) \end{array} \right. \qquad (5) $$

Then, a 4-sum on the $\varphi_i$ may imply one on $\varphi_j$. To guarantee independance among all quadruples images under different $\varphi_i$, we can restrict ourselves to a subset $J \subset \{\varphi_i : \{0, 1\}^* \to \{0, 1\}^*\}_{0 \le i < \alpha}$ such that $\forall i, j \in J, i \neq j, \forall u, v \in \{x, y, w, z\}, u \neq v$ we have $\varphi_i(u) \neq \varphi_j(v)$. We wish to have $J$ as large as possible, hence the following work to show a lower bound on a such $J$ of maximal size.

Since the functions $\varphi_i$ are injective and must all satisfy (4), for a fixed index $i$ and an element of the quadruple, for instance $x$, there are at most 3 elements of the form $\varphi_j(u)$, where $u \in \{y, w, z\}$ and $j$ is a positive integer different from $i$ and less than $\alpha$, such that $\varphi_i(x) = \varphi_j(u)$. Indeed, there is at most one for $y$, one for $w$, one for $z$, and none for $x$.

This remark also applies to the other elements of the quadruple: each can be associated with at most 3 images of the remaining elements for other $\varphi_j$. Consequently, for a fixed $i$, there are at most 11 indexes $j$ different from $i$ such that $\varphi_i(\{x, y, w, z\}) \cap \varphi_j(\{x, y, w, z\}) \neq \emptyset$

Therefore, it is possible to build $J$ as previously defined such that $|J| \ge \alpha/12$. The probability that a fixed quadruple satisfies all the constraints derived from its associated set $J$ is then $2^{-\alpha/12}$.

A last pitfall is that an adversary doesn't need to check all $\alpha$ equations of the multiple 4-sum to ensure that a quadruple is not a solution to the multiple 4-sum problem. In consequence we have the following upper bound on the average amount of solutions, written $X$ after $q$ queries:

$$ \mathbb{E}[X] \le \binom{\alpha q}{4} \cdot \frac{1}{2^{\frac{\alpha \beta}{12}}} \le \frac{(\alpha q)^{4} 2^{-\frac{\alpha \beta}{12}}}{24}. \qquad (6) $$

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

$$ P[X \ge 1] \le \frac{(\alpha q)^4 2^{-\frac{\alpha \beta}{12}}}{24} \qquad (7) $$
## 2.3 The Sponge, The Xor Combiner and the Double Sponge

**Definition 2.4.** (Sponge Construction, [BDPA07]) The sponge construction is an iterated construction for building a hash function $\mathcal{H}$ with variable-length input and arbitrary output length based on a fixed-length 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 bitrate and the value $c$ the capacity. The operation of the sponge construction is described in Algorithm 1.

**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$^P(M, n)\{0, 1\}^* \times \mathbb{N} \rightarrow \{0, 1\}^*
/* The state $S$ is initialized and the message is padded and split into $r$-bit blocks */
2: $S \leftarrow IV$
3: $M_1 \parallel \cdots \parallel M_k \leftarrow \text{pad}(M)$
/* Absorbing phase */
4: **for** $i = 1, \dots, k$ **do**
5: $S \leftarrow P(S \oplus (M_i \parallel 0^c))$
6: **end for**
/* Squeezing phase */
7: **for** $i = 1, \dots, \lfloor n/r \rfloor$ **do**
8: $Z_i \leftarrow \text{outer}_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**

<figure><img src="image_3.png" /><figcaption>Figure 1: The Sponge construction</figcaption></figure>

Note that the sponge construction, when instantiated with a random permutation $P$, is proven to be indifferentiable from a random oracle up to $O(2^{c/2})$ calls to $P$. This implies resistance up to this bound for the three security notions previously defined. These bounds have all been proven to be tight, i.e., generic attacks reaching these bounds in terms of queries to $P$ have been established.

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 constructions interacting with messages whose lengths are always considered multiples of the rate.

**Definition 2.5 (XOR Combiner of Two Sponges).** Let $\mathcal{H}_1$ and $\mathcal{H}_2$ be two sponge constructions defined over the same parameters $b = r+c$, instantiated with two different $b$-bit random permutations, respectively
$P_1$ and $P_2$. We define the XOR combiner as the hash function $\mathcal{H} : \{0, 1\}^* \to \{0, 1\}^n$ such that

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

Its operation is described in Algorithm 2.

**Algorithm 2** The xor of two sponges construction. The algorithm takes as input the message to hash $M$ and the number of bits of the stream to extract $n$. $IV_1, IV_2 \in \{0, 1\}^b$ are two fixed initialization vectors.

1: **function XOR OF TWO SPONGES$^{P_1,P_2}$(M, n)$\{0, 1\}^* \times \mathbb{N} \to \{0, 1\}^*$**
/* The state $S$ is initialized and the message is padded and split into $r$-bit blocks */

2: $(S_1, S_2) \leftarrow (IV_1, IV_2)$

3: $M_1 \parallel \cdots \parallel M_k \leftarrow \text{pad}(M)$

/* Absorbing phase */

4: **for** $i = 1, \dots, k$ **do**

5: $(S_1S_2) \leftarrow (P_1(S_1 \oplus (M_i \parallel 0^c)), P_2(S_2 \oplus (M_i \parallel 0^c)))$

6: **end for**

/* Squeezing phase */

7: **for** $i = 1, \dots, \lfloor n/r \rfloor$ **do**

8: $Z_i \leftarrow \text{outer}_r(S_1) \oplus \text{outer}_r(S_2)$

9: $(S_1, S_2) \leftarrow (P_1(S_1), P_2(S_2))$

10: **end for**

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

12: **end function**

<figure><img src="image_4.png" /><figcaption>Figure 2: The Xor of Two Sponges construction</figcaption></figure>

**Definition 2.6** (The Double Sponge). As mentioned before, the double sponge is a construction proposed by Bart Mennink and Charlotte 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. During the absorption phase, the double sponge operates similarly to the XOR combiner of two sponges, with the key difference being that the two internal states are mixed using 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 state 1 is squeezed, as in a single sponge construction. Algorithm 3 defines the double sponge, and Figure 3 illustrates its operation.

Note that we also introduce two notations that will be heavily used throughout this report.

The first one designates the state of a sponge based construction after full absorption of a message from IV, that is the state right before it is able to absorb another message block. For a construction $\mathcal{H}$ and a message $M_0$ we write this state $S_{\mathcal{H}}(M_0)$. The second state designates the state of $\mathcal{H}$ right after it has xored the last message block it has received. For a message $M_0 \parallel m_1$ we write this state $S_{\mathcal{H}}^*(M_0 \parallel m_1)$.

**Algorithm 3** The double sponge construction based on $P := (P_1, P_2)$. The algorithm takes as input the message to hash $M$ and the number of bits of the stream to extract $n$. pad is an injective padding with the same restrictions as for the sponge construction $IV_1$ and $IV_2$ are two fixed initialization vectors.

function $\mathcal{H}^P(M, n)\{0, 1\}^* \times \mathbb{N} \to \{0, 1\}^*$

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

$(S_1, S_2) \leftarrow (IV_1, IV_2)$

$M_1 \parallel \cdots \parallel M_k \leftarrow \text{pad}(M)$

/* Absorbing phase */

for $i = 1, \dots, k$ do

$(S_1, S_2) \leftarrow \text{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, \dots, \lfloor n/r \rfloor$ do

$Z_i \leftarrow \text{outer}_r((S_1, S_2))$

$(S_1, S_2) \leftarrow \text{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

<figure><img src="image_5.png" /><figcaption>Figure 3: The Double Sponge construction</figcaption></figure>

## 3 Previous Works and Useful Collision Techniques

This section presents a series of collision attacks against the XOR of two sponge constructions. It introduces two key notions in the field of generic attacks: the birthday paradox and the multicollision technique, both
of which will be used later in more complex attacks based on the multiple 4-sum problem.

In this section, $\mathcal{H}_1$ and $\mathcal{H}_2$ denote two sponge constructions operating on a $b$-bit state, and $\mathcal{H}$ denotes the XOR combiner of $\mathcal{H}_1$ and $\mathcal{H}_2$.

## 3.1 Naive Attack Based on the Birthday Paradox

We first describe a basic approach to build two colliding messages $M_0 \neq M_1$ such that $\mathcal{H}(M_0) = \mathcal{H}(M_1)$. This type of procedure often involves manipulating the states of a sponge.

By convention, a state of $b$ bits can be seen as a $b$-bit string, where the first $r$ most significant bits correspond to the rate, and the last $c$ bits correspond to the capacity.

Recall that $\stackrel{x}{=}^r$ is the notation used to indicate equality of the first $x$ bits of two bit strings. Hence, if two sponge states $A$ and $B$ satisfy $A \stackrel{x}{=}^r B$, they share the same rate.

We also denote $A^c$ as the capacity portion of $A$. Thus, $A$ and $B$ have the same capacity if $A^c = B^c$.

Finally, we often need to XOR the rate portions of two states. This operation, which takes two $b$-bit states as input and outputs an $r$-bit string, is denoted by $\oplus^r$. For example, $A \oplus^r B$ corresponds to the XOR of the rate portions of $A$ and $B$.

**First Step:** Absorb $q$ distinct messages from initial states of $\mathcal{H}_1$ and $\mathcal{H}_2$: $IV_1$ and $IV_2$. We search for two messages $m_i$ and $m_j$ such that the two states of the construction obtained after the absorptions of those messages have the same difference in both rates parts of the state, This can be written as:

$$ \left\{ \begin{array}{l} S_{\mathcal{H}_1}(m_j)^c = S_{\mathcal{H}_1}(m_i)^c \\ S_{\mathcal{H}_2}(m_j)^c = S_{\mathcal{H}_2}(m_i)^c \\ S_{\mathcal{H}_1}(m_i) \oplus S_{\mathcal{H}_2}(m_i) \stackrel{r}{=} S_{\mathcal{H}_1}(m_j) \oplus S_{\mathcal{H}_2}(m_j) \end{array} \right. \qquad (8) $$

**Second Step:** Use an additional message block $m$ to correct the remaining differences between $S_{\mathcal{H}}(m_i)$ and $S_{\mathcal{H}}(m_j)$. We see that if we choose $m$ as $S_{\mathcal{H}_1}(m_i) \oplus^r S_{\mathcal{H}_1}(m_j)$, which is equal to $S_{\mathcal{H}_2}(m_i) \oplus^r S_{\mathcal{H}_2}(m_j)$ from (8), then we have the following equalities :

$$ \left\{ \begin{array}{l} S_{\mathcal{H}_1}(m_i) = S_{\mathcal{H}_1}(m_j) \oplus (m \parallel 0^c) \\ S_{\mathcal{H}_2}(m_i) = S_{\mathcal{H}_2}(m_j) \oplus (m \parallel 0^c) \end{array} \right. \qquad (9) $$

or equivalently:

$$ \left\{ \begin{array}{l} S_{\mathcal{H}_1}^*(m_i \parallel 0^r) = S_{\mathcal{H}_1}^*(m_j \parallel m) \\ S_{\mathcal{H}_2}^*(m_i \parallel 0^r) = S_{\mathcal{H}_2}^*(m_j \parallel m) \end{array} \right. \qquad (10) $$

This corresponds to a full-state collision on $\mathcal{H}$. Consequently, we have

$$ \mathcal{H}(m_i \parallel 0^r) = \mathcal{H}(m_j \parallel m). $$

**Complexity Analysis:** The condition formulated in equation (8) in the first step relies on $2c + r$ bits. By a direct application of the birthday paradox, the probability of finding a pair of messages that satisfies this equation becomes non-negligible when $q \approx 2^{c+r/2}$.

The second step does not require any query; hence, the overall cost of the attack is of order $\tilde{O}(2^{c+r/2})$. Note that this attack depends only on the size of the state. More specifically, it also applies if the two sponge states are mixed between iterations, as in the double sponge. Consequently, this attack translates directly to the double sponge and corresponds to the best-known generic attack against the construction, with the same complexity.
## 3.2 Attack Based on Multicollisions

We now present a more efficient attack based on multicollisions, a technique first proposed by Antoine Joux in [Jou04]. This method consists of building a large set of different messages that all lead to the same state in $H_1$.

Using the birthday paradox, we then observe that if the number of these messages is sufficiently large, a pair of them might also collide in $H_2$, thereby producing a complete collision on $H$.

First, we describe how to use this technique to build a $2^t$-multicollision on a single sponge construction in time $O(t \cdot 2^{c/2})$. We then extend the same technique to the XOR of two sponges.

Start from the IV and absorb $q$ distinct messages. If $q^2 \approx 2^c$, there is a non-negligible probability to find two messages, $m_1$ and $m'_1$, such that $S_{H_1}(m_1)$ and $S_{H_1}(m'_1)$ are equal on their capacity. A message is then absorbed by both states to correct differences between their respective rates. For instance, we can take the rate of $S_{H_1}(m_1)$, denoted $r_1$, as a message to be absorbed on $S_{H_1}(m'_1)$, and the rate of $S_{H_1}(m'_1)$, denoted $r'_1$, as a message to be absorbed by $S_{H_1}(m_1)$. Right after absorption of these messages, both states have $r_1 \oplus r'_1$ as their rate. Since they were also chosen to have the same capacity, which remains unchanged during absorption, the two states are now equal.

Take the state obtained at the end of the previous procedure and store the two associated messages $m_1 \parallel r'_1$ and $m'_1 \parallel r_1$. Absorb again $2^{c/2}$ distinct messages to find, with non-negligible probability, two messages $m_2$ and $m'_2$ such that $S_{H_1}(m_2)$ and $S_{H_1}(m'_2)$ collide on their capacity. Differences in the rate must once again be corrected with an extra message block, respectively $r'_2$ for $S_{H_1}(m_2)$ and $r_2$ for $S_{H_1}(m'_2)$, leading again to a full-state collision. We have that:

$$ \mathcal{H}(m_1 \parallel r'_1 \parallel m_2 \parallel r'_2) = \mathcal{H}(m'_1 \parallel r_1 \parallel m'_2 \parallel r_2) \quad (11) $$

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:

$$ \mathcal{H}(m_1 \parallel r'_1 \parallel m_2 \parallel r'_2) = \mathcal{H}(m_1 \parallel r'_1 \parallel m'_2 \parallel r_2) = \mathcal{H}(m'_1 \parallel r_1 \parallel m'_2 \parallel r_2) = \mathcal{H}(m'_1 \parallel r_1 \parallel m_2 \parallel r'_2) \quad (12) $$

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

This behavior was used in [Jou04] to build collisions on the concatenation and the XOR of two Merkle-Damgård constructions, using $\mathcal{O}(2^{n/2})$ compression function calls, which matches 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.

<figure><img src="image_6.png" /><figcaption>Figure 4: Multicollision against the sponge construction</figcaption></figure>

**First Step:** Build a $2^t$-multicollision and denote the set of messages as $M$.
**Second Step:** Evaluate $\mathcal{H}_2$ on these $2^t$ colliding messages. When $t \ge b/2$, there is a non-negligible probability of finding a collision, i.e., two elements $m_i, m_j \in \mathcal{M}$ such that

$$S_{\mathcal{H}_2}(m_j) = S_{\mathcal{H}_2}(m_i).$$

Since $m_i$ and $m_j$ are constructed to already collide on $\mathcal{H}_1$, we obtain in the end a collision on $\mathcal{H}$.

**Complexity Analysis:** Fix $t = b/2$. From the first step, we obtain $2^{b/2}$ colliding messages after $b/2$ consecutive collisions, each requiring $2^{c/2}$ permutation queries. Hence, the first step requires

$$O(b \cdot 2^{c/2})$$

queries to $P_1$.

The second step requires evaluating these messages on $\mathcal{H}_2$. To estimate the number of permutation queries, we must determine the size of each colliding message block $m_i/m_i'$. We distinguish two cases:

* If $r \ge c/2$, then from any state we can find a collision using only one message block and use one extra block to correct differences in the rate. Consequently, the final messages have size $2b$ blocks.

* If $r < c/2$, one message block is insufficient to find an inner $c$-part collision. We require $c/(2r)$ message blocks to achieve a collision, plus one block to correct the rate. Therefore, the messages have size

$$\frac{cb}{4r} + \frac{b}{2} \text{ blocks.}$$

In both situations, we exploit the fact that the final messages form a complete binary tree structure to save permutation queries during evaluation. The resulting overall complexity depends on the relation between $c$ and $r$:

* If $r \ge c$, finding a collision costs

$$O(b \cdot 2^{c/2} + 2^{b/2}) \text{ operations.}$$

* If $r < c$, the cost becomes

$$O(b \cdot 2^{c/2} + \frac{c}{r} \cdot 2^{b/2}) \text{ operations.}$$

Unlike the Merkle-Damgård case, multicollisions do not enable collisions against the XOR of two sponges as efficiently as they do for a single sponge, where building a collision requires $\tilde{O}(2^{c/2})$ operations. 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 rate (the remaining part of the state) changes after each iteration by XORing message blocks. In contrast, for the XOR of two sponges, the same message block is XORed into both rates, which reduces the attacker's control over these parts of the states.

# 4 Tight Indifferentiability of the XOR Combiner

The best known collision attack on the XOR of two sponges has a higher complexity than for a single sponge. Nevertheless, we show that the indifferentiability bound of the XOR of two sponges is still $\tilde{\Theta}(2^{c/2})$, matching that of a single sponge.

To establish this result, we proceed in three steps within the indifferentiability framework:

1. First, we show that the XOR of two sponges is at least as secure as a single sponge.
2. Next, we introduce an attack using four distinct messages.

3. Finally, we demonstrate that this phenomenon corresponds to an instance of the multiple 4-sum problem, which can be used to differentiate the construction from a random oracle.

Since the cost of this attack matches that of distinguishing a single sponge from a random oracle, we obtain a tight indifferentiability result for the XOR of two sponges.

## 4.1 Indifferentiability Lower Bound

**Lemme 4.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 $\mathcal{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 $\mathcal{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 $\mathcal{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 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 (13) $$
**Algorithm 5** Simulator S for the indifferentiability game of A

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

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

1: **if** first call to 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 $S'$ on input $x$ with oracle access to $\mathcal{RO} \oplus \mathcal{H}_2^P$

6: Return $(S'(x), P(y))$

▷ Gives $S'(x)$

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 $S'$ that achieves the following upper bound

$$ \mathrm{Adv}_{\mathrm{indif}}^{\mathcal{H}_{1}^{P}, S', \mathcal{RO}}(\mathcal{A}') \leq \frac{q^2}{2^c} \qquad (14) $$

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

## 4.2 Building 4-sums on the Xor Combiner

To prove an upper bound on the indifferentiability of the XOR of two sponges, we build a solution to a specific instance of the generalized 4-sum problem and then study the set of parameters for which it can be used to distinguish the XOR of two sponges from a random oracle.

The overall 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}$.

**First Step:** Build $2^t$ multicollision $\mathcal{M}_{MC} = \{m_1, ..., m_{2^t}\}$ on $\mathcal{H}_1$. We have that for all $m_i, m_j \in \mathcal{M}_{MC}$, 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 :

$$ \left\{ \begin{array}{l} 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{array} \right. \qquad (15) $$

This system implies a 4-sum in $\mathcal{H}_1$. By choosing $s_1$ and $s_2$ carefully we will be able to build a 4-sum in $\mathcal{H}_2$ as well.

**Second Step:** Let's 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)$. If $\mathcal{M}_{MC}$ is large enough, we can expect to find $i \neq j$ such that $S_{\mathcal{H}_2}(m_i)^c = S_{\mathcal{H}_2}(m_j)^c$. In fact, if the size of $\mathcal{M}_{MC}$ is of order $2^{c/2}$ we expect to find such collision with non negligible probability. We can now use $s_1$ and $s_2$ to correct differences between the rate of $S_{\mathcal{H}_2}(m_i)$ and the rate of $S_{\mathcal{H}_2}(m_j)$. That translates to the following system:

$$ \left\{ \begin{array}{l} 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_i) \oplus (s_2 \parallel 0^c) = S_{\mathcal{H}_2}(m_j) \oplus (s_1 \parallel 0^c) \end{array} \right. \qquad (16) $$

which is equivalent to

$$ \left\{ \begin{array}{l} S_{\mathcal{H}_2}(m_i \parallel s_1) = S_{\mathcal{H}_2}(m_j \parallel s_2) \\ S_{\mathcal{H}_2}(m_i \parallel s_2) = S_{\mathcal{H}_2}(m_j \parallel s_1) \end{array} \right. \qquad (17) $$

Note that the two equations in (16) are exactly equivalent. The system admits $2^r$ solutions $(s_1, s_2)$, for example, $s_1 = 0, s_2 = S_{\mathcal{H}_2}(m_i) \oplus S_{\mathcal{H}_2}(m_j)$. The four messages $m_i \parallel s_1, m_i \parallel s_2, m_j \parallel s_1$, and $m_j \parallel s_2$ now
4-collide in $\mathcal{H}_1$ and also in $\mathcal{H}_2$, as described respectively in (15) and (17). Consequently, they also lead to a 4-sum in $\mathcal{H}$ defined as $\mathcal{H}_1 \oplus \mathcal{H}_2$.

**Complexity analysis:** Step 2 requires $O(c2^{c/2})$ operations to find a suitable pair of messages in $\mathcal{M}_{MC}$, for example through sorting and a dichotomic search over the set. This step does not require any permutation queries. In Step 1, we need to build a $2^{c/2}$ multicollision to construct the set $\mathcal{M}_{MC}$ with sufficient size. This is done using $O(c2^{c/2})$ permutation calls, employing Joux's multicollision technique described previously. The overall cost of building a 4-sum on the XOR of two sponge constructions is $O(c2^{c/2})$.

## 4.3 This 4-sum is a solution of a multiple 4-sum problem

We show how to translate the quadruple obtained previously, now written $(x, y, w, z)$, into a solution of a specific instance of the multiple 4-sum problem. The fact that $(x, y, w, z)$ leads to a collision on $\mathcal{H}$ is ensured by the following structure, which essentially summarizes systems (15) and (16) into one:

$$ \left\{ \begin{array}{ll} S_{\mathcal{H}_1}(x) = S_{\mathcal{H}_1}(y) & S_{\mathcal{H}_1}(w) = S_{\mathcal{H}_1}(z) \\ S_{\mathcal{H}_2}(x) = S_{\mathcal{H}_2}(z) & S_{\mathcal{H}_2}(w) = S_{\mathcal{H}_2}(y) \end{array} \right. \qquad (18) $$

First note an important property: when to messages $m, m'$ lead to a state collision over a sponge construction, which is written here as $S_{\mathcal{H}_1}(m) = S_{\mathcal{H}_1}(m')$ for example, then adding the same suffix $\sigma \in \{0, 1\}^*$ 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 consequence, given the that the previous system holds, we have that for any integer $i$:

$$ \left\{ \begin{array}{ll} S_{\mathcal{H}_1}(x \parallel i) = S_{\mathcal{H}_1}(y \parallel i) & S_{\mathcal{H}_1}(w \parallel i) = S_{\mathcal{H}_1}(z \parallel i) \\ S_{\mathcal{H}_2}(x \parallel i) = S_{\mathcal{H}_2}(z \parallel i) & S_{\mathcal{H}_2}(w \parallel i) = S_{\mathcal{H}_2}(y \parallel i) \end{array} \right. \qquad (19) $$

which implies:

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

This relation holds for any integer $i$ and for the entire output of $\mathcal{H}$. Hence, $\alpha$ and $\beta$ can be chosen freely from $\mathbb{N}$. However, we suppose that the output size of $\mathcal{H}$ is fixed in advance, which implies that $\beta$ is also fixed.

From this expression, we also define our family of functions $\{\varphi_i\}_{i \in \mathbb{N}}$ as:

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

Recall that the probability for an adversary allowed to perform $q$ queries to find at least one solution to an instance of the multiple 4-sum problem can be upper bounded by $\frac{(\alpha q)^{42-\frac{\alpha \beta}{12}}}{24}$. Therefore, when

$$ \log(q) \ll \frac{\alpha \beta}{48} - \log(\alpha) + \frac{\log(24)}{4}, \qquad (20) $$

we obtain a distinguisher with high probability. On one hand, the number of queries allowed to the adversary, $q$, is of order $O(c2^{c/2})$, which is the cost of the attack in Sect. 4.2. On the other hand, as mentioned before, $\alpha$ and $\beta$ are integers chosen at will; consequently, we can always pick $\alpha$ and $\beta$ such that (20) is satisfied.

# 5 Analysis of the Double Sponge Construction

The double sponge construction described in Section 2.3 is a design proposed by B. Mennink and C. Lefèvre [LM24], achieving beyond-birthday-bound security for certain values of rate and capacity. It has been proven indifferentiable from a random oracle up to $2^{2c/3}$ permutation queries. However, this bound is
not known to be tight, as the best known attacks require either $2^{c+r/2}$ queries for the best generic attack, or $2^{2c/3+r/3}$ queries for a simulator-specific attack. The structure of the indifferentiability proof even led the authors to conjecture that the real bound may be higher than the one obtained through the proof. In this section, we use our 4-sum technique to build distinguishers that improve upon the current best attacks.

## 5.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.

From now on, let $\mathcal{H}$ be a double sponge construction. Recall that 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 aim to build a set of four messages $\{m_1, m_2, m_3, m_4\} \subset \{0, 1\}^*$ such that:

$$ \mathcal{H}(m_1) \oplus \mathcal{H}(m_2) \oplus \mathcal{H}(m_3) \oplus \mathcal{H}(m_4) \stackrel{r}{=} 0 \quad (21) $$

Note that in this case, we require that the four outputs sum to zero only on their first $r$ bits. This is a weaker property than in the previous section, and it will require extra care in the section dedicated to the construction of the distinguisher.

Let $m, m'$ be two messages, the state of $\mathcal{H}$ after absorption of $m$ and $m'$ can be written:

$$ S_{\mathcal{H}}(m) := (A, B) \quad S_{\mathcal{H}}(m') := (C, D) \quad (22) $$

Let $x, y, z$ and $w$ be 4 message blocks. We write the internal state of the double sponge after XORing the 4 messages from the state previously defined:

$$ \left\{ \begin{array}{ll} S_{\mathcal{H}}^*(m \parallel x) = ((x \parallel 0^c) \oplus A, (x \parallel 0^c) \oplus B) & S_{\mathcal{H}}^*(m' \parallel y) = ((y \parallel 0^c) \oplus C, (y \parallel 0^c) \oplus D) \\ S_{\mathcal{H}}^*(m' \parallel w) = ((w \parallel 0^c) \oplus C, (w \parallel 0^c) \oplus D) & S_{\mathcal{H}}^*(m \parallel z) = ((z \parallel 0^c) \oplus A, (z \parallel 0^c) \oplus B) \end{array} \right. \quad (23) $$

The goal is to choose $x, y, z$ and $w$ so that the four states above follow a specific structure that translates into equalities over the first and second half of the states:

$$ \left\{ \begin{array}{ll} (x \parallel 0^c) \oplus A = (w \parallel 0^c) \oplus C & (z \parallel 0^c) \oplus A = (y \parallel 0^c) \oplus C \\ (x \parallel 0^c) \oplus B = (y \parallel 0^c) \oplus D & (z \parallel 0^c) \oplus B = (w \parallel 0^c) \oplus D \end{array} \right. \quad (24) $$

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} A^c \oplus C^c = 0 \\ B^c \oplus D^c = 0 \end{array} \right. \quad (25) $$

Assuming that (25) holds — a point that will be examined at the end of this section — the system in (24) is equivalent to the following one applying this time to $r$-bits,

$$ \left\{ \begin{array}{ll} x \oplus w = A \oplus C & z \oplus y = A \oplus C \\ x \oplus y = B \oplus D & w \oplus z = B \oplus D \end{array} \right. \quad (26) $$

Since this system is of rank 3 over $\mathbb{F}_{2^r}$, the total number of solutions is $2^r$. Therefore, as soon as the equations in (25) are verified, it becomes possible to build $2^r$ distinct 4-sums on the double-sponge construction. Indeed, we can fix, for any $i \in \{0, \dots, r-1\}$, the tuple $(x_i, y_i, w_i, z_i)$ as:

$$ \left\{ \begin{array}{ll} x_i = A \oplus B \oplus i & y_i = D \oplus A \oplus i \\ w_i = C \oplus B \oplus i & z_i = C \oplus D \oplus i \end{array} \right. \quad (27) $$
And we have that :

$$ \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) \stackrel{r}{=} 0 \quad (28) $$

It is then necessary to study how to construct two messages, m and m', such that Condition 1 is satisfied.

## 5.2 Complexity Analysis

This section presents an analysis of the structure of the system described in equation (25).

### 5.2.1 Generic Case

At first glance, this system expresses two constraints that fix random values over c bits to zero. Following the design rationale of the double sponge in [LM24], the MIX operator can be any 2 × 2 MDS matrix such that the two coefficients in each row are not equal. In this case, after the absorption of q different message blocks, there is a probability of $\frac{q^2}{2^{2c}}$ to find two messages m and m' that satisfy equation (25). Hence, we can build a 4-collision with constant probability after 2^c permutation calls. However, this probability can be increased for a specific range of parameters and choice of MIX operator.

### 5.2.2 Improvement for a Convenient MIX Operator and a Large Rate

We now focus on a specific case where the MIX operator is defined as in the Double Sponge proposal [LM24]:

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

This is particularly interesting here, since if two elements x and y ∈ $\mathbb{F}_{2^b}$, represented as polynomials of degree b − 1 over $\mathbb{F}_2$, are equal on their c lowest-degree coefficients and on their highest-degree coefficient, then 2x and 2y are also equal on their c lowest-degree coefficients.

In order to use this property, we first we define pre-states for A,B,C and D as a pair of double Sponge states $(X_1, X_2)$ and $(Y_1, Y_2)$ such that $MIX(X_1, Y_1) = (A, B)$ and $MIX(X_2, Y_2) = (C, D)$. That is :

$$ \left\{ \begin{array}{l} (A, B) = (X_1 \oplus 2Y_1, 2X_1 \oplus Y_1) \\ (C, D) = (X_2 \oplus 2Y_2, 2X_2 \oplus Y_2) \end{array} \right. \qquad (29) $$

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

$$ \left\{ \begin{array}{l} X_1^c \oplus X_2^c = (2Y_1)^c \oplus (2Y_2)^c \\ Y_1^c \oplus Y_2^c = (2X_1)^c \oplus (2X_2)^c \end{array} \right. \qquad (30) $$

Note that when inner states $X_1, Y_1$ are equal on their c least significant bits and on their most significant bit (the b-1th bit), then $2X_1, 2Y_1$ are also equal on their c least significant bits. As a consequence, the following condition sufficient to ensure equation (25).

$$ \left\{ \begin{array}{l} X_1^c = X_2^c \qquad Y_1^c = Y_2^c \\ X_1 \stackrel{\text{MSB}}{=} X_2 \qquad Y_1 \stackrel{\text{MSB}}{=} Y_2 \end{array} \right. \qquad (31) $$

Naively, after q messages, equation (31) has a probability of $\frac{q^2}{4 \cdot 2^{2c}}$ to be satisfied. This cost can be reduced if $r \ge \frac{3c}{4}$. The idea of the algorithm is to construct many pairs of messages whose absorptions lead to a collision in the capacity of one of the half-states of the Double Sponge. This corresponds to the first three steps in the following description. Then, if a sufficient number of such pairs are available, we expect to find one that also leads to a collision in the capacity of the other half-state of the Double Sponge.
1. **Forward Step:** Start from $(IV_1, IV_2)$ and build a list of $2^{3c/4}$ messages, written $m_0^i$ and indexed from 0 to $2^{3c/4} - 1$. For each element of the list, compute the 2b-bit inner state after absorption of $m_0^i$, written $S_H(m_0^i)$. The first half of each of these states is stored in a set $M_{forward}$ of size $2^{3c/4}$.

2. **Backward Step:** Fix the $c$ least significant bits of the first half-state at 0. Build $2^{3c/4}$ possible values for the $r$ most significant bits of this half-state. For all these state values, now written $X_i$, $0 \le i < 2^{3c/4} - 1$, compute $P_1^{-1}(X_i)$. We store these preimages in a set of half-state candidates $M_{backward}$ of size $2^{3c/4}$.

3. **Meeting Step:** An element of $M_{forward} \times M_{backward}$ is a pair of two $b$-bit states, and there is a probability of $2^{-c}$ that the two members of the pair collide on their capacity, which we call a match. Since $M_{forward} \times M_{backward}$ is of size $2^{3c/2}$, we end up with $2^{c/2}$ matches. Note that from each match, written $(Fo, Ba)$, we can deduce a message of two blocks $m_0^i \parallel m_1^i$, where we define $S_H^*(m_0^i \parallel m_1^i) := (F_i, S_i)$ such that $P_1(F_i)^c = 0$. Indeed, we take $i$ as the index of $Fo$ in $M_{forward}$; hence $Fo$ is of the form $S_H(m_0^i)$. Then $m_1^i$ is defined as the first $r$ bits of $Fo \oplus Ba$, and consequently $S_i = Ba$. By construction of $M_{backward}$, $P_1(Ba)^c = 0$.

4. **Collision Step:** The previous step allowed us to build a set of $2^{c/2}$ messages whose absorption by $H$ from $(IV_1, IV_2)$ leads to a set of states $\{(F_i, S_i) | 0 \le i \le 2^{c/2} - 1\}$ such that the last $c$ bits of $P_1(F_i)$ are always set to 0. We wish to find $i, j \in \{0, 1, \dots, 2^{c/2} - 1\}$ such that:

$$ \left\{ \begin{array}{l} P_2(S_i)^c = P_2(S_j)^c \\ P_1(F_i) \stackrel{\text{MSB}}{=} P_1(F_j) \qquad P_2(S_i) \stackrel{\text{MSB}}{=} P_2(F_j) \end{array} \right. \qquad (32) $$

From the birthday paradox, we expect to find suitable indexes for the first equalities with non negligible probability. The two other equalities are satisfied with probability $1/4$ independently from the first one. Hence we find a pair of states that verify (31) with non negligible probability.

**Complexity Analysis:** Step 1 and 2 requires $O(2^{3c/4})$ queries, Step 3 and 4 do not require anyone. Note that when one records also basic operations the cost remains of similar order. In consequence the procedure depicted above allows to find 4 state satisfying equation (31) with non negligible probability after $\tilde{O}(2^{3c/4})$ operations. Note that a definition fo this procedure as an algorithm as well as is description in a sketch are available as part B of the Appendix. We also provide an illustration of the procedure and the notation used in Figure 5.

<figure><img src="image_7.png" /><figcaption>Figure 5: Meet in the middle prior to a 4-sum</figcaption></figure>

In the case where $r \ge \frac{3c}{4}$, it is consequently possible to build a 4-sum on the double sponge construction with non-negligible probability after $\tilde{O}(2^{3c/4})$ operations, leveraging the behavior of multiplication by 2 over $\mathbb{F}_{2^b}$. Note that the coefficients of the MIX operator can be changed without affecting the construction's indifferiability bound; however, they can impact the efficiency of potential implementations.
### 5.2.3 Improvement for a convenient MIX operator and a small rate

When the rate is small relative to the capacity, specifically when $r \le \frac{3c}{4}$, it is still possible to find four states that verify (31) while using fewer queries than the initial bound of order $O(2^c)$. We follow the same procedure with several adjustments:

1. **Forward Step:** this step remains the same as before. We process $2^t$ random messages from IV. The parameter $t$ will be set later in order to minimize the overall complexity.

2. **Backward Step:** instead of fixing the capacity of the first state at 0, we introduce some freedom in its value. Split $c$ into two parts, $c = c_1 + c_2$, where $c_1$ is set to 0 and no constraints are imposed on $c_2$. Hence we are able to compute $2^{r+c_2}$ different preimages.

3. **Meeting Step:** we are able to form $2^{t+r+c_2-c}$ matches, that is, pairs of states obtained from the forward and backward steps that collide on their first half's capacity. Among those pairs, we wish to find two that lead to a collision in both their top and bottom capacity. By construction, the last $c_1$ bits of the top capacity will always be set to 0. Hence this corresponds to the probability of having two states that collide on $c+c_2$ bits among a set of size $2^{t+r+c_2-c}$. Using the birthday paradox, for this to happen with constant probability, we need to have: $t+r+c_2-c = \frac{c+c_1}{2}$.

**Optimizing the parameters:** the cost of the procedure is $max(2^{r+c_2}, 2^{t+r+c_2-c})$, with the constraint that $t+r+c_2-c = \frac{c+c_1}{2}$. The two adjustable variables are $t$ and $c_2$, and the constraint can be rewritten as $t + \frac{c_2}{2} = \frac{3c}{2} - r$. The optimal complexity is obtained when $t = r + c_2$. The minimum cost is reached when $t = c - \frac{r}{3}$, which corresponds to a cost of order $O(2^{c-r/3})$. Note that this procedure is also described as an algorithm in Part B of the appendix.

## 5.3 The Link between this 4-sum and the multiple 4-sum problem

As in the case of the XOR of two sponges, we will translate the special kind of 4-sum described in the previous section into a solution of an instance of the generalized 4-sum problem. We will work using the cost of the generic attack that does not rely on assumption on the mix operator. Using $O(2^c)$ queries, we can build a quadruple of messages $(x, y, w, z)$ such that for any integer $i$ from 0 to $2^r - 1$:

$$ \mathcal{H}(x \oplus (0 \parallel i)) \oplus \mathcal{H}(y \oplus (0 \parallel i)) \oplus \mathcal{H}(w \oplus (0 \parallel i)) \oplus \mathcal{H}(z \oplus (0 \parallel i)) \stackrel{r}{=} 0 \quad (33) $$

Looking at equation (33) the intuition is that $\phi_i$ takes as input a bit string and return as output the same string with its $r$ leftmost bits xored with $i$.

$$ \forall i \in \{0, 1, \dots, 2^{r-1}\}, \quad \phi_i : \{x \in \{0, 1\}^* \mid |x| \ge r\} \to \{0, 1\}^*, \quad x \mapsto x \oplus (0^{|x|-r} \parallel i) $$

Recall that the probability for an adversary allowed to perform $q$ queries to find at least a solution to an instance of the multiple 4-sum problem can be upperbounded by $\frac{(\alpha q)^4 2^{-\frac{\alpha \beta}{12}}}{24}$. From equation (33) we can set $\alpha$ at $2^r$ and $\beta$ at $r$. Since $q$ corresponds to the cost of building of 4-sum, $q$ is of order $O(2^c)$.

In consequence the previous bound can be written $\frac{2^{4c-r(\frac{2^r}{12}-4)}}{24}$. Hence we have a distinguisher with high probability when

$$ c \ll \frac{r(\frac{2^r}{12} - 4) + \log(24)}{4}. \quad (34) $$

The right-hand side of this expression grows exponentially with $r$. Hence the distinguisher works for all range of parameter used in practice for the double sponge. For instance if $r = 10$, $c$ must at least be around $2 \times 10^2$ bits for the distinguisher to fail. This goes up to $10^3$ when $r = 12$ and $2 \times 10^4$ if $r = 15$.
# 6 Conclusion

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. We also described a simulator achieving indifferentiability from a random oracle for the XOR combiner up to $2^{c/2}$ permutation and primitive queries. Thus, ignoring polynomial factors, we establish a tight security bound for the XOR of two sponges, which matches that of a single sponge. This shows that XORing two sponges does not improve security over using a single sponge alone.

Then, we described a similar 4-sum technique to reduce the indifferentiability upper bound of the double sponge construction from $O(2^{c+r/2})$ down to $O(2^c)$ permutation queries, and even further to $\tilde{O}(\max(2^{3c/4}, 2^{c-r/3}))$ when using the specific MIX operator proposed in [LM24]. This represents a step closer to closing the security gap of this construction.

To illustrate the improvement of our attacks, we show the evolution of the cost of attacks described in [LM24] alongside our attacks in Figure 5, for increasing values of $c$ and a fixed value of $b$. We observe that in the generic case—that is, without exploiting weaknesses induced by the structure of the MIX operator—the 4-sum attack remains faster than the best known generic attack to date.

<figure><img src="image_8.png" /><figcaption>Figure 6: Indifferentiability of the Double Sponge</figcaption></figure>

It also outperforms the attack against the simulator for specific ranges of parameters, particularly when the capacity is smaller than the rate. As mentioned before, further improvements are possible for specific values of the MIX operator, allowing the overall cost of a 4-collision to be reduced.

Many questions remain open; the security gap of the double sponge, although reduced, remains untight. Furthermore, it seems natural to try to improve the best collision and preimage attacks on the Double Sponge.
References

[AMP11] Elena Andreeva, Bart Mennink, and Bart Preneel. Security reductions of the second round SHA-3 candidates. In Mike Burmester, Gene Tsudik, Spyros S. Magliveras, and Ivana Ilic, editors, *ISC 2010*, volume 6531 of LNCS, pages 39–53. Springer, Berlin, Heidelberg, October 2011. doi:10.1007/978-3-642-18178-8_5.

[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 indiffer-entiability 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.

[BHBLS24] Xavier Bonnetain, Rachelle Heim Boissier, Gaëtan Leurent, and André Schrottenloher. Improving generic attacks using exceptional functions. In Leonid Reyzin and Douglas Stebila, editors, *Advances in Cryptology - CRYPTO 2024*, pages 105–138, Cham, 2024. Springer Nature Switzerland.

[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.

[Din16] Itai Dinur. New attacks on the concatenation and XOR hash combiners. In *Advances in Cryptology - EUROCRYPT 2016*, volume 9665 of *Lecture Notes in Computer Science*, pages 484–508. Springer, 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.

[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. Symmetric Cryptol.*, 2024(1):71–113, 2024. URL: https://doi.org/10.4658/tosc.v2024.i1.71-113, doi:10.4658/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.

[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.

[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 Notations

<table><thead><tr><td>Notation</td><td>Description</td></tr></thead><tbody><tr><td>$\mathcal{H}_1, \mathcal{H}_2$</td><td>underlying sponge construction in a hash combiner.</td></tr><tr><td>$P_1, P_2$</td><td>the internal permutation used in the sponge construction $\mathcal{H}_1$ and $\mathcal{H}_2$.</td></tr><tr><td>$IV_1, IV_2$</td><td>initialization vectors for $\mathcal{H}_1$ and $\mathcal{H}_2$ respectively.</td></tr><tr><td>$A, B$</td><td>internal state of a sponge construction.</td></tr><tr><td>$S_{\mathcal{H}}(m)$</td><td>internal state of $\mathcal{H}$ after absorption of message $m$.</td></tr><tr><td>$S_{\mathcal{H}}^*(m)$</td><td>internal state after partial absorption of message $m$, stopped before applying the last permutation and mix iteration.</td></tr><tr><td>$r$</td><td>the rate, number of bits xored/outputed per sponge iteration.</td></tr><tr><td>$c$</td><td>the capacity i.e. the hidden bits in the sponge state.</td></tr><tr><td>$X^c$</td><td>internal states capacity bits for $\mathcal{H}_1$ and $\mathcal{H}_2$ respectively.</td></tr><tr><td>$\mathcal{H}$</td><td>overall some hash function.</td></tr><tr><td>$m$</td><td>message.</td></tr><tr><td>$\mathcal{M}$</td><td>set of messages</td></tr><tr><td>$\mathcal{A}$</td><td>the adversary in the indifferentiability game.</td></tr><tr><td>$\mathcal{R}\mathcal{O}$</td><td>random oracle in the distinguishing game of indifferentiability</td></tr><tr><td>$\mathcal{S}$</td><td>simulator in the distinguishing game of indifferentiability</td></tr><tr><td>$\oplus_r$</td><td>xor over the rate of two sponge states</td></tr><tr><td>$\underline{\underline{\beta}}$</td><td>equality over the $\beta$ leftmost bits two binary words</td></tr><tr><td>$\mathbb{F}_{2^b}$</td><td>finite field of size $2^b$</td></tr></tbody></table>

## B Algorithm of the meet in the middle procedure on the Double Sponge
<caption>**Algorithm 6** Double Sponge Capacity Meet-in-the-Middle Procedure</caption>

1: **Input:** $c, r$ such that $r \ge 3c/4$, permutations $P_1, P_2$, initial states $(IV_1, IV_2)$
2: **Output:** $(X_i, Y_i), (X_j, Y_j)$ such that $P_1(X_i) \oplus P_1(X_j) = 0$ and $P_2(Y_i) \oplus P_2(Y_j) = 0$
3: $\mathcal{M}_{\text{forward}} \leftarrow []$
4: $\mathcal{M}_{\text{backward}} \leftarrow []$
5: $\mathcal{M}_{\text{match}} \leftarrow []$
6: $\triangleright \text{Forward Step}$
7: **for** $i = 0$ to $2^{3c/4} - 1$ **do**
8: &nbsp;&nbsp;&nbsp;&nbsp; $m_0^i \leftarrow \$ \mathbb{F}_2^r$
9: &nbsp;&nbsp;&nbsp;&nbsp; $(X_i, Y_i) \leftarrow \text{Absorb}_{\mathcal{H}}(m_0^i, IV_1, IV_2)$
10: &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{M}_{\text{forward}} \leftarrow \text{append}(\mathcal{M}_{\text{forward}}, X_i)$
11: **end for**
12: $\triangleright \text{Backward Step}$
13: **for** $j = 0$ to $2^{3c/4} - 1$ **do**
14: &nbsp;&nbsp;&nbsp;&nbsp; $Z_j \leftarrow \$ \mathbb{F}_2^r$
15: &nbsp;&nbsp;&nbsp;&nbsp; $A_j \leftarrow P_1^{-1}(Z_j \parallel 0^c)$
16: &nbsp;&nbsp;&nbsp;&nbsp; $\mathcal{M}_{\text{backward}} \leftarrow \text{append}(\mathcal{M}_{\text{backward}}, A_j)$
17: **end for**
18: $\triangleright \text{Meeting}$
19: **for** $i = 0$ to $2^{3c/4} - 1$ **do**
20: &nbsp;&nbsp;&nbsp;&nbsp; **for** $j = 0$ to $2^{3c/4} - 1$ **do**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $X_i \equiv A_j \pmod{2^c}$ **then**
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $m_1^i \leftarrow (X_i \oplus A_j)^r$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Store $(X_i, A_j, m_0^i \parallel m_1^i)$ in $\mathcal{M}_{\text{match}}$
24: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end if**
25: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end for**
26: **end for**
27: $\triangleright \text{Meeting Step}$
28: **for** $i = 0$ to $2^{c/2} - 1$ **do**
29: &nbsp;&nbsp;&nbsp;&nbsp; $(X_i, Y_i) \leftarrow \mathcal{M}_{\text{match}}[i]$
30: &nbsp;&nbsp;&nbsp;&nbsp; **for** $j = i + 1$ to $2^{c/2} - 1$ **do**
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $(X_j, Y_j) \leftarrow \mathcal{M}_{\text{match}}[j]$
32: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $P_1(X_i)^c \oplus P_1(X_j)^c = 0$ and $P_2(Y_i)^c \oplus P_2(Y_j)^c = 0$ **then**
33: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **return** $(X_i, Y_i), (X_j, Y_j)$
34: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end if**
35: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **end for**
36: **end for**
<caption>**Algorithm 7 Optimized Double Sponge Meet-in-the-Middle**</caption>

1: **Input:** $c, r, P_1, P_2, (IV_1, IV_2)$
2: **Output:** $(X_i, Y_i), (X_j, Y_j)$ s.t. $P_1(X_i) \oplus P_1(X_j) \equiv 0 \pmod{2^c}$ and $P_2(Y_i) \oplus P_2(Y_j) \equiv 0 \pmod{2^c}$
3: $c_2 \leftarrow c - \frac{4}{3}r, c_1 \leftarrow c - c_2, t \leftarrow c - \frac{r}{3}$
4: $\mathcal{M}_{\text{forward}} \leftarrow []$, $\mathcal{M}_{\text{backward}} \leftarrow []$, $\mathcal{M}_{\text{match}} \leftarrow []$
5: $\triangleright$ **Forward Step**
6: **for** $i = 0$ to $2^t - 1$ **do**
7: &nbsp;&nbsp;&nbsp;&nbsp;$m_0^i \leftarrow \$ \mathbb{F}_2^r$
8: &nbsp;&nbsp;&nbsp;&nbsp;$(X_i, Y_i) \leftarrow \text{Absorb}_{\mathcal{H}}(m_0^i, IV_1, IV_2)$
9: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{M}_{\text{forward}} \leftarrow \text{append}(\mathcal{M}_{\text{forward}}, X_i)$
10: **end for**
11: $\triangleright$ **Backward Step**
12: **for** $j = 0$ to $2^{r+c_2} - 1$ **do**
13: &nbsp;&nbsp;&nbsp;&nbsp;$Z_j \leftarrow \$ \mathbb{F}_2^r$
14: &nbsp;&nbsp;&nbsp;&nbsp;$A_j \leftarrow P_1^{-1}(Z_j \parallel 0^{c_1})$
15: &nbsp;&nbsp;&nbsp;&nbsp;$\mathcal{M}_{\text{backward}} \leftarrow \text{append}(\mathcal{M}_{\text{backward}}, A_j)$
16: **end for**
17: $\triangleright$ **Meeting Step (match on c bits)**
18: **for** $X \in \mathcal{M}_{\text{forward}}$ **do**
19: &nbsp;&nbsp;&nbsp;&nbsp;**for** $A \in \mathcal{M}_{\text{backward}}$ **do**
20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $X \equiv A \pmod{2^c}$ **then**
21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$m_1 \leftarrow (X \oplus A)$
22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Store $(X, A, m_0 \parallel m_1)$ in $\mathcal{M}_{\text{match}}$
23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
24: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
25: **end for**
26: $\triangleright$ **Search for double collision**
27: **for** $i = 0$ to $\text{len}(\mathcal{M}_{\text{match}}) - 1$ **do**
28: &nbsp;&nbsp;&nbsp;&nbsp;$(X_i, Y_i) \leftarrow \mathcal{M}_{\text{match}}[i]$
29: &nbsp;&nbsp;&nbsp;&nbsp;**for** $j = i + 1$ to $\text{len}(\mathcal{M}_{\text{match}}) - 1$ **do**
30: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$(X_j, Y_j) \leftarrow \mathcal{M}_{\text{match}}[j]$
31: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $P_1(X_i)^c \oplus P_1(X_j)^c = 0$ **and** $P_2(Y_i)^c \oplus P_2(Y_j)^c = 0$ **then**
32: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $(X_i, Y_i), (X_j, Y_j)$
33: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**end if**
34: &nbsp;&nbsp;&nbsp;&nbsp;**end for**
35: **end for**