missing difference attack, using the basic sieving algorithm instead of the fast-convolution sieving.

## 5.6 Conclusion

The missing difference attacks against CTR of Section 5.5 and the collision attacks against CBC of Section 5.3 are two different ways block cipher modes can fail beyond the birthday bound. They exploit different properties of the modes, but result in similar attacks in terms of concrete requirements. This contradicts previous beliefs that CTR is less sensitive to birthday attacks than CBC. These techniques can be used against many other modes of operations (OFB, CFB, ...); most of them will be vulnerable to at least one the attacks, unless they have been carefully designed to provide security beyond the birthday bound.

**Plaintext recovery for OFB.** It is interesting to consider the security of OFB in light of the previous results. OFB turns a block cipher into stream cipher by iteratively encrypting an IV:

$$z_{-1} = \text{IV}$$

$$z_i = E_k(z_{i-1})$$

$$c_i = z_i \oplus m_i$$

If OFB is used with many short messages with different IVs, then collisions in the sequence $z_i$ are expected. A collision can be detected with partial knowledge of the plaintext; it implies that the next $z_i$ also collide and this leaks plaintext information.

On the other hand, if OFB is used with a single long message (or in a stateful variant without IV), then the $z_i$ sequence follows a cycle of $E_k$. With high probability, the cycle has length close to $2^n$, and no collision is expected around the birthday bound. In this case, the missing difference attack recovers plaintext data.

**Plaintext recovery for f8.** The f8 mode used in UMTS telephony is a variant of the OFB and CTR modes, that was apparently designed to avoid the collision attack against OFB:

$$A = E_{k'}(\text{IV})$$

$$z_{-1} = 0$$

$$z_i = E_k(A \oplus i \oplus z_{i-1})$$

$$c_i = z_i \oplus m_i$$

Our attack can be applied to the first block of ciphertext. Indeed, the first block of message $i$ is encrypted as $c_0 = m_0 \oplus E_k(E_{k'}(\text{IV}))$, where the value $E_k(E_{k'}(\text{IV}))$ is unique for all the messages encrypted with a given key.

**Practical demonstration.** When the block-size $n$ is equal to 64 bits (or smaller), a plaintext-recovery attack can be carried out in practice in a realistic setting, with a man-in-the-browser recovering an authentication token. This should not come as a surprise to cryptographers, but practitioners tended to downplay the impact of these attacks, and ciphers with 64-bit block sizes were still in use in many protocols when we disclosed our results. By implementing an attack against a popular protocol under real-world conditions, we managed to convince them to deprecate those ciphers. Since legacy block ciphers are often used with CBC but very rarely with CTR, we only demonstrated the CTR attack in practice.
# 6. Generic Attacks Against Beyond-Birthday-Bound MACs

This chapter is based on article [LNS18], found in Appendix J.

In order to avoid birthday attacks, several block-cipher based MACs have been proposed with an internal state larger than the primitive size. In particular, several constructions use a 2n-bit internal state so that collisions in the state are only expected after 2n queries.

## 6.1 Double-block hash-then-sum MACs

Several block-cipher based MACs with security beyond the birthday bound have been proposed in the last years. Yasuda first proposed SUM-ECBC [Yas10], a beyond birthday bound (BBB) secure deterministic MAC with a proof of security up to 22n/3 queries. However, this construction has rate 1/2 and Yasuda later proposed PMAC+ [Yas11], a BBB secure MAC achieving rate 1. This inspired several other constructions like 3kf9 [ZWS+12], LightMAC+ [Nail7], GCM-SIV2 [IM16], and single key PMAC+ [DDN+17].

Interestingly, all the above designs share a common structure: the 2n-bit internal state is divided in two n-bit parts, that we denote Σ and Θ, and the final MAC is computed as:

$$MAC(M) = E(\Sigma(M)) \oplus E'(\Theta(M)),$$

where E and E' denote the block cipher with potentially different keys. The functions Σ and Θ can be seen as two n-bit universal hash functions computed on the message. This structure has been called double-block hash-then-sum, and it will be the focus of this chapter. All these MACs have a security proof up to 22n/3 queries [DDN+18], but there are no known attacks with less than 2n queries.

**Our results.** We describe a new cryptanalysis technique for double-block hash-then-sum MACs, that generalizes the collision attack of Preneel and van Oorschot. Instead of looking for a pair of messages so that the full state collides, we look for a quadruple of messages, which can be seen either as two pairs colliding on the first half of the state, or two pairs colliding on the second half. Since the finalization function combines the halves with a sum, we can detect such a quadruple because the corresponding MACs sum to zero, and can usually amplify this filtering. Moreover, when the messages are well constructed, the relations defining the four collisions create a linear system of rank only three, so that we expect one good quadruple out of 23n. Therefore, we only need four lists of 23n/4 queries, and we expect one good quadruple out of the 23n choices in the four lists.

The attacks have a complexity of 23n/4 in the information theoretic model (the model used for most MAC security proofs), but we note that an attacker needs more than 2n operations to create a forgery. However, we have found a variant of our attack against SUM-ECBC and GCM-SIV2 with total complexity below 2n, using O(26n/7) queries and
<figure><img src="image_41.png" /><figcaption>Figure 6.1: SUM-ECBC.</figcaption></figure>

$\tilde{O}(2^{6n/7})$ operations. As far as we know, this is the first attack with complexity below $2^n$ against a deterministic beyond-birthday-bound-secure MAC.

After the publication of our results, a more advanced security proof by Kim, Lee, and Lee [KLL20], proved security up to $2^{3n/4}$ queries, achieving tight security.

## 6.2 Attacking SUM-ECBC

We focus on SUM-ECBC [Yas10], one the simplest double-block hash-then-sum constructions. We describe a universal forgery attack with $O(2^{3n/4})$ queries and $\tilde{O}(2^{3n/2})$ operations, and a variant with total complexity below $2^n$, with $O(2^{6n/7})$ queries and $\tilde{O}(2^{6n/7})$ operations.

SUM-ECBC was designed by Yasuda in 2010 [Yas10], inspired by MAC constructions summing two CBC-MACs in the ISO 9797-1 standard. The scheme uses a block cipher keyed with four independent keys, denoted as $E_1, E_2, E_3, E_4$. The message $M$ is first divided into $n$-bit blocks $M = m_0 \parallel m_1 \parallel m_{L-1}$, and the construction is defined as follows (see Figure 6.1):

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
\Sigma(M) = \sigma_L & \sigma_0 = 0 & \sigma_{i+1} = E_1(\sigma_i \oplus m_i) \\
\Theta(M) = \theta_L & \theta_0 = 0 & \theta_{i+1} = E_3(\theta_i \oplus m_i) \\
\mathsf{MAC}(M) = E_2(\Sigma(M)) \oplus E_4(\Theta(M)) & &
\end{array}
$$

### 6.2.1 Using Quadruples

Our strategy consists in looking for a quadruple of messages $(X, Y, Z, T)$ such that pairs of values collide for one half of the state. More precisely, we look for quadruples satisfying a relation $\mathcal{R}(X, Y, Z, T)$ defined as:

$$ \mathcal{R}(X, Y, Z, T) := \begin{cases} \Sigma(X) = \Sigma(Y) \\ \Theta(Y) = \Theta(Z) \\ \Sigma(Z) = \Sigma(T) \\ \Theta(T) = \Theta(X) \end{cases} $$

In particular, since the MAC is computed as $\mathsf{MAC}(M) = E(\Sigma(M)) \oplus E'(\Theta(M))$, it follows that:

$$ \mathcal{R}(X, Y, Z, T) \implies \mathsf{MAC}(X) \oplus \mathsf{MAC}(Y) \oplus \mathsf{MAC}(Z) \oplus \mathsf{MAC}(T) = 0. \quad (6.1) $$

We build the quadruples with two message injection functions:

$$ 
\begin{array}{l@{\qquad}l@{\qquad}l}
\phi(i) = 0 \parallel i & \psi(i) = 1 \parallel i & \\
X = \phi(x) = 0 \parallel x & Y = \psi(y) = 1 \parallel y & \\
Z = \phi(z) = 0 \parallel z & T = \psi(t) = 1 \parallel t, &
\end{array}
$$
With this construction, the pairs $(X, Y)$, $(Y, Z)$, $(Z, T)$ and $(T, X)$ that we consider always contain a message built with $\phi$ and message built with $\psi$. Therefore, we will have the required collisions in $\Sigma$ or $\Theta$ if the difference introduced in the half-state by the second block cancels the difference found after processing the first block.

More precisely, we have

$$ 
\begin{aligned}
\mathbf{MAC}(\phi(i)) &= E_2 \left( \underbrace{E_1(i \oplus E_1(0))}_{\Sigma_0(i)} \right) \oplus E_4 \left( \underbrace{E_3(i \oplus E_3(0))}_{\Theta_0(i)} \right) \\
\mathbf{MAC}(\psi(i)) &= E_2 \left( \underbrace{E_1(i \oplus E_1(1))}_{\Sigma_1(i)} \right) \oplus E_4 \left( \underbrace{E_3(i \oplus E_3(1))}_{\Theta_1(i)} \right)
\end{aligned}
$$

and the relation $\mathcal{R}$ becomes:

$$ \mathcal{R}(x, y, z, t) \Leftrightarrow \left\{ \begin{array}{l} x \oplus E_1(0) = y \oplus E_1(1) \\ z \oplus E_3(0) = y \oplus E_3(1) \\ z \oplus E_1(0) = t \oplus E_1(1) \\ x \oplus E_3(0) = t \oplus E_3(1) \end{array} \right\} \Leftrightarrow \left\{ \begin{array}{l} x \oplus y \oplus z \oplus t = 0 \\ x \oplus y = E_1(0) \oplus E_1(1) \\ x \oplus t = E_3(0) \oplus E_3(1) \end{array} \right. $$

Because of the choice of the injection functions, $\mathcal{R}$ reduces to a linear system of rank only three. Therefore, we expect to find one quadruple satisfying the relation out of $2^{3n}$, and we can construct $2^{3n}$ quadruples with just $4 \times 2^{3n/4}$ queries. This gives an attack with data complexity $O(2^{3n/4})$.

### 6.2.2 Detecting Quadruples

To complete the attack we need to identify a quadruple satisfying $\mathcal{R}$. We directly observe when $x \oplus y \oplus z \oplus t = 0$, and we also detect the relation on the sum of the MACs following Equation (6.1):

$$ \mathcal{R}(x, y, z, t) \Rightarrow \mathbf{MAC}(\phi(x)) \oplus \mathbf{MAC}(\psi(y)) \oplus \mathbf{MAC}(\phi(z)) \oplus \mathbf{MAC}(\psi(t)) = 0 $$

However, we need a $3n$-bit condition to identify a good quadruple with high probability. We use related quadruples that satisfy $\mathcal{R}$ simultaneously to amplify the filtering. We observe that $\mathcal{R}(x, y, z, t)$ is satisfied if and only if $\mathcal{R}(x \oplus c, y \oplus c, z \oplus c, t \oplus c)$ is satisfied for any constant $c$.

$$ \mathcal{R}(x, y, z, t) \iff \forall c, \mathcal{R}(x \oplus c, y \oplus c, z \oplus c, t \oplus c) \qquad (6.2) $$

This leads to an attack with $O(2^{3n/4})$ queries: we consider four sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \mathcal{T}$ of $2^{3n/4}$ values, and we look for a quadruple $(x, y, z, t) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z} \times \mathcal{T}$ with:

$$ \left\{ \begin{array}{l} x \oplus y \oplus z \oplus t = 0 \\ \mathbf{MAC}(\phi(x)) \oplus \mathbf{MAC}(\psi(y)) \oplus \mathbf{MAC}(\phi(z)) \oplus \mathbf{MAC}(\psi(t)) = 0 \\ \mathbf{MAC}(\phi(x \oplus 1)) \oplus \mathbf{MAC}(\psi(y \oplus 1)) \oplus \mathbf{MAC}(\phi(z \oplus 1)) \oplus \mathbf{MAC}(\psi(t \oplus 1)) = 0. \end{array} \right. \qquad (6.3) $$

In practice, we build consider four lists of size $2^{3n/4}$ to express the search for a quadruple as an instance of the 4-sum problem:

$$ L_1 = \{x \mid \mathbf{MAC}(\phi(x)) \mid \mathbf{MAC}(\phi(x \oplus 1)) : x \in \mathcal{X}\} $$

$$ L_2 = \{y \mid \mathbf{MAC}(\psi(y)) \mid \mathbf{MAC}(\psi(y \oplus 1)) : y \in \mathcal{Y}\} $$

$$ L_3 = \{z \mid \mathbf{MAC}(\phi(z)) \mid \mathbf{MAC}(\phi(z \oplus 1)) : z \in \mathcal{Z}\} $$

$$ L_4 = \{t \mid \mathbf{MAC}(\psi(t)) \mid \mathbf{MAC}(\psi(t \oplus 1)) : t \in \mathcal{T}\} $$
A 4-sum algorithm returns $(x, y, z, t) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z} \times \mathcal{T}$ such that $L_1[x] \oplus L_2[y] \oplus L_3[z] \oplus L_4[t] = 0$. A naive algorithm would take time $2^{3n}$ to examine all quadruples, but there is a simple improvement with time $\tilde{O}(2^{3n/2})$: the attacker first builds $L_1 \times L_2$ and $L_3 \times L_4$, then she looks for a collision between the two lists. After finding a collision, we verify that it is not a false positive by testing the relation for another value $c$.

**Universal Forgeries.** This attack can be extended to a universal forgery. Indeed, the fixed prefix 0 and 1 can be replaced by $v$ and $v \oplus 1$ for any block $v$, and when we identify a right quadruple $(x, y, z, t)$ we deduce the value $\Delta_1 = E_1(v) \oplus E_1(v \oplus 1)$ and $\Delta_3 = E_3(v) \oplus E_3(v \oplus 1)$. There is also a length extension property: if $(x, y, z, t)$ is a right quadruple, then $\mathbf{MAC}(v \parallel x \parallel s) \oplus \mathbf{MAC}(v \oplus 1 \parallel y \parallel s) \oplus \mathbf{MAC}(v \parallel z \parallel s) \oplus \mathbf{MAC}(v \oplus 1 \parallel t \parallel s) = 0$ for any suffix $s$.

Therefore, if we want to forge a MAC for any message $m$ of size $L \ge 2$ blocks we parse it as $m = v \parallel w \parallel s$ (where $s$ has zero, one, or several blocks) and perform the attack to recover $\Delta_1$ and $\Delta_3$. Then we can forge using the previous relation, and Equation (6.2):

$$ \mathbf{MAC}(v \parallel w \parallel s) = \mathbf{MAC}(v \oplus 1 \parallel w \oplus \Delta_1 \parallel s) \oplus \mathbf{MAC}(v \parallel w \oplus \Delta_3 \parallel s) \\ \oplus \mathbf{MAC}(v \oplus 1 \parallel w \oplus \Delta_1 \oplus \Delta_3 \parallel s) $$

### 6.2.3 Optimizing the time complexity.

Equation (6.2) can also be used to reduce the time complexity below $2^n$, at the cost of more oracle queries. Indeed, if we consider a subset $C$ of $\{0, 1\}^n$, we have:

$$ \begin{aligned} & \mathcal{R}(x, y, z, t) \\ & \Leftrightarrow \forall c \in C, \mathcal{R}(x \oplus c, y \oplus c, z \oplus c, t \oplus c) \\ & \Rightarrow \forall c \in C, \mathbf{MAC}(\phi(x \oplus c)) \oplus \mathbf{MAC}(\psi(y \oplus c)) \oplus \mathbf{MAC}(\phi(z \oplus c)) \oplus \mathbf{MAC}(\psi(t \oplus c)) = 0 \\ & \Rightarrow \bigoplus_{c \in C} \mathbf{MAC}(\phi(x \oplus c)) \oplus \bigoplus_{c \in C} \mathbf{MAC}(\psi(y \oplus c)) \oplus \bigoplus_{c \in C} \mathbf{MAC}(\phi(z \oplus c)) \oplus \bigoplus_{c \in C} \mathbf{MAC}(\psi(t \oplus c)) = 0 \end{aligned} \tag{6.4} $$

If we select $C$ as a linear subspace, then the last expression does not depend on the full $(x, y, z, t)$, but only on their projection on the orthogonal complement of $C$. Concretely, we use $C = \{x : x_{[3n/7:n]} = 0\} = \{x : x < 2^{3n/7}\}$, so that the value $\bigoplus_{c \in C} \mathbf{MAC}(\phi(x \oplus c))$ depends on only $4n/7$ bits of $x$.

Therefore, we consider the rewritten MAC function

$$ \mathbf{MAC}'(v \parallel w) = \bigoplus_{c \in C} \mathbf{MAC}(v \parallel w \oplus c), $$

the following message injections, with a $4n/7$-bit input

$$ \phi'(i) = 0 \parallel i|0 \qquad \psi'(i) = 1 \parallel i|0, $$

and a reduced relation over $4n/7$-bit values:

$$ \mathcal{R}'(x, y, z, t) := \begin{cases} x \oplus y = (E_1(0) \oplus E_1(1))_{[3n/7:n]} \\ y \oplus z = (E_3(0) \oplus E_3(1))_{[3n/7:n]} \\ z \oplus t = (E_1(0) \oplus E_1(1))_{[3n/7:n]} \\ t \oplus x = (E_3(0) \oplus E_3(1))_{[3n/7:n]} \end{cases} \Leftrightarrow \begin{cases} x \oplus y \oplus z \oplus t = 0 \\ x \oplus y = (E_1(0) \oplus E_1(1))_{[3n/7:n]} \\ x \oplus t = (E_3(0) \oplus E_3(1))_{[3n/7:n]} \end{cases} $$

Thanks to Equation 6.4, we still have:

$$ \mathcal{R}'(x, y, z, t) \Rightarrow \mathbf{MAC}'(\phi'(x)) \oplus \mathbf{MAC}'(\psi'(y)) \oplus \mathbf{MAC}'(\phi'(z)) \oplus \mathbf{MAC}'(\psi'(t)) = 0 $$

Since the relation $\mathcal{R}'$ is now only a $12n/7$-bit condition, we use shorter lists, with just $2^{3n/7}$ elements. We also increase the filtering using the same trick as previously. Using the 4-sum algorithm, we locate a right quadruple using $\tilde{O}(2^{6n/7})$ operations. The attack uses $O(2^{6n/7})$ queries to generate the lists, because each element is the sum of $2^{3n/7}$ queries.
<table><caption>**Table 6.1:** Summary of the security for studied modes and our main results. *q* is the number of queries, *ℓ* is maximum size of a query, *σ* is the total number of processed blocks. The expected lower bound and attack complexity is in number of constant length queries (*ℓ* = *O*(1)). We use “U” for universal forgeries, and “E” for existential forgeries. Proofs marked with * are invalidated by our results.</caption><thead><tr><th rowspan="2">Mode</th><th colspan="2">Provable security bounds</th><th colspan="3">Our attacks</th></tr><tr><th>Advantage</th><th>Queries</th><th>Queries</th><th>Time Type</th></tr></thead><tbody><tr><td rowspan="2">SUM-ECBC [Yas10]</td><td rowspan="2">O(q<sup>3</sup>ℓ<sup>3</sup>/2<sup>2n</sup>) with ℓ ≤ 2<sup>2n/5</sup></td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω(2<sup>3n/2</sup>) U</td></tr><tr><td>O(2<sup>6n/7</sup>)</td><td>Ω(2<sup>6n/7</sup>) U</td></tr><tr><td>[KLL20]</td><td>O(q<sup>4/3</sup>ℓ<sup>o(1)</sup>/2<sup>n</sup> + q<sup>4/3</sup>ℓ<sup>4</sup>/2<sup>2n</sup>)</td><td>Ω(2<sup>3n/4</sup>)</td><td></td><td></td></tr><tr><td rowspan="2">GCM-SIV2 [IM16]</td><td rowspan="2">O(qℓ/2<sup>n</sup> + q<sup>3</sup>ℓ<sup>2</sup>/2<sup>2n</sup>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω(2<sup>3n/2</sup>) U</td></tr><tr><td>O(2<sup>6n/7</sup>)</td><td>Ω(2<sup>6n/7</sup>) U</td></tr><tr><td rowspan="2">PMAC+ [Yas11]</td><td rowspan="2">O(q<sup>3</sup>ℓ<sup>3</sup>/2<sup>2n</sup>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω(2<sup>3n/2</sup>) E</td></tr><tr><td>O(2<sup>3n/4</sup>)</td><td></td></tr><tr><td rowspan="2">LightMAC+ [Nai17]</td><td rowspan="2">O(q<sup>2</sup>q<sub>v</sub>/2<sup>2n</sup>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω(2<sup>3n/2</sup>) E</td></tr><tr><td>O(2<sup>3n/4</sup>)</td><td></td></tr><tr><td rowspan="2">[Nai18]</td><td rowspan="2">O(q<sup>4/3</sup>q<sub>v</sub>/2<sup>2n</sup>)*</td><td rowspan="2">Ω(2<sup>3n/4</sup>)</td><td></td><td></td></tr><tr><td></td><td></td></tr><tr><td rowspan="2">[KLL20]</td><td rowspan="2">O(q<sup>4/3</sup>/2<sup>n</sup>)</td><td rowspan="2">Ω(2<sup>3n/4</sup>)</td><td></td><td></td></tr><tr><td></td><td></td></tr><tr><td>1kPMAC+ [DDN+17]</td><td>O(σ/2<sup>n</sup> + qσ<sup>2</sup>/2<sup>2n</sup>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω(2<sup>3n/2</sup>) E</td></tr><tr><td rowspan="2">3kf9 [ZWS+12]</td><td rowspan="2">O(q<sup>3</sup>ℓ<sup>3</sup>/2<sup>2n</sup> + qℓ/2<sup>n</sup>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(√n·2<sup>3n/4</sup>)</td><td>Ω(2<sup>5n/4</sup>) U</td></tr><tr><td>Ω(2<sup>3n/4</sup>)</td><td></td></tr><tr><td rowspan="2">[KLL20]</td><td rowspan="2">O(q<sup>4/3</sup>ℓ<sup>4/3</sup>/2<sup>n</sup> + q<sup>2</sup>ℓ<sup>2</sup>/2<sup>2n</sup> + q<sup>4</sup>ℓ<sup>6</sup>/2<sup>3n</sup>)</td><td rowspan="2">Ω(2<sup>3n/4</sup>)</td><td></td><td></td></tr><tr><td></td><td></td></tr><tr><td>1kf9 [DDN+15]</td><td>O(qℓ<sup>2</sup>/2<sup>n</sup> + q<sup>3</sup>ℓ<sup>4</sup>/2<sup>2n</sup> + q<sup>4</sup>ℓ<sup>4</sup>/2<sup>3n</sup> + q<sup>4</sup>ℓ<sup>6</sup>/2<sup>4n</sup>)*</td><td>Ω(2<sup>2n/3</sup>)*</td><td>O(2<sup>n/2</sup>)</td><td>Ω(2<sup>n/2</sup>) U</td></tr></tbody></table>

## 6.3 Generalization to double-block hash-then-sum MACs

In the full paper [LNS18] (Appendix J), we generalize this attack to a framework for attacks against double-block hash-then-sum MACs. Table 6.1 shows a summary of our results and how they compare with their respective provable security claims. In particular, we have forgeries attacks with $O(2^{3n/4})$ short MAC queries against SUM-ECBC, GCM-SIV2, PMAC+, LightMAC+, 1kPMAC+, and 3kf9. As far as we know, these are the first attacks with less than $2^n$ blocks of data against these constructions.

These results were an important step towards understanding the actual security of these modes, by providing a security upper bound of $2^{3n/4}$ short queries when the lower bound from the proof was $2^{2n/3}$ queries. Later work has given security proof with the same bound $2^{3n/4}$ [KLL20] for most of these constructions, which closes the gap between proofs and attacks.

Our attacks exploit the fact that the two halves are combined with a sum, where one side depends only on $\Sigma$, and the other side depends only on $\Theta$. They do not seem applicable to constructions with more intricate finalization functions, such as LightMAC+2 [Nai17], or the tweakable block-cipher based constructions PMAC_TBC [Nai15], PMACx [LN17a], ZMAC [IMP+17], or ZMAC+[LN17b].

**Mistakes in proofs.** Our attack against LightMAC+ contradicts a security bound for LightMAC+ by Naito [Nai18], because we have an attack with $O(2^{3n/4})$ MAC queries, and a single verification query. We have also found an attack with only $O(2^{n/2})$ queries and $\tilde{O}(2^{n/2})$ operations against 1kf9 [DDN+15], a single key variant of 3kf9 with claimed security up to $2^{2n/3}$ queries. 1kf9 had been withdrawn due to issues with its security proof before our result, but no attack was known previously.
# 7. Generic Attacks Against MACs in the Quantum Setting

*This chapter is based on articles [KLL+16a] and [BLN+21], found in Appendix K and L.*

Cryptography would be particularly affected by the development of large-scale quantum computers. In particular, currently used asymmetric cryptographic primitives based on number theory (RSA [RSA78], Diffie-Hellman key exchange [DH76], elliptic-curve cryptography [Mil86; Kob87], ...) would be broken in polynomial time due to Shor's algorithm [Sho97]. This has motivated the cryptographic community to search for quantum-safe solutions: the goal of post-quantum cryptography is to prepare cryptographic primitives to resist quantum adversaries, i.e. adversaries with access to a quantum computer. Symmetric cryptography is much less impacted by quantum algorithms. The main result is a quadratic speed-up of exhaustive search using Grover's algorithm [Gro96]. Since the attack is still exponential, it can be countered by just properly dimensioning the primitive.

In this chapter we analyze the security of MAC algorithms in a quantum setting. We consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in this model.

We show that several classical attacks based on finding collisions can be dramatically sped up using a quantum procedure called *Simon's algorithm*: finding a collision requires $\Omega(2^{n/2})$ queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only $O(n)$ queries in the quantum model. We obtain a series of attacks against many standardized MACs: CBC-MAC, PMAC, GMAC, LightMAC, ... This is quite surprising compared to the situation with encryption modes: standard modes (CBC, CTR, OFB, CFB) are secure with a quantum-secure block ciphers [ATT+16].

## 7.1 Quantum security models

We present our attacks using quantum algorithms as black boxes, so that our results can be understood without specific knowledge of quantum computing. Nonetheless, we give a basic description of the quantum circuit model in order to define quantum security notions.

The basic computation units are qubits, two-level quantum systems whose state is represented by a *superposition* $\alpha|0\rangle + \beta|1\rangle$, with amplitudes $\alpha$ and $\beta$, which is a normalized vector in $\mathbb{C}^2$ (of norm $|\alpha^2| + |\beta^2| = 1$). The state of an $n$-qubit system belongs to $\mathbb{C}^{2^n}$, its $2^n$ basis vectors (in the computational basis) are the $2^n$ $n$-bit strings. A quantum algorithm is a sequence of unitary operators of $\mathbb{C}^{2^n}$, partial measurements, and oracle calls. We say that a function $f$ is queried *in superposition* if the following unitary operator $O_f$ is made available: $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$. Indeed, this operator allows querying $f$ on any quantum state, thus on any *superposition* of inputs $x$.
**Q1 and Q2 setting.** To define quantum security notion, we consider the adversary as a quantum algorithm. Following [KLL+16b], we adopt the Q1 / Q2 terminology to classify quantum attacks on symmetric schemes. In the Q1 setting, the adversary is given only *classical* encryption or decryption query access to black-boxes. In the Q2 setting, the adversary is given *quantum* or *superposition* access, in the sense that a black-box $E_k$ becomes a quantum oracle $O_{E_k}$. Note that these models have alternative names, for example Q2 security has been called “quantum chosen-plaintext attack” (qCPA) or “quantum security” in previous works.

The Q1 setting is more realistic: the adversary receives classical data, and only uses
local quantum computation. This is the setting used by attacks against asymmetric
schemes based on Shor's algorithm: the adversary receives the (classical) public key, and
uses a quantum computer to recover the private key. Key-recovery attacks using Grover's
algorithm are also in the Q1 setting: the adversary receives a pair of known plaintext and
ciphertext, and uses quantum computation locally to recover the corresponding key.

The Q2 setting is a simple and natural extension of the Q1 setting, giving more power to the adversary. It encompasses any reasonable model of quantum attacks, so that a security proof in this model gives a high level of assurance. Previous work has shown that it is possible to build secure cryptosystems in this model [BZ13a]. Concretely, it assumes that the legitimate user implements the algorithm on a quantum computer, and that the adversary obtains oracle access.

The study of quantum attacks on symmetric schemes in the Q2 setting was sparkled
by the seminal work of Kuwakado and Morii [KM10; KM12], who showed that the 3-
round Feistel construction and the Even-Mansour cipher became insecure if exposed
to superposition queries. More precisely, they use Simon's algorithm to respectively
distinguish the construction and recover the key of the cipher in polynomial time, while
classical proofs of security exist.

**Unforgeability.** In this chapter, we consider forgery attacks: the goal of the attacker is to forge a tag for some arbitrary message, without the knowledge of the secret key. In a classical setting, we assume that the adversary has access to a MAC oracle, and she must predict the MAC of a message that she has not queried. In the quantum setting, we must modify this definition because a superposition query can include all messages simultaneously.

We follow the EUF-qCMA security definition of Boneh and Zhandry [BZ13a]. A message authentication code is broken by a quantum existential forgery attack if after *q* queries to the cryptographic oracle, the adversary can generate at least *q* + 1 valid messages with corresponding tags.

For nonce-based MACs, we assume that the nonce is classical, and chosen randomly by
the adversary (as in the IND-qCPA notion [BZ13b]). This sidesteps the issue of defining
the uniqueness of a nonce in quantum superposition.

**7.2 Simon’s algorithm**

Simon's algorithm [Sim97] was one of the first algorithms to show an exponential speedup
in the quantum setting, and inspired Shor's algorithm. It solves the following problem:

**Simon's problem:** Given a Boolean function $f : \{0,1\}^n \to \{0,1\}^n$ and the promise
that there exists $s \in \{0,1\}^n$ such that for any $(x,y) \in \{0,1\}^n$, $[f(x) = f(y)] \Leftrightarrow$
$[x \oplus y \in \{0^n, s\}]$, the goal is to find $s$.

This problem can be solved classically by searching for collisions. The optimal time to
solve it is therefore $\Theta(2^{n/2})$. On the other hand, Simon's algorithm solves this problem
<figure><img src="image_42.png" /><figcaption>Figure 7.1: Encrypt-last-block CBC-MAC.</figcaption></figure>

with quantum complexity $\mathcal{O}(n)$ using superposition queries to $f$.

The algorithm uses a quantum subroutine that makes a single superposition query to $f$, and returns a random vector $y$ such that $y \cdot s = 0$. By repeating this subroutine $\mathcal{O}(n)$ times, one obtains $n-1$ independent vectors orthogonal to $s$ with high probability, and $s$ can be recovered using basic linear algebra.

### 7.2.1 Attack strategy

The general strategy behind our attacks follows the approach used by Kuwakado and Morii. We start with the MAC oracle $F_k: \{0,1\}^n \to \{0,1\}^n$ and exhibit a new function $f$ that satisfies Simon's promise with two additional properties: the adversary should be able to query $f$ in superposition if she has quantum oracle access to $F_k$, and the knowledge of the string $s$ should be sufficient to break the cryptographic scheme. In most cases, the construction of $f$ corresponds to a classical collision attack.

### 7.2.2 Dealing with unwanted collisions

In our cryptanalysis scenario, it is not always the case that the promise of Simon's problem is perfectly satisfied. More precisely, by construction, there will always exist an $s$ such that $f(x) = f(x \oplus s)$ for any input $x$, but there might be additional collisions. If the number of such unwanted collisions is too large, one might not be able to obtain a full rank linear system of equations from Simon's subroutine after $\mathcal{O}(n)$ queries.

In [KLL+16a] (Appendix K), we show that Simon's algorithm runs in time $\mathcal{O}(n)$ under a weaker assumption:

$$ \max_{t \notin \{0,s\}} \mathrm{Pr}_x [f(x \oplus t) = f(x)] \le \frac{1}{2}. \qquad (7.1) $$

In practice, we cannot prove this bound, but if it does not hold, then some of the primitives used in the construction are far from ideal. We can show that this happens with low probability, and would imply a classical attack against the system.

## 7.3 Breaking CBC-MAC

CBC-MAC is one of the earliest MAC constructions, inspired by the CBC encryption mode [NBS85]. Since the basic CBC-MAC is only secure when the queries are prefix-free, there are many variants of CBC-MAC to provide security for arbitrary messages. In the following we describe the Encrypt-last-block CBC-MAC variant [BKR94], using two keys $k$ and $k'$, but the attack can be easily adapted to other variants. On a message $M = m_0 \parallel \dots \parallel m_{L-1}$, CBC-MAC is defined as (see Figure 7.1):

$$ x_0 = 0 \qquad x_{i+1} = E_k(x_i \oplus m_i) \qquad \mathrm{CBC-MAC}(M) = E_{k'}(x_L) $$

CBC-MAC is standardized and widely used. It has been proven secure up to the birthday bound [BKR94], assuming that the block cipher is indistinguishable from a random permutation.
**Quantum attack.** We present a powerful forgery attack on CBC-MAC with very low complexity using superposition queries. We fix two arbitrary message blocks $\alpha_0, \alpha_1$, with $\alpha_0 \neq \alpha_1$, and we define the following function:

$$f: \{0,1\} \times \{0,1\}^n \to \{0,1\}^n \\ b, x \mapsto \text{CBC-MAC}(\alpha_b \| x) = E_{k'}(E_k(x \oplus E_k(\alpha_b))).$$

The function $f$ can be computed with a single call to the cryptographic oracle, and we can build a quantum circuit for $f$ given a black box quantum circuit for CBC-MAC$_k$. Moreover, $f$ satisfies the promise of Simon's problem with $s = 1 \| E_k(\alpha_0) \oplus E_k(\alpha_1)$:

$$\begin{align*}
f(0, x) &= E_{k'}(E_k(x \oplus E_k(\alpha_1))), \\
f(1, x) &= E_{k'}(E_k(x \oplus E_k(\alpha_0))), \\
f(b, x) &= f(b \oplus 1, x \oplus E_k(\alpha_0) \oplus E_k(\alpha_1)).
\end{align*}$$

More precisely:

$$\begin{align*}
f(b', x') = f(b, x) &\Leftrightarrow x \oplus E_k(\alpha_b) = x' \oplus E_k(\alpha_{b'}) \\
&\Leftrightarrow \begin{cases} x' \oplus x = 0 & \text{if } b' = b \\ x' \oplus x = E_k(\alpha_0) \oplus E_k(\alpha_1) & \text{if } b' \neq b \end{cases}
\end{align*}$$

Therefore, an application of Simon's algorithm returns $E_k(\alpha_0) \oplus E_k(\alpha_1)$. This allows to forge messages easily:

1. Query the tag of $\alpha_0 \| m_1$ for an arbitrary block $m_1$;

2. The same tag is valid for $\alpha_1 \| m_1 \oplus E_k(\alpha_0) \oplus E_k(\alpha_1)$.

In order to break the formal notion of EUF-qCMA security, we must produce $q+1$ valid tags with only $q$ queries to the oracle. Let $q' = O(n)$ denote the number of quantum queries made to learn $E_k(\alpha_0) \oplus E_k(\alpha_1)$. The attacker just repeats the forgery step $q' + 1$ times, in order to produce $2(q' + 1)$ messages with valid tags, after a total of $2q' + 1$ classical and quantum queries to the cryptographic oracle. Therefore, CBC-MAC is broken by a quantum existential forgery attack.

## 7.4 Breaking PMAC

PMAC is a parallelizable block-cipher based MAC designed by Rogaway [Rog04]. PMAC is based on the XE construction: the construction uses secret offsets $\Delta_i$ and $\Delta^*$ derived from the secret key to turn the block cipher into a tweakable block cipher. More precisely, the PMAC algorithm is defined on a message $M = m_0 \| \dots \| m_{L-1}$ as (see Figure 7.2):

$$c_i = E_k(m_i \oplus \Delta_i) \qquad \text{PMAC}(M) = E_k(\Delta^* \oplus m_{L-1} \oplus \bigoplus_{i=0}^{L-2} c_i)$$

Some authenticated encryption schemes use variants of PMAC; we denote as PMAC' the variant used in [HKR17] (see Figure 7.3):

$$c_i = E_k(m_i \oplus \Delta_i) \qquad \text{PMAC'}(M) = E_k(\Delta^* \oplus \bigoplus_{i=0}^{L-1} c_i)$$

We omit the generation of the secret offsets because it is irrelevant to our attacks.
<figure><img src="image_43.png" /><figcaption>Figure 7.2: PMAC.</figcaption></figure>

<figure><img src="image_44.png" /><figcaption>Figure 7.3: PMAC' variant.</figcaption></figure>

**Using the CBC-MAC attack.** When PMAC is used with two-block messages, it has the same structure as CBC-MAC: PMAC($m_0 \parallel m_1$) = $E_k^*(m_1 \oplus E_k^0(m_0))$, with $E_k^0(x) = E_k(x \oplus \Delta_0)$ and $E_k^*(x) = E_k(x \oplus \Delta_*)$. Therefore, we can use the attack of the previous section to recover $E_k^0(\alpha_0) \oplus E_k^0(\alpha_1)$ for arbitrary values of $\alpha_0$ and $\alpha_1$.

**Quantum attack targeting offsets.** The CBC-MAC attack is not applicable to the PMAC' variant. We propose an alternative attack to recover the difference between two offsets $\Delta_i$. We use the following function:

$$f: \{0,1\}^n \to \{0,1\}^n \\ x \mapsto \text{PMAC}'(x \parallel x) = E_k^*(E_k(x \oplus \Delta_0) \oplus E_k(x \oplus \Delta_1)).$$

In particular, it satisfies $f(x \oplus s) = f(x)$ with $s = \Delta_0 \oplus \Delta_1$. This function does not satisfy the strict promise of Simon's algorithm because it has additional collisions, but we can show that the condition (7.1) is satisfied if E is a good block cipher. Therefore, we apply Simon's algorithm to recover $\Delta_0 \oplus \Delta_1$. We obtain forgeries as follows:

1. Query the tag of $m \parallel m$ for an arbitrary block $m$;

2. The same tag is valid for $m \oplus \Delta_0 \oplus \Delta_1 \parallel m \oplus \Delta_0 \oplus \Delta_1$.

## 7.5 Breaking GMAC

GMAC is the underlying MAC of the widely used GCM standard, designed by McGrew and Viega [MV04], and standardized by NIST. GMAC follows the Wegman-Carter construction [CW77]: it is built from a universal hash function, using polynomial evaluation in a Galois field. As opposed to the constructions of the previous sections, GMAC is a randomized MAC; it requires a second input $N$, which must be non-repeating (a nonce). GMAC is essentially defined as:

$$\text{GMAC}(N, M) = \text{GHASH}(M \parallel \text{len}(M)) \oplus E_k(N \parallel 1) \\ \text{GHASH}(M) = \bigoplus_{i=0}^{\text{len}(M)-1} m_i \odot H^{\text{len}(M)-i} \quad \text{with } H = E_k(0),$$

where $\text{len}(M)$ is the length of $M$, and $\odot$ is the finite-field multiplication.

**Quantum attack.** When the polynomial is evaluated with Horner's rule, the structure of GMAC is similar to that of CBC-MAC (see Figure 7.4). For a two-block message, we have $\text{GMAC}(m_0 \parallel m_1) = ((m_0 \odot H) \oplus m_1) \odot H \oplus E_k(N \parallel 1)$. Therefore, we use the same function as in the CBC-MAC attack, with fixed blocks $\alpha_0$ and $\alpha_1$:

$$f_N: \{0,1\} \times \{0,1\}^n \to \{0,1\}^n \\ b, x \mapsto \text{GMAC}(N, \alpha_b \parallel x) = \alpha_b \odot H^2 \oplus x \odot H \oplus E_k(N \parallel 1).$$
<figure><img src="image_45.png" /><figcaption>Figure 7.4: GMAC.</figcaption></figure>

In particular, we have:

$$ 
\begin{align*}
f_N(b', x') = f(b, x) &\Leftrightarrow \alpha_b \odot H^2 \oplus x \odot H = \alpha_{b'} \odot H^2 \oplus x' \odot H \\
&\Leftrightarrow \begin{cases} x' \oplus x = 0 & \text{if } b' = b \\ x' \oplus x = (\alpha_0 \oplus \alpha_1) \odot H & \text{if } b' \neq b \end{cases}
\end{align*}
$$

Therefore $f_N$ satisfies the promise of Simon's algorithm with $s = 1 \parallel (\alpha_0 \oplus \alpha_1) \odot H$.

**Dealing with the nonce.** Since $N$ is a nonce we can only query $f_N$ once.<fnref n="1" /> Therefore, we cannot apply Simon's algorithm as is, because this requires $O(n)$ queries to the same function. However, a single step of Simon's algorithm requires a single query to the $f_N$ function, and returns a vector orthogonal to $s$, for any random choice of $N$ (the secret period $s$ is independent of $N$). Therefore, we recover $(\alpha_0 \oplus \alpha_1) \odot H$ after $O(n)$ steps, even if each step uses a different value of $N$. Then, we deduce $H$ easily, and generate forgeries using $H$:

1. Query the tag of $N$, $m_0 \parallel m_1$ for arbitrary blocks $m_0, m_1$ (under a random nonce $N$).

2. The same tag is valid for $m_0 \oplus 1 \parallel m_1 \oplus H$ (with the same nonce $N$).

As for CBC-MAC, repeating these two steps leads to an existential forgery attack.

## 7.6 Breaking $\Theta$CB3

$\Theta$CB3 [KR11] is the tweakable block-cipher variant of the authenticated encryption scheme OCB3; OCB3 has been standardized by IETF [KR14]. $\Theta$CB3 has the advantage of being secure up to $2^n$ queries (beyond the birthday bound). When used with an empty message, it becomes a nonce-based MAC:

$$ c_i = E_k^i(m_i) \qquad \Theta\text{CB3-MAC}(N, M) = F_k(N) \oplus \bigoplus_{i=0}^{L-1} c_i $$

In this description, $E$ is a tweakable block-cipher: each $E^i$ is assumed to be an independent block cipher. We omit the details of the $F_k$ function for simplicity.

**Quantum linearization attack.** All the attacks described so far exploit the XOR between a secret value (the internal state or a secret offset) and a value chosen by the attacker. Variants of those attacks can be mounted against many MACs with this property. However, in $\Theta$CB3 there is no XOR between the message and a sensitive value, and we need a different type of attack.

Our key idea is to linearize the MAC by restricting the block inputs so that the internal state $\Sigma = \bigoplus_{i=0}^{L-1} E_k^i(m_i)$ is an affine function. We fix two arbitrary message blocks $\alpha_0, \alpha_1$,

<footnote n="1">¹Indeed, we use a quantum security definition where $N$ is a random classical value chosen by the oracle.</footnote>
<figure><img src="image_46.png" /><figcaption>Figure 7.5: ΘCB3 used as a MAC.</figcaption></figure>

with $\alpha_0 \neq \alpha_1$, and we consider messages of the form $M_b = \alpha_{b[0]} \parallel \alpha_{b[1]} \parallel \alpha_{b[2]} \parallel \dots \parallel \alpha_{b[L-1]}$ with $b \in \{0, 1\}^L$. We observe that the internal state is an affine function of b:

$$ \Sigma(M_b) = \bigoplus_{i=0}^{L} E_k^i(\alpha_{b[i]}) = \bigoplus_{i=0}^{L} (E_k^i(\alpha_0) \oplus b[i] \odot (E_k^i(\alpha_0) \oplus E_k^i(\alpha_1))) $$

In particular, with $L > n$ the function $b \mapsto \Sigma(M_b)$ necessarily has a non-trivial kernel: there exist an L-bit vector $s \neq 0$ with $\Sigma(M_{b \oplus s}) = \Sigma(M_b)$ for all b. With $L = n + 1$, s is likely to be unique.

Therefore, we define the following function:

$$ f_N : \{0, 1\}^L \to \{0, 1\}^n \\ b \mapsto \Theta_{CB3-\text{MAC}}(N, M_b) = F_k(N) \oplus \Sigma(M_b) $$

The function has period $s$, so that we recover it using Simon's algorithm. We obtain forgeries as follows:

1. Query the tag of $N, M_0 \parallel m$ for an arbitrary block $m$ (under a random nonce $N$).

2. The same tag is valid for $M_s \parallel m$ (with the same nonce $N$).

**Alternative quantum attacks.** We observe that the function $f_N$ in ΘCB3 is actually an affine function. Therefore, we can mount alternative attacks using other quantum algorithms: Deutsch's algorithm [Deu85] or Bernstein-Vazirani's algorithm [BV97]. This is the first application of those algorithms in the context of symmetric cryptography.

## 7.7 Conclusion

These techniques apply to most of the block-cipher-based MACs proposed in the literature: we obtain polynomial attacks in the Q2 setting against CBC-MAC, PMAC, PMAC+, GMAC, LightMAC, LightMAC+, PolyMAC, ZMAC, PMAC_TBC3k. Similarly, we can break the authentication of the authenticated encryption schemes OCB, ΘCB3, GCM, GCM-SIV, GCM-SIV2, EAX. We also found an efficient attack against Poly1305 using Shor's algorithm based on similar ideas.

Those attacks are not a practical threat because they use the Q2 model, assuming that the adversary can query a MAC oracle with a quantum superposition of messages. However, this is a surprising result, because all those constructions have classical proof of security and we didn't expect an exponential speedup in the quantum model for symmetric cryptosystems. In particular, this partially answers an open question by Boneh and Zhandry in 2013 [BZ13b]: “Do the CBC-MAC or NMAC constructions give quantum-secure PRFs?”.

**Quantum-secure MACs.** Those attacks also motivate the search for efficient quantum-secure MACs. In [SY17], Song and Yun have proven that HMAC and NMAC are secure against an exponential number of quantum queries. Therefore, when we designed
Saturnin [CDL+20], an authenticated encryption scheme aiming for quantum security, we used a mode based on HMAC.

Building a *parallelizable* quantum-secure MAC is more challenging. Indeed, the linearization technique is applicable to a large class of constructions, as long as they can be written in form $G_N(\bigoplus F_i(m_i))$ with $F_i$ arbitrary functions and $G_N$ a function potentially depending on a nonce. This includes most of the proposed parallelizable MACs. In [BBC+21] we propose a new authenticated encryption mode that is efficient, parallelizable, and quantum secure: QCB. QCB is similar to θCB3, but we make all tweakable block-cipher calls dependent on the nonce to avoid this class of attacks.
Bibliography

[ABD+15] D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Zanella-Béguelin, and P. Zimmermann. "Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice". In: *ACM CCS 2015*. Ed. by I. Ray, N. Li, and C. Kruegel. ACM Press, Oct. 2015, pp. 5–17. DOI: 10.1145/2810103.2813707.

[ABP+13] N. J. AlFardan, D. J. Bernstein, K. G. Paterson, B. Poettering, and J. C. N. Schuldt. "On the Security of RC4 in TLS". In: *USENIX Security 2013*. Ed. by S. T. King. USENIX Association, Aug. 2013, pp. 305–320. URL: https://www.usenix.org/system/files/conference/usenixsecurity13/sec13-paper_alfardan.pdf.

[AES] National Institute for Standards and Technology. *Advanced Encryption Standard (AES)*. FIPS 197. Nov. 2001. DOI: https://doi.org/10.6028/NIST.FIPS.197-upd1.

[AHM+10] J.-P. Aumasson, L. Henzen, W. Meier, and R. C.-W. Phan. *SHA-3 proposal BLAKE*. Submission to NIST. 2008/2010. URL: http://131002.net/blake/blake.pdf.

[Ajt96] M. Ajtai. "Generating Hard Instances of Lattice Problems (Extended Abstract)". In: *28th ACM STOC*. ACM Press, May 1996, pp. 99–108. DOI: 10.1145/237814.237838.

[Alb17] A. Albertini. *Exploiting Hash collisions*. Presented at Black Alps 2017. Nov. 2017. URL: https://github.com/corkami/collisions.

[AP13a] N. AlFardan and K. Paterson. *Lucky Thirteen: Breaking the TLS and DTLS Record Protocols*. Blog post. Archived from the original. Feb. 2013. URL: https://web.archive.org/web/20230327103922/http://www.isg.rhul.ac.uk/tls/lucky13.html.

[AP13b] N. J. AlFardan and K. G. Paterson. "Lucky Thirteen: Breaking the TLS and DTLS Record Protocols". In: *2013 IEEE Symposium on Security and Privacy*. IEEE Computer Society Press, May 2013, pp. 526–540. DOI: 10.1109/SP.2013.42.

[ATT+16] M. V. Anand, E. E. Targhi, G. N. Tabia, and D. Unruh. "Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation". In: *Post-Quantum Cryptography - 7th International Workshop, PQCrypto 2016*. Ed. by T. Takagi. Springer, Heidelberg, 2016, pp. 44–63. DOI: 10.1007/978-3-319-29360-8_4.
[BBB+20] D. Bellizia, F. Berti, O. Bronchain, G. Cassiers, S. Duval, C. Guo, G. Leander, G. Leurent, I. Levi, C. Momin, O. Pereira, T. Peters, F.-X. Standaert, B. Udvarhelyi, and F. Wiemer. "Spook: Sponge-Based Leakage-Resistant Authenticated Encryption with a Masked Tweakable Block Cipher". In: *IACR Trans. Symm. Cryptol.* 2020.S1 (2020), pp. 295-349. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.iS1.295-349.

[BBC+21] R. Bhaumik, X. Bonnetain, A. Chailloux, G. Leurent, M. Naya-Plasencia, A. Schrottenloher, and Y. Seurin. "QCB: Efficient Quantum-Secure Authenticated Encryption". In: *ASIACRYPT 2021, Part I*. Ed. by M. Tibouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 668-698. DOI: 10.1007/978-3-030-92062-3_23.

[BBD+15] B. Beurdouche, K. Bhargavan, A. Delignat-Lavaud, C. Fournet, M. Kohlweiss, A. Pironti, P.-Y. Strub, and J. K. Zinzindohoue. "A Messy State of the Union: Taming the Composite State Machines of TLS". In: *2015 IEEE Symposium on Security and Privacy*. IEEE Computer Society Press, May 2015, pp. 535-552. DOI: 10.1109/SP.2015.39.

[BBF+16] K. Bhargavan, C. Brzuska, C. Fournet, M. Green, M. Kohlweiss, and S. Zanella-Béguelin. "Downgrade Resilience in Key-Exchange Protocols". In: *2016 IEEE Symposium on Security and Privacy*. IEEE Computer Society Press, May 2016, pp. 506-525. DOI: 10.1109/SP.2016.37.

[BBK08] E. Barkan, E. Biham, and N. Keller. "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication". In: *Journal of Cryptology* 21.3 (July 2008), pp. 392-429. DOI: 10.1007/s00145-007-9001-y.

[BBL+15] A. Banerjee, H. Brenner, G. Leurent, C. Peikert, and A. Rosen. "SPRING: Fast Pseudorandom Functions from Rounded Ring Products". In: *FSE 2014*. Ed. by C. Cid and C. Rechberger. Vol. 8540. LNCS. Springer, Heidelberg, Mar. 2015, pp. 38-57. DOI: 10.1007/978-3-662-46706-0_3.

[BBL+22] A. Bariant, C. Bouvier, G. Leurent, and L. Perrin. "Algebraic Attacks against Some Arithmetization-Oriented Primitives". In: *IACR Trans. Symm. Cryptol.* 2022.3 (2022), pp. 73-101. DOI: 10.46586/tosc.v2022.i3.73-101.

[BC04] E. Biham and R. Chen. "Near-Collisions of SHA-0". In: *CRYPTO 2004*. Ed. by M. Franklin. Vol. 3152. LNCS. Springer, Heidelberg, Aug. 2004, pp. 290-305. DOI: 10.1007/978-3-540-28628-8_18.

[BCD+20] T. Beyne, A. Canteaut, I. Dinur, M. Eichlseder, G. Leander, G. Leurent, M. Naya-Plasencia, L. Perrin, Y. Sasaki, Y. Todo, and F. Wiemer. "Out of Oddity - New Cryptanalytic Techniques Against Symmetric Primitives Optimized for Integrity Proof Systems". In: *CRYPTO 2020, Part III*. Ed. by D. Micciancio and T. Ristenpart. Vol. 12172. LNCS. Springer, Heidelberg, Aug. 2020, pp. 299-328. DOI: 10.1007/978-3-030-56877-1_11.

[BCJ+05] E. Biham, R. Chen, A. Joux, P. Carribault, C. Lemuet, and W. Jalby. "Collisions of SHA-0 and Reduced SHA-1". In: *EUROCRYPT 2005*. Ed. by R. Cramer. Vol. 3494. LNCS. Springer, Heidelberg, May 2005, pp. 36-57. DOI: 10.1007/11426639_3.

[BCK96] M. Bellare, R. Canetti, and H. Krawczyk. "Keying Hash Functions for Message Authentication". In: *CRYPTO'96*. Ed. by N. Koblitz. Vol. 1109. LNCS. Springer, Heidelberg, Aug. 1996, pp. 1-15. DOI: 10.1007/3-540-68697-5_1.

[BD07] E. Biham and O. Dunkelman. *A Framework for Iterative Hash Functions - HAIFA*. Cryptology ePrint Archive, Report 2007/278. https://eprint.iacr.org/2007/278. 2007.
[BDG+20] Z. Bao, I. Dinur, J. Guo, G. Leurent, and L. Wang. "Generic Attacks on Hash Combiners". In: *Journal of Cryptology* 33.3 (July 2020), pp. 742-823.
DOI: 10.1007/s00145-019-09328-w.

[BDJ+97] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. "A Concrete Security Treatment of Symmetric Encryption". In: *38th FOCS*. IEEE Computer Society Press, Oct. 1997, pp. 394-403.
DOI: 10.1109/SFCS.1997.646128.

[BDL+21] C. Beierle, P. Derbez, G. Leander, G. Leurent, H. Raddum, Y. Rotella, D. Rupprecht, and L. Stennes. "Cryptanalysis of the GPRS Encryption Algorithms GEA-1 and GEA-2". In: *EUROCRYPT 2021, Part II*. Ed. by A. Canteaut and F.-X. Standaert. Vol. 12697. LNCS. Springer, Heidelberg, Oct. 2021, pp. 155-183.
DOI: 10.1007/978-3-030-77886-6_6.

[Ber05] D. J. Bernstein. "The Poly1305-AES Message-Authentication Code". In: *FSE 2005*. Ed. by H. Gilbert and H. Handschuh. Vol. 3557. LNCS. Springer, Heidelberg, Feb. 2005, pp. 32-49.
DOI: 10.1007/11502760_3.

[Ber08] D. J. Bernstein. "The Salsa20 Family of Stream Ciphers". In: *New Stream Cipher Designs: The eSTREAM Finalists*. Ed. by M. Robshaw and O. Billet. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008, pp. 84-97.
ISBN: 978-3-540-68351-3.
DOI: 10.1007/978-3-540-68351-3_8.

[BKR94] M. Bellare, J. Kilian, and P. Rogaway. "The Security of Cipher Block Chaining". In: *CRYPTO'94*. Ed. by Y. Desmedt. Vol. 839. LNCS. Springer, Heidelberg, Aug. 1994, pp. 341-358.
DOI: 10.1007/3-540-48658-5_32.

[BL16a] K. Bhargavan and G. Leurent. "On the Practical (In-)Security of 64-bit Block Ciphers: Collision Attacks on HTTP over TLS and OpenVPN". In: *ACM CCS 2016*. Ed. by E. R. Weippl, S. Katzenbeisser, C. Kruegel, A. C. Myers, and S. Halevi. ACM Press, Oct. 2016, pp. 456-467.
DOI: 10.1145/2976749.2978423.

[BL16b] K. Bhargavan and G. Leurent. "Transcript Collision Attacks: Breaking Authentication in TLS, IKE and SSH". In: *NDSS 2016*. The Internet Society, Feb. 2016.
DOI: 10.14722/ndss.2016.23418.

[BL23] A. Bariant and G. Leurent. "Truncated Boomerang Attacks and Application to AES-Based Ciphers". In: *EUROCRYPT 2023, Part IV*. Ed. by C. Hazay and M. Stam. Vol. 14007. LNCS. Springer, Heidelberg, Apr. 2023, pp. 3-35.
DOI: 10.1007/978-3-031-30634-1_1.

[BLN+21] X. Bonnetain, G. Leurent, M. Naya-Plasencia, and A. Schrottenloher. "Quantum Linearization Attacks". In: *ASIACRYPT 2021, Part I*. Ed. by M. Ti-bouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 422-452.
DOI: 10.1007/978-3-030-92062-3_15.

[BLR13] A. Biryukov, G. Leurent, and A. Roy. "Cryptanalysis of the "Kindle" Cipher". In: *SAC 2012*. Ed. by L. R. Knudsen and H. Wu. Vol. 7707. LNCS. Springer, Heidelberg, Aug. 2013, pp. 86-103.
DOI: 10.1007/978-3-642-35999-6_7.

[BS91] E. Biham and A. Shamir. "Differential Cryptanalysis of DES-like Cryptosystems". In: *Journal of Cryptology* 4.1 (Jan. 1991), pp. 3-72.
DOI: 10.1007/BF00630563.

[BV97] E. Bernstein and U. V. Vazirani. "Quantum Complexity Theory". In: *SIAM J. Comput.* 26.5 (1997), pp. 1411-1473.
DOI: 10.1137/S0097539796300921.
URL: https://doi.org/10.1137/S0097539796300921.
[BWG+17] Z. Bao, L. Wang, J. Guo, and D. Gu. "Functional Graph Revisited: Updates on (Second) Preimage Attacks on Hash Combiners". In: *CRYPTO 2017, Part II*. Ed. by J. Katz and H. Shacham. Vol. 10402. LNCS. Springer, Heidelberg, Aug. 2017, pp. 404–427. DOI: 10.1007/978-3-319-63715-0_14.

[BZ13a] D. Boneh and M. Zhandry. "Quantum-Secure Message Authentication Codes". In: *EUROCRYPT 2013*. Ed. by T. Johansson and P. Q. Nguyen. Vol. 7881. LNCS. Springer, Heidelberg, May 2013, pp. 592–608. DOI: 10.1007/978-3-642-38348-9_35.

[BZ13b] D. Boneh and M. Zhandry. "Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World". In: *CRYPTO 2013, Part II*. Ed. by R. Canetti and J. A. Garay. Vol. 8043. LNCS. Springer, Heidelberg, Aug. 2013, pp. 361–379. DOI: 10.1007/978-3-642-40084-1_21.

[CDL+20] A. Canteaut, S. Duval, G. Leurent, M. Naya-Plasencia, L. Perrin, T. Pornin, and A. Schrottenloher. "Saturnin: a suite of lightweight symmetric algorithms for post-quantum security". In: *IACR Trans. Symm. Cryptol*. 2020.S1 (2020), pp. 160–207. ISSN: 2519-173X. DOI: 10.13154/tosc.v2020.iS1.160-207.

[CDL16] A. Canteaut, S. Duval, and G. Leurent. "Construction of Lightweight S-Boxes Using Feistel and MISTY Structures". In: *SAC 2015*. Ed. by O. Dunkelman and L. Keliher. Vol. 9566. LNCS. Springer, Heidelberg, Aug. 2016, pp. 373–393. DOI: 10.1007/978-3-319-31301-6_22.

[CDM+05] J.-S. Coron, Y. Dodis, C. Malinaud, and P. Puniya. "Merkle-Damgård Revisited: How to Construct a Hash Function". In: *CRYPTO 2005*. Ed. by V. Shoup. Vol. 3621. LNCS. Springer, Heidelberg, Aug. 2005, pp. 430–448. DOI: 10.1007/11535218_26.

[Cen23] Censys. *Host Search*. Archived version at https://web.archive.org/web/20231108185913/https://search.censys.io/search/report?resource=hosts&q=services.extended_service_name%3A+HTTPS&virtual_hosts=EXCLUDE&field=services.tls.cipher_selecte&num_buckets=50. Accessed on 2023-11-08. Nov. 2023. URL: https://search.censys.io/search/report?resource=hosts&q=services extended_service_name%3A+HTTPS&virtual_hosts=EXCLUDE&field=services.tls.cipher_selecte&num_buckets=50.

[CJ98] F. Chabaud and A. Joux. "Differential Collisions in SHA-0". In: *CRYPTO'98*. Ed. by H. Krawczyk. Vol. 1462. LNCS. Springer, Heidelberg, Aug. 1998, pp. 56–71. DOI: 10.1007/BFb0055720.

[CW77] L. Carter and M. N. Wegman. "Universal Classes of Hash Functions (Extended Abstract)". In: *Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA*. Ed. by J. E. Hopcroft, E. P. Friedman, and M. A. Harrison. ACM, 1977, pp. 106–112. DOI: 10.1145/800105.803400.

[DAM+15] Z. Durumeric, D. Adrian, A. Mirian, M. Bailey, and J. A. Halderman. "A Search Engine Backed by Internet-Wide Scanning". In: *ACM CCS 2015*. Ed. by I. Ray, N. Li, and C. Kruegel. ACM Press, Oct. 2015, pp. 542–553. DOI: 10.1145/2810103.2813703.

[Dam90] I. Damgård. "A Design Principle for Hash Functions". In: *CRYPTO'89*. Ed. by G. Brassard. Vol. 435. LNCS. Springer, Heidelberg, Aug. 1990, pp. 416–427. DOI: 10.1007/0-387-34805-0_39.
[dB94] B. den Boer and A. Bosselaers. "Collisions for the Compressin Function of MD5". In: *EUROCRYPT'93*. Ed. by T. Helleseth. Vol. 765. LNCS. Springer, Heidelberg, May 1994, pp. 293-304. DOI: 10.1007/3-540-48285-7_26.

[DD13] V. Dolmatov and A. Degtyarev. *GOST R 34.11-2012: Hash Function*. RFC 6986. Aug. 2013. DOI: 10.17487/RFC6986.

[DDN+15] N. Datta, A. Dutta, M. Nandi, G. Paul, and L. Zhang. *Building Single-Key Beyond Birthday Bound Message Authentication Code*. Cryptology ePrint Archive, Report 2015/958. https://eprint.iacr.org/2015/958. 2015.

[DDN+17] N. Datta, A. Dutta, M. Nandi, G. Paul, and L. Zhang. "Single Key Variant of PMAC_Plus". In: *IACR Trans. Symm. Cryptol.* 2017.4 (2017), pp. 268-305. ISSN: 2519-173X. DOI: 10.13154/tosc.v2017.i4.268-305.

[DDN+18] N. Datta, A. Dutta, M. Nandi, and G. Paul. "Double-block Hash-then-Sum: A Paradigm for Constructing BBB Secure PRF". In: *IACR Trans. Symm. Cryptol.* 2018.3 (2018), pp. 36-92. ISSN: 2519-173X. DOI: 10.13154/tosc.v2018.i3.36-92.

[Deu85] D. Deutsch. "Quantum theory, the Church-Turing principle and the universal quantum computer". In: *Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences* 400.1818 (1985), pp. 97-117. DOI: 10.1098/rspa.1985.0070.

[DH76] W. Diffie and M. E. Hellman. "New Directions in Cryptography". In: *IEEE Transactions on Information Theory* 22.6 (1976), pp. 644-654. DOI: 10.1109/TIT.1976.1055638.

[DH79] W. Diffie and M. E. Hellman. "Privacy and authentication: An introduction to cryptography". In: *Proceedings of the IEEE* 67.3 (1979), pp. 397-427. DOI: 10.1109/PROC.1979.11256.

[DL05] M. Daum and S. Lucks. *Hash Collisions (The Poisoned Message Attack) "The Story of Alice and her Boss"*. Presented at the rump session of Eurocrypt 2005. 2005. URL: https://www.sos.cs.ru.nl/applications/courses/security2015/md5collisions/index.html.

[DL14] I. Dinur and G. Leurent. "Improved Generic Attacks against Hash-Based MACs and HAIFA". In: *CRYPTO 2014, Part I*. Ed. by J. A. Garay and R. Gennaro. Vol. 8616. LNCS. Springer, Heidelberg, Aug. 2014, pp. 149-168. DOI: 10.1007/978-3-662-44371-2_9.

[DL16] I. Dinur and G. Leurent. "Improved Generic Attacks Against Hash-Based MACs and HAIFA". In: *Algorithmica* (2016), pp. 1-35. ISSN: 1432-0541. DOI: 10.1007/s00453-016-0236-6.

[DL18] S. Duval and G. Leurent. "MDS Matrices with Lightweight Circuits". In: *IACR Trans. Symm. Cryptol.* 2018.2 (2018), pp. 48-78. ISSN: 2519-173X. DOI: 10.13154/tosc.v2018.i2.48-78.

[Dob96] H. Dobbertin. "Cryptanalysis of MD4". In: *FSE'96*. Ed. by D. Gollmann. Vol. 1039. LNCS. Springer, Heidelberg, Feb. 1996, pp. 53-69. DOI: 10.1007/3-540-60865-6_43.

[Dob97] H. Dobbertin. "RIPEMD with Two-Round Compress Function is Not Collision-Free". In: *Journal of Cryptology* 10.1 (Dec. 1997), pp. 51-70. DOI: 10.1007/s001459900019.

[Dol10] V. Dolmatov. *GOST R 34.11-94: Hash Function Algorithm*. RFC 5831. Mar. 2010. DOI: 10.17487/RFC5831.
[DR06] C. De Cannière and C. Rechberger. "Finding SHA-1 Characteristics: General Results and Applications". In: *ASIACRYPT 2006*. Ed. by X. Lai and K. Chen. Vol. 4284. LNCS. Springer, Heidelberg, Dec. 2006, pp. 1–20. DOI: 10.1007/11935230_1.

[DR11] T. Duong and J. Rizzo. *Here come the ⊕ ninjas*. May 2011. URL: https://bugzilla.mozilla.org/attachment.cgi?id=540839.

[EKM+08] T. Eisenbarth, T. Kasper, A. Moradi, C. Paar, M. Salmasizadeh, and M. T. M. Shalmani. "On the Power of Power Analysis in the Real World: A Complete Break of the KeeLoqCode Hopping Scheme". In: *CRYPTO 2008*. Ed. by D. Wagner. Vol. 5157. LNCS. Springer, Heidelberg, Aug. 2008, pp. 203–220. DOI: 10.1007/978-3-540-85174-5_12.

[FLN+20] A. Flórez-Gutiérrez, G. Leurent, M. Naya-Plasencia, L. Perrin, A. Schrottenloher, and F. Sibleyras. "New Results on Gimli: Full-Permutation Distinguishers and Improved Collisions". In: *ASIACRYPT 2020, Part I*. Ed. by S. Moriai and H. Wang. Vol. 12491. LNCS. Springer, Heidelberg, Dec. 2020, pp. 33–63. DOI: 10.1007/978-3-030-64837-4_2.

[FLN+21] A. Flórez-Gutiérrez, G. Leurent, M. Naya-Plasencia, L. Perrin, A. Schrottenloher, and F. Sibleyras. "Internal Symmetries and Linear Properties: Full-permutation Distinguishers and Improved Collisions on Gimli". In: *Journal of Cryptology* 34.4 (Oct. 2021), p. 45. DOI: 10.1007/s00145-021-09413-z.

[FLS+10] N. Ferguson, S. Lucks, B. Schneier, D. Whiting, M. Bellare, T. Kohno, J. Callas, and J. Walker. *The Skein Hash Function Family*. Submission to NIST. 2008/2010. URL: http://skein-hash.info.

[FLS15] T. Fuhr, G. Leurent, and V. Suder. "Collision Attacks Against CAESAR Candidates - Forgery and Key-Recovery Against AEZ and Marble". In: *ASIACRYPT 2015, Part II*. Ed. by T. Iwata and J. H. Cheon. Vol. 9453. LNCS. Springer, Heidelberg, Nov. 2015, pp. 510–532. DOI: 10.1007/978-3-662-48800-3_21.

[FM01] S. R. Fluhrer and D. A. McGrew. "Statistical Analysis of the Alleged RC4 Keystream Generator". In: *FSE 2000*. Ed. by B. Schneier. Vol. 1978. LNCS. Springer, Heidelberg, Apr. 2001, pp. 19–30. DOI: 10.1007/3-540-44706-7_2.

[FMS01] S. R. Fluhrer, I. Mantin, and A. Shamir. "Weaknesses in the Key Scheduling Algorithm of RC4". In: *SAC 2001*. Ed. by S. Vaudenay and A. M. Youssef. Vol. 2259. LNCS. Springer, Heidelberg, Aug. 2001, pp. 1–24. DOI: 10.1007/3-540-45537-X_1.

[FO90] P. Flajolet and A. M. Odlyzko. "Random Mapping Statistics". In: *EURO-CRYPT'89*. Ed. by J.-J. Quisquater and J. Vandewalle. Vol. 434. LNCS. Springer, Heidelberg, Apr. 1990, pp. 329–354. DOI: 10.1007/3-540-46885-4_34.

[FS09] P. Flajolet and R. Sedgewick. *Analytic Combinatorics*. Cambridge University Press, 2009. ISBN: 978-0-521-89806-5. URL: https://ac.cs.princeton.edu/home/.

[FSK11] N. Ferguson, B. Schneier, and T. Kohno. *Cryptography engineering: design principles and practical applications*. John Wiley & Sons, 2011. ISBN: 9780470474242. DOI: 10.1002/9781118722367.
[GHK+23] H. Gilbert, R. Heim Boissier, L. Khati, and Y. Rotella. "Generic Attack on Duplex-Based AEAD Modes Using Random Function Statistics". In: EUROCRYPT 2023, Part IV. Ed. by C. Hazay and M. Stam. Vol. 14007. LNCS. Springer, Heidelberg, Apr. 2023, pp. 348-378. DOI: 10.1007/978-3-031-30634-1_12.

[GIS06] M. Gebhardt, G. Illies, and W. Schindler. "A Note on the Practical Value of Single Hash Collisions for Special File Formats". In: Sicherheit 2006: Sicherheit - Schutz und Zuverlässigkeit, Beiträge der 3. Jahrestagung des Fachbereichs Sicherheit der Gesellschaft für Informatik e.v. (GI), 20.-22. Februar 2006 in Magdeburg. Ed. by J. Dittmann. Vol. P-77. LNI. GI, 2006, pp. 333-344. URL: https://dl.gi.de/handle/20.500.12116/24792.

[GK08] P. Gauravaram and J. Kelsey. "Linear-XOR and Additive Checksums Don't Protect Damgård-Merkle Hashes from Generic Attacks". In: CT-RSA 2008. Ed. by T. Malkin. Vol. 4964. LNCS. Springer, Heidelberg, Apr. 2008, pp. 36-51. DOI: 10.1007/978-3-540-79263-5_3.

[GKM+08] F. D. Garcia, G. de Koning Gans, R. Muijrers, P. van Rossum, R. Verdult, R. Wichers Schreur, and B. Jacobs. "Dismantling MIFARE Classic". In: ESORICS 2008. Ed. by S. Jajodia and J. López. Vol. 5283. LNCS. Springer, Heidelberg, Oct. 2008, pp. 97-114. DOI: 10.1007/978-3-540-88313-5_7.

[GKS13] F. Giesen, F. Kohlar, and D. Stebila. "On the security of TLS renegotiation". In: ACM CCS 2013. Ed. by A.-R. Sadeghi, V. D. Gligor, and M. Yung. ACM Press, Nov. 2013, pp. 387-398. DOI: 10.1145/2508859.2516694.

[GLS+14] V. Grosso, G. Leurent, F.-X. Standaert, K. Varici, F. Durvaux, L. Gaspar, and S. Kerckhof. SCREAM & iSCREAM: Side-Channel Resistant Authenticated Encryption with Masking. Submitted to the CAESAR competition. Mar. 2014. URL: http://perso.uclouvain.be/fstandae/SCREAM/.

[GLS+15] V. Grosso, G. Leurent, F.-X. Standaert, and K. Varici. "LS-Designs: Bitslice Encryption for Efficient Masked Software Implementations". In: FSE 2014. Ed. by C. Cid and C. Rechberger. Vol. 8540. LNCS. Springer, Heidelberg, Mar. 2015, pp. 18-37. DOI: 10.1007/978-3-662-46706-0_2.

[GM84] S. Goldwasser and S. Micali. "Probabilistic Encryption". In: Journal of Computer and System Sciences 28.2 (1984), pp. 270-299. DOI: 10.1016/0022-0000(84)90070-9.

[Gol97] J. D. Golic. "Cryptanalysis of Alleged A5 Stream Cipher". In: EUROCRYPT'97. Ed. by W. Fumy. Vol. 1233. LNCS. Springer, Heidelberg, May 1997, pp. 239-255. DOI: 10.1007/3-540-69053-0_17.

[GPS+14] J. Guo, T. Peyrin, Y. Sasaki, and L. Wang. "Updates on Generic Attacks against HMAC and NMAC". In: CRYPTO 2014, Part I. Ed. by J. A. Garay and R. Gennaro. Vol. 8616. LNCS. Springer, Heidelberg, Aug. 2014, pp. 131-148. DOI: 10.1007/978-3-662-44371-2_8.

[GPv15] C. Garman, K. G. Paterson, and T. van der Merwe. "Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS". In: USENIX Security 2015. Ed. by J. Jung and T. Holz. USENIX Association, Aug. 2015, pp. 113-128. URL: https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-garman.pdf.

[Gro96] L. K. Grover. "A Fast Quantum Mechanical Algorithm for Database Search". In: 28th ACM STOC. ACM Press, May 1996, pp. 212-219. DOI: 10.1145/237814.237866.
[HBK+11] R. Holz, L. Braun, N. Kammenhuber, and G. Carle. "The SSL landscape: a thorough analysis of the x. 509 PKI using active and passive measurements". In: *Proceedings of the 2011 ACM SIGCOMM conference on Internet measurement conference*. 2011, pp. 427-444. DOI: 10.1145/2068816.2068856.

[HKR17] V. T. Hoang, T. Krovetz, and P. Rogaway. *AEZ v5: Authenticated Encryption by Enciphering*. Submission to the CAESAR competition. Mar. 2017. URL: https://competitions.cr.yp.to/round3/aezv5.pdf.

[HP08] H. Handschuh and B. Preneel. "Key-Recovery Attacks on Universal Hash Function Based MAC Algorithms". In: *CRYPTO 2008*. Ed. by D. Wagner. Vol. 5157. LNCS. Springer, Heidelberg, Aug. 2008, pp. 144-161. DOI: 10.1007/978-3-540-85174-5_9.

[HRR+15] V. T. Hoang, R. Reyhanitabar, P. Rogaway, and D. Vizár. "Online Authenticated-Encryption and its Nonce-Reuse Misuse-Resistance". In: *CRYPTO 2015, Part I*. Ed. by R. Gennaro and M. J. B. Robshaw. Vol. 9215. LNCS. Springer, Heidelberg, Aug. 2015, pp. 493-517. DOI: 10.1007/978-3-662-47989-6_24.

[HS08] J. J. Hoch and A. Shamir. "On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak". In: *ICALP 2008, Part II*. Ed. by L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz. Vol. 5126. LNCS. Springer, Heidelberg, July 2008, pp. 616-630. DOI: 10.1007/978-3-540-70583-3_50.

[IIM+19] A. Inoue, T. Iwata, K. Minematsu, and B. Poettering. "Cryptanalysis of OCB2: Attacks on Authenticity and Confidentiality". In: *CRYPTO 2019, Part I*. Ed. by A. Boldyreva and D. Micciancio. Vol. 11692. LNCS. Springer, Heidelberg, Aug. 2019, pp. 3-31. DOI: 10.1007/978-3-030-26948-7_1.

[IKD+08] S. Indesteege, N. Keller, O. Dunkelman, E. Biham, and B. Preneel. "A Practical Attack on KeeLoq". In: *EUROCRYPT 2008*. Ed. by N. P. Smart. Vol. 4965. LNCS. Springer, Heidelberg, Apr. 2008, pp. 1-18. DOI: 10.1007/978-3-540-78967-3_1.

[IM16] T. Iwata and K. Minematsu. "Stronger Security Variants of GCM-SIV". In: *IACR Trans. Symm. Cryptol*. 2016.1 (2016), pp. 134-157. ISSN: 2519-173X. DOI: 10.13154/tosc.v2016.i1.134-157.

[IMP+17] T. Iwata, K. Minematsu, T. Peyrin, and Y. Seurin. "ZMAC: A Fast Tweakable Block Cipher Mode for Highly Secure Message Authentication". In: *CRYPTO 2017, Part III*. Ed. by J. Katz and H. Shacham. Vol. 10403. LNCS. Springer, Heidelberg, Aug. 2017, pp. 34-65. DOI: 10.1007/978-3-319-63697-9_2.

[IMV16] T. Iwata, B. Mennink, and D. Vizár. *CENC is Optimally Secure*. Cryptology ePrint Archive, Report 2016/1087. https://eprint.iacr.org/2016/1087. 2016.

[ISO14] *On the Assessment of Cryptographic Techniques and Key Lengths, 4th edition*. ISO/IEC JTC 1/SC 27 Standing Document 12. Archived at https://web.archive.org/web/20231120102344if_/_https://docplayer.net/storage/25/6483684/1700477932/FFAaPq4RA7y5QPn7TqVbew/6483684.pdf. May 2014.

[ISO19] *On the Assessment of Cryptographic Techniques and Key Lengths, 5th edition*. ISO/IEC JTC 1/SC 27 Standing Document 12. May 2019. URL: https://committee.iso.org/files/live/sites/jtc1sc27/files/resources/sc27-sd12-assessment-of-cryptographic-techniques-and-key-lengths-data.zip.
[Iwa06] T. Iwata. "New Blockcipher Modes of Operation with Beyond the Birthday Bound Security". In: *FSE 2006*. Ed. by M. J. B. Robshaw. Vol. 4047. LNCS. Springer, Heidelberg, Mar. 2006, pp. 310-327. DOI: 10.1007/11799313_20.

[JJV02] É. Jaulmes, A. Joux, and F. Valette. "On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit: A New Construction". In: *FSE 2002*. Ed. by J. Daemen and V. Rijmen. Vol. 2365. LNCS. Springer, Heidelberg, Feb. 2002, pp. 237-251. DOI: 10.1007/3-540-45661-9_19.

[JKS+12] T. Jager, F. Kohlar, S. Schäge, and J. Schwenk. "On the Security of TLS-DHE in the Standard Model". In: *CRYPTO 2012*. Ed. by R. Safavi-Naini and R. Canetti. Vol. 7417. LNCS. Springer, Heidelberg, Aug. 2012, pp. 273-293. DOI: 10.1007/978-3-642-32009-5_17.

[Jou04] A. Joux. "Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions". In: *CRYPTO 2004*. Ed. by M. Franklin. Vol. 3152. LNCS. Springer, Heidelberg, Aug. 2004, pp. 306-316. DOI: 10.1007/978-3-540-28628-8_19.

[Jou09] A. Joux. *Algorithmic Cryptanalysis*. Chapman & Hall / CRC Press, June 2009. ISBN: 9781420070026.

[JP07] A. Joux and T. Peyrin. "Hash Functions and the (Amplified) Boomerang Attack". In: *CRYPTO 2007*. Ed. by A. Menezes. Vol. 4622. LNCS. Springer, Heidelberg, Aug. 2007, pp. 244-263. DOI: 10.1007/978-3-540-74143-5_14.

[KBP+06] J. Kim, A. Biryukov, B. Preneel, and S. Hong. "On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1 (Extended Abstract)". In: *SCN 06*. Ed. by R. D. Prisco and M. Yung. Vol. 4116. LNCS. Springer, Heidelberg, Sept. 2006, pp. 242-256. DOI: 10.1007/11832072_17.

[Kel02] J. Kelsey. "Compression and Information Leakage of Plaintext". In: *FSE 2002*. Ed. by J. Daemen and V. Rijmen. Vol. 2365. LNCS. Springer, Heidelberg, Feb. 2002, pp. 263-276. DOI: 10.1007/3-540-45661-9_21.

[Ker83] A. Kerckhoffs. "La cryptographie militaire". In: *Journal des sciences mil- itaires* IX (Jan. 1883), pp. 5-38. URL: https://www.petitcolas.net/ kerckhoffs/crypto_militaire_1_b.pdf.

[KK06] J. Kelsey and T. Kohno. "Herding Hash Functions and the Nostradamus Attack". In: *EUROCRYPT 2006*. Ed. by S. Vaudenay. Vol. 4004. LNCS. Springer, Heidelberg, May 2006, pp. 183-200. DOI: 10.1007/11761679_12.

[Kli06] V. Klima. *Tunnels in Hash Functions: MD5 Collisions Within a Minute*. Cryptology ePrint Archive, Report 2006/105. https://eprint.iacr.org/ 2006/105. 2006.

[KLL+16a] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia. "Breaking Symmetric Cryptosystems Using Quantum Period Finding". In: *CRYPTO 2016, Part II*. Ed. by M. Robshaw and J. Katz. Vol. 9815. LNCS. Springer, Heidelberg, Aug. 2016, pp. 207-237. DOI: 10.1007/978-3-662-53008-5_8.

[KLL+16b] M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia. "Quantum Differential and Linear Cryptanalysis". In: *IACR Trans. Symm. Cryptol.* 2016.1 (2016), pp. 71-94. ISSN: 2519-173X. DOI: 10.13154/tosc.v2016.i1. 71-94.

[KLL20] S. Kim, B. Lee, and J. Lee. "Tight Security Bounds for Double-Block Hash-then-Sum MACs". In: *EUROCRYPT 2020, Part I*. Ed. by A. Canteaut and Y. Ishai. Vol. 12105. LNCS. Springer, Heidelberg, May 2020, pp. 435-465. DOI: 10.1007/978-3-030-45721-1_16.
[KM10] H. Kuwakado and M. Morii. "Quantum distinguisher between the 3-round Feistel cipher and the random permutation". In: *IEEE International Symposium on Information Theory, ISIT 2010*. IEEE, 2010, pp. 2682-2685. DOI: 10.1109/ISIT.2010.5513654.

[KM12] H. Kuwakado and M. Morii. "Security on the quantum-type Even-Mansour cipher". In: *Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012*. IEEE, 2012, pp. 312-316. URL: https://ieeexplore.ieee.org/document/6400943/.

[Kob87] N. Koblitz. "Elliptic Curve Cryptosystems". In: *Mathematics of Computation* 48.177 (1987), pp. 203-209. ISSN: 00255718, 10886842. URL: http://www.jstor.org/stable/2007884 (visited on 11/13/2023).

[KPS15] P. Karpman, T. Peyrin, and M. Stevens. "Practical Free-Start Collision Attacks on 76-step SHA-1". In: *CRYPTO 2015, Part I*. Ed. by R. Gennaro and M. J. B. Robshaw. Vol. 9215. LNCS. Springer, Heidelberg, Aug. 2015, pp. 623-642. DOI: 10.1007/978-3-662-47989-6_30.

[KPW13] H. Krawczyk, K. G. Paterson, and H. Wee. "On the Security of the TLS Protocol: A Systematic Analysis". In: *CRYPTO 2013, Part I*. Ed. by R. Canetti and J. A. Garay. Vol. 8042. LNCS. Springer, Heidelberg, Aug. 2013, pp. 429-448. DOI: 10.1007/978-3-642-40041-4_24.

[KR11] T. Krovetz and P. Rogaway. "The Software Performance of Authenticated-Encryption Modes". In: *FSE 2011*. Ed. by A. Joux. Vol. 6733. LNCS. Springer, Heidelberg, Feb. 2011, pp. 306-327. DOI: 10.1007/978-3-642-21702-9_18.

[KR14] T. Krovetz and P. Rogaway. *The OCB Authenticated-Encryption Algorithm*. RFC 7253. May 2014. DOI: 10.17487/RFC7253.

[Kra03] H. Krawczyk. "SIGMA: The "SIGn-and-MAc" Approach to Authenticated Diffie-Hellman and Its Use in the IKE Protocols". In: *CRYPTO 2003*. Ed. by D. Boneh. Vol. 2729. LNCS. Springer, Heidelberg, Aug. 2003, pp. 400-425. DOI: 10.1007/978-3-540-45146-4_24.

[KS05] J. Kelsey and B. Schneier. "Second Preimages on n-Bit Hash Functions for Much Less than 2n Work". In: *EUROCRYPT 2005*. Ed. by R. Cramer. Vol. 3494. LNCS. Springer, Heidelberg, May 2005, pp. 474-490. DOI: 10.1007/11426639_28.

[LBF08] G. Leurent, C. Bouillaguet, and P.-A. Fouque. *SIMD Is a Message Digest*. Submitted to the SHA-3 competition. 2008. URL: https://who.rocq.inria.fr/Gaetan.Leurent/simd.html.

[Leu07] G. Leurent. "Message Freedom in MD4 and MD5 Collisions: Application to APOP". In: *FSE 2007*. Ed. by A. Biryukov. Vol. 4593. LNCS. Springer, Heidelberg, Mar. 2007, pp. 309-328. DOI: 10.1007/978-3-540-74619-5_20.

[Leu08a] G. Leurent. "MD4 is Not One-Way". In: *FSE 2008*. Ed. by K. Nyberg. Vol. 5086. LNCS. Springer, Heidelberg, Feb. 2008, pp. 412-428. DOI: 10.1007/978-3-540-71039-4_26.

[Leu12] G. Leurent. "Analysis of Differential Attacks in ARX Constructions". In: *ASIACRYPT 2012*. Ed. by X. Wang and K. Sako. Vol. 7658. LNCS. Springer, Heidelberg, Dec. 2012, pp. 226-243. DOI: 10.1007/978-3-642-34961-4_15.

[Leu13] G. Leurent. "Construction of Differential Characteristics in ARX Designs Application to Skein". In: *CRYPTO 2013, Part I*. Ed. by R. Canetti and J. A. Garay. Vol. 8042. LNCS. Springer, Heidelberg, Aug. 2013, pp. 241-258. DOI: 10.1007/978-3-642-40041-4_14.
[Leu16b] G. Leurent. "Improved Differential-Linear Cryptanalysis of 7-Round Chaskey with Partitioning". In: *EUROCRYPT 2016, Part I*. Ed. by M. Fischlin and J.-S. Coron. Vol. 9665. LNCS. Springer, Heidelberg, May 2016, pp. 344–371. DOI: 10.1007/978-3-662-49890-3_14.

[LKS+06] C. Lee, J. Kim, J. Sung, S. Hong, and S. Lee. "Forgery and Key Recovery Attacks on PMAC and Mitchell's TMAC Variant". In: *ACISP 06*. Ed. by L. M. Batten and R. Safavi-Naini. Vol. 4058. LNCS. Springer, Heidelberg, July 2006, pp. 421–431. DOI: 10.1007/11780656_35.

[LMP+23] G. Leurent, B. Mennink, K. Pietrzak, and V. Rijmen. *Analysis of MinRoot: Public report*. Tech. rep. Ethereum Foundation, Sept. 2023. URL: https://crypto.ethereum.org/events/minrootanalysis2023.pdf.

[LN17a] E. List and M. Nandi. "Revisiting Full-PRF-Secure PMAC and Using It for Beyond-Birthday Authenticated Encryption". In: *CT-RSA 2017*. Ed. by H. Handschuh. Vol. 10159. LNCS. Springer, Heidelberg, Feb. 2017, pp. 258–274. DOI: 10.1007/978-3-319-52153-4_15.

[LN17b] E. List and M. Nandi. "ZMAC<sup>+</sup> – An Efficient Variable-output-length Variant of ZMAC". In: *IACR Trans. Symm. Cryptol.* 2017.4 (2017), pp. 306–325. ISSN: 2519-173X. DOI: 10.13154/tosc.v2017.i4.306-325.

[LNS18] G. Leurent, M. Nandi, and F. Sibleyras. "Generic Attacks Against Beyond-Birthday-Bound MACs". In: *CRYPTO 2018, Part I*. Ed. by H. Shacham and A. Boldyreva. Vol. 10991. LNCS. Springer, Heidelberg, Aug. 2018, pp. 306–336. DOI: 10.1007/978-3-319-96884-1_11.

[LP18] A. Luykx and B. Preneel. "Optimal Forgeries Against Polynomial-Based MACs and GCM". In: *EUROCRYPT 2018, Part I*. Ed. by J. B. Nielsen and V. Rijmen. Vol. 10820. LNCS. Springer, Heidelberg, Apr. 2018, pp. 445–467. DOI: 10.1007/978-3-319-78381-9_17.

[LP19] G. Leurent and T. Peyrin. "From Collisions to Chosen-Prefix Collisions Application to Full SHA-1". In: *EUROCRYPT 2019, Part III*. Ed. by Y. Ishai and V. Rijmen. Vol. 11478. LNCS. Springer, Heidelberg, May 2019, pp. 527–555. DOI: 10.1007/978-3-030-17659-4_18.

[LP20] G. Leurent and T. Peyrin. "SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust". In: *USENIX Security 2020*. Ed. by S. Capkun and F. Roesner. USENIX Association, Aug. 2020, pp. 1839–1856. URL: https://www.usenix.org/system/files/sec20-leurent.pdf.

[LP21] G. Leurent and C. Pernot. "New Representations of the AES Key Schedule". In: *EUROCRYPT 2021, Part I*. Ed. by A. Canteaut and F.-X. Standaert. Vol. 12696. LNCS. Springer, Heidelberg, Oct. 2021, pp. 54–84. DOI: 10.1007/978-3-030-77870-5_3.

[LPR+07] M. Lamberger, N. Pramstaller, C. Rechberger, and V. Rijmen. "Second Preimages for SMASH". In: *CT-RSA 2007*. Ed. by M. Abe. Vol. 4377. LNCS. Springer, Heidelberg, Feb. 2007, pp. 101–111. DOI: 10.1007/11967668_7.

[LPS21] G. Leurent, C. Pernot, and A. Schrottenloher. "Clustering Effect in Simon and Simeck". In: *ASIACRYPT 2021, Part I*. Ed. by M. Tibouchi and H. Wang. Vol. 13090. LNCS. Springer, Heidelberg, Dec. 2021, pp. 272–302. DOI: 10.1007/978-3-030-92062-3_10.
[LPW13] G. Leurent, T. Peyrin, and L. Wang. "New Generic Attacks against Hash-Based MACs". In: *ASIACRYPT 2013, Part II*. Ed. by K. Sako and P. Sarkar. Vol. 8270. LNCS. Springer, Heidelberg, Dec. 2013, pp. 1-20. DOI: 10.1007/978-3-642-42045-0_1.

[LS18] G. Leurent and F. Sibleyras. "The Missing Difference Problem, and Its Applications to Counter Mode Encryption". In: *EUROCRYPT 2018, Part II*. Ed. by J. B. Nielsen and V. Rijmen. Vol. 10821. LNCS. Springer, Heidelberg, Apr. 2018, pp. 745-770. DOI: 10.1007/978-3-319-78375-8_24.

[LW05] A. K. Lenstra and B. de Weger. "On the Possibility of Constructing Meaningful Hash Collisions for Public Keys". In: *ACISP 05*. Ed. by C. Boyd and J. M. G. Nieto. Vol. 3574. LNCS. Springer, Heidelberg, July 2005, pp. 267-279. DOI: 10.1007/11506157_23.

[LW15] G. Leurent and L. Wang. "The Sum Can Be Weaker Than Each Part". In: *EUROCRYPT 2015, Part I*. Ed. by E. Oswald and M. Fischlin. Vol. 9056. LNCS. Springer, Heidelberg, Apr. 2015, pp. 345-367. DOI: 10.1007/978-3-662-46800-5_14.

[Mar09] M. Marlinspike. "More tricks for defeating SSL in practice". In: *Black Hat USA* (2009). URL: https://www.blackhat.com/presentations/bh-usa-09/MARLINSPIKE/BHUSA09-Marlinspike-DefeatSSL-SLIDES.pdf.

[Mat94] M. Matsui. "Linear Cryptanalysis Method for DES Cipher". In: *EUROCRYPT'93*. Ed. by T. Helleseth. Vol. 765. LNCS. Springer, Heidelberg, May 1994, pp. 386-397. DOI: 10.1007/3-540-48285-7_33.

[McE78] R. J. McEliece. "A Public-Key Cryptosystem Based On Algebraic Coding Theory". In: *Deep Space Network Progress Report* 44 (Jan. 1978), pp. 114-116. URL: https://ipnpr.jpl.nasa.gov/progress_report2/42-44/44N.PDF.

[McG12] D. McGrew. *Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes*. Cryptology ePrint Archive, Report 2012/623. Accepted to FSE 2013. Nov. 2012. URL: https://eprint.iacr.org/2012/623.

[MDK14] B. Möller, T. Duong, and K. Kotowicz. *This POODLE Bites: Exploiting The SSL 3.0 Fallback*. 2014. URL: https://www.openssl.org/~bodo/ssl-poodle.pdf.

[Mer90] R. C. Merkle. "One Way Hash Functions and DES". In: *CRYPTO'89*. Ed. by G. Brassard. Vol. 435. LNCS. Springer, Heidelberg, Aug. 1990, pp. 428-446. DOI: 10.1007/0-387-34805-0_40.

[Mil86] V. S. Miller. "Use of Elliptic Curves in Cryptography". In: *CRYPTO'85*. Ed. by H. C. Williams. Vol. 218. LNCS. Springer, Heidelberg, Aug. 1986, pp. 417-426. DOI: 10.1007/3-540-39799-X_31.

[MLM+14] K. Minematsu, S. Lucks, H. Morita, and T. Iwata. "Attacks and Security Proofs of EAX-Prime". In: *FSE 2013*. Ed. by S. Moriai. Vol. 8424. LNCS. Springer, Heidelberg, Mar. 2014, pp. 327-347. DOI: 10.1007/978-3-662-43933-3_17.

[Moz23] Mozilla. *Measurement Dashboard*. Accessed on 2023-11-08. Nov. 2023. URL: https://telemetry.mozilla.org/new-pipeline/dist.html#!measure=SSL_CIPHER_SUITE_FULL&max_channel_version=nightly%252F121&min_channel_version=nightly%252F121.
[MRS15] F. Mendel, V. Rijmen, and M. Schläffer. "Collision Attack on 5 Rounds of Grøstl". In: *FSE 2014*. Ed. by C. Cid and C. Rechberger. Vol. 8540. LNCS. Springer, Heidelberg, Mar. 2015, pp. 509–521. DOI: 10.1007/978-3-662-46706-0_26.

[MS02] I. Mantin and A. Shamir. "A Practical Attack on Broadcast RC4". In: *FSE 2001*. Ed. by M. Matsui. Vol. 2355. LNCS. Springer, Heidelberg, Apr. 2002, pp. 152–164. DOI: 10.1007/3-540-45473-X_13.

[MV04] D. A. McGrew and J. Viega. "The Security and Performance of the Galois/Counter Mode (GCM) of Operation". In: *INDOCRYPT 2004*. Ed. by A. Canteaut and K. Viswanathan. Vol. 3348. LNCS. Springer, Heidelberg, Dec. 2004, pp. 343–355. DOI: 10.1007/978-3-540-30556-9_27.

[Nai15] Y. Naito. "Full PRF-Secure Message Authentication Code Based on Tweakable Block Cipher". In: *ProvSec 2015*. Ed. by M. H. Au and A. Miyaji. Vol. 9451. LNCS. Springer, Heidelberg, Nov. 2015, pp. 167–182. DOI: 10.1007/978-3-319-26059-4_9.

[Nai17] Y. Naito. "Blockcipher-Based MACs: Beyond the Birthday Bound Without Message Length". In: *ASIACRYPT 2017, Part III*. Ed. by T. Takagi and T. Peyrin. Vol. 10626. LNCS. Springer, Heidelberg, Dec. 2017, pp. 446–470. DOI: 10.1007/978-3-319-70700-6_16.

[Nai18] Y. Naito. "Improved Security Bound of LightMAC_Plus and Its Single-Key Variant". In: *CT-RSA 2018*. Ed. by N. P. Smart. Vol. 10808. LNCS. Springer, Heidelberg, Apr. 2018, pp. 300–318. DOI: 10.1007/978-3-319-76953-0_16.

[NBS80] National Bureau of Standards. *DES Modes of Operation*. FIPS 81. Dec. 1980. DOI: 10.6028/NBS.FIPS.81.

[NBS85] National Bureau of Standards. *Computer Data Authentication*. FIPS 113. May 1985. DOI: 10.6028/NBS.FIPS.113.

[NIS01] M. Dworkin. *Recommendation for Block Cipher Modes of Operation. Methods and Techniques*. NIST Special Publication 800-38A. National Institute for Standards and Technology, Dec. 2001. DOI: 10.6028/NIST.SP.800-38A.

[NIS12] W. C. Barker and E. Barker. *Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher*. NIST Special Publication 800-67. Revision 1. National Institute for Standards and Technology, Jan. 2012. DOI: 10.6028/NIST.SP.800-67r1.

[NIS17] E. Barker and N. Mouha. *Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher*. NIST Special Publication 800-67. Revision 2. National Institute for Standards and Technology, Nov. 2017. DOI: 10.6028/NIST.SP.800-67r2.

[NIS19] E. Barker and A. Roginsky. *Transitioning the Use of Cryptographic Algorithms and Key Lengths*. NIST Special Publication 800-131A. Revision 2. National Institute for Standards and Technology, Mar. 2019. DOI: 10.6028/NIST.SP.800-131Ar2.

[NKB06] C. Namprempre, T. Kohno, and M. Bellare. *The Secure Shell (SSH) Transport Layer Encryption Modes*. RFC 4344. Jan. 2006. DOI: 10.17487/RFC4344.

[PC15] G. Procter and C. Cid. "On Weak Keys and Forgery Attacks Against Polynomial-Based MAC Schemes". In: *Journal of Cryptology* 28.4 (Oct. 2015), pp. 769–795. DOI: 10.1007/s00145-014-9178-9.

[Pey07] T. Peyrin. "Cryptanalysis of Grindahl". In: *ASIACRYPT 2007*. Ed. by K. Kurosawa. Vol. 4833. LNCS. Springer, Heidelberg, Dec. 2007, pp. 551–567. DOI: 10.1007/978-3-540-76900-2_34.
[Pol75] J. M. Pollard. "A Monte Carlo method for factorization". In: *BIT Numerical Mathematics* 15.3 (Sept. 1975), pp. 331-334. ISSN: 1572-9125. DOI: 10.1007/BF01933667.

[PR00] E. Petrank and C. Rackoff. "CBC MAC for Real-Time Data Sources". In: *Journal of Cryptology* 13.3 (June 2000), pp. 315-338. DOI: 10.1007/s001450010009.

[Pv95] B. Preneel and P. C. van Oorschot. "MDx-MAC and Building Fast MACs from Hash Functions". In: *CRYPTO'95*. Ed. by D. Coppersmith. Vol. 963. LNCS. Springer, Heidelberg, Aug. 1995, pp. 1-14. DOI: 10.1007/3-540-44750-4_1.

[Pv96] B. Preneel and P. C. van Oorschot. "On the Security of Two MAC Algorithms". In: *EUROCRYPT'96*. Ed. by U. M. Maurer. Vol. 1070. LNCS. Springer, Heidelberg, May 1996, pp. 19-32. DOI: 10.1007/3-540-68339-9_3.

[PW14] T. Peyrin and L. Wang. "Generic Universal Forgery Attack on Iterative Hash-Based MACs". In: *EUROCRYPT 2014*. Ed. by P. Q. Nguyen and E. Oswald. Vol. 8441. LNCS. Springer, Heidelberg, May 2014, pp. 147-164. DOI: 10.1007/978-3-642-55220-5_9.

[RD12] J. Rizzo and T. Duong. "The CRIME attack". In: *EKOparty Security Conference*. Vol. 2012. 2012. URL: https://docs.google.com/presentation/d/11eBmGiHbYcHR9gL5nDyZChu_-1Ca2GizeuOfaLU2HOU/edit.

[Reg05] O. Regev. "On lattices, learning with errors, random linear codes, and cryptography". In: *37th ACM STOC*. Ed. by H. N. Gabow and R. Fagin. ACM Press, May 2005, pp. 84-93. DOI: 10.1145/1060590.1060603.

[RFC1321] R. L. Rivest. *The MD5 Message-Digest Algorithm*. RFC 1321. Apr. 1992. DOI: 10.17487/RFC1321.

[RFC2246] C. Allen and T. Dierks. *The TLS Protocol Version 1.0*. RFC 2246. Jan. 1999. DOI: 10.17487/RFC2246.

[RFC4270] P. E. Hoffman and B. Schneier. *Attacks on Cryptographic Hashes in Internet Protocols*. RFC 4270. Dec. 2005. DOI: 10.17487/RFC4270.

[RFC4880] H. Finney, L. Donnerhacke, J. Callas, R. L. Thayer, and D. Shaw. *OpenPGP Message Format*. RFC 4880. Nov. 2007. DOI: 10.17487/RFC4880.

[RFC4894] P. E. Hoffman. *Use of Hash Algorithms in Internet Key Exchange (IKE) and IPsec*. RFC 4894. May 2007. DOI: 10.17487/RFC4894.

[RFC8996] K. Moriarty and S. Farrell. *Deprecating TLS 1.0 and TLS 1.1*. RFC 8996. Mar. 2021. DOI: 10.17487/RFC8996.

[RFC9155] L. Velvindron, K. Moriarty, and A. Ghedini. *Deprecating MD5 and SHA-1 Signature Hashes in TLS 1.2 and DTLS 1.2*. RFC 9155. Dec. 2021. DOI: 10.17487/RFC9155.

[Riv91] R. L. Rivest. "The MD4 Message Digest Algorithm". In: *CRYPTO'90*. Ed. by A. J. Menezes and S. A. Vanstone. Vol. 537. LNCS. Springer, Heidelberg, Aug. 1991, pp. 303-311. DOI: 10.1007/3-540-38424-3_22.

[Rog04] P. Rogaway. "Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC". In: *ASIACRYPT 2004*. Ed. by P. J. Lee. Vol. 3329. LNCS. Springer, Heidelberg, Dec. 2004, pp. 16-31. DOI: 10.1007/978-3-540-30539-2_2.
[Rog11] P. Rogaway. *Evaluation of Some Blockcipher Modes of Operation*. Tech. rep. CRYPREC, Feb. 2011. URL: https://web.cs.ucdavis.edu/~rogaway/papers/modes.pdf.

[RR08] C. Rechberger and V. Rijmen. "New Results on NMAC/HMAC when Instantiated with Popular Hash Functions". In: *J. Univers. Comput. Sci.* 14.3 (2008), pp. 347–376. DOI: 10.3217/JUCS-014-03-0347.

[RSA78] R. L. Rivest, A. Shamir, and L. M. Adleman. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". In: *Communications of the Association for Computing Machinery* 21.2 (Feb. 1978), pp. 120–126. DOI: 10.1145/359340.359342.

[Saa12] M.-J. O. Saarinen. "Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes". In: *FSE 2012*. Ed. by A. Canteaut. Vol. 7549. LNCS. Springer, Heidelberg, Mar. 2012, pp. 216–225. DOI: 10.1007/978-3-642-34047-5_13.

[SBK+17] M. Stevens, E. Bursztein, P. Karpman, A. Albertini, and Y. Markov. "The First Collision for Full SHA-1". In: *CRYPTO 2017, Part I*. Ed. by J. Katz and H. Shacham. Vol. 10401. LNCS. Springer, Heidelberg, Aug. 2017, pp. 570–596. DOI: 10.1007/978-3-319-63688-7_19.

[SHA1] National Institute for Standards and Technology. *Secure Hash Standard*. FIPS 180-1. Apr. 1995. DOI: 10.6028/NIST.FIPS.180-1.

[SHA2] National Institute for Standards and Technology. *Secure Hash Standard*. FIPS 180-2. Aug. 2002. URL: https://csrc.nist.gov/files/pubs/fips/180-2/final/docs/fips180-2.pdf.

[SHA3] National Institute for Standards and Technology. *SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions*. FIPS 202. Aug. 2015. DOI: 10.6028/NIST.FIPS.202.

[Sha49] C. E. Shannon. "Communication theory of secrecy systems". In: *Bell Systems Technical Journal* 28.4 (1949), pp. 656–715. DOI: 10.1002/j.1538-7305.1949.tb00928.x.

[Sho94] P. W. Shor. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring". In: *35th FOCS*. IEEE Computer Society Press, Nov. 1994, pp. 124–134. DOI: 10.1109/SFCS.1994.365700.

[Sho96] V. Shoup. "On Fast and Provably Secure Message Authentication Based on Universal Hashing". In: *CRYPTO'96*. Ed. by N. Koblitz. Vol. 1109. LNCS. Springer, Heidelberg, Aug. 1996, pp. 313–328. DOI: 10.1007/3-540-68697-5_24.

[Sho97] P. W. Shor. "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". In: *SIAM J. Comput.* 26.5 (1997), pp. 1484–1509. DOI: 10.1137/S0097539795293172.

[Sim97] D. R. Simon. "On the Power of Quantum Computation". In: *SIAM J. Comput.* 26.5 (1997), pp. 1474–1483. DOI: 10.1137/S0097539796298637.

[SLW07] M. Stevens, A. K. Lenstra, and B. de Weger. "Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities". In: *EURO-Crypt 2007*. Ed. by M. Naor. Vol. 4515. LNCS. Springer, Heidelberg, May 2007, pp. 1–22. DOI: 10.1007/978-3-540-72540-4_1.
[SSA+09] M. Stevens, A. Sotirov, J. Appelbaum, A. K. Lenstra, D. Molnar, D. A. Osvik, and B. de Weger. "Short Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA Certificate". In: CRYPTO 2009. Ed. by S. Halevi. Vol. 5677. LNCS. Springer, Heidelberg, Aug. 2009, pp. 55–69. DOI: 10.1007/978-3-642-03356-8_4.

[Sta22a] Statista. Data volume of global consumer IP traffic from 2017 to 2022. Accessed on 2023-11-21. 2022. URL: https://www.statista.com/statistics/267202/global-data-volume-of-consumer-ip-traffic/.

[Sta22b] Statista. Total installed based of data storage capacity in the global datasphere from 2020 to 2025. Accessed on 2023-11-21. 2022. URL: https://www.statista.com/statistics/1185900/worldwide-datasphere-storage-capacity-installed-base/.

[Ste13] M. Stevens. "New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis". In: EUROCRYPT 2013. Ed. by T. Johansson and P. Q. Nguyen. Vol. 7881. LNCS. Springer, Heidelberg, May 2013, pp. 245–261. DOI: 10.1007/978-3-642-38348-9_15.

[Ste99] F. A. Stevenson. Cryptanalysis of Contents Scrambling System. Online. Nov. 1999. URL: https://insecure.org/news/cryptanalysis_of_contents_scrambling_system.htm.

[SY17] F. Song and A. Yun. "Quantum Security of NMAC and Related Constructions - PRF Domain Extension Against Quantum attacks". In: CRYPTO 2017, Part II. Ed. by J. Katz and H. Shacham. Vol. 10402. LNCS. Springer, Heidelberg, Aug. 2017, pp. 283–309. DOI: 10.1007/978-3-319-63715-0_10.

[Tsu92] G. Tsudik. "Message Authentication with One-way Hash Functions". In: SIGCOMM Comput. Commun. Rev. 22.5 (Oct. 1992), pp. 29–38. ISSN: 0146-4833. DOI: 10.1145/141809.141812.

[TWP08] E. Tews, R.-P. Weinmann, and A. Pyshkin. "Breaking 104 Bit WEP in Less Than 60 Seconds". In: WISA 07. Ed. by S. Kim, M. Yung, and H.-W. Lee. Vol. 4867. LNCS. Springer, Heidelberg, Aug. 2008, pp. 188–202. DOI: 10.1007/978-3-540-77535-5_14.

[Vau02] S. Vaudenay. "Security Flaws Induced by CBC Padding - Applications to SSL, IPSEC, WTLS..." In: EUROCRYPT 2002. Ed. by L. R. Knudsen. Vol. 2332. LNCS. Springer, Heidelberg, Apr. 2002, pp. 534–546. DOI: 10.1007/3-540-46035-7_35.

[VP15] M. Vanhoef and F. Piessens. "All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS". In: USENIX Security 2015. Ed. by J. Jung and T. Holz. USENIX Association, Aug. 2015, pp. 97–112. URL: https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-vanhoef.pdf.

[vW94] P. C. van Oorschot and M. J. Wiener. "Parallel Collision Search with Application to Hash Functions and Discrete Logarithms". In: ACM CCS 94. Ed. by D. E. Denning, R. Pyle, R. Ganesan, and R. S. Sandhu. ACM Press, Nov. 1994, pp. 210–218. DOI: 10.1145/191177.191231.

[vW99] P. C. van Oorschot and M. J. Wiener. "Parallel Collision Search with Cryptanalytic Applications". In: Journal of Cryptology 12.1 (Jan. 1999), pp. 1–28. DOI: 10.1007/PL00003816.
[WC81] M. N. Wegman and L. Carter. "New Hash Functions and Their Use in Authentication and Set Equality". In: *Journal of Computer and System Sciences* 22 (1981), pp. 265-279. DOI: 10.1016/0022-0000(81)90033-7.

[WHW+23] P. Wouters, D. Huigens, J. Winter, and N. Yutaka. *OpenPGP*. Internet-Draft draft-ietf-openpgp-crypto-refresh-12. Work in Progress. Oct. 2023. 199 pp. URL: https://datatracker.ietf.org/doc/draft-ietf-openpgp-crypto-refresh/12/.

[WLF+05] X. Wang, X. Lai, D. Feng, H. Chen, and X. Yu. "Cryptanalysis of the Hash Functions MD4 and RIPEMD". In: *EUROCRYPT 2005*. Ed. by R. Cramer. Vol. 3494. LNCS. Springer, Heidelberg, May 2005, pp. 1-18. DOI: 10.1007/11426639_1.

[WMA+19] L. Wouters, E. Marin, T. Ashur, B. Gierlichs, and B. Preneel. "Fast, Furious and Insecure: Passive Keyless Entry and Start Systems in Modern Supercars". In: *IACR TCHES* 2019.3 (2019), pp. 66-85. ISSN: 2569-2925. DOI: 10.13154/tches.v2019.i3.66-85.

[WY05] X. Wang and H. Yu. "How to Break MD5 and Other Hash Functions". In: *EUROCRYPT 2005*. Ed. by R. Cramer. Vol. 3494. LNCS. Springer, Heidelberg, May 2005, pp. 19-35. DOI: 10.1007/11426639_2.

[WYW+09] X. Wang, H. Yu, W. Wang, H. Zhang, and T. Zhan. "Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC". In: *EUROCRYPT 2009*. Ed. by A. Joux. Vol. 5479. LNCS. Springer, Heidelberg, Apr. 2009, pp. 121-133. DOI: 10.1007/978-3-642-01001-9_7.

[WYY05] X. Wang, Y. L. Yin, and H. Yu. "Finding Collisions in the Full SHA-1". In: *CRYPTO 2005*. Ed. by V. Shoup. Vol. 3621. LNCS. Springer, Heidelberg, Aug. 2005, pp. 17-36. DOI: 10.1007/11535218_2.

[Yas07] K. Yasuda. ""Sandwich" Is Indeed Secure: How to Authenticate a Message with Just One Hashing". In: *ACISP 07*. Ed. by J. Pieprzyk, H. Ghodosi, and E. Dawson. Vol. 4586. LNCS. Springer, Heidelberg, July 2007, pp. 355-369. DOI: 10.1007/978-3-540-73458-1_26.

[Yas10] K. Yasuda. "The Sum of CBC MACs Is a Secure PRF". In: *CT-RSA 2010*. Ed. by J. Pieprzyk. Vol. 5985. LNCS. Springer, Heidelberg, Mar. 2010, pp. 366-381. DOI: 10.1007/978-3-642-11925-5_25.

[Yas11] K. Yasuda. "A New Variant of PMAC: Beyond the Birthday Bound". In: *CRYPTO 2011*. Ed. by P. Rogaway. Vol. 6841. LNCS. Springer, Heidelberg, Aug. 2011, pp. 596-609. DOI: 10.1007/978-3-642-22792-9_34.

[ZWS+12] L. Zhang, W. Wu, H. Sui, and P. Wang. "3kf9: Enhancing 3GPP-MAC beyond the Birthday Bound". In: *ASIACRYPT 2012*. Ed. by X. Wang and K. Sako. Vol. 7658. LNCS. Springer, Heidelberg, Dec. 2012, pp. 296-312. DOI: 10.1007/978-3-642-34961-4_19.
Selected Publications

<table><tr><td>A</td><td>The Sum Can Be Weaker Than Each Part</td><td>88</td></tr><tr><td>B</td><td>Generic Attacks on Hash Combiners</td><td>111</td></tr><tr><td>C</td><td>From Collisions to Chosen-Prefix Collisions</td><td>195</td></tr><tr><td>D</td><td>SHA-1 is a Shambles</td><td>225</td></tr><tr><td>E</td><td>Transcript Collision Attacks</td><td>260</td></tr><tr><td>F</td><td>New Generic Attacks against Hash-Based MACs</td><td>277</td></tr><tr><td>G</td><td>Improved Generic Attacks Against Hash-Based MACs and HAIFA</td><td>297</td></tr><tr><td>H</td><td>On the Practical (In-)Security of 64-bit Block Ciphers</td><td>331</td></tr><tr><td>I</td><td>The Missing Difference Problem</td><td>343</td></tr><tr><td>J</td><td>Generic Attacks Against Beyond-Birthday-Bound MACs</td><td>370</td></tr><tr><td>K</td><td>Breaking Symmetric Cryptosystems Using Quantum Period Finding</td><td>400</td></tr><tr><td>L</td><td>Quantum Linearization Attacks</td><td>430</td></tr></table>
# The Sum Can Be Weaker Than Each Part*

Gaëtan Leurent<fnref n="1" /> and Lei Wang<fnref n="2" />

**Abstract.** In this paper we study the security of summing the outputs of two *independent* hash functions, in an effort to increase the security of the resulting design, or to hedge against the failure of one of the hash functions. The exclusive-or (XOR) combiner $H_1(M) \oplus H_2(M)$ is one of the two most classical combiners, together with the concatenation combiner $H_1(M) \parallel H_2(M)$. While the security of the concatenation of two hash functions is well understood since Joux's seminal work on multicollisions, the security of the sum of two hash functions has been much less studied. The XOR combiner is well known as a good PRF and MAC combiner, and is used in practice in TLS versions 1.0 and 1.1. In a hash function setting, Hoch and Shamir have shown that if the compression functions are modeled as random oracles, or even weak random oracles (i.e. they can easily be inverted – in particular $H_1$ and $H_2$ offer no security), $H_1 \oplus H_2$ is indifferentiable from a random oracle up to the birthday bound.

In this work, we focus on the preimage resistance of the sum of two narrow-pipe *n*-bit hash functions, following the Merkle-Damgård or HAIFA structure (the internal state size and the output size are both *n* bits). We show a rather surprising result: the sum of two such hash functions, e.g. SHA-512 $\oplus$ Whirlpool, can never provide *n*-bit security for preimage resistance. More precisely, we present a generic preimage attack with a complexity of $\tilde{O}(2^{5n/6})$. While it is already known that the XOR combiner is not preserving for preimage resistance (i.e. there might be some instantiations where the hash functions are secure but the sum is not), our result is much stronger: for *any* narrow-pipe functions, the sum is not preimage resistant.

Besides, we also provide concrete preimage attacks on the XOR combiner (and the concatenation combiner) when one or both of the compression functions are weak; this complements Hoch and Shamir's proof by showing its tightness for preimage resistance.

Of independent interests, one of our main technical contributions is a novel structure to control *simultaneously* the behavior of independent hash computations which share the same input message. We hope that breaking the pairwise relationship between their internal states will have applications in related settings.

**Keywords:** Hash functions, combiners, XOR combiner, preimage attack.

<footnote n="1">¹ Inria, France, gaetan.leurent@inria.fr</footnote>

<footnote n="2">² Nanyang Technological University, Singapore, wang.lei@ntu.edu.sg</footnote>

<footnote>* ©IACR 2015. This article is the final version submitted by the authors to the IACR and to Springer-Verlag on January 30 2015. The version published by Springer-Verlag will be available in the proceedings of Eurocrypt 2015.</footnote>
# 1 Introduction

Hash functions are a very important class of primitive in modern cryptography, used in almost every secure system. A hash function $H: \{0,1\}^* \to \{0,1\}^n$ takes an arbitrary length input and produces an $n$-bit output or digest. Hash functions are used in many setting with various security requirements; the general expectation is that a hash function should behave like a random function from $\{0,1\}^*$ to $\{0,1\}^n$. More concretely, the main security notions expected from a hash function are:

**Collision resistance.** It should be hard to find two messages $M \neq M'$ with $H(M) = H(M')$.

**Second-preimage resistance.** Given a message $M$, it should be hard to find $M' \neq M$ with $H(M) = H(M')$.

**Preimage resistance.** Given a target hash value $\overline{H}$, it should be hard to find $M$ with $H(M) = \overline{H}$.

Since generic collision attacks require $2^{n/2}$ work, and generic preimage attacks require $2^n$ work, a secure hash function should have the same level of resistance.

In order to build more secure hash functions, or to protect oneself against future cryptanalysis advances, such as the devastating attacks of Wang et al. against the SHA family [42,41], a practical countermeasure might be to combine two different hash functions. The goal is that the combined hash function can only be broken when both components are weak. In particular, this reasoning was used by the designers of SSL [14] and TLS [8], who combined MD5 and SHA-1 in various ways. More precisely, the Key Derivation Function of TLS v1.0/v1.1 uses a sum of HMAC-MD5 and HMAC-SHA-1.<fnref n="3" /> The designers explain [8]: "In order to make the PRF as secure as possible, it uses two hash algorithms in a way which should guarantee its security if either algorithm remains secure."

There are two classical hash function combiners: the concatenation combiner $H_1(M) \parallel H_2(M)$ and the XOR combiner $H_1(M) \oplus H_2(M)$. In a seminal work [20], Joux showed that the concatenation combiner with narrow-pipe hash functions offers much less security than could be expected: it has $2^n$ bits of output, but essentially offers the same security as an $n$-bit hash function. In this work, we carry a similar analysis for the XOR combiner. Previous work has shown that it is indifferentiable from a random oracle up to the birthday bound [17], even if the initial functions are weak; in particular, it has optimal collision resistance of $n/2$ bits. However, we show that the preimage security is much less than one might expect, with a generic preimage attack with complexity $\tilde{O}(2^{5n/6})$.

Since the goal of a combiner is to keep some security even if one of the functions is found to be weak, it is natural that the two hash functions $H_1$ and $H_2$ are independent in practice. Throughout this paper the two hash functions

<footnote n="3">³ We note that this MD5/SHA-1 combiner has been replaced by primitives based on single hash function (e.g., SHA-256) since TLS v1.2 [9].</footnote>
used in a combiner are always assumed to be independent without specifying it explicitly<fnref n="4" />.

**Iterated hash function.** In this paper we consider iterated hash functions, following the Merkle-Damgård construction [30,7] or the more general HAIFA construction [3], as shown in Figure 1. We focus on narrow-pipe designs, i.e. we assume that the internal state size is the same as the output size $n$. The message $M$ is first split into blocks $m_0, \dots, m_\ell$, and the hash function iterates a series of compression functions $h_i$ over an internal state $x$, with the initial value denoted as $IV$. Finally, the hash value is computed with a finalization function $g$:

$$x_0 = IV \qquad x_{i+1} = h_i(x_i, m_i) \qquad H(M) = g(x_{\ell+1}, |M|)$$

In the following, we assume that the compression function is the same at every step ($\forall i, h_i = h$) in order to simplify the notations, but it is straightforward to apply the attack with the corresponding function at each step.

<figure><img src="image_47.png" /><figcaption>Fig. 1. Iterated hash function.</figcaption></figure>

## 1.1 Related works

Combiners have been studied in several different settings. For generic attacks, the compression functions are modeled as random functions, in order to devise attacks that don't use any weakness of the compression functions. On the other hand, some work assumes that the compression function is a *weak* random oracle (that can easily be inverted), and prove that some constructions are still secure in this model. Finally, more theoretical work focus on the notion of *robustness*, i.e. the existence of a reduction from attacks on the hash functions to attacks on the combiner.

<footnote n="4">⁴ If the two hash functions can be related, it is trivial that the XOR combiner is not security-preserving. For instance, let $H_2(M) := H_1(M) \oplus \text{const}$, where $\text{const}$ is a constant. If $H_1$ is ideally secure, then $H_2$ is also ideally secure. However, the XOR combiner $H_1(M) \oplus H_2(M) = \text{const}$ for any message $M$.</footnote>
**Analysis of the concatenation combiner.** The concatenation combiner $H_1(M) \parallel H_2(M)$ is probably the most studied one. In 2004, Joux [20] described surprising attacks on the concatenation of two narrow-pipe hash functions using multicollisions: while the output size is $2n$ bits, the concatenation can at most provide $n/2$-bit security for collision resistance and $n$-bit security for preimage resistance$^5$. In particular, the concatenation is not security-amplifying. On the other hand, the concatenation combiner is robust for preimages and collisions, which gives a matching lower bound for generic attacks.

Later, Hoch and Shamir [17] evaluated the security of the concatenation
combiner with two weak hash functions. More precisely, the two hash functions are
narrow-pipe Merkle-Damgård, and the compression functions are modeled as weak
random oracles (as defined by Liskov [24]), i.e., the adversary is given additional
interfaces to receive (random) preimages of the compression functions. They have
proven that in this model, the concatenation combiner is still indifferentiable
from a random oracle with $n/2$-bit security, implying (at least) the same security
bound for collision resistance and preimage resistance. The bound is matched by
Joux's attack for collisions, but there is a gap with Joux's attack for preimages,
with complexity $2^n$, which might be interesting to investigate further.

Mendel et al. analyzed some dedicated instantiations of the concatenation
combiner [28], in particular using the hash function MD5. We omit the details
and refer interested readers to [28].

**Analysis of the XOR combiner.** The XOR combiner has received less analysis. The work of Hoch and Shamir [17] actually proves the security of the XOR combiner as an intermediate result: it is also indifferentiable from a random oracle up to $2^{n/2}$ queries in the weak random oracle model. In particular, this proves that there are no generic attacks with complexity smaller than $2^{n/2}$. For collision resistance, the bound is tight, since it is matched with the generic birthday attack bound. On the other hand, for preimage resistance, there exists a gap between the $n/2$-bit proven bound and the $n$-bit expected ideal security bound.

To the best of our knowledge, no preimage attacks have been shown against
the XOR combiner. Therefore, the preimage security of the XOR combiner against
generic attacks is still an open problem, and will be the main topic of our work.
We will also consider the preimage security of the XOR combiner with weak hash
functions, and study the tightness of Hoch and Shamir's bound.

**Robust combiners.** In the last years, the general problem of combining two (or more) hash functions $H_1$ and $H_2$ has been extensively studied from a theoretical point of view. These works focus on the notion of a *robust combiner*: a robust combiner is secure with respect to property $\alpha$ as long as one of the underlying hash functions is secure for $\alpha$. It can be shown that the concatenation combiner is a robust combiner for collision-resistant hash functions and for MACs, while the

<footnote>$^5$ The attacks actually require only one of the functions to be narrow-pipe.</footnote>
XOR combiner is robust for PRFs and for MACs [23]. More advanced combiners have been constructed in order to be robust for multiple properties simultaneously [11,12,13]. The notion was mostly studied via the black-box reduction model. A series of results have showed that robust combiners for collision resistance and preimage resistance cannot have an output length significantly shorter than the sum of the output length of the underlying hash functions [4,35,36,31]. Since the XOR combiner is length preserving, this shows that it is not robust for collision resistance and preimage resistance.

Actually, the impossibility results are in part due to the stringent requirement from the black-box reduction model. In order to overcome this limitation, Mittelbach introduced the *idealized* random oracle model [32]. He gives a construction of a short output combiner with optimal collision and preimage security in this model<fnref n="6" /> (assuming that one of the functions is ideal): Cryptophia's short combiner uses the sum of two hash functions with some pre-processing of the messages (to allow non-independent functions).

More generally, we point out that a combiner being non-robust does not necessarily mean there is an attack. The non-robustness results only show that the security of the combiner cannot be proved with a *reduction* from the security of the hash functions. In particular, the XOR combiner is not robust for collision-resistance, or even collision-resistance preserving. However, Hoch and Shamir's work proves that there are no generic collision attacks on this construction, either with ideal compression function, or even with weak compression functions. This arguably makes the XOR a useful combiner for collision resistance. Regarding preimage security, the non-robustness result does not imply that the XOR of two concrete hash functions is weak, and the simplicity and short output of this construction still make it quite attractive.

## 1.2 Our results

In this work, we study the preimage security of the XOR combiner, the main remaining open problem for classical combiners. We show that, surprisingly, the sum of two narrow-pipe $n$-bit hash functions can never achieve $n$-bit security for preimage resistance. More precisely, we find a generic preimage attack with a complexity of $\tilde{O}(2^{5n/6})$. It does not exploit any structural weakness of the compression functions and hence is applicable even if the compression functions are two ideal random oracles. Thus, even if the two hash functions are $n$-bit secure for preimage resistance, the XOR combiner is at most $5n/6$-bit secure for preimage resistance. In other words, the sum can be weaker than each part.

The attack is based on a novel technique to break the pairwise relationship between the internal states of the two hash functions. More precisely, the two hash functions $H_1$ and $H_2$ share the same input message, and hence the internal states of their iterative compression function computations are related. We control the computation chains of $H_1$ and $H_2$ simultaneously by constructing a new message

<footnote n="6">⁶ A mistake in the initial proof and construction was later fixed by Mennink and Preneel [29].</footnote>
structure $\mathcal{M}$, and two sets of internal states $\mathcal{A}$ for $H_1$ and $\mathcal{B}$ for $H_2$ such that: for any value $A$ from $\mathcal{A}$ and any value $B$ from $\mathcal{B}$, we can derive a message $M_{A,B}$ from $\mathcal{M}$ such that $H_1(M_{A,B})$ produces $A$ and $H_2(M_{A,B})$ produces $B$. Hence we can select states from $\mathcal{A}$ and $\mathcal{B}$ independently. After that, we use a birthday match to find a message block $m$, a value $A$ from $\mathcal{A}$ and a value $B$ from $\mathcal{B}$ such that $h_1(A, m) \oplus h_2(B, m)$ is equal to the target hash digest, where $h_1$ and $h_2$ are the compression functions of $H_1$ and $H_2$ respectively. Finally we derive the message $M_{A,B}$ from $\mathcal{M}$, and output $M_{A,B} \parallel m$ as a preimage of the target hash digest.

Our preimage attack is also applicable to Cryptophia's short combiner [32,29]. This construction has been proven to provide optimal collision and preimage resistance, assuming that at least one of the initial functions is a monolithic random oracle, but our attack does not violate the security proof, because we use the fact that both functions have an iterative structures with an *n*-bit internal state. Still, this shows that with many practical hash functions, the combiner will be weaker than the initial functions. Our results also show that the XOR combiner and Cryptophia's combiner are not robust in the semi-black-box model introduced by Mittelbach [32]<fnref n="7" />, even with independent hash functions $H_1$ and $H_2$.

Our analysis on the XOR combiner is also interesting for dedicated hash function design. The hash function family RIPEMD [10] is based on a compression function with two parallel lanes, added together at the end of each compression function. Interestingly, RIPEMD-160 has been quite resilient to cryptanalysis [27,38,25,26], and are still considered secure. Several more recent designs use parallel lanes in a similar way (combining them at the end of each compression function call), such as HAS-V [34], FORK [18] and LANE [19]. It might be tempting to use parallel lanes during the full iteration, and to combine them only at the end. Indeed, the designers of SHA-V [15] used this approach: the 160-bit version of SHA-V has two parallel lanes, combined at the end with a modular sum. This is equivalent to summing two different hash functions, and hence our attack can be applied to SHA-V.

Another contribution of this paper is to present concrete preimage attacks on the XOR combiner with one or both weak hash functions (defined in [24]). The complexity of our attacks is $\tilde{O}(2^{n/2})$. Furthermore, the attack can be extended to the concatenation combiner with two weak hash functions under the same complexity. It can be seen that these attacks match the bound of Hoch and Shamir's security proof [17], and hence fulfill the gaps pointed out in Section 1.1. It implies the tightness of Hoch and Shamir's proof on the classical combiners with weak hash functions for preimage resistance.

Finally, we would like to highlight the technical interests of this paper. We devise a novel structure named interchange structure to simultaneously control

<footnote n="7">⁷ Loosely speaking, a combiner is robust with respect to property $\alpha$ if it is (at least) as secure as the stronger underlying hash function for $\alpha$.</footnote>
two (or more) hash lanes with the same input message, and succeed in further relaxing the pairwise relation between the internal states of lanes. It is indeed a step of technical advance compared with previous extensive studies on this topic, and hence will hopefully have applications or lead to new technical development in related settings. We refer to the open discussions in Section 7 for more details.

## 1.3 Notations and roadmap in the rest of paper

We use the following notations:

$H_1, H_2$ : hash functions

$IV_1, IV_2$ : initial values for $H_1$ and $H_2$, respectively

$h_1, h_2$ : compression functions of $H_1$ and $H_2$, respectively

$h_1^*, h_2^*$ : compression functions iterated over several blocks
(in particular, $H_i(M) = h_i^*(IV_i, M)$)

$m$ : message block

$M$ : message chunk ($n/2$ blocks)

$\mathbf{M}$ : long message (several chunks)

$a_j, b_k$ : chains for $H_1$ and $H_2$, respectively

$a_j$ denotes a generic chain, while $a_{j_0}$ denotes a particular chain

$A_j, B_k$ : end points of the chains

$n$ : hash function output size

**Roadmap.** Section 2 provides an overview of our generic preimage attack on the XOR combiner. Sections 3, 4, and 5 elaborate the attack procedure step by step in details. Section 6 presents the applications and extensions of the attack. Finally we conclude the paper and discuss future directions in Section 7.

# 2 Overview of the attack

We first give an overview of the techniques and the structures used in the attack, while more detailed descriptions will be given in the following sections.

The main idea is to consider several chains of internal states reached by processing a common message $\mathbf{M}$ from different starting points (note that the message $\mathbf{M}$ is not fixed in advance, but will be determined when building the structure). More precisely, the message $\mathbf{M}$ is denoted as the *primary message*, and divided in several chunks: $\mathbf{M} = M_0 \parallel M_1 \parallel \dots$ (as discussed later, a chunk will consist of several message blocks). We denote chains of internal states for $H_1$ as $a_j$, and the individual states of the chain as $a_j^i$, with $h_1^*(a_j^i, M_i) = a_j^{i+1}$. Similarly, we denote chains for $H_2$ as $b_k$, with $h_2^*(b_k^i, M_i) = b_k^{i+1}$. When considering both hash functions, message block $M_i$ leads from the pair of states $(a_j^i, b_k^i)$ to $(a_j^{i+1}, b_k^{i+1})$, which is denoted:

$$ (a_j^i, b_k^i) \stackrel{M_i}{\rightsquigarrow} (a_j^{i+1}, b_k^{i+1}). $$
**Switch structure.** Next we build special structures called *switches* in order to jump between chains in a controlled way. A switch allows to jump from a specific pair of chains $(a_{j_0}, b_{k_0})$ to a different pair of chains $(a_{j_0}, b_{k_1})$ using a secondary message chunk $M'_i$, in addition to the normal transitions using chunk $M_i$ of the primary message $M$:

$$ (a_j^i, b_k^i) \stackrel{M_i}{\rightsquigarrow} (a_j^{i+1}, b_k^{i+1}) : \quad \text{normal transition for each chain} $$

$$ (a_{j_0}^i, b_{k_0}^i) \stackrel{M'_i}{\rightsquigarrow} (a_{j_0}^{i+1}, b_{k_1}^{i+1}) : \quad \text{jump from chains } (a_{j_0}, b_{k_0}) \text{ to } (a_{j_0}, b_{k_1}) $$

In order to simplify the notations, we often omit the chunk index, in order to show only the chains that are affected by the switch.

The main message chunk $M_i$ and the secondary message chunk $M'_i$ are determined when building the switch, and the main message defines the next state of all the chains. We note that the secondary message chunk $M'_i$ should only be used when the state is $(a_{j_0}^i, b_{k_0}^i)$. A simple example is depicted in Figure 2.

<figure><img src="image_48.png" /><figcaption>**Fig. 2.** A single switch: jump from $(a_0, b_0)$ to $(a_0, b_1)$ by using $M'$ (dashed lines) instead of $M$ (solid lines).</figcaption></figure>

Alternatively, a switch can be designed to jump from $(a_{j_0}, b_{k_0})$ to $(a_{j_1}, b_{k_0})$. We defer the details of the construction to Section 3; it can be built with a complexity of $\tilde{O}(2^{n/2})$.

**Interchange structure.** By combining several simple switches, we can build an interchange structure with starting points $IV_1$ and $IV_2$ and ending points $\{A_j, j = 0 \dots 2^t - 1\}$ and $\{B_k, k = 0 \dots 2^t - 1\}$, so that we can select a message ending in any state $(A_j, B_k)$. Figure 3 shows one possible way to build such a structure, and Figure 4 shows how to select a given message in the structure. An interchange structure with $2^t$ chains for each function requires about $2^{2t}$ switches. Since we can build a switch for a cost of $\tilde{O}(2^{n/2})$, the total structure is built with $\tilde{O}(2^{2t+n/2})$ operations.

**Preimage search.** Finally, we can use an interchange structure with ending points $\{A_j, j = 0 \dots 2^t - 1\}$ and $\{B_k, k = 0 \dots 2^t - 1\}$, to build a preimage
<figure><img src="image_49.png" /></figure>

<figure><img src="image_50.png" /><figcaption>Fig. 3. Overview of an interchange structure</figcaption></figure>

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

<figure><img src="image_52.png" /><figcaption>Fig. 4. Using of the interchange structure to reach output ($A_1, B_2$)</figcaption></figure>

attack as follows. Let $\overline{H}$ denote the target value. We select a random message block $m$, and we compute two lists by evaluating the compression functions after the interchange structure: $\{A'_j = h_1(A_j, m), j = 0...2^t - 1\}$ and $\{B'_k = \overline{H} \oplus h_2(B_k, m), k = 0...2^t - 1\}$. We expect a match between the lists with probability $2^{2t-n}$. After about $2^{n-2t}$ random choices of $m$, we get a match $(j^*, k^*)$:

$$h_1(A_{j^*}, m) = \overline{H} \oplus h_2(B_{k^*}, m) \quad \text{i.e.} \quad h_1(A_{j^*}, m) \oplus h_2(B_{k^*}, m) = \overline{H}.$$

Therefore, we can construct a preimage of $\overline{H}$ by concatenating the message leading to $(A_{j^*}, B_{k^*})$ in the interchange structure, and the block $m$ (we ignore the finalization function in this section).
The complexity of the preimage search is about $2^{n-t}$ evaluations of the compression function, using an interchange structure with $2^t$ end-points.

**Complexity analysis.** Building the interchange structures requires about $2^{2t+n/2}$ evaluations of the compression function, while the preimage search requires about $2^{n-t}$. The optimal complexity is reached when both steps take the same time, i.e. $t = n/6$. This gives a complexity of $\tilde{O}(2^{5n/6})$.

## 3 The switch structure

We now explain how to build the switch structure at the core of our attack. This construction is strongly based on the multicollision technique of Joux [20].

Given states $a_{j_0}^i, b_{k_0}^i$ and $b_{k_1}^i$, we want to build message chunks $M_i$ and $M'_i$ in order to have the following transitions:

$$ (a_{j_0}^i, b_{k_0}^i) \overset{M_i}{\rightleftharpoons} (a_{j_0}^{i+1}, b_{k_0}^{i+1}) \quad (a_{j_0}^i, b_{k_1}^i) \overset{M_i}{\rightleftharpoons} (a_{j_0}^{i+1}, b_{k_1}^{i+1}) \quad (a_{j_0}^i, b_{k_0}^i) \overset{M'_i}{\rightleftharpoons} (a_{j_0}^{i+1}, b_{k_1}^{i+1}). $$

The main message chunk $M_i$ is used to define the next state of all the remaining chains, while the secondary message chunk $M'_i$ will be used to jump from chains $(a_{j_0}, b_{k_0})$ to $(a_{j_0}, b_{k_1})$. We note that $M'_i$ will only be used when the state is $(a_{j_0}^i, b_{k_0}^i)$. In particular, $M_i$ and $M'_i$ must satisfy:

$$ a_{j_0}^{i+1} = h_1^*(a_{j_0}^i, M_i) = h_1^*(a_{j_0}^i, M'_i) $$

$$ b_{k_1}^{i+1} = h_2^*(b_{k_1}^i, M_i) = h_2^*(b_{k_0}^i, M'_i) $$

$$ b_{k_0}^{i+1} = h_2^*(b_{k_0}^i, M_i) \neq b_{k_1}^{i+1} $$

We first build a multicollision for $h_1^*$, starting from state $a_{j_0}^i$, i.e. a large set $\mathcal{M}$ of $2^{n/2}$ messages that all reach the same state $a_{j_0}^{i+1}$ ($\forall M \in \mathcal{M}, h_1^*(a_{j_0}^i, M) = a_{j_0}^{i+1}$). As shown by Joux, this can be done efficiently by sequentially building $n/2$ collisions.

Next, we evaluate $h_2^*(b_{k_0}^i, M)$ and $h_2^*(b_{k_1}^i, M)$ for all the messages $M$ in the set $\mathcal{M}$. With high probability there is match between the sets of values$^8$. We denote the colliding messages as $M_i$ and $M'_i$, so that we have $h_2^*(b_{k_0}^i, M'_i) = h_2^*(b_{k_1}^i, M_i)$.

Finally we compute the missing chains using the message $m_i: a_j^{i+1} = h_1^*(a_j^i, m_i)$, $b_k^{i+1} = h_2^*(b_k^i, m_i)$. With high probability all the chains reach distinct values; if this is not the case, we restart the construction with a new multicollision. The full algorithm is shown as Algorithm 1, and illustrated by Figure 5; it requires about $n/2 \cdot 2^{n/2}$ evaluations of the compression functions.

<footnote>$^8$ If this is not the case, we build a new multicollision.</footnote>
<figure><img src="image_53.png" /><figcaption>Fig. 5. Building a switch structure. First, $M$ and $M'$ are selected from $M$ to generate a collision (defining the new $b_{k_1}$), then $b_{k_0}$ is evaluated using $M$.</figcaption></figure>

## 4 The interchange structure

Let us now describe the combination of switch structures into an interchange structure. The goal of this structure is to select the final value of the $H_1$ computation and the $H_2$ computation independently. More precisely, the structure defines two sets of final values $A_j$ and $B_k$, and a set of messages $M_{jk}$ such that:

$$ (IV_1, IV_2) \overset{M_{jk}}{\rightleftharpoons} (A_j, B_k). $$

In order to build this structure, we initialize the first chains with $a_0^0 = IV_1$, $b_0^0 = IV_2$, and set the other starting points randomly. Then, we use switches to jump for an already reachable pair $(a_{j_0}, b_{k_0})$ to a different pair $(a_{j_0}, b_{k_1})$ (or to $(a_{j_1}, b_{k_0})$, respectively). By using $2^{2t} - 1$ switches, we can make all pairs reachable. There are many way to combine the switches; a simple one can be described as follows:

1. first, build switches from $(a_0, b_0)$ to each of the $(a_0, b_k)$'s;

2. then for each $k$, build a series of switches from $(a_0, b_k)$ to all the $(a_j, b_k)$'s.

In order to reach the chains $(a_j, b_k)$, one would activate the $k$-th switch in the first part to jump from $(a_0, b_0)$ to $(a_0, b_k)$, and then the $j$-th switch in the $k$-th series of the second part to jump from $(a_0, b_k)$ to $(a_j, b_k)$. This structure is shown in Figure 3 and a pseudo-code description is given by Algorithm 2, where the INTERCHANGE functions builds the structure, and the SELECTMESSAGE function extracts the message reaching $(a_j, b_k)$.

The structure can be somewhat optimized using the fact that the extra chains have no prespecified initial values. We show how to take advantage of this in Appendix A, using multicollision structures in addition to the switch structures. However, this doesn't change significantly the complexity: we need $(2^t - 1)(2^t - 1)$ switches instead of $2^{2t} - 1$. In total, we need about $n/2 \cdot 2^{2t+n/2}$ evaluations of the compression functions to build a $2^t$-interchange structure.

We believe that a $2^t$-interchange structure based on switches will need at least $\Theta(2^{2t})$ switches, because every switch can only increase the number of reachable
<caption>**Algorithm 1 Building a single switch**</caption>

```c
function SWITCH(h1, h2, a, b, b')
    x ← a
    M ← ∅
    for 0 ≤ i < n/2 do
        (m, m') ← COLLISION(h1, x)
        M ← (M || m) ∪ (M || m')
        x ← h1(x, m)
    end for
    H ← {}
    for M ∈ M do
        y ← h2(b, M)
        H[y] ← M
    end for
    for M ∈ M do
        y ← h2(b', M)
        if H[y] exists then
            return M, H[y]
        end if
    end for
end function

function COLLISION(h, x)
    H ← {}
    loop
        m ← $
        y ← h1(x, m)
        if H[y] exists then
            return m, H[y]
        else
            H[y] ← m
        end if
    end loop
end function
```

pairs $(a_j, b_k)$ by one. As shown in Appendix A some switches can be saved in the beginning but it seems that new ideas would be needed to reduce the total complexity below $\Theta(2^{2t+n/2})$.

## 5 Preimage Attack

Finally, we describe the full preimage attack. We first build an interchange structure with $2^t$ chains for each of $H_1$ and $H_2$. We denote the ending points as $\{A_j, j = 0 \dots 2^t - 1\}$ and $\{B_k, k = 0 \dots 2^t - 1\}$, and we know how to select a message $M_{jk}$ to reach any state $(A_j, B_k)$. When adding a message block $m$ to one of the messages $M_{jk}$ in the interchange structure, the output of the combiner
<caption>**Algorithm 2** Building and using a T-interchange structure</caption>

function INTERCHANGE(h₁, h₂, IV₁, IV₂)
    a₀ ← IV₁, b₀ ← IV₂
    **for** 1 ≤ k < T **do**
        aₖ ← $, bₖ ← $
    **end for**
    **for** 1 ≤ j < T **do**
        (M, M') ← SWITCH(h₁, h₂, a₀, b₀, b₃)
        **M** ← **M** || M; **M'** ← **M'** || **M'**
        **for** 0 ≤ k < T **do**
            aₖ ← h₁*(aₖ, M)
            bₖ ← h₂*(bₖ, M)
        **end for**
    **end for**
    **for** 1 ≤ j < T **do**
        **for** 1 ≤ i < T **do**
            (M, M') ← SWITCH(h₂, h₁, b₃, a₀, aᵢ)
            **M** ← **M** || M; **M'** ← **M'** || **M'**
            **for** 0 ≤ k < T **do**
                aₖ ← h₁*(aₖ, M)
                bₖ ← h₂*(bₖ, M)
            **end for**
        **end for**
    **end for**
    **return** (M, M')
end function

function SELECTMESSAGE(M, M', j, k)
    μ ← M
    **if** k ≠ 0 **then**
        μ[k - 1] ← M'[k - 1]
    **end if**
    **if** j ≠ 0 **then**
        μ[(k + 1) · (T - 1) + j - 1] ← M'[[(k + 1) · (T - 1) + j - 1]]
    **end if**
    **return** μ
end function

can be written as:

$$
H_1(\mathbf{M}_{jk} \parallel m) \oplus H_2(\mathbf{M}_{jk} \parallel m) = g_1(h_1(A_j, m), \ell+1) \oplus g_2(h_2(B_k, m), \ell+1),
$$

where $g_1$ and $g_2$ are the finalization functions of $H_1$ and $H_2$, respectively, and $\ell$ is the length of the messages in the structure.

In order to reach a target value $\overline{H}$, we select a random block $m$, and we evaluate
$\{A'_j = g_1(h_1(A_j, m), \ell+1), j = 0 \dots 2^t - 1\}$ and $\{B'_k = \overline{H} \oplus g_2(h_2(B_k, m), \ell + \dots)$
1), $k = 0...2^t - 1$}. If there is a match $(j^*, k^*)$ between the two lists, we have:

$$ 
\begin{aligned}
A'_{j^*} &= B'_{k^*} \Leftrightarrow g_1(h_1(A_{j^*}, m), \ell+1) = \overline{H} \oplus g_2(h_2(B_{k^*}, m), \ell+1) \\
&\Leftrightarrow H_1(M_{jk} \parallel m) \oplus H_2(M_{jk} \parallel m) = \overline{H}.
\end{aligned}
$$

For a random choice of $m$, we expect that a match exists with probability $2^{2t-n}$, and testing it requires about $2^t$ operations<fnref n="9" />. We will have to repeat this procedure $2^{n-2t}$ times on average, therefore the total cost of the preimage search is about $2^{n-t}$ evaluations of $h_1$ and $h_2$.

As explained in the previous section, building a $2^t$-interchange structure requires about $n/2 \cdot 2^{2t+n/2}$ operations. Using $t = n/6$ we balance the two steps of the attack, and reach the optimal complexity of about $n/2 \cdot 2^{5n/6}$ operations for the preimage attack.

## 5.1 Message length and memory complexity

The attack uses messages of length $n/2 \cdot 2^t$, and the memory complexity of the attack<fnref n="10" /> is also $n/2 \cdot 2^t$. The optimal choice $t = n/6$ gives messages of length $n/2 \cdot 2^{n/3}$. The memory requirement is probably not an issue<fnref n="11" /> for an attacker that can spend time $2^{5n/6}$, but the message length can be a problem with some hash functions that don't accept long inputs. For instance SHA-256 is only defined for message with less than $2^{64}$ bits (i.e. $2^{55}$ blocks).

In this case, one can apply the attack with a smaller value of $t$: this reduces the length of the messages, at the cost of more time spent in the preimage search step. For instance, we can mount a preimage attack against SHA-256 ⊕ BLAKE-256 with complexity $2^{232}$ using $t = 24$, while the optimal attack with $n = 256$ would cost only $2^{220.3}$. Similarly, our attack applied to SHA-512 ⊕ Whirlpool has a complexity of $2^{461}$, rather than $2^{434.7}$.

## 6 Applications and Extensions

The attack works identically if the hash functions use the HAIFA mode rather than the plain Merkle-Damgård iteration. Also it can easily be extended to $H_1(M) \odot H_2(M)$ where $\odot$ denotes an easy to invert group operation (for instance, a modular addition rather than the exclusive or). The attack can also be extended to hash functions $H_1$ and/or $H_2$ using an internal check-sum, such as the GOST family of hash functions, using pairs of blocks with a constant sum.

<footnote n="9">⁹ It takes $O(t \cdot 2^t)$ operations by sorting the lists, but only $2 \cdot 2^t$ using a hash table.</footnote>

<footnote n="10">¹⁰ We only need to store the messages $M$ and $M'$</footnote>

<footnote n="11">¹¹ For instance, the attack is on the verge of practicality with $n = 64$; the time complexity is $2^{58.3}$ and the memory complexity is $2^{26.3}$.</footnote>
## 6.1 Application to the sum of wide-pipe hash functions

The attack can also be used when the internal state size $ℓ$ is larger than the output size $n$. The complexity of building a $2^t$-interchange structure is related to $ℓ$ as $ℓ/2 \cdot 2^{2t+ℓ/2}$. On the other hand, the complexity of the meet-in-the-middle preimage search is related to $n$ as $2^{n-t}$. The optimal complexity is $ℓ/2 \cdot 2^{2n/3+ℓ/6}$ by matching the two complexities with $t = n/3 - ℓ/6$. Therefore our attack can be applied as long as $ℓ + 6 \log(ℓ) \le 2n$ holds. For instance, we can compute preimages of SHA-224 ⊕ BLAKE-224 with complexity roughly $2^{199}$.

## 6.2 Application to Cryptophia's short combiner

Our attack can also be applied to Cryptophia's short combiner, as proposed by Mittelbach [32], and to the revised version of Mennink and Preneel [29]. This combiner computes the sum of two hash functions with some pre-processing of the message, to allow non-independent functions:

$$ 
\begin{aligned}
C(M) &= H_1(\tilde{m}_1^1 \| \dots \| \tilde{m}_\ell^1) \oplus H_2(\tilde{m}_1^2 \| \dots \| \tilde{m}_\ell^2) \\
\tilde{m}_j^1 &= H_1(0 \| l_1 \| m_j \oplus k_1) \oplus H_2(0 \| l_2 \| m_j \oplus k_2) \\
\tilde{m}_j^2 &= H_1(1 \| l_1 \| m_j \oplus k_1) \oplus H_2(1 \| l_2 \| m_j \oplus k_2)
\end{aligned}
$$

where $k_1, k_2, l_1, l_2$ is a randomly chosen key. The security proof in the ideal model shows that $C$ is optimally preimage resistant if at least one of the hash functions is ideal.

However, if both $H_1$ and $H_2$ are narrow-pipe, we can apply our preimage attack with complexity $\tilde{O}(2^{5n/6})$. This does not violate the security proof because we need both functions to be narrow-pipe, hence not $n$-bit ideal<fnref n="12" />. From a practical point of view, though, it shows that in many cases (e.g. using SHA-512 and Whirlpool) the combiner is weaker than the initial functions.

## 6.3 Improvements using weaknesses of the hash functions

If $H_1$ or $H_2$ has known cryptographic weaknesses, more efficient attacks are possible. More precisely, if the compression function of one of the hash functions can be inverted<fnref n="13" /> in time $2^t$, then we can find a preimage of $H_1 \oplus H_2$ with complexity only $\tilde{O}(2^{(n+t)/2})$.

The attack is presented using the case, where (at least) one compression function is modeled as a weak compression function defined in [24], as an example. Without loss of the generality, we assume the compression function of $H_2$, $h_2(x, y) = z$, is such a weak compression function, which is a random oracle with two additional interfaces as below.

<footnote n="12">¹² A large multi-collisions can be built with a cost of roughly $2^{n/2}$ in a narrow-pipe function, but costs almost $2^n$ for an ideal hash function.</footnote>

<footnote n="13">¹³ finding an input chaining value from the output chaining value and the message</footnote>
*   **Backward interface.** On a query $(?, y, z)$, it returns either a value $x$ uniformly chosen from all the values satisfying $h_2(x, y) = z$, or $\perp$ if no such $x$ exists.

*   **Bridging interface.** On a query $(x, ?, z)$, it returns either a value $y$ uniformly chosen from all the values satisfying $h_2(x, y) = z$, or $\perp$ if no such $y$ exists.

Note that the inversion of compression function $h_2$ takes unit time and hence the attack against $H_1 \oplus H_2$ takes time $\tilde{O}(2^{n/2})$. The procedure is detailed as follows, which is also illustrated in Figure 6.

Let the target hash digest be denoted as $\overline{H}$. We firstly build an $n$-block long multicollision on $H_1$ following Joux's approach [20]. Let the final output be denoted as $Z$. It contains a set of up to $2^n$ messages that link $IV_1$ to $Z$ on $H_1$. We split every $n$-block long multicolliding message into halves, and collect the first half $n/2$-block long messages as a set $M_1$ and the second half as another set $M_2$. Hence for any message $M_1 \in M_1$ and any $M_2 \in M_2$, the concatenated message $M_1 \parallel M_2$ links $IV_1$ to $Z$ on $H_1$. Secondly, for the messages $M_2 \in M_2$, we use the additional backward interface of $h_2$ to carry out backward computations from $\overline{H} \oplus Z$, and get values $X$ such that $h_2^*(X, M_2) = \overline{H} \oplus Z$. We store $(X, M_2)$ in a table $T_X$. On average $T_X$ contains $2^{n/2}$ elements.<fnref n="14" /> Finally, for each message $M_1 \in M_1$, we iteratively compute $h_2$ forward from $IV_2$, and get an internal state $Y$. We match $Y$ to the elements in $T_X$. A match implies that concatenated $M_1 \parallel M_2$ links $IV_2$ to $\overline{H} \oplus Z$, and in turn is a preimage of $H_1(M_1 \parallel M_2) \oplus H_2(M_1 \parallel M_2) = Z \oplus \overline{H} \oplus Z = \overline{H}$. The success probability of finding such a match is not negligible since there are $2^{n/2}$ $X$'s and $Y$'s. The complexity is around $n \cdot 2^{n/2}$ that is $\tilde{O}(2^{n/2})$ by ignoring the polynomial factors.

<figure><img src="image_54.png" /><figcaption>**Fig. 6.** Preimage attack on the XOR combiner with a weak $H_2$</figcaption></figure>

Moreover, the above preimage attack can be extended to the concatenation
combiner $H_1 \parallel H_2$ if both $H_1$ and $H_2$ are weak by a minor modification. This

<footnote n="14">¹⁴ The backward interface may output $\perp$ for some message block. To compensate it, for the other message blocks, we make multiple queries, since they may have more than one preimages. On average, the backward interface should produce one preimage for each query.</footnote>
shows that the proof of Hoch and Shamir [17] is tight for preimage resistance. Here we mainly highlight the modifications. Let the target hash digest be $\overline{H}_1 \parallel \overline{H}_2$, where $\overline{H}_1$ is from $H_1$ and $\overline{H}_2$ from $H_2$. After we build the multicollision on $H_1$ and let the output internal state be denoted as $Z$, we link $Z$ to $\overline{H}_1$ by using the bridging interface of $h_1$ to receive a message $m$ such that $h_1(Z, m) = \overline{H}_1$. This gives us a set of messages linking $IV_1$ to $\overline{H}_1$ on $H_1$. Also note that for the backward computations on $H_2$, the starting value should be $\overline{H}_2$. The rest of the attack procedure remains the same. Hence it is easy to get that the complexity is also $\tilde{O}(2^{n/2})$.

## 6.4 Extension to the sum of three or more hash functions

The attack can be extended to the sum of three or more hash functions. In order to attack the sum of $k$ functions, two different strategies are possible: either we use a simpler structure that only gives two degrees of freedom, and fixes $k-2$ functions to a constant value, or we build an interchange structure to control all the $k$ functions independently.

**Controlling only two functions.** The easiest way to extend the attack is to use a single chain in the $k-2$ extra hash functions. The procedure to build a switch is modified in order to use multicollisions for $k-1$ functions instead a simple multicollisions for one function; this costs $O(n^{k-1} \cdot 2^{n/2})$ using Joux's method [20].

As in the basic attack, we need $O(t^2)$ switches to generate a $2^t$-interchange for two functions, and the preimage search costs $O(2^{n-t})$; the optimal complexity is therefore $O(n^{k-1} \cdot 2^{5n/6})$ with $t=n/6$.

**Controlling all the functions.** Alternatively, we can build a more complex interchange structure in order to control all the functions independently. When attacking three functions, we will use the switch structure to jump from chains $(a_{j_0}, b_{k_0}, c_{l_0})$ to $(a_{j_0}, b_{k_0}, c_{l_1})$ (or $(a_{j_0}, b_{k_1}, c_{l_0})$ or $(a_{j_1}, b_{k_0}, c_{l_0})$, respectively). We need $2^{3t}-1$ switches in the interchange structure to reach all the $2^{3t}$ triplets of chains (a switch makes only one new triplet reachable). Each switch is built using a $2^{n/2}$-multicollision on two functions, which can be built for a cost of $O(n^2 \cdot 2^{n/2})$ following Joux's technique [20]. Therefore we can build a $2^t$-interchange for a cost of $O(n^2 \cdot 2^{3t+n/2})$. More generally, for the sum of $k$ hash functions, we can build an interchange structure for $k$ functions for a cost of $O(n^{k-1} \cdot 2^{kt+n/2})$.

In the preimage search phase, we generate $k$ lists of size $2^t$, and we need to detect efficiently whether we can combine them to generate a zero sum. This problem can be solved using an algorithm similar to Wagner's generalized birthday algorithm [40]. If $k = 2^\kappa$, we find a solution with probability $O(2^{n-(\kappa+1)\cdot t})$ for a cost of $O(k \cdot 2^t)$. Therefore the preimage search costs $O(k \cdot 2^{n-\kappa t})$. With $k=4$ (i.e. $\kappa=2$), this yields a complexity of $O(n^3 \cdot 2^{5n/6})$. However, this approach is less efficient than the previous one for $k=3$ and for $k>4$.
To summarize, attacking the sum of $k$ hash functions ($k \ge 2$) costs $O(n^{k-1} \cdot 2^{5n/6})$. Controlling chains independently in more than two hash function might be useful for further work, but it doesn't improve the preimage attack on the sum of $k$ hash functions.

# 7 Conclusion and open discussions

In this work, we gave the first generic attack on the XOR combiner. Our result is rather surprising: the sum of two ideal narrow-pipe hash functions only has about $5n/6$ bits of security against preimage attacks. In particular, the sum is easier to break than the initial functions. Since most practical hash functions are narrow-pipe (e.g. SHA-1, SHA-256, SHA-512, Whirlpool, RIPEMD, GOST, BLAKE, Skein...), the XOR combiner will usually provide a weaker security than the component hash functions.

Moreover, we would like to discuss a few directions for future work.

**On controlling multiple hash lanes.** Since 2004, several generic attacks have been found against narrow-pipe hash functions, such as the multicollision attack [20], the long-message second preimage attack [22] and the herding attack [21]. There has been extensive work to extend these attacks to more complex constructions with several computation chains, such as the concatenation $H_1(M) \parallel H_2(M)$ and the cascade $H_2(H_1(M), M)$.

As in our present work, the essential difficulty in those attacks comes from the fact that several lanes of computation share the same input message, and hence their outputs are related. If an adversary considers a naïve set of messages, the set of outputs gives random pairs of $n$-bit values $\{(A_i, B_i) : i \in \mathcal{I}\}$: selecting a value for the first entry of the pair gives a single candidate for the second entry, and the adversary is essentially working with a $2n$-bit state. Previous works [33,16,2] have developed various message structures (mostly based on multicollision and diamond structures), in order to relax this relation. They mainly result in a set of messages $\mathcal{M}$ such that the corresponding outputs are in a more structured set $\{(A, B_i) : i \in \mathcal{I}\}$: the first entry is a constant value $A$, but several options $B_i$ can be selected for the second entry. For any value $(A, B_i)$, it is then possible to select a message in $\mathcal{M}$ so that the first lane reaches $A$, while the second lane reaches $B_i$. This allows to modify the value of the second lane without affecting the first lane.

Our result is quite stronger: with the interchange structure we have a set of message such that the corresponding outputs are a set $\{(A_i, B_j) : i \in \mathcal{I}, j \in \mathcal{J}\}$, where both lanes have several options that can be selected independently. We hope that our technique will have applications or lead to new technical development in related settings, e.g., the open problem of generic second preimage attacks (with long messages) on the concatenation hash or on the Zipper hash [24].
**On extending to practical hash function.** Several practical hash functions such as RIPEMD [10] and HAS-V [34] are based on a compression function with more than one independent lanes, which interacts with each other at the end of each compression function call. It is very interesting to investigate if our attack can be further modified to attack these hash functions in future. Again the obstacle comes from the relations between internal states of lanes. Particularly, the internal states of the lanes interact with each other, which makes the relation even tighter and in turn harder to attack.

## Acknowledgements

The authors would like to thank the anonymous referees for their helpful comments. Lei Wang is supported by the Singapore National Research Foundation Fellowship 2012 (NRF-NRFF2012-06).

## References

1. Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.): Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part II - Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, Lecture Notes in Computer Science, vol. 5126. Springer (2008)

2. Andreeva, E., Bouillaguet, C., Dunkelman, O., Kelsey, J.: Herding, Second Preimage and Trojan Message Attacks beyond Merkle-Damgård. In: Jr., M.J.J., Rijmen, V., Safavi-Naini, R. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 5867, pp. 393-414. Springer (2009)

3. Biham, E., Dunkelman, O.: A Framework for Iterative Hash Functions - HAIFA. IACR Cryptology ePrint Archive, Report 2007/278 (2007)

4. Boneh, D., Boyen, X.: On the Impossibility of Efficiently Combining Collision Resistant Hash Functions. In: Dwork, C. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 4117, pp. 570-583. Springer (2006)

5. Brassard, G. (ed.): Advances in Cryptology - CRYPTO '89, 9th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 1989, Proceedings, Lecture Notes in Computer Science, vol. 435. Springer (1990)

6. Cramer, R. (ed.): Advances in Cryptology - EUROCRYPT 2005, 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, May 22-26, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3494. Springer (2005)

7. Damgård, I.: A Design Principle for Hash Functions. In: Brassard [5], pp. 416-427

8. Dierks, T., Allen, C.: The TLS Protocol Version 1.0. RFC 2246 (Proposed Standard) (Jan 1999), http://www.ietf.org/rfc/rfc2246.txt, obsoleted by RFC 4346, updated by RFCs 3546, 5746, 6176

9. Dierks, T., Rescorla, E.: The Transport Layer Security (TLS) Protocol Version 1.2. RFC 5246 (Proposed Standard) (Aug 2008), http://www.ietf.org/rfc/rfc5246.txt, updated by RFCs 5746, 5878, 6176
10. Dobbertin, H., Bosselaers, A., Preneel, B.: RIPEMD-160: A Strengthened Version of RIPEMD. In: Gollmann, D. (ed.) FSE. Lecture Notes in Computer Science, vol. 1039, pp. 71–82. Springer (1996)

11. Fischlin, M., Lehmann, A.: Multi-property Preserving Combiners for Hash Functions. In: Canetti, R. (ed.) TCC. Lecture Notes in Computer Science, vol. 4948, pp. 375–392. Springer (2008)

12. Fischlin, M., Lehmann, A., Pietrzak, K.: Robust Multi-property Combiners for Hash Functions Revisited. In: Aceto et al. [1], pp. 655–666

13. Fischlin, M., Lehmann, A., Pietrzak, K.: Robust Multi-Property Combiners for Hash Functions. J. Cryptology 27(3), 397–428 (2014)

14. Freier, A., Karlton, P., Kocher, P.: The Secure Sockets Layer (SSL) Protocol Version 3.0. RFC 6101 (Historic) (Aug 2011), http://www.ietf.org/rfc/rfc6101.txt

15. Her, Y.S., Sakurai, K.: A Design of Cryptographic Hash Function Group with Variable Output-Length Based on SHA-1. Technical report of IEICE. ISEC 102(212), 69–76 (July 2002), http://ci.nii.ac.jp/naid/110003298501/en/

16. Hoch, J.J., Shamir, A.: Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions. In: Robshaw [37], pp. 179–194

17. Hoch, J.J., Shamir, A.: On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak. In: Aceto et al. [1], pp. 616–630

18. Hong, D., Chang, D., Sung, J., Lee, S., Hong, S., Lee, J., Moon, D., Chee, S.: A New Dedicated 256-Bit Hash Function: FORK-256. In: Robshaw [37], pp. 195–209

19. Indesteege, S.: The lane hash function. Submission to NIST (2008), http://www.cosic.esat.kuleuven.be/publications/article-1181.pdf

20. Joux, A.: Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions. In: Franklin, M.K. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 3152, pp. 306–316. Springer (2004)

21. Kelsey, J., Kohno, T.: Herding Hash Functions and the Nostradamus Attack. In: Vaudenay, S. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4004, pp. 183–200. Springer (2006)

22. Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2ⁿ Work. In: Cramer [6], pp. 474–490

23. Lehmann, A.: On the Security of Hash Function Combiners. Ph.D. thesis, TU Darmstadt (2010)

24. Liskov, M.: Constructing an Ideal Hash Function from Weak Ideal Compression Functions. In: Biham, E., Youssef, A.M. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 4356, pp. 358–375. Springer (2006)

25. Mendel, F., Nad, T., Scherz, S., Schläffer, M.: Differential attacks on reduced RIPEMD-160. In: Gollmann, D., Freiling, F.C. (eds.) ISC 2012. Lecture Notes in Computer Science, vol. 7483, pp. 23–38. Springer (2012)

26. Mendel, F., Peyrin, T., Schläffer, M., Wang, L., Wu, S.: Improved Cryptanalysis of Reduced RIPEMD-160. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT (2). Lecture Notes in Computer Science, vol. 8270, pp. 484–503. Springer (2013)

27. Mendel, F., Pramstaller, N., Rechberger, C., Rijmen, V.: On the collision resistance of RIPEMD-160. In: Katsikas, S.K., Lopez, J., Backes, M., Gritzalis, S., Preneel, B. (eds.) ISC 2006. Lecture Notes in Computer Science, vol. 4176, pp. 101–116. Springer (2006)

28. Mendel, F., Rechberger, C., Schläffer, M.: MD5 Is Weaker Than Weak: Attacks on Concatenated Combiners. In: Matsui, M. (ed.) ASIACRYPT. Lecture Notes in Computer Science, vol. 5912, pp. 144–161. Springer (2009)

29. Mennink, B., Preneel, B.: Breaking and Fixing Cryptopbia's Short Combiner. In: Gritzalis, D., Kiayias, A. (eds.) CANS. Lecture Notes in Computer Science (2014)
30. Merkle, R.C.: One Way Hash Functions and DES. In: Brassard [5], pp. 428–446

31. Mittelbach, A.: Hash Combiners for Second Pre-image Resistance, Target Collision Resistance and Pre-image Resistance Have Long Output. In: Visconti, I., Prisco, R.D. (eds.) SCN. Lecture Notes in Computer Science, vol. 7485, pp. 522–539. Springer (2012)

32. Mittelbach, A.: Cryptophia's Short Combiner for Collision-Resistant Hash Functions. In: Jr., M.J.J., Locasto, M.E., Mohassel, P., Safavi-Naini, R. (eds.) ACNS. Lecture Notes in Computer Science, vol. 7954, pp. 136–153. Springer (2013)

33. Nandi, M., Stinson, D.R.: Multicollision Attacks on Some Generalized Sequential Hash Functions. IEEE Transactions on Information Theory 53(2), 759–767 (2007)

34. Park, N.K., Hwang, J.H., Lee, P.J.: HAS-V: A New Hash Function with Variable Output Length. In: Stinson, D.R., Tavares, S.E. (eds.) Selected Areas in Cryptography. Lecture Notes in Computer Science, vol. 2012, pp. 202–216. Springer (2000)

35. Pietrzak, K.: Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don't Exist. In: Naor, M. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4515, pp. 23–33. Springer (2007)

36. Rjasko, M.: On Existence of Robust Combiners for Cryptographic Hash Functions. In: Vojtás, P. (ed.) ITAT. CEUR Workshop Proceedings, vol. 584, pp. 71–76. CEUR-WS.org (2009)

37. Robshaw, M.J.B. (ed.): Fast Software Encryption, 13th International Workshop, FSE 2006, Graz, Austria, March 15-17, 2006, Revised Selected Papers, Lecture Notes in Computer Science, vol. 4047. Springer (2006)

38. Sasaki, Y., Wang, L.: Distinguishers beyond Three Rounds of the RIPEMD-128/-160 Compression Functions. In: Bao, F., Samarati, P., Zhou, J. (eds.) ACNS. Lecture Notes in Computer Science, vol. 7341, pp. 275–292. Springer (2012)

39. Shoup, V. (ed.): Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, California, USA, August 14-18, 2005, Proceedings, Lecture Notes in Computer Science, vol. 3621. Springer (2005)

40. Wagner, D.: A Generalized Birthday Problem. In: Yung, M. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 2442, pp. 288–303. Springer (2002)

41. Wang, X., Yin, Y.L., Yu, H.: Finding Collisions in the Full SHA-1. In: Shoup [39], pp. 17–36

42. Wang, X., Yu, H.: How to Break MD5 and Other Hash Functions. In: Cramer [6], pp. 19–35

## A Optimized Interchange Structure

We now describe an optimized attack using only $(2^t - 1)(2^t - 1)$ switches rather than $2^{2t} - 1$. The attack also requires multicollision structures, as introduced by Joux[20].

We replace the first $2^t - 1$ switches with a $2^t$-multicollision in $H_1$, and we use those messages to initialize all the $b_k$ chains in $H_2$. We can also optimize the first series of switches in $H_2$ in the same way: we build a $2^t$-multicollision in $H_2$ starting from $b_0$, and we use those messages to initialize the $a_j$ chains in $H_1$. This is illustrated by Figure 7, and the detailed attack is given as Algorithm 3.
<caption>**Algorithm 3 Optimized T-interchange structure**</caption>

**function** INTERCHANGE($h_1, h_2, IV_1, IV_2, T$)
    $a_0 \leftarrow IV_1, b_0 \leftarrow IV_2$
    $\mathcal{M}_0 \leftarrow \text{MULTICOLLISION}(h_1, a_0)$
    **for** $0 \le k < T$ **do**
        $b_k \leftarrow h_2^*(b_0, \mathcal{M}_0[k])$
    **end for**
    $a_0 \leftarrow h_1^*(a_0, \mathcal{M}_0[0])$
    $\mathcal{M}_1 \leftarrow \text{MULTICOLLISION}(h_2, b_0)$
    **for** $1 \le k < T$ **do**
        $a_k \leftarrow h_2^*(a_0, \mathcal{M}_1[k])$
    **end for**
    $a_0 \leftarrow h_2^*(a_0, \mathcal{M}_1[0])$
    $b_0 \leftarrow h_1^*(b_0, \mathcal{M}_1[0])$
    **for** $2 \le j < T$ **do**
        **for** $1 \le i < T$ **do**
            $(M, M') \leftarrow \text{SWITCH}(h_2, h_1, b_j, a_0, a_i)$
            $\mathcal{M} \leftarrow \mathcal{M} \parallel M$; $M' \leftarrow \mathcal{M}' \parallel M'$
            **for** $0 \le k < T$ **do**
                $a_k \leftarrow h_1^*(a_k, M)$
                $b_k \leftarrow h_2^*(b_k, M)$
        **end for**
    **end for**
    $\text{return } (\mathcal{M}_0, \mathcal{M}_1, M, M')$

**end function**

**function** SELECTMESSAGE($\mathcal{M}_0, \mathcal{M}_1, M, M', j, k$)
    **if** $j = 0$ **then**
        **return** $\mathcal{M}_0[k] \parallel \mathcal{M}_1[0] \parallel M$
    **else if** $k = 0$ **then**
        **return** $\mathcal{M}_0[0] \parallel \mathcal{M}_1[j] \parallel M$
    **else**
        $\mu \leftarrow M$
        $\mu[(k-1) \cdot (T-1) + j - 1] \leftarrow M'[(k-1) \cdot (T-1) + j - 1]$
        **return** $\mathcal{M}_0[k] \parallel \mathcal{M}_1[0] \parallel \mu$

**end if**

**end function**

**function** MULTICOLLISION($h, x$)
    $\mathcal{M} \leftarrow \{\}$
    **for** $0 \le i < n/2$ **do**
        $(m, m') \leftarrow \text{COLLISION}(h, x)$
        $x \leftarrow h(x, m)$
        $\mathcal{M} \leftarrow (\mathcal{M} \parallel m) \cup (\mathcal{M} \parallel m')$

**end for**

**return** $\mathcal{M}$

**end function**
<figure><img src="image_55.png" /><figcaption>Fig. 7. Optimized interchange structure</figcaption></figure>
Generic Attacks on Hash Combiners

Zhenzhen Bao<fnref n="1" />,<fnref n="2" />, Itai Dinur<fnref n="3" />, Jian Guo<fnref n="1" />, Gaëtan Leurent⁴, and Lei Wang<fnref n="5" />,<fnref n="6" />

**Abstract.** Hash combiners are a practical way to make cryptographic hash functions more tolerant to future attacks and compatible with existing infrastructure. A combiner combines two or more hash functions in a way that is hopefully more secure than each of the underlying hash functions, or at least remains secure as long as one of them is secure. Two classical hash combiners are the exclusive-or (XOR) combiner $H_1(M) \oplus H_2(M)$ and the concatenation combiner $H_1(M) \parallel H_2(M)$. Both of them process the same message using the two underlying hash functions in parallel. Apart from parallel combiners, there are also cascade constructions sequentially calling the underlying hash functions to process the message repeatedly, such as Hash-Twice $H_2(H_1(IV, M), M)$ and the Zipper hash $H_2(H_1(IV, M), \overleftarrow{M})$, where $\overleftarrow{M}$ is the reverse of the message $M$.

In this work, we study the security of these hash combiners by devising the best-known generic attacks. The results show that the security of most of the combiners is not as high as commonly believed. We summarize our attacks and their computational complexities (ignoring the polynomial factors) as follows:

1. Several generic preimage attacks on the XOR combiner:

- A first attack with a best-case complexity of $2^{5n/6}$ obtained for messages of length $2^{n/3}$. It relies on a novel technical tool named Interchange Structure. It is applicable for combiners whose underlying hash functions follow the Merkle-Damgård construction or the HAIFA framework.

- A second attack with a best-case complexity of $2^{2n/3}$ obtained for messages of length $2^{n/2}$. It exploits properties of functional graphs of random mappings. It achieves a significant improvement over

<footnote n="1">¹ Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore
baozhenzhen10@gmail.com, guojian@ntu.edu.sg</footnote>

<footnote n="2">² Strategic Centre for Research in Privacy-Preserving Technologies and Systems, Nanyang Technological University, Singapore</footnote>

<footnote n="3">³ Department of Computer Science, Ben-Gurion University, Israel
dinuri@cs.bgu.ac.il
⁴ Inria, France
gaetan.leurent@inria.fr</footnote>

<footnote n="5">⁵ Shanghai Jiao Tong University, Shanghai, China</footnote>

<footnote n="6">⁶ Westone Cryptologic Research Center, Beijing, China
wanglei_hb@sjtu.edu.cn</footnote>

<footnote n="8">⁸ This paper is a combination and extension of three conference papers [LW15,Din16,BWGG17].</footnote>
the first attack but is only applicable when the underlying hash
functions use the Merkle-Damgård construction.

- An improvement upon the second attack with a best-case complexity of $2^{5n/8}$ obtained for messages of length $2^{5n/8}$. It further exploits properties of functional graphs of random mappings and uses longer messages.

These attacks show a rather surprising result: regarding preimage
resistance, the sum of two *n*-bit narrow-pipe hash functions following
the considered constructions can never provide *n*-bit security.

2. A generic second-preimage attack on the concatenation combiner of two Merkle-Damgård hash functions. This attack finds second preim-ages faster than $2^n$ for challenges longer than $2^{2n/7}$ and has a best-case complexity of $2^{3n/4}$ obtained for challenges of length $2^{3n/4}$. It also exploits properties of functional graphs of random mappings.

3. The first generic second-preimage attack on the Zipper hash with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{3n/5}$, obtained for challenge messages of length $2^{2n/5}$.

4. An improved generic second-preimage attack on Hash-Twice with underlying hash functions following the Merkle-Damgård construction. The best-case complexity is $2^{13n/22}$, obtained for challenge messages of length $2^{13n/22}$.

The last three attacks show that regarding second-preimage resistance, the concatenation and cascade of two *n*-bit narrow-pipe Merkle-Damgård hash functions do not provide much more security than that can be provided by a single *n*-bit hash function.

Our main technical contributions include the following:

1. The interchange structure, which enables simultaneously controlling the behaviours of two hash computations sharing the same input.

2. The simultaneous expandable message, which is a set of messages of length covering a whole appropriate range and being multi-collision for both of the underlying hash functions.

3. New ways to exploit the properties of functional graphs of random mappings generated by fixing the message block input to the underlying compression functions.

**Keywords:** Hash function, Generic attack, Hash combiner, XOR combiner, Concatenation combiner, Zipper hash, Hash-Twice, (Second) Preimage attack

# 1 Introduction

A cryptographic hash function $\mathcal{H} : \{0,1\}^* \rightarrow \{0,1\}^n$ maps arbitrarily long messages to *n*-bit digests. It is a fundamental primitive in modern cryptography and is among the main building blocks of many widely utilized cryptographic protocols and cryptosystems. There are three *basic* security requirements on a hash function $\mathcal{H}$:
- **Collision resistance:** It should be computationally infeasible to find a pair of different messages $M$ and $M'$ such that $\mathcal{H}(M) = \mathcal{H}(M')$.

- **Preimage resistance:** Given an arbitrary $n$-bit value $V$, it should be computationally infeasible to find any message $M$ such that $\mathcal{H}(M) = V$.

- **Second-preimage resistance:** Given a challenge message $M$, it should be computationally infeasible to find any different message $M'$ such that $\mathcal{H}(M) = \mathcal{H}(M')$.

As the birthday and brute-force attack requires $2^{n/2}$ and $2^n$ computations, respectively, to find a collision and a (second) preimage, a secure hash function is expected to provide the same level of resistance.

Unfortunately, widely deployed standards (such as MD5 and SHA-1) fail to provide the expected resistance because of cryptographic weaknesses [WYY05,WY05]. Moreover, Kelsey and Schneier have demonstrated a generic second-preimage attack against all hash functions based on the classical Merkle-Damgård construction (such as MD5, SHA-1, and SHA-2) when the challenge message is long [KS05]. As a result, countermeasures have been proposed in order to build more tolerant hash functions, and to protect oneself against future attacks, while keeping the same interface for compatibility. A practical way is to combine the outputs of two (or more) independent hash functions to provide better security in case one or even both hash functions are weak. In particular, this reasoning was used by the designers of SSL [FKK11] and TLS [DA99b], who combined MD5 and SHA-1 in various ways. More precisely, the Key Derivation Function of TLS v1.0/v1.1 uses a sum of HMAC-MD5 and HMAC-SHA-1.<fnref n="7" /> The designers explain [DA99b], “In order to make the PRF as secure as possible, it uses two hash algorithms in a way which should guarantee its security if either algorithm remains secure.” Formally, we call the resulting construction a *hash function combiner* (or combiner for short). The goal of a hash combiner is to achieve *security amplification*, i.e., the hash combiner has higher security than its underlying hash functions, or to achieve *security robustness*, i.e., the hash combiner is secure as long as (at least) one of its underlying hash functions is secure.

There are two classical hash combiners, the concatenation combiner and the exclusive-or (XOR) combiner. Both of them process the same message using two (independent) hash functions $\mathcal{H}_1$ and $\mathcal{H}_2$ in parallel. Then, the former concatenates their outputs, $\mathcal{H}_1(M) \parallel \mathcal{H}_2(M)$, and the latter XORs them, $\mathcal{H}_1(M) \oplus \mathcal{H}_2(M)$. More generally<fnref n="8" />, cryptographers have also studied cascade constructions of two (or more) hash functions, that is, to compute $\mathcal{H}_1$ and $\mathcal{H}_2$ in sequential order. Examples are Hash-Twice, $\mathcal{H}(M) \triangleq \mathcal{H}_2(\mathcal{H}_1(IV, M), M)^9$, and the Zipper hash [Lis06], $\mathcal{H}_2(\mathcal{H}_1(IV, M), \overleftarrow{M})$, where $\overleftarrow{M}$ is the message with the same blocks as $M$ but in reversed order. Such kinds of cascade constructions

<footnote n="7">⁷ We note that this MD5/SHA-1 combiner has been replaced by primitives based on single hash function (e.g., SHA-256) since TLS v1.2 [DR08].</footnote>

<footnote n="8">⁸ Here, we generalize the syntax of hash functions to also regard the initial value $IV$ as an input parameter.</footnote>

<footnote n="9">⁹ The original specification of Hash-Twice is $\mathcal{H}(M) \triangleq \mathcal{H}(\mathcal{H}(IV, M), M)$, which processes the same message twice using a single hash function as shown in [ABDK09].</footnote>
are not strictly black-box hash combiners compared with the XOR combiner and the concatenated combiner. That is because the initial vector of the subsequent hash functions are not fixed as in their specifications. Instead, for such constructions, to get black-box access to the underlying hash functions, the initial vector of these hash functions is required to be an input parameter. However, apart from this point, other parts of the hash functions are all accessed as black boxes by the constructions. Considering that such constructions can be classified into the method of designing hash functions using multiple existing hash functions, and for the sake of conciseness, we regard these cascade constructions of hash functions as hash combiners in this paper. In the sequel, for these combiners, we call the computation of the first (resp. the second) hash function the first (resp. the second) computation pass (or simply, the first pass, resp. the second pass).

In this paper, we study the security of these hash combiners. We focus on combiners of iterated hash functions. Iterated hash functions commonly first pad and split the message $M$ into message blocks of fixed length (e.g., b-bit), i.e., $M = m_1 \parallel m_2 \parallel \dots \parallel m_L$. They then process message blocks by iteratively applying a series of compression function $h_i$. Those compression functions update an internal state, initialized with a public value $IV$, using the previous state value and the current message block, i.e., $x_i = h_i(x_{i-1}, m_i)$. Finally, the internal state is updated by a finalization function which can be either the compression function or another independent function, and the output of the finalization function is outputted as the hash digest. For simplicity of description, we assume that the finalization function is the same as the compression function in the rest of the paper, but we stress that our attacks also work in a straightforward way with an independent finalization function. In this work, we mainly focus on hash functions whose internal state size is equal to its output size, which are known as “narrow-pipe” designs. We will discuss the applicability of our proposed attacks on “wide-pipe” designs whose internal state size is (not much) larger than its output size at the end of the paper. In particular, we consider hash functions following the classical Merkle-Damgård construction [Dam89,Mer89] and the more general HAIFA framework [BD07], for which we naturally take the length padding mentioned next as the message padding scheme. The Merkle-Damgård construction (MD) applies the same compression function $h$ in all iterations (see Fig. 1) and adds a padding of the message length to the final message block (known as length padding, or Merkle-Damgård strengthening). The HAIFA framework is similar to the MD construction but uses extra inputs to the compression function with the number of message bits hashed so far and a salt value; this is equivalent to using a different compression function for each block. The primary goal of that construction is to thwart some narrow-pipe attacks (e.g., Kelsey and Schneier’s long message second-preimage attack on MD hash [KS05]). HAIFA framework is formally defined as follows:<fnref n="10" />

$$x_0 = IV \quad x_i = h(x_{i-1}, m_i, \#\text{bits}, \text{salt}) \quad \mathcal{H}(M) = h(x_{L-1}, m_L).$$

<footnote n="10">¹⁰ For simplicity of description, we omit the computation of the initial value $IV_n = h(IV, n, 0, 0)$, which is used to support variable hash size in the specification of HAIFA in [BD07]. This does not influence the attacks.</footnote>
<figure><img src="image_56.png" /><figcaption>Fig. 1: Narrow-pipe Merkle-Damgård hash function</figcaption></figure>

## 1.1 Related Works

Combiners have been studied in several settings, including generic attacks and security proof. For generic attacks, the compression functions are modelled as random functions to devise attacks that do not use any weakness of the compression function. Thus, they provide upper bounds on the security of the combiners.

Security proof, which is more theoretical work, focuses on the notion of robustness and security amplification. A robust combiner is secure regarding property $\alpha$ as long as one of the underlying hash functions is secure regarding $\alpha$. Lines of research for those security notions include the study of advanced combiners in [Her05,CRS+07,FL07,FL08,FLP08,Her09,Leh10,FLP14]. A series of studies on the minimum output length of robust combiners have shown that robust combiners for collision resistance and preimage resistance cannot have an output length significantly shorter than the sum of the output length of the underlying hash functions [BB06,Pie07,Pie08,Rja09] (more recent works include [MP14,Mit12]).

There are also some works that assume that the compression function is a weak random oracle (i.e., the attacker is given additional interfaces to receive random preimages of the compression functions) and prove that some constructions are still secure in this model [Lis06,HS08] or provide efficient attacks on the combiners by exploiting weakness of the underlying hash functions [CJ15,JN15].

**Analysis of the concatenation combiner.** The concatenation combiner $H_1(M) \parallel H_2(M)$ (see Fig. 2) is probably the most well-known and most studied hash combiner. This combiner was described already in 1993 [Pre93].

<figure><img src="image_57.png" /><figcaption>Fig. 2: The concatenation combiner</figcaption></figure>
*Generic attacks.* In 2004, Joux [Jou04] described surprising attacks on the concatenation of two narrow-pipe iterated hash functions using multi-collisions: while the output size is $2n$ bits, the concatenation combiner merely provides at most $n/2$-bit security for collision resistance and $n$-bit security for preimage resistance$^{11}$ (see Sect. 2.1 for a description). In particular, the concatenation combiner is not security-amplifying (it does not increase collision and preimage resistance).

Following the results of Joux (which showed that the concatenation combiner does not increase collision and preimage resistance) and the later results of Kelsey and Schneier (which showed that the second-preimage resistance of the MD construction is less than $2^n$), a natural question is whether there exists a second-preimage attack on the concatenation combiner of MD hash functions that is faster than $2^n$. Interestingly, the problem of devising such an attack remained open for a long time despite being explicitly mentioned in several papers including [DP07]. In fact, although the works of [Jou04,KS05] have attracted a significant amount of follow-up research on countermeasures against second-preimage attacks (such as Hash-Twice or dithered hash) and attacks that break them [ABD$^+$16,ABDK09,ABF$^+$08], there has been no progress concerning second-preimage attacks on the basic concatenation combiner. In this paper, we try to provide an answer to this question by devising the first second-preimage attack on the concatenation combiner of MD hash functions, which is faster than $2^n$.

*Security proof.* From the theoretical side, the concatenation combiner is robust for collision resistance, e.g., a collision $H_1(M) \parallel H_2(M) = H_1(M') \parallel H_2(M')$ implies $H_1(M) = H_1(M')$ and $H_2(M) = H_2(M')$.

Hoch and Shamir [HS08] evaluated the security of the concatenation combiner with two weak hash functions. More precisely, the two hash functions are narrow-pipe MD, and the compression functions are modelled as weak random oracles (as defined by Liskov [Lis06]), i.e., the adversary is given additional interfaces to receive (random) preimages of the compression functions. They have proven that in this model, the concatenation combiner is still indifferentiable from a random oracle with $n/2$-bit security, implying (at least) the same security bound for collision resistance and preimage resistance. The bound is matched by Joux's attack for collisions, but there is a gap with Joux's attack for preimages, with complexity $2^n$, which might be interesting to investigate further.

*Analysis of dedicated instantiations.* Mendel et al. analysed some dedicated instantiations of the concatenation combiner [MRS09], in particular using the hash function MD5. We omit the details and refer interested readers to [MRS09].

**Analysis of the XOR combiner.** The XOR combiner $H_1(M) \oplus H_2(M)$ (see Fig. 3) has received less analysis.

<footnote n="11">11 The attacks essentially only require one of the functions to be iterated.</footnote>
<figure><img src="image_58.png" /><figcaption>Fig. 3: The XOR combiner</figcaption></figure>

*Generic attacks.* To the best of our knowledge, no preimage attacks have been shown against the XOR combiner. Therefore, the preimage security of the XOR combiner against generic attacks is still an open problem and will be one of the main topics of our work.

*Security proof.* Theoretically, the XOR combiner is robust concerning PRF (Pseudo-Random Function) and MAC (Message Authentication Code) in the black-box reduction model [Leh10]. Since the XOR combiner is length-preserving, from the conclusions regarding the minimum output length of robust combiners, it is not robust for collision resistance and preimage resistance. However, the work of Hoch and Shamir [HS08] actually proves the security of the XOR combiner as an intermediate result: it is also indifferentiable from a random oracle up to $2^{n/2}$ queries in the weak random oracle model. In particular, this proves there are no generic attacks with complexity less than $2^{n/2}$. For collision resistance, the bound is tight, since it is matched with the generic birthday attack bound. On the other hand, for preimage resistance, there exists a gap between the $n/2$-bit proven bound and the $n$-bit expected ideal security bound. Note that the non-robustness result regarding preimage security does not imply that the XOR of two concrete hash functions is weak, and the simplicity and short output of this construction still make it quite attractive.

**Analysis of Hash-Twice.** Hash-Twice is a folklore hash construction that hashes a (padded) message twice, with the output of the first hash value as the value of the initialization vector of the second hash. In its original definition [ABDK09], the two underlying hash functions are identical, i.e., $\mathcal{H}\mathcal{T}(M) \triangleq \mathcal{H}(\mathcal{H}(IV, M), M)$; here, we consider a generalized version, where the underlying hash functions are independent, i.e., $\mathcal{H}\mathcal{T}(M) \triangleq \mathcal{H}_2(\mathcal{H}_1(IV, M), M)$ (see Fig. 4).

<figure><img src="image_59.png" /><figcaption>Fig. 4: The Hash-Twice</figcaption></figure>

*Generic attacks.* Towards the three basic security requirements, a second-preimage attack on Hash-Twice ($\mathcal{H}\mathcal{T}(M) \triangleq \mathcal{H}(\mathcal{H}(IV, M), M)$) has been published by An-
dreeva et al. in [ABDK09]. The attack is based on a herding attack, which exploits the diamond structure originally used in the herding attack on a single hash function [KK06] (see Sect. 2.3 for an introduction). The complexity of the attack is approximately $2^{(n+t)/2} + 2^{n-\ell} + 2^{n-t}$, where $2^t$ is the width of the diamond structure, and $2^\ell$ is the length of the challenge.

*Security proof.* To the best of our knowledge, there is no published formal proof regarding the security of Hash-Twice. However, we can claim that they are at least as secure as the original functions: a generic collision attack requires at least $2^{n/2}$ (because we need a collision in one of the compression functions); a preimage attack requires at least $2^n$ (because we need a preimage for the finalization function); a second-preimage requires at least $2^{n/2}$ (because it implies a collision).

**Analysis of the Zipper hash.** The Zipper hash has been proposed with the goal of constructing an ideal hash function from weak ideal compression functions (by “weak ideal”, it means that the compression function is vulnerable to strong forms of attack but is otherwise random). Similar to Hash-Twice, it cascades two independent hash functions evaluating the same (padded) message. The difference is that the second hash processes the message blocks in reverse order, i.e., $ZH \triangleq H_2(H_1(IV_1, M), \overleftarrow{M})$ (see Fig. 5). Note that the messages are first padded by a padding scheme and split into message blocks, and then they are processed in forward and reverse order sequentially. Thus, the padded message block $m_L$ is processed at the end of the first hash computation and at the beginning of the second hash computation, i.e., in the middle of the whole processing procedure. The padding scheme of Zipper was specified to be any injective function of the message [Lis06]. In this paper, and as for all other combiners, we take the length padding of the MD construction as the padding scheme.

<figure><img src="image_60.png" /><figcaption>Fig. 5: The Zipper hash</figcaption></figure>

*Generic attacks.* To the best of our knowledge, no generic attacks on the Zipper hash regarding the three basic security notions have been shown. However, there are a number of works that consider other security notions, such as multi-collision, herding attack or attacks assuming weak compression functions. Examples include [NS07,HS06,ABDK09,CJ15,JN15], some of which also consider the corresponding security of Hash-Twice.
*Security proof.* Zipper hash is proved ideal in the sense that the overall hash function is indistinguishable from a random oracle (up to the birthday bound) when instantiated with weak ideal compression functions. More precisely, its provable security is $2^{\min(b,n)/2}$ for collision resistance and $2^{\min(b,n)}$ for (second-) preimage resistance, where *b* is the size of the message block and *n* is the size of the internal state and the hash value (considering “narrow-pipe” design).

## 1.2 Our Results

In this work, we study the upper bound of the security of these hash combiners by devising the best-known generic preimage attacks and second-preimage attacks with a long challenge. We do not assume any weakness of the compression functions, i.e., they are accessed as black boxes in our attacks. The compression functions are chosen uniformly at random from all $n+b$ to $n$-bit functions, which implies that our analysis applies to most compression functions. Table 1 summarizes the updated security status of various hash combiners after integrating our new results. It shows that the security of most combiners is not as high as commonly believed. Regarding certain basic security requirements, these combiners of two (or even more) $n$-bit hash functions fail to provide more (or even the same) security than that provided by a single $n$-bit ideal hash function.

Next, we briefly introduce our main attacks on combiners of two narrow-pipe hash functions and their computational complexities (ignoring the polynomial factors). In addition to the attacks summarized next, we also present improved but more complex attacks and apply our techniques to attack combiners of more than two hash functions.

**Preimage attacks on the XOR combiner.** We present several generic attacks:

- A first attack with a best-case complexity of $2^{5n/6}$ computations obtained for messages of length $2^{n/3}$. This attack involves a meet-in-the-middle procedure enabled by building a novel technical tool named *interchange structure*. This structure consists of a sequence of basic building modules named *switches* among different hash computation lanes such that it breaks the pairwise dependency between the internal states of these hash computations on the same message. This attack is applicable for the XOR combiner with underlying hash functions following a wide range of iterated constructions (e.g., the classical MD construction and the more general HAIFA framework) and for the Cryptophia's short combiner [Mit13,MP14].

- A second attack with a best-case complexity of $2^{2n/3}$ computations obtained for messages of length $2^{n/2}$. This attack also involves a meet-in-the-middle procedure, but instead of using the interchange structure, it exploits properties of functional graphs of random mappings. The random mappings are generated by fixing the message block input to the underlying compression functions. The functional graphs of these random mappings are formed by
successive iteration of the mappings, whose nodes are all possible values of input/output and whose edges are all from preimages to images. We exploited special nodes that are images of a large number of iterations of the mappings. We named them *deep iterates* because they are located at deep strata in the functional graphs. By exploiting such deep iterates, the variability of the number of iterations provides extra freedom to find a linking message fragment mapping a pair of starting states to a predefined pair of states. When using this freedom, to overcome the hurdle set by the length padding, we construct a structure named *simultaneous expandable message*, which is a set of messages of length covering a whole appropriate range and being multi-collisions for both of the underlying hash functions. This attack achieves a trade-off of $2^n \cdot L^{-2/3}$ between the maximal allowed message length $L$ and the time complexity of attack. This improves the trade-off of $2^n \cdot L^{-1/2}$, obtained by the first interchange-structure-based attack. On the other hand, it only applies when both underlying hash functions combined use the MD construction.

- *An improvement upon the second attack with a best-case complexity of $2^{5n/8}$ obtained for messages of length $2^{5n/8}$. In this attack, we exploit more special nodes in functional graphs of random mappings, which are called cyclic nodes, and we utilize a technique named *multi-cycles*. Linking pairs of states through cyclic nodes and allowing to loop around the cycles makes the attack more efficient. The complexity improvement of the resulting preimage attack is $2^{n/24}$. We point out that this attack has the limitation that the length of the message must be at least $2^{n/2}$ blocks. Therefore, its practical impact is limited and its main significance is theoretical. This attack shows that the security level regarding preimage resistance of the XOR combiner is quite close to the provable security level $2^{n/2}$, which is also the level of collision resistance.*

These attacks on the XOR combiner show a rather surprising result – regarding preimage resistance, the sum of two *n*-bit iterated hash functions can never provide *n*-bit security. In general, the sum is *weaker* than each of the two hash functions.

**Second-preimage attack on the concatenation combiner.** We describe the first generic second-preimage attack faster than $2^n$ on the concatenation combiner of two MD hash functions. The general framework follows that of the long message second-preimage attack on a single MD hash [KS05]. It is faster than $2^n$ computations by overcoming two main challenges. The first is to overcome the length padding. We solve this by using the *simultaneous expandable message*. The second is to speed up the connection from a crafted message to the challenge message on chaining states. In the case of hash combiners, one must connect to the challenge message on a pair of *n*-bit states, while in the second-preimage attack on a single MD hash, one needs only to connect on a single *n*-bit state. Thus, the attempt is essentially to reach a *2n*-bit state (in a set of $L$ states, where $L$ is the message length in blocks, and thus $L < 2^n$) faster than
$2^n$ computations. We solve this by exploiting again deep iterates in functional graphs. In this attack, we choose a pair of deep iterates as target chaining states, such that the connection from our crafted message to the challenge message is more efficient. Indeed, this attack is closely related with our deep-iterates-based preimage attack on the XOR combiners.

We obtain a trade-off between the complexity of the attack and the length of the challenge message. This second-preimage attack is faster than $2^n$ for input messages of length at least $2^{2n/7}$. The best-case complexity$^{13}$ is $2^{3n/4}$, obtained for (very) long challenges of length $2^{3n/4}$. Again, due to these constraints, the practical impact of our second-preimage attack is limited and its main significance is theoretical. Namely, it shows that regarding second-preimage resistance, the concatenation of two $n$-bit MD hash functions is not as strong as a single $n$-bit ideal hash function.

**Second-preimage attack on the Zipper hash.** We show the first generic second-preimage attack on the Zipper hash. This attack combines multiple tools, including Joux's multi-collision, the simultaneous expandable message, deep iterates and multi-cycles in functional graph of random mappings. The general framework is similar to that of above ones on combiners of MD hashes. However, some special specifications of the Zipper hash allow the attacker to choose an optimal configuration on message length for the attack, and to launch a more efficient meet-in-the-middle connecting procedure in the attack. The best-case complexity of this attack is $2^{3n/5}$, obtained for challenge message of length $2^{2n/5}$. This result shows that combination of two MD hash functions using a Zipper can be vulnerable to second-preimage attack with long challenges.

**Second-preimage attack on Hash-Twice.** We give an improved second-preimage attack on Hash-Twice. This attack also combines multiple tools including Joux's multi-collision, the diamond structure, the interchange structure, the simultaneous expandable message, deep iterates and multi-cycles in functional graphs. Like all our previous functional-graph-based attacks, it improves a previous attack from [ABDK09] because of the efficiency brought by exploiting the special nodes in the functional graphs. The best-case complexity of this attack is $2^{13n/22}$, obtained for challenge message of length $2^{13n/22}$. This attack shows that regarding second-preimage resistance, hashing a message twice using two Merkle-Damgård hash functions does not provide much more security compared with hashing the message only once.

Finally, we highlight the technical interests of this paper. We believe that the tools introduced in this paper – the interchange structure, the simultaneous expandable message, deep iterates and multi-cycles in random functional

<footnote>$^{12}$ For example, for $n = 160$ and message block of length 512 bits (as in SHA-1), the attack is faster than $2^{160}$ for messages containing at least $2^{46}$ blocks, or $2^{52}$ bytes.</footnote>

<footnote>$^{13}$ The complexity formulas do not take into account (small) constant factors, which are generally ignored throughout this paper.</footnote>
graphs – are important technical advances and will hopefully have further applications or lead to new technical developments in related settings. Particularly, we point out that we can use the interchange structure in order to optimize the complexity of functional-graph-based attacks on the XOR combiner, concatenation combiner, and Hash-Twice. Although this does not lead to a very big improvement, it further demonstrates the wide applicability of this structure in cryptanalysis of hash function combiners.

<table><thead><tr><th colspan="2">H</th><th colspan="2">Collision</th><th colspan="2">Preimage</th><th colspan="2">2nd Preimage (challenge length)</th></tr></thead><tbody><tr><td>Ideal</td><td>2<sup>0.5n</sup></td><td>Birthday</td><td>2<sup>n</sup></td><td>Brute-force</td><td>2<sup>n</sup></td><td>Brute-force</td><td></td></tr><tr><td>HAIFA</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td></td></tr><tr><td>MD</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.5n</sup></td><td>[KS05] DS</td><td>(2<sup>0.5n</sup>)</td></tr><tr><td>Provable</td><td>2<sup>0.5n</sup></td><td></td><td>2<sup>n</sup></td><td></td><td>2<sup>0.5n</sup></td><td></td><td></td></tr></tbody></table><table><thead><tr><th colspan="2">H<sub>1</sub> ⊕ H<sub>2</sub></th><th colspan="2">Collision</th><th colspan="2">Preimage</th><th colspan="2">2nd Preimage</th></tr></thead><tbody><tr><td>Ideal</td><td>2<sup>0.5n</sup></td><td>Birthday</td><td>2<sup>n</sup></td><td>Brute-force</td><td>2<sup>n</sup></td><td>Brute-force</td><td></td></tr><tr><td>HAIFA</td><td>-</td><td>-</td><td>2<sup>0.833n</sup></td><td>[Sect. 3.1] IS</td><td></td><td></td><td></td></tr><tr><td rowspan="6">MD</td><td>-</td><td>-</td><td>2<sup>0.833n</sup></td><td>[Sect. 3.1] IS</td><td></td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>2<sup>0.667n</sup></td><td>[Sect. 4.1] SEM+FGDI</td><td></td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>2<sup>0.643n</sup></td><td>[Sect. 4.3] SEM+FGDI+IS</td><td></td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>2<sup>0.625n</sup></td><td>[Sect. 5.2] SEM+FGMC</td><td></td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>2<sup>0.612n</sup></td><td>[Sect. 5.3] SEM+FGMC+IS</td><td></td><td></td><td></td></tr><tr><td>Provable</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td></td></tr></tbody></table><table><thead><tr><th colspan="2">H<sub>1</sub> || H<sub>2</sub></th><th colspan="2">Collision</th><th colspan="2">Preimage</th><th colspan="2">2nd Preimage (challenge length)</th></tr></thead><tbody><tr><td>Ideal</td><td>2<sup>n</sup></td><td>Birthday</td><td>2<sup>2n</sup></td><td>Brute-force</td><td>2<sup>2n</sup></td><td>Brute-force</td><td></td></tr><tr><td>HAIFA</td><td>2<sup>0.5n</sup></td><td>[Jou04] MC</td><td>2<sup>n</sup></td><td>[Jou04] MC</td><td></td><td></td><td></td></tr><tr><td rowspan="2">MD</td><td>2<sup>0.5n</sup></td><td>[Jou04] MC</td><td>2<sup>n</sup></td><td>[Jou04] MC</td><td></td><td></td><td></td></tr><tr><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.75n</sup></td><td>[Sect. 6.1] SEM+FGDI</td><td>(2<sup>0.75n</sup>)</td></tr><tr><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.735n</sup></td><td>[Sect. 6.3] SEM+FGDI+IS</td><td>(2<sup>0.735n</sup>)</td></tr><tr><td>Provable</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td>2<sup>0.5n</sup></td><td>[HS08]</td><td></td></tr></tbody></table><table><thead><tr><th colspan="2">Zipper</th><th colspan="2">Collision</th><th colspan="2">Preimage</th><th colspan="2">2nd Preimage (challenge length)</th></tr></thead><tbody><tr><td>Ideal</td><td>2<sup>0.5n</sup></td><td>Birthday</td><td>2<sup>n</sup></td><td>Brute-force</td><td>2<sup>n</sup></td><td>Brute-force</td><td></td></tr><tr><td rowspan="2">MD</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.625n</sup></td><td>[Sect. 7] SEM+FGDI [L &lt; 2<sup>n/2</sup>]</td><td>(2<sup>0.375n</sup>)</td></tr><tr><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.6n</sup></td><td>[Sect. 7] SEM+FGMC [L &gt; 2<sup>n/2</sup>]</td><td>(2<sup>0.4n</sup>)</td></tr><tr><td>Provable</td><td>2<sup>0.5r</sup></td><td>[Lis06]</td><td>2<sup>0.5r</sup></td><td>[Lis06]</td><td>2<sup>0.5r</sup></td><td>[Lis06]</td><td></td></tr></tbody></table><table><thead><tr><th colspan="2">Hash-Twice</th><th colspan="2">Collision</th><th colspan="2">Preimage</th><th colspan="2">2nd Preimage (challenge length)</th></tr></thead><tbody><tr><td>Ideal</td><td>2<sup>0.5n</sup></td><td>Birthday</td><td>2<sup>n</sup></td><td>Brute-force</td><td>2<sup>n</sup></td><td>Brute-force</td><td></td></tr><tr><td>MD</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.667n</sup></td><td>[ABDK09] EM+MC+DS</td><td>(2<sup>0.333n</sup>)</td></tr><tr><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.612n</sup></td><td>[Sect. 8.3] SEM+IS+DS+FGDI</td><td>(2<sup>0.5n</sup>)</td></tr><tr><td></td><td>-</td><td>-</td><td>-</td><td>-</td><td>2<sup>0.591n</sup></td><td>[Sect. 8.2] SEM+IS+DS+FGMC</td><td>(2<sup>0.591n</sup>)</td></tr><tr><td>Provable</td><td>2<sup>0.5</sup></td><td>-</td><td>2<sup>n</sup></td><td>-</td><td>2<sup>0.5n</sup></td><td>-</td><td></td></tr></tbody></table>

r : min(b, n)

L : 2nd preimage length

MC: Joux's Multi-Collisions

EM: Kelsey and Schneier's Expandable Message

DS: Diamond Structure

IS: Interchange Structure

SEM: Simultaneous Expandable Message

FGDI: Deep-Iterates in Functional Graph

FGMC: Multi-Cycles in Functional Graph

All computational complexities of the attacks are presented ignoring the polynomial factors.

<caption>Table 1: Security status of various combiners of two narrow-pipe hashes</caption>
## 1.3 Notations and Roadmap of the Rest of Paper

**Notations.** We summarize below notations shared across various attacks.

<table><tr><td>H<sub>1</sub>, H<sub>2</sub></td><td>: Underlying hash functions in a hash combiner</td></tr><tr><td>IV<sub>1</sub>, IV<sub>2</sub></td><td>: Initialization vectors of H<sub>1</sub> and H<sub>2</sub>, respectively</td></tr><tr><td>h<sub>1</sub>, h<sub>2</sub></td><td>: Compression functions of H<sub>1</sub> and H<sub>2</sub>, respectively</td></tr><tr><td>h<sub>1</sub><sup>*</sup>, h<sub>2</sub><sup>*</sup></td><td>: Compression functions iterated over several blocks (in particular, H<sub>i</sub>(M) = h<sub>i</sub><sup>*</sup>(IV<sub>i</sub>, M) for i ∈ {1, 2})</td></tr><tr><td>V</td><td>: Targeted image</td></tr><tr><td>m</td><td>: Message block</td></tr><tr><td>M</td><td>: Message chunk</td></tr><tr><td>[m]<sup>q</sup></td><td>: Message chunk formed by concatenating q message blocks m, with [m] = [m]<sup>1</sup></td></tr><tr><td>M<sub>∥q</sub></td><td>: Message chunk with q message blocks</td></tr><tr><td>M =<br>m<sub>1</sub> || . . . || m<sub>L</sub></td><td>: Target message or computed preimage (of L massage blocks)</td></tr><tr><td>L</td><td>: Length of M (measured in the number of blocks)</td></tr><tr><td>l</td><td>: The binary logarithm of the length of the message M, i.e., denote L = 2<sup>l</sup></td></tr><tr><td>M'</td><td>: Computed second preimage</td></tr><tr><td>L'</td><td>: Length of M' (measured in the number of blocks)</td></tr><tr><td>a<sub>0</sub>, . . . , a<sub>L</sub></td><td>: Sequence of internal states computed during the invocation of h<sub>1</sub> on M, a<sub>0</sub> = IV<sub>1</sub></td></tr><tr><td>b<sub>0</sub>, . . . , b<sub>L</sub></td><td>: Sequence of internal states computed during the invocation of h<sub>2</sub> on M, b<sub>0</sub> = IV<sub>2</sub></td></tr><tr><td>x, y</td><td>: Computed internal states</td></tr><tr><td>a&#773;<sub>j</sub>, b&#773;<sub>k</sub></td><td>: Chains of internal states for H<sub>1</sub> and H<sub>2</sub>, respectively. a&#773;<sub>j</sub> denotes a generic chain, while a&#773;<sub>j<sub>0</sub></sub> denotes a particular chain</td></tr><tr><td>A<sub>j</sub>, B<sub>k</sub></td><td>: End points (final states) of the chains</td></tr><tr><td>n</td><td>: Bit-size of the output of each underlying hash function (H<sub>1</sub> and H<sub>2</sub>); In addition, we suppose their compression functions h<sub>1</sub> and h<sub>2</sub> have n-bit internal states (i.e., suppose the underlying hash functions are narrow-pipe)</td></tr><tr><td>b</td><td>: Bit-size of a message block</td></tr><tr><td>N</td><td>: The considered random mappings are from a finite N-set domain to a finite N-set range, and N = 2<sup>n</sup></td></tr><tr><td>F<sub>GF</sub><sub>f<sub>1</sub></sub>, F<sub>GF</sub><sub>f<sub>2</sub></sub></td><td>: The functional graphs of random mappings f<sub>1</sub>(·) ≜ h<sub>1</sub>(·, m) and f<sub>2</sub>(·) ≜ h<sub>2</sub>(·, m) generated by fixing a message block m to the compression functions</td></tr><tr><td>M</td><td>: A set of messages</td></tr><tr><td>M<sub>MC/EM/SEM/DS/IS</sub></td><td>: The set of messages in a standard Joux's multi-collision or an expandable message or a simultaneous expandable message or a diamond structure or an interchange structure</td></tr></table>
<table><tr><td>x &rarr; x'<br>x',</td><td>x &rarr; x'<br>x'</td><td>We say that m (resp. M&#770;) maps state x to state x' if x' = h(x, m)<br>: (resp. x' = h<sup>*</sup>(x, M&#770;)) and denote this by x &rarr; x' (resp. x &rarr; x',<br>the compression function h is clear from the context).</td></tr><tr><td>h<sub>[m]</sub></td><td></td><td>An n-bit random mapping obtained by feeding an arbitrary fixed<br>message block m into a compression function h with n-bit state.</td></tr><tr><td>tilde O</td><td></td><td>Soft-O, is used as a variant of big O notation that ignores<br>: logarithmic factors. Thus, f(n) &isin; O&#770;(g(n)) is shorthand for<br>&exist;k: f(n) &isin; O(g(n) log<sup>k</sup> g(n)).</td></tr></table>

**Roadmap.** Section 2 exhibits preliminaries including generic tools and known attacks on hash constructions. Particularly, sections 2.5, 2.6, 2.7 demonstrate those new tools – the interchange structure, the simultaneous expandable message, deep iterates and multi-cycles in random functional graphs – which make the presented attacks possible. Sections 3, 4, and 5 illustrate preimage attacks on the XOR combiner using interchange structure, deep iterates, and multi-cycles in functional graphs, respectively. Sections 6, 7, and 8 describes the second-preimage attacks on the concatenation combiner, Zipper hash, and Hash-Twice, respectively. Within the description of each attack, we provide an overview followed by detailed steps. In Section 9, we discuss more applications and extensions of the proposed attacks, including applications to combiners of wide-pipe hash functions and extensions to the combination of more than two hash functions. Section 10 summarizes attacks presented in this paper and discusses open problems.

## 2 Preliminaries

In this section, we introduce the technical tools and general concepts used in our attacks. Those tools briefly introduced in Sect. 2.1 through Sect. 2.4 are all existing and well-known tools. Those tools described in detail in Sect. 2.5 through Sect. 2.7 are our new tools exploited in different attacks.

### 2.1 Joux's Multi-Collision (MC) and Its Applications in Attacks on the Concatenation Combiner [Jou04]

In 2004, Joux introduced multi-collisions on narrow-pipe Merkle-Damgård hash functions. Given a hash function $\mathcal{H}$, a multi-collision refers to a set of messages $\mathcal{M} = \{M_1, M_2, \dots\}$ whose hash digests are all the same, i.e., $\mathcal{H}(M_i) = \mathcal{H}(M_j)$ for any pair $M_i, M_j \in \mathcal{M}$. The computational complexity of generic brute-force search increases exponentially when the target size $|\mathcal{M}|$ increases; more precisely, it is approximately $2^{(|\mathcal{M}|-1) \cdot n / |\mathcal{M}|}$. Utilizing the iterative nature of Merkle-Damgård structure, Joux's algorithm (see Alg. 1, whose pseudo-code is given in Appendix A) is able to find multi-collision of size $2^t$ with a complexity of $t \cdot 2^{n/2}$, i.e., a complexity not much greater than that of finding a single collision.
<caption>**Algorithm 1: Building a 2<sup>t</sup>-Joux's Multi-Collision**</caption>

**Require:** Given an iterated hash function $\mathcal{H}$ with a compression function $h$, and an initial value $x_0$.

1. Initialize $\mathcal{M}_{\text{MC}}$ as a data structure of pairs of message blocks

2. For $i = 1, \dots, t$:

(a) Find a pair of message blocks $(m_i, m'_i)$ such that $h(x_{i-1}, m_i) = h(x_{i-1}, m'_i) = x_i$. This can be done with a complexity of $2^{n/2}$ due to birthday paradox.

(b) Append $(m_i, m'_i)$ to $\mathcal{M}_{\text{MC}}$

3. Output $(x_t, \mathcal{M}_{\text{MC}})$

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

It is trivial to see the message set $\mathcal{M} = \{\overline{m}_1 \parallel \overline{m}_2 \parallel \dots \parallel \overline{m}_t \mid \overline{m}_i = m_i \text{ or } m'_i \text{ for } i = 1, 2, \dots, t\}$ forms a multi-collision of size $2^t$, and the overall complexity is $O(t \cdot 2^{n/2})$. Moreover, a data structure $\mathcal{M}_{\text{MC}}$ of $t$ pairs of message blocks can fully define the set $\mathcal{M}$ of $2^t$ colliding messages.

With Joux's multi-collision at hand, one can immediately deploy a collision attack and a preimage attack on concatenation combiner with complexities $n \cdot 2^{n/2}$ and $n \cdot 2^n$, respectively. The collision attack goes as follows: first, build a 2<sup>n/2</sup>-Joux's multi-collision for one of the underlying hash function (iterated), and then exploit the messages in the structure to launch a birthday attack for the other hash function to find a collision among the outputs. The preimage attack follows a similar framework (see [BGW18] for an illustration and Joux's original paper [Jou04] for more details).

Since its invention, Joux's multi-collisions have been employed in numerous cryptanalysis of hash functions, including the following most relevant ones and works such as [HS06,NS07].

## 2.2 Expandable Message (EM) and the Long Message Second-Preimage Attack [KS05]

In [DA99a], Dean devised a second-preimage attack for long messages on specific Merkle-Damgård hash functions for which it is easy to find fixed points in their compression function. Given a challenge message $\mathcal{M} = m_1 \parallel m_2 \parallel \dots \parallel m_L$, the attacker computes the sequence of internal states $a_0, a_1, \dots, a_L$ generated during the invocation of the compression function on $\mathcal{M}$. A simplified attack would now start from the state $x_0 = \text{IV}$ and evaluate the compression function with arbitrary message blocks until a collision $h(x_0, m) = a_p$ is found for some message block $m$ and index $p$. The attacker can now append the message suffix