<table><caption>**Table 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 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.</caption><thead><tr><th rowspan="2">Mode</th><th colspan="2">Provable security bounds</th><th colspan="3">Attacks (this work)</th></tr><tr><th>Advantage</th><th>Queries</th><th>Queries</th><th>Time</th><th>Type</th></tr></thead><tbody><tr><td rowspan="2">SUM-ECBC [42]</td><td rowspan="2">O(<sup>q<sup>3</sup>ℓ<sup>3</sup></sup>&frasl;<sub>2<sup>2n</sup></sub>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>3n/2</sup>)</td><td>U</td></tr><tr><td>O(2<sup>6n/7</sup>)</td><td>Ω̃(2<sup>6n/7</sup>)</td><td>U</td></tr><tr><td rowspan="2">GCM-SIV2 [20]</td><td rowspan="2">O(<sup>q<sup>3</sup>ℓ<sup>2</sup></sup>&frasl;<sub>2<sup>2n</sup></sub>)</td><td rowspan="2">Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>3n/2</sup>)</td><td>U</td></tr><tr><td>O(2<sup>6n/7</sup>)</td><td>Ω̃(2<sup>6n/7</sup>)</td><td>U</td></tr><tr><td>PMAC+ [43]</td><td>O(<sup>q<sup>3</sup>ℓ<sup>3</sup></sup>&frasl;<sub>2<sup>2n</sup></sub>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>3n/2</sup>)</td><td>E</td></tr><tr><td>LightMAC+ [33]</td><td>O(<sup>q<sup>3</sup></sup>&frasl;<sub>2<sup>2n</sup></sub>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>3n/2</sup>)</td><td>E</td></tr><tr><td>1kPMAC+ [9]</td><td>O(<sup>σ</sup>&frasl;<sub>2n</sub> + <sup>qσ<sup>2</sup></sup>&frasl;<sub>2<sup>2n</sup></sub>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>3n/2</sup>)</td><td>E</td></tr><tr><td>3kf9 [44]</td><td>O(<sup>q<sup>3</sup>ℓ<sup>3</sup></sup>&frasl;<sub>2<sup>2n</sup></sub> + <sup>qℓ</sup>&frasl;<sub>2n</sub>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(<sup>4&radic;n</sup>&frasl;<sub>2</sub> &middot; 2<sup>3n/4</sup>)</td><td>Ω̃(2<sup>5n/4</sup>)</td><td>U</td></tr><tr><td>1kf9 [8]</td><td>O(<sup>qℓ<sup>2</sup></sup>&frasl;<sub>2n</sub> + <sup>q<sup>3</sup>ℓ<sup>4</sup></sup>&frasl;<sub>2<sup>2n</sup></sub> + <sup>q<sup>4</sup>ℓ<sup>4</sup></sup>&frasl;<sub>2<sup>3n</sup></sub> + <sup>q<sup>4</sup>ℓ<sup>6</sup></sup>&frasl;<sub>2<sup>4n</sup></sub>)</td><td>Ω(2<sup>2n/3</sup>)</td><td>O(2<sup>n/2</sup>)</td><td>Ω̃(2<sup>n/2</sup>)</td><td>U</td></tr></tbody></table>

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 message 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 $2^{3n}$. Therefore, we only need four lists of $2^{3n/4}$ queries, and we expect one good quadruple out of the $2^{3n}$ choices in the four lists.

Table 1 shows a summary of our main results and how they compare with their respective provable security claims. In particular, we have forgeries attacks with $O(2^{3n/4})$ 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$ queries against these constructions. Our attack against LighMAC+ contradicts the recent security bound for LighMAC+ [34], because we have an attack with $O(2^{3n/4})$ MAC queries, and a single verification query. The other attacks do not contradict the security proofs, but they make an important step towards understanding the actually security of these modes: we now have a lower bound of $2^{2n/3}$ queries from the proofs, and an upper bound of $2^{3n/4}$ from our attacks.

The attacks have a complexity of $2^{3n/4}$ in the information theoretic model (the model used for most MAC security proofs), but we note that an attacker needs more than $2^n$ operations to create a forgery. However, we have found a variant of our attack against SUM-ECBC and GCM-SIV2 with total complexity below $2^n$, using $O(2^{6n/7})$ queries and $\tilde{O}(2^{6n/7})$ operations.

We have also found an attack with only $O(2^{n/2})$ queries and $\tilde{O}(2^{n/2})$ operations against 1kf9 [8], a single key variant of 3kf9 with claimed security up to $2^{2n/3}$ queries. 1kf9 has been withdrawn due to issues with its security proof, but no attack was known previously.
**Related works.** There has been extensive work on security proofs for modes of operations, with a recent focus on security beyond the birthday bound. An interesting example is the encryption mode CENC by Iwata [17]: the initial proof was only up to $2^{2n/3}$ queries, but a later proof showed that it actually remains secure close to $2^n$ queries [19]. Our results show that in the case of double-block-hash-then-sum MACs, the security is lower than $n$-bit security.

Similarly, the initial proof of the randomized MAC EHtM only gave security up to $2^{2n/3}$, but a later proof showed security up to $2^{3n/4}$ [11]. This result also includes a matching attack, using a technique similar to ours based on looking for quadruples. However in the case of EHtM the attacker can observe part of the state, which allows him to find a right quadruple in $O(2^{3n/4})$ time and memory. In our case we can't observe the internal state at all, thus we need to use different tricks tailored to each construction in order to amplify the filtering and avoid the many false-positives. In particular, this significantly increases the time and memory complexity.

There has also been intensive work on generic attacks to complement the security proof results. After the generic collision attack of Preneel and van Oorschot [37], more advanced attacks against MACs have been described, with stronger outcomes than existential forgeries, starting with a key-recovery attack against the envelop MAC by the same authors [38]. In particular, a series of attacks against hash-based MACs [26,36,16,10] led to universal forgery attacks against long challenges, and key-recovery attacks when the hash function has an internal checksum (like the GOST family). Against PMAC, Lee et al. showed a universal forgery attack in 2006 [25]. Later, Fuhr, Leurent and Suder gave a key-recovery attack against the PMAC variant used in AEZv3 [14]. Issues with GCM authentication with truncated tags were also pointed out by Ferguson [12]. These attacks don't contradict the security proofs of the schemes, but they are important results to understand the security degradation after the birthday bound.

**Organization of the paper.** We first explain our attack technique using quadruples of messages in Section 2, and give three concrete attacks using this technique: an attack against SUM-ECBC and GCM-SIV2 in Section 3, an attack against PMAC+ and related constructions in Section 4, and an attack against 3kf9 in Section 5. Finally, we show a variant of the technique using special properties of the single-key constructions of [8,9] in Section 6.

**Notations.** We denote the concatenation of messages blocks $x$ and $y$ as $x \parallel y$. When $x$ and $y$ fit together in one block, we use $x|y$ to denote their concatenation. We use $L[i]$ to denote element $i$ of list $L$, $x_{[i]}$ to denote bit $i$ of $x$, and $x_{[i:j]}$ to denote bits $i$ to $j-1$. Finally, we use a curly brace for systems of equations.

## 2 Generic Attack against double-block-hash MACs

We first explain our attacks in a generic way, and leave the specific details to later sections focused on concrete MAC constructions.
We consider MACs where 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, hence the name double-block-hash-then-sum MAC.

Our attacks exploit the fact that the two halves are combined with a sum, where one side depends only on Σ, and the other side depends only on Θ. They do not seem applicable to constructions with more intricate finalization functions, such as LightMAC+2 [33], or the tweakable block-cipher based constructions PMAC_TBC [32], PMACx [27], ZMAC [21], or ZMAC+[28].

## 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 $MAC(M) = E(\Sigma(M)) \oplus E'(\Theta(M))$, it follows that:

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

In addition, if the messages X, Y, Z, T are well constructed, the relation $\mathcal{R}$ reduces to a linear system of rank only three, i.e.

$$[\Sigma(X) = \Sigma(Y) \text{ and } \Theta(Y) = \Theta(Z) \text{ and } \Sigma(Z) = \Sigma(T)] \implies \Theta(T) = \Theta(X).$$

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

In practice, we consider lists of $2^{3n/4}$ messages, generated with two message injection functions $\phi$ and $\psi$. These functions are different in every attack, but they mostly correspond to adding two distinct prefixes, as in the following example:

$$\begin{align*} \phi(i) &= 0 \parallel i \\ X &= \phi(x) = 0 \parallel x \end{align*}$$

$$\begin{align*} \psi(i) &= 1 \parallel i \\ Y &= \psi(y) = 1 \parallel y \end{align*}$$

$$Z = \phi(z) = 0 \parallel z$$

$$T = \psi(t) = 1 \parallel t,$$
In particular, 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.

This type of attack has some similarities with a higher order differential attack. Indeed, in the easiest case (e. g. our attack against SUM-ECBC), the relation $\mathcal{R}$ can be written as $\mathcal{R}(x, y, z, t) \iff [x \oplus y = z \oplus t = \Delta_1$ and $x \oplus t = y \oplus z = \Delta_3]$ for some secret values $\Delta_1$ and $\Delta_3$. This idea of looking for quadruples is also very similar to the attack on EHTM [11], but the full attack will turn out quite different. Indeed, in the case of EHTM, the attacker can observe the salt $\mathcal{R}$ which represent half of the $2n$-bit internal state. Here this would be the equivalent of observing $\Sigma(m)$ for all processed messages $m$. This is clearly not possible for the studied constructions and we need something more to discriminate and find a good quadruple that satisfies $\mathcal{R}$.

## 2.2 Detecting Quadruples: Generalized Birthday Algorithms

To finish the attack we usually need to locate one good quadruple. The relation $\text{MAC}(X) \oplus \text{MAC}(Y) \oplus \text{MAC}(Z) \oplus \text{MAC}(T) = 0$ in itself is too weak because we expect one quadruple out of $2^n$ to satisfy it randomly, but we can usually amplify the filtering using related quadruples that satisfy $\mathcal{R}$ simultaneously (the exact details depend on the MAC construction).

In most of our attacks, we can express the search for a quadruple as an instance of the 4-sum problem, and solve it using variants of Wagner's generalized birthday algorithm [40]. This reduces the time complexity of the attacks (compared to a naive search), and provides trade-offs between the query, memory and time complexities.

More precisely, our problem can be stated as follows:

**Definition 1 (4-sum problem).** Given four lists $L_1, L_2, L_3, L_4$ of $2^s$ elements, with on average $2^p$ quadruples $(x, y, z, t) \in L_1 \times L_2 \times L_3 \times L_4$ such that $x \oplus y \oplus z \oplus t = 0$, find one of them.

Note that if the lists contain random $n$-bit words, we expect to have $2^p = 2^{4s-n}$ solutions, but in some of our instances there are more solutions because of the structure of the lists.

We denote the join operator as $\bowtie$; it computes the pairwise sum of two lists, and keeps the initial values attached to the sum. In addition, the join operator with filtering $\bowtie_t^\alpha$ only keeps values such that the $t$ least significant bits of the sum agree with the value $\alpha$:

$$A \bowtie B = \{(a \oplus b, a, b) : (a, b) \in A \times B\} \\ A \bowtie_t^\alpha B = \{(a \oplus b, a, b) : (a, b) \in A \times B, a_{[0:t]} \oplus b_{[0:t]} = \alpha\}$$

In particular, we have $\bowtie = \bowtie_0^0$. We also denote as $\bowtie_\infty$ the joint operator with filtering over the full input values. The filtered joint operator is the basis of Wagner's algorithm, and it can be computed in almost linear time by sorting the two input lists, and stepping through them simultaneously.
<figure><img src="image_141.png" /><figcaption>**Fig. 1.** Generalized Birthday algorithm to find good quadruples.</figcaption></figure>

**Direct algorithm.** While a naive algorithm for our 4-sum instances would take time $2^{4s}$ to examine all quadruples, there is a simple improvement with time and memory $\tilde{O}(2^{2s})$. First, the attacker builds $L_{12} = L_1 \bowtie L_2$ and $L_{34} = L_3 \bowtie L_4$. Then, he looks for a collision between the first component of $L_{12}$ and $L_{34}$. A collision directly yields a solution. This always finds a solution if it exists in $\tilde{O}(2^{2s})$ operations but it also takes $O(2^{2s})$ memory.

**Memory efficient algorithm.** We can reduce the memory complexity of the algorithm if we avoid constructing the full lists $L_{12}$ and $L_{34}$. An algorithm with low memory complexity was first described by Chose et al. [6], but we use the description given by Wagner in the full version of [40].

Instead of building the full lists $L_{12}$ and $L_{34}$, we filter values such that $s$ least significant bits differ by some fixed value $\alpha$. This reduces the expected size of the lists to only $2^s$: $E[|L_{34}^\alpha|] = E[|L_{12}^\alpha|] = |L_1| \cdot |L_2|/2^s = 2^s$. If this algorithm is repeated for every $s$-bit value $\alpha$, it will eventually find all solutions.

Actually, one run of the algorithm detects the solutions whose least significant bits of $x \oplus y$ are equal to $\alpha$. If there are $2^p$ solutions in total, there is one such solution with probability $2^{p-s}$, and this algorithm will find the first solution after trying $2^{s-p}$ values of $\alpha$ on average. Therefore, the expected time complexity of the algorithm given by Figure 1 is only $\tilde{O}(2^{2s-p})$.

**Related work.** In a 2016 work, Nikolic and Sasaki [35] investigate the 4-sum where we need to find 4 different inputs $x, y, z, t$ to a function $f$ such that $f(x) \oplus f(y) \oplus f(z) \oplus f(t) = 0$. They also mention that their algorithm is adaptable to pairwise identical functions, i. e. $f(x) \oplus g(y) \oplus f(z) \oplus g(t) = 0$.

Most of our attacks can be written in this way; concretely, they are equivalent to instances of random functions with $3n$-bit outputs. In this setting our algorithm takes time $\tilde{O}(2^{3n/2})$ and memory $O(2^{3n/4})$, while Nikolic and Sasaki's work can reach $\tilde{O}(2^{9n/8})$ time and $O(2^{3n/4})$ memory. Unfortunately, their algorithm requires $\tilde{O}(2^{9n/8})$ queries to the functions; this would translate to $\tilde{O}(2^{9n/8})$ queries to the MAC, which is not interesting in our context.
<figure><img src="image_142.png" /><figcaption>Fig. 2. Diagram for SUM-ECBC with a $\ell$-block message.</figcaption></figure>

## 3 Attacking SUM-ECBC-like constructions

We start with attacks against SUM-ECBC [42] and GCM-SIV2 [20]; while the constructions are quite different, they have a similar structure and the same attacks can be used in both cases. We give a universal forgery attack with $O(2^{3n/4})$ queries and $\tilde{O}(2^{3n/2})$ operations (using memory $O(2^{3n/4})$), and a variant with total complexity below $2^n$, with $O(2^{6n/7})$ queries and $\tilde{O}(2^{6n/7})$ operations.

### 3.1 Attacking SUM-ECBC

SUM-ECBC was designed by Yasuda in 2010 [42], 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 padded with 10* padding, and divided into $n$-bit blocks. In the following we ignore the padding and consider the padded message as the input: this makes our description easier, and any padded message whose last block is non-zero can be “un-padded” to generate a valid input message. The construction is defined as follows (see also Figure 2):

$$ 
\begin{aligned}
\Sigma(M) &= \sigma_{\ell} & \sigma_{0} &= 0 & \sigma_{i} &= E_{1}(\sigma_{i-1} \oplus m_{i}) \\
\Theta(M) &= \theta_{\ell} & \theta_{0} &= 0 & \theta_{i} &= E_{3}(\theta_{i-1} \oplus m_{i}) \\
\text{MAC}(M) &= E_{2}(\Sigma(M)) \oplus E_{4}(\Theta(M))
\end{aligned}
$$
**Attack.** Following the framework of Section 2, we consider quadruple of messages, built with two message injection functions:

$$\phi(i) = 0 \parallel i$$

$$\psi(i) = 1 \parallel i$$

In particular, we have

$$\mathrm{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)$$

$$\mathrm{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)$$

Next, we build quadruples of messages X, Y, Z, T with

$$X = \phi(x)$$

$$Y = \psi(y)$$

$$Z = \phi(z)$$

$$T = \psi(t),$$

and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation:

$$\mathcal{R}(x, y, z, t) := \begin{cases} \Sigma_0(x) = \Sigma_1(y) \\ \Sigma_0(z) = \Sigma_1(t) \\ \Theta_0(z) = \Theta_1(y) \\ \Theta_0(x) = \Theta_1(t). \end{cases}$$

We have

$$\mathcal{R}(x, y, z, t) \Leftrightarrow \begin{cases} 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{cases} \Leftrightarrow \begin{cases} 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{cases}$$

As promised in Section 2, $\mathcal{R}$ defines a 3n-bit relation. We can easily observe when $x \oplus y \oplus z \oplus t = 0$, and we can also detect the relation on the sum of the MACs following Equation (1):

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

Moreover, 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$. We use this relation to build several quadruples that satisfy $\mathcal{R}$ simultaneously:

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

This leads to an attack with $\mathcal{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 \\ \mathrm{MAC}(\phi(x)) \oplus \mathrm{MAC}(\psi(y)) \oplus \mathrm{MAC}(\phi(z)) \oplus \mathrm{MAC}(\psi(t)) = 0 \\ \mathrm{MAC}(\phi(x \oplus 1)) \oplus \mathrm{MAC}(\psi(y \oplus 1)) \oplus \mathrm{MAC}(\phi(z \oplus 1)) \oplus \mathrm{MAC}(\psi(t \oplus 1)) = 0. \end{array} \right. \quad (3)$$
Because we need a fair distribution of values $x \oplus y$ and $x \oplus t$ to find the good quadruple we build the sets as:

$$ \mathcal{X} = \{x \in \{0, 1\}^n : x_{[0:n/4]} = 0\} \qquad \mathcal{Y} = \{x \in \{0, 1\}^n : x_{[n/4:n/2]} = 0\} $$

$$ \mathcal{Z} = \{x \in \{0, 1\}^n : x_{[n/2:3n/4]} = 0\} \qquad \mathcal{T} = \{x \in \{0, 1\}^n : x_{[3n/4:n]} = 0\} $$

With this construction, there is exactly one quadruple $(x, y, z, t) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z} \times \mathcal{T}$ that respects $\mathcal{R}$, given by:

$$ x = v_1|w_2|u_3|0 \qquad y = w_1|v_2|0|u_4 \qquad z = u_1|0|v_3|w_4 \qquad t = 0|u_2|w_3|v_4, $$

where:

$$ E_1(0) \oplus E_1(1) =: u_1|u_2|u_3|u_4 $$

$$ E_3(0) \oplus E_3(1) =: v_1|v_2|v_3|v_4 $$

$$ E_1(0) \oplus E_1(1) \oplus E_3(0) \oplus E_3(1) =: w_1|w_2|w_3|w_4. $$

We expect on average one random quadruple satisfying (3) (with $2^{3n}$ potential quadruples, and a 3n-bit filtering), in addition to the quadruple satisfying $\mathcal{R}$. The correct quadruple can easily be checked with a few extra queries.

In practice, we use the generalized birthday algorithms of Section 2.2 in order to optimize the complexity of the attack. We consider four lists:

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

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

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

$$ L_4 = \{t \mid \text{MAC}(\psi(t)) \mid \text{MAC}(\psi(t \oplus 1)) : t \in \mathcal{T}\} $$

Notice that we can build those lists with $5 \cdot 2^{3n/4}$ queries as, by construction, for any element $i$ of $\mathcal{Y}, \mathcal{Z}, \mathcal{T}$ the element $(i \oplus 1)$ also belongs to $\mathcal{Y}, \mathcal{Z}, \mathcal{T}$, respectively. We use the algorithm of Section 2.2 to find $(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$ with $\tilde{O}(2^{3n/2})$ operations, using a memory of size $O(2^{3n/4})$. After finding a collision, we verify that it is not a false positive by testing the relation for another value $c$. As there are on average $O(1)$ random quadruples the attack is indeed using a total of $5 \cdot 2^{3n/4} + O(1) = O(2^{3n/4})$ queries.

**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 $\text{MAC}(v \parallel x \parallel s) \oplus \text{MAC}(v \oplus 1 \parallel y \parallel s) \oplus \text{MAC}(v \parallel z \parallel s) \oplus \text{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 $\ell \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 (2):

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

**Optimizing the time complexity.** Equation (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 $\mathcal{C}$ of $\{0, 1\}^n$, we have:

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

If we select $\mathcal{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 of $\mathcal{C}$. Concretely, we use $\mathcal{C} = \{x : x_{[3n/7:n]} = 0\} = \{x : x < 2^{3n/7}\}$, so that the value $\bigoplus_{c \in \mathcal{C}} \text{MAC}(\phi(x \oplus c))$ is independent of bits 0 to $3n/7 - 1$ of $x$.

Therefore, we consider the rewritten MAC function

$$ \text{MAC}'(v \parallel w) = \bigoplus_{c \in \mathcal{C}} \text{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 4, we still have:

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

Since the relation $\mathcal{R}'$ is now only a $12n/7$-bit condition, we can use shorter lists than before, with just $2^{3n/7}$ elements. We can also increase the filtering using
the same trick as previously, considering the following lists:

$$L'_{1} = \{ x \mid \mathrm{MAC}'(\phi'(x)) \mid \mathrm{MAC}'(\phi'(x \oplus 1)) : x \in \{0,1\}^{4n/7}, x_{[0:n/7]} = 0 \}$$

$$L'_{2} = \{ y \mid \mathrm{MAC}'(\psi'(y)) \mid \mathrm{MAC}'(\psi'(y \oplus 1)) : y \in \{0,1\}^{4n/7}, y_{[n/7:2n/7]} = 0 \}$$

$$L'_{3} = \{ z \mid \mathrm{MAC}'(\phi'(z)) \mid \mathrm{MAC}'(\phi'(z \oplus 1)) : z \in \{0,1\}^{4n/7}, z_{[2n/7:3n/7]} = 0 \}$$

$$L'_{4} = \{ t \mid \mathrm{MAC}'(\psi'(t)) \mid \mathrm{MAC}'(\psi'(t \oplus 1)) : t \in \{0,1\}^{4n/7}, t_{[3n/7:4n/7]} = 0 \}$$

Finally, using the algorithm of Section 2.2 with $s = 3n/7$ and $p = 0$, we can locate a right quadruple using $\tilde{O}(2^{6n/7})$ queries, $\tilde{O}(2^{6n/7})$ operations, and $O(2^{3n/7})$ memory. This recovers only $4n/7$ bits of $E_1(0) \oplus E_1(1)$ and $E_3(0) \oplus E_3(1)$, but we can easily recover the remaining bits, either by brute force, or by repeating the attack with a different set $C$.

## 3.2 Attacking GCM-SIV2

GCM-SIV2 is an authenticated encryption mode designed by Iwata and Minematsu [20] as a double-block-hash version of GCM-SIV (in the following, we consider GCM-SIV2 with GHASH as the underlying universal hash function). For simplicity, we focus on the authentication part of GCM-SIV2, using inputs with a non-empty associated data, and an empty message. In this case, GCM-SIV2 becomes a nonce-based MAC. The message $M$ (considered as associated data for the mode) is zero-padded, divided into $n$-bit blocks, and the length is appended in an extra block. Then the construction is defined as follows, with $\odot$ a finite field multiplication (see also Figure 3):

$$\begin{align*}
\Sigma(N, M) &= N \oplus \ell \odot H_1 \oplus \bigoplus_{i=1}^{\ell} m_i \odot H_1^{\ell+2-i} \\
\Theta(N, M) &= N \oplus \ell \odot H_2 \oplus \bigoplus_{i=1}^{\ell} m_i \odot H_2^{\ell+2-i} \\
\mathrm{MAC}(N, M) &= E_1(\Sigma(M)) \oplus E_2(\Theta(M)) \quad \Vert \quad E_3(\Sigma(M)) \oplus E_4(\Theta(M))
\end{align*}$$

**Attack.** The structure of the authentication part of GCM-SIV2 is essentially the same as the structure of SUM-ECBC, where the block cipher calls $E_1$ and $E_3$ are replaced by multiplication by $H_1$ and $H_2$. The finalization function has a $2n$-bit output MAC$^1$, MAC$^2$, but quadruples following $\mathcal{R}$ will collide on both outputs. Thus, we can essentially repeat the SUM-ECBC attack, but there is an important difference: GCM-SIV2 is a nonce-based MAC, rather than a deterministic one. Therefore, all queries must include a nonce $N$, and we should not query two different messages with the same nonce. We adapt the previous attack using message injection functions that output both a nonce and a message, so that we use two fixed messages, 0 and 1, with variable nonces:

$$\phi(i) = (i, 0)$$

$$\psi(i) = (i, 1)$$
<figure><img src="image_143.png" /><figcaption>Fig. 3. Diagram for authentication in GCM-SIV2 using GHASH with a $\ell$-block message, a nonce $N$, hash keys $H_1$ and $H_2$.</figcaption></figure>

$$ \text{MAC}(\phi(i)) = E_1(\underbrace{i \oplus H_1}_{\Sigma_0(i)} \oplus E_2(\underbrace{i \oplus H_2}_{\Theta_0(i)})) \quad \| \quad E_3(\Sigma_0(i)) \oplus E_4(\Theta_0(i)) $$

$$ \text{MAC}(\psi(i)) = E_1(\underbrace{i \oplus H_1 \oplus H_1^2}_{\Sigma_1(i)}) \oplus E_2(\underbrace{i \oplus H_2 \oplus H_2^2}_{\Theta_1(i)}) \quad \| \quad E_3(\Sigma_1(i)) \oplus E_4(\Theta_1(i)). $$

We consider quadruples of nonce/messages $X, Y, Z, T$ with

$$ X = \phi(x) \qquad Y = \psi(y) \qquad Z = \phi(z) \qquad T = \psi(t), $$

and we have the same kind of relations as in the previous attack:

$$ \begin{aligned} \mathcal{R}(x, y, z, t) &:= \begin{cases} \Sigma_0(x) = \Sigma_1(y) \\ \Sigma_0(z) = \Sigma_1(t) \\ \Theta_0(z) = \Theta_1(y) \\ \Theta_0(x) = \Theta_1(t). \end{cases} & \Leftrightarrow & \begin{cases} x \oplus y \oplus z \oplus t = 0 \\ x \oplus y = H_1^2 \\ x \oplus t = H_2^2 \end{cases} \\ &\Rightarrow \text{MAC}(\phi(x)) \oplus \text{MAC}(\psi(y)) \oplus \text{MAC}(\phi(z)) \oplus \text{MAC}(\psi(t)) = 0 \end{aligned} $$

Since the MAC output is $2n$-bit long, we can directly build an attack with $O(2^{3n/4})$ queries: we consider four distinct sets $X, Y, Z, T$ of $2^{3n/4}$ values, and we look for a quadruple $(x, y, z, t) \in X \times Y \times Z \times T$, such that

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

we expect to find one good quadruple that respects $\mathcal{R}$ along with $O(1)$ quadruples that randomly satisfy the observable filter (5). This leads to an attack with $O(2^{3n/4})$ queries and time $\tilde{O}(2^{3n/2})$. Since we recover $H_1$ and $H_2$ (from $H_1^2 = x \oplus y$ and $H_2^2 = x \oplus t$), we can do universal forgeries. In addition, we can also easily adapt the attack with $O(2^{6n/7})$ queries and time $\tilde{O}(2^{6n/7})$.
# 4 Attacking PMAC-like constructions

We now describe attacks against PMAC+ [43] and related constructions: 1kMAC+ [9], and LightMAC+ [33]. We have an existential forgery attack with $O(2^{3n/4})$ queries and $\tilde{O}(2^{3n/2})$ operations (using memory $O(2^{3n/4})$), with a range of time-memory trade-offs with $O(2^t)$ queries, with $3n/4 < t < n$, and $\tilde{O}(2^{3n-2t})$ operations (using memory $O(2^t)$).

## 4.1 Attacking PMAC+

PMAC+ was designed by Yasuda in 2011 [43], as a variant of PMAC [5] with a larger internal state. The scheme internally uses a tweakable block cipher construction inspired by the XE construction [39], that we denote as $\tilde{E}_i$. The message $M$ is first padded with $10^*$ padding, and divided into $n$-bit blocks, but for simplicity we ignore the padding in our description. The construction is shown in Figure 4$^3$:

$$ 
\begin{aligned}
\Sigma(M) &= \bigoplus_{i=1}^{\ell} \tilde{E}_i(m_i) & \tilde{E}_i(x) &= E_1(x \oplus 2^i \odot \Delta_0 \oplus 2^{2i} \odot \Delta_1) \\
\Theta(M) &= \bigoplus_{i=1}^{\ell} 2^{\ell-i} \odot \tilde{E}_i(m_i) & \Delta_0 &= E_1(0) \quad \Delta_1 = E_1(1) \\
MAC(M) &= E_2(\Sigma(M)) \oplus E_3(\Theta(M))
\end{aligned}
$$

**Attack.** As in the previous attack, we use message injection functions with two different prefixes, but we include an extra block $u$ to define related quadruples:

$$ \phi_u(i) = u \parallel 0 \parallel i \qquad \psi_u(i) = u \parallel 1 \parallel i $$

$$ MAC(\phi_u(i)) = E_2 \left( \underbrace{\tilde{E}_1(u) \oplus \tilde{E}_2(0) \oplus \tilde{E}_3(i)}_{\Sigma_{u,0}(i)} \right) \oplus E_3 \left( \underbrace{4\tilde{E}_1(u) \oplus 2\tilde{E}_2(0) \oplus \tilde{E}_3(i)}_{\Sigma_{u,0}(i)} \right) $$

$$ MAC(\psi_u(i)) = E_2 \left( \underbrace{\tilde{E}_1(u) \oplus \tilde{E}_2(1) \oplus \tilde{E}_3(i)}_{\Sigma_{u,1}(i)} \right) \oplus E_3 \left( \underbrace{4\tilde{E}_1(u) \oplus 2\tilde{E}_2(1) \oplus \tilde{E}_3(i)}_{\Sigma_{u,1}(i)} \right). $$

Next, we build quadruples of messages $X, Y, Z, T$ with

$$ X = \phi_u(x) \qquad Y = \psi_u(y) \qquad Z = \phi_u(z) \qquad T = \psi_u(t), $$

and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation:

$$ \mathcal{R}(x, y, z, t) := \begin{cases} \Sigma_{u,0}(x) = \Sigma_{u,1}(y) \\ \Sigma_{u,0}(z) = \Sigma_{u,1}(t) \\ \Theta_{u,0}(z) = \Theta_{u,1}(y) \\ \Theta_{u,0}(x) = \Theta_{u,1}(t). \end{cases} $$

<footnote n="3">3 The algorithm and the figure given in [43] differ in the coefficients used to compute $\Theta$. We use the algorithmic description because it matches later PMAC+ variants, but the attack can easily be adapted to the other case.</footnote>
<figure><img src="image_144.png" /><figcaption>Fig. 4. Diagram for PMAC+ with a $\ell$-block message where $\Delta_0 = E_1(0)$ and $\Delta_1 = E_1(1)$.</figcaption></figure>

We have

$$ \begin{aligned} \mathcal{R}(x, y, z, t) &\Leftrightarrow \left\{ \begin{array}{l} \tilde{E}_3(x) \oplus \tilde{E}_2(0) = \tilde{E}_3(y) \oplus \tilde{E}_2(1) \\ \tilde{E}_3(z) \oplus \tilde{E}_2(0) = \tilde{E}_3(t) \oplus \tilde{E}_2(1) \\ \tilde{E}_3(y) \oplus 2\tilde{E}_2(1) = \tilde{E}_3(z) \oplus 2\tilde{E}_2(0) \\ \tilde{E}_3(t) \oplus 2\tilde{E}_2(1) = \tilde{E}_3(x) \oplus 2\tilde{E}_2(0) \end{array} \right. \\ &\Leftrightarrow \left\{ \begin{array}{l} \tilde{E}_3(x) \oplus \tilde{E}_3(y) \oplus \tilde{E}_3(z) \oplus \tilde{E}_3(t) = 0 \\ \tilde{E}_3(x) \oplus \tilde{E}_3(y) = \tilde{E}_2(0) \oplus \tilde{E}_2(1) \\ \tilde{E}_3(t) \oplus \tilde{E}_3(x) = 2\tilde{E}_2(0) \oplus 2\tilde{E}_2(1) \end{array} \right. \end{aligned} $$

Again, $\mathcal{R}$ defines a $3n$-bit relation, and we can detect it through the sum of the MACs following Equation (1):

$$ \mathcal{R}(x, y, z, t) \Rightarrow \mathrm{MAC}(\phi_u(x)) \oplus \mathrm{MAC}(\psi_u(y)) \oplus \mathrm{MAC}(\phi_u(z)) \oplus \mathrm{MAC}(\psi_u(t)) = 0 $$

In addition, the relation $\mathcal{R}$ is independent of the value $u$, so that we can easily build several quadruples that satisfy $\mathcal{R}$ simultaneously. This leads to an attack with $O(2^{3n/4})$ queries: we consider four sets $X, Y, Z, T$ of $2^{3n/4}$ random values, and we look for a quadruple $(x, y, z, t) \in X \times Y \times Z \times T$, such that

$$ \forall u \in \{0, 1, 2\}, \mathrm{MAC}(\phi_u(x)) \oplus \mathrm{MAC}(\psi_u(y)) \oplus \mathrm{MAC}(\phi_u(z)) \oplus \mathrm{MAC}(\psi_u(t)) = 0 $$
We expect on average one random quadruple (with $2^{3n}$ potential quadruples, and a $3n$-bit filtering), and one quadruple satisfying $\mathcal{R}$ (also a $3n$-bit condition). The correct quadruple can easily be checked with a few extra queries.

In practice, we use the generalized birthday algorithms of Section 2.2 in order to optimize the complexity of the attack. We consider four lists:

$$L_1 = \{\text{MAC}(\phi_0(x)) \parallel \text{MAC}(\phi_1(x)) \parallel \text{MAC}(\phi_2(x)) : x \in \mathcal{X}\}$$

$$L_2 = \{\text{MAC}(\psi_0(y)) \parallel \text{MAC}(\psi_1(y)) \parallel \text{MAC}(\psi_2(y)) : y \in \mathcal{Y}\}$$

$$L_3 = \{\text{MAC}(\phi_0(z)) \parallel \text{MAC}(\phi_1(z)) \parallel \text{MAC}(\phi_2(z)) : z \in \mathcal{Z}\}$$

$$L_4 = \{\text{MAC}(\psi_0(t)) \parallel \text{MAC}(\psi_1(t)) \parallel \text{MAC}(\psi_2(t)) : t \in \mathcal{T}\}$$

and we look for a quadruple $(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$. This can be done with $\tilde{O}(2^{3n/2})$ operations, using a memory of size $O(2^{3n/4})$. Finally, once a quadruple $(x, y, z, t)$ satisfying $\mathcal{R}(x, y, z, t)$ has been detected, it can be used to generate forgeries. Indeed, we can predict the MAC of a new message by making three new queries using Equation (1):

$$\forall u, \text{MAC}(\phi_u(x)) = \text{MAC}(\psi_u(y)) \oplus \text{MAC}(\psi_u(z)) \oplus \text{MAC}(\phi_u(t))$$

**Time-Query Trade-offs.** As opposed to the SUM-ECBC attack, we don't have an analogue to Equation (2) that can be used to reduce the time complexity. However, the time complexity of the algorithm can be slightly reduced when using more than $O(2^{3n/4})$ queries. If we consider sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \mathcal{T}$ of size $2^t$ with $3n/4 < t < n$, the resulting 4-sum is slightly easier, because there are $2^{4t-3n}$ expected solutions. Using the algorithm of section 2.2, this can be solved in time $\tilde{O}(2^{3n-2t})$, using a memory of size $O(2^t)$.

## 4.2 Attacking LightMAC+

LightMAC+ was designed by Naito [33] using ideas from PMAC+ [43] and LightMAC [29]. If we consider it as based on a tweakable block cipher $\tilde{E}$, it follows the same structure as PMAC+ (see Figure 5), but $\tilde{E}$ takes a message block smaller than $n$ bits:

$$\Sigma(M) = \bigoplus_{i=1}^{\ell} \tilde{E}_i(m_i) \qquad \tilde{E}_i(x) = E_1(i|x)$$

$$\Theta(M) = \bigoplus_{i=1}^{\ell} 2^{\ell-i} \odot \tilde{E}_i(m_i)$$

$$\text{MAC}(M) = E_2(\Sigma(M)) \oplus E_3(\Theta(M))$$

Since the structure of LightMAC+ is the same as the structure of PMAC+, we can use the same attack. The only difference from our point of view is that the message blocks are shorter than the block-size. As long as one message block is big enough to fit $2^{3n/4}$ different values, our attack will succeed.

This attack violates the improved security proof recently published at CT-RSA [34], with a security bound of $O(q_t^2 q_v / 2^{2n})$ (with $q_t$ MAC queries and $q_v$ verification queries). Indeed, our attack reaches a constant success probability with $q_t = O(2^{3n/4})$ and $q_v = 1$. We have shared our attack with Naito and he agreed that his proof is flawed.
<figure><img src="image_145.png" /><figcaption>Fig. 5. Diagram for LightMAC+ with (n − z)-bit blocks of a ℓ -block message where ( v )$_{z}$ is the value v written over z bits.</figcaption></figure>

4.3 Attacking 1kPMAC+

1kPMAC+ is a single-key variant of PMAC+ [43] designed by Datta, Dutta, Nandi, Paul and Zhang [9], shown in Figure 8.

Since the structure of 1kPMAC+ is the same as the structure of PMAC+, we can use the same attack. Alternatively, we can take advantage of the fix functions to mount a more straightforward attack, as shown in Section 6.

5 Attacking f9-like constructions

Our third attack is applicable to 3kf9 [44] and similar constructions. We have a universal forgery attack with O (2 3 n/ $^{4}$) queries and ¯ O (2 5 n/ $^{4}$) operations using memory O (2 $^{n}$), with a possible time-memory trade-offs.

5.1 Attacking 3kf9

3kf9 [44], designed by Xhang, Wu, Sui and Wang, is a three-key variant of the f9 mode used in 3G telephony. While the original f9 does not have security beyond the birthday bound [24], 3kf9 is secure up to 2 2 n/ 3 queries. We describe 3kf9 in Figure 6:

$$
\begin{align*}
\Sigma(M) &= \sigma_{\ell} & \sigma_{0} &= 0 \quad \sigma_{i} = E_{1}(\sigma_{i-1} \oplus m_{i}) \\
\Theta(M) &= \bigoplus_{i=1}^{\ell} \sigma_{i} & & \\
\mathrm{MAC}(M) &= E_{2}(\Sigma(M)) \oplus E_{3}(\Theta(M)) & &
\end{align*}
$$
**Attack.** Our attack follows the same structure as the previous attacks. We start with messages of the form:

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

and the corresponding MACs:

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

We use quadruples of messages X, Y, Z, T with

$$ X = \phi(x) \qquad Y = \psi(y) \qquad Z = \phi(z) \qquad T = \psi(t), $$

and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation:

$$ \begin{aligned} \mathcal{R}(x, y, z, t) &:= \begin{cases} \Sigma_0(x) = \Sigma_1(y) \\ \Sigma_0(z) = \Sigma_1(t) \\ \Theta_0(z) = \Theta_1(y) \\ \Theta_0(x) = \Theta_1(t). \end{cases} \\ &\Leftrightarrow \begin{cases} x \oplus E_1(0) = y \oplus E_1(1) \\ z \oplus E_1(0) = t \oplus E_1(1) \\ E_1(z \oplus E_1(0)) \oplus E_1(0) = E_1(y \oplus E_1(1)) \oplus E_1(1) \\ E_1(x \oplus E_1(0)) \oplus E_1(0) = E_1(t \oplus E_1(1)) \oplus E_1(1) \end{cases} \\ &\Leftrightarrow \begin{cases} x \oplus y \oplus z \oplus t = 0 \\ x \oplus y = E_1(0) \oplus E_1(1) \\ E_1(x \oplus E_1(0)) \oplus E_1(t \oplus E_1(1)) = E_1(0) \oplus E_1(1) \end{cases} \\ &\Rightarrow \text{MAC}(\phi(x)) \oplus \text{MAC}(\psi(y)) \oplus \text{MAC}(\phi(z)) \oplus \text{MAC}(\psi(t)) = 0. \end{aligned} $$

As in the previous attacks, $\mathcal{R}$ defines a $3n$-bit relation. Moreover, we can easily observe when $x \oplus y \oplus z \oplus t = 0$, and the relation $x \oplus y = E_1(0) \oplus E_1(1)$ can be verified across several quadruples. We don't have related quadruples satisfying $\mathcal{R}$ simultaneously as in the previous attacks, but we can use those properties to detect right quadruples. This leads to an attack with $\tilde{O}(2^{3n/4})$ queries: we consider four sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \mathcal{T}$ of $\sqrt[4]{n} \times 2^{3n/4}$ random values, and we look for quadruples $(x, y, z, t) \in \mathcal{X} \times \mathcal{Y} \times \mathcal{Z} \times \mathcal{T}$, such that:

$$ \left\{ \begin{array}{l} x \oplus y \oplus z \oplus t = 0 \\ \text{MAC}(\phi(x)) \oplus \text{MAC}(\psi(y)) \oplus \text{MAC}(\phi(z)) \oplus \text{MAC}(\psi(t)) = 0. \end{array} \right. \qquad (6) $$
<figure><img src="image_146.png" /><figcaption>Fig. 6. Diagram for 3kf9 with a $\ell$-block message.</figcaption></figure>

Since this a 2n-bit condition, we expect on average $n \cdot 2^n$ quadruples $(x, y, z, t)$ satisfying (6). In order to filter out the right ones, we look at the value $x \oplus y$ for all these quadruples. While the wrong quadruples should have a random $x \oplus y$, the right ones have $x \oplus y = E_1(0) \oplus E_1(1)$. Therefore, with high probability, the most frequent value for $x \oplus y$ is equal to $E_1(0) \oplus E_1(1)$, and quadruples satisfying this extra relation are right quadruples with probability 1/2. More precisely, we expect on average n wrong quadruples for each value of $x \oplus y$, and n right quadruples with $x \oplus y = E_1(0) \oplus E_1(1)$.

**Optimizing the time complexity.** While the algorithm of Section 2.2 would take time $\tilde{O}(2^{3n/2})$ with $\tilde{O}(2^{3n/4})$ queries, we can reduce the time complexity using sets $\mathcal{X}, \mathcal{Y}, \mathcal{Z}, \mathcal{T}$ with some structure. More precisely, we use:

$$ \mathcal{X} = \mathcal{Z} = \{x \in \{0,1\}^n : x_{[0:n/4]} = 0\} $$

$$ \mathcal{Y} = \mathcal{T} = \{x \in \{0,1\}^n : x_{[n/4:n/2]} = 0\} $$

so that quadruples can be written as

$$ x := x_3|x_2|x_1|0 \in \mathcal{X} $$

$$ y := y_3|y_2|0|y_0 \in \mathcal{Y} $$

$$ z := z_3|z_2|z_1|0 \in \mathcal{Z} $$

$$ t := t_3|t_2|0|t_0 \in \mathcal{T}. $$

In particular, right quadruples satisfy $x \oplus y \oplus z \oplus t = 0$, therefore $x_1 = z_1$, $y_0 = t_0$, and $x_3|x_2 \oplus z_3|z_2 = y_3|y_2 \oplus t_3|t_2$. We use these properties to adapt the algorithm of Section 2.2 and locate the quadruples efficiently. First we guess the n/2-bit value $\alpha_3|\alpha_2 := x_3|x_2 \oplus z_3|z_2 = y_3|y_2 \oplus t_3|t_2$. Then, for each $x = x_3|x_2|x_1|0$, there is a single candidate $z = (x_3 \oplus \alpha_3)|(x_2 \oplus \alpha_2)|x_1|0$ that could be part of a right quadruple. Similarly, every $y = y_3|y_2|0|y_0$ can be paired with a single
$t = (y_3 \oplus \alpha_3)|(y_2 \oplus \alpha_2)|0|y_0$. Therefore, we consider the two following lists:

$$L_1 = \{\text{MAC}(\phi(x_3|x_2|x_1|0)) \oplus \text{MAC}((x_3 \oplus \alpha_3)|(x_2 \oplus \alpha_2)|x_1|0) : x_3|x_2|x_1|0 \in \mathcal{X}\}$$

$$L_2 = \{\text{MAC}(\phi(y_3|y_2|0|y_0)) \oplus \text{MAC}((y_3 \oplus \alpha_3)|(y_2 \oplus \alpha_2)|0|y_0) : y_3|y_2|0|y_0 \in \mathcal{Y}\}$$

After sorting the lists, we look for matches, and the corresponding quadruples $x, y, z, t$ are exactly the quadruples satisfying

$$\left\{ \begin{array}{l} x \oplus y \oplus z \oplus t = 0 \\ (x \oplus z)_{[n/2:n]} = \alpha_3|\alpha_2 \\ \text{MAC}(\phi(x)) \oplus \text{MAC}(\psi(y)) \oplus \text{MAC}(\phi(z)) \oplus \text{MAC}(\psi(t)) = 0. \end{array} \right. \qquad (7)$$

More precisely, a match $L_1[x] = L_2[y]$ suggests $z = x \oplus \alpha_3|\alpha_2|0|0$ and $t = y \oplus \alpha_3|\alpha_2|0|0$, but there are four corresponding quadruples: $(x, y, z, t)$, $(z, y, x, t)$, $(x, t, z, y)$, $(z, t, x, y)$, and two candidate values for $E_1(0) \oplus E_1(1)$: $x \oplus y$ and $x \oplus y \oplus \alpha_3|\alpha_2|0|0$.

We need $\tilde{O}(2^{3n/4})$ operations to generate those quadruples. We repeat this $2^{n/2}$ times to exhaust all $n/2$-bit values $\alpha_3|\alpha_2$ and generate all quadruples satisfying (6). Finally, we use an array to count the number of occurrences of each possible value of $x \oplus y$. Each counter receives an average two values, but the counter corresponding to $E_1(0) \oplus E_1(1)$ will receive three values on average. After repeating all the operations $O(n)$ times, with some arbitrary constants in place of the zero bits, the highest counter corresponds to $E_1(0) \oplus E_1(1)$ with high probability, as proved in Section 5.2. This gives an attack with $\tilde{O}(2^{3n/4})$ queries, $\tilde{O}(2^{5n/4})$ operations, and $O(2^n)$ memory<fnref n="4" />.

**Time-Memory Trade-offs.** We can reduce the memory usage if we store only a subset of the counters, and repeat the whole algorithm until the whole set has been covered. Concretely, we store only the counters with a fixed value for bits $[0:n/8]$ and $[n/4:3n/8]$ of $x \oplus y$. Because of the way the lists $L_1$ and $L_2$ are constructed, we have actually fixed $n/8$ bits of $y_0$ and $x_1$, and we can reduce the lists to size $2^{5n/8}$. Therefore we evaluate $2^{3n/4}$ counters in time $\tilde{O}(2^{n/2} \cdot 2^{5n/8})$, using only $O(2^{3n/4})$ memory. We repeat iteratively over the full counter set, so we need time $\tilde{O}(2^{n/4} \cdot 2^{n/2} \cdot 2^{5n/8}) = \tilde{O}(2^{11n/8})$. More generally, we have a time-memory trade-off with time $\tilde{O}(2^{5n/4+t/2})$ and memory $O(2^{n-t})$ for $0 < t < n/4$.

**Forgeries.** Once we found a quadruple $(x, y, z, t)$ that respects $\mathcal{R}(x, y, z, t)$ we know that after processing message $\phi(x) = 0 \parallel x$ and $\psi(t) = 1 \parallel t$, there is no difference in the $\Theta$ part of the state ($\Theta_0(x) = \Theta_1(t)$). Moreover we have $\Theta_0(x) = \Sigma_0(x) \oplus E_1(0)$ and $\Theta_1(t) = \Sigma_1(x) \oplus E_1(1)$; this implies that there is a difference $E_1(0) \oplus E_1(1) = x \oplus y$ in the $\Sigma$ part of the state. Therefore, we can build a full state collision with message $0 \parallel x \parallel 0$ and $1 \parallel t \parallel x \oplus y$. In particular, the following relation can be used to create forgeries with an arbitrary message $m$ (of any length):

$$\text{MAC}(0 \parallel x \parallel 0 \parallel m) = \text{MAC}(1 \parallel t \parallel x \oplus y \parallel m).$$

<footnote n="4">⁴ We can actually reduce the polynomial factors by fixing only $(n - \log_2(n))/4$ bits to zero, in order to have sets of size $\sqrt{n} \cdot 2^{3n/4}$.</footnote>
**Universal Forgeries.** We can even forge the tag of an arbitrary message of length at least $(2n+2)$ blocks with complexity only $n+1$ times the complexity of the simple forgery attack. The technique is more advanced and inspired by the multi-collision attack described by Joux [23]. For ease of notation we'll show how to forge the signature for a message starting with $2n+2$ blocks of zero, but this can be trivially adapted for any message.

First, we find a quadruple $(x_1, y_1, z_1, t_1)$ as before. Then we consider messages $0 \parallel 0$ and $1 \parallel x_1 \oplus y_1$. Since $x_1 \oplus y_1 = E_1(0) \oplus E_1(1)$, we have $\Sigma(0 \parallel 0) = \Sigma(1 \parallel x_1 \oplus y_1)$, i. e. the $\Sigma$ part of the state collides. Moreover, we know the difference in the $\Theta$ part: $\Theta(0 \parallel 0) \oplus \Theta(1 \parallel x_1 \oplus y_1) = x_1 \oplus y_1$.

More generally, at step $i$ we use message injection functions

$$ \phi_i(x) = \underbrace{0 \parallel 0 \parallel \dots \parallel 0}_{\times 2(i-1)} \parallel 0 \parallel x \qquad \psi_i(x) = \underbrace{0 \parallel 0 \parallel \dots \parallel 0}_{\times 2(i-1)} \parallel 1 \parallel x, $$

to look for a quadruple of messages

$$ X_i = \phi_i(x_i) \qquad Y_i = \psi_i(y_i) \qquad Z_i = \phi_i(z_i) \qquad T_i = \psi_i(t_i). $$

When a right quadruple $(x_i, y_i, z_i, t_i)$ has been identified, we can deduce that the MACs for $0 \parallel 0 \parallel \dots \parallel 0 \parallel 0 \parallel 0$ and $0 \parallel 0 \parallel \dots \parallel 0 \parallel 1 \parallel x_i \oplus y_i$ will match on the $\Sigma$ branch and differ by $x_i \oplus y_i$ in their $\Theta$ branch.

After several iterations, we have actually built a multi-collision: all the messages $h_1 \parallel h_2 \parallel \dots \parallel h_n \parallel h_{n+1}$ with $h_i \in \{(1 \parallel x_i \oplus y_i), (0 \parallel 0)\}$ collide on the $\Sigma$ branch. In addition, we also know the difference in the $\Theta$ branch for those messages: it is equal to $\bigoplus_{\{i: h_i \neq 0 \parallel 0\}} (x_i \oplus y_i)$.

After at most $n+1$ steps, we can find a non empty subset $\mathcal{I} \subseteq [1:n+1]$ such that $\bigoplus_{i \in \mathcal{I}} (x_i \oplus y_i) = 0$ by simple linear algebra$^5$. This gives a collision on the full state, using messages $m_0 = 0 \parallel 0 \parallel \dots \parallel 0$ (with $2(n+1)$ blocks) and $h = h_1 \parallel h_2 \parallel \dots \parallel h_n \parallel h_{n+1}$ with $h_i = 1 \parallel x_i \oplus y_i$ if $i \in \mathcal{I}$, $h_i = 0 \parallel 0$ otherwise. Since the full state collides, we have for any message $m$ (of any length):

$$ \mathrm{MAC}(h \parallel m) = \mathrm{MAC}(m_0 \parallel m). $$

## 5.2 Detailed Complexity Analysis

We want to prove the claim that one will need to find $\mathcal{O}(n \cdot 2^n)$ quadruples in order to finish the attack on 3kf9 described in Section 5.1. We say the attack finishes when we recover the target value $T = E(0) \oplus E(1)$.

Assuming that each quadruple we find respects $\mathcal{R}$ with probability $1/2^n$, we fill a list of counters for every suspected values of $T$; a random quadruple gives two random values and a right one gives one value equal to $T$ and one random value. Therefore we sum up the distribution of an observable value $x$ as:

$$ x \begin{cases} \leftarrow \$ \{0, 1\}^n & \text{with probability } 1 - 1/2^{n+1} \\ \leftarrow T & \text{with probability } 1/2^{n+1} \end{cases} $$

<footnote>$^5$ We construct the kernel of the linear function $\lambda_i \mapsto \bigoplus_i \lambda_i (x_i \oplus y_i)$</footnote>
Let N be the number of observed values, and $X_i^c$ represents the indicator that the $i^{th}$ value equals c (following a Bernoulli distribution), so that the counter corresponding to c is $X^c = \sum_{i=1}^N X_i^c$. Now we have to discriminate between the distributions of $X^c$ with $c \neq T$, and the distribution of $X^T$:

$$ 
\begin{aligned}
\Pr(X_i^T = 1) &= \Pr(x = T) = (1 - 1/2^{n+1})/2^n + 1/2^{n+1} = (3/2 - 1/2^{n+1})/2^n \\
&\implies \mathbf{E}[X^T] = N(3/2 - 1/2^{n+1})/2^n \\
\Pr(X_i^c = 1) &= \Pr(x = c) = (1 - 1/2^{n+1})/2^n \\
&\implies \mathbf{E}[X^c] = N(1 - 1/2^{n+1})/2^n \\
&\implies \mathbf{E}[X^T] \geq 3/2 \cdot \mathbf{E}[X^c]
\end{aligned}
$$

We use the Chernoff bound to get a lower bound on the probability that a given counter is higher than the average value of $X^T$:

$$ \Pr(X^c \geq \mathbf{E}[X^T]) \leq \Pr(X^c \geq 3/2 \cdot \mathbf{E}[X^c]) \leq e^{-N(1-1/2^{n+1})/2^{n+1}} $$

and assuming the counters are independent:

$$ 
\begin{aligned}
\Pr(X^c < \mathbf{E}[X^T]) &\geq 1 - e^{-N(1-1/2^{n+1})/2^{n+1}} \\
\Pr(\forall c \neq T : X^c < \mathbf{E}[X^T]) &\geq (1 - e^{-N(1-1/2^{n+1})/2^{n+1}})^{2^n}
\end{aligned}
$$

This expression will asymptotically converge to a strictly positive constant when $e^{-N(1-1/2^{n+1})/2^{n+1}} \approx 2^{-n}$. Therefore, we use

$$ N \approx n \ln(2) \cdot \frac{2^{n+1}}{(1 - 1/2^{n+1})} = \mathcal{O}(n \cdot 2^n). $$

Since we observe 2 values per quadruples, this makes $\mathcal{O}(n \cdot 2^n)$ quadruples. Moreover, the event '$X^T \geq \mathbf{E}[X^T]$' has a probability close to 0.5, therefore after $\mathcal{O}(n \cdot 2^n)$ quadruples, we indeed have a $\mathcal{O}(1)$ probability that $X^T$ is greater than all of the other counters, which allows to recover the value $T$. Performing the attack until the end with probability $\mathcal{O}(1)$ also requires $\mathcal{O}(n \cdot 2^n)$ quadruples.

To get to this result some assumptions have been made, like the independence of the counters, but they all tend to be either conservative or asymptotically true.

## 5.3 Attacking 1kf9

1kf9 is a single-key variant of 3kf9 suggested in [8], and later withdrawn. Since the structure of 1kf9 is the same as the structure of 3kf9, we can use the same attack. However, in the next section, we give an attack with birthday complexity using properties of the fix functions.

## 6 Attacks using collision in fix functions

Finally, we show attacks against single key variant of beyond-birthday-bound MACs based on fix functions, as defined by Datta, Dutta, Nandi, Paul and
<figure><img src="image_147.png" /><figcaption>Fig. 7. Diagram for 1kf9 with a $\ell$-block message.</figcaption></figure>

Zhang [8,9]. The fix functions just fix the least significant bit an n-bit value to zero or one, and are used for domain separation:

$$ \text{fix0}: x \mapsto x_{[1:n]}|0 $$

$$ \text{fix1}: x \mapsto x_{[1:n]}|1 $$

Datta et al. used those function to build a single-key variant of PMAC+ called 1kPMAC+ [9], and a single-key variant of 3kf9 called 1kf9 [8], both with security up to $2^{2n/3}$ queries. However, 1kf9 has been withdrawn because of issues in its security proof. In this section, we exploit trivial collisions in the fix functions to build colliding pairs or quadruples more easily:

$$ \text{fix0}(x) = \text{fix0}(x \oplus 1) $$

$$ \text{fix1}(x) = \text{fix1}(x \oplus 1) $$

This allows a more straightforward attack against 1kPMAC+ with the same complexity as the attacks in Section 4, and an attack against 1kf9 [8] with birthday complexity, violating its security claims.

## 6.1 Attacking 1kf9

The 1kf9 mode uses the fix function for domain separation to build a single-key variant of 3kf9, as shown in Figure 7:

$$ \begin{aligned} \sigma_0 &= 0 \\ \Sigma'(M) &= \sigma_\ell \\ \Theta'(M) &= \bigoplus_{i=1}^\ell \sigma_i \\ \text{MAC}(M) &= E(\Sigma(M)) \oplus E(\Theta(M)) \end{aligned} $$

$$ \begin{aligned} \sigma_i &= E(\sigma_{i-1} \oplus m_i) \\ \Sigma(M) &= 2 \odot \text{fix0}(\Sigma'(M)) \\ \Theta(M) &= 2 \odot \text{fix1}(\Theta'(M)) \end{aligned} $$
**Attack.** Because of a mistake in the proof of 1kf9, we can use pairs of messages instead of quadruples. More precisely, instead of looking for a quadruple with pairwise collisions in $\Sigma$ and $\Theta$, we look for a pair of message X, Y colliding on $\Sigma'$, and with a difference in $\Theta'$ that will be absorbed by the fix1 function. Therefore, we define the relation $\mathcal{R}$ as:

$$ \mathcal{R}(X, Y) := \begin{cases} \Sigma'(X) = \Sigma'(Y) \\ 2\Theta'(X) = 2\Theta'(Y) \oplus 1 \\ \Rightarrow \mathrm{MAC}(X) = \mathrm{MAC}(Y). \end{cases} $$

We build the messages with different postfixes, parametrized by $u$:

$$ X = \phi_u(x) = x \parallel u \qquad Y = \psi_u(y) = y \parallel u \oplus d, $$

where $d$ is the inverse of 2 in the finite field. With this construction, we have

$$ \begin{aligned} \Sigma'(\phi_u(x)) &= E(u \oplus E(x \oplus E(0))) \\ \Theta'(\phi_u(x)) &= E(u \oplus E(x \oplus E(0))) \oplus E(x \oplus E(0)) \oplus E(0) \\ \Sigma'(\psi_u(y)) &= E(u \oplus d \oplus E(y \oplus E(0))) \\ \Theta'(\psi_u(y)) &= E(u \oplus d \oplus E(y \oplus E(0))) \oplus E(y \oplus E(0)) \oplus E(0) \end{aligned} $$

In particular, we observe

$$ \begin{aligned} E(x \oplus E(0)) \oplus E(y \oplus E(0)) &= d \Leftrightarrow \Sigma'(\phi_u(x)) = \Sigma'(\psi_u(y)) \\ &\Rightarrow \Theta'(\phi_u(x)) \oplus \Theta'(\psi_u(y)) = d \\ &\Rightarrow \mathrm{MAC}(\phi_u(x)) = \mathrm{MAC}(\psi_u(y)). \end{aligned} \quad (8) $$

From this observation, we construct a birthday attack against 1kf9. We build two lists:

$$ L_0 = \{\mathrm{MAC}(\phi_0(x)) : x < 2^{n/2}\} \qquad L_1 = \{\mathrm{MAC}(\psi_0(y)) : y < 2^{n/2}\}, $$

and we look for a match between the lists. We expect on average one pair to match randomly, and one pair to match because of (8). Moreover, when we have a collision candidate $L_0[x], L_1[y]$, we can verify whether it is a right pair by comparing $\mathrm{MAC}(x \parallel 1)$ and $\mathrm{MAC}(y \parallel d \oplus 1)$.

Therefore, we find a pair satisfying $\mathcal{R}(X, Y)$ with complexity $2^{n/2}$, and this leads to simple forgeries using (8). This contradicts the security proof of 1kf9 given in [8]. Note that this attack is still valid if we use different multiplications for the two branches in the finalization function.

## 6.2 Attacking 1kPMAC+

The 1kPMAC+ mode uses the fix function for domain separation to build a single-key variant of PMAC+, as shown in Figure 8.

$$ \begin{aligned} \Sigma'(M) &= \bigoplus_{i=1}^{\ell} \tilde{E}_i(m_i) \\ \Theta'(M) &= \bigoplus_{i=1}^{\ell} 2^{\ell+1-i} \odot \tilde{E}_i(m_i) \\ \mathrm{MAC}(M) &= E(\Sigma(M)) \oplus E(\Theta(M)) \end{aligned} \qquad \begin{aligned} \Sigma(M) &= \mathrm{fix0}(\Sigma'(M)) \\ \Theta(M) &= \mathrm{fix1}(\Theta'(M)) \end{aligned} $$
<figure><img src="image_148.png" /><figcaption>Fig. 8. Diagram for 1kPMAC+ with a $\ell$-block message where $\Delta_1 = E(1)$ and $\Delta_2 = E(2)$.</figcaption></figure>

**Attack.** Since the fix functions used in the finalization have collisions, we can build a variant of the attacks from Section 4 using differences in $\Sigma'$ and/or $\Theta'$ that are absorbed by the fix functions. More precisely, we use the following relation $\mathcal{R}$ on quadruple of messages:

$$ \mathcal{R}(X, Y, Z, T) := \begin{cases} \Sigma'(X) = \Sigma(Y)' \oplus 1 \\ \Theta'(Y) = \Theta(Z)' \oplus 1 \\ \Sigma'(Z) = \Sigma(T)' \oplus 1 \\ \Theta'(T) = \Theta(X)' \oplus 1 \end{cases} \Rightarrow \mathrm{MAC}(X) \oplus \mathrm{MAC}(Y) \oplus \mathrm{MAC}(Z) \oplus \mathrm{MAC}(T) = 0. $$

We can find quadruple of messages satisfying $\mathcal{R}$ using a single message injection function:

$$ \phi_u(i) = u \parallel i \\ X = \phi_u(x) = u \parallel x \quad Y = \psi_u(y) = u \parallel y \quad Z = \phi_u(z) = u \parallel z \quad T = \psi_u(t) = u \parallel t $$

Indeed we have

$$ \mathrm{MAC}(\phi_u(i)) = E(\mathrm{fix0}(\underbrace{\tilde{E}_1(u) \oplus \tilde{E}_2(x)}_{\Sigma'_u(i)})) \oplus E(\mathrm{fix1}(\underbrace{4\tilde{E}_1(u) \oplus 2\tilde{E}_2(x)}_{\Theta'_u(i)})) $$
We observe that:

$$ \begin{align*} \mathcal{R}(x, y, z, t) &\Leftrightarrow \left\{ \begin{array}{l} \tilde{E}_2(x) = \tilde{E}_2(y) \oplus 1 \\ \tilde{E}_2(z) = \tilde{E}_2(t) \oplus 1 \\ 2\tilde{E}_2(x) = 2\tilde{E}_2(z) \oplus 1 \\ 2\tilde{E}_2(y) = 2\tilde{E}_2(t) \oplus 1 \end{array} \right. \\ &\Leftrightarrow \left\{ \begin{array}{l} \tilde{E}_2(x) \oplus \tilde{E}_2(y) \oplus \tilde{E}_2(z) \oplus \tilde{E}_2(t) = 0 \\ \tilde{E}_2(x) = \tilde{E}_2(y) \oplus 1 \\ \tilde{E}_2(x) = \tilde{E}_2(z) \oplus d \end{array} \right. \end{align*} $$

Therefore, $\mathcal{R}$ defines a 3n-bit relation that is independent of the value $u$. This can be used for attacks in the same way as in the previous sections, using a single list

$$ L = \{ \mathrm{MAC}(\phi_0(x)) \parallel \mathrm{MAC}(\phi_1(x)) \parallel \mathrm{MAC}(\phi_2(x)) : x < 2^{3n/4} \} $$

We can find a quadruple of four distinct values $(x, y, z, t)$ such that $L[x] \oplus L[y] \oplus L[z] \oplus L[t] = 0$ with $\tilde{O}(2^{3n/2})$ operations, using a memory of size $O(2^{3n/4})$, and this easily leads to forgeries.

# 7 Conclusion

In this paper we have introduced a cryptanalysis technique to attack double-block-hash MACs using quadruples of messages. We show three variants of the technique, with attacks with $O(2^{3n/4})$ queries against SUM-ECBC, GCM-SIV2, PMAC+, LightMAC+, 1kPMAC+ and 3kf9. All these modes have a security proof up to $2^{2n/3}$ queries, but no attacks with fewer than $2^n$ queries were known before our work.

Our main attacks are in the information theoretic model, and an attacker would need more than $2^n$ operations to perform a forgery. On the other hand, we also have a variant of the attack against SUM-ECBC and GCM-SIV2 with time complexity $\tilde{O}(2^{6n/7})$. This opens the path for attack with total complexity below $2^n$ for other double-block-hash MACs.

We believe that studying generic attacks is important in order to understand the security of these MACs, and is needed in addition to security proofs. In particular our results show that they do not reach full security, and we invalidate a recent proof for LightMAC+. However, there is still a gap between the $2^{2n/3}$ bound of the proofs, and our attacks with $O(2^{3n/4})$ queries. Further work is needed to determine whether the attacks can be improved, or whether better proofs are possible.

# Acknowledgement

Mridul Nandi is supported by R.C.Bose Centre for Cryptology and Security. Part of this work was supported by the French DGA.
## A SageMath Implementation

In order to verify that the algorithm is correct, we have implemented the attack against SUM-ECBC with complexity $\tilde{O}(2^{6n/7})$ given in Section 3.1 with SageMath:

```python
xor = lambda x, y: x.__xor__(y)
txor = lambda a,b: tuple(xor(u,v) for u,v in zip(a,b))
def random_perm(n):
    pp = Permutations(n).randomElement()
    return lambda x: pp(x+1)-1

def CBC(E,M):
    x = 0
    for m in M:
        x = E(x.__xor__(m))
    return x
def SUMECBC(E1,E2,E3,E4,M):
    a = E2(CBC(E1,M))
    b = E4(CBC(E3,M))
    return a.__xor__(b)

E1, E2, E3, E4 = (random_perm(2^21) for _ in range(4))
MAC = lambda x: SUMECBC(E1,E2,E3,E4,x)
print "Values to recover | {0:06x} {1:06x}".format(
    xor(E1(0),E1(1)), xor(E3(0),E3(1)))

print "Generating data..."
L1,L2,L3,L4 = [], [], [], []
for i in range(2^12):
    if (i&0b0000000000111 == 0): L1.append(i)
    if (i&0b0000000111000 == 0): L2.append(i)
    if (i&0b0001110000000 == 0): L3.append(i)
    if (i&0b1110000000000 == 0): L4.append(i)
def macs(u,i):
    x = (0,0)
    for j in range(i,2^21,2^12):
        x = txor(x,(MAC([u,j]), MAC([u, xor(1,j)])))
    return (i,x)
L1 = [macs(0,i) for i in L1]
L2 = [macs(0,i) for i in L2]
L3 = [macs(1,i) for i in L3]
L4 = [macs(1,i) for i in L4]

print "Looking for quadruples..."
L13 = sorted((txor(a[1],b[1]),a[0],b[0]) for a in L1 for b in L3)
L24 = sorted((txor(a[1],b[1]),a[0],b[0]) for a in L2 for b in L4)
```
i,j = 0,0
while i<len(L13) and j<len(L24):
    if L13[i][0] == L24[j][0]:
        if L13[i] != L24[j]:
            print "{:06x} {:06x} {:06x} {:06x} | {:06x} {:06x}".format(
                L13[i][1], L13[i][2], L24[j][1], L24[j][2],
                xor(L13[i][1],L13[i][2]), xor(L13[i][1],L24[j][2]))
        if L13[i] < L24[j]:
            i+=1
        else:
            j+=1
    elif L13[i][0] < L24[j][0]:
        i+=1
    else:
        j+=1

## References

1. An, J.H., Bellare, M.: Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions. In: Wiener, M.J. (ed.) CRYPTO'99. LNCS, vol. 1666, pp. 252-269. Springer, Heidelberg (Aug 1999)

2. Bellare, M., Canetti, R., Krawczyk, H.: Keying hash functions for message authentication. In: Koblitz, N. (ed.) CRYPTO'96. LNCS, vol. 1109, pp. 1-15. Springer, Heidelberg (Aug 1996)

3. Bellare, M., Guérin, R., Rogaway, P.: XOR MACs: New methods for message authentication using finite pseudorandom functions. In: Coppersmith, D. (ed.) CRYPTO'95. LNCS, vol. 963, pp. 15-28. Springer, Heidelberg (Aug 1995)

4. Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences 61(3), 362-399 (2000)

5. Black, J., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 384-397. Springer, Heidelberg (Apr / May 2002)

6. Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 209-221. Springer, Heidelberg (Apr / May 2002)

7. Cogliati, B., Seurin, Y.: EWCDM: An efficient, beyond-birthday secure, nonce-misuse resistant MAC. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 121-149. Springer, Heidelberg (Aug 2016)

8. Datta, N., Dutta, A., Nandi, M., Paul, G., Zhang, L.: Building single-key beyond birthday bound message authentication code. Cryptology ePrint Archive, Report 2015/958 (2015), http://eprint.iacr.org/2015/958

9. Datta, N., Dutta, A., Nandi, M., Paul, G., Zhang, L.: Single key variant of PMAC_Plus. IACR Trans. Symm. Cryptol. 2017(4), 268-305 (2017)

10. Dinur, I., Leurent, G.: Improved generic attacks against hash-based MACs and HAIFA. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 149-168. Springer, Heidelberg (Aug 2014)
11. Dutta, A., Jha, A., Nandi, M.: Tight security analysis of EHtM MAC. IACR Trans. Symm. Cryptol. 2017(3), 130–150 (2017)

12. Ferguson, N.: Authentication weaknesses in GCM. Comment to NIST (2005), http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf

13. Computer data authentication. National Bureau of Standards, NIST FIPS PUB 113, U.S. Department of Commerce (1985)

14. Fuhr, T., Leurent, G., Suder, V.: Collision attacks against CAESAR candidates - forgery and key-recovery against AEZ and Marble. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part II. LNCS, vol. 9453, pp. 510–532. Springer, Heidelberg (Nov / Dec 2015)

15. Gilbert, E.N., MacWilliams, F.J., Sloane, N.J.: Codes which detect deception. Bell Labs Technical Journal 53(3), 405–424 (1974)

16. Guo, J., Peyrin, T., Sasaki, Y., Wang, L.: Updates on generic attacks against HMAC and NMAC. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 131–148. Springer, Heidelberg (Aug 2014)

17. Iwata, T.: New blockcipher modes of operation with beyond the birthday bound security. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 310–327. Springer, Heidelberg (Mar 2006)

18. Iwata, T., Kurosawa, K.: OMAC: One-key CBC MAC. In: Johansson, T. (ed.) FSE 2003. LNCS, vol. 2887, pp. 129–153. Springer, Heidelberg (Feb 2003)

19. Iwata, T., Mennink, B., Vizár, D.: CENC is optimally secure. Cryptology ePrint Archive, Report 2016/1087 (2016), http://eprint.iacr.org/2016/1087

20. Iwata, T., Minematsu, K.: Stronger security variants of GCM-SIV. IACR Trans. Symm. Cryptol. 2016(1), 134–157 (2016), http://tosc.iacr.org/index.php/ToSC/article/view/539

21. Iwata, T., Minematsu, K., Peyrin, T., Seurin, Y.: ZMAC: A fast tweakable block cipher mode for highly secure message authentication. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 34–65. Springer, Heidelberg (Aug 2017)

22. Jaulmes, E., Joux, A., Valette, F.: On the security of randomized CBC-MAC beyond the birthday paradox limit: A new construction. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 237–251. Springer, Heidelberg (Feb 2002)

23. Joux, A.: Multicollisions in iterated hash functions. Application to cascaded constructions. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 306–316. Springer, Heidelberg (Aug 2004)

24. Knudsen, L.R., Mitchell, C.J.: Analysis of 3gpp-mac and two-key 3gpp-mac. Discrete Applied Mathematics 128(1), 181 – 191 (2003), http://www.sciencedirect.com/science/article/pii/S0166218X02004444, international Workshop on Coding and Cryptography (WCC2001).

25. Lee, C., Kim, J., Sung, J., Hong, S., Lee, S.: Forgery and key recovery attacks on PMAC and mitchell's TMAC variant. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 06. LNCS, vol. 4058, pp. 421–431. Springer, Heidelberg (Jul 2006)

26. Leurent, G., Peyrin, T., Wang, L.: New generic attacks against hash-based MACs. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 1–20. Springer, Heidelberg (Dec 2013)

27. List, E., Nandi, M.: Revisiting full-PRF-secure PMAC and using it for beyond-birthday authenticated encryption. In: Handschuh, H. (ed.) CT-RSA 2017. LNCS, vol. 10159, pp. 258–274. Springer, Heidelberg (Feb 2017)

28. List, E., Nandi, M.: ZMAC<sup>+</sup> – an efficient variable-output-length variant of ZMAC. IACR Trans. Symm. Cryptol. 2017(4), 306–325 (2017)
29. Luykx, A., Preneel, B., Tischhauser, E., Yasuda, K.: A MAC mode for lightweight block ciphers. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 43–59. Springer, Heidelberg (Mar 2016)

30. Mennink, B., Neves, S.: Encrypted davies-meyer and its dual: Towards optimal security using mirror theory. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part III. LNCS, vol. 10403, pp. 556–583. Springer, Heidelberg (Aug 2017)

31. Minematsu, K.: How to thwart birthday attacks against MACs via small randomness. In: Hong, S., Iwata, T. (eds.) FSE 2010. LNCS, vol. 6147, pp. 230–249. Springer, Heidelberg (Feb 2010)

32. Naito, Y.: Full PRF-secure message authentication code based on tweakable block cipher. In: Au, M.H., Miyaji, A. (eds.) ProvSec 2015. LNCS, vol. 9451, pp. 167–182. Springer, Heidelberg (Nov 2015)

33. Naito, Y.: Blockcipher-based MACs: Beyond the birthday bound without message length. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017, Part III. LNCS, vol. 10626, pp. 446–470. Springer, Heidelberg (Dec 2017)

34. Naito, Y.: Improved security bound of LightMAC_Plus and its single-key variant. In: Smart, N.P. (ed.) CT-RSA 2018. LNCS, vol. 10808, pp. 300–318. Springer, Heidelberg (Apr 2018)

35. Nikolic, I., Sasaki, Y.: Refinements of the k-tree algorithm for the generalized birthday problem. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015, Part II. LNCS, vol. 9453, pp. 683–703. Springer, Heidelberg (Nov / Dec 2015)

36. Peyrin, T., Wang, L.: Generic universal forgery attack on iterative hash-based MACs. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 147–164. Springer, Heidelberg (May 2014)

37. Preneel, B., van Oorschot, P.C.: MDx-MAC and building fast MACs from hash functions. In: Coppersmith, D. (ed.) CRYPTO’95. LNCS, vol. 963, pp. 1–14. Springer, Heidelberg (Aug 1995)

38. Preneel, B., van Oorschot, P.C.: On the security of two MAC algorithms. In: Maurer, U.M. (ed.) EUROCRYPT’96. LNCS, vol. 1070, pp. 19–32. Springer, Heidelberg (May 1996)

39. Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 16–31. Springer, Heidelberg (Dec 2004)

40. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (Aug 2002)

41. Wegman, M.N., Carter, L.: New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22, 265–279 (1981)

42. Yasuda, K.: The sum of CBC MACs is a secure PRF. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 366–381. Springer, Heidelberg (Mar 2010)

43. Yasuda, K.: A new variant of PMAC: Beyond the birthday bound. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 596–609. Springer, Heidelberg (Aug 2011)

44. Zhang, L., Wu, W., Sui, H., Wang, P.: 3kf9: Enhancing 3GPP-MAC beyond the birthday bound. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 296–312. Springer, Heidelberg (Dec 2012)
# Breaking Symmetric Cryptosystems using Quantum Period Finding

Marc Kaplan$^{1,2}$, Gaëtan Leurent$^3$ Anthony Leverrier$^3$, and María Naya-Plasencia$^3$

$^1$LTCI, Télécom ParisTech, 23 avenue d'Italie, 75214 Paris CEDEX 13, France

$^2$School of Informatics, University of Edinburgh,
10 Crichton Street, Edinburgh EH8 9AB, UK

$^3$Inria Paris, France

**Abstract.** Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, 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 it.

We study applications of a quantum procedure called *Simon's algorithm* (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using 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 attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption (e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF.

Second, we show that Simon's algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

**Keywords:** post-quantum cryptography, symmetric cryptography, quantum attacks, block ciphers, modes of operation, slide attack.

# 1 Introduction

The goal of post-quantum cryptography is to prepare cryptographic primitives to resist quantum adversaries, i.e. adversaries with access to a quantum computer.
Indeed, cryptography would be particularly affected by the development of large-scale quantum computers. While currently used asymmetric cryptographic primitives would suffer from devastating attacks due to Shor's algorithm [42], the status of symmetric ones is not so clear: generic attacks, which define the security of ideal symmetric primitives, would get a quadratic speed-up thanks to Grover's algorithm [23], hinting that doubling the key length could restore an equivalent ideal security in the post-quantum world. Even though the community seems to consider the issue settled with this solution [6], only very little is known about real world attacks, that determine the real security of used primitives. Very recently, this direction has started to draw attention, and interesting results have been obtained. New theoretical frameworks to take into account quantum adversaries have been developed [11, 12, 19, 22, 15, 2].

Simon's algorithm [43] is central in quantum algorithm theory. Historically, it was an important milestone in the discovery by Shor of his celebrated quantum algorithm to solve integer factorization in polynomial time [42]. Interestingly, Simon's algorithm has also been applied in the context of symmetric cryptography. It was first used to break the 3-round Feistel construction [30] and then to prove that the Even-Mansour construction [31] is insecure with superposition queries. While Simon's problem (which is the problem solved with Simon's algorithm) might seem artificial at first sight, it appears in certain constructions in symmetric cryptography, in which ciphers and modes typically involve a lot of structure.

These first results, although quite striking, are not sufficient for evaluating the security of actual ciphers. Indeed, the confidence we have on symmetric ciphers depends on the amount of cryptanalysis that was performed on the primitive. Only this effort allows researchers to define the security margin which measures how far the construction is from being broken. Thanks to the large and always updated cryptanalysis toolbox built over the years in the *classical* world, we have solid evaluations of the security of the primitives against classical adversaries. This is, however, no longer the case in the post-quantum world, *i.e.* when considering quantum adversaries.

We therefore need to build a complete cryptanalysis toolbox for quantum adversaries, similar to what has been done for the classical world. This is a fundamental step in order to correctly evaluate the post-quantum security of current ciphers and to design new secure ciphers for the post-quantum world.

**Our results.** We make progresses in this direction, and open new surprising and important ranges of applications for Simon's algorithm in symmetric cryptography:

1. The original formulation of Simon's algorithm is for functions whose collisions happen only at some hidden period. We extend it to functions that have more collisions. This leads to a better analysis of previous applications of Simon's algorithm in symmetric cryptography.

2. We then show an attack against the LRW construction, used to turn a block-cipher into a tweakable block cipher [32]. Like the results on 3-round Feistel and Even-Mansour, this is an example of construction with provable security in the classical setting that becomes insecure against a quantum adversary.
3. Next, we study block cipher modes of operation. We show that some of the most common modes for message authentication and authenticated encryption are completely broken in this setting. We describe forgery attacks against standardized modes (CBC-MAC, PMAC, GMAC, GCM, and OCB), and against several CAESAR candidates, with complexity only $O(n)$, where $n$ is the size of the block. In particular, this partially answers an open question by Boneh and Zhandry [13]: "Do the CBC-MAC or NMAC constructions give quantum-secure PRFs?".

Those results are in stark contrast with a recent analysis of encryption modes in the same setting: Anand et al. show that some classical encryption modes are secure against a quantum adversary when using a quantum-secure PRF [3]. Our results imply that some authentication and authenticated encryption schemes remain insecure with any block cipher.

4. The last application is a quantization of slide attacks, a popular family of cryptanalysis that is independent of the number of rounds of the attacked cipher. Our result is the first exponential speed-up obtained directly by a quantization of a classical cryptanalysis technique, with complexity dropping from $O(2^{n/2})$ to $O(n)$, where $n$ is the size of the block.

These results imply that for the symmetric primitives we analyze, doubling the key length is not sufficient to restore security against quantum adversaries. A significant effort on quantum cryptanalysis of symmetric primitives is thus crucial for our long-term trust in these cryptosystems.

**The attack model.** We consider attacks against classical cryptosystems using quantum resources. This general setting broadly defines the field of post-quantum cryptography. But attacking specific cryptosystems requires a more precise definition of the operations the adversary is allowed to perform. The simplest setting allows the adversary to perform local quantum computation. For instance, this can be modeled by the quantum random oracle model, in which the adversary can query the oracle in an arbitrary superposition of the inputs [11,14,48,44]. A more practical setting allows quantum queries to the hash function used to instantiate the oracle on a quantum computer.

We consider here a much stronger model in which, in addition to local quantum operations, an adversary is granted an access to a possibly remote cryptographic oracle in superposition of the inputs, and obtains the corresponding superposition of outputs. In more detail, if the encryption oracle is described by a classical function $O_k : \{0,1\}^n \to \{0,1\}^n$, then the adversary can make standard quantum queries $|x\rangle|y\rangle \mapsto |x\rangle|O_k(x) \oplus y\rangle$, where $x$ and $y$ are arbitrary $n$-bit strings and $|x\rangle$, $|y\rangle$ are the corresponding $n$-qubit states expressed in the computational basis. A circuit representing the oracle is given in Figure 1. Moreover, any superposition $\sum_{x,y} \lambda_{x,y} |x\rangle|y\rangle$ is a valid input to the quantum oracle, who then returns $\sum_{x,y} \lambda_{x,y} |x\rangle|y \oplus O_k(x)\rangle$. In previous works, these attacks have been called superposition attacks [19], quantum chosen message attacks [13] or quantum security [47].
<figure><img src="image_149.png" /><figcaption>Fig. 1. The quantum cryptographic oracle.</figcaption></figure>

Simon's algorithm requires the preparation of the uniform superposition of all *n*-bit strings, $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|0\rangle^4$. For this input, the quantum encryption oracle returns $\frac{1}{\sqrt{2^n}} \sum_x |x\rangle|O_k(x)\rangle$, the superposition of all possible pairs of plaintext-ciphertext. It might seem at first that this model gives an overwhelming power to the adversary and is therefore uninteresting. Note, however, that the laws of quantum mechanics imply that the measurement of such a 2*n*-qubit state can only reveal 2*n* bits of information, making this model nontrivial.

The simplicity of this model, together with the fact that it encompasses any reasonable model of quantum attacks makes it very interesting. For instance, [12] gave constructions of message authenticated codes that remain secure against superposition attacks. A similar approach was initiated by [19], who showed how to construct secure multiparty protocols when an adversary can corrupt the parties in superposition. A protocol that is proven secure in this model may truthfully be used in a quantum world.

Our work shows that superposition attacks, although they are not trivial, allow new powerful strategies for the adversary. Modes of operation that are provably secure against classical attacks can then be broken. There exist a few options to prevent the attacks that we present here. A possibility is to forbid all kind of quantum access to a cryptographic oracle. In a world where quantum resources become available, this restriction requires a careful attention. This can be achieved for example by performing a quantum measurement of any incoming quantum query to the oracle. But this task involves meticulous engineering of quantum devices whose outcome remains uncertain. Even information theoretically secure quantum cryptography remains vulnerable to attacks on their implementations, as shown by attacks on quantum key distribution [49,34,45].

A more realistic approach is to develop a set of protocols that remains secure against superposition attacks. Another advantage of this approach is that it also covers more advanced scenarios, for example when an encryption device is given to the adversary as an obfuscated algorithm. Our work shows how important it is to develop protocols that remain secure against superposition attacks.

Regarding symmetric cryptanalysis, we have already mentioned the protocol of Boneh and Zhandry for MACs that remains secure against superposition attacks. In particular, we answer negatively to their question asking whether CBC-MAC is secure in their model. Generic quantum attacks against symmetric cryptosystems have also been considered. For instance, [27] studies the security of iterated block ciphers, and Anand et al. investigated the security of various

<footnote n="4">⁴ When there is no ambiguity, we write $|0\rangle$ for the state $|0\dots0\rangle$ of appropriate length.</footnote>
modes of operations for encryption against superposition attacks [3]. They show
that OFB and CTR remain secure, while CBC and CFB are not secure in general
(with attacks involving Simon's algorithm), but are secure if the underlying PRF
is quantum secure. Recently, [28] considers symmetric families of cryptanalysis,
describing quantum versions of differential and linear attacks.

Cryptographic notions like indistinguishability or semantic security are well
understood in a classical world. However, they become difficult to formalize when
considering quantum adversaries. The quantum chosen message model is a good
framework to study these [22,15,2].

In this paper, 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 quantum setting, we follow the EUF-qCMA security definition that was
given by Boneh and Zhandry [12]. 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.

**Organization.** The paper is organized as follows. First, Section 2 introduces Simon's algorithm and explains how to modify it in order to handle functions that only approximately satisfy Simon's promise. This variant seems more appropriate for symmetric cryptography and may be of independent interest. Section 3 summarizes known quantum attacks against various constructions in symmetric cryptography. Section 4 presents the attack against the LRW constructions. In Section 5, we show how Simon's algorithm can be used to obtain devastating attacks on several widely used modes of operations: CBC-MAC, PMAC, GMAC, GCM, OCB, as well as several CAESAR candidates. Section 6 shows the application of the algorithm to slide attacks, providing an exponential speed-up. The paper ends in Section 7 with a conclusion, pointing out possible new directions and applications.

## 2 Simon's algorithm and attack strategy

In this section, we present Simon's problem [43] and the quantum algorithm
for efficiently solving it. The simplest version of our attacks directly exploits
this algorithm in order to recover some secret value of the encryption algorithm.
Previous works have already considered such attacks against 3-round Feistel
schemes and the Even-Mansour construction (see Section 3 for details).

Unfortunately, it is not always possible to recast an attack in terms of Simon's
problem. More precisely, Simon's problem is a promise problem, and in many
cases, the relevant promise (that only a structured class of collisions can occur)
is not satisfied, far from it in fact. We show in Theorem 1 below that, however,
these additional collisions do not lead to a significant increase of the complexity
of our attacks.

### 2.1 Simon's problem and algorithm

We first describe Simon's problem, and then the quantum algorithm for solving it.
We refer the reader to the recent review by Montanaro and de Wolf on quantum
property testing for various applications of this algorithm [37]. We assume here a basic knowledge of the quantum circuit model. We denote the addition and multiplication in a field with $2^n$ elements by “⊕” and “:”, respectively.

We consider that the access to the input of Simon's problem, a function $f$, is made by querying it. A classical query oracle is a function $x \mapsto f(x)$. To run Simon's algorithm, it is required that the function $f$ can be queried quantum-mechanically. More precisely, it is supposed that the algorithm can make arbitrary quantum superpositions of queries of the form $|x\rangle|0\rangle \mapsto |x\rangle|f(x)\rangle$.

Simon's problem is the following:

**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 with quantum complexity $O(n)$. Recall that the Hadamard transform $H^{\otimes n}$ applied on an $n$-qubit state $|x\rangle$ for some $x \in \{0,1\}^n$ gives $H^{\otimes n}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle$, where $x \cdot y := x_1y_1 \oplus \cdots \oplus x_ny_n$.

The algorithm repeats the following five quantum steps.

1. Starting with a $2n$-qubit state $|0\rangle|0\rangle$, one applies a Hadamard transform $H^{\otimes n}$ to the first register to obtain the quantum superposition

$$ \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle|0\rangle. $$

2. A quantum query to the function $f$ maps this to the state

$$ \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle|f(x)\rangle. $$

3. Measuring the second register in the computational basis yields a value $f(z)$ and collapses the first register to the state:

$$ \frac{1}{\sqrt{2}} (|z\rangle + |z \oplus s\rangle). $$

4. Applying again the Hadamard transform $H^{\otimes n}$ to the first register gives:

$$ \frac{1}{\sqrt{2}} \frac{1}{\sqrt{2^n}} \sum_{y \in \{0,1\}^n} (-1)^{y \cdot z} (1 + (-1)^{y \cdot s}) |y\rangle. $$

5. The vectors $y$ such that $y \cdot s = 1$ have amplitude 0. Therefore, measuring the state in the computational basis yields a random vector $y$ such that $y \cdot s = 0$.

By repeating this subroutine $O(n)$ times, one obtains $n-1$ independent vectors orthogonal to $s$ with high probability, and $s$ can be recovered using basic linear algebra. Theorem 1 gives the trade-off between the number of repetitions of the subroutine and the success probability of the algorithm.
## 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 many more collisions than those of this form. 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 $O(n)$ queries. Theorem 1 rules this out provided that $f$ does not have too many collisions of the form $f(x) = f(x \oplus t)$ for some $t \notin \{0, s\}$.

For $f: \{0, 1\}^n \to \{0, 1\}^n$ such that $f(x \oplus s) = f(x)$ for all $x$, consider

$$ \varepsilon(f, s) = \max_{t \in \{0,1\}^n \setminus \{0,s\}} \mathrm{Pr}_x[f(x) = f(x \oplus t)]. \quad (1) $$

This parameter quantifies how far the function is from satisfying Simon's promise. For a random function, one expects $\varepsilon(f, s) = \Theta(n2^{-n})$, following the analysis of [18]. On the other hand, for a constant function, $\varepsilon(f, s) = 1$ and it is impossible to recover $s$.

The following theorem, whose proof can be found in Appendix A, shows the effect of unwanted collisions on the success probability of Simon's algorithm.

**Theorem 1 (Simon's algorithm with approximate promise).** If $\varepsilon(f, s) \le p_0 < 1$, then Simon's algorithm returns $s$ with $cn$ queries, with probability at least $1 - (2(\frac{1+p_0}{2})^c)^n$.

In particular, choosing $c \ge 3/(1-p_0)$ ensures that the error decreases exponentially with $n$. To apply our results, it is therefore sufficient to prove that $\varepsilon(f, s)$ is bounded away from 1.

Finally, if we apply Simon's algorithm without any bound on $\varepsilon(f, s)$, we can not always recover $s$ unambiguously. Still if we select a random value $t$ orthogonal to all vectors $u_i$ returned by each step of the algorithm, $t$ satisfy $f(x \oplus t) = f(x)$ with high probability.

**Theorem 2 (Simon's algorithm without promise).** After $cn$ steps of Simon's algorithm, if $t$ is orthogonal to all vectors $u_i$ returned by each step of the algorithm, then $\mathrm{Pr}_x[f(x \oplus t) = f(t)] \ge p_0$ with probability at least $1 - (2(\frac{1+p_0}{2})^c)^n$.

In particular, choosing $c \ge 3/(1-p_0)$ ensures that the probability is exponentially close to 1.

## 2.3 Attack strategy

The general strategy behind our attacks exploiting Simon's algorithm is to start with the encryption oracle $E_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 he has quantum oracle access to $E_k$, and the knowledge of the string $s$ should be sufficient to break the cryptographic scheme. In the following, this function is called Simon's function.
In most cases, our attacks correspond to a classical collision attack. In particular, the value $s$ will usually be the difference in the internal state after processing a fixed pair of messages $(\alpha_0, \alpha_1)$, i.e. $s = E(\alpha_0) \oplus E(\alpha_1)$. The input of $f$ will be inserted into the state with the difference $s$ so that $f(x) = f(x \oplus s)$.

In our work, this function $f$ is of the form:

$$f^1 : x \mapsto P(\tilde{E}(x) + \tilde{E}(x \oplus s)) \quad \text{or,} \\ f^2 : b, x \mapsto \begin{cases} \tilde{E}(x) & \text{if } b = 0, \\ \tilde{E}(x \oplus s) & \text{if } b = 1, \end{cases}$$

where $\tilde{E}$ is a simple function obtained from $E_k$ and $P$ a permutation. It is immediate to see that $f^1$ and $f^2$ have periods $s$ for $f^1$ or $1 \mid s$ for $f^2$.

In most applications, Simon's function satisfies $f(x) = f(y)$ for $y \oplus x \in \{0, s\}$, but also for additional inputs $x, y$. Theorem 1 extends Simon's algorithm precisely to this case. In particular, if the additional collisions of $f$ are random, then Simon's algorithm is successful. When considering explicit constructions, we can not in general prove that the unwanted collisions are random, but rather that they look random enough. In practice, if the function $\varepsilon(f, s)$ is not bounded, then some of the primitives used in the construction have are far from ideal. We can show that this happens with low probability, and would imply a classical attack against the system. Applying Theorem 1 is not trivial, but it stretches the range of application of Simon's algorithm far beyond its original version.

**Construction of Simon's functions.** To make our attacks as clear as possible, we provide the diagrams of circuits computing the function $f$. These circuits use a little number of basic building blocks represented in Figure 2.

In our attacks, we often use a pair of arbitrary constants $\alpha_0$ and $\alpha_1$. The choice of the constant is indexed by a bit $b$. We denote by $U_\alpha$ the gate that maps $b$ to $\alpha_b$ (See Figure 2.1). For simplicity, we ignore here the additional qubits required in practice to make the transform reversible through padding.

Although it is well known that arbitrary quantum states cannot be cloned, we use the CNOT gate to copy classical information. More precisely, a CNOT gate can copy states in the computational basis: $\text{CNOT}: |x\rangle|0\rangle \rightarrow |x\rangle|x\rangle$. This transform is represented in Figure 2.2.

Finally, any unitary transform $U$ can be controlled by a bit $b$. This operation, denoted $U^b$ maps $x$ to $U(x)$ if $b = 1$ and leaves $x$ unchanged otherwise. In the quantum setting, the qubit $|b\rangle$ can be in a superposition of 0 and 1, resulting in a superposition of $|x\rangle$ and $|U(x)\rangle$. The attacks that we present in the following sections only make use of this procedure when the attacker knows a classical description of the unitary to be controlled. In particular, we do not apply it to the cryptographic oracle.

When computing Simon's function, i.e. the function $f$ on which Simon's algorithm is applied, the registers containing the value of $f$ must be unentangled with any other working register. Otherwise, these registers, which might hinder the periodicity of the function, have to be taken into account in Simon's algorithm and the whole procedure could fail.
<figure><img src="image_150.png" /><figcaption>2.1. One-to-one mapping.</figcaption></figure>

<caption>2.2. CNOT gate.</caption>

<caption>2.3. Controlled Unitary.</caption>

Fig. 2. Circuit representation of basic building blocks.

## 3 Previous works

Previous works have used Simon's algorithm to break the security of classical constructions in symmetric cryptography: the Even-Mansour construction and the 3-round Feistel scheme. We now explain how these attacks work with our terminology and extend two of the results. First, we show that the attack on the Feistel scheme can be extended to work with random functions, where the original analysis held only for random permutations. Second, using our analysis Simon's algorithm with approximate promise, we make the number of queries required to attack the Even-Mansour construction more precise. These observations have been independently made by Santoli and Schaffner [40]. They use a slightly different approach, which consists in analyzing the run of Simon's algorithm for these specific cases.

### 3.1 Applications to a three-round Feistel scheme

The Feistel scheme is a classical construction to build a random permutation out of random functions or random permutations. In a seminal work, Luby and Rackoff proved that a three-round Feistel scheme is a secure pseudo-random permutation [33].

A three-round Feistel scheme with input $(x_L, x_R)$ and output $(y_L, y_R) = E(x_L, x_R)$ is built from three round functions $R_1, R_2, R_3$ as (see Figure 3):

$$ (u_0, v_0) = (x_L, x_R), \quad (u_i, v_i) = (v_{i-1} \oplus R_i(u_{i-1}), u_{i-1}), \quad (y_L, y_R) = (u_3, v_3). $$

In order to distinguish a Feistel scheme from a random permutation in a quantum setting, Kuwakado and Morii [30] consider the case where the $R_i$ are permutations, and define the following function, with two arbitrary constants $\alpha_0$ and $\alpha_1$ such that $\alpha_0 \neq \alpha_1$:

$$ \begin{gathered} f: \{0,1\} \times \{0,1\}^n \rightarrow \{0,1\}^n \\ b, x \mapsto y_R \oplus \alpha_b, \quad \text{where } (y_R, y_L) = E(\alpha_b, x) \\ f(b, x) = R_2(x \oplus R_1(\alpha_b)) \end{gathered} $$
<figure><img src="image_151.png" /><figcaption>**Fig. 3.** Three-round Feistel scheme.</figcaption></figure>

<figure><img src="image_152.png" /><figcaption>**Fig. 4.** Simon's function for Feistel.</figcaption></figure>

In particular, this $f$ satisfies $f(b, x) = f(b \oplus 1, x \oplus R_1(\alpha_0) \oplus R_1(\alpha_1))$. Moreover,

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

Therefore, the function satisfies Simon's promise with $s = 1 \parallel R_1(\alpha_0) \oplus R_1(\alpha_1)$, and we can recover $R_1(\alpha_0) \oplus R_1(\alpha_1)$ using Simon's algorithm. This gives a distinguisher, because Simon's algorithm applied to a random permutation returns zero with high probability. This can be seen from Theorem 2, using the fact that with overwhelming probability[18], there is no value $t \neq 0$ such that $\Pr_x[f(x \oplus t) = f(x)] > 1/2$ for a random permutation $f$.

We can also verify that the value $R_1(\alpha_0) \oplus R_1(\alpha_1)$ is correct with two additional classical queries $(y_L, y_R) = E(\alpha_0, x)$ and $(y'_L, y'_R) = E(\alpha_1, x \oplus R_1(\alpha_0) \oplus R_1(\alpha_1))$ for a random $x$. If the value is correct, we have $y_R \oplus y'_R = \alpha_0 \oplus \alpha_1$.

Note that in their attack, Kuwakado and Morii implicitly assume that the adversary can query in superposition an oracle that returns solely the left part $y_L$ of the encryption. If the adversary only has access to the complete encryption oracle $E$, then a query in superposition would return two entangled registers containing the left and right parts, respectively. In principle, Simon's algorithm requires the register containing the input value to be completely disentangled from the others.

**Feistel scheme with random functions.** Kuwakado and Morii [30] analyze only the case where the round functions $R_i$ are permutations. We now extend this analysis to random functions $R_i$. The function $f$ defined above still satisfies $f(b, x) = f(b \oplus 1, x \oplus R_1(\alpha_0) \oplus R_1(\alpha_1))$, but it doesn't satisfy the exact promise of Simon's algorithm: there are additional collisions in $f$, between inputs with random differences. However, the previous distinguisher is still valid: at the end of Simon's algorithm, there exist at least one non-zero value orthogonal to all
the values y measured at each step: s. This would not be the case with a random permutation.

Moreover, we can show that $\varepsilon(f, 1 \| s) < 1/2$ with overwhelming probability, so that Simon's algorithm still recovers $1 \| s$ following Theorem 1. If $\varepsilon(f, 1 \| s) > 1/2$, there exists $(\tau, t)$ with $(\tau, t) \notin \{(0, 0), (1, s)\}$ such that: $\Pr[f(b, x) = f(b \oplus \tau, x \oplus t)] > 1/2$. Assume first that $\tau = 0$, this implies:

$$ \Pr[f(0, x) = f(0, x \oplus t)] > 1/2 \quad \text{or} \quad \Pr[f(1, x) = f(1, x \oplus t)] > 1/2. $$

Therefore, for some $b$, $\Pr[R_2(x \oplus R_1(\alpha_b)) = R_2(x \oplus t \oplus R_1(\alpha_b))] > 1/2$, i.e. $\Pr[R_2(x) = R_2(x \oplus t)] > 1/2$. Similarly, if $\tau = 1$, $\Pr[R_2(x \oplus R_1(\alpha_0)) = R_2(x \oplus t \oplus R_1(\alpha_1))] > 1/2$, i.e. $\Pr[R_2(x) = R_2(x \oplus t \oplus R_1(\alpha_0) \oplus R_1(\alpha_1))] > 1/2$.

To summarize, if $\varepsilon(f, 1 \| s) > 1/2$, there exists $u \neq 0$ such that $\Pr[R_2(x) = R_2(x \oplus u)] > 1/2$. This only happens with negligible probability for a random choice of $R_2$ as shown in [18].

## 3.2 Application to the Even-Mansour construction

The Even-Mansour construction is a simple construction to build a block cipher from a public permutation [21]. For some permutation $P$, the cipher is:

$$ E_{k_1,k_2}(x) = P(x \oplus k_1) \oplus k_2. $$

Even and Mansour have shown that this construction is secure in the random permutation model, up to $2^{n/2}$ queries, where $n$ is the size of the input to $P$.

<figure><img src="image_153.png" /><figcaption>Fig. 5. Even-Mansour scheme.</figcaption></figure>

<figure><img src="image_154.png" /><figcaption>Fig. 6. Simon's function for Even-Mansour.</figcaption></figure>

However, Kuwakado and Morii [31] have shown that the security of this construction collapses if an adversary can query an encryption oracle with a superposition of states. More precisely, they define the following function:

$$ f: \{0, 1\}^n \rightarrow \{0, 1\}^n \\ x \mapsto E_{k_1, k_2}(x) \oplus P(x) = P(x \oplus k_1) \oplus P(x) \oplus k_2. $$
In particular, $f$ satisfies $f(x \oplus k_1) = f(x)$ (interestingly, the slide with a twist attack of Biryukov and Wagner[8] uses the same property). However, there are additional collisions in $f$ between inputs with random differences. As in the attack against the Feistel scheme with random round functions, we use Theorem 1, to show that Simon's algorithm recovers $k_1^5$.

We show that $\varepsilon(f, k_1) < 1/2$ with overwhelming probability for a random permutation $P$, and if $\varepsilon(f, k_1) > 1/2$, then there exists a classical attack against the Even-Mansour scheme. Assume that $\varepsilon(f, k_1) > 1/2$, that is, there exists $t$ with $t \notin \{0, k_1\}$ such that $\Pr[f(x) = f(x \oplus t)] > 1/2$, i.e.,

$$p = \Pr[P(x) \oplus P(x \oplus k_1) \oplus P(x \oplus t) \oplus P(x \oplus t \oplus k_1) = 0] > 1/2.$$

This correspond to higher order differential for $P$ with probability $1/2$, which only happens with negligible probability for a random choice of $P$. In addition, this would imply the existence of a simple classical attack against the scheme:

1. Query $y = E_{k_1,k_2}(x)$ and $y' = E_{k_1,k_2}(x \oplus t)$

2. Then $y \oplus y' = P(x) \oplus P(x \oplus t)$ with probability at least one half

Therefore, for any instantiation of the Even-Mansour scheme with a fixed $P$, either there exist a classical distinguishing attack (this only happens with negligible probability with a random $P$), or Simon's algorithm successfully recovers $k_1$. In the second case, the value of $k_2$ can then be recovered from an additional classical query: $k_2 = E(x) \oplus P(x \oplus k_1)$.

In the next sections, we give new applications of Simon's algorithm, to break various symmetric cryptography schemes.

# 4 Application to the LRW construction

We now show a new application of Simon's algorithm to the LRW construction. The LRW construction, introduced by Liskov, Rivest and Wagner [32], turns a block cipher into a tweakable block cipher, i.e. a family of unrelated block ciphers. The tweakable block cipher is a very useful primitive to build modes for encryption, authentication, or authenticated encryption. In particular, tweakable block ciphers and the LRW construction were inspired by the first version of OCB, and later versions of OCB use the tweakable block ciphers formalism. The LRW construction uses a (almost) universal hash function $h$ (which is part of the key), and is defined as (see also Figure 7):

$$\tilde{E}_{t,k}(x) = E_k(x \oplus h(t)) \oplus h(t).$$

We now show that the LRW construction is not secure in a quantum setting. We fix two arbitrary tweaks $t_0, t_1$, with $t_0 \neq t_1$, and we define the following

<footnote n="5">⁵ Note that Kuwakado and Morii just assume that each step of Simon's algorithm gives a random vector orthogonal to $k_1$. Our analysis is more formal and captures the conditions on $P$ required for the algorithm to be successful.</footnote>
<figure><img src="image_155.png" /><figcaption>7.1. LRW construction.</figcaption></figure>

<caption>7.2. XEX construction.</caption>

<caption>7.3. XE construction.</caption>

<caption>**Fig. 7.** The LRW construction, and efficient instantiations XEX (CCA secure) and XE (only CPA secure).</caption>

function:

$$ 
\begin{array}{l}
f : \{0,1\}^n \rightarrow \{0,1\}^n \\
x \mapsto \tilde{E}_{t_{0,k}}(x) \oplus \tilde{E}_{t_{1,k}}(x) \\
f(x) = E_k(x \oplus h(t_0)) \oplus h(t_0) \oplus E_k(x \oplus h(t_1)) \oplus h(t_1).
\end{array}
$$

Given a superposition access to an oracle for an LRW tweakable block cipher, we can build a circuit implementing this function, using the construction given in Figure 8. In the circuit, the cryptographic oracle $\tilde{E}_{t,k}$ takes two inputs: the block $x$ to be encrypted and the tweak $t$. Since the tweak comes out of $\tilde{E}_{t,k}$ unentangled with the other register, we do not represent this output in the diagram. In practice, the output is forgotten by the attacker.

It is easy to see that this function satisfies $f(x) = f(x \oplus s)$ with $s = h(t_0) \oplus h(t_1)$. Furthermore, the quantity $\varepsilon(f, s) = \max_{t \in \{0,1\}^n \setminus \{0,s\}} \Pr[f(x) = f(x \oplus t)]$ is bounded with overwhelming probability, assuming that $E_k$ behaves as a random permutation. Indeed if $\varepsilon(f, s) > 1/2$, there exists some $t$ with $t \notin \{0, s\}$ such that $\Pr[f(x) = f(x \oplus t)] > 1/2$, i.e.,

$$ \Pr[E_k(x) \oplus E_k(x \oplus s) \oplus E_k(x \oplus t) \oplus E_k(x \oplus t \oplus s) = 0] > 1/2 $$

This correspond to higher order differential for $E_k$ with probability $1/2$, which only happens with negligible probability for a random permutation. Therefore, if $E$ is a pseudo-random permutation family, $\varepsilon(f, s) \le 1/2$ with overwhelming probability, and running Simon's algorithm with the function $f$ returns $h(t_0) \oplus h(t_1)$. The assumption that $E$ behaves as a PRP family is required for the security proof of LRW, so it is reasonable to make the same assumption in an attack. More concretely, a block cipher with a higher order differential with probability $1/2$ as seen above would probably be broken by classical attacks. The attack is not immediate because the differential can depend on the key, but it would seem to
indicate a structural weakness. In the following sections, some attacks can also be mounted using Theorem 2 without any assumptions on $E$.

In any case, there exist at least one non-zero value orthogonal to all the values $y$ measured during Simon's algorithm: $s$. This would not be the case if $f$ is a random function, which gives a distinguisher between the LRW construction and an ideal tweakable block cipher with $O(n)$ quantum queries to $\tilde{E}$.

In practice, most instantiations of LRW use a finite field multiplication to define the universal hash function $h$, with a secret offset $L$ (usually computed as $L = E_k(0)$). Two popular constructions are:

- $h(t) = \gamma(t) \cdot L$, used in OCB1 [39], OCB3 [29] and PMAC [10], with a Gray encoding $\gamma$ of $t$,

- $h(t) = 2^t \cdot L$, the XEX construction, used in OCB2 [38].

In both cases, we can recover $L$ from the value $h(t_0) \oplus h(t_1)$ given by the attack.

This attack is important, because many recent modes of operation are inspired by the LRW construction, and the XE and XEX instantiations, such as CAESAR candidates AEZ [24], COPA [4], OCB [29], OTR [36], Minalpher [41], OMD [17], and POET [1]. We will see in the next section that variants of this attack can be applied to each of these modes.

<figure><img src="image_156.png" /><figcaption>**Fig. 8.** Simon's function for LRW.</figcaption></figure>

# 5 Application to block cipher modes of operations

We now give new applications of Simon's algorithm to the security of block cipher modes of operations. In particular, we show how to break the most popular and widely used block-cipher based MACs, and message authentication schemes: CBC-MAC (including variants such as XCBC [9], OMAC [25], and CMAC [20]), GMAC [35], PMAC [10], GCM [35] and OCB [29]. We also show attacks against several CAESAR candidates. In each case, the mode is proven secure up to $2^{n/2}$ in the classical setting, but we show how, by a reduction to Simon's problem, forgery attacks can be performed with superposition queries at a cost of $O(n)$.

**Notations and preliminaries.** We consider a block cipher $E_k$, acting on blocks of length $n$, where the subscript $k$ denotes the key. For simplicity, we
only describe the modes with full-block messages, the attacks can trivially be extended to the more general modes with arbitrary inputs. In general, we consider a message $M$ divided into $\ell$ n-bits block: $M = m_1 \parallel \dots \parallel m_\ell$. We also assume that the MAC is not truncated, i.e. the output size is $n$ bits. In most cases, the attacks can be adapted to truncated MACS.

## 5.1 Deterministic MACs: CBC-MAC and PMAC

We start with deterministic Message Authentication Codes, or MACs. A MAC is used to guarantee the authenticity of messages, and should be immune against forgery attacks. The standard security model is that it should be hard to forge a message with a valid tag, even given access to an oracle that computes the MAC of any chosen message (of course the forged message must not have been queried to the oracle).

To translate this security notion to the quantum setting, we assume that the adversary is given an oracle that takes a quantum superposition of messages as input, and computes the superposition of the corresponding MAC.

**CBC-MAC.** CBC-MAC is one of the first MAC constructions, inspired by the CBC encryption mode. 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 Encrypted-CBC-MAC variant [5], using two keys $k$ and $k'$, but the attack can be easily adapted to other variants [9,25,20]. On a message $M = m_1 \parallel \dots \parallel m_\ell$, CBC-MAC is defined as (see Figure 9):

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

<figure><img src="image_157.png" /><figcaption>Fig. 9. Encrypt-last-block CBC-MAC.</figcaption></figure>

CBC-MAC is standardized and widely used. It has been proved to be secure up to the birthday bound [5], assuming that the block cipher is indistinguishable from a random permutation.

**Attack.** We can build 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 \rightarrow \{0,1\}^n \\ b, x \mapsto \text{CBC-MAC}(\alpha_b \parallel 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 \parallel E_k(\alpha_0) \oplus E_k(\alpha_1)$:

$$ 
\begin{aligned}
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{aligned}
$$

More precisely:

$$ 
\begin{aligned}
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{aligned}
$$

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 \parallel m_1$ for an arbitrary block $m_1$;

2. The same tag is valid for $\alpha_1 \parallel 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 of quantum queries made to learn $E_k(\alpha_0) \oplus E_k(\alpha_1)$. The attacker will 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.

After some exchange at early stages of the work, an extension of this forgery attack has been found by Santoli and Schaffner [40]. Its main advantage is to handle oracles that accept input of fixed length, while our attack works for oracles accepting messages of variable length.

**PMAC.** PMAC is a parallelizable block-cipher based MAC designed by Rog- way [38]. PMAC is based on the XE construction: the construction uses secret offsets $\Delta_i$ derived from the secret key to turn the block cipher into a tweakable block cipher. More precisely, the PMAC algorithm is defined as

$$ c_i = E_k(m_i \oplus \Delta_i) \qquad \text{PMAC}(M) = E_k^*(m_\ell \oplus \sum c_i) $$

where $E^*$ is a tweaked variant of $E$. We omit the generation of the secret offsets because they are irrelevant to our attack.

**First attack.** When PMAC is used with two-block messages, it has the same structure as CBC-MAC: PMAC($m_1 \parallel m_2$) = $E_k^*(m_2 \oplus E_k(m_1 \oplus \Delta_0))$. Therefore we can use the attack of the previous section to recover $E_k(\alpha_0) \oplus E_k(\alpha_1)$ for arbitrary values of $\alpha_0$ and $\alpha_1$. Again, this leads to a simple forgery attack. First, query the tag of $\alpha_0 \parallel m_1 \parallel m_2$ for arbitrary blocks $m_1, m_2$. The same tag is
valid for $\alpha_1 \parallel m_1 \parallel m_2 \oplus E_k(\alpha_0) \oplus E_k(\alpha_1)$. As for CBC-MAC, these two steps can be repeated $t+1$ times, where $t$ is the number of quantum queries issued. The adversary then produces $2(t+1)$ messages after only $2t+1$ queries to the cryptographic oracle.

**Second attack.** We can also build another forgery attack on PMAC where we recover the difference between two offsets $\Delta_i$, following the attack against LRW given in Section 4. More precisely, we use the following function:

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

In particular, it satisfies $f(m \oplus s) = f(m)$ with $s = \Delta_0 \oplus \Delta_1$. Furthermore, we can show that $\varepsilon(f, s) \le 1/2$ when E is a good block cipher$^6$, and we can apply Simon's algorithm to recover $\Delta_0 \oplus \Delta_1$. This allows to create forgeries as follows:

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

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

As mentioned in Section 4, the offsets in PMAC are defined as $\Delta_i = \gamma(i) \cdot L$, with $L = E_k(0)$ and $\gamma$ a Gray encoding. This allows to recover $L$ from $\Delta_0 \oplus \Delta_1$, as $L = (\Delta_0 \oplus \Delta_1) \cdot (\gamma(0) \oplus \gamma(1))^{-1}$. Then we can compute all the values $\Delta_i$, and forge arbitrary messages.

We can also mount an attack without any assumption on $\varepsilon(f, s)$, using Theorem 2. Indeed, with a proper choice of parameters, Simon's algorithm will return a value $t \ne 0$ that satisfies $\text{Pr}_x[f(x \oplus t) = f(x)] \ge 1/2$. This value is not necessarily equal to $s$, but it can also be used to create forgeries in the same way, with success probability at least $1/2$.

<figure><img src="image_158.png" /><figcaption>**Fig. 10.** Simon's function for CBC-MAC.</figcaption></figure>

<figure><img src="image_159.png" /><figcaption>**Fig. 11.** Simon's function for the second attack against PMAC.</figcaption></figure>

<footnote>$^6$ Since this attack is just a special case of the LRW attack of Section 4, we don't repeat the detailed proof.</footnote>
## 5.2 Randomized MAC: GMAC

GMAC is the underlying MAC of the widely used GCM standard, designed by McGrew and Viega [35], and standardized by NIST. GMAC follows the Carter-Wegman construction [16]: 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:

$$GMAC(N, M) = \text{GHASH}(M \parallel \text{len}(M)) \oplus E_k(N||1)$$

$$\text{GHASH}(M) = \sum_{i=1}^{\text{len}(M)} m_i \cdot H^{\text{len}(M)-i+1} \quad \text{with } H = E_k(0),$$

where $\text{len}(M)$ is the length of $M$.

<figure><img src="image_160.png" /><figcaption>Fig. 12. GMAC</figcaption></figure>

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

$$f_N : \{0,1\} \times \{0,1\}^n \rightarrow \{0,1\}^n$$

$$b, x \mapsto \text{GMAC}(N, \alpha_b \parallel x) = \alpha_b \cdot H^2 \oplus x \cdot H \oplus E_k(N||1).$$

In particular, we have:

$$f(b', x') = f(b, x) \Leftrightarrow \alpha_b \cdot H^2 \oplus x \cdot H = \alpha_{b'} \cdot H^2 \oplus x' \cdot H$$

$$\Leftrightarrow \begin{cases} x' \oplus x = 0 & \text{if } b' = b \\ x' \oplus x = (\alpha_0 \oplus \alpha_1) \cdot H & \text{if } b' \neq b \end{cases}$$

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

**Role of the nonce.** There is an important caveat regarding the use of the nonce. In a classical setting, the nonce is chosen by the adversary under the constraint that it is non-repeating, i.e. the oracle computes $N, M \mapsto \text{GMAC}(N, M)$. However, in the quantum setting, we don't have a clear definition of non-repeating
if the nonce can be in superposition. To sidestep the issue, we use a weaker
security notion where the nonce is chosen at random by the oracle, rather than
by the adversary (following the IND-qCPA definition of [13]). The oracle is then
$M \mapsto (r, \text{GMAC}(r, M))$. If we can break the scheme in this model, the attack
will also be valid with any reasonable CPA security definition.

In this setting we can access the function $f_N$ only for a random value of $N$. In
particular, we cannot apply Simon's algorithm as is, because this requires $O(n)$
queries to the same function $f_N$. 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$. Therefore, we can recover $(\alpha_0 \oplus \alpha_1) \cdot H$ after $O(n)$
steps, even if each step uses a different value of $N$. Then, we can recover $H$ easily,
and it is easy to generate forgeries when $H$ is known:

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

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

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

## 5.3 Classical Authenticated Encryption Schemes: GCM and OCB

We now give applications of Simon's algorithm to break the security of stan-
dardized authenticated encryption modes. The attacks are similar to the attacks
against authentication modes, but these authenticated encryption modes are
nonce-based. Therefore we have to pay special attention to the nonce, as in
the attack against GMAC. In the following, we assume that the nonce is ran-
domly chosen by the MAC oracle, in order to avoid issues with the definition of
non-repeating nonce in a quantum setting.

**Extending MAC attacks to authenticated encryption schemes.** We first present a generic way to apply MAC attacks in the context of an authenticated encryption scheme. More precisely, we assume that the tag of the authenticated encryption scheme is computed as $f(g(A), h(M, N))$, i.e. the authentication of the associated data $A$ is independent of the nonce $N$. This is the case in many practical schemes (e.g. GCM, OCB) for efficiency reasons.

In this setting, we can use a technique similar to our attack against GMAC: we define a function $M \mapsto f_N(M)$ for a fixed nonce $N$, such that for any nonce $N$, $f_N(M) = f_N(M \oplus \Delta)$ for some secret value $\Delta$. Next we use Simon's algorithm to recover $\Delta$, where each step of Simon's algorithm is run with a random nonce, and returns a vector orthogonal to $\Delta$. Finally, we can recover $\Delta$, and if $f_N$ was carefully built, the knowledge of $\Delta$ is sufficient for a forgery attack.

The CCM mode is a notable exception, where all the computations depend on
the nonce. In particular, there is no obvious way to apply our attacks to CCM.

**Extending GMAC attack to GCM.** GCM is one of the most widely used authenticated encryption modes, designed by McGrew and Viega [35]. GMAC is the composition of the counter mode for encryption with GMAC (computed over the associated data and the ciphertext) for authentication.
In particular, when the message is empty, GCM is just GMAC, and we can use the attack of the previous section to recover the hash key $H$. This immediately allows a forgery attack.

**OCB.** OCB is another popular authenticated encryption mode, with a very high efficiency, designed by Rogaway et al. [39,38,29]. Indeed, OCB requires only $\ell$ block cipher calls to process an $\ell$-block message, while GCM requires $\ell$ block cipher calls, and $\ell$ finite field operations. OCB is build from the LRW construction discussed in Section 4. OCB takes as input a nonce $N$, a message $M = m_1 \parallel \dots \parallel m_\ell$, and associated data $A = a_1 \parallel \dots a_@$, and returns a ciphertext $C = c_1 \parallel \dots \parallel c_\ell$ and a tag $\tau$:

$$c_i = E_k(m_i \oplus \Delta_i^N) \oplus \Delta_i^N, \quad \tau = E_k(\Delta'_\ell \oplus \sum m_i) \oplus \sum b_i, \quad b_i = E_k(a_i \oplus \Delta_i).$$

**Extending PMAC attack to OCB.** In particular, when the message is empty, OCB reduces to a randomized variant of PMAC:

$$\text{OCB}_k(N, \varepsilon, A) = \phi_k(N) \oplus \sum b_i, \quad b_i = E_k(a_i \oplus \Delta_i).$$

Note that the $\Delta_i$ values used for the associated data are independent of the nonce $N$. Therefore, we can apply the second PMAC attack previously given, using the following function:

$$f_N : \{0,1\}^n \rightarrow \{0,1\}^n \\ x \mapsto \text{OCB}_k(N, \varepsilon, x \parallel x) \\ f_N(x) = E_k(x \oplus \Delta_0) \oplus E_k(x \oplus \Delta_1) \oplus \phi_k(N)$$

Again, this is a special case of the LRW attack of Section 4. The family of functions satisfies $f_N(a \oplus \Delta_0 \oplus \Delta_1) = f_N(a)$, for any $N$, and $\varepsilon(f_N, \Delta_0 \oplus \Delta_1) \le 1/2$ with overwhelming probability if $E$ is a PRP. Therefore we can use the variant of Simon's algorithm to recover $\Delta_0 \oplus \Delta_1$. Two messages with valid tags can then be generated by a single classical queries:

1. Query the authenticated encryption $C, \tau$ of $M, a \parallel a$ for an arbitrary message $M$, and an arbitrary block $a$ (under a random nonce $N$).

2. $C, \tau$ is also a valid authenticated encryption of $M, a \oplus \Delta_0 \oplus \Delta_1 \parallel a \oplus \Delta_0 \oplus \Delta_1$, with the same nonce $N$.

Repeating these steps lead again to an existential forgery attack.

**Alternative attack against OCB.** For some versions of OCB, we can also mount a different attack targeting the encryption part rather than the authentication part. The goal of this attack is also to recover the secret offsets, but we target the $\Delta_i^N$ used for the encryption of the message. More precisely, we use the following function:

$$f_i : \{0,1\}^n \rightarrow \{0,1\}^n \\ m \mapsto c_1 \oplus c_2, \text{ where } (c_1, c_2, \tau) = \text{OCB}_k(N, m \parallel m, \varepsilon) \\ f_i(m) = E_k(m \oplus \Delta_1^N) \oplus \Delta_1^N \oplus E_k(m \oplus \Delta_2^N) \oplus \Delta_2^N$$
This function satisfies $f_N(m \oplus \Delta_1^N \oplus \Delta_2^N) = f_N(m)$ and $\varepsilon(f_N, \Delta_0^N \oplus \Delta_1^N) \le 1/2$, with the same arguments as previously. Moreover, in OCB1 and OCB3, the offsets are derived as $\Delta_i^N = \Phi_k(N) \oplus \gamma(i) \cdot E_k(0)$ for some function $\Phi$ (based on the block cipher $E_k$). In particular, $\Delta_1^N \oplus \Delta_2^N$ is independent of $N$:

$$ \Delta_1^N \oplus \Delta_2^N = (\gamma(1) \oplus \gamma(2)) \cdot E_k(0). $$

Therefore, we can apply Simon's algorithm to recover $\Delta_1^N \oplus \Delta_2^N$. Again, this leads to a forgery attack, by repeating the following two steps:

1. Query the authenticated encryption $c_1 \parallel c_2, \tau$ of $m \parallel m, A$ for an arbitrary block $m$, and arbitrary associated data $A$ (under a random nonce $N$).

2. $c_2 \oplus \Delta_0^N \oplus \Delta_1^N \parallel c_1 \oplus \Delta_0^N \oplus \Delta_1^N, \tau$ is also a valid authenticated encryption of $m \oplus \Delta_0^N \oplus \Delta_1^N \parallel m \oplus \Delta_0^N \oplus \Delta_1^N, A$ with the same nonce $N$.

The forgery is valid because we swap the inputs of the first and second block ciphers. In addition, we have $\sum m_i = \sum m'_i$, so that the tag is still valid.

## 5.4 New Authenticated Encryption Schemes: CAESAR Candidates

In this section, we consider recent proposals for authenticated encryption, submitted to the ongoing CAESAR competition. Secret key cryptography has a long tradition of competitions: AES and SHA-3 for example, were chosen after the NIST competitions organized in 1997 and 2007, respectively. The CAESAR competition<fnref n="7" /> aims at stimulating research on authenticated encryption schemes, and to define a portfolio of new authenticated encryption schemes. The competition is currently in the second round, with 29 remaining algorithms.

First, we point out that the attacks of the previous sections can be used to break several CAESAR candidates:

- CLOC [26] uses CBC-MAC to authenticate the message, and the associated data is processed independently of the nonce. Therefore, the CBC-MAC attack can be extended to CLOC<fnref n="8" />.

- AEZ [24], COPA [4], OTR [36] and POET [1] use a variant of PMAC to authenticate the associated data. In both cases, the nonce is not used to process the associated data, so that we can extend the PMAC attack as we did against OCB<fnref n="9" />.

- The authentication of associated data in OMD [17] and Minalpher [41] are also variants of PMAC (with a PRF that is not block cipher), and the attack can be applied.

In the next section, we show how to adapt the PMAC attack to Minalpher and OMD, since the primitives are different.

<footnote n="7">⁷ http://competitions.cr.yp.to/</footnote>

<footnote n="8">⁸ This is not the case for the related mode SILC, because the nonce is processed before the data in CBC-MAC.</footnote>

<footnote n="9">⁹ Note that AEZ, COPA and POET also claim security when the nonce is misused, but our attacks are nonce-respecting.</footnote>
**Minalpher.** Minalpher [41] is a permutation-based CAESAR candidate, where the permutation is used to build a tweakable block-cipher using the tweakable Even-Mansour construction. When the message is empty (or fixed), the authentication part of Minalpher is very similar to PMAC. With associated data $A = a_1 \parallel \dots \parallel a_@$, the tag is computed as:

$$ 
\begin{aligned}
b_i &= P(a_i \oplus \Delta_i) \oplus \Delta_i & \tau &= \phi_k \left( N, M, a_@ \oplus \sum_{i=1}^{@-1} b_i \right) \\
\Delta_i &= y^i \cdot L' & L' &= P(k \parallel 0) \oplus (k \parallel 0)
\end{aligned}
$$

where $\phi_k$ is a permutation (we omit the description of $\phi_k$ because it is irrelevant for our attack). Since the tag is a function of $a_@ \oplus \sum_{i=1}^{@-1} b_i$, we can use the same attacks as against PMAC. For instance, we define the following function:

$$ 
\begin{aligned}
f_N : \{0,1\} \times \{0,1\}^n &\rightarrow \{0,1\}^n \\
b, x &\mapsto \text{Minalpher}(N, \varepsilon, \alpha_b \parallel x) = \phi_k(N, \varepsilon, P(\alpha_b \oplus \Delta_1) \oplus \Delta_1 \oplus x).
\end{aligned}
$$

In particular, we have:

$$ 
\begin{aligned}
f_N(b', x') &= f_N(b, x) \Leftrightarrow P(\alpha_{b'} \oplus \Delta_1) \oplus x' = P(\alpha_b \oplus \Delta_1) \oplus x \\
&\Leftrightarrow \begin{cases} x' \oplus x = 0 & \text{if } b' = b \\ x' \oplus x = P(\alpha_0 \oplus \Delta_1) \oplus P(\alpha_1 \oplus \Delta_1) & \text{if } b' \neq b \end{cases}
\end{aligned}
$$

Since $s = P(\alpha_0 \oplus \Delta_1) \oplus P(\alpha_1 \oplus \Delta_1)$ is independent of $N$, we can easily apply Simon's algorithm to recover $s$, and generate forgeries.

**OMD.** OMD [17] is a compression-function-based CAESAR candidate. The internal primitive is a keyed compression function denoted $F_k$. Again, when the message is empty the authentication is very similar to PMAC. With associated data $A = a_1 \parallel \dots \parallel a_@$, the tag is computed as:

$$ b_i = F_k(a_i \oplus \Delta_i) \qquad \tau = \phi_k(N, M) \oplus \sum b_i $$

We note that the $\Delta_i$ used for the associated data do not depend on the nonce. Therefore we can use the second PMAC attack with the following function:

$$ 
\begin{aligned}
f_N : \{0,1\}^n &\rightarrow \{0,1\}^n \\
x &\mapsto \text{OMD}(N, \varepsilon, x \parallel x) \\
f_N(x) &= \phi_k(N, \varepsilon) \oplus F_k(x \oplus \Delta_1) \oplus F_k(x \oplus \Delta_2)
\end{aligned}
$$

This is the same form as seen when extending the PMAC attack to OCB, therefore we can apply the same attack to recover $s = \Delta_1 \oplus \Delta_2$ and generate forgeries.

## 6 Simon's algorithm applied to slide attacks

In this section we show how Simon's algorithm can be applied to a cryptanalysis family: slide attacks. In this case, the complexity of the attack drops again
exponentially, from $O(2^{n/2})$ to $O(n)$ and therefore becomes much more dangerous. To the best of our knowledge this is the first symmetric cryptanalytic technique that has an exponential speed-up in the post-quantum world.

**The principle of slide attacks** In 1999, Wagner and Biryukov introduced the technique called slide attack [7]. It can be applied to block ciphers made of $r$ applications of an identical round function $R$, each one parametrized by the same key $K$. The attack works independently of the number of rounds, $r$. Intuitively, for the attack to work, $R$ has to be vulnerable to known plaintext attacks.

The attacker collects $2^{n/2}$ encryptions of plaintexts. Amongst these couples of plaintext-ciphertext, with large probability, he gets a “slid” pair, that is, a pair of couples $(P_0, C_0)$ and $(P_1, C_1)$ such that $R(P_0) = P_1$. This immediately implies that $R(C_0) = C_1$. For the attack to work, the function $R$ needs to allow for an efficient recognition of such pairs, which in turns makes the key extraction from $R$ easy. A trivial application of this attack is the key-alternate cipher with blocks of $n$ bits, identical subkeys and no round constants. The complexity is then approximately $2^{n/2}$. The speed-up over exhaustive search given by this attack is then quadratic, similar to the quantum attack based on Grover's algorithm.

This attack is successful, for example, to break the TREYFER block cipher [46], with a data complexity of $2^{32}$ and a time complexity of $2^{32+12} = 2^{44}$ (where $2^{12}$ is the cost of identifying the slid pair by performing some key guesses). Comparatively, the cost for an exhaustive search of the key is $2^{64}$.

**Exponential quantum speed-up of slide attacks** We consider the attack represented in Figure 13. The unkeyed round function is denoted $P$ and the whole encryption function $E_k$.

<figure><img src="image_161.png" /><figcaption>Fig. 13. Representation of a slid-pair used in a slide attack.</figcaption></figure>

We define the following function:

$$f: \{0,1\} \times \{0,1\}^n \rightarrow \{0,1\}^n \\ b, x \mapsto \begin{cases} P(E_k(x)) \oplus x & \text{if } b=0, \\ E_k(P(x)) \oplus x & \text{if } b=1. \end{cases}$$
The slide property shows that all $x$ satisfy $P(E_k(x)) \oplus k = E_k(P(x \oplus k))$. This implies that $f$ satisfies the promise of Simon's problem with $s = 1 \parallel k$:

$$f(0, x) = P(E_k(x)) \oplus x = E_k(P(x \oplus k)) \oplus k \oplus x = f(1, x \oplus k).$$

In order to apply Theorem 1, we bound $\varepsilon(f, 1 \parallel k)$, assuming that both $E_k \circ P$ and $P \circ E_k$ are indistinguishable from random permutations. If $\varepsilon(f, 1 \parallel k) > 1/2$, there exists $(\tau, t)$ with $(\tau, t) \notin \{(0, 0), (1, k)\}$ such that: $\Pr[f(b, x) = f(b \oplus \tau, x \oplus t)] > 1/2$. Let us assume $\tau = 0$. This implies

$$\Pr[f(0, x) = f(0, x \oplus t)] > 1/2 \quad \text{or} \quad \Pr[f(1, x) = f(1, x \oplus t)] > 1/2,$$

which is equivalent to

$$\Pr[P(E_k(x)) = P(E_k(x \oplus t)) \oplus t] > 1/2 \quad \text{or} \quad \Pr[E_k(P(x)) = E_k(P(x \oplus t)) \oplus t] > 1/2.$$

In particular, there is a differential in $P \circ E_k$ or $E_k \circ P$ with probability $1/2$. Otherwise, $\tau = 1$. This implies

$$\Pr[P(E_k(x)) \oplus x = E_k(P(x \oplus t)) \oplus x \oplus t] > 1/2 \\ \text{i.e.} \quad \Pr[E_k(P(x \oplus k)) \oplus k = E_k(P(x \oplus t)) \oplus t] > 1/2.$$

Again, it means there is a differential in $E_k \circ P$ with probability $1/2$.

Finally we conclude that $\varepsilon(f, 1 \parallel k) \le 1/2$, unless $E_k \circ P$ or $P \circ E_k$ have differentials with probability $1/2$. If $E_k$ behave as a random permutation, $E_k \circ P$ and $P \circ E_k$ also behave as random permutations, and these differential are only found with negligible probability. Therefore, we can apply Simon's algorithm, following Theorem 1, and recover $k$.

<figure><img src="image_162.png" /><figcaption>Fig. 14. Simon's function for slide attacks. The $X$ gate is the quantum equivalent of the NOT gate that flips the qubit $|0\rangle$ and $|1\rangle$.</figcaption></figure>

# 7 Conclusion

We have been able to show that symmetric cryptography is far from ready for the post quantum world. We have found exponential speed-ups on attacks on
symmetric cryptosystems. In consequence, some cryptosystems that are believed
to be safe in a classical world become vulnerable in a quantum world.

With the speed-up on slide attacks, we provided the first known exponential
quantum speed-up of a classical attack. This attack now becomes very power-
ful. An interesting follow-up would be to seek other such speed-ups of generic
techniques. For authenticated encryption, we have shown that many modes of
operations that are believed to be solid and secure in the classical world, become
completely broken in the post-quantum world. More constructions might be
broken following the same ideas.

Acknowledgements

We would like to thank Thomas Santoli and Christian Schaffner for sharing an
early stage manuscript of their work [40], Michele Mosca for discussions and LTCI
for hospitality. This work was supported by the Commission of the European
Communities through the Horizon 2020 program under project number 645622
PQCRYPTO. MK acknowledges funding through grants ANR-12-PDOC-0022-01
and ESPRC EP/N003829/1.

References

1. Abed, F., Fluhrer, S.R., Forler, C., List, E., Lucks, S., McGrew, D.A., Wenzel, J.: Pipelineable on-line encryption. In: Cid, C., Rechberger, C. (eds.) Fast Software Encryption - 21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8540, pp. 205-223. Springer (2014)

2. Alagic, G., Broadbent, A., Fefferman, B., Gagliardoni, T., Schaffner, C., Jules, M.S.: Computational security of quantum encryption. arXiv preprint arXiv:1602.01441 (2016)

3. Anand, M.V., Targhi, E.E., Tabia, G.N., Unruh, D.: Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation. In: Takagi, T. (ed.) Post-Quantum Cryptography - 7th International Workshop, PQCrypto 2016, Fukuoka, Japan, February 24-26, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9606, pp. 44-63. Springer (2016)

4. Andreeva, E., Bogdanov, A., Luykx, A., Mennink, B., Tischhauser, E., Yasuda, K.: Parallelizable and authenticated online ciphers. In: Sako, K., Sarkar, P. (eds.) Advances in Cryptology - ASIACRYPT 2013 - 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I. Lecture Notes in Computer Science, vol. 8269, pp. 424-443. Springer (2013)

5. Bellare, M., Kilian, J., Rogaway, P.: The security of the cipher block chaining message authentication code. J. Comput. Syst. Sci. 61(3), 362-399 (2000)

6. Bernstein, D.J.: Introduction to post-quantum cryptography. In: Post-quantum cryptography, pp. 1-14. Springer (2009)

7. Biryukov, A., Wagner, D.: Slide attacks. In: Knudsen, L.R. (ed.) Fast Software Encryption, 6th International Workshop, FSE '99, Rome, Italy, March 24-26, 1999, Proceedings. Lecture Notes in Computer Science, vol. 1636, pp. 245-259. Springer (1999)
8. Biryukov, A., Wagner, D.: Advanced slide attacks. In: Preneel, B. (ed.) Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding. Lecture Notes in Computer Science, vol. 1807, pp. 589-606. Springer (2000)

9. Black, J., Rogaway, P.: CBC macs for arbitrary-length messages: The three-key constructions. In: Bellare, M. (ed.) Advances in Cryptology - CRYPTO 2000, 20th Annual International Cryptology Conference, Santa Barbara, California, USA, August 20-24, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1880, pp. 197-215. Springer (2000)

10. Black, J., Rogaway, P.: A block-cipher mode of operation for parallelizable message authentication. In: Knudsen, L.R. (ed.) Advances in Cryptology - EUROCRYPT 2002, International Conference on the Theory and Applications of Cryptographic Techniques, Amsterdam, The Netherlands, April 28 - May 2, 2002, Proceedings. Lecture Notes in Computer Science, vol. 2332, pp. 384-397. Springer (2002)

11. Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., Zhandry, M.: Random oracles in a quantum world. In: Lee, D., Wang, X. (eds.) Advances in Cryptology - ASIACRYPT 2011, Lecture Notes in Computer Science, vol. 7073, pp. 41-69. Springer Berlin Heidelberg (2011)

12. Boneh, D., Zhandry, M.: Quantum-secure message authentication codes. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7881, pp. 592-608. Springer (2013)

13. Boneh, D., Zhandry, M.: Secure signatures and chosen ciphertext security in a quantum computing world. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II. Lecture Notes in Computer Science, vol. 8043, pp. 361-379. Springer (2013)

14. Brassard, G., Høyer, P., Kalach, K., Kaplan, M., Laplante, S., Salvail, L.: Merkle puzzles in a quantum world. In: Advances in Cryptology-CRYPTO 2011, pp. 391-410. Springer (2011)

15. Broadbent, A., Jeffery, S.: Quantum homomorphic encryption for circuits of low T-gate complexity. In: Advances in Cryptology-CRYPTO 2015, pp. 609-629. Springer (2015)

16. Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: Hopcroft, J.E., Friedman, E.P., Harrison, M.A. (eds.) Proceedings of the 9th Annual ACM Symposium on Theory of Computing, May 4-6, 1977, Boulder, Colorado, USA. pp. 106-112. ACM (1977)

17. Cogliani, S., Maimut, D., Naccache, D., do Canto, R.P., Reyhanitabar, R., Vaudenay, S., Vizár, D.: OMD: A compression function mode of operation for authenticated encryption. In: Joux, A., Youssef, A.M. (eds.) Selected Areas in Cryptography - SAC 2014 - 21st International Conference, Montreal, QC, Canada, August 14-15, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8781, pp. 112-128. Springer (2014)

18. Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Mathematical Cryptology 1(3), 221-242 (2007)

19. Damgård, I., Funder, J., Nielsen, J.B., Salvail, L.: Superposition attacks on cryptographic protocols. In: Padró, C. (ed.) Information Theoretic Security - 7th International Conference, ICITS 2013, Singapore, November 28-30, 2013, Proceedings. Lecture Notes in Computer Science, vol. 8317, pp. 142-161. Springer (2013)
20. Dworkin, M.: Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. NIST Special Publication 800-38B, National Institute for Standards and Technology (May 2005)

21. Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. J. Cryptology 10(3), 151–162 (1997)

22. Gagliardoni, T., Hülsing, A., Schaffner, C.: Semantic security and indistinguishability in the quantum world. arXiv preprint arXiv:1504.05255 (2015)

23. Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, Philadelphia, Pennsylvania, USA, May 22-24, 1996. pp. 212–219. ACM (1996)

24. Hoang, V.T., Krovetz, T., Rogaway, P.: Robust authenticated-encryption AEZ and the problem that it solves. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Lecture Notes in Computer Science, vol. 9056, pp. 15–44. Springer (2015)

25. Iwata, T., Kurosawa, K.: OMAC: one-key CBC MAC. In: Johansson, T. (ed.) Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers. Lecture Notes in Computer Science, vol. 2887, pp. 129–153. Springer (2003)

26. Iwata, T., Minematsu, K., Guo, J., Morioka, S.: CLOC: authenticated encryption for short input. In: Cid, C., Rechberger, C. (eds.) Fast Software Encryption - 21st International Workshop, FSE 2014, London, UK, March 3-5, 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8540, pp. 149–167. Springer (2014)

27. Kaplan, M.: Quantum attacks against iterated block ciphers. CoRR abs/1410.1434 (2014)

28. Kaplan, M., Leurent, G., Leverrier, A., Naya-Plasencia, M.: Quantum differential and linear cryptanalysis. CoRR abs/1510.05836 (2015)

29. Krovetz, T., Rogaway, P.: The software performance of authenticated-encryption modes. In: Joux, A. (ed.) Fast Software Encryption - 18th International Workshop, FSE 2011, Lyngby, Denmark, February 13-16, 2011, Revised Selected Papers. Lecture Notes in Computer Science, vol. 6733, pp. 306–327. Springer (2011)

30. Kuwakado, H., Morii, M.: Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on. pp. 2682–2685 (June 2010)

31. Kuwakado, H., Morii, M.: Security on the quantum-type Even-Mansour cipher. In: Information Theory and its Applications (ISITA), 2012 International Symposium on. pp. 312–316 (Oct 2012)

32. Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. J. Cryptology 24(3), 588–613 (2011)

33. Luby, M., Rackoff, C.: How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)

34. Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., Makarov, V.: Hacking commercial quantum cryptography systems by tailored bright illumination. Nature photonics 4(10), 686–689 (2010)

35. McGrew, D.A., Viega, J.: The security and performance of the galois/counter mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) Progress in Cryptology - INDOCRYPT 2004, 5th International Conference on Cryptology in India, Chennai, India, December 20-22, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3348, pp. 343–355. Springer (2004)
36. Minematsu, K.: Parallelizable rate-1 authenticated encryption from pseudorandom functions. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology - EUROCRYPT 2014 - 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014. Proceedings. Lecture Notes in Computer Science, vol. 8441, pp. 275-292. Springer (2014)

37. Montanaro, A., de Wolf, R.: A survey of quantum property testing. arXiv preprint arXiv:1310.2035 (2013)

38. Rogaway, P.: Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC. In: Lee, P.J. (ed.) Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings. Lecture Notes in Computer Science, vol. 3329, pp. 16-31. Springer (2004)

39. Rogaway, P., Bellare, M., Black, J., Krovetz, T.: OCB: a block-cipher mode of operation for efficient authenticated encryption. In: Reiter, M.K., Samarati, P. (eds.) CCS 2001, Proceedings of the 8th ACM Conference on Computer and Communications Security, Philadelphia, Pennsylvania, USA, November 6-8, 2001. pp. 196-205. ACM (2001)

40. Santoli, T., Schaffner, C.: Using simon's algorithm to attack symmetric-key cryptographic primitives. arXiv preprint arXiv:1603.07856 (2016)

41. Sasaki, Y., Todo, Y., Aoki, K., Naito, Y., Sugawara, T., Murakami, Y., Matsui, M., Hirose, S.: Minalpher v1.1. CAESAR submission (August 2015)

42. Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484-1509 (1997)

43. Simon, D.R.: On the power of quantum computation. SIAM journal on computing 26(5), 1474-1483 (1997)

44. Unruh, D.: Non-interactive zero-knowledge proofs in the quantum random oracle model. In: Eurocrypt 2015. vol. 9057, pp. 755-784. Springer (2015), preprint on IACR ePrint 2014/587

45. Xu, F., Qi, B., Lo, H.K.: Experimental demonstration of phase-remapping attack in a practical quantum key distribution system. New Journal of Physics 12(11), 113026 (2010)

46. Yuval, G.: Reinventing the travois: Encryption/mac in 30 ROM bytes. In: Biham, E. (ed.) Fast Software Encryption, 4th International Workshop, FSE '97, Haifa, Israel, January 20-22, 1997, Proceedings. Lecture Notes in Computer Science, vol. 1267, pp. 205-209. Springer (1997)

47. Zhandry, M.: How to construct quantum random functions. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012. pp. 679-687. IEEE Computer Society (2012)

48. Zhandry, M.: Secure identity-based encryption in the quantum random oracle model. International Journal of Quantum Information 13(04), 1550014 (2015)

49. Zhao, Y., Fung, C.H.F., Qi, B., Chen, C., Lo, H.K.: Quantum hacking: Experimental demonstration of time-shift attack against practical quantum-key-distribution systems. Physical Review A 78(4), 042333 (2008)

A Proof of Theorem 1

The proof of Theorem 1 is based on the following lemma.
**Lemma 1.** For $t \in \{0,1\}^n$, consider the function $g(x) := 2^{-n} \sum_{y \in t^{\perp}} (-1)^{x \cdot y}$, where $t^{\perp} = \{y \in \{0,1\}^n \text{ s.t. } y \cdot t = 0\}$. for any $x$, it satisfies

$$g(x) = \frac{1}{2}(\delta_{x,0} + \delta_{x,t}). \qquad (2)$$

*Proof.* If $t = 0$ then $g(x) = \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} = \delta(x,0)$, which proves the claim. From now on, assume that $t \neq 0$. It is straightforward to check that $g(0) = g(t) = \frac{1}{2}$ because all the terms of the sum are equal to 1 and there are $2^{n-1}$ vectors $y$ orthogonal to $t$. Since $\sum_{x \in \{0,1\}^n} g(x) = 1$, it is sufficient to prove that $g(x) \ge 0$ to establish the claim in the case $t \neq 0$. For this, decompose $g(x)$ into two terms:

$$g(x) = \sum_{y \in E_0} (-1)^{x \cdot y} - \sum_{y \in E_1} (-1)^{x \cdot y} = |E_0| - |E_1|,$$

where $E_i := \{y \in \{0,1\}^n \text{ s.t. } y \cdot x = i \text{ and } y \cdot y = 0\}$ for $i = 0, 1$. Simple counting shows that:

$$|E_0| = \begin{cases} 2^{n-1} & \text{if } x = 0, \\ 2^{n-1} & \text{if } x = t, \\ 2^{n-2} & \text{otherwise.} \end{cases}$$

In particular, $|E_0| \ge |E_1|$ which implies that $g(x) \ge 0$.

We are now ready to prove Theorem 1. Each call to the main subroutine of Simon's algorithm will return a vector $u_i$. If cn calls are made, one obtains cn vectors $u_1, \dots, u_{cn}$. By construction, f is such that $f(x) = f(x \oplus s)$ and consequently, the cn vectors $u_1, \dots, u_{cn}$ are all orthogonal to s. The algorithm is successful provided one can recover the value of s unambiguously, which is the case if the cn vectors span the $(n-1)$-dimensional space orthogonal to s. (Let us note that if the space is $(n-d)$-dimensional for some constant d, one can still recover s efficiently by testing all the vectors orthogonal to the subspace.) In other words, the failure probability $p_{\text{fail}}$ is

$$\begin{align*}
p_{\text{fail}} &= \Pr[\dim(\text{Span}(u_1, \dots, u_n)) \le n-2] \\
&\le \Pr[\exists t \in \{0,1\}^n \setminus \{0,s\} \text{ s.t. } u_1 \cdot t = u_2 \cdot t = \dots = u_{cn} \cdot t = 0] \\
&\le \sum_{t \in \{0,1\}^n \setminus \{0,s\}} \Pr[u_1 \cdot t = u_2 \cdot t = \dots = u_{cn} \cdot t = 0] \\
&\le \sum_{t \in \{0,1\}^n \setminus \{0,s\}} (\Pr[u_1 \cdot t = 0])^{cn} \\
&\le \max_{t \in \{0,1\}^n \setminus \{0,s\}} (2\Pr[u_1 \cdot t = 0])^c
\end{align*}$$

where the second inequality results from the union bound and the third inequality follows from the fact that the results of the cn subroutines are independent.

In order to establish the theorem, it is now sufficient to show that $\Pr[u \cdot t = 0]$ is bounded away from 1 for all $t$, where $u$ is the vector corresponding to the
output of Simon's subroutine. We will prove that for all $t \in \{0, 1\}^n \setminus \{0, s\}$, the following inequality holds:

$$ \mathrm{Pr}_u[u \cdot t = 0] = \frac{1}{2}(1 + \mathrm{Pr}_x[f(x) = f(x \oplus t)]) \le \frac{1}{2}(1 + \varepsilon(f, s)) \le \frac{1}{2}(1 + p_0). \quad (3) $$

In Simon's algorithm, one can wait until the last step before measuring both registers. The final state before measurement can be decomposed as:

$$ 2^{-n} \sum_{x \in \{0,1\}^n} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle|f(x)\rangle = 2^{-n} \sum_{\substack{y \in \{0,1\}^n \\ \text{s.t. } y \cdot t = 0}} \sum_{x \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle|f(x)\rangle \\ + 2^{-n} \sum_{\substack{y \in \{0,1\}^n \\ \text{s.t. } y \cdot t = 1}} \sum_{x \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle|f(x)\rangle. $$

The probability of obtaining $u$ such that $u \cdot t = 0$ is given by

$$ \begin{aligned} \mathrm{Pr}_u[u \cdot t = 0] &= \left\| 2^{-n} \sum_{\substack{y \in \{0,1\}^n \\ \text{s.t. } y \cdot t = 0}} |y\rangle \sum_{x \in \{0,1\}^n} (-1)^{x \cdot y} |f(x)\rangle \right\|^2 \\ &= 2^{-2n} \sum_{\substack{y \in \{0,1\}^n \\ \text{s.t. } y \cdot t = 0}} \sum_{x, x' \in \{0,1\}^n} (-1)^{(x \oplus x') \cdot y} \langle f(x')|f(x)\rangle \\ &= 2^{-2n} \sum_{x, x' \in \{0,1\}^n} \langle f(x')|f(x)\rangle \sum_{\substack{y \in \{0,1\}^n \\ \text{s.t. } y \cdot t = 0}} (-1)^{(x \oplus x') \cdot y} \\ &= 2^{-2n} \sum_{x, x' \in \{0,1\}^n} \langle f(x')|f(x)\rangle 2^{n-1}(\delta_{x,x'} + \delta_{x',x \oplus t}) \end{aligned} \quad (4) $$

$$ = 2^{-(n+1)} \left[ \sum_{x \in \{0,1\}^n} \langle f(x)|f(x)\rangle + \sum_{x \in \{0,1\}^n} \langle f(x \oplus t)|f(x)\rangle \right] \quad (5) $$

$$ = \frac{1}{2} [1 + \mathrm{Pr}_x[f(x) = f(x \oplus t)]] \quad (6) $$

where we used Lemma 1 proven in the appendix in Eq. 4, and $\delta_{x,x'} = 1$ if $x = x'$ and 0 otherwise.

## B Proof of Theorem 2

Let $t$ be a fixed value and $p_t = \mathrm{Pr}_x[f(x \oplus t = f(t))]$. Following the previous analysis, the probability that the $cn$ vectors $u_i$ are orthogonal to $t$ can be written as $\mathrm{Pr}[u_1 \cdot t = u_2 \cdot t = \cdots = u_{cn} \cdot t = 0] = \left(\frac{1+p_t}{2}\right)^{cn}$.

In particular, we can bound the probability that Simon's algorithm returns a value $t$ with $p_t < p_0$:

$$ \mathrm{Pr}[p_t < p_0] = \sum_{t: p_t < p_0} \left(\frac{1+p_t}{2}\right)^{cn} \le 2^n \times \left(\frac{1+p_0}{2}\right)^{cn} $$
# Quantum Linearization Attacks

Xavier Bonnetain<fnref n="1" />,<fnref n="2" />, Gaëtan Leurent<fnref n="2" />, María Naya-Plasencia<fnref n="2" />, and André Schrottenloher<fnref n="3" />

**Abstract.** Recent works have shown that quantum period-finding can be used to break many popular constructions (some block ciphers such as Even-Mansour, multiple MACs and AEs...) in the superposition query model. So far, all the constructions broken exhibited a strong algebraic structure, which enables to craft a periodic function of a single input block. Recovering the secret period allows to recover a key, distinguish, break the confidentiality or authenticity of these modes.

In this paper, we introduce the *quantum linearization attack*, a new way of using Simon's algorithm to target MACs in the superposition query model. Specifically, we use inputs of multiple blocks as an interface to a function hiding a linear structure. Recovering this structure allows to perform forgeries.

We also present some variants of this attack that use other quantum algorithms, which are much less common in quantum symmetric crypt-analysis: Deutsch's, Bernstein-Vazirani's, and Shor's. To the best of our knowledge, this is the first time these algorithms have been used in quantum forgery or key-recovery attacks.

Our attack breaks many parallelizable MACs such as LightMac, PMAC, and numerous variants with (classical) beyond-birthday-bound security (LightMAC+, PMAC+) or using tweakable block ciphers (ZMAC). More generally, it shows that constructing parallelizable quantum-secure PRFs might be a challenging task.

**Keywords:** Quantum cryptanalysis, MACs, superposition query model, Deutsch's algorithm, Bernstein-Vazirani algorithm, Simon's algorithm, Shor's algorithm.

# 1 Introduction

The possible emergence of large-scale quantum computing devices in a near future has prompted a wide move towards *post-quantum security*, which takes into account the new security threats that they pose. In particular, the most popular asymmetric cryptosystems currently in use, such as RSA, can be broken

<footnote n="1">¹ Institute for Quantum Computing, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, Canada</footnote>

<footnote n="2">² Inria, Paris, France</footnote>

<footnote n="3">³ Cryptology Group, CWI, Amsterdam, The Netherlands</footnote>
by an adversary capable of successfully implementing Shor's algorithm [59]. An ongoing standardization project led by the NIST [56] has structured the efforts of the (asymmetric) cryptographic community on this question.

As symmetric primitives do not rely on a trapdoor, they seemed for a long time to avoid the cases where quantum computers bring an exponential speedup over the best classical algorithms. In fact, most problems in symmetric cryptography, such as the search for the secret key of a black-box cipher, seem to admit a quadratic speedup at best, given by Grover's quantum search algorithm [29]. Although this speedup is significant, it could be countered by increasing the parameters of symmetric cryptosystems, e.g., doubling the size of secret keys.

However, in the past few years, a series of works have shown the insecurity of some symmetric cryptosystems against quantum adversaries entitled to superposition queries. That is, some primitives become broken if they can be queried inside a quantum algorithm. This started with the 3-round Feistel distinguisher proposed by Kuwakado and Morii [44]. Later, they found a polynomial-time key-recovery attack on the Even-Mansour cipher [45], which was the first quantum key-recovery on a classically secure symmetric construction. These results rely crucially on the fact that many popular designs in symmetric cryptography have a strong algebraic structure, as they are built by combining smaller primitives (such as permutations or block ciphers) using cheap operations such as XORs. Kaplan et al. [39] showed that many other constructions exhibited a structure exploitable by a quantum adversary, and designed the first forgery attacks on MACs (notably CBC-MAC [11], OMAC [35], PMAC [12]) and authenticated encryption schemes (e.g., OCB3 [43], GCM [49]).

In this paper, we will focus on idealized MAC constructions that authenticate messages of arbitrary size using smaller primitives such as permutations, block ciphers or tweakable block ciphers (TBCs) of block size $n$. These constructions have classical proofs of security showing either that the MAC behaves as a pseudo-random function, or that it is unforgeable, up to some exponential bound in $n$. We will exhibit polynomial-time quantum attacks on constructions that were not vulnerable to previous Simon's attacks (like those of [39,58]).

**Previous Attacks.** Although there have been many of them, all the quantum forgery attacks known so far follow the same paradigm. They query the MAC with a constant number of blocks, using usually a single block of message $x$ in superposition. Inside the MAC, this block of message $x$ is XORed to some unknown value $\alpha$ depending on other blocks: thus, the result is $\text{MAC}(x \oplus \alpha)$. Having two different values $\alpha_0, \alpha_1$, we then have access to two functions $f(x) = \text{MAC}(x \oplus \alpha_0)$ and $g(x) = \text{MAC}(x \oplus \alpha_1)$, such that $f(x) = g(x \oplus \alpha_0 \oplus \alpha_1)$. From there, we can use Simon's Boolean hidden shift algorithm [60] as a black box. It recovers $\alpha_0 \oplus \alpha_1$ in quantum polynomial time, whereas any classical algorithm would require exponentially many queries to $f$ and $g$ (thus to the MAC). The recovery of the internal shift $\alpha_0 \oplus \alpha_1$ then enables the adversary to forge new messages, and in some cases to recover secret-key material.

Let us point out the following important remark:
If the message blocks are not directly XORed to internal values (keys, offsets, encryption of other blocks...), then the previous attacks based on Simon's algorithm do not apply.

**Contributions.** In this paper, we present the quantum linearization attack, which is a new family of quantum attacks on classically unforgeable MACs when superposition queries are allowed. Thanks to the novelty of our approach, we are able to attack many MACs that resisted previous cryptanalysis, as they do not exhibit the property recalled above (a message block XORed to an internal state value). In particular, our attack usually circumvents the use of TBCs instead of block ciphers. It is also the first case of a quantum polynomial-time attack on MACs with beyond-birthday security, where the internal state has a bigger size. As an example, we break LightMAC with a linear number of queries, and we can attack LightMAC+ with only twice as much.

*Overview.* Our attack starts with the following remark. Consider a function of $\ell$ blocks $x_1, \dots, x_\ell$ of the form: $G(x_1, \dots, x_\ell) = g_1(x_1) \oplus \dots \oplus g_\ell(x_\ell) \oplus C$, where $C$ is an independent constant, and the $g_i$ are independent random functions to which the adversary does not have access. Then classically, this function cannot be distinguished from random with a single query, though as little as four would be enough: we make $x_3, \dots, x_\ell$ constant, we query for every $x_1 \in \{0, 1\}$ and $x_2 \in \{0, 1\}$: the XOR of the four results is zero.

Our key idea is to linearize the function $G$ by restricting the block inputs so that the output is an affine function. Similarly to the simple classical distinguisher, we make the blocks $x_1, \dots, x_\ell$ take only one-bit values and emulate a function of an $\ell$-bit input: $F(x) = F(b_1 \parallel \dots \parallel b_\ell) = G(0^{n-1} \parallel b_1, \dots, 0^{n-1} \parallel b_\ell)$. Now, we will remark that $F$ is an affine function of $b_1, \dots, b_\ell$. As the $g_i$ are XORed; flipping a bit $b_i$ in the input XORs $g_i(0) \oplus g_i(1)$ to the output.

It is well known that the Bernstein-Vazirani algorithm allows to distinguish an affine function from a random one with a single quantum query. This shows that, thanks to a multi-block input, we can access new vulnerabilities of cryptographic constructions. But the power of our attack is clearly demonstrated when we make $G$ go through a new random function:

$$G'(x_1, \dots, x_\ell) = g(G(x)) = g(g_1(x_1) \oplus \dots \oplus g_\ell(x_\ell) \oplus C) . \quad (1)$$

All the functions $g_1, \dots, g_\ell, g$ are unknown to the adversary, so she cannot find the affine structure of the internal $G$. In fact, this function would be classically secure as a MAC. However, when linearizing, we obtain: $G'(x) = g(F(x))$ where $F$ is an affine function of $x = b_1 \parallel \dots \parallel b_\ell$. Thus, $G'$ embeds a hidden Boolean period, and Simon's algorithm can recover it in polynomial time.

*Applications.* In Section 4 and Section 5, we detail the applications of our algorithm. We obtain the first polynomial-time attacks against the following MACs:

* ΘCB3 [57,43], LightMAC [47], LightMAC+ [54], Deoxys [38], ZMAC [37], PMAC_TBC3k [53], PolyMAC [36], GCM-SIV2 [36]

In addition, we provide attacks on the XOR-MACs of [4], on MACs based on universal hashing (e.g., NMH* [31] and BRW Hashing [7]) and, in Section 5.5,
a new superposition forgery attack against Poly1305 [6]. A previous quantum
attack was given in [18], using a hidden shift structure. Using Shor's algorithm
instead, we reduce the number of superposition queries from 2³⁸ to about 32.

*On Parallelizable MACs.* The quantum linearization attack leaves only little space for quantum-secure parallelizable PRFs. Indeed, we are able to break any PRF with extendable domain, where at least $\ge n$ independent input blocks of $\le n$ bits are processed independently, then XORed. This works as well for any operation that is linear on $(\mathbb{F}_2)^n$. It is still possible to obtain an unforgeable IV-or nonce-based MAC of this form, as shown in [9], but the security then relies on the non-repetition of IVs. We do not know if an attack applies when we use a modular addition instead of a XOR in (1). If this was the case, then it would clearly mean that one has to rely on sequentiality or on nonlinear operations.

*Organization.* We start in Section 2 by reviewing some quantum computing notions, the quantum algorithms used in this paper (Deutsch's algorithm, Bernstein-Vazirani, Simon's algorithm, Shor's algorithm), the Q1/Q2 attack scenarios and notions of quantum unforgeability. In Section 3, we detail our new algorithmic ideas. In Section 4, we apply our attack to many parallelizable MAC constructions. We dedicate Section 5 to MACs based on universal hashing. We discuss the implications of our attacks in Section 6 and conclude the paper in Section 7.

## 2 Preliminaries

In this section, we give some preliminaries about quantum computing, quantum attacker models and the well-known quantum algorithms that will be used throughout this paper. We elaborate about the Q2 attacker model and the notion of quantum unforgeability for MACs, with or without IVs. Note that some details of quantum computing will appear in this section. They are intended for the interested reader. In the rest of this paper (with the exception of Section 5.5), we will use the algorithms of this section as black boxes.

### 2.1 Notation

We consider $n$-bit string values, sometimes as elements of $\mathbb{F}_{2^n}$, sometimes as elements of $\mathbb{F}_2^n$. This shall be clear from context. We let $\oplus$ denote the XOR (addition in $\mathbb{F}_2^n$), $\odot$ denote multiplication in $\mathbb{F}_{2^n}$, and $+$ modular addition. We let $\cdot$ denote the scalar product of bit-strings seen as $n$-bit vectors.

### 2.2 On Quantum Computing

Although we choose to present in detail the quantum algorithms that we will use for our attacks, most of our results can be obtained by applying them as black boxes. Thus we stress that our results, similarly as other structural attacks on symmetric cryptosystems [45,39], can be understood from a high-level perspective, and our attacks do not require specific knowledge of quantum computing. Further details are only required to prove the correctness of the algorithms.
A general presentation of the quantum circuit model can be found in [55]. 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 to query $f$ on any quantum state, thus on any superposition of inputs $x$. This is the standard oracle, equivalent to the phase oracle $O_{f,\pm}$ which computes $|x\rangle \mapsto (-1)^{f(x)} |x\rangle$.

One of the basic unitary operations of the quantum circuit model (quantum gates), and actually the most important one in the algorithms of Section 2.3, is the Hadamard gate $H$ which maps a single qubit $|b\rangle$ to $\frac{1}{\sqrt{2}}(|0\rangle + (-1)^b |1\rangle)$. By applying Hadamard gates to each individual qubit of an n-bit input, we compute the Hadamard transform, a particular example of Quantum Fourier Transform:

$$H^{\otimes n} : |x\rangle \mapsto \frac{1}{2^{n/2}} \sum_{y \in \{0,1\}^n} (-1)^{x \cdot y} |y\rangle .$$

An important property is that the Hadamard transform is involutive. For better readability, we often omit global amplitude factors such as the $\frac{1}{2^{n/2}}$ above, as quantum states are always normalized.

Given a quantum state of the form $\sum_x \alpha_x |x\rangle$, the measurement operation destroys the state and yields an element $x$ with probability $|\alpha_x|^2$. Partially measuring the state projects it on a smaller superposition of elements. For a quantum state of the form: $\sum_{x,y} \alpha_{xy} |x\rangle|y\rangle$, measuring the register $|x\rangle$ yields a value $x_0$ with probability $\sum_y |\alpha_{x_0 y}|^2$, and projects on the state $\frac{1}{\sqrt{\sum_y |\alpha_{x_0 y}|^2}} \sum_y \alpha_{x_0 y} |y\rangle$.

## 2.3 Quantum Algorithms

Our new attacks are based on well-known quantum algorithms: Deutsch's algorithm [26], which is a single-bit version of the Deutsch-Jozsa algorithm [27], the Bernstein-Vazirani algorithm [8], Simon's algorithm [60] and Shor's algorithm [59]. These algorithms have in common to be based on Fourier sampling, a process in which a quantum Fourier transform is applied before and after a single query to a superposition oracle. They are also amongst the earliest quantum algorithms proven to beat any classical algorithm, and as such are often presented in textbooks (see e.g. [55]). However, except for Shor's algorithm, their practical interest remained unclear for a long time.

**Deutsch's Algorithm.** Deutsch's algorithm [26] solves Problem 1 with probability 1 using a single query to $O_f$, whereas classically, two queries to $f$ are needed for the same success probability. This constant speedup might seem anecdotal, but is crucial when the same function cannot be queried more than once.
<table><caption>**Algorithm 1** Deutsch's algorithm</caption><tr><td>1: Start from |0⟩</td><td>▷ |0⟩</td></tr><tr><td>2: Apply a Hadamard gate</td><td>▷ |0⟩ + |1⟩</td></tr><tr><td>3: Apply O<sub>f,±</sub></td><td>▷ (-1)<sup>f(0)</sup> |0⟩ + (-1)<sup>f(1)</sup> |1⟩ = (-1)<sup>f(0)</sup> (|0⟩ + (-1)<sup>f(0)⊕f(1)</sup> |1⟩)</td></tr><tr><td>4: Apply a Hadamard gate</td><td>▷ (-1)<sup>f(0)</sup> |f(0) ⊕ f(1)⟩</td></tr><tr><td>5: Measure the state</td><td></td></tr></table>

<table><caption>**Algorithm 2** Bernstein-Vazirani algorithm</caption><tr><td>1: Start from |0<sub>n</sub>⟩</td><td>▷ |0<sub>n</sub>⟩</td></tr><tr><td>2: Apply a Hadamard transform</td><td>▷ &sum;<sub>i</sub> |i⟩</td></tr><tr><td>3: Apply O<sub>f,±</sub></td><td>▷ &sum;<sub>i</sub> (-1)<sup>(a&middot;i)&oplus;<sup>b</sup></sub> |i⟩</td></tr><tr><td>4: Apply a Hadamard transform</td><td></td></tr><tr><td>5: Measure the state</td><td>▷ (-1)<sup>b</sup> H<sup>&otimes;n</sup> &sum;<sub>i</sub> (-1)<sup>a&middot;i</sup> |i⟩ = (-1)<sup>b</sup> H<sup>&otimes;n</sup> (H<sup>&otimes;n</sup> |a⟩) = (-1)<sup>b</sup> |a⟩</td></tr></table>

**Problem 1 (Deutsch's problem).** Given access to a quantum oracle $O_f$ for a function $f: \{0,1\} \rightarrow \{0,1\}$, decide whether $f$ is constant ($f(0) = f(1)$) or balanced ($f(0) \neq f(1)$).

Deutsch's algorithm (**Algorithm 1**) is best presented with a phase oracle $O_{f,\pm}|b\rangle = (-1)^{f(b)}|b\rangle$. It can be seen that upon measurement, the algorithm actually yields the value $f(0) \oplus f(1)$ (although a single query has been made to $f$) whose knowledge solves **Problem 1**.

**Bernstein-Vazirani Algorithm.** The Bernstein-Vazirani algorithm [8] offers a polynomial speedup for finding the slope of an affine function over $\mathbb{F}_2^n$.

**Problem 2 (Bernstein-Vazirani).** Given access to an oracle $O_f$ for an affine function $f: \{0,1\}^n \rightarrow \{0,1\}$, that is, $f(x) = a \cdot x \oplus b$ for $a, b$ unknown, find $a$.

Upon measurement in **Algorithm 2**, we obtain the unknown $a$ with certainty, using a single query to $O_{f,\pm}$, while $n$ queries would be needed classically.

**Remark 1.** This algorithm can be seen as a generalization of Deutsch's algorithm. Indeed, in the case $n=1$, there are only two types of affine functions: $f(x) = x \oplus b$ ($a=1$) and $f(x) = b$ ($a=0$), and Bernstein-Vazirani allows to distinguish them in one query.

**Simon's Algorithm.** Simon's algorithm [60] solves the problem of distinguishing an injective function from a periodic one. Note that it was the first example of an exponential quantum speedup relatively to an oracle.

**Problem 3 (Simon).** Given access to a function $f: \{0,1\}^n \rightarrow \{0,1\}^n$ for which there exists $s$ such that: $\forall x, y, f(x) = f(y) \iff y \in \{x, x \oplus s\}$, find $s$.

In **Algorithm 3**, at Step 9 in the injective case, the value $a$ obtained before has a single preimage $x_a$. Thus, the current state is $\sum_y ((-1)^{x_a \cdot y}) |y\rangle$ and we sample a uniformly random $y \in \{0,1\}^n$. After $n+r$ such samples, the family Y
<caption>**Algorithm 3** Simon's algorithm</caption>

1: $Y = \emptyset$
2: Choose a number $r$ depending on the required probability of error
3: **Repeat** $n + r$ times
4: Start from $|0_n 0_n\rangle$
5: Apply a Hadamard transform to the first register $\triangleright \sum_x |x\rangle|0\rangle$
6: Apply $O_f$ (standard) $\triangleright \sum_x |x\rangle|f(x)\rangle$
7: Measure the second register, obtain $a$ $\triangleright \sum_{x|f(x)=a} |x\rangle$
8: Apply a Hadamard transform $\triangleright \sum_y (\sum_{x|f(x)=a} (-1)^{x \cdot y}) |y\rangle$
9: Measure a $y$, $Y \leftarrow Y \cup \{y\}$
10: **EndRepeat**
11: **if** $Y$ is of full rank **then**
12: **return** "injective case"
13: **else if** $Y$ is of rank $n-1$ **then**
14: **return** "periodic case" and the $s$ orthogonal to $Y$
15: **else**
16: **return** "failure"
17: **end if**

will grow to a full-rank family. In the periodic case, the value $a$ has exactly two preimages $x_a$ and $x_a \oplus s$ which interfere with each other. The current state is

$$ \sum_y ((-1)^{x_a \cdot y} + (-1)^{(x_a \oplus s) \cdot y}) |y\rangle = \sum_y (-1)^{x_a \cdot y} (1 + (-1)^{s \cdot y}) |y\rangle $$

and only the vectors $y$ orthogonal to $s$ have a non-zero amplitude. Thus, the family $Y$ grows to span the euclidean subspace orthogonal to $s$. Computing the rank of $Y$ allows to detect the period and solving the linear system $Ys = 0_n$ allows to recover it.

*Generalizations.* Although the original Simon's problem concerns functions without random collisions (that is, we cannot have $f(x) = f(y)$ if $x \oplus y \notin \{0, s\}$), it can be shown that the algorithm works as well for random functions having a period, which models the cryptographic problems that we are interested in.

The following simple condition was given in [39]. For Simon's algorithm to run as expected (i.e., with $O(n)$ queries), it is sufficient for the periodic function $f$, of period $s$, to satisfy the following condition:

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

That is, $f$ should not admit another "unwanted partial period" $t$. In the examples studied in this paper, the condition (2) will be easy to check.

Note that if we had $f(x \oplus t) = f(x)$ for all $x$, then $t$ would simply turn the set of periods of $f$ into a vector space of dimension 2. In general, the space of periods could be a vector space of any dimension. An extended version of Simon's algorithm by Brassard and Høyer [20] allows to recover this whole space in polynomial time.
Finally, another important case is when the output set is smaller than the input set. This was studied in [16] for Simon's algorithm and [48] for period-finding in general. The results in [16] show that as long as the functions behave as random (but with the periodicity constraint), then for $n$ input bits, the number of output bits required to run correctly without any cost increase is of order $\log_2 n$. The results in [48] show that the output can be hashed down to a single bit, and the algorithms still work up to a constant increase in queries.

*Shor's Algorithm.* We will use Shor's algorithm [59] to solve the *abelian hidden period* problem. It will appear in a “black-box” manner in Section 5.4, and in Section 5.5. We will analyse in detail the behavior of the algorithm on Poly1305.

*Problem 4 (Abelian hidden period).* Let $(G, +)$ be an abelian group, $X$ a set. Given access to a function $f: G \to X$ which is either injective, or periodic $(\exists s \in G, f(s+\cdot) = f(\cdot))$, then determine the case and / or find the period.

In particular, we consider $G = \mathbb{Z}_{M_1} \times \dots \times \mathbb{Z}_{M_k}$ the product of multiple cyclic groups of known order. For simplicity, and to prepare for Section 5.5, we present the algorithm in the case of $\mathbb{Z}_p^2$ for some prime $p$. Note that $f$ is also periodic over $\mathbb{Z}_p$ in each of its parameters. This is the typical situation when Shor's algorithm is used to solve the Discrete Logarithm Problem. The periods of $f$ form a two-dimensional integer lattice, which is generated by $(p, 0)$ and $(-1, s)$ for some $s$. In other words, the value of $f(x, y)$ depends only on the value of $xs + y \bmod p$. We may assume for simplicity that the function $xs + y \bmod p \mapsto f(x, y)$ is injective.

The algorithm only relies on an efficient implementation of the Quantum Fourier Transform over $\mathbb{Z}_p$:

$$|x\rangle \mapsto \sum_{y=0}^{p-1} \exp \left( 2i\pi \frac{xy}{p} \right) |y\rangle ,$$

which we assume exact. We represent the elements of $X$ on $m$ bits.

In *Algorithm 4*, at Step 4, we can only measure a vector $|z, t\rangle$ having a nonzero amplitude. This means that we need:

$$\sum_{x=0}^{p-1} \exp \left( 2i\pi \frac{(z-st)x}{p} \right) \neq 0 ,$$

which happens only when $(z - st) = 0$. In that case, the sum simply gives $p$. After renormalization, all vectors $|z, t\rangle$ with $(z - st) = 0$ have the same amplitude $\frac{1}{\sqrt{p}}$, and we will measure one of them taken uniformly at random. If $t \neq 0$, we compute $s$ by $s = zt^{-1} \bmod p$. This occurs with probability $1 - \frac{1}{p}$.

## 2.4 Attack Scenarios

We consider different *attack scenarios* throughout this paper.
<caption>**Algorithm 4** Shor's algorithm</caption>

1: Start from $|0, 0, 0_m\rangle$ $\triangleright |0, 0, 0_m\rangle$
2: Apply a Quantum Fourier Transform on both input registers
$\triangleright \sum_{x,y=0}^{p-1} |x, y\rangle |0_m\rangle$
3: Apply $O_f$ $\triangleright \sum_{x,y=0}^{p-1} |x, y\rangle |f(x, y)\rangle$
4: Measure the second register. The state collapses on a uniform superposition of all $(x, y)$ such that $xs + y = a \mod p$ for some unknown $a$, meaning $y = a - xs \mod p$:
$$ \sum_{x=0}^{p-1} |x\rangle |a - xs\rangle . $$

5: Apply a Quantum Fourier Transform again. The state becomes:

$$ \sum_{z,t=0}^{p-1} \left( \sum_{x=0}^{p-1} \exp \left( 2i\pi \frac{zx + (a - xs)t}{p} \right) \right) |z,t\rangle \\ = \sum_{z,t=0}^{p-1} \exp(2i\pi at/p) \left( \sum_{x=0}^{p-1} \exp \left( 2i\pi \frac{(z - st)x}{p} \right) \right) |z,t\rangle . $$

6: Measure a $|z, t\rangle$ and return $s = zt^{-1} \mod p$.

**Q1 and Q2 setting.** Following [40,33,17], we will adopt the Q1 / Q2 terminology to classify quantum attacks on symmetric schemes. Note that these models have alternative names, for example “quantum chosen-plaintext attack” (qCPA) is used for “Q2” in [34,22]. 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}$. This is the case for all the attacks of this paper.

The study of quantum attacks on symmetric schemes in the Q2 setting was sparkled by seminal work of Kuwakado and Morii [44,45], who showed that the 3-round Luby-Rackoff construction and the Even-Mansour cipher became insecure if exposed to superposition queries. More precisely, they can 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.

**Attacks based on period-finding.** Since these earlier results, many works have extended the reach of Q2 attacks [39,15,46,19,28,30]. However, the attack strategy has remained the same. A hidden structure is embedded in the construction to be attacked, so that $f(E_K(x), x)$ for some choice of combination $f$, is a periodic function of $x$; or that a shift exists between $f(E_K(x), x)$ and $g(E_K(x), x)$. The recovery of this hidden period or shift, which is secret material, then leads to a break. We can cite some examples:
Against the Even-Mansour construction [45]: $E_K(x) = K_2 \oplus \Pi(x \oplus K_1)$ for a random public permutation $\Pi$ and two keys $K_1, K_2$. One has:

$$E_K(x) \oplus \Pi(x) = E_K(x \oplus K_1) \oplus \Pi(x \oplus K_1)$$

which leads to a recovery of $K_1$ in $O(n)$ queries and $O(n^3)$ computations.

Against CBC-MAC with two blocks [39]: It can be defined as:

$$\text{CBC-MAC}(y, x) = E_{K'} \circ E_K(x \oplus E_K(y)),$$

where $K$ and $K'$ are two keys that will remain unknown to the adversary. Due to the structure of CBC-MAC, one can take two arbitrary values $\alpha_0, \alpha_1$, and define the function:

$$F : \left\{ \begin{array}{l} \{0,1\} \times \{0,1\}^n \mapsto \{0,1\}^n \\ (b, x) \quad \rightarrow \quad \text{CBC-MAC}(\alpha_b, x) \end{array} \right. \qquad (3)$$

We have then that $F(b, x) = F(b \oplus 1, x \oplus E_K(\alpha_0) \oplus E_K(\alpha_1))$. Thus $F$ has a hidden boolean period $1 \parallel E_K(\alpha_0) \oplus E_K(\alpha_1)$. Having obtained the internal value $E_K(\alpha_0) \oplus E_K(\alpha_1)$, we can query the tag of any message starting with block $\alpha_0$, and then forge a message starting with $\alpha_1$ with the same tag.

*Constructions based on IVs.* We consider two types of constructions with quantum access: some make use of an initialization value (IV, sometimes also named a nonce) and some do not. In the IV case, we consider that the IV is a classical value, chosen randomly before each oracle query, and not repeated. This model follows from the idea that the IV is not controlled by the adversary, and it can serve as an intermediate between the classical setting and a (much) stronger model in which the adversary would completely (and quantumly) control the IVs.

In fact, the latter case does not seem to have been studied so far in quantum security. Well-known notions such as IND-qCPA [14] rely on classical randomness, and many modes of operation have been proven secure in this model [3,9].

In the classical setting, many MAC constructions have a security that relies on the non-repetition of IVs, for example the MAC of OCB [43]. The same happens in the quantum setting, since the MAC of QCB [9] has been proven secure under quantum queries with classical non-repeated IVs.

*Unforgeability.* The first notion of quantum unforgeability for MACs was defined by Boneh and Zhandry [13]. We will name it plus-one unforgeability (PO), following [1]. The idea is that an adversary making $q$ quantum queries to the construction, where $q$ is polynomial, should not be able to produce $q + 1$ valid $\{\text{message, tag}\}$ pairs. A more recent definition is blind-unforgeability (BU), proposed in [1]. It is strictly stronger than PO-unforgeability. In this paper, we will give several quantum forgery attacks that break the PO notion, thereby also breaking BU.

*Quantum PRFs.* A quantum pseudorandom function (qPRF) is a family of functions $F_K$, indexed by a key space $K$, such that no quantum adversary making queries to an oracle $O_f$ can distinguish efficiently between a function $F_K$, with
K drawn uniformly at random, and a truly random function. It is shown respectively in [13] and [1] that a qPRF is also a quantum-secure deterministic MAC by the PO and BU definitions. Therefore, any function that is not PO-unforgeable is also not a secure qPRF. To the best of our knowledge, the only classical symmetric construction that has been proven quantum-secure as a deterministic MAC, the Cascade / NMAC / HMAC construction [61], is also a qPRF.

## 2.5 A Quantum Attack on OCB3

We detail the Q2 attack on the MAC of OCB3 from [39]. As the other previous works recalled above, this attack relies on a Boolean period-finding problem.

**Specification.** OCB3 is an IV-based mode of authenticated encryption with associated data (AEAD), based on a block cipher [43]. As OCB stands for offset codebook, the scheme relies on the definition of offsets that are dependent on the key and change between each block. We will focus on the authentication tag of OCB3 (see Figure 1). Our considerations are independent on the exact value of the offsets, and apply to all versions of OCB, but we use OCB3 as a concrete example.

<figure><img src="image_163.png" /><figcaption>Fig. 1. Computation of the tag in OCB3. Only the offset $\Delta^{IV}$ depends on the IV.</figcaption></figure>

**Forgery Attack with Simon's Algorithm.** Kaplan et al. showed in [39] how to forge authentication tags using Simon's algorithm. The idea is to query the tag of an empty message with two AD blocks $A_0, A_1 = x$:

$$x \rightarrow E_K(\Delta_{IV}) \oplus E_K(\Delta_0 \oplus x) \oplus E_K(\Delta_1 \oplus x).$$

One can then remark that this function of $x$ is periodic, of period $\Delta_0 \oplus \Delta_1$, independent of the IV, and only on the secret key $K$. Although the function changes at each query (since the IV changes), the period is always the same and Simon's algorithm allows to recover it with $\mathcal{O}(n)$ superposition queries. (For the same reason, we could use a non-empty message, and even different messages between the queries.)
<figure><img src="image_164.png" /><figcaption>Fig. 2. Computation of the tag in ΘCB3. Only the final tweak t depends on the IV.</figcaption></figure>

Once $\Delta_0 \oplus \Delta_1$ has been obtained, one can then query the tag of any pair of AD blocks $A_0, A_1$ and forge the tag of $A_1, A_0$.

*Remark 2.* It is easy to check that Equation (2) is satisfied in practice. If it wasn’t, then the existence of an unwanted partial period $t$:

$$ \Pr_x [f(x \oplus t) = f(x)] \geq \frac{1}{2}, $$

would imply a higher-order differential of probability greater than $\frac{1}{2}$ for $E_K$, which is impossible if $E_K$ is a pseudorandom permutation (in other words, $E_K$ would suffer from a classical break).

# 3 The Quantum Linearization Attack: Algorithmic Ideas

In this section, we present the algorithmic ideas underlying our new quantum linearization attack. To that end, we keep the example of OCB3 [43] introduced in Section 2.5. We explain a new way to forge with Q2 queries. The extensions and applications of this new idea will be explored in the next sections.

Note that to the best of our knowledge, this is the first application of the Deutsch and Bernstein-Vazirani algorithms for forgery attacks.

## 3.1 Attack on ΘCB with Deutsch’s Algorithm

The attack of Section 2.5 works only because of the offsets. In fact, the existence of a controlled value (here $x$) XORed to a secret (here the offsets) has been so far a prerequisite of all Q2 attacks.

Here we present a forgery attack against the mode ΘCB3 [57,43], which is a more abstract version of OCB3 in which the block cipher $E_K$ is replaced by a *tweakable* block cipher (a family of independent block ciphers $\tilde{E}_{K,t}$ indexed by a *tweak* $t$). This is shown in Figure 2.

Here, the tweaks $t_0, \dots, t_j, t_*$ form an arbitrary sequence of distinct values, that depend only on the block index; the tweak $t$ is the only one dependent on the IV. Again, we consider an empty message, but this time a single AD block
that is either 0 or 1. We define $i$ functions which truncate the output of such a call to the $i$th bit:

$$F_i: \begin{cases} \{0,1\} \to \{0,1\} \\ b \mapsto \text{Trunc}_i(\tilde{E}_{K,t_0}(b) \oplus \tilde{E}_{K,t}(0)) \end{cases} .$$

The functions $F_i$ change at each new superposition query (because the IV intervenes in $\tilde{E}_{K,t}(0)$). Thus we need the ability to compute a query to $F_i$ using a single query to the untruncated mode itself. This is fortunately easy to do so using the truncation technique of [33].

With this single query, Deutsch's algorithm allows to recover the value:

$$\begin{aligned} & \text{Trunc}_i(\tilde{E}_{K,t_0}(0) \oplus \tilde{E}_{K,t}(0)) \oplus \text{Trunc}_i(\tilde{E}_{K,t_0}(1) \oplus \tilde{E}_{K,t}(0)) \\ & = \text{Trunc}_i(\tilde{E}_{K,t_0}(0) \oplus \tilde{E}_{K,t_0}(1)), \end{aligned}$$

and within $n$ queries and uses of the algorithm, we can obtain the full value $\tilde{E}_{K,t_0}(0) \oplus \tilde{E}_{K,t_0}(1)$.

We can now forge valid messages as follows: we query a message with 0 as the first block, we XOR $\tilde{E}_{K,t_0}(0) \oplus \tilde{E}_{K,t_0}(1)$ to the tag, and we have obtained the tag of the same message with 1 replacing the first block. This works for any block and for any pair of messages.

This attack shows that XORing with an IV-dependent value, although it provides sufficient protection against forgeries in the classical setting (since $\Theta$CB has a security proof), does not in the quantum setting.

Interestingly, it is possible to protect against this attack by using the IV in the TBC calls, as done by Bhaumik et al. in [9]. While this simple modification has practically no incidence on the classical security of the mode, it is crucial to obtain unforgeability in the quantum setting.

*Another Example: XOR-MACs.* In [4], two XOR-MAC constructions are defined, which can be attacked with Deutsch's algorithm. They are both based on a pseudorandom function $F_K$ and an IV. The first one, XMACR (*randomized XOR scheme*), considers that the IV is drawn uniformly at random, and the second one, XMACC (*counter-based XOR scheme*) that it is maintained as a counter. Both compute:

$$\text{MAC}(m_1, \dots, m_\ell; \text{IV}) = F_K(0 \| \text{IV}) \oplus \bigoplus_{1 \le i \le \ell} F_K(1 \| i \| m_i).$$

Then, since the contribution of the IV is only XORed, forgeries can be made.

## 3.2 Using the Bernstein-Vazirani algorithm

We propose here a generalization of the previous attack, with longer queries. We now consider functions of the form

$$g_1(x_1) \oplus g_2(x_2) \oplus \dots \oplus g_\ell(x_\ell) \oplus C$$
with, as before, a C that is independent from all $x_i$. Now, we can choose some arbitrary $\alpha_i^0$ and $\alpha_i^1$, and consider the function

$$F_j: \{0,1\}^\ell \to \{0,1\} \\ (b_1, \dots, b_\ell) \mapsto \text{Trunc}_j \left( \bigoplus_{i=1}^\ell g_i(\alpha_i^{b_i}) \oplus C \right),$$

It is easy to see that this function is affine: indeed, if we change the value of $b_i$, then we add $\text{Trunc}_j(g_i(\alpha_i^0) \oplus g_i(\alpha_i^1))$ to the output.

Hence, if we apply the Berstein-Vazirani algorithm, in one query, we recover the values of the $\text{Trunc}_j(g_i(\alpha_i^0) \oplus g_i(\alpha_i^1))$, for all $i$. Next, it suffices to repeat the algorithm for each bit of the output to obtain the value of all the $g_i(\alpha_i^0) \oplus g_i(\alpha_i^1)$.

This technique can be applied to OCB3 / $\Theta$CB3, as the tag is a function of the form

$$\bigoplus_i g_i^k (AD_i) \oplus f_k (IV, M)$$

Hence, we can attack multiple blocks of associated data at once.

## 3.3 Attacking any XOR of permutations

The main limitation of the previous attacks is that they need a direct access to the linear combination of independent blocks. In this section, we overcome this limitation with an attack that leverages linear combinations of permutations in a more intrinsic way, using Simon's algorithm in a novel fashion.

We consider a MAC construction that processes $m > n$ message blocks $x_1, \dots, x_m$ by pushing the $x_i$ through independent TBC calls $\tilde{E}_{K,i}$, XORing the result and applying an IV-dependent function afterwards.

$$IV, (x_1, \dots, x_m) \mapsto f_K \left( IV, \left( \bigoplus_{1 \le i \le m} \tilde{E}_{K,i}(x_i) \right) \right).$$

*Remark 3.* We write the attack with a TBC, i.e., a family of independent block ciphers $\tilde{E}_{K,T}$ indexed by a secret key K and a public tweak T. This is to emphasize the application of our attack to parallelizable MACs; however, the attack works in the same way if we replace the independent block ciphers by independent functions.

In the case of $\Theta$CB, the definition of $f_K$ is simple, since it only XORs the IV- and the AD-dependent parts. But the attack of Section 3.2 does not apply anymore if $f_K$ is a pseudorandom function. This will be the case of our new attack, which is why it will apply to many MAC constructions.

*Quantum Attack.* First of all, it is easy to see that if the $\tilde{E}_{K,i}$ are independent block ciphers, and if $f_K$ is a pseudorandom function family, then this construction is a classically unforgeable MAC: this is the security of $\Theta$CB3.

Our attack in the quantum setting starts from the same idea as above (Section 3.2): we query the MAC with arbitrary blocks taking two values: $x_1 =$
$b_1||0_{n-1}, \dots, x_m = b_m||0_{n-1}$, where $x = b_1 \dots b_m$ forms an $m$-bit input (in the remaining of this paper, we will write the $n-1$ zeroes used for completion as a single 0). We will put $x$ in superposition, and so, there will be only “one superposed bit” in each individual block input.

One then observes that $\tilde{E}_{K,1}(x_1) \oplus \dots \oplus \tilde{E}_{K,m}(x_m)$ is an affine function of $x$:

$$F(x) := \tilde{E}_{K,1}(x_1) \oplus \dots \oplus \tilde{E}_{K,m}(x_m) \\ = \bigoplus_i \left( b_i \odot \left( \tilde{E}_{K,i}(0) \oplus \tilde{E}_{K,i}(1) \right) \oplus \tilde{E}_{K,i}(0) \right) .$$

More precisely, if we identify bit-strings with boolean column vectors, $F(b_1 \dots b_m)$ is equal to:

$$\underbrace{((\tilde{E}_{K,1}(0) \oplus \tilde{E}_{K,1}(1)) \cdots (\tilde{E}_{K,m}(0) \oplus \tilde{E}_{K,m}(1)))}_{M_m} \times \begin{pmatrix} b_1 \\ \vdots \\ b_m \end{pmatrix} \oplus \bigoplus_i \tilde{E}_{K,i}(0) .$$

The matrix $M_m$ has $n$ rows and $m$ columns, so when $m \ge n + 1$, its kernel is nontrivial. This means there will exist a non-zero $m$-bit boolean vector $\alpha$ such that:

$$((\tilde{E}_{K,1}(0) \oplus \tilde{E}_{K,1}(1)) \cdots (\tilde{E}_{K,m}(0) \oplus \tilde{E}_{K,m}(1))) \times \alpha = \begin{pmatrix} 0 \\ \vdots \\ 0 \end{pmatrix},$$

and for all such vectors $\alpha$, seen as $m$-bit strings, we have:

$$F(x \oplus \alpha) = M_m \times (x \oplus \alpha) \oplus \bigoplus_i \tilde{E}_{K,i}(0) = F(x) .$$

In other words, this function $F$ hides a subgroup of $(\mathbb{F}_2)^m$ generated by all the vectors $\alpha$ satisfying the condition above (it is easy to see that they indeed form a group). Thus, $F$ satisfies the promise of Simon's algorithm: by making a single superposition query, we can find $y$ such that $y \cdot \alpha = 0$ for such an $\alpha$, and furthermore, as Brassard and Høyer showed [20], we can even recover the full subspace of periods with a polynomial number of quantum queries to $F$.

However, in our model, we cannot query $F$ directly and we have instead access to: $f_K(IV, F(x))$, where $IV$ changes at each query. The key remark is that the hidden subgroup is unchanged, since $F$ is independent of the $IV$. This assumption is enough to allow Simon's algorithm and its extensions to work.

**Remark 4 (Smaller $m$).** Some period might still arise if $m \le n$. Indeed, if $m = n$, there will be a non-trivial period with probability around $1 - 1/e$. This quickly decays for smaller $m$.

**Remark 5 (Unwanted collisions).** Since the “inner” function $F$ is affine, it does not contain any unwanted collisions. If $F(x \oplus \alpha) = F(x)$ for some $\alpha$ and $x$,