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

*Complexity analysis.* Using similar analysis to Section 6.1, we have $c_1 = 2u + s - \ell$ (as a pair of chains collides at the same offset with probability $2^{s-\ell}$, and we have $2^{2u}$ such pairs) and $c_2 = 2t + 2s - \ell$. The attack succeeds if the sets of collisions found online and offline intersect. According to Lemma 3, this occurs with high probability if $c_1 + c_2 \ge \ell - 2s$. In the following, we assume $c_1 + c_2 = \ell - 2s$.

**Step 1:** $2^{u+s} = 2^{s/2+c_1/2+\ell/2}$ **Step 2:** $2^{s+c_1/2+\ell/2} = 2^{\ell-c_2/2}$

**Step 3:** $2^{t+s} = 2^{\ell/2+c_2/2}$ **Step 4:** $2^{c_2+s} + 2^{c_1+c_2} \cdot c_1 = 2^{c_2+s} + 2^{\ell-2s} \cdot c_1$

The best tradeoffs are achieved by balancing steps 2 and 3, i.e. with $c_2 = \ell/2$, implying that $c_1 = \ell/2 - 2s$. This reduces the complexity to:

**Step 1:** $2^{3\ell/4-s/2}$ **Step 2:** $2^{3\ell/4}$

**Step 3:** $2^{3\ell/4}$ **Step 4:** $2^{\ell/2+s} + 2^{\ell-2s} \cdot \ell/2$

With $s \le \ell/8$, we have $\ell/2 + s \le 5\ell/8$ and $3\ell/4 \le \ell - 2s$; therefore the complexity of the attack is $\tilde{O}(2^{\ell-2s})$.

We note that the complexity can be reduced to a minimum of $O(2^{3\ell/4})$ (without logarithmic factors) by using messages which are slightly longer than $2^{\ell/8}$. In particular, this gives optimal attacks for functions of the SHA-2 family.

## 7.2 HAIFA

The general structure of the attack on HAIFA is similar to one of the previous attack on Merkle-Damgård. The main difference between the attacks is that we are forced to use same-offset collision search offline, rather than free-offset collision search as in the previous attack.

### Attack 5: Short message attack for HMAC with HAIFA

Complexity $\tilde{O}(2^{\ell-2s})$, with $s \le \ell/10$ (min: $2^{4\ell/5}$)

1. (online) Fix an arbitrary message suffix $C$ of length $2^s$, query the oracle with $2^u$ messages $M_i = [i] \parallel C$, and locate $2^{c_1}$ collisions.

2. (online) For each collision $(i, j)$, use a binary search to find the distance (offset) $d_{ij}$ from the starting point to the collision, and denote the (unknown) state reached after $M_i$ (or $M_j$) by $y_{ij}$.
Denote the set of all $y_{ij}$ (containing about $2^{c_1}$ states) by $Y$. Build an online diamond filter for all the states in $Y$.

3. (offline) Run a same-offset collision search algorithm by computing the compression function with the message $C$ from $2^t$ arbitrary starting points, and locate $2^{c_2}$ collisions.

4. (offline) For each offline collision $\hat{x}$, match the endpoint of its chain with all online collisions $y_{ij} \in Y$ that occur at the same offset as $\hat{x}$. More precisely, for each $\hat{x}$ with offset $d$, use the diamond filter to test only the endpoint of its chain (at offset $2^s$) with the corresponding collisions in $Y$ that occur at offset $d_{ij} = d$. If a match with some $y_{ij}$ is found, then with high probability the state reached after $M_i$ and $M_j$ is the endpoint of the offline collision $\hat{x}$.

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

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

We generate collisions and build an online diamond filter, and match the endpoints with offline collisions endpoints using the collision offset as a first filter.

*Analysis.* The attack succeeds in case there is a match between the set of collisions detected online and offline that occur at the same offset. According to Lemma 4, this match occurs with high probability when $c_1 + c_2 \ge \ell - s$, and thus we assume that $c_1 + c_2 = \ell - s$.

*Complexity analysis.* Similarly to the analysis of the previous attack on Merkle-Damgård, we have $c_1 = 2u + s - \ell$, but as we use same-offset collision search offline, we can detect a smaller number of $c_2 = 2t + s - \ell$ collisions. We note that the online collision offsets $d_{ij}$ are essentially uniform (see Lemma 1), and therefore in Step 4, each offline collision $\hat{x}$ at offset $d$ is matched with about $2^{c_1} \cdot 2^{-s}$ states in $Y$.

$$ \textbf{Step 1:} \quad 2^{u+s} = 2^{s/2+c_1/2+\ell/2} $$

$$ \textbf{Step 3:} \quad 2^{s+t} = 2^{s/2+c_2/2+\ell/2} $$

$$ \textbf{Step 2:} \quad 2^{s+c_1/2+\ell/2} = 2^{\ell-c_2/2+s/2} $$

$$ \textbf{Step 4:} \quad 2^{c_1+c_2-s} \cdot c_1 = 2^{\ell-2s} \cdot c_1 $$

The optimal tradeoffs are achieved by balancing steps 2 and 3, i.e. with $c_2 = \ell/2$, implying that $c_1 = \ell/2 - s$. This reduces the complexity to:

$$ \textbf{Step 1:} \quad 2^{3\ell/4} $$

$$ \textbf{Step 3:} \quad 2^{3\ell/4+s/2} $$

$$ \textbf{Step 2:} \quad 2^{3\ell/4+s/2} $$

$$ \textbf{Step 4:} \quad 2^{\ell-2s} \cdot \ell/2 $$

With $s \le \ell/10$, we have $3\ell/4 + s/2 \le 4\ell/5 \le \ell - 2s$; therefore the complexity of the attack is $\tilde{O}(2^{\ell-2s})$.
# 8 Key-Recovery Attack on HMAC with GOST R 34.11-2012 (Streebog)

In this section we are interested in hash functions that use an internal checksum, as shown in Figure 4. In [19], the state-recovery attack on HMAC with a Merkle-Damgård hash function was extended into a key-recovery attack, in case the hash function uses an internal checksum like the GOST R 34.11-94 hash function. Here, we show that a similar attack can be applied to a hash function based on HAIFA with an internal checksum. Namely, the state-recovery attack (with complexity $2^{4\ell/5}$) can be extended into a key-recovery attack (with complexity $2^{4\ell/5}$).

In particular, this attack is applicable to the standard GOST R 34.11-2012 (aka Streebog), and gives a key-recovery attack with complexity $2^{417}$ for its 512-bit version. This result shows that HMAC-GOST R 34.11-2012 is weaker than HMAC-SHA-512 (for which no key-recovery attack better than exhaustive search is known).

## 8.1 Description of the attack

The attack uses the same framework as [19], exploiting the structure of hash functions with a checksum. We target the finalization function in the first hash function call. The input state value $x_*$ can be recovered using the previous state-recovery attacks, and we exploit the fact that the checksum value is key dependant, but can be controlled by injecting differences in the message: $\sigma = K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M)$. This allows for attacks which are somewhat similar to related-key attacks.

More precisely, we first generate a large set of messages of length $L$, leading to the same state $x_*$, but with different checksums $\sigma$. Then, we consider collisions in the function $\sigma \mapsto g(x_*, L, \sigma)$, which can be detected using online calls to the MAC oracle. At the same time, we can also generate such collisions offline since $x_*$ and $L$ are known. Moreover, if we find two collisions with the same difference in the $\sigma$ input, there is a high probability that the actual $\sigma$ values are the same, because the other inputs to $g$ ($x_*$ and $L$) are fixed (on average, we expect a single collision with a fixed difference). Once we find an online collision and an offline collision with the same difference, we can therefore recover the value of $K$ by exploiting the equation $\sigma = K \oplus \text{ipad} \oplus \text{Sum}^{\oplus}(M)$.

## 8.2 Detailed attack process

The first step of the attack uses the state-recovery attack of Section 7.2. However, unlike hash functions without checksums, equal tags of arbitrary messages of the same length (but with different checksums) do not imply equality (with high probability) of the states reached after the messages are processed. Therefore, we execute Attack 5 with the modifications below that ensure we only compare tags of messages with a fixed checksum.
<figure><img src="image_126.png" /><figcaption>Fig. 4 HMAC based on a hash function with a block counter and a checksum (dashed lines).</figcaption></figure>

* In step 1, we use $M_i = [i] \parallel [i] \parallel C$

* In step 2, when building the diamond structure, we extend the messages by $m \parallel m$. We do the same when building a collision pair for the endpoint of the diamond.

* For the offline steps, we ignore the checksum, and only look for collisions in the iterated state.

## Attack 6: Key-recovery attack against HMAC with a GOST-like hash function

Complexity $\tilde{O}(2^{4\ell/5})$

0. Execute Attack 5 to recover a state $x_1$ obtained after processing some message $M_1$, with $|M_1| = s = \ell/10$.

1. (offline) Starting from state $x_1$, use Joux's multicollision attack [14] to generate a set of $2^{7\ell/10}$ messages that all collide on an internal state before the checksum block, but with different checksums. Denote the final state as $x_*$, and the length of the messages as $L$.

2. (online) Query the MAC oracle with the set of messages from Step 1 and collect collisions ($2^{2 \cdot 7\ell/10 - \ell} = 2^{2\ell/5}$ collisions are expected). For each collision $(M, M')$, compute the checksum difference $\Delta M = \text{Sum}^{\oplus}(M) \oplus \text{Sum}^{\oplus}(M')$, and store $(\Delta M, \text{Sum}^{\oplus}(M))$.

3. (offline) Choose a set of $2^{4\ell/5}$ one-block random checksums $\sigma$, compute $g(x_*, L, \sigma)$ and collect collisions ($2^{3\ell/5}$ collisions are expected). For each collision $(\sigma, \sigma')$, compute the difference $\sigma \oplus \sigma'$ and compare it with the stored $\Delta M$ from Step 2. If a match is found, consider $\text{Sum}^{\oplus}(M) \oplus \sigma \oplus \text{ipad}$ and $\text{Sum}^{\oplus}(M) \oplus \sigma' \oplus \text{ipad}$ as potential key candidates, and test them using a known tag.
*Analysis.* Since we have $2^{2\ell/5}$ collisions in Step 2 and $2^{3\ell/5}$ collisions in Step 3, there is a high probability to find a match which is likely to reveal the key.

*Complexity.*

$$
\begin{array}{llll}
\textbf{Step 0:} & \tilde{O}(2^{4\ell/5}) & \textbf{Step 1:} & \ell \cdot 2^{\ell/2} \\
\textbf{Step 2:} & 2^{s+7\ell/10} = 2^{4\ell/5} & \textbf{Step 3:} & 2^{4\ell/5}
\end{array}
$$

The total complexity is $\tilde{O}(2^{4\ell/5})$. In Appendix B, we give a more precise complexity evaluation of this attack and show that it requires less than $2^{417}$ operations on average when applied to *Streebog* (with $\ell = 512$).

*Significance of short message attacks.* The efficient state-recovery attack for short messages is an important factor here, as the message length directly influences the time complexity of the attack in Step 2. In fact, state-recovery attacks with complexity $2^{\ell-s}$ as in Section 5 (or in [19], for the Merkle-Damgård construction) can only reach complexity $2^{5\ell/6}$ for key-recovery, while the attacks with complexity $2^{\ell-2s}$ (described in Section 7) allow to reach complexity $2^{4\ell/5}$.

We note that in GOST R 34.11-94 (which is based on Merkle-Damgård as opposed to HAIFA) the message length is processed with the same function as the other blocks. This (in addition to some padding properties) allowed the attack of [19] to deduce the state of a short message from the state of a long message. Therefore, unlike our key-recovery attack on HMAC with GOST R 34.11-2012, efficient state-recovery attacks for short messages did not play an important role in the key-recovery attack on HMAC with GOST R 34.11-94 [19].

## 9 Universal Forgery Attacks with Short Queries

In the setting of universal forgery attacks the adversary receives a challenge message $C$ at the beginning of the game. The goal of the adversary is to predict the tag of the challenge by interacting with the MAC oracle, but without querying for the actual challenge $C$.

We now revisit the universal forgery attack of Peyrin and Wang [24]. This attack has two phases, where in the first phase the adversary recovers one of the internal states computed by the MAC oracle on the challenge $C$. In the second phase, the adversary uses a second-preimage attack on long messages in order to generate a different message $C'$ known to have the same tag as the challenge. Thus, by querying the MAC oracle for $C'$, the adversary can forge the tag of $C$. The first phase of the attack is the most expensive; the attack of [24] requires $\tilde{O}(2^{5\ell/6})$ computations, which has been improved to $\tilde{O}(2^{3\ell/4})$ in [11] using a heuristic assumption on the functional graph of random functions.

The main drawback of those attacks is that its first phase uses very long queries to the MAC oracle, regardless of the length of the challenge.<fnref n="4" /> Therefore,

<footnote n="4">⁴ The first phase of the attacks of [11,24] uses queries of length $2^{\ell/2}$. Their algorithms are related to the cycle-based attack of [19] that is generalized in Section 6.2.</footnote>
the attack is inapplicable to many concrete HMAC instantiations where the hash function limits the message length (such as HMAC-SHA-1 and HMAC-SHA-2).

In this section, we use the tools developed in this paper to devise two universal forgery attacks using shorter queries to the MAC oracle. For a challenge of length $2^s$, our first universal forgery attack has a complexity of $\tilde{O}(2^{\ell-s})$ with $s \le \ell/7$, using queries to the MAC oracle of length of at most $2^{2s}$ (which is significantly smaller than $2^{\ell/2}$ for any $s \le \ell/7$). Thus, the optimal complexity of this attack is $\tilde{O}(2^{6\ell/7})$, obtained with a challenge of length at least $2^{\ell/7}$ and queries of length $2^{2\ell/7}$. Our second universal forgery attack has a complexity of only $\tilde{O}(2^{\ell-s/2})$. However, it is applicable for any $s \le 2\ell/5$, using queries to the MAC oracle of length of at most $2^s$. Thus, this attack has an improved optimal complexity of $O(2^{4\ell/5})$, which is obtained with a challenge of length at least $2^{2\ell/5}$ and queries of length $2^{2\ell/5}$.

In order to devise our attacks, we construct new state-recovery algorithms, but reuse the second phase from [24] (i.e., the second-preimage attack) in both of the attacks. Thus, in the following, we concentrate on the state-recovery algorithms. For the sake of completeness, we describe the second phase of the attack in Appendix A. Since its complexity is about $2^{\ell-s}$ for any $s \le \ell/2$, it does not add a significant factor to the total time complexity.

## 9.1 A universal forgery attack based on the reduction of the image-set size

Directly matching the $2^s$ states computed by the MAC oracle on the challenge message with some states evaluated offline is too expensive. Therefore, we first compute and match the images of the states under iterations of a fixed function (as images match with higher probability than arbitrary states). Then, we use the initial matching of the images to efficiently match and recover an actual state that is computed by the MAC oracle on the challenge message. The 2-phase matching used in the attack resembles the approach used in [11,24], but the main difference is that the first phase of the matching does not exploit cycles in the functional graph. Moreover, the second phase of the matching is performed using an efficient binary search matching algorithm (Algorithm 1, whose pseudo-code is given in Appendix C). This algorithm can be simplified using a heuristic assumption on the number of nodes that need to be matched in the second phase (such an assumption was made explicitly in [11], and more implicitly in [6]). However, the analysis of Algorithm 1 is more rigorous and does not require any conjecture.

We denote the challenge message by $C$, and the first $\kappa$ blocks of $C$ by $C_{|\kappa}$. The details of the (first phase of the) universal forgery attack are as follows.

### Attack 7: Universal forgery attack using chains (first phase)

Complexity $\tilde{O}(2^{\ell-s})$, with $s \le \ell/7$ (min: $2^{6\ell/7}$)

Query length: $O(2^{2s})$
1. (online) Query the oracle with $2^s$ messages $M_i = C_{|i} \parallel [0]^{2^s-i}$. Denote the set of (unknown) final states of the chains by $Y$. Build an online diamond filter for all states in $Y$.

2. (offline) Compute a structure of chains containing a total of $2^{\ell-s}$ points. Each chain is extended until it cycles or collides with a previous chain. Consider the set $X$ of the $2^{2s}$-iterations of $f$ (namely images of $f^{2^{2s}}$ in the structure). According to Lemma 2, this set contains (no more than) about $2^{\ell-2s}$ distinct points. Build an online diamond filter for $X$.

3. (offline) Match all the points $x \in X$ with the $2^s$ points in $Y$.

4. (offline) For each match between $x \in X$ and an online state in $Y$ (obtained using $M_i$), use an additional matching algorithm to test the actual message $C_{|i}$: call the binary search matching algorithm (Algorithm 1) with:

* input message $M_i = C_{|i} \parallel [0]^{2^s-i}$;

* the tree rooted at $x$ (obtained by disconnecting the edge between $x$ and $f(x)$ from the graph and considering all the points that merge into $x$);

* and distance $2^s - i$.

If the algorithm returns a match $y'$, then with high probability the state obtained after processing $C_{|i}$ is equal to $y'$.

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

We efficiently detect a match between the challenge points (●) and the offline structure, by first matching $X$ (●) and $Y$ (●).

**Algorithm 1: Binary search matching**

**Inputs:** distance $d$, message $M$ of length $d' > d$ whose last $d$ blocks are zero, tree of chains computed with the zero block that merge into the root $x$

**Output:** node $y$ in the tree with distance $d$ to $x$ that is equal to the state reached after evaluating $M_{|d'-d}$ (NULL if $y$ does not exist)

1. Denote by $SIZE(u)$ the number of nodes in the tree whose root is $u$. Traverse the tree rooted at $x$ (backwards) for at most $d$ steps until a leaf or a collision is encountered:
* If a total of *d* steps were traversed, denote the node at distance *d* from *x* by *z*. Build a collision filter for *z* and test it on $M_{|d'|-d}$. If they match, return *y* = *z*, otherwise go to Step 2.

* If a leaf is encountered (before *d* steps were traversed), denote the current node by *z* and go to Step 2.

* If colliding states $z_1, z_2$ such that $f(z_1) = f(z_2) = z$ are encountered, then if $SIZE(z_1) \ge SIZE(x)/2$ continue traversing $z_1$ in Step 1. Otherwise, if $SIZE(z_2) \ge SIZE(x)/2$ continue traversing $z_2$ in Step 1.ª
Otherwise (sizes of trees rooted at $z_1$ and $z_2$ are small), let $d(z)$ denote the distance of $z$ from $x$. Build collision filters for $z_1$ and $z_2$ and test them on $M_{|d'-d(z_1)}$ (note that $d(z_1) = d(z_2) = d(z) + 1$). If there is no match, go to Step 2. Otherwise, assume without loss of generality that the match is with $z_1$. Call the algorithm recursively with input message $M_{|d'-d(z_1)}$, tree rooted at $z_1$, and distance $d' - d(z_1)$ (note that $SIZE(z_1) < SIZE(x)/2$).

2. Backtrack (by cutting off half of the tree): Denote by *z* the current node in the traversal. Let *z'* be the first ancestor of *z* (in the direction of the root *x*) for which there is a collision $f(z') = f(z'')$ for some *z''*. If there is no such *z'*, return NULL. Otherwise, call the algorithm recursively with input message *M*, tree rooted at *x* with *z'* cut off, and distance *d* (note that $SIZE(z') \ge SIZE(x)/2$).

*Analysis.* The offline structure of Step 2 contains $2^{\ell-s}$ distinct points, and thus according to the birthday paradox, it covers one of the $2^s$ points of the challenge with high probability. In this case, the attack will successfully recover the state of the covered point with high probability, since the $2^{2s}$-iterate of the covered point is also covered by the offline structure and will be matched in Step 3.<fnref n="5" />

The analysis of Algorithm 1 used in Step 4 is based on the following property: the size of the tree parameter is cut by at least half in every recursive call, where in each such recursive call we traverse at most $d \le 2^{2s}$ nodes and compute and test a small constant number of collision filters. Since the initial tree has at

<footnote>ª The algorithm can be easily generalized to deal with collisions between $t \ge 2$ states by analyzing all *t* nodes in the *t*-way collision (looking for a child whose subtree size is at least half of the total tree size, and building filters for all the children if required). As the maximal value of *t* in an *l*-bit random mapping is not expected to exceed *l*, such collisions only add (up to) a logarithmic factor to the total complexity of the algorithm.</footnote>

<footnote n="5">⁵ The only case in which the $2^{2s}$-iterate (denoted by *x*) of a covered point *y* is not covered by the offline structure, is when this iterate goes through the disconnected edge from *x* to $f(x)$ (namely, $f(x)$ is on a path from *y* to *x* whose length is at most $2^{2s}$). This can only occur if *x* is on a cycle with less than $2^{2s}$ elements. Such (small) cycles are expected to belong to (small) connected components whose total size is $O(2^{2 \cdot 2s}) = O(2^{4s})$ (see [9]). On the other hand, we evaluate a total of $2^{\ell-s}$ nodes offline, and since $2^{4s} \ll 2^{\ell-s}$ for $s \le \ell/7$, it is unexpected that the covered point *y* will belong to such a small component.</footnote>
most $2^\ell$ nodes, there are at most $\ell$ recursive calls in Algorithm 1 (for a single call in Step 4). The complexity of each recursive call is dominated by building a few offline collision filters, and therefore the complexity of Algorithm 1 is about $\ell \cdot 2^{\ell/2}$ (note that testing the filter online has complexity $2^{2s} < 2^{\ell/2}$, and traversing nodes in each recursive call has complexity at most $d \le 2^{2s} < 2^{\ell/2}$).

Since we have $2^s$ points in $Y$ and all the points in $X$ are distinct, there are at most $2^s$ matches in Step 3, and the time complexity of Step 4 is at most $\ell \cdot 2^{\ell/2} \cdot 2^s = \ell \cdot 2^{\ell/2+s}$.

Complexity.

$$
\begin{array}{ll}
\text{Step 1:} & 2^{2s+s/2+\ell/2} = 2^{\ell/2+5s/2} \\
\text{Step 3:} & s \cdot 2^{\ell-2s+s} = s \cdot 2^{\ell-s}
\end{array}
\qquad
\begin{array}{ll}
\text{Step 2:} & 2^{\ell-s} \\
\text{Step 4:} & \ell \cdot 2^{\ell/2+s}
\end{array}
$$

With $s \le \ell/7$, we have $\ell/2 + 5s/2 \le 6\ell/7 \le \ell - s$; the complexity of the first phase of the universal forgery attack is $\tilde{O}(2^{\ell-s})$. Since the second phase has a similar complexity, this is also the complexity of the full attack.

## 9.2 A universal forgery attack using collisions

In this attack, we devise a different algorithm which recovers one of the states computed during the MAC computation on the challenge message. The main idea here is to begin with a state-recovery attack in order to determine the value of some online states. Then, we use iterates of a fixed function on the challenge states and on the known points, and detect (online) collisions between the two sets of iterates. This allows to determine the values of several iterates of challenge states, and removes the need for online filters (that are required in the first matching phase of the previous attack). Next, we evaluate some states offline and execute the second matching phase on offline iterates that match the online challenge iterates. This allow to recover an actual challenge state (the second phase matching uses Algorithm 1 as the previous attack).

### Attack 8: Universal forgery attack using collisions (first phase)

Complexity $O(2^{\ell-s/2})$, with $s \le 2\ell/5$ (min: $2^{4\ell/5}$)

Query length: $O(2^s)$

1. (online) Query the oracle with $2^s$ messages $M_i = C_{|i} \parallel [0]^{2^{s+1}-i}$, and sort the tags.

2. (online) Execute state-recovery Attack 2 using messages of length $\min(2^s, 2^{\ell/3})$, and denote by $W$ a message of length $2^s$ whose last computed state is recovered.ª

3. (online) Query the oracle with $2^v$ messages $W_j = W \parallel [j] \parallel 0^{2^s-1}$, sort the tags, and locate $2^c$ collisions with the tags computed using the messages $M_i$. For each collision of tags between $M_i$ and $W_j$, the
state reached after $M_i$ is known, because the state reached after $W$ is already known. We denote the set of those states as $X$.

4. (offline) Compute a structure of chains containing a total of $2^{\ell-c}$ points. Each chain is extended until it cycles or collides with a previous chain.

5. (online) For each offline point in the structure $y$ which matches a point in $X$ (corresponding to $M_i$), call the binary search matching algorithm (Algorithm 1) with inputs:

* message $M_i$;

* the tree rooted at $y$ (obtained by disconnecting the edge between $y$ and $f(y)$) from the graph and considering all the points that merge into $y$);

* and distance $2^{s+1} - i$.

If the algorithm returns a match $y'$, then with high probability the state obtained after processing $C_{|i}$ is equal to $y'$.

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

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

We match the known points in $X(\bullet)$ and $Y(\bullet)$ in order to detect a match between the challenge points ($\bullet$) and the offline structure.

*Analysis.* In Step 3 of the attack, we find $2^c$ collisions between pairs of chains, where the prefix of one chain in each pair is some challenge prefix $C_{|i}$. Thus, the $2^c$ collisions cover $2^c$ such challenge prefixes, and moreover, the offline structure computed in Step 4 contains $2^{\ell-c}$ points. Thus, according to the birthday paradox, with high probability the offline structure covers one of the states obtained after the computation of such a prefix $C_{|i}$. Since iterate $2^{s+1} - i$ of $C_{|i}$ is also covered by the offline structure,^6 then the state corresponding to $C_{|i}$ will be recovered in Step 5.

In order to calculate the value of $c$, note that the online structure computed in Step 1 contains $2^s$ chains, each of length at least $2^s$, and thus another arbitrary chain of length $2^s$ collides with one of the chains in this structure at the same offset with probability of about $2^{2s-\ell}$ (see Lemma 1). Since the

<footnote>a In case $s > \ell/3$, we first recover the last computed state of a message of size $2^{\ell/3}$, and then complement it arbitrarily to a length of $2^s$.</footnote>

<footnote>^6 This occurs with high probability, and can be shown by analyzing the cycle structure of the graph as in the previous attack.</footnote>
structure computed in Step 3 contains $2^v$ such chains, the expected number of detected collisions between the structures is $2^c = 2^{2s+v-l}$, i.e., $c = 2s + v - l$.

In Step 5, we call Algorithm 1 at most $2^c$ times (at most once for each online collision), and each invocation has complexity $l \cdot 2^{l/2}$ (the analysis of Algorithm 1 is essentially the same as in the previous attack). In total, the complexity of Step 5 is $l \cdot 2^{c+l/2} = l \cdot 2^{2s+v-l/2}$.

$$
\begin{array}{ll}
\text{Step 1:} & 2^{2s} \\
\text{Step 3:} & 2^{v+s} \\
\text{Step 5:} & l \cdot 2^{2s+v-l/2}
\end{array}
\qquad
\begin{array}{ll}
\text{Step 2:} & \max(2^{l-s}, 2^{2l/3}) \\
\text{Step 4:} & 2^{l-c} = 2^{2l-2s-v}
\end{array}
$$

We balance steps 3 and 4 by setting $v + s = 2\ell - 2s - v$, or $v = \ell - 3s/2$. This yields $c = s/2$, a complexity of $2^{\ell-s/2}$ for steps 3 and 4, and $2^{\ell/2+s/2}$ for Step 5. This gives a total complexity of $O(2^{\ell-s/2})$ for any $s \le 2\ell/5$.

10 Conclusions and Open Problems

In this paper, we provided improved analysis of HMAC and similar hash-based
MAC constructions. More specifically, we devised the first state-recovery attacks
for HMAC with hash functions based on the HAIFA mode, and provided improved
tradeoffs between the message length and the complexity of state-recovery
attacks for HMAC with Merkle-Damgård hash functions. Finally, we presented
the first universal forgery attacks which can be applied with short queries to the
MAC oracle. Since it is widely deployed, our attacks have many applications
to HMAC constructions used in practice, built using GOST, the SHA family, and
other concrete hash functions.

We give a more concrete application of some of these results in Section 8,
with a key-recovery attack against HMAC with the new Russian standard
GOST R 34.11-2012. In particular this attack requires a key-recovery attack
against HMAC with HAIFA hash functions, and improved tradeoffs for short
messages.

Our results raise several interesting future work items such as devising
efficient universal forgery attacks on HMAC built using hash functions based
on the HAIFA mode, or proving that this mode provides resistance against
such attacks (perhaps under certain natural assumptions). At the same time,
it would be useful to find additional applications of our algorithms to related
cryptosystems (such as various modes of operation) where some level of security
beyond the birthday bound is required.

References

1. Aumasson, J.P., Henzen, L., Meier, W., Phan, R.C.W.: SHA-3 proposal BLAKE. Submission to NIST (2008/2010), http://131002.net/blake/blake.pdf
2. Aumasson, J.P., Neves, S., Wilcox-O'Hearn, Z., Winnerlein, C.: BLAKE2: Simpler, Smaller, Fast as MD5. In: Jr., M.J.J., Locasto, M.E., Mohassel, P., Safavi-Naini, R. (eds.) ACNS. Lecture Notes in Computer Science, vol. 7954, pp. 119-135. Springer (2013)

3. Bellare, M.: New Proofs for. In: Dwork, C. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 4117, pp. 602-619. Springer (2006)

4. Bellare, M., Canetti, R., Krawczyk, H.: Keying Hash Functions for Message Authentication. In: Koblitz, N. (ed.) CRYPTO. Lecture Notes in Computer Science, vol. 1109, pp. 1-15. Springer (1996)

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

6. Dinur, I., Leurent, G.: Improved Generic Attacks against Hash-Based MACs and HAIFA. In: Garay and Gennaro [10], pp. 149-168

7. Dolmatov, V., Degtyarev, A.: GOST R 34.11-2012: Hash Function. RFC 6986 (Informational) (Aug 2013), http://www.ietf.org/rfc/rfc6986.txt

8. Ferguson, N., Lucks, S., Schneier, B., Whiting, D., Bellare, M., Kohno, T., Callas, J., Walker, J.: The Skein hash function family. Submission to NIST (2008/2010), http://skein-hash.info

9. Flajolet, P., Odlyzko, A.M.: Random Mapping Statistics. In: Quisquater, J., Vandewalle, J. (eds.) Advances in Cryptology - EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques, Houthalen, Belgium, April 10-13, 1989, Proceedings. Lecture Notes in Computer Science, vol. 434, pp. 329-354. Springer (1989)

10. Garay, J.A., Gennaro, R. (eds.): Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I, Lecture Notes in Computer Science, vol. 8616. Springer (2014)

11. Guo, J., Peyrin, T., Sasaki, Y., Wang, L.: Updates on Generic Attacks against HMAC and NMAC. In: Garay and Gennaro [10], pp. 131-148

12. Guo, J., Sasaki, Y., Wang, L., Wang, M., Wen, L.: Equivalent Key Recovery Attacks Against HMAC and NMAC with Whirlpool Reduced to 7 Rounds. 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. 571-590. Springer (2014)

13. Guo, J., Sasaki, Y., Wang, L., Wu, S.: Cryptanalysis of HMAC/NMAC-Whirlpool. In: Sako and Sarkar [25], pp. 21-40

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

15. Kelsey, J., Kohno, T.: Herding Hash Functions and the Nostradamus Attack. In: Vaudey, N. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 4004, pp. 183-200. Springer (2006)

16. Kelsey, J., Schneier, B.: Second Preimages on n-Bit Hash Functions for Much Less than 2ⁿ Work. In: Cramer, R. (ed.) EUROCRYPT. Lecture Notes in Computer Science, vol. 3494, pp. 474-490. Springer (2005)

17. Kortelainen, T., Kortelainen, J.: On Diamond Structures and Trojan Message Attacks. In: Sako and Sarkar [25], pp. 524-539

18. Leurent, G., Peyrin, T., Wang, L.: New Generic Attacks Against Hash-based MACs. IACR Cryptology ePrint Archive 2014, 406 (2014), http://eprint.iacr.org/2014/406

19. Leurent, G., Peyrin, T., Wang, L.: New Generic Attacks against Hash-Based MACs. In: Sako and Sarkar [25], pp. 1-20

20. Love, E.R.: Some Logarithm Inequalities. The Mathematical Gazette 64(427), 55-57 (1980), http://www.jstor.org/stable/3615890

21. Naito, Y., Sasaki, Y., Wang, L., Yasuda, K.: Generic State-Recovery and Forgery Attacks on ChopMD-MAC and on NMAC/HMAC. In: Sakiyama, K., Terada, M. (eds.) IWSEC. Lecture Notes in Computer Science, vol. 8231, pp. 83-98. Springer (2013)

22. van Oorschot, P.C., Wiener, M.J.: Parallel Collision Search with Cryptanalytic Applications. J. Cryptology 12(1), 1-28 (1999)

23. Peyrin, T., Sasaki, Y., Wang, L.: Generic Related-Key Attacks for HMAC. In: Wang, X., Sako, K. (eds.) ASIACRYPT. Lecture Notes in Computer Science, vol. 7658, pp. 580-597. Springer (2012)
24. Peyrin, T., Wang, L.: Generic Universal Forgery Attack on Iterative Hash-Based MACs. 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. 147-164. Springer (2014)

25. 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 II, Lecture Notes in Computer Science, vol. 8270. Springer (2013)

26. Tsudik, G.: Message authentication with one-way hash functions. SIGCOMM Comput. Commun. Rev. 22(5), 29-38 (Oct 1992)

27. Yasuda, K.: "Sandwich" Is Indeed Secure: How to Authenticate a Message with Just One Hashing. In: Pieprzyk, J., Ghodosi, H., Dawson, E. (eds.) ACISP. Lecture Notes in Computer Science, vol. 4586, pp. 355-369. Springer (2007)

A The Second Phase of the Universal Forgery Attacks [24]

In this section we describe the second phase of our universal forgery attacks, which is identical to the second phase of the attack of [24]. Recall the we are given a challenge message $C = m_1 \parallel m_2 \parallel \dots \parallel m_{2^s}$ of length $2^s$ blocks and our goal is to predict the tag of $C$ by querying the MAC oracle with queries that are different from $C$. We denote the internal states computed by the MAC oracle on the challenge $C$ by $y_0, y_1, \dots, y_{2^s}$. In the first phase of the attack, we recover one of these internal states, which we denote by $y_p$. We assume that $p \le 2^{s-1}$. This can be assured by running the first phase of the attack only on the first half of the blocks of $C$, which results in a small constant penalty in the complexity of the attack.

In the second phase of the attack we use a second-preimage attack on long messages in order to generate a different message $C'$ which has the same tag as the challenge. The second-preimage attack is based on the one by Kelsey and Schneier [16]. The attack uses a structure known as an $(i, j)$-expandable message (for integers $i < j$), proposed in [16]. An $(i, j)$-expandable message is composed of an arbitrary initial state $x$ and a final state $z$ where for each integer $d$ such that $i \le d \le j$, there is an efficiently computable message of $d$ blocks $M_d = m'_1 \parallel m'_2 \parallel \dots \parallel m'_d$ that links $x$ to $z$, namely, $z = h(...h(h(x, m'_1), m'_2) \dots, m'_d)$. Assuming that $i \le l/2$ (which is the case in our attack), an $(i, 2^i)$-expandable message can be constructed from any initial state $x$ in complexity of $\ell \cdot 2^{\ell/2}$. The details of how to construct this structure are found in [16].

<caption>Algorithm 2: Universal Forgery Attack (second phase)</caption>

Complexity $\tilde{O}(2^{\ell-s})$, with $s \le \ell/2$

1. (offline) Compute the states $y_p, y_{p+1}, \dots, y_{p+2^{s-1}}$ and store them in a sorted table.

2. (offline) Build an $(s-1, 2^{s-1})$-expandable message starting from $y_p$ and denote its final state by $z$.

3. (offline) For about $2^{\ell-s}$ values of the single-block $[i]$, compute $h(z, [i])$ and search the sorted table for $y_j$ such that $y_j = h(z, [i])$ and $j \ge p+s$. Once such $i$ and $j$ are found, continue to the next step.

4. (online) Let $M_{j-1-p}$ be the message of $j-1-p$ blocks that links $y_p$ to $z$, computed from the expandable message. Let $C' = C_p \parallel M_{j-p-1} \parallel [i] \parallel m_{j+1} \parallel m_{j+2} \parallel \dots \parallel m_{2^s}$ be the 2$^s$-block message computed by concatenating the p-block prefix of $C$ with $M_{j-p-1} \parallel [i]$ and the suffix of $2^s-j$ blocks of $C$. Query the MAC oracle with $C'$ and denote the result by $T$.

5. (offline) Output $T$ as the tag for $C$.
Complexity.

<table><tr><td>Step 1:</td><td>2<sup>s-1</sup></td><td>Step 2:</td><td>l &middot; 2<sup>l/2</sup></td></tr><tr><td>Step 3:</td><td>2<sup>l-s</sup></td><td>Step 4:</td><td>2<sup>s</sup></td></tr><tr><td>Step 5:</td><td>2<sup>s</sup></td><td></td><td></td></tr></table>

For $s \le l/2$ the total complexity is $\tilde{O}(2^{l-s})$ as required.

## B Concrete Complexity of HMAC-Streebog Key-Recovery

In this section we calculate with better precision (taking into account constants and logarithmic factors) an upper bound on the expected complexity of Attack 6 (applied to Streebog with $l = 512$). While the analysis can be refined to give slightly better complexity, our calculations demonstrate that the constants involved in our attacks are indeed small.

Attack 6 is dominated by Step 0, which uses Attack 5, with $s = l/10$. Therefore, we start with a concrete analysis of Attack 5.

**Attack 5.** The most expensive steps are 2 and 4, where we match two sets by building and using a diamond filter. In order to optimize the attack, we use parameters $c_1 = l/2 - s$ and $c_2 = l/2 + \alpha$ for a small constant $\alpha$ (e.g. $\alpha = 4$), and run steps 1 and 3 until we have the required number of collisions ($2^{c_1}$ and $2^{c_2}$).

The expected value of $u$ required to generate $2^{c_1}$ collisions in Step 1 is roughly $u = (c_1 + l - s + 1)/2$, accounting for the factor $1/2$ in the number of message pairs. Similarly, the expected value of $t$ in Step 3 is $t = (c_2 + l - s + 1)/2$. This results in a complexity that is still negligible compared to steps 2 and 4, in spite of the small constants added ($2^{3l/4+1/2}$ for Step 1 and $2^{3l/4+(s+\alpha+1)/2}$ for Step 3).

With these parameters the online diamond filter for the set of size $2^{c_1}$ will have depth $[c_1]$, and require less than $8 \frac{e}{e-1} 2^{c_1/1+l/2}$ evaluations of the MAC (following [17]). Since each query has $2^s$ blocks, the total complexity is $8 \frac{e}{e-1} 2^{s+c_1/2+l/2} < 2^{3l/4+s/2+3.7}$ for Step 2.

Finally, in Step 4, we use only collisions with an offset $d$ such that $d \ge 2^{s-1}$, to simplify the analysis (we keep about $2^{c_2-1} = 2^{l/2+3}$ offline collisions). Following Lemma 4, we fix an offline collision $\hat{x}$ (with preimages $x_d$ and $x'_d$) and we evaluate the probability that a random pair of chains $y_0, y'_0$ reaches the same collision, under the condition that $y_0, y'_0$ collide at the same offset $d$. Let $A$ denotes the event that $y_0, y'_0$ collide on $\hat{x}$ and $B$ the event that they collide at offset $d$ on an arbitrary point (all collisions are same-offset collisions). We first evaluate the probability that the chains starting at $y_0$ and $y'_0$ reach $x_d$ or $x'_d$, and then the probability that $y_0, y'_0$ collide on $\hat{x}$ (namely $\text{Pr}[A]$).

$$ \begin{align*} \Pr[y_0 \not\to x_d] &\le (1 - 2^{-l}) 2^{s-1} \le e^{-2^{s-1-l}} \\ \Pr[y_0 \rightsquigarrow x_d] &= 1 - \Pr[y_0 \not\to x_d] \ge 1 - e^{-2^{s-1-l}} \approx 2^{s-1-l} \\ \Pr[A] &\ge \Pr[y_0 \rightsquigarrow x_d] \cdot \Pr[y'_0 \rightsquigarrow x'_d] + \Pr[y'_0 \not\to x_d] \cdot \Pr[y_0 \not\to x'_d] \ge 2^{2s-2l-1} \end{align*} $$

We have $\Pr[B] \le 2^{-l}$, hence $\Pr[A|B] = \Pr[A \cap B]/\Pr[B] \ge 2^{2s-l-1}$. Therefore, the matching of Step 4 is expected to succeed after less than $2^{l-2s+1}$ attempts on average (the actual complexity without the restriction $d \ge 2^{s-1}$ is slightly smaller). Since each match requires to follow a path in a diamond of length $c_1$, the total complexity is less than $c_1 \cdot 2^{l-2s+1} \le l \cdot 2^{l-2s}$ on average. This results in the following complexities:

<table><tr><td>Step 1:</td><td>2<sup>3l/4+1/2</sup></td><td>Step 2:</td><td>2<sup>3l/4+s/2+3.7</sup></td></tr><tr><td>Step 3:</td><td>2<sup>3l/4+s/2+(α+1)/2</sup></td><td>Step 4:</td><td>l &middot; 2<sup>l-2s</sup></td></tr></table>

In particular, with $l = 512$ and $s = 54$, we obtain a complexity of $2^{415.1}$.
Attack 6. Let us now examine the full key-recovery attack, using a short message $M_1$ of length $2^s$. We run Step 2 until we gather $2^{2\ell/5}$ collisions, which requires about $2^{7\ell/10+1/2}$ calls to the MAC on average. Similarly, we run Step 3 until we recover the key; this should require $2^{3\ell/5}$ collisions on average, i.e. $2^{4\ell/5+1/2}$ evaluations of the compression function.

Since Step 0 still dominates, we use $s = 54$ to minimize the complexity:

Step 0: $2^{415.1}$ Step 1: $\ell \cdot 2^{\ell/2} = 2^{247}$

Step 2: $2^{s+7\ell/10+1/2} = 2^{412.9}$ Step 3: $2^{4\ell/5+1/2} = 2^{410.1}$

Therefore, the expected complexity is less than $2^{416}$.

Finally, recall from Section 2 that our attacks use a modified scheme $\text{MAC}_2(K, M) = \text{MAC}_1(K, M \parallel [0]) \parallel \text{MAC}_1(K, M \parallel [1])$, which results in a multiplicative penalty of at most 2. Hence, the total expected complexity is less than $2^{417}$.
C Pseudo-code

<table><caption>**Algorithm 1 Binary search matching**</caption>
  <tbody>
    <tr>
      <td>function SEARCH(x, d)</td>
      <td>▷ The message is a global parameter</td>
    </tr>
    <tr>
      <td>if |NEXT(x) = 0| then</td>
      <td></td>
    </tr>
    <tr>
      <td>return NULL</td>
      <td></td>
    </tr>
    <tr>
      <td>end if</td>
      <td></td>
    </tr>
    <tr>
      <td>z &larr; x</td>
      <td></td>
    </tr>
    <tr>
      <td>i &larr; d</td>
      <td></td>
    </tr>
    <tr>
      <td>while i &gt; 0 do</td>
      <td></td>
    </tr>
    <tr>
      <td>if |NEXT(z) = 0| then</td>
      <td></td>
    </tr>
    <tr>
      <td>return CUT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>else if |NEXT(z) = 1| then</td>
      <td></td>
    </tr>
    <tr>
      <td>z &larr; NEXT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>else if |NEXT(z) = 2| then</td>
      <td></td>
    </tr>
    <tr>
      <td>z<sub>1</sub>, z<sub>2</sub> &larr; NEXT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>if SIZE(z<sub>1</sub>) &gt; SIZE(x)/2 then</td>
      <td></td>
    </tr>
    <tr>
      <td>z &larr; z<sub>1</sub></td>
      <td></td>
    </tr>
    <tr>
      <td>else if SIZE(z<sub>2</sub>) &gt; SIZE(x)/2 then</td>
      <td></td>
    </tr>
    <tr>
      <td>z &larr; z<sub>2</sub></td>
      <td></td>
    </tr>
    <tr>
      <td>else</td>
      <td></td>
    </tr>
    <tr>
      <td>if TEST(z<sub>1</sub>) then</td>
      <td>▷ Compare z<sub>1</sub> to a message node using a filter</td>
    </tr>
    <tr>
      <td>return SEARCH(z<sub>1</sub>, i)</td>
      <td>▷ We have SIZE(z<sub>1</sub>) &le; SIZE(x)/2</td>
    </tr>
    <tr>
      <td>else if TEST(z<sub>2</sub>) then</td>
      <td>▷ Compare z<sub>2</sub> to a message node using a filter</td>
    </tr>
    <tr>
      <td>return SEARCH(z<sub>2</sub>, i)</td>
      <td>▷ We have SIZE(z<sub>2</sub>) &le; SIZE(x)/2</td>
    </tr>
    <tr>
      <td>else</td>
      <td></td>
    </tr>
    <tr>
      <td>return CUT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>end if</td>
      <td></td>
    </tr>
    <tr>
      <td>end if</td>
      <td></td>
    </tr>
    <tr>
      <td>else if |NEXT(z) = 3| then</td>
      <td></td>
    </tr>
    <tr>
      <td>...</td>
      <td>▷ Handling a t &gt; 2-collision is similar</td>
    </tr>
    <tr>
      <td>end if</td>
      <td></td>
    </tr>
    <tr>
      <td>i &larr; i &minus; 1</td>
      <td></td>
    </tr>
    <tr>
      <td>end while</td>
      <td></td>
    </tr>
    <tr>
      <td>if TEST(z) then</td>
      <td></td>
    </tr>
    <tr>
      <td>return z</td>
      <td></td>
    </tr>
    <tr>
      <td>else</td>
      <td></td>
    </tr>
    <tr>
      <td>return CUT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>end if</td>
      <td></td>
    </tr>
    <tr>
      <td>end function</td>
      <td></td>
    </tr>
    <tr>
      <td>function CUT(z)</td>
      <td></td>
    </tr>
    <tr>
      <td>while |NEXT(PREV(z))| = 1 do</td>
      <td></td>
    </tr>
    <tr>
      <td>z &larr; NEXT(PREV(z))</td>
      <td></td>
    </tr>
    <tr>
      <td>end while</td>
      <td></td>
    </tr>
    <tr>
      <td>Remove z subtree</td>
      <td>▷ We have SIZE(z) &ge; SIZE(x)/2</td>
    </tr>
    <tr>
      <td>return SEARCH(x, d)</td>
      <td></td>
    </tr>
    <tr>
      <td>end function</td>
      <td></td>
    </tr>
  </tbody>
</table>
# On the Practical (In-)Security of 64-bit Block Ciphers

## Collision Attacks on HTTP over TLS and OpenVPN

Karthikeyan Bhargavan

Inria, France

karthikeyan.bhargavan@inria.fr

Gaëtan Leurent

Inria, France

gaetan.leurent@inria.fr

## ABSTRACT

While modern block ciphers, such as AES, have a block size of at least 128 bits, there are many 64-bit block ciphers, such as 3DES and Blowfish, that are still widely supported in Internet security protocols such as TLS, SSH, and IPsec. When used in CBC mode, these ciphers are known to be susceptible to collision attacks when they are used to encrypt around $2^{32}$ blocks of data (the so-called birthday bound). This threat has traditionally been dismissed as impractical since it requires some prior knowledge of the plaintext and even then, it only leaks a few secret bits per gigabyte. Indeed, practical collision attacks have never been demonstrated against any mainstream security protocol, leading to the continued use of 64-bit ciphers on the Internet.

In this work, we demonstrate two concrete attacks that exploit collisions on short block ciphers. First, we present an attack on the use of 3DES in HTTPS that can be used to recover a secret session cookie. Second, we show how a similar attack on Blowfish can be used to recover HTTP BasicAuth credentials sent over OpenVPN connections. In our proof-of-concept demos, the attacker needs to capture about 785GB of data, which takes between 19-38 hours in our setting. This complexity is comparable to the recent RC4 attacks on TLS: the only fully implemented attack takes 75 hours. We evaluate the impact of our attacks by measuring the use of 64-bit block ciphers in real-world protocols. We discuss mitigations, such as disabling all 64-bit block ciphers, and report on the response of various software vendors to our responsible disclosure of these attacks.

## 1. INTRODUCTION

Internet protocols such as TLS [13], SSH [34], and IPsec [18] are *agile*, in the sense that they are designed to support a wide variety of *ciphersuites*: combinations of key exchange protocols, encryption schemes, authentication modes, etc. Each protocol implementation may choose to support a different subset of ciphersuites, but two implementations can still interoperate if they can negotiate a common cipher-

<figure><img src="image_130.png" /><figcaption>**Figure 1:** The Beastly attacker model for HTTPS: A network attacker injects JavaScript on some window in the user's browser, which then makes cross-origin HTTPS requests to a target website. The browser attaches a secret cookie or HTTP BasicAuth password to authenticate each request. The attacker observes the encrypted traffic stream and tries to recover the secret.</figcaption></figure>

suite. When it works well, protocol agility can enable a graceful transition from old cryptographic algorithms to new ones. A server can, for example, offer AES-GCM to modern clients while still supporting legacy ciphers like 3DES for older clients that have not yet been upgraded. However, a negative consequence of agility is that old ciphers may never be removed, resulting in implementations that support a few strong modern ciphers, followed by a long tail of obsolete ciphers that are still supported for backwards compatibility, but are known to be cryptographically weak. For example, the OpenSSL library supports five versions of TLS and hundreds of ciphersuites, even though many of these ciphersuites include weak algorithms like RC4 and MD5.

There are several reasons why practitioners do not consider theoretical weaknesses in cryptographic to be sufficient for their removal from mainstream protocols. First, even if an obsolete primitive is supported, it will typically only be negotiated if one of the parties does not support a modern alternative, in which case, the obsolete cipher is still better than nothing. Second, the attack may not be applicable to the way the primitive is used in the protocol, or it may require too much computation to be considered practical. Third, the attack may require special knowledge about the structure or the content of the plaintext stream which may be difficult to obtain in general. Consequently, protocol implementations tend to support legacy ciphers until a concrete attack is demonstrated in a common usage of the protocol.

Publication rights licensed to ACM. ACM acknowledges that this contribution was authored or co-authored by an employee, contractor or affiliate of a national government. As such, the Government retains a nonexclusive, royalty-free right to publish or reproduce this article, or to allow others to do so, for Government purposes only.

CCS '16, October 24-28, 2016, Vienna, Austria.

© 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM.

ACM ISBN 978-1-4503-4139-4/16/10...$15.00

DOI: http://dx.doi.org/10.1145/2976749.2978423
**Attacks on Legacy Crypto.** A series of recent attacks on TLS have conclusively shown that this line of defense for legacy ciphers is fatally flawed. Leaving old protocol versions and obsolete cryptographic algorithms enabled can lead to devastating attacks, such as BEAST [15] (on CBC encryption in TLS 1.0), CRIME [28] (on TLS compression), Lucky13 [4] (on CBC padding in TLS 1.2), POODLE [11] (on CBC padding in SSL 3.0), RC4 NOMORE [3, 19, 32] (on keystream biases in RC4), FREAK [9] (on export-grade RSA keys), Logjam [2] (on export-grade Diffie-Hellman groups), SLOTH [10] (on MD5 signatures), and DROWN [5] (on RSA-PKCS#1v1.5 encryption in SSL 2.0).

These attacks follow a common pattern. Each attack is based on a classic cryptographic weakness that was known to cryptographers for years or even decades in advance, but had not been demonstrated in real-world TLS scenarios. So these works showed that with modern network speeds and computing power, the computational effort required to exploit the theoretical weakness is feasible even for academic researchers. Furthermore, many of these attacks (e.g. BEAST, CRIME, RC4 NOMORE) can be made more efficient by relying on a new HTTPS attacker model introduced by BEAST. Figure 1 depicts this Beastly attacker model, where a network attacker uses JavaScript to implement an adaptive chosen- plaintext adversary who can mix in his plaintext with the user's secret values, and then use his network vantage point to actively or passively attack the ciphertext.

The final element of each attack is finding clients and servers who are willing to negotiate the legacy cipher. Some of the attacked algorithms (e.g. RC4) and protocol versions (e.g. SSL 3.0) were highly popular before the attack and have since been deprecated. Other weak algorithms (e.g. export ciphers) and versions (e.g. SSL 2.0) had already been deprecated years ago and were never expected to be negotiated between modern clients and servers. Surprisingly however, in many cases the attacker is able to force the negotiation of a weak algorithm via a downgrade attack by exploiting protocol flaws (e.g. Logjam, SLOTH) or implementation bugs (e.g. FREAK, DROWN). One lesson to take from these downgrade attacks is that relying on the negotiation protocol to avoid legacy ciphers is error-prone and dangerous. When a concrete attack against a legacy cipher is discovered, the only safe mitigation is to fully remove the weak cipher from all implementations.

These previous attacks evaluated a variety of obsolete cryptographic constructions and provided enough evidence of their dangers for them to be disabled in popular implementations. We believe that it is important for the research community to be vigilant and to continue to investigate the strength of the weakest ciphers still supported by mainstream protocols. For example, the attacks on RC4 have resulted in RC4 being removed as the default fallback cipher for TLS implementations, and this role has now fallen to 3DES, which is a 28 year old 64-bit block cipher with known weaknesses. However, the practical security of 64-bit block ciphers as used in TLS and other protocols has not been previously studied. This work aims to address this gap and to provide concrete attacks and firm guidance on the use of such ciphers.

**Collision Attacks on 64-bit Block Ciphers.** The security of a block cipher is often reduced to the key size $k$: the best attack should be the exhaustive search of the key, with complexity $2^k$. However, the block size $n$ is also an important security parameter, defining the amount of data that can be encrypted under the same key. This is particularly im-

portant when using common modes of operation: we require block ciphers to be secure with up to $2^n$ queries, but most modes of operation (e.g. CBC, CTR, GCM, OCB, etc.) are unsafe with more than $2^{n/2}$ blocks of message (the so-called birthday bound). In particular, when these many blocks are encrypted under a key in CBC mode, the probability of collisions between two ciphertext blocks becomes significant, and each ciphertext collision reveals the XOR of the two corresponding plaintext blocks from the stream. Consequently, if the attacker can guess one of the plaintext blocks, he can recover the plaintext in the other block. While this attack is well-known to researchers [30, 25], it is often disregarded by practitioners because it require known plaintext, and reveals only a few bits of a large datastream.

With a modern block cipher with 128-bit blocks such as AES, the birthday bound corresponds to 256 EB ($2^{68}$ bytes). While this is leaves a safe margin for common uses of cryptography today, the resulting security is still lower than could be expected of 128-bit security and might be an issue in the future. As a point of comparison, Google is estimated to store around 16 EB ($2^{64}$ bytes), and the global Internet traffic is expected to reach 1 ZB ($2^{70}$ bytes) per year in 2016.

More strikingly, the birthday bound corresponds to only 32 GB for a block cipher with 64-bit blocks, and there are many real-world protocol scenarios in which this amount of data may be sent under a 64-bit cipher: e.g. 3G telephone connections (UMTS), which are encrypted with KASUMI, OpenVPN tunnels, which uses Blowfish as the default cipher, and Internet standards like TLS, SSH, and IPsec that use 3DES and Blowfish as legacy ciphers for interoperability. In all these scenarios, 32 GB of data can be transferred in less than one hour with a fast connection.

More recently, 64-bit ciphers have become common in the field of lightweight cryptography for applications, such as embedded systems and smart devices, where resources are too constrained to use conventional block ciphers. For instance, PRESENT [12] and HIGHT [20] have been standardized by ISO recently (in ISO/IEC 29192 and ISO/IEC 18033-3, respectively).

**Our Results.** In this work, we study the concrete impact of birthday attacks against 64-bit block-ciphers as used in popular protocols. We present the first concrete attacks based on ciphertext collisions on mainstream Internet protocols.

We focus on two concrete use cases. First, we consider the use of OpenVPN to secure HTTP connections between a web browser and a website, where the website asks the user for HTTP BasicAuth (user/password) authentication. OpenVPN uses Blowfish in CBC mode by default, and we show how one can use the Beastly attacker scenario to generate a lot of traffic including the BasicAuth in every request, until collisions collisions in the Blowfish ciphertext reveal the BasicAuth token (i.e. the password). We demonstrate a proof-of-concept attack between a Firefox client and an nginx server connected via OpenVPN. The attack requires about 785GB, which takes 19 hours in our setting to recover the 16-byte authorization token.

Second, we consider the use of TLS to secure HTTP connections between a browser and an HTTPS website that sets secure session cookies on the browser. We find that 3DES is supported by nearly 90% of HTTPS servers and by all mainstream TLS clients. In practice, however, 3DES is less preferred than AES and negotiated by only 1-2% of
HTTPS connections. For such connections, we demonstrate an attack, again using the Beastly attacker setup, that can recover the secret 16-byte session cookie sent by the browser with every HTTPS request to the target server. We demonstrate the attack between a Firefox browser and an IIS 6.0 server (Windows Server 2003 R2 SP2), both in their default up-to-date configuration. This attack also requires 785GB, which takes 38 hours in our setting.

Our attacks demonstrate that collision-based attacks on 64-bit block ciphers are practically exploitable. We suggest two mitigations for the attack. Considering the low negotiation probability of 3DES in TLS, we recommend disabling it in popular clients and servers. For protocols where 64-bit ciphers cannot yet be deprecated, we recommend using strict rekeying limits to mitigate the attack. In response to our attacks, mainstream TLS libraries, web browsers, and OpenVPN have begun implementing these mitigations.

**Outline.** Section 2 provides background on collision attacks on block ciphers and estimates their success probability under various conditions. Section 3 investigates the usage of 64-bit ciphers in various Internet protocols, and specifically in HTTPS. Section 4 shows how block cipher collisions in the encrypted stream can be used to attack HTTP. Section 4.4 and 4.5 describe our proof-of-concept attacks on OpenVPN and HTTPS, respectively. Section 5 discusses the impact of our attacks and their mitigations.

## 2. COLLISION ATTACKS ON BLOCK CIPHERS

Block ciphers like AES and 3DES are widely used for symmetric encryption in security protocols. Mathematically, a block cipher with a $\kappa$-bit key and $n$-bit blocks defines of family of permutations of $n$-bit strings, indexed by the key. The main security notion is that a block cipher should behave like a pseudo-random permutation (PRP) family: the block cipher $E_k$ with a random key $k$ should be hard to distinguish from a random permutation.

Block ciphers operate on blocks of fixed size, $n$ bits, usually with $n = 64$ (DES, 3DES, Blowfish, IDEA, KASUMI, PRESENT, ...) or $n = 128$ (AES, Camellia, Twofish, Serpent, SEED, ...). In order to deal with arbitrary-length messages, they are used within a mode of operation. A mode divides the message $M$ into $n$-bit blocks $m_i$, and process the blocks one by one through the block cipher $E$ with various chaining rules, to produce ciphertext blocks $c_i$ and/or an authentication tag $\tau$. Several modes have been widely studied and standardized [16] for encryption (CBC, CFB, OFB, CTR), authentication (CBC-MAC, PMAC) and authenticated encryption (OCB, CCM, GCM).

### 2.1 Security at the Birthday Bound

While block ciphers are required to resist any attack with up to $2^n$ data and $2^\kappa$ time, most modes of operation are only proven secure up to $2^{n/2}$ blocks of plaintext, a limit that is commonly called the *birthday bound*. Indeed, there are attacks matching this limit. In CBC mode, the probability of collisions between two $n$-bit ciphertext blocks becomes significant after $2^{n/2}$ blocks because of the birthday paradox. Rogaway summarizes the situation as follows [30, page 36]:

> In general, unless special efforts are taken, almost any mode of operation based on an $n$-bit block-

<figure><img src="image_131.png" /><figcaption>Figure 2: CBC mode</figcaption></figure>

> cipher will admit attacks that employ $\sigma = 2^{n/2}$ blocks. [...]

> Do birthday-bound attacks on CBC, CFB, and OFB actually matter? They are of relatively little concern when the blockcipher has a blocksize of $n = 128$ bits, but the attacks can be a serious concern when employing a blockcipher of $n = 64$ bits, requiring relatively frequent rekeying to keep $\sigma \ll 2^{32}$.

More recently, McGrew investigated plaintext recovery attacks on 64-bit ciphers in CBC, CFB, and CTR modes. He studied the mount of information leakage by assuming that the attacker can observe all the ciphertext in an encrypted stream and he has some (incomplete) knowledge of the plaintext [25]. This theoretical analysis resulted in new security recommendations for IPsec [26], but they did not trigger any significant changes in mainstream deployments of 64-bit ciphers in IPsec, TLS, or SSH. Arguably the main reason for the limited impact of these attacks is that they were never implemented against a popular protocol under real-world conditions.

Following McGrew, we explain theoretical attacks against the CBC and CTR modes (the two most widely used encryption modes) in more detail below. In the rest of the paper, we will show that these attacks can be exploited to mount concrete attacks on HTTP over TLS and OpenVPN.

### 2.2 Plaintext recovery attack against CBC

The CBC mode is one of the oldest encryption modes, and still widely used. The message $M$ is divided into blocks $m_i$, $0 \le i < \ell$ (see Figure 2) and is encrypted as:

$$c_i = E_k(m_i \oplus c_{i-1}),$$

where $c_{-1}$ is an initialization value usually denoted as IV. For simplicity, here we assume that all message sizes are a multiple of the block size.

When encrypting a sequence of messages $M^{(j)}$, each message should be encrypted with a fresh random IV $c_{-1}^{(j)}$. It is important that the IV can not be predicted by an adversary who can encrypt chosen messages; otherwise, it can lead to attacks, as first observed by Rogaway in 1995 [29], and subsequently exploited in the BEAST attack [15] in 2011 on TLS versions prior to 1.1.

CBC has been proven secure up to $2^{n/2}$ blocks of messages [7, 27]. On the other hand there is a simple birthday attack against CBC: after $2^{n/2}$ message blocks encrypted
with the same key (in the same message or in different messages), a collision between two ciphertext blocks $c_i^{(j)} = c_{i'}^{(j')}$ is expected. Since $E_k$ is a permutation, a collision in the output means that the inputs are the same ($m_i^{(j)} \oplus c_{i-1}^{(j)} = m_{i'}^{(j')}$ $\oplus c_{i'-1}^{(j')}$), which reveals the xor of two plaintext blocks:

$$m_i^{(j)} \oplus m_{i'}^{(j')} = c_{i-1}^{(j)} \oplus c_{i'-1}^{(j')}. $$

**Success probability.** In general, with $2^d$ blocks of data, the probability that there is at least one collision is (using $D = 2^d$ and $N = 2^n$):

$$ 
\begin{aligned}
p &= 1 - \prod_{i=0}^{D-1} \frac{N-i}{N} \\
  &\ge 1 - \prod_{i=0}^{D-1} e^{-i/N} \quad \text{using } 1-x \le e^{-x} \\
  &\ge 1 - e^{-D(D-1)/2N}
\end{aligned}
$$

In particular, with $d > n/2$, we have $p \ge 1 - e^{-1/2} \approx 0.39$. With larger values of $d$, the probably grows very close to 1:

$$ 
\begin{aligned}
p &\ge 1 - \frac{2N}{D(D-1) + 2N} \quad \text{using } 1 - e^{-x} > \frac{x}{x+1} \\
  &\ge 1 - \frac{2N}{D^2} \quad \text{since } D^2 < D(D-1) + 2N \\
  &\ge 1 - 2^{n-2d+1}
\end{aligned}
$$

On the other hand, when $d < n/2$ we can use:

$$p \ge \frac{D(D-1)}{4N} \approx 2^{2d-n-2} \quad \text{using } e^{-x} < 1 - x/2$$

Furthermore, with $2^d$ blocks of data the expected number of collisions is roughly $2^{2d-n-1}$.

## 2.3 Distinguishing attack against CTR

The counter mode CTR is another popular mode of operation for encryption, first proposed by Diffie and Hellman [14]. In particular, it provides the encryption part of authenticated encryption modes CCM and GCM, and a variant of counter mode is used in 3G telephony (f8). The counter mode actually builds a stream cipher out of a block cipher: a counter is encrypted to generate key-stream that is xored with the message. More precisely, the message $M$ is divided into blocks $m_i, 0 \le i < \ell$ which are encrypted as:

$$c_i = E_k(IV + i) \oplus m_i,$$

where IV is the initial value of the counter (see Figure 3).

If the encryption function $E_k$ is a pseudo-random function, rather than a pseudo-random permutation, then CTR is secure up to $2^n$ blocks [6]. However, in the common case where $E_k$ is a permutation, CTR is proven secure only up to $2^{n/2}$ blocks, and there is matching distinguishing attack with complexity $2^{n/2}$. If a message where all the plaintext blocks are equal is encrypted, then all the ciphertext blocks will be pairwise different. Indeed, all the $E_k(IV + i)$ are unique, because $E_k$ is a permutation. This enables the attacker to distinguish the counter mode from an ideal encryption scheme, because a collision between two ciphertext blocks becomes likely (with probability about 0.39). More interestingly, if the attacker has prior knowledge about the plaintext (such as a

<figure><img src="image_132.png" /><figcaption>Figure 3: CTR mode</figcaption></figure>

dictionary), he can use the distinguishing attack to eliminate impossible values to eventually guess the right plaintext [25].

It is interesting to compare the collision attacks against CBC and CTR. Both attacks have the same complexity, and show that the proofs are tight. However, the loss of security is quite different: an attacker can immediately recover some bits of information from the attack against CBC, while the attack against the counter mode requires a lot more work to recover any plaintext. In the remainder of this paper, we investigate on the practical impact of the CBC attack, but similar techniques (with higher complexity and more assumptions on the plaintext) may be used to attack CTR and GCM mode encryption in protocols like TLS and SSH.

## 2.4 Rekeying before the Birthday Bound

The main countermeasure against birthday attacks is to change the key frequently, before reaching the birthday bound under any single key. For instance, if the key is changed after $2^{n/2-16}$ blocks, a birthday attack against a given only succeeds with probability $2^{-32}$, and an attacker has to collect $2^{32}$ different sessions to mount an attack with high probability.

If implemented properly, this is an effective security measure to strengthen block ciphers with a small block-size. We stress than the key must be changed *well before* $2^{n/2}$ blocks, despite misleading recommendations in published standards. For instance, ISO recommends [21]:

> Generally, for a block cipher with block size of $n$ bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is $2^{(n/2)}$ blocks, due to the birthday paradox. As long as the implementation of a specific block cipher do not exceed these limits, using the block cipher will be safe.

This is incorrect, because collisions can be found with high probability (close to 0.39) with only $2^{n/2}$ blocks. Indeed, we will show that our concrete attacks also work against connections that are rekeyed close to the birthday bound.

## 2.5 Towards a Practical Attack on CBC

The CBC attack reveals the xor of two plaintext block, and in many contexts, this may not be sufficient for a practical attack. However, an effective attack can be mounted when the following conditions are fulfilled: (1) some high-value secret data is sent repeatedly; and (2) some fraction of the plaintext is known. In this case, there is a chance that a collision leaks the xor between a valuable secret and a known block; this would immediately reveal the secret. More precisely, this attack is expected to succeed (i.e. to recover one block of a high-value secret) with high probability as
soon as $2^a$ blocks of secret and $2^t$ known blocks are encrypted, with $s+t \ge n$.

To mount the attack in practice, an adversary would collect and store all the traffic, then sort the ciphertext blocks to find collisions. Assuming that the adversary knows the position of the secret blocks and of the known blocks in the stream, he can quickly see which collisions are useful, and recover the secret values by xoring with the known plaintext.

**Attack Complexity.** Let us denote the known fraction of the data as $\alpha$ and the secret and valuable fraction of the traffic as $\beta$ (with fraction $1 - \alpha - \beta$ that is neither known nor valuable to the attacker). In order to recover some secret information, an attacker must collect roughly $1/2\alpha\beta$ collisions, so that one collision is between a valuable secret block and a known block. Following the analysis of Section 2.2, this requires about $\sqrt{1/\alpha\beta} \cdot 2^{n/2}$ blocks of data.

For instance, with $n = 64$, in an optimal case for the adversary half of the traffic is known, and half of the traffic is highly valuable ($\alpha = \beta = 1/2$). In this case, a collision an attack requires about:

$$ \sqrt{1/\alpha\beta} \cdot 2^{n/2} = 2 \cdot 2^{n/2} = 2^{33} $$

blocks of data, which corresponds to just 64 GB. For a more concrete scenario, let us assume that the messages are HTTP queries of 512 bytes (64 blocks), with a secret 8-byte cookie (1 block), and that the remaining of the message is known, i.e. $\alpha = 63/64 \approx 1$, $\beta = 1/64$. The number of blocks needed by an attacker is roughly:

$$ \sqrt{1/\alpha\beta} \cdot 2^{n/2} \approx 8 \cdot 2^{n/2} = 2^{35} $$

which correspond to 256 GB.

**Rekeying at the Birthday Bound.** The attack can also be carried out when rekeying is used, if the keys are changed with low frequency. In particular, even if the keys are changed before $2^{n/2}$ blocks are encrypted, there is still a non-negligible probability that a collision occurs.

More precisely, let us assume that keys are rotated after encrypting $2^r$ blocks ($r \le n/2$). As explained in Section 2.2, the probability to have a collision between $2^r$ blocks is at least $2^{2r-n-2}$. Therefore, an attacker needs $1/2\alpha\beta \cdot 2^{n+2-2r}$ sessions (i.e. $1/2\alpha\beta \cdot 2^{n+2-r}$ blocks) to collect an interesting collision. In practice, the attacker would collect all the data in a session, sort it to find collisions, and can discard the data before collecting data from the next session.

In an optimal setting for the attacker ($\alpha = \beta = 1/2$), if the keys are changed after $2^{n/2}$ blocks as recommended by ISO [21] ($r = n/2$), the number of blocks needed by an attacker is roughly:

$$ \frac{1}{2\alpha\beta} \cdot 2^{n+2-r} = 2 \cdot 2^{n/2+2} = 2^{35} $$

which correspond to 256 TB. In the HTTP example above, the number of blocks needed is roughly:

$$ \frac{1}{2\alpha\beta} \cdot 2^{n+2-r} \approx 32 \cdot 2^{n/2+2} = 2^{39} $$

which correspond to 4 TB. Therefore rekeying just before $2^{n/2}$ blocks only has a limited impact on collision attacks.

**Optimal Rekeying Strategies.** The optimal use of rekeying has been studied by Abdalla and Bellare in [1], with the goal of increasing the encryption threshold (the number of blocks that can be encrypted before the advantage of an adversary becomes significant). Their result depend on the

key size $\kappa$ and the block size $n$. When $n = \kappa$, the optimal strategy is to rekey after $2^{n/3}$ blocks, leading to an encryption threshold of $2^{2n/3}$ (rather than $2^{n/2}$ without rekeying). Concrete figures for AES-based modes are also given in [24].

On the other hand, when $\kappa \ge 2n$ (as is the case for 3DES and Blowfish-128), the optimal strategy is to rekey for every block. Assuming a perfect rekeying function, this leads to an encryption threshold of $2^n$ (rather than $2^{n/2}$). In actual protocols such as TLS or OpenVPN, rekeying requires a new key exchange, which can be quite expensive. Therefore, rekeying should probably be implemented with a fixed limit, in the order of a few megabytes. We can compute the encryption threshold when rekeying every $2^r$ blocks as $2^{n-r}$ (this figure correspond to the optimal case for an adversary, with $\alpha = \beta = 1/2$). For example, by rekeying every megabyte, a client and server can exchange a petabyte of data before collision attacks become significant.

**Exploiting Repeated Messages.** We now assume that a fixed message of $2^n$ blocks is sent repeatedly (this will be the case for the concrete attacks we describe in Sections 4.4 and 4.5). The attacker's goal is to recover the full message, assuming that $\alpha \cdot 2^u$ blocks are known or predictable.

If there is a single unknown block, we can use the previous analysis with $\alpha \approx 1$ and $\beta = 2^{-u}$, an attacker need roughly $2^{(n+u)/2}$ blocks. Indeed, this should lead to roughly $2^{u-1}$ collisions, and there is a good chance that one of these collision is between the secret block and a known block. For a more accurate analysis, we can use the results of van Oorschot and Wiener [31], which gives an expected complexity of $\sqrt{\pi/2} \cdot 2^{(n+u-1)/2}$ blocks to find $2^{u-1}$ collisions.

If there are a few unknown blocks ($k = (1 - \alpha) \cdot 2^u$), the number of encrypted blocks required to recover them can be approximated as:

$$ \sqrt{H_k} \cdot \sqrt{\pi/2} \cdot 2^{(n+u-1)/2}, $$

because the number of collision required follows the harmonic numbers $^1 H_k = \sum_{i=1}^k 1/i$.

On the other hand, if $\alpha$ is small, the attacker can use collisions to derive equations between the plaintext blocks, even if both blocks are unknown. Each collision reveals the xor between two plaintext blocks, which can seen as an edge in a graph whose vertexes are the plaintext blocks. If we model the graph as a random graph with $2^u$ vertexes, we know that with high probability, the graph will be fully connected when there are more than $\Theta(u/2 \cdot 2^u)$ edges [17]. At this point, all plaintext blocks can be recovered from a single known block. Therefore, the expected attack complexity becomes:

$$ \sqrt{u} \cdot \sqrt{\pi/2} \cdot 2^{(n+u-1)/2} $$

**Summary of Attack Scenario.** With a fixed message of size $2^u$ repeatedly encrypted, an attacker that knows a fraction $\alpha$ of the message can recover the $k$ missing blocks of plaintext ($k = (1 - \alpha) \cdot 2^u$) by observing about $\log(k) \cdot 2^{n-1}$ collisions. This gives an attack with a data complexity of

$$ O(\sqrt{\log(k)} \cdot 2^{(n+u-1)/2}) $$

encrypted blocks. With rekeying every $2^r$ blocks ($r < n/2$), the complexity becomes:

$$ O(\log(k) \cdot 2^{u+n+2-r}). $$

<footnote n="1">¹Assuming that the time to recover each block follows a geometric law</footnote>
<table><caption>Table 1: Block ciphers in popular versions of Internet protocols; 64-bit ciphers are shown in red</caption><thead><tr><th>Protocol</th><th>Year</th><th>Block ciphers</th><th>Mandatory</th><th>Rekey</th></tr></thead><tbody><tr><td>TLS 1.0</td><td>1999</td><td>3DES, DES, IDEA</td><td>3DES</td><td></td></tr><tr><td>TLS 1.1</td><td>2006</td><td>AES, 3DES, DES</td><td>3DES</td><td>2<sup>78</sup></td></tr><tr><td>TLS 1.2</td><td>2008</td><td>AES, 3DES</td><td>AES</td><td>2<sup>78</sup></td></tr><tr><td>SSH 1</td><td>1995</td><td>3DES, DES, IDEA</td><td>3DES</td><td>-</td></tr><tr><td>SSH 2</td><td>2006</td><td>AES, 3DES, Blowfish</td><td>3DES</td><td>2<sup>30</sup></td></tr><tr><td>IKEv1</td><td>1998</td><td>3DES, DES, Blowfish</td><td>DES</td><td>-</td></tr><tr><td>IKEv2</td><td>2010</td><td>AES, 3DES, Blowfish</td><td>3DES</td><td>-</td></tr><tr><td>IPsec</td><td>2014</td><td>AES, 3DES</td><td>AES</td><td>1GB</td></tr></tbody></table>

In particular, we will apply this attack to break the security of encrypted HTTP connections when an authentication token is send with every request. We use the Beastly attacker of Figure 1 to generate a large number of requests, where the headers are mostly predictable or even controlled by the attacker ($\alpha \approx 1$), who can then recover the authentication token by observing collisions in the encrypted traffic.

## 3. 64-BIT BLOCK CIPHER USAGE ON THE INTERNET

Many of the most influential Internet security protocols, such as TLS, SSH, and IPsec were standardized at a time when 64-bit block ciphers, such as 3DES and Blowfish, were still considered strong. Consequently, these ciphers are still widely supported on the Internet. In this section, we investigate the real-world usage of these ciphers in order to quantify the feasibility and practical impact of our attacks.

### 3.1 Block Ciphers in Internet Standards

Table 1 summarizes the support for various block ciphers in several versions of the TLS, SSH, and IPsec standards. The table shows that protocols that were standardized before 2000 typically supported only 64-bit ciphers (primarily 3DES), although later protocol extensions enabled 128-bit ciphers (primarily AES). Still, old versions of these protocols remain quite popular on the web. Notably, each standard specifies a mandatory cipher that “MUST” be supported for interoperability, and in most of these specifications, the mandatory encryption algorithm is 3DES. This means that all implementations of TLS, SSH, and IPsec must implement 3DES, and unless the user explicitly disables it, they will offer to negotiate 3DES with their peers.

For example, in TLS 1.0 and 1.1, 3DES is the mandatory encryption algorithm, so all TLS libraries implement it and a vast majority of web servers support it. Although TLS 1.2 changed the mandatory cipher to AES, it still explicitly recommends 3DES as secure [13, Sec. 7.3]:

> If you negotiate 3DES with a 1024-bit RSA key exchange with a host whose certificate you have verified, you can expect to be that secure.

As a result, mainstream TLS libraries still treat 3DES to be at the same security level as AES-128. For example, until we disclosed the attacks in this paper, OpenSSL included 3DES ciphersuites in its HIGH-security list (it has now been moved to MEDIUM). Moreover, while the use of RC4 in TLS has been explicitly deprecated in RFC7465 in response to recent attacks, 3DES continues to be trusted by TLS libraries.

In fact, it has even started being recommended as the new backup cipher in place of RC4.<fnref n="2" /> TLS does not mandate rekeying for short block ciphers, and so TLS libraries leave the decision to rekey to their applications.

In SSH version 1, the strongest available ciphers are all 64-bit block ciphers: 3DES, Blowfish, and IDEA, and although SSH 2 introduced AES-based ciphers, it still labeled 3DES as the mandatory cipher. Consequently, popular implementations such as OpenSSH still use 3DES as the default cipher for SSH-1 connections, and 3DES continues to be the most widely supports cipher in SSH.<fnref n="3" /> SSH standards recommend that implementations rekey after every 1GB of data, or after every $2^{n/4}$ blocks [8], but many popular SSH clients do not implement this feature.

The early IPsec specifications also widely used and recommended 3DES. For example, RFC4835 recommended 3DES as a mandatory (MUST) algorithm until 2007, although the more recent RFC7321 has downgraded it to a “MAY”. Consequently, most IPsec libraries continue to support 3DES, and since IPSec deployments tend to be stable over a long period of time within corporate networks, we anticipate that the algorithm may continue to be supported on IPsec networks for the foreseeable future.

In summary, short block ciphers and 3DES in particular have widespread support in major secure transport protocols, making them vulnerable to the attacks described in this paper. However, to evaluate the real-world impact of this vulnerability, the key question is whether these ciphers are actually used in connections between popular clients and servers. In the rest of this section, we attempt to quantify this usage.

### 3.2 3DES and Blowfish usage in VPNs

TLS, SSH, and IPsec are often used to implement tunnels or virtual private networks (VPNs) across untrusted network connections. We have already discussed the widespread support for 64-bit block ciphers in these protocols, but estimating whether these ciphers are actually negotiated in practice is hard, because unlike web servers, most VPN services are not publicly accessible, and each VPN server may use its own configuration. However, we found a few VPN solutions that use 64-bit ciphers by default.

**IPsec.** Most IPsec-based VPN clients support 3DES for interoperability. Notably, some versions of Microsoft’s L2TP VPN client use 3DES by default<fnref n="4" />; some versions of MAC OS X negotiate 3DES with certain VPN servers<fnref n="5" />; and some versions of CISCO IPsec VPN devices implement hardware optimizations for 3DES and consequently prefer it over other ciphers.<fnref n="6" />

**OpenVPN.** OpenVPN is a popular open-source VPN solution originally written by James Yonan. The default encryption for the transport protocol of OpenVPN is Blowfish, a 64-bit cipher, in CBC mode. OpenVPN supports two different ways of generating session keys to encrypt the messages. In pre-shared-key mode, static keys are used for all the traffic.

<footnote n="2">²https://wiki.mozilla.org/Security/Server_Side_TLS</footnote>

<footnote n="3">³https://blog.binaryedge.io/2015/11/10/ssh/</footnote>

<footnote n="4">⁴https://support.microsoft.com/en-us/kb/325158</footnote>

<footnote n="5">⁵http://www.jacco2.dds.nl/networking/openswan-macosx.html</footnote>

<footnote n="6">⁶http://www.cisco.com/c/en/us/td/docs/ios/12.2/12.2z/12.2zj/feature/guide/gtaimvpn.html</footnote>
<table><caption>Table 2: Cipher use for TLS connection from the Firefox web browser (percentage). The figures come from telemetry data available at https://telemetry.mozilla.org/ (we use the SSL_SYMMETRIC_CIPHER_FULL metric), and are gathered during the lifetime of a particular version. RC4 is fallback-only since version 36.</caption><thead><tr><th colspan="2">Firefox Version</th><th colspan="5">AES</th></tr><tr><th>#</th><th>Release date</th><th>RC4</th><th>3DES</th><th>CBC</th><th>GCM</th><th></th></tr></thead><tbody><tr><td>35</td><td>2015/01/13</td><td>20.4</td><td>0.15</td><td>27.5</td><td>51.9</td><td></td></tr><tr><td>36</td><td>2015/02/24</td><td>0.20</td><td>1.81</td><td>45.5</td><td>52.5</td><td></td></tr><tr><td>37</td><td>2015/03/31</td><td>0.13</td><td>1.81</td><td>41.7</td><td>56.4</td><td></td></tr><tr><td>38</td><td>2015/05/12</td><td>0.09</td><td>1.82</td><td>36.0</td><td>62.1</td><td></td></tr><tr><td>39</td><td>2015/07/02</td><td>0.08</td><td>1.81</td><td>31.6</td><td>66.5</td><td></td></tr><tr><td>40</td><td>2015/08/11</td><td>0.08</td><td>1.68</td><td>29.7</td><td>68.6</td><td></td></tr><tr><td>41</td><td>2015/09/22</td><td>0.08</td><td>1.44</td><td>27.9</td><td>70.6</td><td></td></tr><tr><td>42</td><td>2015/11/03</td><td>0.08</td><td>1.26</td><td>27.9</td><td>70.7</td><td></td></tr><tr><td>43</td><td>2015/12/15</td><td>0.05</td><td>1.19</td><td>28.6</td><td>70.2</td><td></td></tr><tr><td>44</td><td>2016/01/26</td><td>-</td><td>1.17</td><td>28.3</td><td>70.5</td><td></td></tr><tr><td>45</td><td>2016/03/08</td><td>-</td><td>1.13</td><td>28.1</td><td>70.8</td><td></td></tr></tbody></table>

fic. In particular, there is no limit to the lifetime of those keys. In TLS mode, session keys are generated with a TLS handshake, using certificates to authenticate the peers. The session keys are updated periodically, with limits on the number of packets, the number of bytes, or a session time. The default configuration rekeys the tunnel every hour. In addition, the tunnel is rekeyed shortly before $2^{32}$ packets in TLS mode, because the packet counter is a 32-bit integer. In pre-shared-key mode, the packet counter is a 64-bit integer.

### 3.3 3DES usage in HTTPS

3DES is the second most widely supported cipher (after AES) in HTTPS servers, with about 87% of servers supporting it.<fnref n="7" /> Furthermore, all popular web browsers support 3DES. The cipher that is actually negotiated for a TLS connection is chosen by the server, based on its local preference order and on the order in which the client advertises its ciphersuites. Since most modern browsers and servers prefer AES over 3DES, we find evidence that 1-2% of all TLS connections likely use 3DES in CBC mode, as detailed below.

**Browser Telemetry.** Telemetry data from Mozilla Firefox (given in Table 2) show that 3DES is used for more than 1% of HTTPS connections from Firefox browsers. Interestingly, the use of 3DES with Firefox has actually increased recently, as a consequence of the removal of RC4 from the list of supported ciphers in version 36 (following [3] and RFC 7465). Indeed a number of servers are configured to use, in order of preference, first RC4, then 3DES, and now use 3DES with Firefox.

Other browser vendors have privately reported the following telemetry data to us. Microsoft sees 1.2% 3DES connections for Internet Explorer and Edge, but only 0.8% system wide (the lower value can be explained by the fact that some applications still support RC4). Google Chrome sees 1.1% of connections using 3DES, but this number peaked at 1.6% soon after RC4 was disabled.

<table><caption>Table 3: 3DES support for HTTPS servers in Alexa's top website list. We count servers that support 3DES, and servers that would select 3DES with common browsers: Android 5.0 integrated browser, Firefox 44, Internet Explorer 11, and Chrome 47. Scans performed on February 16 - 18, 2016.</caption><thead><tr><th>3DES support</th><th>Andr5</th><th>FF44</th><th>IE11</th><th>Chr47</th></tr></thead><tbody><tr><td>Top 1k</td><td>93%</td><td>0.4%</td><td>1.6%</td><td>1.6%</td></tr><tr><td>Top 10k</td><td>92%</td><td>1.0%</td><td>2.1%</td><td>2.1%</td></tr><tr><td>Top 100k</td><td>89%</td><td>0.8%</td><td>1.9%</td><td>1.9%</td></tr><tr><td>Top 1m</td><td>86%</td><td>0.6%</td><td>1.3%</td><td>1.3%</td></tr></tbody></table>

**Scanning the Top 1M Websites.** We performed a scan of the top 1 million servers as listed by Alexa using the cipherscan tool<fnref n="8" />. We found that 86% of the servers that support TLS include 3DES as one of the supported ciphers. Moreover, using the ciphersuites sent by a modern client (Firefox 44, IE 11 or Chrome 47), we estimate that 1.2% will actually use a 3DES based ciphersuite. We report detailed figures in Table 3.

**Windows XP Clients and Windows 2003 Servers.** The Windows XP and Windows Server 2003 operating systems do not support AES-based ciphersuites, although support for AES can be added with an optional hotfix. With the default configuration, they support only RC4, 3DES, DES, and RC2-40. While these operating systems are not supported anymore by Microsoft, they still have users, and this creates situations where the best available cipher is 3DES.

If a client uses Internet Explorer on Windows XP or Windows Server 2003 to connect to a modern web server (with no RC4 ciphersuites), the connection will use 3DES or fail. Indeed, supporting Windows XP clients is the main stated reason for servers to continue supporting RC4 and 3DES.

If a web server runs on IIS 6.0 (i.e. Windows XP or Windows Server 2003), it will offer only RC4 and 3DES ciphersuites, unless support for AES ciphersuites has been added. If a modern web browser visits the website over HTTPS, the connection will use 3DES. According to web server surveys<fnref n="9" />, IIS 6.0 powers about 1.9% of SSL enabled web servers, but it is likely used even more within corporate networks, and these servers would not appear in public scans.

**Long-lived HTTPS connections.** In order to mount the attack in practice, we need to find client and servers that not only negotiate the use of 3DES, but also exchange a large number of HTTP request in the same TLS connection (without rekeying). This is possible using a persistent HTTP connection, as defined in HTTP/1.1 (Keep-Alive).

On the client side, all browsers that we tested (Firefox, Chrome, Opera) will reuse a TLS connection as long as the server keeps it open. On the server side, we found that a number of HTTP servers will close the TLS connection even when it is still active. In particular, Apache and Nginx limit the number of requests sent in the same connection, with a maximum of 100 in the default configuration<fnref n="10" />. On

<footnote n="7">⁷https://securitypitfalls.wordpress.com/2016/04/17/february-2016-scan-results-incomplete/</footnote>

<footnote n="8">⁸https://github.com/jvehent/cipherscan</footnote>

<footnote n="9">⁹http://www.securityspace.com/s survey/sdata/201604/ servers.html</footnote>

<footnote n="10">¹⁰The setting is called MaxKeepAliveRequests for Apache, and keepalive_requests for Nginx.</footnote>
<table><caption>Table 4: Maximum connection lifetime for Alexa's top 10 servers (detected experimentally). The “i” symbol marks servers which accept at least one million requests in a single TLS connection.</caption><thead><tr><td>Website</td><td>connection closed after</td></tr></thead><tbody><tr><td>google.com</td><td>1 hour†</td></tr><tr><td>facebook.com</td><td>no limit detected†</td></tr><tr><td>youtube.com</td><td>no limit detected†</td></tr><tr><td>yahoo.com</td><td>no limit detected†</td></tr><tr><td>live.com</td><td>up to one day†</td></tr><tr><td>baidu.com</td><td>100 requests</td></tr><tr><td>amazon.com</td><td>100 requests</td></tr><tr><td>wikipedia.org</td><td>100 requests</td></tr><tr><td>qq.com</td><td>2000 requests</td></tr><tr><td>twitter.com</td><td>50 requests</td></tr></tbody></table>

the other hand, IIS does not seem to have such a limit. In practice, many high profile servers accept a very large number of requests in a single TLS connection. We made some experiments using a simple Perl script to send simple HTTP requests over a TLS connection, using pipelining to maximize the throughput. As seen in Table 4, we found that about half of the servers in Alexa's top 10 support a large number of requests without rekeying.

For a better estimate of the number of vulnerable servers, we tested servers from Alexa's top 10k that negotiate 3DES with a modern client. We identified 11483 different HTTPS servers<fnref n="11" />, and found that 226 of them (1.9%) negotiate 3DES with a modern client. Moreover, 72 of these (0.6% of the total) also accept to keep a connection open for at least 800k requests. Consequently, the duration of the attack is not unrealistic, at least at the viewpoint of browsers and servers, and we estimate that at least 0.6% of HTTPS connections are vulnerable to our attacks.

**Downgrading to 3DES.** From our measurements, only 1-2% of HTTPS connections use 3DES, and perhaps even fewer of these connections are to servers that allow long-lived TLS connections. However, ignoring the danger posed by 3DES would be dangerous for several reasons. 3DES is typically the second or third most preferred encryption algorithms in HTTPS, so any change in the client or server configurations, say in response to some future attack on AES, would cause a large number of connections to fallback to 3DES. Furthermore, as recent downgrade attacks on TLS (e.g. FREAK) have demonstrated, protocol and implementation flaws can sometimes cause a weaker cipher to be negotiated. For example, if a downgrade attack from TLS 1.2 to SSL 3 becomes possible, then the strongest SSL 3 cipher that can be negotiated may well be 3DES. As an example, we describe a downgrade attack to 3DES that is currently possible on TLS connections. Although it does not enable our full attack, it nevertheless serves as a useful warning for practitioners.

**Downgrading False Start.** TLS False Start [23] is an optimization to the TLS handshake that reduces its latency. A client implementing False Start will start sending data before receiving the Finished message from the server. This allows an attacker to force the selection of a ciphersuite by

tampering with the ServerHello message (he can replace AES by 3DES, for example) and the client will start sending data before verifying that the ciphersuite was really selected by the authentic server. If the client is willing to send millions of requests and gigabytes of data before finishing the handshake, this could allow our attack even against a server that would not select a 3DES ciphersuite. While 3DES ciphersuite are not recommended for use with False Start in the RFC draft [23], it turns out that they are white-listed for use with False Start with Internet Explorer. We have informed the Microsoft security team and they decided to remove 3DES from this white-list.

# 4. ATTACKING AUTHENTICATED HTTP OVER TLS AND OPENVPN

We now demonstrate concrete attacks against authenticated HTTP sessions even when they are secured by TLS or OpenVPN. First, we identify a few examples of secret authentication credentials that are repeatedly sent by the browser on every request. We then show how we can recover these secrets using block cipher collisions.

## 4.1 HTTP bearer tokens

**Cookie-based Sessions.** Modern HTTPS websites use a variety of methods to manage authenticated sessions with their clients. The most popular mechanism is secure *cookies* as specified in RFC6265. Once a user has logged in, the server sets a cookie containing a secret value on the user's browser. The browser will then send the cookie on all subsequent requests to the website, implicitly authenticating the user. For example, if `domain.com` sets a cookie `C=XXXX`, a subsequent HTTPS request from the browser looks like:

GET /path/to/file HTTP/1.1
User-Agent: Mozilla/4.0 ...
Host: domain.com
Cookie: C=XXXXX
Accept-Language: en-us
Accept-Encoding: gzip, deflate
Connection: Keep-Alive

Cookies are sensitive, because an attacker who obtains a session cookie can then log in as the user from a different browser. The cookie acts as a *bearer token* that carries the user's delegated credential. Except for its short-lived nature, it has the same security requirements as a password. Indeed, many websites, such as Facebook, use cookies with very long expiry times, making cookie theft even more attractive.

A cookie for a website is normally included in all requests to that website whether that request was initiated by the user, or a script on the website, or even by a different website. Browsers sometimes impose stricter rules for this last category of requests, called cross-origin or cross-domain requests. For example, `XmlHttpRequests` sent from one domain to another may not have cookies attached. However, cross-domain requests for images or iframes will still send cookies.

**HTTP BasicAuth.** On corporate networks and even on the web, many websites are protected using the HTTP Basic Authentication mechanism specified in RFC7617. When the server asks for Basic authentication, the browser prompts the user to enter a username and password into a special dialog and then sends this information (in plaintext) as an HTTP header of the form:

<footnote n="11">¹¹We tested common sub-domains: www, m, secure, signin, auth, account, login</footnote>
Authorization: Basic dGVzdDoxMjPCow=

Once a user has entered his login information once, the browser will typically cache this information and use it on all subsequent requests to the server. Notably, even if a different website creates a cross-domain request to the authenticated server, the BasicAuth credentials will be automatically sent by the browser.

BasicAuth credentials contain the user's password and are hence security-critical. One should only use this authentication mechanism over HTTPS but a number of corporate websites use BasicAuth over HTTP, under the assumption that their users can only access the website over a VPN or some other secure connection.

** OAuth and OpenID Connect Access Tokens.** With the growth in popularity of single sign-on protocols, many websites now allow users to login with third-party credentials, such as OAuth or OpenID Connect tokens, issued by major websites like Google and Facebook. These tokens are effectively bearer tokens that must then be attached to all authentication and authorization requests and are sent either within the URI or in an Authorization header. While the use of these tokens is specific to each website, an attacker can usually repeatedly trigger the sending of these tokens by re-initiating the login sequence. An attacker who steals one of these tokens can then impersonate the user as well as retrieve sensitive data about the user from the login provider.

## 4.2 The Beastly Attack Scenario

Our attack scenario, depicted in Figure 1, is similar to the setup used in recent attacks on RC4 [3, 19, 32]. The attacker wants to steal some bearer token that is being repeatedly sent by a browser to a website secured with HTTPS, or an HTTP website accessed through a VPN. We assume that the attacker can control some JavaScript on a web page loaded by the user's browser, either by actively tampering with an HTTP response on the wire, or by hosting a malicious website that the user is fooled into visiting. We also assume that the attacker can observe all the encrypted traffic between the target browser and the secure website.

We further assume that the data is encrypted with a 64-bit block cipher in CBC mode (either an HTTPS connection where the client and server have negotiated 3DES, or an HTTP connection though a VPN encrypted with Blowfish or 3DES). Suppose the victim is already logged in to a website and has a session cookie. The attacker runs malicious JavaScript code on the victim's browser that repeatedly sends HTTP queries to the target website server, each containing the session cookie. If he sends close to $2^{32}$ queries, a collision is expected between a ciphertext block corresponding to the cookie ($c_i$), and a known block ($c_j$), containing a known part of the query. The collision attack against CBC reveals the session cookie: $p_i = p_j \oplus c_{i-1} \oplus c_{j-1}$.

Note that most of the traffic generated by the attacker is known or predictable. The requested URL is chosen by the attacker, and all the headers excepted the cookie are predictable and can be observed in any plaintext HTTP traffic. We will assume that the Cookie takes 16-bytes, i.e. two blocks, and that the attacker has aligned the cookie to a block boundary using other headers. As explained in Section 2.2, if a query contains $2^u$ known blocks, the number of encrypted blocks required for the attack is about:

$$ \sqrt{H_2} \cdot \sqrt{\pi/2} \cdot 2^{(n+u-1)/2}. $$

In practice, an HTTP query is about 512 bytes (64 blocks), which implies a total complexity of $2^{35.1}$ blocks ($2^{29.1}$ queries), and a total captured trace of size 280 GB.

However, the attack can be made faster by using larger queries: this increases the total amount of data to capture, but it reduces the total number of queries. Since the speed of clients and servers is dependent on the number of queries, a larger query size can result in a faster attack overall. In our experiments, we got good results with 4 kB queries (512 blocks). In this setting, the attack requires $2^{36.6}$ blocks (785 GB), but this corresponds to only $2^{27.6}$ queries: increasing the requests size by a factor 8 (from 512 bytes to 4 kB) increases the total data to capture by a factor $\sqrt{8}$, and reduces the number of queries needed by a factor $\sqrt{8}$. In practice large queries can be produced by adding a long query string to the URL.

## 4.3 Proof-of-concept Code

The attacker code consists of two parts: a JavaScript program that sends a large number of HTTP requests, and a network adversary who processes the resulting ciphertext to recovers a 16-byte secret.

** Man-in-the-browser code.** We experimented with hidden <img> tags in a web-page with Javascript code to theonload event to reload the images repeatedly, and web workers issuing [XmlHttpRequests](https://developer.mozilla.org/en-US/docs/Reference/Global_Objects/XmlHttpRequests). Cookies are automatically inserted when loading images from a different domain, and are also included in cross-domain [XmlHttpRequests](https://developer.mozilla.org/en-US/docs/Reference/Global_Objects/XmlHttpRequests) if the [withCredentials](https://developer.mozilla.org/en-US/docs/Reference/Global_Objects/XmlHttpRequests/withCredentials) property is set to true (this is only allowed for synchronous request, and the request result can not be read, but these restrictions don't prevent our attack). According to our experiments, request are generated faster using [XmlHttpRequest](https://developer.mozilla.org/en-US/docs/Reference/Global_Objects/XmlHttpRequest). In order to avoid caching, we request a non-cacheable resource. Alternatively, we can include a unique query string in each URL, but the responses are still cached by the client and this can affect the query rate. We experimented with several browsers, and we obtained the best results with Firefox Developer Edition 47.0a2$^{12}$.

** Recovering collisions.** We captured the encrypted packets with `tcpdump` and used a C++ program to extract the ciphertext blocks (using `libpcap`). In both the HTTPS attack and the OpenVPN attack, each HTTP query is sent in a separate encrypted record, which contain the plaintext at a fixed position, as well as some extra information (packet number, padding, MAC, ...). Therefore, it is easy to know to which plaintext block corresponds each ciphertext block, and to align the cookie to a block limit.

After capturing all the traffic, the C++ program sorts the ciphertext blocks in order to locate collisions. Since the amount of data is quite large (hundreds of gigabytes), we use the external sort implementation of the `stxxl` library. With a NAS storage, sorting the data took around four hours.

## 4.4 Attacking Basic Auth over OpenVPN

To demonstrate the attack against OpenVPN, we use a pre-shared-key tunnel between two physical machines running Linux, with Firefox Developer Edition 47.0a2 on one side, and an nginx server on the other side. Access to the server is protected by BasicAuth, and the user has entered his

<footnote>12We have similar results with the stable version Firefox 48.0 which was released after we made our experiments.</footnote>
credentials. Using the default OpenVPN settings, the tunnel is encrypted with Blowfish in CBC mode.

We use the Javascript code described in the previous section to send a large number of requests to the server though the tunnel. We found that increasing the size of the request to 4 kB does not significantly reduce the query rate, but reduces the number of queries required for the attack. In our setting, the browser generates about 2900 requests per second, using several web Worker running in parallel. We expect the first collision after roughly $2^{32.3}$ blocks (40 GB), i.e. one hour. In practice, we detected the first collision early, after only 30 minutes ($2^{31.3}$ blocks); as expected, the predicted xor difference was correct. The full attack needs about $2^{36.6}$ blocks (785 GB) to recover a two-block secret out of 4 kB messages; this should take about 19 hours in this setting. In our demo, it took 18.6 hours and 705 GB, and we successfully recovered the 16-byte authentication token.

**OpenVPN in TLS mode.** In TLS mode, OpenVPN rekeys the tunnel every hour with the default settings (as apposed to the pre-shared-key mode used above that doesn't do any rekeying). With our experimental setting, this means we can only capture about $2^{23.3}$ requests encrypted with a given key, i.e. $2^{32.3}$ blocks. Therefore, we expect to detect a collision with probability close<fnref n="13" /> to 1/2. In order to recover a two-byte secret out of 4 kB messages, we need about 384 collisions as explained in Section 2.2. Therefore, this attack will take roughly 768 hours, or 32 days.

This illustrate the point that keys should be changed *well before* reaching $2^{32}$ blocks: if each session is broken after $2^{32}$ blocks, there is still a collision with probability roughly $1-e^{-1/2} \approx 0.4$. This increases the time required by the attack to 40 days, but it will still succeed with high probability.

## 4.5 Attacking Secure Cookies over HTTPS

The attack against HTTPS connection is very similar to the attack against OpenVPN, as long as we have a client and server that negotiate 3DES, and that keep a connection open for a long time.

**Vulnerable Websites.** As detailed in Section 3.3, about 0.6% of the top Alexa 100K websites support 3DES and allow long-lived HTTPS connections. This list contains many high-profile e-commerce and banking websites, including the ones shown in Table 5. In addition, we found a number of domains were the server serving `domain.com` will use 3DES, but it just redirects the client to a better configured server for `www.domain.com`. This could still open the way for our attacks, if sessioncookies for `www.domain.com` are set at the top-level domain and hence also sent to `domain.tld`. The last three websites in Table 5 belong to this category.

**Proof-of-Concept Attack Demo.** In our setup we use Firefox Developer Edition 47.0a2 running on Linux and an IIS 6.0 server in a Windows Server 2003 R2 SP2 Virtual machine. The default configuration of IIS 6.0 with all recommended updates offers only RC4 and 3DES ciphers, and will use 3DES with Firefox and other recent browsers where RC4 is disabled. Moreover, IIS 6.0 supports HTTP/1.1 and keeps an active connection open for an arbitrary long time.

We use the Javascript code described in Section 4.3, but we note that with several Workers running in parallel (or several `<img>` tags), modern browsers open a few parallel connec-

<table><caption>Table 5: High-value websites that negotiate 3DES with modern browsers, and accept at least 1 million requests in the same TLS session</caption><thead><tr><td>Website</td><td>Category</td></tr></thead><tbody><tr><td>https://login.ebay.com</td><td>E-commerce</td></tr><tr><td>https://account.nasdaq.com</td><td>Finance</td></tr><tr><td>https://www.bancomercantil.com</td><td>Banking</td></tr><tr><td>https://www.unionbankonline.co.in</td><td>Banking</td></tr><tr><td>https://ziraatbank.com.tr</td><td>Banking</td></tr><tr><td>https://www.state.nj.us</td><td>Government</td></tr><tr><td>https://secure.match.com</td><td>Dating</td></tr><tr><td>https://amadeus.net</td><td>Travel</td></tr><tr><td>https://walmart.com</td><td>Corporate</td></tr><tr><td>https://citrix.com</td><td>Corporate</td></tr></tbody></table>

tions to the server (typically, 6) and split the requests over these connections. For our attack, we need to maximize the throughput over a single connection. This can be achieved by disturbing some of the connections so that most of request are send in a single. In our setup, we used `iptables` rules to limit the rate of all connections except one. In a real attack, this would be done by an active man-in-the-middle, but a passive man-in-the-middle can also mount the attack – it will just take more time to collect the data.

On Firefox Developer Edition 47.0a2, with a few dozen Workers running in parallel, we can send up to 2000 requests per second in a single TLS connection. To further reduce the time needed for the attack, we inject a padding cookie to expand the requests to 4 KB (512 blocks). In our setting this reduces the rate to 1500 requests per second, but it still leads to a faster attack. Again, we expect the first collision after roughly $2^{32.3}$ blocks (40 GB), i.e. $2^{23.3}$ queries. This should take slightly less than two hours.

In our experiment, we were lucky to detect the first collision after only 25 minutes ($2^{20.1}$ requests), and we verified that the collision revealed the xor of two plaintexts blocks. As seen previously, the full attack should require $2^{36.6}$ blocks (785 GB) to recover a two-block cookie, which should take 38 hours in our setting. Experimentally, we recovered the two-block cookie after only 30.5 hours and 610 GB.

Note that special care must be taken to recover the first block of a TLS fragment. When a collision involves the first ciphertext block ($c_1^{(j)} = c_0^{(j')}$), this gives an equation involving the IV ($c_{i-1}^{(j)} = c_{i}^{(j')}$). In particular, this requires special treatment for TLS 1.0, because the IV of a given of a given record is not explicitly included in the message: it is the last ciphertext block of the previous record.

Our attack above relied on knowing most of the plaintext, but if we have enough data we can even recover most of the plaintext using just a single known block. In our experiment, after 65 hours ($2^{28.3}$ requests, 1.3TB) we can recover 492 blocks out of 510, assuming a single known plaintext block.

## 5. IMPACT AND MITIGATION

We have demonstrated the first concrete attacks on mainstream Internet protocols that exploit block cipher collisions. Our attacks can recover valuable secrets such as HTTP cookies and passwords in under 40 hours. Our attacks impact a

<footnote n="13">¹³The probability can be computed as $1 - e^{-2^{32.2}e^{232.2}/2^{64}}$.</footnote>
majority of OpenVPN connections and an estimated 0.6% of HTTPS connections to popular websites. We expect that our attacks also impact a number of SSH and IPsec connections, but we do not have concrete measurements for these protocols. Like many recent attacks on TLS, such a BEAST and RC4 NOMORE, the underlying principles behind our attacks were well known to cryptographers. Our goal is to raise awareness among practitioners about the vulnerabilities of short block ciphers and on safe ways of using them.

## 5.1 Comparison with RC4 attacks

Our attack scenario is very similar to the setup of the recent attacks on the use of RC4 in HTTPS. We use the same man-in-the-browser setting to generate a large number of HTTP requests, and the data complexity of our attacks is comparable to these prior works:

* the first attack by Al Fardan et al. [3] uses between $2^{28}$ and $2^{32}$ sessions, with rekeying for each session, to recover the first 220 bytes a the message (but the cookie is not usually in these 220 bytes);

* the second attack by Al Fardan et al. [3] uses between $2^{33}$ and $2^{34}$ request, in the same TLS session or in different sessions, to recover a cookie;

* Garman et al. [19] improved the first attack to require only $2^{26}$ sessions when targeting a BasicAuth password, using a better guessing strategy;

* the latest attack by Vanhoef and Piessens [32] requires $2^{30.2}$ requests, in the same TLS session or in different sessions, to recover a cookie.

In comparison, our attack requires only $2^{29.1}$ short queries of 512 bytes (280 GB in total), which can be reduced to $2^{27.6}$ longer queries of 4 kB (785 GB in total). However, these numbers are for the case when all the data is encrypted within the same session. Even if the amount of data sent on a single connection is limited, as long as the limit is close enough to the birthday bound, we can still mount our attacks across multiple parallel and sequential sessions, albeit with a higher data and time complexity.

## 5.2 Mitigation

The obvious way to avoid these attacks is to stop using legacy 64-bit block-ciphers. There is no good reason to configure a VPN or an HTTPS server to prefer 3DES (or Blowfish) over AES. AES is more secure, is a FIPS standard, and will almost certainly be faster: it is implemented in hardware in most server and desktop CPUs, and can be implemented efficiently in dedicated hardware when an extremely high throughput is required.

On the other hand, there are specific uses of cryptography were 128-bit block ciphers can not be used, because of legacy reasons, or due to the relatively large hardware footprint of 128-bit ciphers (in this case, lightweight 64-bit block ciphers such as PRESENT or HIGHT would typically be used). In these scenarios, protocol designers should pay close attention to the issue of birthday attacks. In particular, they should verify that the amount of data encrypted with a fixed key is significantly smaller than $2^{32}$ blocks, or use modes that provide security beyond the birthday bound, such as CENC [22] or PMAC plus [33].

Concretely, we recommend the following measures to prevent our attack:

1. Web servers and VPNs should be configured to prefer 128-bit ciphers. According to our scans, about 1.1% of the top 100k web server from Alexa, and 0.5% of the top 1 million, support AES but prefer to use 3DES.

2. Web browsers should offer 3DES as a fallback-only cipher, to avoid using it with servers that support AES but prefer 3DES.

3. TLS libraries and web browsers and servers should limit the length of TLS sessions with a 64-bit cipher. This could be done in TLS renegotiation, or in some cases by closing the connection and starting a new one (i.e. limiting HTTP/1.1 Keep-Alive, SPDY, and HTTP/2 with 3DES ciphersuites).

## 5.3 Responsible Disclosure

We have communicated our results and concerns to the OpenVPN team, and to various website owners, browser vendors, and TLS libraries. They all acknowledged the issue, and are working on implementing countermeasures. The TLS vulnerability received CVE number CVE-2016-2183.

OpenVPN will display a warning to users who choose to use 64-bit ciphers and encourage them to transition to AES-GCM (cipher negotiation is also being implemented in the 2.4 branch). It will also implement a default renegotiation limit of 64MB when used in TLS mode.

OpenSSL has moved 3DES ciphersuites from the HIGH category to MEDIUM in the 1.0.2 branch, and will disable it by default in the upcoming 1.1.0 release.

Akamai will offer an option for web server administrators to drop 3DES from the offered ciphers.

Apple has disabled 3DES on icloud.com and is recommending that all its customers disable 3DES on their websites.

Currently, most browsers see about 1% of their connections using 3DES, and vendors consider this number too high to simply disable 3DES on the client side, since too many websites would be broken. So, they are instead considering implementing data limits per connection to force rekeying, or offering 3DES ciphersuites only in a fallback negotiation if no AES ciphersuite is acceptable to the server.

Mozilla is implementing data limits for all ciphersuites:

https://bugzilla.mozilla.org/show_bug.cgi?id=1268745

Microsoft has removed 3DES from the False Start whitelist: https://technet.microsoft.com/library/security/3155527.aspx

More details about implemented countermeasures will be added to our webpage as they become available:

http://sweet32.info

# 6. REFERENCES

[1] M. Abdalla and M. Bellare. Increasing the lifetime of a key: a comparative analysis of the security of re-keying techniques. In T. Okamoto, editor, ASIACRYPT 2000, volume 1976 of LNCS, pages 546–559. Springer, Heidelberg, Dec. 2000.

[2] D. Adrian, K. Bhargavan, Z. Durumeric, P. Gaudry, M. Green, J. A. Halderman, N. Heninger, D. Springall, E. Thomé, L. Valenta, B. VanderSloot, E. Wustrow, S. Z. Béguelin, and P. Zimmermann. Imperfect forward secrecy: How Diffie-Hellman fails in practice. In I. Ray, N. Li, and C. Kruegel, editors, ACM CCS 15, pages 5–17. ACM Press, Oct. 2015.
[3] N. J. AlFardan, D. J. Bernstein, K. G. Paterson, B. Poettering, and J. C. N. Schuldt. On the Security of RC4 in TLS. In S. T. King, editor, USENIX Security, pages 305-320. USENIX Association, 2013.

[4] N. J. AlFardan and K. G. Paterson. Lucky thirteen: Breaking the TLS and DTLS record protocols. In 2013 IEEE Symposium on Security and Privacy, pages 526-540. IEEE Computer Society Press, May 2013.

[5] N. Aviram, S. Schinzel, J. Somorovsky, N. Heninger, M. Dankel, J. Steube, L. Valenta, D. Adrian, J. A. Halderman, V. Dukhovni, E. Kasper, S. Cohney, S. Engels, C. Paar, and Y. Shavitt. DROWN: Breaking TLS using SSLv2, 2016. https://drownattack.com.

[6] M. Bellare, A. Desai, E. Jokipii, and P. Rogaway. A concrete security treatment of symmetric encryption. In 38th FOCS, pages 394-403. IEEE Computer Society Press, Oct. 1997.

[7] M. Bellare, J. Kilian, and P. Rogaway. The security of cipher block chaining. In Y. Desmedt, editor, CRYPTO'94, volume 839 of LNCS, pages 341-358. Springer, Heidelberg, Aug. 1994.

[8] M. Bellare, T. Kohno, and C. Namprempre. The Secure Shell (SSH) Transport Layer Encryption Modes. IETF RFC 4344, 2006.

[9] B. Beurdouche, K. Bhargavan, A. Delignat-Lavaud, C. Fournet, M. Kohlweiss, A. Pironti, P.-Y. Strub, and J. K. Zinzindohoue. A messy state of the union: Taming the composite state machines of TLS. In 2015 IEEE Symposium on Security and Privacy, pages 535-552. IEEE Computer Society Press, May 2015.

[10] K. Bhargavan and G. Leurent. Transcript Collision Attacks: Breaking Authentication in TLS, IKE, and SSH. In ISOC Network and Distributed System Security Symposium (NDSS16), 2016.

[11] K. K. Bodo Moller, Thai Duong. This POODLE Bites: Exploiting The SSL 3.0 Fallback, 2014. https://www.openssl.org/~bodo/ssl-poodle.pdf.

[12] A. Bogdanov, L. R. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe. PRESENT: An ultra-lightweight block cipher. In P. Paillier and I. Verbauwhede, editors, CHES 2007, volume 4727 of LNCS, pages 450-466. Springer, Heidelberg, Sept. 2007.

[13] T. Dierks and E. Rescorla. The Transport Layer Security (TLS) Protocol Version 1.2. IETF RFC 5246, 2008.

[14] W. Diffie and M. E. Hellman. Privacy and authentication: An introduction to cryptography. Proceedings of the IEEE, 67(3):397-427, 1979.

[15] T. Duong and J. Rizzo. Here come the ⊕ ninjas. Unpublished manuscript, 2011.

[16] M. Dworkin. Recommendation for Block Cipher Modes of Operation. NIST Special Publication 800-38{A,B,C,D}, National Institute for Standards and Technology, 2001 - 2011.

[17] P. Erdos and A. Rényi. On the evolution of random graphs. Bull. Inst. Internat. Statist, 38(4):343-347, 1961.

[18] S. Frankel and S. Krishnan. IP Security (IPsec) and Internet Key Exchange (IKE) Document Roadmap. IETF RFC 6071, 2011.

[19] C. Garman, K. G. Paterson, and T. V. der Merwe. Attacks Only Get Better: Password Recovery Attacks Against RC4 in TLS. In J. Jung and T. Holz, editors, USENIX Security, pages 113-128. USENIX Association, 2015.

[20] D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B.-S. Koo, C. Lee, D. Chang, J. Lee, K. Jeong, H. Kim, J. Kim, and S. Chee. HIGHT: A new block cipher suitable for low-resource device. In L. Goubin and M. Matsui, editors, CHES 2006, volume 4249 of LNCS, pages 46-59. Springer, Heidelberg, Oct. 2006.

[21] On the Assessment of Cryptographic Techniques and Key Lengths, 4th edition. ISO/IEC JTC 1/SC 27 Standing Document 12, May 2014. Available online: http://www.din.de/blob/78392/6f4bbd95d0cf11d1b32784948039600b/sc27-sd12-data.pdf.

[22] T. Iwata. New blockcipher modes of operation with beyond the birthday bound security. In M. J. B. Robshaw, editor, FSE 2006, volume 4047 of LNCS, pages 310-327. Springer, Heidelberg, Mar. 2006.

[23] A. Langley, N. Modadugu, and B. Moeller. Transport Layer Security (TLS) False Start. Internet Draft, Nov. 2015. https://tools.ietf.org/html/draft-ietf-tls-falsestart-01.

[24] A. Luykx and K. G. Paterson. Limits on authenticated encryption use in TLS, march 2016. http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf.

[25] D. McGrew. Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes. In Fast Software Encryption Workshop (FSE), 2013. https://eprint.iacr.org/2012/623.

[26] D. McGrew and P. Hoffman. Cryptographic Algorithm Implementation Requirements and Usage Guidance for Encapsulating Security Payload (ESP) and Authentication Header (AH). IETF RFC 7321, 2014.

[27] E. Petrank and C. Rackoff. CBC MAC for real-time data sources. Journal of Cryptology, 13(3):315-338, 2000.

[28] J. Rizzo and T. Duong. The crime attack. In EKOparty Security Conference, volume 2012, 2012.

[29] P. Rogaway. Problems with Proposed IP Cryptography. Unpublished draft, 1995. http://web.cs.ucdavis.edu/~rogaway/papers/draft-rogaway-ipsec-comments-00.txt.

[30] P. Rogaway. Evaluation of Some Blockcipher Modes of Operation. Technical report, CRYPREC, Feb 2011.

[31] P. C. van Oorschot and M. J. Wiener. Parallel collision search with cryptanalytic applications. Journal of Cryptology, 12(1):1-28, 1999.

[32] M. Vanhoef and F. Piessens. All Your Biases Belong to Us: Breaking RC4 in WPA-TKIP and TLS. In J. Jung and T. Holz, editors, USENIX Security, pages 97-112. USENIX Association, 2015.

[33] K. Yasuda. A new variant of PMAC: Beyond the birthday bound. In P. Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 596-609. Springer, Heidelberg, Aug. 2011.

[34] T. Ylonen and C. Lonvick. The Secure Shell (SSH) Transport Layer Protocol. IETF RFC 4253, 2006.
# The Missing Difference Problem, and its Applications to Counter Mode Encryption*

Gaëtan Leurent and Ferdinand Sibleyras

Inria, France

{gaetan.leurent,ferdinand.sibleyras}@inria.fr

**Abstract.** The counter mode (CTR) is a simple, efficient and widely used encryption mode using a block cipher. It comes with a security proof that guarantees no attacks up to the birthday bound (i.e. as long as the number of encrypted blocks $\sigma$ satisfies $\sigma \ll 2^{n/2}$), and a matching attack that can distinguish plaintext/ciphertext pairs from random using about $2^{n/2}$ blocks of data.

The main goal of this paper is to study attacks against the counter mode beyond this simple distinguisher. We focus on message recovery attacks, with realistic assumptions about the capabilities of an adversary, and evaluate the full time complexity of the attacks rather than just the query complexity. Our main result is an attack to recover a block of message with complexity $\tilde{O}(2^{n/2})$. This shows that the actual security of CTR is similar to that of CBC, where collision attacks are well known to reveal information about the message.

To achieve this result, we study a simple algorithmic problem related to the security of the CTR mode: the missing difference problem. We give efficient algorithms for this problem in two practically relevant cases: where the missing difference is known to be in some linear subspace, and when the amount of data is higher than strictly required.

As a further application, we show that the second algorithm can also be used to break some polynomial MACs such as GMAC and Poly1305, with a universal forgery attack with complexity $\tilde{O}(2^{2n/3})$.

**Keywords:** Modes of operation, CTR, GCM, Poly1305, Cryptanalysis

## 1 Introduction

Block ciphers (such as DES or the AES) are probably the most widely used cryptographic primitives. Formally, a block cipher is just a keyed family of permutations over $n$-bit blocks, but when combined with a mode of operation, it can provide confidentiality (e.g. using CBC, or CTR), authenticity (e.g. using CBC-MAC, CMAC, or GMAC), or authenticated encryption (e.g. using GCM, CCM, or OCB). A mode of operation defines how to divide a message into blocks, and how to process the blocks one by one with some chaining rule.

<footnote>* © IACR 2018. This article is the final version submitted by the author(s) to the IACR and to Springer-Verlag on 2018-02-07. The version published by Springer-Verlag is available on their website.</footnote>
The security of block ciphers is studied with cryptanalysis, with classical techniques such as differential [8] and linear [27] cryptanalysis, dedicated techniques like the SQUARE attack [9], and ad-hoc improvements for specific targets. This allows to evaluate the security margin of block ciphers, and today we have a high confidence that AES or Blowfish are as secure as a family of pseudo-random permutations with the same parameters (key size and block size).

On the other hand, modes of operation are mostly studied with security proofs, in order to determine conditions where using a particular mode of operation is safe. However, exceeding those conditions doesn't imply that there is an attack, and even when there is one, it can range from a weak distinguisher to a devastating key recovery. In order to get a better understanding of the security of modes of operations, we must combine lower bound on the security from security proofs, and upper bounds from attacks.

In particular, most of the modes used today are sensible to birthday attacks because of collisions; those attacks can even be practical with 64-bit block ciphers, as shown in [7], but security proofs don't tell us how dangerous the attacks are. For instance, the CBC and CTR modes have been proven secure against chosen plaintext attacks up to $\sigma \ll 2^{n/2}$ blocks of encrypted data [5,35]. Formally, the security statements bound the maximum advantage of an attacker against the modes as follows:

$$ \mathbf{Adv}_{\text{CBC}-E}^{\text{CPA}} \le \mathbf{Adv}_{E}^{\text{prp}} + \sigma^2/2^n, $$

$$ \mathbf{Adv}_{\text{CTR}-E}^{\text{CPA}} \le \mathbf{Adv}_{E}^{\text{prp}} + \sigma^2/2^{n+1}. $$

Both statements are essentially the same, and become moot when $\sigma$ reaches $2^{n/2}$, but attacks can actually be quite different.

More precisely, the CBC mode is defined as $c_i = E(m_i \oplus c_{i-1})$, with E a block cipher. A collision between two ciphertext blocks $c_i = c_j$ is expected after $2^{n/2}$ blocks, and reveals the xor of two plaintext blocks: $m_i \oplus m_j = c_{i-1} \oplus c_{j-1}$. On the other hand, the counter mode is defined as $c_i = E(i) \oplus m_i$. There are no collisions in the inputs/outputs of E, but this can actually be used by a distinguisher. Indeed, if an adversary has access to $2^{n/2}$ known plaintext/ciphertext pairs, he can recover $E(i) = c_i \oplus m_i$ and detect that the values are unique (because E is a permutation), while collisions would be expected with a random ciphertext. Both attacks have the same complexity, and show that the corresponding proofs are tight. However, the loss of security is quite different: the attack against CBC lets an attacker recover message blocks from collisions (as shown in practice in [7]), but the attack against the counter mode hardly reveals any useful information.

In general, there is a folklore belief that the leakage of the CTR mode is not as bad as the leakage of the CBC mode. For instance, Ferguson, Schneier and Kohno wrote [15, Section 4.8.2] (in the context of a 128-bit block cipher):

CTR leaks very little data. [...] It would be reasonable to limit the cipher mode to $2^{60}$ blocks, which allows you to encrypt $2^{64}$ bytes but restricts the leakage to a small fraction of a bit.

When using CBC mode you should be a bit more restrictive. [...] We suggest limiting CBC encryption to $2^{32}$ blocks or so.
**Our contribution.** The main goal of this paper is to study attacks against the counter mode beyond the simple distinguisher given above. This is an important security issue, because uses of the CTR mode with 64-bit block ciphers could be attacked in practice. We consider generic attacks that work for any instance of the block cipher *E*, and assume that *E* behaves as a pseudo-random permutation. The complexity of the attacks will be determined by the block size *n*, rather than the key size, and we focus on the asymptotic complexity, using the Big-O notation *O*(), and the Soft-O notation $\tilde{O}()$ (ignoring logarithmic factors).

We consider message recovery attacks, where an attacker tries to recover secret information contained in the message, rather than recovering the encryption key *k*. Following recent attacks against HTTPS [12,2,7], we assume that a fixed message containing both known blocks and secret blocks is encrypted multiple times (this is common with web cookies, for instance). As shown by McGrew [28], this kind of attack against the CTR mode can be written as a simple algorithmic problem: the *missing difference problem*, defined as follows: given two functions $f, g: X \rightarrow \{0,1\}^n$, with the promise that there exists a unique $S \in \{0,1\}^n$ such that $\forall (x,y), f(x) \oplus g(y) \neq S$, recover $S$. We further assume that $f$ and $g$ behave like random functions, and that we are given a set $S \subseteq \{0,1\}^n$, such that $S \in S$ ($S$ represents prior knowledge about the secret). In an attack against the counter mode, $f$ outputs correspond to known keystream blocks, while $g$ outputs correspond to encryptions of $S$.

In the information theoretic setting, this problem can be solved with $\tilde{O}(2^{n/2})$ queries for any set $S$, and requires at least $\Omega(2^{n/2})$ queries when $|S| \ge 2$. However, the analysis is more complex when taking into account the cost of the computations required to recover $S$. McGrew introduces two algorithms for this problem: a sieving algorithm with $\tilde{O}(2^{n/2})$ queries and time $\tilde{O}(2^n)$, and a searching algorithm that can be optimized to time and query complexity $\tilde{O}(2^{n/2}\sqrt{|S|})$. Our main contribution is to give better algorithms for this problem:

1. An algorithm with $\tilde{O}(2^{n/2})$ queries and time $\tilde{O}(2^{n/2} + 2^{\dim\langle S \rangle})$, in the case where $S$ is (a subset of) a linear subspace of $\{0,1\}^n$. In particular, when $S$ is a linear subspace of dimension $n/2$, we reach a time and query complexity of $\tilde{O}(2^{n/2})$, while the searching algorithm of McGrew has a time and query complexity of $\tilde{O}(2^{3n/4})$.

2. An algorithm with time and query complexity $\tilde{O}(2^{2n/3})$ for any $S$. In particular, with $S = \{0,1\}^n$, the best previous algorithm had a time complexity of $\tilde{O}(2^n)$.

We also show new applications of these algorithms. The first algorithm leads to an efficient message recovery attack with complexity $\tilde{O}(2^{n/2})$ against the CTR mode, assuming that the adversary can control the position of the secret, by splitting it across block boundaries (following ideas of [32] and [12]). The second algorithm can be used to recover the polynomial key in some polynomial based MACs such as GMAC and Poly1305, leading to a universal forgery attack with complexity $\tilde{O}(2^{2n/3})$. As far as we know, this is the first universal forgery attack against those MACs with complexity below $2^n$.
**Related works.** There are several known results about the security of mode of operation beyond the birthday bound, when the proof is not applicable. For encryption modes, the security of the CBC mode beyond the birthday bound is well understood: collision attacks reveal the XOR of two message blocks, and can exploited in practice [7]. Other modes that allow collisions (eg. CFB) have the same properties. The goal of this paper is to study the security of modes that don't have collisions, to get a similar understanding of their security.

Many interesting attacks have also been found against authentication modes. In 1995, Preneel and van Oorschot [31] gave a generic collision attack against all deterministic iterated message authentication codes (MACs), leading to existential forgeries with complexity $O(2^{n/2})$. Later, a number of more advanced generic attacks have been described, with stronger outcomes than existential forgeries, starting with a key-recovery attack against the envelop MAC by the same authors [32]. In particular, a series of attack against hash-based MAC [25,30,18,11] 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 [24]. Later, Fuhr, Leurent and Suder gave a key-recovery attack against the PMAC variant used in AEZv3 [17]. Issues with GCM authentication with truncated tags were also pointed out by Ferguson [14].

None of these attacks contradict the proof of security of the scheme they target, but they are important results to understand the security degradation after the birthday bound.

**Organization of the paper.** We introduce the CTR mode and the missing difference problem in Section 2, and present our algorithmic contributions in Section 3. Then we describe concrete attacks against the CTR mode in Section 4, and attacks against Carter-Wegman MACs in Section 5. At last we show detailed proofs and simulation results in Section 6.

## 2 Message Recovery Attacks on CTR mode

<figure><img src="image_133.png" /><figcaption>Fig. 1. CTR mode</figcaption></figure>
The CTR mode was first proposed by Diffie and Hellman in 1979 [10]. It was not included in the first series of standardized modes by NIST [16], but was added later [13]. The CTR mode essentially turns a block cipher into a stream cipher, by encrypting some non-repeating counter. It is now a popular mode of operation, thanks to its parallelizability, speed, and simple design. This led Phillip Rogaway to write in an evaluation of different privacy modes of operation talking about CTR [35]: “Overall, usually the best and most modern way to achieve privacy-only encryption”. In particular, CTR is used as the basic of the authenticated encryption mode GCM, the most widely used mode in TLS today.

## 2.1 Setting and Notations

In the following we assume that the counter mode is implemented such that the input to the block cipher never repeats. For simplicity we consider a stateful variant of the counter mode with a global counter that is maintained across messages and initialized as 0 (as shown in Figure 1):

$$c_i = E_k(i) \oplus m_i,$$

where $E_k$ is an n-bit block cipher, $m_i$ an n-bit block of plaintext and $c_i$ an n-bit block of ciphertext.

Our attacks do not depend on the details of how the input to the block cipher is constructed, and can also be applied to nonce-based variants<fnref n="1" />; we only require that all inputs are different. Note that some variants of the counter mode can have repetitions in the block cipher input<fnref n="2" />, but this gives easy attacks because repetitions leak the xor of two plaintext blocks (as in the CBC mode).

We consider a message recovery attack, where the attacker tries to recover some secret message block $S$. Throughout the attack, the key $k$ will be invariant so we will write $E_k(i)$ as $a_i$ to represent the $i^{th}$ block of CTR keystream. We can immediately notice that if we have partial knowledge of the plaintext, for every known block $m_i$ we can recover the associated $a_i$ as $c_i \oplus m_i = a_i$. Assume further that we have access to the repeated encryption $b_j$ of the secret $S$ so that $b_j = a_j \oplus S$. The first property of the CTR mode is that $E_k(\cdot)$ being a permutation, the keystream $a_i$ never repeats, thus we have the following inequalities:

$$i \neq j \Rightarrow a_i \neq a_j \Rightarrow a_i \oplus a_j \oplus S \neq S \Rightarrow a_i \oplus b_j \neq S.$$

From now on we will always assume that we can observe and collect lists of many $a_i$ and $b_j$ and use them with the previous inequality to recover $S$. This setting is similar to the practical attack Sweet32 on the CBC mode mounted by Bhargavan and Leurent, using repeated encryptions of an authentication token to obtain many different ciphertext blocks for the same secret information [7].

Formally, let $\mathcal{A} \subseteq \{0,1\}^n$ be the set of observed keystream blocks, $\mathcal{B} \subseteq \{0,1\}^n$ the set of observed encryptions and $S \subseteq \{0,1\}^n$ the set of possible secrets

<footnote n="1">¹ For instance, GCM concatenates a per-message nonce and a counter within a message.</footnote>

<footnote n="2">² For instance, the treatment of non-default-length nonces in GCM can lead to collisions [23].</footnote>
(corresponding to some already known information about $S$). We define the missing difference algorithmic problem in terms of set:

**Definition 1 (Missing Difference Problem).** Given two sets $A$ and $B$, and a hint $S$, find the value $S \in S$ such that:

$$ \forall (a, b) \in A \times B, S \neq a \oplus b. $$

Alternatively, we can consider that the attacker is given oracle access to $A$ and $B$ though some functions $f$ and $g$, so that its running time includes calls to $f$ and $g$, and computations to recover $S$. This presentation corresponds to a more active attack, where the adversary can optimize the size of the sets.

**Definition 2 (Missing Difference Problem with Functions).** Given two functions $f, g: X \to \{0, 1\}^n$, and a hint $S$, find the value $S \in S$ such that:

$$ \forall (x, y), S \neq f(x) \oplus g(y). $$

## 2.2 Previous Work

An attack can only be carried to the end if the secret $S$ is the only value in $S$ such that $\forall (a, b) \in A \times B, S \neq a \oplus b$, or else it will be indistinguishable from the other values that satisfy the same condition (those values could have produced the same sets with same probability). The coupon collector's problem predicts that $N$ out of $N$ different coupons are found after $N \cdot H_N \approx N \ln N$ draws (with $H_N$ the $N$-th harmonic number), assuming uniform distribution of the draws. In our case we will assume that all the differences $a \oplus b$ are independent and uniformly distributed over $\{0, 1\}^n \setminus S$, which is a reasonable approximation validated by our experiments. To carry the attack to the end we require to collect $N = |S| - 1$ differences thus we will need $O(|S| \ln |S|)$ “draws”. A draw is a couple $(a, b)$ s.t. $a \oplus b \in |S|$, otherwise we discard it; it happens with probability $(|S| - 1)/(2^n - 1)$. Therefore we need to observe enough data to have $|A| \cdot |B|$ in the order of $O(2^n \ln |S|)$; this may be achieved by having both sets in the order of $O(2^{n/2} \sqrt{\ln |S|})$. This size of the observed sets can be understood as the query complexity, that is the number of encrypted messages the attacker will have to intercept in order to carry out the attack. Notice that even for $|S| = O(2^n)$, $|A| = |B| = O(\sqrt{n} \cdot 2^{n/2})$ is quite close to the theoretical lower bound of $O(2^{n/2})$ given by the distinguishing attack and the security proof for the CTR mode. Therefore, message recovery attacks are possible with an (almost) optimal data complexity. The next question is to study the time complexity, i.e. how to efficiently recover $S$.

A first approach consists in computing all the impossible values of $S$ from the large set of $A \times B$ and discard any new value we encounter as impossible until there's only one possible plaintext left. This is algorithm 1. This approach works but requires to actually compute $O(2^n \ln |S|)$ values and maintain in memory a sieve of size $|S|$. In the case where the key size is equal to the block size $n$, like AES-128, this attack is actually worse than a simple exhaustive search of the key.
<caption>**Algorithm 1.** Simple sieving algorithm</caption>

**Input:** $\mathcal{A}, \mathcal{B}, \mathcal{S}$
**Output:** $\{s \in \mathcal{S} \mid \forall (a, b) \in \mathcal{A} \times \mathcal{B}, a \oplus b \neq s\}$
**for** $a$ **in** $\mathcal{A}$ **do**
  **for** $b$ **in** $\mathcal{B}$ **do**
    Remove $(a \oplus b)$ from $\mathcal{S}$;
  **end for**
**end for**
**return** $\mathcal{S}$

<caption>**Algorithm 2.** Searching algorithm</caption>

**Input:** $\mathcal{A}, \mathcal{B}, \mathcal{S}$
**Output:** $\{s \in \mathcal{S} \mid \forall (a, b) \in \mathcal{A} \times \mathcal{B}, a \oplus b \neq s\}$
Store $\mathcal{B}$ so that operation $\in$ is efficient.
**for** $s$ **in** $\mathcal{S}$ **do**
  **for** $a$ **in** $\mathcal{A}$ **do**
    **if** $(s \oplus a) \in \mathcal{B}$ **then**
      Remove $s$ from $\mathcal{S}$;
    **end if**
  **end for**
**end for**
**return** $\mathcal{S}$

In a 2012 work, McGrew [28] described this sieving algorithm and noticed that when the set $\mathcal{S}$ is small, the sieving wastes a lot of time computing useless values. Therefore he proposed a second algorithm, algorithm 2, to test and eliminate values of $\mathcal{S}$ one by one. This algorithm loops over $\mathcal{S}$ and $\mathcal{A}$ to efficiently test whether $s \oplus a \in \mathcal{B}$; if yes then we sieve the value $s$ out of $\mathcal{S}$.

Both algorithms act on a sieving set $\mathcal{S}$ to reduce it, so McGrew proposed a hybrid algorithm switching from one algorithm to the other in order to reduce the searching space as quickly as possible. This improves the attack when $\mathcal{A}$ and $\mathcal{B}$ are fixed, but if the adversary can choose the sizes of $\mathcal{A}$ and $\mathcal{B}$ (in particular, if he actually has oracle access to functions $f$ and $g$), then the searching algorithm allows better trade-offs. Indeed, the searching algorithm has a complexity of $O(|\mathcal{B}|+|\mathcal{A}|\cdot|\mathcal{S}|)$, and is successful as soon as $|\mathcal{A}|\cdot|\mathcal{B}| = \Omega(2^n \ln |\mathcal{S}|)$. To optimize the complexity, we use $|\mathcal{B}| = |\mathcal{A}|\cdot|\mathcal{S}|$ to obtain an overall complexity of $O(2^{n/2}\sqrt{|\mathcal{S}|\ln|\mathcal{S}|})$ in both time and queries. In particular for small $\mathcal{S}$ (of size polynomial in $n$) this algorithm is (almost) optimal, reaching the birthday bound $\tilde{O}(2^{n/2})$.

Starting from these observations we will show improved algorithms to recover a block of secret information without big exhaustive searches in the next section.
# 3 Efficient Algorithms for the Missing Difference Problem

We now propose two new algorithms to solve the missing difference algorithmic problem more efficiently in two practically relevant different settings. Our first algorithm requires that the set $\mathcal{S}$ — or its linear span $\langle \mathcal{S} \rangle$ — is a vector space of relatively small dimension, and has complexity $\tilde{\mathcal{O}}(2^{n/2} + |\langle \mathcal{S} \rangle|)$. The second algorithm uses a larger query complexity of $\tilde{\mathcal{O}}(2^{2n/3})$, to reduce the computation and memory usage to $\tilde{\mathcal{O}}(2^{2n/3})$.

## 3.1 Known Prefix Sieving

In many concrete attack scenarios, an attacker knows some bits of the secret message in advance. For instance, an HTTP cookie typically uses ASCII printable characters, whose high order bit is always set to zero. More generally, we assume that $\mathcal{S}$ is (included in) an affine subspace of $\{0, 1\}^n$ of dimension $n-z$ for some natural $z < n$. In order to simplify the attack, we use a bijective affine function $\phi$ that maps $\mathcal{S}$ onto $\{0\}^z \times \{0, 1\}^{n-z}$, and rewrite the problem as follows:

$$S \neq a \oplus b \Leftrightarrow \phi(S) \neq \phi(a \oplus b), \quad \text{as } \phi \text{ is a bijection.}$$

$$\Leftrightarrow \phi(S) \neq \phi(a) \oplus \phi(b) \oplus \phi(0), \quad \text{as } \phi \text{ is affine}$$

Therefore, we can reduce the missing difference problem on $\mathcal{A}$, $\mathcal{B}$, $\mathcal{S}$ with $\dim(\langle \mathcal{S} \rangle) = n-z$ to the missing difference problem on $\mathcal{A}'$, $\mathcal{B}'$, $\mathcal{S}'$, where the secret is known to start with $z$ zeroes:

$$\mathcal{S}' := \{0\}^z \times \{0, 1\}^{n-z}$$

$$\mathcal{A}' := \{\phi(a) \mid a \in \mathcal{A}\}$$

$$\mathcal{B}' := \{\phi(b) \oplus \phi(0) \mid b \in \mathcal{B}\}$$

We now introduce a known prefix sieving algorithm (Algorithm 3) to solve this problem efficiently. The algorithm is quite straightforward; it looks for a prefix collision before sieving in the same way as before to recover $\mathcal{S}$. The complexity depends on the dimension $n-z$; the sieving requires $\mathcal{O}(2^{n-z})$ memory and $\mathcal{O}((n-z) \cdot 2^{n-z})$ XOR computations in expectation, while looking for collisions only requires to store the prefix keys and to go through one of the set. Looking for collisions allows us to skip the computations of many pairs $(a, b)$ that would be irrelevant as $a \oplus b \notin \mathcal{S}$.

The expected number of collisions required to isolate the secret is given by the coupon collector problem as $\ln(2^{n-z})2^{n-z} = \ln 2 \cdot (n-z) \cdot 2^{n-z}$. Therefore the total optimized complexity (with balanced sets $\mathcal{A}$ and $\mathcal{B}$) to recover an $n-z$ bits secret with this algorithm is:

$\mathcal{O}(\sqrt{n-z} \cdot 2^{n/2})$ queries

$\mathcal{O}(2^{n-z} + n\sqrt{n-z} \cdot 2^{n/2})$ bits of memory (sieving & queries)

$\mathcal{O}((n-z) \cdot 2^{n-z} + \sqrt{n-z} \cdot 2^{n/2})$ operations (sieving & collisions searching)
As we can see from the complexity, when $z = 0$ this is the naive algorithm with its original complexity. When $z$ nears $n$, this performs similarly to McGrew's searching algorithm i.e. the cost of looking for collisions (or storing $\mathcal{B}$ so that the search is efficient) will dominate the overall cost of the algorithm therefore the time and query complexity will match. Actually, this algorithm improves over previous works for intermediate values of $z$. With $z = n/2$, we have an algorithm with complexity $\tilde{O}(2^{n/2})$, while McGrew's searching algorithm would require $\tilde{O}(2^{3n/4})$ computations in the same setting. The complexity therefore becomes tractable and we could implement and run this algorithm for $n = 64$ bits with success, as shown in Section 6.2.

<caption>**Algorithm 3.** Known prefix sieving algorithm</caption>

**Input:** $n, z < n$, $\mathcal{A}, \mathcal{B}$, $S \subseteq \{0\}^z \times \{0, 1\}^{n-z}$
**Output:** $\{s \in S \mid \forall (a, b) \in \mathcal{A} \times \mathcal{B}, a \oplus b \neq s\}$
$h_B \leftarrow \text{Empty hash table.}$
**for** $b$ **in** $\mathcal{B}$ **do**
$h_B[b_{[0 \dots (z-1)]}] \stackrel{\cup}{\leftarrow} \{b_{[z \dots (n-1)]}\}$
**end for**
**for** $a$ **in** $\mathcal{A}$ **do**
$v_a \leftarrow a_{[z \dots (n-1)]}$
**for** $v_b$ **in** $h_B[a_{[0 \dots (z-1)]}]$ **do**
Remove $\bar{0} \parallel (v_a \oplus v_b)$ from $S$;
**end for**
**end for**
**return** $S$

## 3.2 Fast Convolution Sieving

Alternatively, we can reduce the complexity of the sieving algorithm by using sets $\mathcal{A}$ and $\mathcal{B}$ of size $2^m \gg 2^{n/2}$, rather than $\tilde{O}(2^{n/2})$ as required to uniquely identify $S$. If we consider all the values $a \oplus b$ for $(a, b)$ in $\mathcal{A} \times \mathcal{B}$, we expect that they are close to uniformly distributed over $\{0, 1\}^n \setminus S$, so that every value except $S$ is reached about $2^{2m-n}$ times, while $S$ is never hit. Increasing $m$ makes the gap more visible than with sets of size only $\tilde{O}(2^{n/2})$. Therefore, we can consider buckets of several candidates $s$, and accumulate the number of $a \oplus b$ in each bucket. If we consider buckets of $2^t$ values, each bucket receives $2^{2m+t-n}$ values on average, but the bucket containing $S$ receives only $2^{2m+t-n} - 2^{2m-n}$ values. If we model this number with random variables following a binomial distribution, the variance $\sigma^2$ is about $2^{m+t/2-n/2}$. Therefore, the bias will be detectable when: $\sigma \ll 2^{2m-n}$, i.e. when $t \ll 2m-n$.

Concretely, we use a truncation function $T$ that keeps only $n-t$ bits of an $n$-bit word. We consider the values $T(a \oplus b)$ for all $(a, b) \in \mathcal{A} \times \mathcal{B}$, and count how
many times each value is reached. If $m$ is large enough, the value with the lowest counter corresponds to $T(S)$. This attack does not require any prior information on the secret; it can be used with $S = \{0, 1\}^n$, and once $T(S)$ is known, we can use known-prefix sieving to recover the remaining bits (looking for $S$ in an affine space of dimension $t$).

We now show an algorithm to quickly count the number of occurrences for each combination. For a given multi-set $\mathcal{X}$, we consider an array of counters $C_{\mathcal{X}}$, to represent how many times each value $T(x)$ is reached:

$$C_{\mathcal{X}}[i] = |\{x \in \mathcal{X} \mid T(x) = i\}|.$$

Our goal is to compute $C_{\mathcal{A} \oplus \mathcal{B}}$ efficiently from $\mathcal{A}$ and $\mathcal{B}$, where $\mathcal{A} \oplus \mathcal{B}$ is the multi-set $\{a \oplus b \mid (a, b) \in \mathcal{A} \times \mathcal{B}\}$. We observe that:

$$
\begin{align*}
C_{\mathcal{A} \oplus \mathcal{B}}[i] &= |\{(a, b) \in \mathcal{A} \times \mathcal{B} \mid T(a \oplus b) = i\}| \\
&= \sum_{a \in \mathcal{A}} |\{b \in \mathcal{B} \mid T(a \oplus b) = i\}| \\
&= \sum_{a \in \mathcal{A}} |\{b \in \mathcal{B} \mid T(b) = i \oplus T(a)\}| \\
&= \sum_{a \in \mathcal{A}} C_{\mathcal{B}}[i \oplus T(a)] \\
&= \sum_{j \in \{0,1\}^{n-t}} C_{\mathcal{A}}[j] C_{\mathcal{B}}[i \oplus j]
\end{align*}
$$

This is a form of convolution that can be computed efficiently only using the Fast Walsh-Hadamard Transform (Algorithm 4), in the same way we use the Fast Fourier Transform to compute circular convolutions (see Algorithm 5). Therefore the full attack (shown in Algorithm 6) takes time $\tilde{O}(2^{n-t})$ using lists of size $2^m$ with $m \gg (n+t)/2$ and a sieve of $2^{n-t}$ elements.

In order to optimize the attack, we select $t = n/3$ such that the time complexity, data complexity, and memory usage are all roughly $2^{2n/3}$. A detailed analysis in Section 6.1 shows that we reach a constant success rate with $t = n/3$ using lists of size $\mathcal{O}(\sqrt{n} \cdot 2^{2n/3})$. This gives the following complexity for the full attack:

$$
\begin{align*}
\mathcal{O}(\sqrt{n} \cdot 2^{2n/3}) & \quad \text{queries} \\
\mathcal{O}(n \cdot 2^{2n/3}) + \mathcal{O}(n\sqrt{n} \cdot 2^{n/2}) & \quad \text{bits of memory (counters + sieving)} \\
\mathcal{O}(n \cdot 2^{2n/3}) + \mathcal{O}(n\sqrt{n} \cdot 2^{n/2}) & \quad \text{computations (fast Walsh-Hadamard + sieving)}
\end{align*}
$$

As seen in Section 6.1, we performed experiments with $n = 12, 24, 48$, and the correct $S$ was found with the lowest counter in at least 70% of our experiments, using list of size $\sqrt{n} 2^{2n/3}$. This validates our approach and shows that the constant in the $\mathcal{O}$ notation is small. We could run this algorithm over $n = 48$ bits in a matter of minutes.

**Optimizations.** In order to increase the success rate of the algorithm, one can test several candidates for $T(S)$ (using the lowest remaining counters), and use
<caption>**Algorithm 4.** Fast Walsh-Hadamard Transform</caption>

**Input:** $C_A$, $|C_A| = 2^m$
**Output:** The Walsh-Hadamard transform of $C_A$
**for** $d = m$ **downto** 0 **do**
    **for** $i = 0$ **to** $2^{m-d}$ **do**
        **for** $j = 0$ **to** $2^{d-1}$ **do**
            $C_A[i \cdot 2^d + j] \leftarrow C_A[i \cdot 2^d + j] + C_A[i \cdot 2^d + j + 2^{d-1}]$
            $C_A[i \cdot 2^d + j + 2^{d-1}] \leftarrow C_A[i \cdot 2^d + j] - 2 \cdot C_A[i \cdot 2^d + j + 2^{d-1}]$
        **end for**
        **end for**
    **end for**
    **return** $C_A$

<caption>**Algorithm 5.** Fast convolution</caption>

**Input:** $C_A, C_B$
**Output:** $C_{A \oplus B}$
{Perform fast Walsh-Hadamard transform in-place}
FWHT($C_A$); FWHT($C_B$);
**for** $c = 0$ **to** $2^{n-t}$ **do**
    $C_{A \oplus B}[c] \leftarrow C_A[c] \cdot C_B[c]$
**end for**
{Perform fast Walsh-Hadamard transform in-place}
FWHT($C_{A \oplus B}$);
**return** $C_{A \oplus B}$

<caption>**Algorithm 6.** Sieving with fast convolution</caption>

**Input:** $A, B, t \le n$
**Output:** $S$ s.t. $\forall (a, b) \in A \times B$, $a \oplus b \ne S$
$C_A, C_B, C_{A \oplus B} \leftarrow$ arrays of $2^{n-t}$ integers initialized to 0;
**for** $a$ **in** $A$ **do**
    Increment $C_A[a_{0..(n-t-1)}]$
**end for**
**for** $b$ **in** $B$ **do**
    Increment $C_B[b_{0..(n-t-1)}]$
**end for**
$C_{A \oplus B} \leftarrow$ FASTCONVOLUTION($C_A, C_B$)
$u \leftarrow$ argmin$_i$ $C_{A \oplus B}[i]$
Run known prefix sieving (Algorithm 3), knowing that $T(S) = u$
the known-prefix sieving to detect whether the candidate is correct. Another option is to run multiple independent runs of the algorithm with different choices of the $n/3$ truncated bits. This would avoid some bad cases we have observed in simulations, where the right counter grows abnormally high and gets hidden in all of the other counters.

For the memory complexity, notice that we don't need to store all the data but simply to increment a counter. We only need to keep enough blocks for the second part of the algorithm so that the sieving yields a unique result. Initially the counters for $C_A$ and $C_B$ are quite small, $\sqrt{n}$ in expectation. However, $C_{A\oplus B}$ will have much bigger entries, $n \cdot 2^{2n/3}$ in expectation, so that we need $O(n)$ bits to store each entry.

# 4 Application to the CTR Mode

We know show how to mount attacks against the counter mode using the new algorithms for the missing difference problem.

## 4.1 Attack using Fast Convolution

Use of the fast convolution algorithm to recover one block of CTR mode plaintext is straightforward. The attacker is completely passive and observes encryptions of $S$ (gathered in set $\mathcal{B}$), and keystream blocks recovered from the encryption of known message blocks (gathered in set $\mathcal{A}$). When the lists are large enough, he runs the fast convolution algorithm on $\mathcal{A}$ and $\mathcal{B}$ to recover $S$.

## 4.2 Attacks using Known Prefix Sieving

**Direct attack.** There are many settings where unknown plaintext will naturally lie in some known affine subspace, and the known prefix sieving algorithm can be used directly. For instance a credit card number (or any number) could be encoded in 16 bytes of ASCII then encrypted. Because in ASCII the encoding of any digit starts by `0x3` (`0x30` to `0x39`), we know half of the bits of the plaintext, and we can use the known-prefix sieving with $z = n/2$. Other examples are information encoded by `uuencode` that uses ASCII values `0x20` to `0x5F` (corresponding to two known bits) or HTML authentication cookies that are typically encoded to some subset of ASCII numbers and letters<fnref n="3" />.

**Block splitting.** We often assume that the secret is encrypted in its own block, but when the secret is part of the message, it can also be split across block boundaries, depending on how the plaintext is constructed and encrypted by the protocol. In particular, if a message block contains both known bytes and secret

<footnote n="3">³ For example, wikipedia.org encodes cookies with lower case letters and digits, this corresponds to two known bits.</footnote>
<figure><img src="image_134.png" /><figcaption>**Table 1.** Example of an attack on two blocks secret $S = S_1 \parallel S_2 \parallel S_3 \parallel S_4$. Each step performs the known prefix sieving algorithm. Known information in blue, unknown information in red, attacked information in yellow.</figcaption></figure>

bytes, we can apply the known prefix sieving algorithm to this block and recover the secret bytes.

In many protocols, messages start with some low entropy header that can be guessed by an attacker. Moreover, the attacker often has some degree of control over those headers. For instance, in the BEAST attack [12] against HTTPS, an attacker uses Javascript code to generate HTTPS requests, and he can choose the URL corresponding to the requests. Using this control of the length of the header, block splitting attacks have been shown in the BEAST model [12,20]. The attacker starts with a header length so that a small chunk of the secret message is encrypted together with known information, and recovers this secret chunk. Then he changes the length of the header to recover a second chunk of the message, using the fact that the first chunk is now known. Eventually, the full secret can be recovered iteratively.

In our case, the easiest choice is to recover chunks of $n/2$ bits of secret one by one, using the known-prefix sieving algorithm with $z = n/2$. We illustrate this attack in Table 1, assuming a two-block secret $S = S_1 \parallel S_2 \parallel S_3 \parallel S_4$, and a protocol that lets the adversary query an encryption of the secret with an arbitrary chosen prefix:

1. The attacker makes two kind of queries

- $Q_1$ with a known half-block header $H_1$ ($\mathcal{E}([H_1 \parallel S_1] \parallel [S_2 \parallel S_3] \parallel [S_4]))$;

- $Q_2$ with a known full-block header $H_1 \parallel H_2$ ($\mathcal{E}([H_1 \parallel H_2] \parallel [S_1 \parallel S_2] \parallel [S_3 \parallel S_4]))$.

2. He first recovers $S_1$ using the known-prefix sieving with the first block of each type of query. More precisely, he uses $\mathcal{A} = \{\mathcal{E}(H_1 \parallel H_2)\}$ and $\mathcal{B} = \{\mathcal{E}(H_1 \parallel S_1)\}$, so that the missing difference is $0 \parallel (S_1 \oplus H_2)$.

3. When $S_1$ is known, he can again use known prefix sieving to recover $S_2$, with the first and second blocks of $Q_2$ queries: $\mathcal{A} = \{\mathcal{E}(H_1 \parallel H_2)\}$ and $\mathcal{B} = \{\mathcal{E}(S_1 \parallel S_2)\}$, so that the missing difference is $(S_1 \oplus H_1) \parallel (S_2 \oplus H_2)$. To improve the success rate of this step, he can also consider the first block of $Q_1$ queries as known keystream.

4. When $S_2$ is known, another round of known prefix sieving reveals $S_3$, e.g. with $\mathcal{A} = \{\mathcal{E}(H_1 \parallel H_2)\}$ and $\mathcal{B} = \{\mathcal{E}(S_2 \parallel S_3)\}$, the missing difference is $(S_2 \oplus H_1) \parallel (S_3 \oplus H_2)$.
5. Finally, $S_4$ is recovered with a last round of known prefix sieving using $\mathcal{A} = \{\mathcal{E}(H_1 \parallel H_2)\}$ and $\mathcal{B} = \{\mathcal{E}(S_3 \parallel S_4)\}$, with missing difference is $(S_3 \oplus H_1) \parallel (S_4 \oplus H_2)$.

This gives an algorithm with query complexity of $O(\sqrt{n}2^{n/2})$ to recover repeated encryption of a secret over multiple blocks in the BEAST attacker model. In Section 6.2, we analyze the constants in the $O(\cdot)$ and run experiments with $n = 64$ using locally encrypted data. In particular, we have a success probability higher than 80% using two lists of $5 \times 2^{32}$ queries with $n = 64$.

More generally, we show that for $n \ge 32$ the success probability of this attack is at least 99% with lists of size $\sqrt{n/2} \cdot 2^{n/2}$. With a one block secret, an optimal attack uses two lists of $\sqrt{n/2} \cdot 2^{n/2}$ two-block queries: queries $[H_1 \parallel S_1] \parallel [S_2]$ with a half-block header, and queries $[H_1 \parallel H_2] \parallel [S_1 \parallel S_2]$ with a full-block header. This translates to a data complexity of $4\sqrt{n/2} \cdot 2^{n/2}$ blocks. For comparison, an attack against the CBC mode requires on average $2 \cdot 2^{n/2}$ blocks of data in the ideal case.

Alternatively, an attacker could recover the secret bit by bit. This leads to a more complex attack in practice, but the complexity is similar, and this variant could use McGrew's searching algorithm instead of our known-prefix sieving algorithm (because in this scenario, we have $|S| = 2$). We show a detailed analysis of this variant in Section 6.2, taking into account the $n$ steps necessary for this attack.

## 4.3 Use of CTR Mode in Communication Protocols

The CTR mode is widely used in internet protocols, in particular as part of the GCM authenticated encryption mode [29], with the AES block cipher. For instance, Mozilla telemetry data show that more than 90% of HTTPS connections from Firefox 58 use AES-GCM<fnref n="4" />. While attacks against modes with a 128-bit block cipher are not practical yet, it is important to limit the amount of data processed with a given key, in order to keep the probability of a successful attack negligible, following the guidelines of Luykx and Paterson [26].

Surprisingly, there are also real protocols that use 64-bit block ciphers with the CTR mode (or variants of the CTR mode), as shown below. Attacks against those protocols would be (close to) practical, assuming a scenario where an attacker can generate the encryption of a large number of messages with some fixed secret.

**SSH.** Ciphersuites based on the CTR mode were added to SSHv2 in 2006 [4]. In particular, 3DES-CTR is one of the recommended ciphers, but actual usage of 3DES-CTR seems to be rather low [1]. In practice, 3DES-CTR is optionally supported by the dropbear server, but it is not implemented in OpenSSH. According to a scan of the full IPv4 space by Censys.io<fnref n="5" />, around 9% of SSH servers

<footnote n="4">⁴ https://mzl.la/2GY53Mc, accessed February 8, 2018</footnote>

<footnote n="5">⁵ https://censys.io/data/22-ssh-banner-full_ipv4, scan performed July 5, 2017</footnote>
support 3DES-CTR, but actual usage is hard to estimate because it depends on
client configuration.

The SSH specification requires to rekey after 1GB of data, but an attack is
still possible, although the complexity increases.

**3G telephony.** The main encryption algorithm in UMTS telephony is based on the 64-bit blockcipher Kasumi. The mode of operation, denoted as f8, is represented in Figure 2. While this mode in not the CTR mode and was designed to avoid its weaknesses, our attack can be applied to the first block of ciphertext. Indeed the first block of message *i* is encrypted as $c_{i,0} = m_{i,0} \oplus E_k(E_{k'}(i))$, where the value $E_k(E_{k'}(i))$ is unique for all the messages encrypted with a given key.

There is a maximum of $2^{32}$ messages encrypted with a given key in 3G, but
this only has a small effect on the complexity of attacks.

<figure><img src="image_135.png" /><figcaption>Fig. 2. f8 mode (*i* is a message counter)</figcaption></figure>

Because of the low usage of 3DES-CTR in SSH, and the difficulty of mounting
an attack against 3G telephony in practice, we did not attempt to demonstrate the
attack in practice, but the setting and complexity of our attacks are comparable
to recent results on the CBC mode with 64-bit ciphers [7].

**4.4 Counter-measures.**

As for many modes of operation, the common wisdom to counter this kind of
attacks asks for rekeying before the birthday bound, i.e. before $2^{n/2}$ blocks.
However rekeying too close to the birthday bound may not be enough. For
example let's consider an implementation of a CTR based mode of operation that
rekeys every $2^{n/2}$ blocks, Using the same model as previously, and a one-block
secret, an optimal attack uses queries $[H_1 \parallel S_1] \parallel [S_2]$ with a half-block header, and queries $[H_1 \parallel H_2] \parallel [S_1 \parallel S_2]$ with a full-block header, where rekeying occurs after $2^{n/2-2}$ queries of each type. To recover $S_1$, we use the known prefix sieving algorithm as previously, but we can only use relations between ciphertext blocks encrypted with the same key. In each session of $2^{n/2}$ blocks, we consider $2^{n-4}$ pairs of ciphertext blocks; on average there are $2^{n/2-4}$ pairs with the correct prefix used for sieving. Since we need $n/2 \cdot 2^{n/2}$ draws to reduce the sieve to a single element with high probability, we use $8n$ sessions, i.e. $8n \cdot 2^{n/2}$ blocks of data in total. The same data can be reused to recover $S_2$ when $S_1$ is known. This should be compared with the previous data complexity of $4\sqrt{n/2} \cdot 2^{n/2}$ in the absence of rekeying.

However, rekeying every $2^{n/2-16}$ blocks makes the data complexity goes up to $2^{35}n$ sessions or $n \cdot 2^{19+n/2}$ blocks to recover the secret block. Notice that the security gain of rekeying is comparable with what is gained in CBC, where rekeying every $2^{n/2-16}$ blocks forces increases the data complexity from $2 \cdot 2^{n/2}$ to $2^{18} \cdot 2^{n/2}$.

# 5 Application to Wegman-Carter MACs

Because the fast convolution algorithm requires fewer assumptions, it can be adapted to other modes of operation based on CTR and particularly to Wegman-Carter type of constructions for MAC. Wegman-Carter MACs use a keyed permutation $E$ and a keyed universal hash function $h$, with $k1$ and $k2$ two private keys. The input is a message $M$ and a nonce $N$, and the MAC is defined as:

$$MAC(N, M) = h_{k1}(M) + E_{k2}(N)$$

Again, the construction requires that all block cipher inputs are different. To apply our attack, we use two fixed message $M$ and $M'$, and we capture many values $MAC(N, M)$ in a list $\mathcal{A}$ and values $MAC(N', M')$ in a list $\mathcal{B}$, all using unique nonces. Then we solve the missing difference problem to recover $h_{k1}(M) - h_{k1}(M')$ as we know that $\forall N \neq N' : E_{k2}(N) - E_{k2}(N') \neq 0$. It is often sufficient to know this difference and the two messages $M$ and $M'$ to recover the key $k_1$. We give two examples with concrete MAC algorithms.

**Galois/Counter Mode.** GCM is an authenticated encryption mode with associated data, combining the CTR mode for encryption and a Wegman-Carter MAC based on polynomial evaluation in a Galois field for authentication. It takes as input a message $M$ that is encrypted and authenticated, and some associated data $A$ that is authenticated but not encrypted. When used with an empty message, the resulting MAC is known as GMAC. In our attack, we use an empty message with one block of authenticated data $A$, so that the tag is computed as:

$$MAC(N, A) = A \cdot H^2 \oplus H \oplus E_k(N),$$

with $H$ the hash key and $(\cdot)$ the multiplication in a Galois Field defined by a public polynomial. So, for two different blocks of authenticated data $A$ and $A'$
we collect $O(\sqrt{n} \cdot 2^{2n/3})$ MACs and perform the fast convolution algorithm to recover $A \cdot H^2 \oplus H \oplus A' \cdot H^2 \oplus H = (A \oplus A') \cdot H^2$. We known $A \oplus A'$ and the field is known so we invert that value and recover $H^2$ then compute the square root and recover the hash key $H$.

**Comparison with previous attacks against GMAC.** There are several known attacks against GCM and GMAC, but none of them seems to allow universal forgery with just $2^{2n/3}$ blocks of data and $2^{2n/3}$ computations. In particular, Handschuh and Preneel [19] gave a weak-key attack, that can also be used to recover the hash key without weak key assumptions, using roughly $2^{n/2}$ messages of $2^{n/2}$ blocks. Later work extended these weak key properties [36,33] but an attack still requires about $2^n$ blocks in total when no assumptions are made about the key. We also note that these attacks require access to a verification oracle, while our attack only uses a MAC oracle.

Some earlier attacks use specific options of the GCM specifications to reach a lower complexity, but cannot be applied with standard-length IV, and tag: Ferguson [14] showed an attack when the tag is truncated, and Joux [23] gave an attack based on non-default IV lengths.

**Poly1305.** Poly1305 [6] is a MAC scheme following the Wegman-Carter construction, using polynomial evaluation modulo the prime number $2^{130} - 5$. It uses a keyed 128-bit permutation (usually AES), and the hash function key, $r$, has 106 free bits (22 bits of the key are set to 0, including in particular the 4 most significant ones). The message blocks are first padded to 129-bit values $c_i$. Then the MAC of a $q$-block message $M$ with nonce $N$ is defined as:

$$T(M, N) = (((c_1 r^q + c_2 r^{q-1} + \dots + c_q r) \bmod 2^{130} - 5) + E_k(N)) \bmod 2^{128}.$$

With the same strategy as above, using two different messages $M$ and $M'$ we recover the missing difference

$$(((c_1 - c'_1)r^q + (c_2 - c'_2)r^{q-1} + \dots + (c_q - c'_q)r) \bmod 2^{130} - 5) \bmod 2^{128}.$$

Moreover, we chose $M$ and $M'$ such that $c_i - c'_i = 0$ and $c_q - c'_q = 1$; since by design, $r < 2^{124}$ the value recovered is simply the hash key $r$.

Notice that Poly1305 doesn't use the XOR operation but a modular addition, and we have to adapt our algorithms to this case. Luckily, the fast convolution algorithm can easily be tweaked. First, we keep the $2n/3$ least significant bits to avoid issues the carry, something the XOR operation doesn't have. Then, when the lists of counters are up, we need to compute their cyclic convolution, which is done with a fast convolution algorithm based on the fast Fourier transform (instead of fast Walsh-Hadamard). Then we verify the value suggested by the lowest counter by running the known prefix algorithm looking for collisions on the least significant bits and sieving the modular subtraction of the most significant bits. This adaptation has similar complexities and proofs than the one described earlier. Moreover, in the case of Poly1305, one can further adapt the algorithms
to take into account the fact that 22 bits of the key $r$ are fixed at 0 effectively reducing the dimension of $S$.

# 6 Proofs and Simulations

In this section we give some theoretical and simulation results that further support the claims we made thus far.

## 6.1 About the Fast Convolution Algorithm

**Proof of query complexity** for the claim made in Section 3.2. Consider, without loss of generality and for blocks of size $n$, that we possess $a \cdot 2^{2n/3}$ blocks of keystream and the same number of blocks of encrypted secret $S$ with $a$ a function of $n$. So in this setting we have $a^2 \cdot 2^{4n/3}$ different XORed-values possible between the two lists, that we will consider as independent and uniformly distributed over $2^n - 1$ values. We will then focus on the $2n/3$ bits truncation, $T(\cdot)$, and ignore the rest. We count the number of occurrences for every truncated values and store them in two lists of size $2^{2n/3}$. Using the fast Walsh-Hadamard transform 3 times, Algorithm 5, we can therefore compute the same counters but for all the XORed-values. We hope that the counter for $T(S)$, the good counter, will be lower than all of the other counters, the bad counters, with probability $\Omega(1)$. In which case we say the algorithm succeeds.

Let $X_i^c$ represents the fact that the $i^{th}$ value truncates to $c$, so that $X_i^c$ follows a Bernoulli distribution and any counter can be written as $X^c = \sum_{i=1}^{a^2 2^{4n/3}} X_i^c$. Now we have to discriminate between the distributions of the good and bad counters:

$$ \text{Good case } c = T(S): \quad \begin{aligned} & \Pr(X_i^{T(S)} = 1) = (2^{n/3} - 1)/2^n = 2^{-2n/3} - 2^{-n} \\ & \implies \mathbf{E}[X^{T(S)}] = 2^{2n/3}a^2 - 2^{n/3}a^2 \end{aligned} $$

$$ \text{Bad case } c \neq T(S): \quad \begin{aligned} & \Pr(X_i^c = 1) = (2^{n/3})/2^n = 2^{-2n/3} \\ & \implies \mathbf{E}[X^c] = 2^{2n/3}a^2 \end{aligned} $$

Now we are interested by the probability that a bad counter gets a value below $\mathbf{E}[X^{T(S)}]$ as a measure of how distinct the distributions are. Using Chernov Bound we get for all $c \neq T(S)$:

$$ \begin{aligned} \Pr(X^c < \mathbf{E}[X^{T(S)}]) &= \Pr(X^c < (1 - 2^{-n/3})2^{2n/3}a^2) \\ &= \Pr(X^c < (1 - 2^{-n/3})\mathbf{E}[X^c]) \\ &\le e^{-(2^{-n/3})^2 \cdot 2^{2n/3}a^2/2} = e^{-a^2/2} \end{aligned} $$

And to compute the probability that no bad counter gets below $\mathbf{E}[X^{T(S)}]$ we will have to assume their independence, which is wrong, but we will come back later to discuss this assumption.
$$ 
\begin{aligned}
\Pr(\forall c \neq T(S) : X^c \geq \mathbf{E}[X^{T(S)}]) &= \prod_{c \neq T(S)} \left(1 - \Pr(X^c < \mathbf{E}[X^{T(S)}])\right) \\
&\geq \left(1 - e^{-a^2/2}\right)^{2^{2n/3}}
\end{aligned}
$$

To conclude, we need to find an $a = a(n)$ such that this probability remains greater than some positive value as $n$ grows. This is clearly achieved with $a = O(\sqrt{n})$ as for example taking $a = \frac{2\sqrt{n}}{\sqrt{3 \cdot \log_2(e)}} \approx 0.96\sqrt{n}$ we get:

$$ 
\begin{aligned}
\Pr(\forall c \neq T(S) : X^c \geq \mathbf{E}[X^{T(S)}]) &\geq (1 - e^{-a^2/2})^{2^{2n/3}} \\
&\geq (1 - 2^{-2n/3})^{2^{2n/3}} \\
&\geq 0.25, \qquad \forall n \geq 3/2
\end{aligned}
$$

Therefore we can bound the probability of success by the events '$X^{T(S)} < \mathbf{E}[X^{T(S)}]$', probability $\approx 1/2$, and '$\forall c \neq T(S) : X^c \geq \mathbf{E}[X^{T(S)}]$', probability at least $1/4$. Then we indeed have a probability of at least $1/8$ of having a successful algorithm. We can conclude that with $O(n \cdot 2^{4n/3})$ XORed-values the algorithm has probability $\Omega(1)$ of succeeding.

Notice that this requires lists of size $O(\sqrt{n} \cdot 2^{2n/3})$ but for the proof we only need the total number of pairs between the two lists. So we can break the requirement that the two lists are of comparable sizes as long as the product of their sizes sum up to the order of required values.

On the independence of the counters, this is obviously wrong as they are bound by the relation $\sum_c X^c = a^2 2^{4n/3}$. However this relation becomes looser and looser as $n$ grows so the approximation obtained should still be correct asymptotically. Moreover, the covariances implied are negative i.e. knowing one draw is big makes the other draws smaller in expectation to compensate. Small negative covariances will make the distribution look more evenly distributed in the sense that we can't observe too many extreme events in a particular direction which is good for the success rate of the algorithm. So the assumption of independence may be a conservative one for this complexity analysis.

**Simulation results.** We ran simulations for block sizes $n = 12, 24, 32$ and $48$ bits, so that we could do some statistical estimations of the success probability for this attack. We first create two lists of same size, one of raw keystream output and one XORed with an $n$-bit secret $S$. Then we pass the two lists in algorithm 5 counting over $n' = 2n/3$ bits (unless specified otherwise) to get a list of counters for each possible XOR outputs on those $n'$ bits. Then the expected behaviour of the attack would be to look for a solution whose $n'$ first bits correspond to the position of the lowest counter and test this hypothesis with algorithm 3. If it returns a unique value then this is $S$ and we are done, if it returns an empty set then test with the position of the second lowest counter, etc. We can therefore
know the number of key candidates that would be required to recover $S$ and, over many trials, have an estimation of the probability of success after a given number of candidates in these parameters.

For block sizes of 12 and 24 we simulated a permutation simply by shuffling a range into a list. For bigger sizes of 32 and 48 we used the Simon lightweight cipher from the NSA [3] as that is one of the rare block cipher who can act on 48-bit blocks. We could quickly gather 10 000 runs for each setting except for the 48-bit blocks simulation where we gathered 756 runs.

In general we observe in Figure 6 that the algorithm has a good chance of success with the first few candidates when using the suggested parameters. Moreover the sensibility with respect to the data complexity (Figure 4) and to the number of bits counted over (Figure 5) is fairly high. These results back up our complexity analysis and are a good indication that no big constant is ignored by the $O()$ notation.

On the speed at which the probability increases we realized that, despite the log scale on the $x$ axis, the curves take a straight (Figure 3) or concave shape (Figure 5 6). That means that the probability of success with the next key candidate decreases very quickly with the number of key candidates already tested and proved wrong. For example for $n = 48$ bits (Figure 6) over 756 trials the right key candidate was in the 2048 lowest counters in 98.1% of the time but the worst case found was 1 313 576 and these “very bad” cases push the mean rank of the right key candidate to 2287 and its sample variance to 2 336 937 008.

For $n = 48$ bits, one simulation took us 40 minutes over 10 cores (each step is highly parallelizable), and 64 gibibytes of RAM for the counters lists.

## 6.2 About the Known Prefix Sieving Algorithm

We consider two particular settings for the known prefix sieving algorithm and the corresponding block splitting attack, with $z = n/2$ and $z = 1$.

**Theoretical bound.** We first give a theoretical lower bound to the probability of success of the sieving when $\dim(S) = n/2$ (i.e. $z = n/2$), depending on the query complexity. Every partial collision found helps us to sieve. After collecting many blocks of keystream and encryption of $S$ let $|A| \cdot |B| =: \alpha 2^n$ for some $\alpha$. Thus we get $\alpha 2^n/2^{n/2} = \alpha 2^{n/2}$ partial collisions in expectation. More precisely, the Chernoff bound gives us a lower bound for the probability of finding at least $(1 - \delta)\alpha 2^{n/2}$ collisions:

$$p \ge 1 - \left( \frac{e^{-\delta}}{(1 - \delta)^{(1 - \delta)}} \right)^{\alpha 2^{n/2}}$$

for any $\delta > 0$.

We see one partial collision as a draw in the coupon collector problem. One can use the formula in [34] for the tail of coupon collector problem probability
<figure><img src="image_136.png" /><figcaption>Fig. 3. Results for lists size of $3 \cdot 2^{2n/3}$</figcaption></figure>

<figure><img src="image_137.png" /><figcaption>Fig. 4. Results for $n = 24$ bits</figcaption></figure>

<figure><img src="image_138.png" /><figcaption>Fig. 5. Results for $n = 32$ bits; $\sqrt{n}2^{2n/3} \sim 5.66 \cdot 2^{2n/3}$ data</figcaption></figure>

<figure><img src="image_139.png" /><figcaption>Fig. 6. Results for $\sqrt{n}2^{2n/3}$ data; counting over $2n/3$ bits</figcaption></figure>
distribution to estimate the chance of success after obtaining $\beta \cdot 2^{n/2}$ partial collisions:

$$p \geq 1 - 2^{-\beta/\ln(2)+n/2}$$

which is positive whenever $\beta \geq n/2 \cdot \ln(2)$.

Therefore we bound the probability of success when collecting $|\mathcal{A}| \cdot |\mathcal{B}| = \alpha 2^n$ pairs as the probability of obtaining at least $(1 - \delta)\alpha 2^{n/2}$ partial collisions multiplied by the probability of success after sieving $(1 - \delta)\alpha 2^{n/2}$ values:

$$p \geq \left(1 - \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right)^{\alpha 2^{n/2}}\right) \cdot \left(1 - 2^{-(1-\delta)\alpha/\ln(2)+n/2}\right)$$

In particular, with two lists of size $\sqrt{n/2} \cdot 2^{n/2}$ (i.e. $\alpha = n/2$), we get $p \geq 0.99$ as long as $n \geq 32$ (using $\delta = 2^{-8}$).

<figure><img src="image_140.png" /><figcaption>**Fig. 7.** Probability of success of the known prefix sieving knowing $2^{32}$ encryptions of a 32-bit secret against the number of chunks of $2^{32}$ keystream blocks of size $n = 64$ bits used.</figcaption></figure>

**Simulation results.** We ran simulations with a block size $n = 64$ bits, and a secret $S$ of size $n/2 = 32$ bits, using the Tiny Encryption Algorithm (TEA [37]) in CTR mode to encrypt the data. We create two lists, the keystream output list $a_i \in \mathcal{A}$, and the encryptions $b_j = a_j \oplus (\bar{0} \parallel S) \in \mathcal{B}$. We first produce and sort a list $\mathcal{B}$ with $2^{32}$ elements then produce, sort and sieve iteratively several lists $\mathcal{A}$ with $2^{32}$ elements, until the secret $S$ is the only one remaining in the sieve.

One simulation runs in around 20 minutes over 36 cores, as every steps are trivially parallelizable: encryption, sorting and sieving. We ran 3700 simulations
and tracked how many chunks of $2^{n/2} = 2^{32}$ keystream outputs were needed for sieving. The coupon collector problem predicts that one will need on average $n/2 \cdot \ln(2) \cdot 2^{n/2}$ partial collisions which will be obtained after $n/2 \cdot \ln(2) \approx 22.18 < 23$ rounds in expectation. And indeed the simulations showed a 64.5% probability of success after 23 iterations. Figure 7 shows the convergence between the theoretical lower bound and the simulated probabilities. We also noticed that the discrepancy in the number of rounds required is largely due to the last few candidates remaining in the sieve. If we decided the attack is successful when we are left with less than 1000 potential candidates for the secret then the algorithm successfully finishes after 16 rounds every time. In fact after 16 rounds the number of candidates left varies from 419 to 560 in all the simulations we have run.

**Bit by bit secret recovery.** We also want to study the complexity of recovering the secret $S$ bit by bit as an extreme case of the block splitting scenario described in Section 4.2. For simplicity, we consider a setting where one query returns a block of keystream and the encryption of $0 \parallel s_i$ with an unknown bit $s_i$. We are interested in the query complexity for recovering $n$ bits of secret one bit at a time; that is we need to know the first bit to ask for the second one, etc. Clearly this can be done in $O(n \cdot 2^{n/2})$ queries by repeating $n$ times the attack on one bit. But the intuition is that we may need less and less queries to uncover the next bit as we go forward and accumulate blocks of keystream.

Let:

$U_i \leftarrow$ The expected number of encryption of $0 \parallel s_i$ to recover $s_i$.

$K_i \leftarrow$ The expected number of raw keystream outputs to recover $s_i$.

From the definition of a query, the above description and because each time we find a bit of secret we can deduce a range of keystream blocks for the next step we have the relations:

$$K_1 = U_1 \tag{1}$$

$$K_{i+1} = K_i + U_i + U_{i+1} \quad \text{for } i \ge 1 \tag{2}$$

$$K_i \cdot U_i = 2^n \quad (\text{in expectation}) \tag{3}$$

We consider the following proposition:

$$P_i : U_i = 2^{n/2}(\sqrt{i} - \sqrt{i-1}),$$

and, using (2), when $P_k$ true for all $k \le i$ we have:

$$K_i = 2 \sum_{k=1}^{i-1} U_k + U_i = 2^{n/2}(\sqrt{i} + \sqrt{i-1}).$$
Moreover (1) and (3) imply $K_1 = U_1 = 2^{n/2}$ so $P_1$ is true. Now suppose $P_k$ true for all $k \le i$, let's prove it holds for $P_{i+1}$:

$$ 
\begin{align*}
& K_{i+1} \cdot U_{i+1} = 2^n && \text{by (3)} \\
\Rightarrow & U_{i+1}^2 + (K_i + U_i) \cdot U_{i+1} - 2^n = 0 && \text{by (2)} \\
\Rightarrow & U_{i+1}^2 + 2^{n/2} \cdot 2\sqrt{i} \cdot U_{i+1} - 2^n = 0 && \text{by } P_i \\
\Rightarrow & U_{i+1} = 2^{n/2}(\sqrt{i+1} - \sqrt{i}) && \text{as } U_{i+1} \ge 0 \\
\Rightarrow & P_{i+1} \text{ is true.} &&
\end{align*}
$$

Now that we have a closed form for $U_i$ we can deduce the expected number of queries needed to recover $n$ bits of secret by summing over as $\sum_{i=1}^n U_i = 2^{n/2}\sqrt{n}$.

Therefore the query complexity is really $O(\sqrt{n} \cdot 2^{n/2})$ ignoring a constant depending on the length of a query. Notice that this complexity is the same as when sieving $S$ as a whole showing that we don't grow the query complexity by more than a constant with this strategy.

## Conclusion

In this work, we have studied the missing difference problem and its relation to the security of the CTR mode. We have given efficient algorithms for the missing difference problem in two practically relevant cases: with an arbitrary missing difference, and when the missing difference is known to be in some low-dimension vector space. These algorithms lead to a message-recovery attack against the CTR mode with complexity $\tilde{O}(2^{n/2})$, and a universal forgery attack against some Carter-Wegman MACs with complexity $\tilde{O}(2^{2n/3})$.

In particular, we show that message-recovery attacks against the CTR mode can be mounted with roughly the same requirements and the same complexity as attacks against the CBC mode. While both modes have similar security proofs, there was a folklore assumption that the security loss of the CTR mode with large amounts of data is slower than in the CBC mode, because the absence of collision in the CTR keystream is harder to exploit than CBC collisions [15, Section 4.8.2]. Our results show that this is baseless, and use of the CTR mode with 64-bit block ciphers should be considered unsafe (unless strict data limits are in place). As a counter-measure, we recommend to use larger block sizes, and to rekey well before $2^{n/2}$ blocks of data. Concrete guidelines for 128-bit block ciphers have been given by Luykx and Paterson [26]. Alternatively, if the use of small block is required, we suggest using a mode with provable security beyond the birthday bound, such as CENC [21,22].

Our missing difference attacks against CTR and the collision attacks against CBC are two different possible failure of block cipher modes beyond the birthday bound. They exploit different properties of the modes but result in similar attacks. These techniques can be used against other modes of operations (OFB, CFB, ...), and most of them will be vulnerable to at least one the attacks, unless they have been specially designed to provide security beyond the birthday bound.
Acknowledgement

Part of this work was supported by the French DGA, and the authors are partially
supported by the French Agence Nationale de la Recherche through the BRUTUS
project under Contract ANR-14-CE28-0015.

References

1. Albrecht, M.R., Degabriele, J.P., Hansen, T.B., Paterson, K.G.: A surfeit of SSH cipher suites. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16. pp. 1480–1491. ACM Press (Oct 2016)

2. AlFardan, N.J., Bernstein, D.J., Paterson, K.G., Poettering, B., Schuldt, J.C.N.: On the Security of RC4 in TLS. In: King, S.T. (ed.) USENIX Security 2013. pp. 305–320. USENIX Association (2013)

3. Beaulieu, R., Shors, D., Smith, J., Treatman-Clark, S., Weeks, B., Wingers, L.: SIMON and SPECK: Block ciphers for the internet of things. Cryptology ePrint Archive, Report 2015/585 (2015), http://eprint.iacr.org/2015/585

4. Bellare, M., Kohno, T., Namprempre, C.: The Secure Shell (SSH) Transport Layer Encryption Modes. IETF RFC 4344 (2006)

5. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th FOCS. pp. 394–403. IEEE Computer Society Press (Oct 1997)

6. Bernstein, D.J.: The poly1305-AES message-authentication code. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 32–49. Springer, Heidelberg (Feb 2005)

7. Bhargavan, K., Leurent, G.: On the practical (in-)security of 64-bit block ciphers: Collision attacks on HTTP over TLS and OpenVPN. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16. pp. 456–467. ACM Press (Oct 2016)

8. Biham, E., Shamir, A.: Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology 4(1), 3–72 (1991)

9. Daemen, J., Knudsen, L.R., Rijmen, V.: The block cipher Square. In: Biham, E. (ed.) FSE’97. LNCS, vol. 1267, pp. 149–165. Springer, Heidelberg (Jan 1997)

10. Diffie, W., Hellman, M.E.: Privacy and authentication: An introduction to cryptography. Proceedings of the IEEE 67(3), 397–427 (1979)

11. 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)

12. Duong, T., Rizzo, J.: Here come the ⊕ ninjas (2011)

13. Dworkin, M.: Recommendation for Block Cipher Modes of Operation: Methods and Techniques. NIST Special Publication 800-38A, National Institute for Standards and Technology (Dec 2001)

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

15. Ferguson, N., Schneier, B., Kohno, T.: Cryptography engineering: design principles and practical applications. John Wiley & Sons (2011)

16. DES modes of operation. NIST Special Publication 81, National Institute for Standards and Technology (Dec 1980)
17. 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)

18. 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)

19. Handschuh, H., Preneel, B.: Key-recovery attacks on universal hash function based MAC algorithms. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 144-161. Springer, Heidelberg (Aug 2008)

20. Hoang, V.T., Reyhanitabar, R., Rogaway, P., Vizár, D.: Online authenticated-encryption and its nonce-reuse misuse-resistance. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part I. LNCS, vol. 9215, pp. 493-517. Springer, Heidelberg (Aug 2015)

21. 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)

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

23. Joux, A.: Authentication failures in NIST version of GCM. Comment to NIST (2006), http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/800-38_Series-Drafts/GCM/Joux_commments.pdf

24. 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)

25. 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)

26. Luykx, A., Paterson, K.G.: Limits on authenticated encryption use in TLS (march 2016), http://www.isg.rhul.ac.uk/~kp/TLS-AEbounds.pdf

27. Matsui, M.: Linear cryptoanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT'93. LNCS, vol. 765, pp. 386-397. Springer, Heidelberg (May 1994)

28. McGrew, D.: Impossible plaintext cryptanalysis and probable-plaintext collision attacks of 64-bit block cipher modes. Cryptology ePrint Archive, Report 2012/623. Accepted to FSE 2013. (2012), http://eprint.iacr.org/2012/623

29. McGrew, D.A., Viega, J.: The security and performance of the Galois/counter mode (GCM) of operation. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 343-355. Springer, Heidelberg (Dec 2004)

30. 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)

31. 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)

32. 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)

33. Procter, G., Cid, C.: On weak keys and forgery attacks against polynomial-based MAC schemes. Journal of Cryptology 28(4), 769-795 (Oct 2015)

34. Rajeev, M., Prabhakar, R.: Randomized Algorithms. Cambridge University Press (1995)
35. Rogaway, P.: Evaluation of some blockcipher modes of operation (2011)

36. Saarinen, M.J.O.: Cycling attacks on GCM, GHASH and other polynomial MACs and hashes. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 216–225. Springer, Heidelberg (Mar 2012)

37. Wheeler, D.J., Needham, R.M.: TEA, a tiny encryption algorithm. In: Preneel, B. (ed.) FSE’94. LNCS, vol. 1008, pp. 363–366. Springer, Heidelberg (Dec 1995)
# Generic Attacks against
Beyond-Birthday-Bound MACs

Gaëtan Leurent¹, Mridul Nandi², and Ferdinand Sibleyras¹

¹ Inria, France

`{gaetan.leurent,ferdinand.sibleyras}@inria.fr`

² Indian Statistical Institute, Kolkata
mridul.nandi@gmail.com

**Abstract.** In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to $2^{2n/3}$ queries, but there are no known attacks with less than $2^n$ queries.

We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with $O(2^{3n/4})$ queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above $2^n$, but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito. Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity $\tilde{O}(2^{6n/7})$. As far as we know, this is the first attack with complexity below $2^n$ against a deterministic beyond-birthday-bound secure MAC.

As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

**Keywords:** Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security

# 1 Introduction

Message authentication codes (or MACs) ensure the authenticity of messages in the secret-key setting. They are a core element of real-world security protocols such as TLS, SSH, or IPSEC. A MAC takes a message (and optionally a nonce) and a secret key to generate a tag that is sent with the message. Traditionally, they are classified into three types: deterministic, nonce-based, and probabilistic.

Deterministic MAC designs are the most popular, with widely used constructions based on block-cipher (CBC-MAC [13,4], OMAC [18], PMAC [5], LightMAC [29], ...) and hash functions (HMAC [2], NMAC [2], NI-MAC [1], ...). However, there is a generic forgery attack against all deterministic iterated MACs, using collisions in
the internal state, due to Preneel and van Oorschot [37]. Therefore, these MACs
only achieve security up to the birthday bound, i.e. when the number of queries
by the adversary is bounded by $2^{n/2}$, with $n$ the state size. This is equivalently
called $n/2$-bit security.

One way to increase the security is to use a *nonce*, a unique value provided
by the user (in practice, the nonce is usually a counter). This approach has been
pioneered by Wegman and Carter [41] based on an earlier work by Gilbert *et al.* [15]. Later a few follow ups like EDM and EWCDM [7], and Dual EDM [30] have
been proposed to achieve beyond birthday security.

Alternatively, a probabilistic MAC uses a random coin for the extra value,
which is usually called a *salt*, and must be transmitted with the MAC. Probabilistic MACs have the advantage that they can stay secure when called with
the same input twice, and don't require a state to keep the nonce unique. Some
popular probabilistic MAC constructions are XMACR [3], RMAC [22] and EHtM [31].
In particular, RMAC and EHtM have security beyond the birthday bound.

However, deterministic MACs are easier to use in practice, and there has been
an important research effort to build deterministic MAC with security beyond
the birthday bound, using an internal state larger than the primitive size. In
particular, several constructions use a $2n$-bit internal state so that collisions in
the state are only expected after $2^n$ queries. Yasuda first proposed SUM-ECBC [42],
a beyond birthday bound (BBB) secure deterministic MAC that achieves $2n/3$-
bit security. However, this construction has rate 1/2 and later Yasuda himself
proposed one of the most popular BBB secure MAC PMAC+ [43] achieving rate 1.
Later several other constructions like 3kf9 [44], LightMAC+ [33], GCM-SIV2 [20],
and single key PMAC+ [9] have been proposed. Interestingly, all the above designs
share a common structure: a double-block universal hash function outputs a $2n$-
bit hash value (seen as two $n$-bit halves), and a finalization function generates the
tag by XORing encrypted values of the two $n$-bit hash values. This structure has
been called double-block-hash-then-sum, and it will be the focus of our paper.

More recently, variants of PMAC+ based on tweakable block-cipher have also
been proposed, such as PMAC_TBC [32], PMACx [27], ZMAC [21], and ZMAC+[28].

**Our results.** We focus on the security of deterministic block-cipher based
MACs with security beyond the birthday bound and double-block hash con-
struction. Several previous works have been focused on security proofs, showing
that they are secure up to $2^{2n/3}$ queries [43,44,20,9,42,33]. For most of these con-
structions, the advantage of an adversary making $q$ short queries is bounded by
$O(q^3/2^{2n})$. Recently, Naito [34] gave an improved security proof for LighMAC+,
with advantage at most $O(q_t^2 q_v/2^{2n})$, with $q_t$ MAC queries and $q_v$ verification
queries. In particular, this would prove security up to $2^n$ when the adversary
can only do a single verification query.

In this work, we take the opposite approach and look for generic attacks
against these modes. We use a cryptanalysis technique that can be seen as a
generalisation of the collision attack of Preneel and van Oorschot [37]. Instead
of looking for a pair of messages so that the full state collides, we look for a
quadruple of messages, which can be seen either as two pairs colliding on the first