computed [DMR07, KPS15], or even collisions on the whole SHA-1 compression function [SKP16], which eventually led to the announcement in 2017 of the first SHA-1 collision [SBK+17]. The best known results are listed in Table 1: the best collision attack against SHA-1 has complexity $2^{61}$ on CPU [Ste13], and $2^{64.7}$ when implemented on GPU [SBK+17], while the best chosen-prefix collision attack has complexity $2^{77.1}$ [SKP16].

Even though SHA-1 has been broken in 2004, it is still deployed in many security systems, because collision attacks do not seem to directly threaten most protocols, and migration is expensive. Web browsers have recently started to reject certificates with SHA-1 signatures, but there are still many users with older browsers, and many protocols and softwares that allow SHA-1 signatures. Concretely, it is still possible to buy a SHA-1 certificate from a trusted CA, and many email clients accept a SHA-1 certificate when opening a TLS connection. SHA-1 is also widely supported to authenticate TLS handshake messages.

**Main SHA-1 cryptanalysis techniques.** Attacks against SHA-1 are based on differential cryptanalysis, where an attacker manages to somewhat control the output of the compression function. Several important ideas were used to turn differential cryptanalysis into an effective tool against hash functions:

**Linearization [CJ98].** In order to build differential trails with high probability, a linearized version of the step function is used. Differential trails with a low-weight output difference $\delta_O$ can be used to find near-collisions in the compression function (i.e. two outputs that are close to a collision, the distance metric being for example the Hamming distance).

**Message modification [BC04, WYY05a]** In a differential attack against a hash function, the attacker can choose messages that directly satisfy some of the constraints of the path, because there is no secret key. While the conditions in the first steps are easy to satisfy, more advanced techniques have been introduced to extend the usage of these degree of freedom to later rounds in order to speed-up collision search: neutral bits (firstly introduced for cryptanalysis SHA-0 [BC04, BCJ+05]), message modifications [WYY05a] and boomerangs/tunnels [Kli06, JP07].

**Non-linear trails [WYY05a].** In order to get more flexibility on the differential trails, the first few steps can use non-linearity instead of following the constraints of the linearized step function. This does not affect the complexity of the search for conforming messages (thanks to messages modification techniques), but it allows to build trails from an arbitrary input difference to a good fixed output difference $\delta_O$ (or its opposite).

**Multi-block technique [CJ98, WYY05a].** The multi-block technique takes advantage of the Davies-Meyer construction used inside the compression function. Indeed, it can be written as $h(x, m) = x + E_m(x)$ where E is a block cipher, and + denotes some group operation. Because of this feed-forward, an attacker can use several differential trails in E, and several near-collisions blocks, to iteratively affect the internal state. In particular, using non-linearity in the first steps, he can derive two related trails $0 \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and
$\delta_O \stackrel{-\delta_M}{\rightsquigarrow} -\delta_O$ in $E$ from a single linear trail, by swapping the message pair. When conforming messages are found for each block, this leads to a collision because the internal state differences cancel out (see Figure 1).

**Birthday phase for chosen-prefix collisions [SLdW07, Ste13].** Differen- tial techniques have also been used for chosen-prefix collision attacks. An attacker can relax the last steps of the differential trail to allow a set $\mathcal{D}$ of output differences rather than a single $\delta_O$. He can also use several differen- tial trails, and use the union of the corresponding sets. Starting from two different prefixes $P, P'$, the chosen-prefix collision attack has two stages (see Figure 2):

- In the *birthday stage*, the attacker uses a generic collision search with message blocks $m_0, m'_0$ to reach a difference $\delta = H(P' \| m'_0) - H(P \| m_0)$ in $\mathcal{D}$ with complexity roughly $\sqrt{\pi \cdot 2^n / |\mathcal{D}|}$.

- In the *near-collision stage*, he builds a differential trail $\delta \rightsquigarrow -\delta$ using non-linearity in the first steps, and searches a conforming message to build the chosen-prefix collision.

**Multi-block for chosen-prefix collisions [SLdW07].** If a collection of differ- ential trails affecting separate parts of the internal state is available, chosen- prefix collision attacks can be greatly improved. In particular, if an arbi- trary input difference $\delta_R$ can be decomposed as $\delta_R = -(\delta_O^{(1)} + \delta_O^{(2)} + \cdots + \delta_O^{(r)})$, where each $\delta_O^{(i)}$ can be reached as the output of a differential trail, the attacker just has to find near-collision blocks with output differences $\delta_O^{(1)}, \dots, \delta_O^{(r)}$ (see Figure 3).

Alternatively, if this only covers a subset of input differences, the multi-block technique is combined with a birthday stage.

**Our contributions.** In this work, we describe new chosen-prefix collision at- tacks against the MD-SHA family, using several improvements to reduce the com- plexity.

1. The main improvement comes from how we use multiple near-collision blocks. For instance, using two blocks we can start from any difference in the set $S := \{\delta_1 + \delta_2 | \delta_1, \delta_2 \in \mathcal{D}\}$, and cancel it iteratively with a first block following a trail $\delta_1 + \delta_2 \rightsquigarrow -\delta_1$ and a second block following a trail $\delta_2 \rightsquigarrow -\delta_2$ (see Figure 4). The set $S$ grows with the number of blocks: this reduces the cost of the birthday search in exchange for a more expensive near-collision stage. While there are previous chosen-prefix collision attacks using several near- collision blocks [LPRR07, Pey07, SLdW07, SSA$^+$09, MRS15], these attacks use a collection of differential trails to impact different parts of the state (each block uses a different trail). On the opposite, our technique can be used with a single differential trail, or a collection of trails without any special property. In particular, previous chosen-prefix collision attacks based on a single trail (against SHA-1 [Ste13] and MD5 [SSA$^+$09, Section 6]) used only one near-collision block.
<figure><img src="image_86.png" /><figcaption>**Fig. 1.** 2-block collision attack using a linear trail $\delta_I \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and two non-linear trails $0 \rightsquigarrow \delta_I$ and $\delta_O \rightsquigarrow -\delta_I$. Green values between bracket represent differences in the state.</figcaption></figure>

<figure><img src="image_87.png" /><figcaption>**Fig. 2.** Single-block chosen-prefix collision attack with a birthday stage. The linear trail $\delta_I \rightsquigarrow \delta_O$ is relaxed to reach a set $S$ of feasible differences.</figcaption></figure>

<figure><img src="image_88.png" /><figcaption>**Fig. 3.** Multi-block chosen-prefix collision attack. We assume that an arbitrary difference $\delta_R$ can be decomposed as $\delta_R = -(\delta_O^{(1)} + \delta_O^{(2)} + \cdots + \delta_O^{(r)})$, where each $\delta_O^{(i)}$ can be reached as the output of a differential trail.</figcaption></figure>
2. In addition, we use a clustering technique to optimize the near-collision stage, taking advantage of multiple ways to cancel a given difference. For instance, let's assume that we have to cancel a difference $δ$ in the internal state that can be written in two different ways: $δ = δ_1 + δ_2 = δ'_1 + δ'_2$, with $δ_1, δ'_1, δ_2, δ'_2 \in D$, knowing trails $δ \rightsquigarrow -δ_1$ and $δ \rightsquigarrow -δ'_1$ with the same message constraints. Then, an attacker can target simultaneously $-δ_1$ and $-δ'_1$ for the first near-collision block (and use either a trail $δ_2 \rightsquigarrow -δ_2$ or $δ'_2 \rightsquigarrow -δ'_2$ for the second block, depending on the first block found). This can reduce the cost of finding the first block by a factor two.

This technique can be seen as a generalization of an optimisation used for collision attacks with two blocks, where the first is less constrained and several output differences are allowed (for instance the **SHA-1** collision attack of [Ste13] allows 6 output differences, so that the first block is 6 times less expensive than the second).

Using these techniques, we obtain significant improvements to chosen-prefix collision attacks against MD5 and **SHA-1**.

**Application to MD5.** We use multiple near-collision blocks to improve the complexity of the chosen-prefix collision attack with a single near-collision block given in [SSA+09, Section 6]. We start with the same differential trail, and a set $D$ of size $2^{25.2}$, built in the same way. Using two near-collision blocks, we can target the set $S := \{δ_1 + δ_2 | δ_1, δ_2 \in D\}$ which contains $2^{37.1}$ elements. This leads to an attack with complexity roughly $\sqrt{\pi \cdot 2^{128}/2^{37.1}} \approx 2^{46.3}$, while the best previous attack with two blocks or less required $2^{53.2}$ MD5 computations. However, the best chosen-prefix collision attack against MD5 is still the attack from [SSA+09] with complexity $2^{39.1}$ using 9 near-collision blocks.

**Application to SHA-1.** For **SHA-1**, we start with the attack of Stevens [Ste13], and after using several improvements we obtain a chosen-prefix collision attack with estimated complexity between $2^{66.9}$ and $2^{69.4}$ **SHA-1** computations. This is within a small factor of the complexity of a plain collision attack, estimated at $2^{64.7}$ on average [WYY05a, SBK+17], and orders of magnitude better than the $2^{77.1}$ computations cost of the currently best known chosen-prefix collision attack [Ste13] on **SHA-1**. We have conducted tests to check that our assumptions are indeed verified in practice.

First, we use a more relaxed version of the differential trail than used in [Ste13], so that we have a set $S$ of size 8768 rather than 192. This directly reduces the attack cost by a factor 6.75, down to $2^{74.3}$. Next, we use the multi-block technique to build a large set $S$ and to reduce further the cost of the birthday stage. Using a set $S$ of size $2^{29.4}$ with a near-collision cost at most $12 \times 2^{64.7}$, this reduces the cost of the attack down to $2^{68.6}$ (with an optimistic estimate). Finally, we use the clustering technique to reduce the near-collision cost. After optimization, we have a set $S$ of $2^{32.67}$ differences that can be reached with a maximum cost of $3.5 \times 2^{64.7}$ (with an optimistic estimate), leading to a full attack with complexity $2^{66.9}$ — about five times more expensive than the collision attack.
<table><caption>**Table 1.** Comparison of previous and new cryptanalysis results on MD5 and SHA-1. A free-start collision is a collision or the compression function only, where the attacker has full control on all the primitive's inputs. Complexities in the table are given in terms of SHA-1 equivalents on a GTX-970 GPU (when possible).</caption><thead><tr><th>Function</th><th>Collision type</th><th>Complexity</th><th>Ref.</th></tr></thead><tbody><tr><td rowspan="4">SHA-1</td><td>free-start collision</td><td>2<sup>57.5</sup></td><td>[SKP16]</td></tr><tr><td>collision</td><td>2<sup>69</sup></td><td>[WYY05a]</td></tr><tr><td>chosen-prefix collision</td><td>2<sup>64.7</sup></td><td>[Ste13, SBK<sup>+17</sup>]<sup>a</sup></td></tr><tr><td></td><td>2<sup>77.1</sup></td><td>[Ste13]</td></tr><tr><td></td><td>2<sup>66.9</sup> — 2<sup>69.4</sup></td><td>New</td></tr><tr><td rowspan="5">MD5</td><td>collision</td><td>2<sup>40</sup></td><td>[WY05]</td></tr><tr><td>chosen-prefix collision</td><td>2<sup>16</sup></td><td>[SSA<sup>+09</sup>]</td></tr><tr><td>chosen-prefix collision (9 blocks)</td><td>2<sup>39.1</sup></td><td>[SSA<sup>+09</sup>]</td></tr><tr><td>chosen-prefix collision (3 blocks)</td><td>2<sup>49</sup></td><td>[SSA<sup>+09</sup>]</td></tr><tr><td>chosen-prefix collision (1 block)</td><td>2<sup>53.2</sup></td><td>[SSA<sup>+09</sup>]</td></tr><tr><td></td><td>chosen-prefix collision (2 blocks)</td><td>2<sup>46.3</sup></td><td>New</td></tr></tbody></table>

Our result is surprising since we show that the cost to find a chosen-prefix collision for SHA-1 is not much more than a simple collision search. Moreover our work has a strong impact in practice as chosen-prefix collision attacks are much more dangerous than simple collisions (see for example the case of MD5 [SSA+09]). This is yet another warning that SHA-1 should be totally removed from any security product as soon as possible. The thinking “a collision attack is not directly exploitable, thus we are fine” is clearly wrong for SHA-1, and we give a proof here.

Our method is in essence quite generic, even though a lot of details have to be taken care of in order to make it work. Since most collision attacks on members of the MD-SHA family are built on the same principles as SHA-1 attacks, we believe similar ideas would apply and a collision attack can probably be transformed into a chosen-prefix collision attack for a reasonable extra cost factor. We do not foresee any reason why this technique would not apply to non MD-SHA hash functions as well (except wide-pipe hash functions which would make the birthday part too costly).

**Outline.** We first consider the impact of this result and give some recommendations in Section 2. Then, we describe SHA-1 and previous cryptanalysis works on this hash function in Section 3. The generic high-level description of our attack is given in Section 4, while the details regarding its application to MD5 and SHA-1 are provided in Sections 5 and 6, respectively. Eventually, we conclude and propose future works in Section 7.

<footnote>a The attack has a complexity of $2^{61}$ on CPU, and $2^{64.7}$ on GPU</footnote>
## 2 Implications and Recommendations

Our work shows that finding a chosen-prefix collision is much easier than previously expected, and potentially not much harder than a normal collision search for SHA-1. As a real collision has already been computed for this hash function, one can now assume that chosen-prefix collisions are reachable even by medium funded organisations. Since a chosen-prefix collision attack can break many widely used protocols, we strongly urge users to migrate to SHA-2 or SHA-3, and to disable SHA-1 to avoid downgrade attacks.

**Cost Estimation.** We use the same estimation process as in [SBK+17]. With an optimistic spot-price scenario on g2.8xlarge instances of Amazon EC2, the authors estimated that the workload spent to find the SHA-1 collision was equivalent to a cost of about US$ 110 K, with $2^{63.4}$ SHA-1 equivalent calls on GTX-970 GPUs. We recall that they found the collision with less computations than expected. Using expected computational cost, the average workload required to find a SHA-1 collision is equivalent to a cost of about US$ 275 K, or $2^{64.7}$ SHA-1 calls. An optimistic analysis of our attack leads to a complexity of $2^{66.9}$ SHA-1 equivalent calls on GTX-970 GPUs, corresponding to a cost of US$ 1.2 M, while a more conservative analysis yields a complexity of $2^{69.4}$, or a cost of US$ 7M.

Hardware will improve as well as cryptanalysis and we can expect that collision together with chosen-prefix collision attacks will get cheaper over the years. Migration from SHA-1 to the secure SHA-2 or SHA-3 hash algorithms should now be done as soon as possible, if not already.

**Impact of Chosen-prefix Collisions.** Chosen-prefix collision attacks have been demonstrated already for MD5, and they are much more dangerous that identical-prefix collision attacks, with a strong impact in practice. In particular, chosen-prefix collision attack on MD5 have been used to generate colliding X.509 certificates [SLdW07] and later a rogue certificate authority [SSA+09], undermining the security of websites. They have also been shown to threaten important internet protocols, including TLS, IKE, and SSH using forgery of handshake messages. The SLOTH attacks [BL16] can break various security properties of these protocols using MD5 chosen-prefix collisions, such as client impersonation in TLS 1.2. MD5 has now been removed from most security applications, but the very same threats are now a reality for SHA-1.

However, after these attacks were demonstrated with MD5, countermeasures have been implemented that make the attacks harder to exploit. In particular, CAs are now expected to randomize the serial number of X.509 certificates, which prevents the attack against certificates. Similarly, IKEv2 implementations randomize the SPI of each connection, forcing an attacker to compute the chosen-prefix collision online, after receiving the SPI. Many implementations are also more strict with suspicious looking messages and parameters (such as the cookies used in the IKEv2 attack), and SHA-1 has been deprecated from some protocols (in particular, RFC 8247 deprecates SHA-1 in IKEv2, and SHA-1 has been removed from TLS 1.3).
As far as we understand, attacks with an online chosen-prefix collision should still be possible against the SSH and TLS 1.2 handshake. This is still far from practical<fnref n="4" />, but it is nonetheless significantly easier than it should be with sound cryptographic primitives. Moreover, the IKEv2 and X.509 attacks might still be possible against implementations that still use SHA-1 and don't use proper countermeasures, but this requires a careful analysis of every implementation.

**Usage of SHA-1.** Even if practically broken only very recently, SHA-1 has been theoretically broken since 2004. It is therefore surprising that SHA-1 remains deployed in many security systems. In particular, as long as SHA-1 is *allowed*, even if it is not used in normal operation, an attacker can use weaknesses in SHA-1 to forge a signature, and the signature will be accepted.

First, SHA-1 is still widely used to authenticate handshake messages in secure protocols such as TLS, SSH or IKE. As shown with the SLOTH attack [BL16], this allows various attacks using chosen-prefix collision, such as breaking authentication. These protocols have removed support for MD5 after the SLOTH attack, but SHA-1 is still widely supported. Actually, more than 5% of the web servers from Alexa's top 1M (including *skype.com*) prefer to use SHA-1 to authenticate TLS handshake messages.

An important effort is underway to remove SHA-1 certificates from the Web, and major browsers are now refusing to connect to servers still using SHA-1-based certificates. Yet SHA-1-based certificates remains present: according to scans of the top 1 million websites from Alexa by censys.io, there are still about 35 thousand<fnref n="6" /> servers with SHA-1 certificates out of 1.2 million servers with HTTPS support. SHA-1-based certificates are also used with other protocols: for instance 700 thousand<fnref n="7" /> out of 4.4 million mail servers (with IMAPS) use a SHA-1 certificate. Actually, it is still possible to buy a SHA-1 certificate from a trusted root<fnref n="8" />! Even though recent web browsers reject those certificates, they are accepted by older browsers and by many clients for other protocols. For instance, the “Mail” application included in Windows 10 still accepts SHA-1 certificates without warnings when opening an IMAPS connection.

Unfortunately, many industry players did not consider moving away from SHA-1 a priority, due to important costs and possible compatibility and bug issues induced by this move. An often-heard argument is that a simple collision attacks against a hash function is not very useful for an attacker, because he

<footnote n="4">⁴ Using our attack, it would take a computation power similar to the full bitcoin network to compute a SHA-1 chosen-prefix collision within one minute, and some parts of the attack will be hard to parallelize to such a degree.</footnote>

<footnote n="5">⁵ https://censys.io/domain?q=tags:https+and+443.https.tls signature.hash_ algorithm:sha1</footnote>

<footnote n="6">⁶ https://censys.io/domain?q=tags:https+and+443.https.tls certificate. parsed signature_algorithm.name:SHA1*</footnote>

<footnote n="7">⁷ https://censys.io/ipv4?q=tags:imaps+and+993.imaps.tls.tls certificate. parsed signature_algorithm.name:SHA1*</footnote>

<footnote n="8">⁸ https://www.secure128.com/online-security-solutions/products/ ssl-certificate/symantec/sha-1-private-ssl/</footnote>
doesn't have much control over the colliding messages. Therefore, there seemed to be a long way to go before really useful collision attacks would be found for SHA-1, if ever. Indeed, the current best chosen-prefix collision attack against SHA-1 requires $2^{77.1}$ hash calls [Ste13], thus orders of magnitude harder than the cost of finding a simple collision. Similarly, in the case of MD5, the cost goes from $2^{16}$ to $2^{39}$ for the currently best known collision and chosen-prefix collision attacks. However, this is a dangerous game to play as the history showed that cryptanalysis only keep improving, and attackers will eventually come up with ways to further improve their cryptanalysis techniques. For example, in the case of MD5, collisions for the compression function were found [dB94] in 1993, collisions for the whole hash function were found [WY05] in 2004, colliding X.509 MD5-based certificates were computed [SLdW07] in 2007, and rogue Certificate Authority certificate [SSA+09] was eventually created in 2009.

# 3 Preliminaries

## 3.1 Description of SHA-1

We describe here the SHA-1 hash function, but we refer to [Nat95] for all the complete details.

SHA-1 is a 160-bit hash function based on the well-known Merkle-Damgård paradigm [Dam89, Mer89]. The message input is first padded (with message length encoded) to a multiple of 512 bits, and divided into blocks $m_i$ of 512 bits each. Then, each block is processed via the SHA-1 compression function $h$ to update a 160-bit chaining variable $cv_i$ that is initialised to a constant and public initial value (IV): $cv_0 = IV$. More precisely, we have $cv_{i+1} = h(cv_i, m_{i+1})$. When all blocks have been processed, the hash output is the last chaining variable.

The compression function is similar to other members of the MD-SHA family of hash functions. It is based on the Davies-Meyer construction, that turns a block cipher $E$ into a compression function: $cv_{i+1} = E_{m_{i+1}}(cv_i) + cv_i$, where $E_k(y)$ is the encryption of the plaintext $y$ with the key $k$, and $+$ is a word-wise modular addition.

The internal block cipher is composed of 80 steps (4 rounds of 20 steps each) processing a generalised Feistel network. More precisely, the state is divided into five registers ($A_i, B_i, C_i, D_i, E_i$) of 32-bit each. At each step, an extended message word $W_i$ updates the registers as follows:

$$ 
\left\{ 
\begin{aligned}
A_{i+1} &= (A_i \ll 5) + f_i(B_i, C_i, D_i) + E_i + K_i + W_i \\
B_{i+1} &= A_i \\
C_{i+1} &= B_i \gg 2 \\
D_{i+1} &= C_i \\
E_{i+1} &= D_i
\end{aligned}
\right. 
$$

where $K_i$ are predetermined constants and $f_i$ are boolean functions (in short: IF function for the first round, XOR for the second and fourth round, MAJ for the third round, see Table 2). Since only a single register value is updated
$(A_{i+1})$, the other registers being only rotated copies, we can express the **SHA-1** step function using a single variable:

$$A_{i+1} = (A_i \ll 5) + f_i(A_{i-1}, A_{i-2} \gg 2, A_{i-3} \gg 2) + (A_{i-4} \gg 2) + K_i + W_i.$$

For this reason, the differential trails figures in this article will only represent $A_i$, the other register values at a certain point of time can be deduced directly.

<table><caption>**Table 2.** Boolean functions and constants of **SHA-1**</caption><thead><tr><th>step i</th><th>f<sub>i</sub>(B, C, D)</th><th>K<sub>i</sub></th></tr></thead><tbody><tr><td>0 ≤ i < 20</td><td>f<sub>IF</sub> = (B ∧ C) ⊕ (B̄ ∧ D)</td><td>0x5a827999</td></tr><tr><td>20 ≤ i < 40</td><td>f<sub>XOR</sub> = B ⊕ C ⊕ D</td><td>0x6ed6eba1</td></tr><tr><td>40 ≤ i < 60</td><td>f<sub>MAJ</sub> = (B ∧ C) ⊕ (B ∧ D) ⊕ (C ∧ D)</td><td>0x8fabbcdc</td></tr><tr><td>60 ≤ i < 80</td><td>f<sub>XOR</sub> = B ⊕ C ⊕ D</td><td>0xca62c1d6</td></tr></tbody></table>

The extended message words $W_i$ are computed linearly from the incoming 512-bit message block $m$, the process being called message extension. One first splits $m$ into 16 32-bit words $M_0, \dots, M_{15}$, and then the $W_i$'s are computed as follows:

$$W_i = \begin{cases} M_i, & \text{for } 0 \le i \le 15 \\ (W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}) \ll 1, & \text{for } 16 \le i \le 79 \end{cases}$$

## 3.2 Previous Works

**Collision attacks on SHA-1.** We quickly present here without details the previous advances on **SHA-1** collision search. First results on **SHA-0** and **SHA-1** were obtained by linearizing the compression function and constructing differential trails based on the probabilistic event that difference spreads will indeed happen linearly. These linear trails are generated with a succession of so-called local collisions (small message disturbances whose influence is corrected with other message differences inserted in the subsequent **SHA-1** steps) that follows the **SHA-1** message expansion. However, with this linear construction, impossibilities might appear in the first 20 steps of **SHA-1** (for example due to the $f_{IF}$ boolean function that never behaves linearly in some specific situations) and the cheapest linear trail candidates might not be the ones that start and end with the same difference (which is a property required to obtain a collision after the compression function feed-forward). Thus, since [WYY05a], collision attacks on **SHA-1** are performed using two blocks containing differences. The idea is to simply pick the cheapest linear trail from roughly step 20 to 80, without paying any attention to the $f_{IF}$ constraints or to the input/output differences. Then, the attacker will generate a non-linear differential trail for the first 20 steps in order
to connect the actual incoming input difference to the linear part difference at step 20. With two successive blocks using the same linear trail (just ensuring that the output difference of the two blocks have opposite signs), one can see in Figure 1 that a collision is obtained at the end of the second block.

Once the differential trail is set, the attacker can concentrate on finding a pair of messages that follows it for each successive block. For this, he will construct a large number of messages that follow the trail up to some predetermined step, and compute the remaining steps to test whether the output difference is the required one. The computational cost is minimized by using a simple early-abort strategy for the 16 first steps, but also more advanced amortization methods such as neutral bits [BCJ$^+$05], boomerangs [JP07] or message modification [WYY05a] for a few more steps. Usually, the first 20 or so steps do not contribute the complexity of the attack.

**Chosen-prefix collision attacks.** The first concrete application of a chosen-prefix collision attack was proposed in [SLdW07] for MD5. This work was also the first to introduce a birthday search phase in order to find such collisions. The idea is to process random message blocks after the challenged prefixes, until the chaining variable difference $\delta$ belongs to a large predetermined set $S$. Since the message blocks after each prefix are chosen independently, this can be done with birthday complexity $\sqrt{\pi \cdot 2^n |S|}$. Then, from that difference $\delta$, the authors eventually manage to reach a collision by slowly erasing the unwanted difference bits by successfully applying some near-collision blocks. We note that the starting difference set $S$ during the birthday phase must not be too small, otherwise this phase would be too costly. Moreover, the near-collisions blocks must not be too expensive either, and this will of course depend on the cryptanalysis advancements of the compression function being studied.

Finally, using also this two-phase strategy, in [Ste13] is described a chosen-prefix collision attack against the full SHA-1, for a cost of $2^{77.1}$ hash calls. The improvement compared to the generic $2^80$ attack is not very large, due to the difficulty for an attacker to generate enough allowable differences that can later be erased efficiently with a near-collisions block. Indeed, the compression function of SHA-1 being much stronger than that of MD5, few potential candidates are found. Actually, Stevens only considers one type of near collision block, following the best differential trail used for the collision attack. By varying the signs of the message and output differences, and by letting some uncontrolled differences spread during the very last steps of the compression function, a set $S$ of 192 allowable differences is obtained. However, having such a small set makes the birthday part by far the most expensive phase of the attack.

In this article, we will use essentially the same strategy: a birthday phase to reach a set $S$ of allowable differences and a near-collision phase to remove the remaining differences. We improve over previous works on several points. First, we further generalise for SHA-1 the set of possible differences that can be obtained for a cheap cost with a single message block. Secondly, we propose a multi-block strategy for SHA-1 that allows to greatly increase the size of the set $S$. Finally, we study the clustering effect that appears when using a multi-
block strategy. This can be utilised by the attacker to select dynamically the allowable differences at the output of each successive blocks, to further reduce the attack complexity. Notably, and in contrary to previous works, our set $\mathcal{S}$ is not the direct sum of independent subspaces corresponding to distinct trails. On the opposite, our applications use the same core differential trail for all the near-collision blocks. Overall, we improve substantially previous attack [Ste13] from $2^{77.1}$ SHA-1 calls to only $2^{66.9}$. Surprisingly, our attack is very close to some sort of optimal since its cost is not much greater than that of finding a simple collision. Our attack being rather generic, we believe that this might be the case for many hash functions, which contradicts the idea that chosen-prefix collisions are much harder to obtain than simple collisions.

One can mention other parallel researches conducted on finding chosen-prefix collision attacks for various hash functions. For example, in [Pey07], the author explains how to compute collisions with random incoming differences in the internal state for the GRINDAHL hash function, the strategy being to slowly remove these differences thanks to the many degrees of freedom available every step. Such a divide-and-conquer technique is not applicable at all to SHA-1 as the degrees of freedom are much fewer and only available at the beginning of the compression function. In [MRS15], inspired by the second-preimage attack against SMASH [LPRR07], the authors proposed a chosen-prefix collision attack on a reduced version of the GROSTL hash function. However, this attack strongly relies on the ability of the attacker to perform a rebound attack, which seems really hard to achieve in the case of SHA-1.

# 4 From Collision to Chosen-Prefix Collision

## 4.1 The Chosen-prefix Collision Attack

We assume that the hash function considered is an $n$-bit narrow pipe primitive, based on a Merkle-Damgård-like operating mode. In addition, we assume that the compression function is built upon a block cipher in a Davies-Meyer mode.

**Preparing the attack.** The attacker first builds a set $\mathcal{S}$ and a graph $\mathcal{G}$; $\mathcal{S}$ corresponds to a set of differences that can be cancelled with near-collision blocks, and $\mathcal{G}$ is used to find the sequence of blocks needed to cancel a difference in $\mathcal{S}$. We first explain how to execute the attack when $\mathcal{S}$ and $\mathcal{G}$ are given, and we will explain how to build them in Section 4.2.

**The prefixes (stage 1 of Figure 4).** The attacker receives the two challenge prefixes and pads them to two prefixes of the same length, to avoid differences in the final length padding. After processing the two padded prefixes starting from the IV, he reaches states $cv/cv'$, and we denote the corresponding difference as $\delta_R$.
<figure><img src="image_89.png" /><figcaption>Fig. 4. High-level view of the chosen-prefix collision attack</figcaption></figure>
**The birthday search (stage 2 of Figure 4).** The goal of the attacker is now to find one message block pair $(u, u')$ to reach a chaining variable pair with a difference $\delta$ that belongs to $S$, the set of acceptable chaining variable differences.

For this stage, we use the parallel collision search algorithm of van Oorschot and Wiener [vW99]. When a memory $M \gg C$ is available, this algorithm can find $C$ collisions in a function $f: \{0,1\}^k \to \{0,1\}^k$ with complexity $\sqrt{\pi/2 \cdot 2^k \cdot C}$, and is efficiently parallelizable. It computes chains of iterates of the function $f$, and stops when the end point is a distinguished point, i.e. it satisfies some easy to detect property. In practice, we stop a chain when $x < 2^k \cdot \theta$, with $\theta \gg \sqrt{C/2^k}$, and we store on average the starting points and end points of $\theta \cdot \sqrt{\pi/2 \cdot 2^k \cdot C}$ chains (the expected length of a chain is $1/\theta$). When colliding end points are detected, we restart the corresponding chains to locate the collision point, with an expected cost of $2C/\theta$, which is small compared to the total complexity if $\theta \gg \sqrt{C/2^k}$.

In our case, we are looking for message blocks $(u, u')$ such that $h(cv, u) - h(cv', u') \in S$. Therefore, we need a function $f$ such that a collision in $f$ corresponds to good $(u, u')$ with high probability. First, we consider a truncation function $\tau: \{0,1\}^n \to \{0,1\}^k$, so that pairs $(x, x')$ with $x - x' \in S$ have $\tau(x) = \tau(x')$ with high probability:

$$p = \Pr_{x,x'}[\tau(x) = \tau(x') | x - x' \in S] \approx 1.$$

For functions of the MD-SHA family, the group operation $+$ is a word-wise modular addition, and we build $\tau$ by removing bits that are directly affected when adding a value in $S$, and bits that are affected by a carry with a relatively high probability. This typically leads to $p$ close to one (as seen in previous attacks [SSA$^+$09, Ste13], and the new attacks in this paper). Then, we build $f$ as:

$$f(u) := \begin{cases} \tau(h(cv, pad(u))) & \text{if } u[0] = 1; \\ \tau(h(cv', pad(u))) & \text{else.} \end{cases}$$

The probability that a collision in $f$ corresponds to a pair $(u, u')$ with $h(cv, u) - h(cv', u') \in S$ can be estimated as:

$$p_f = \frac{1}{2} \cdot \Pr_{x,x'} [x - x' \in S | \tau(x) = \tau(x')] = \frac{p}{2} \cdot \frac{|S|/2^n}{2^{-k}}$$

Finally, we need $1/p_f$ collisions in $f$, and the total complexity of the birthday stage is on average:

$$\sqrt{\frac{\pi \cdot 2^k}{2 \cdot p_f}} = \sqrt{\frac{\pi \cdot 2^n}{p \cdot |S|}} \approx \sqrt{\frac{\pi \cdot 2^n}{|S|}}.$$

**The multi-block collision search (stage 3 of Figure 4).** The attacker now uses the graph $G$ to build a sequence of near-collision blocks that ends up with a collision. Each node of the graph represents one chaining variable difference
in the set $\mathcal{S}$. To each node $i$ of the graph is associated a cost value $w_i$ that represents the cost an attacker will expect to pay from this particular chaining variable difference $i$ in order to reach a colliding state (with one or multiple message blocks). Of course, a null cost will be associated with the zero difference ($w_0 = 0$). A directed edge from node $i$ to node $j$ represents a way for an attacker to reach chaining variable difference $j$ from difference $i$ with a single message block. Note that the graph is acyclic, as we will ensure that the edges will always go to strictly lower costs (i.e. an edge from $i$ to $j$ is only possible if $w_j < w_i$). To each edge is attached the details of the differential trail and message difference to use for that transition to happen. However, a *very* important point is that all edges going out of a node $i$ will share the same core differential trail (by core differential trail, we mean the entire differential trail except the last steps for which one can usually accept a few divergences in the propagation of the differences). For example, during the attack, from a chaining difference $i$, an attacker can potentially reach difference $j$ or difference $k$ using the same core differential trail (and thus without having to commit in advance which of the two differences he would like to reach). Thus, in essence, the details of the differential trail and message difference to use can be directly attached to the source node.

Once the attacker hits a starting difference $\delta \in \mathcal{S}$ in the birthday phase, he will pick the corresponding node in $\mathcal{G}$, and use the differential trail and message difference attached to this node. He will use this differential trail until he reaches one of the target nodes (which has necessarily a lower expected cost attached to it). As explained in the next section, targeting several nodes simultaneously reduces the cost of the attack, because it is easier to hit one node out of many than a fixed one. We call this the clustering effect, because we use a cluster of paths in the graph. When a new node is reached, the attacker repeats this process until he eventually reaches the colliding state (i.e. null difference). Overall, the expected computational cost for this phase is the cost attached to the node $\delta$ (in practice, when actually computing one collision, he might pay a slightly lower or higher computational cost as the $w_i$'s are expected values).

We note that any suffix message blocks that do not contain differences can of course be added after this colliding state, as the Merkle-Damgård-like mode will maintain the collision throughout the subsequent compression function calls.

## 4.2 Building the Set $\mathcal{S}$ and the Graph $\mathcal{G}$

We now describe how the set $\mathcal{S}$ and the graph $\mathcal{G}$ can be built during the preparation of the attack. For that, we first need to describe what an adversary can do when he tries to attack the compression function. We consider that the attacker knows some good core differential trails for the internal block cipher $E$, that is differential trails that go from early steps to late steps of $E$. For each core differential trail $CDT_i$ there are several possible output differences $\delta_j^i$ for $E$. This is typically what happens in the chosen-prefix collision attack on SHA-1 [Ste13] where some differences in the very last steps can be allowed to spread differently than planned, thus generating new output differences. We denote the set of all possible
output differences as $\mathcal{D}$ (in particular, we have $0 \in \mathcal{D}$, and $\delta \in \mathcal{D} \iff -\delta \in \mathcal{D}$ because of symmetries).

We finally assume that any input difference for $E$ can be mapped to any of the core differential trails inside the primitive. In the case of a **SHA-1** attack, this is achieved with the non-linear part of the trail in the first steps of the function. As shown in previous works, it allows to map any input difference to any internal difference. The non-linear part has a low probability, but during the near-collision search this is solved using the many degrees of freedom available in the first steps of the function.

**Building the graph $\mathcal{G}'$.** The attacker will first build a graph $\mathcal{G}'$ and filter it later to create $\mathcal{G}$. The graph $\mathcal{G}'$ is similar to the graph $\mathcal{G}$: each node will represent a chaining variable difference. A directed edge from node $i$ to node $j$ represents again a way for an attacker to reach chaining variable difference $j$ from difference $i$ with a single message block, stored with the details of the differential trail attached to it, and the cost to find the corresponding block. The differences with $\mathcal{G}$ are that (see Figure 5):

- $\mathcal{G}'$ can potentially be cyclic, as we do not ensure that an edge goes from a higher to a strictly smaller cost;

- all outgoing edges from a node $i$ will not necessarily share the same core differential trail;

- there can be several edges from $i$ to $j$, with different core differential trails.

In order to build the graph $\mathcal{G}'$, starting from the colliding state $\delta = 0$, we will simply proceed backward. We go through all possible core differential trails for $E$ and their possible output differences $\delta_j^i$. Due to the feed-forward of the Davies-Meyer construction, all these differences can be used to reach the colliding state by simply forcing their respective opposite $-\delta_j^i$ as input difference of the cipher (since we assumed that any input difference for $E$ can be mapped to any of the core differential trails inside the primitive, this is always possible). Thus, for each such difference $\delta_j^i$ coming from a core differential trail $CDT_i$, we will add a node $-\delta_j^i$ in the graph $\mathcal{G}'$, and an edge going from this new node to the colliding state. If a node with that difference already exists in the graph, we add the edge between this node and the colliding state. This means that nodes can have several incoming and outgoing edges.

We iteratively repeat this process again with all the newly created nodes as starting points (instead of the collision state). This will create a bigger and bigger graph as we keep iterating, and the attacker can simply stop when he believes that he has enough nodes in the graph (alternatively, he can set an upper limit on the cost of the nodes to consider, or on the depth of the search, which will naturally limit the size of the graph).

**The clustering effect.** A simple way to build a graph $\mathcal{G}$ for the attack is to keep only the minimal cost paths in the graph $\mathcal{G}'$ (the corresponding edges form a tree), and to set the cost of the nodes to cost of the minimal path. However,
<figure><img src="image_90.png" /><figcaption>**Fig. 5.** Example of a graph $\mathcal{G}'$, with a bundle $\{\alpha, 2\alpha\}$ with costs 1 and 2 (solid green lines), and a bundle $\{-\alpha, -2\alpha\}$ with costs 1 and 2 (dashed red lines). The corresponding set $S$ is $\{-4\alpha, -3\alpha, -2\alpha, -\alpha, 0, \alpha, 2\alpha, 3\alpha, 4\alpha\}$.</figcaption></figure>

<caption>**Fig. 6.** The graph $\mathcal{G}$ corresponding to $\mathcal{G}'$. We show the cost of each edge and each node. In particular, note that use of clustering reduces the cost of node 4$\alpha$ from 4 to $64/27 \approx 2.37$.</caption>

the attack cost can be greatly improved with the *clustering effect*: during the last phase of the attack, when the attacker is currently located at a node $N$, he does not necessarily need to choose in advance which outgoing edge of $N$ he will try to follow. Indeed, the only commitment he needs to make at this point is which core differential trail he will use to go to the next node. Thus, he can simultaneously target several output differences corresponding to the same core differential trail, and the cost to reach one difference out of many is significantly lower than the cost of reaching any given output difference. For instance, when computing the first block of a SHA-1 collision, Stevens [Ste13] allows six output differences with a similar cost, so that the cost to reach one of them is one sixth of the cost to reach a predetermined one.

For a given node, we call *bundle* of a core differential trail $CDT_i$ the grouping of all outgoing edges of that node that use $CDT_i$ (see Figure 5). Let $\mathcal{B}_N$ stand for the set of all bundles of a node $N$, where each bundle $\beta \in \mathcal{B}_N$ corresponds to a distinct core differential trail $CDT_i$. Then, for each node of $\mathcal{G}'$, we compute its
assigned cost as follows<fnref n="9" />:

$$w_N = \min_{\beta \in \mathcal{B}_N} \left\{ \frac{1 + \sum_{(N,j) \in \beta | w_j < w_N} \left( \frac{w_j}{c_j^\beta} \right)}{\sum_{(N,j) \in \beta | w_j < w_N} \left( \frac{1}{c_j^\beta} \right)} \right\}, \quad (1)$$

where for an edge $(N, j)$ of the bundle $\beta$, $c_j^\beta$ represents the cost to find a conforming message pair with difference output $j - N$ for $E$, and $w_j$ is the cost assigned to the node $j$.

We initialize the costs of the nodes in $\mathcal{G}'$ using the shortest path in the graph, and update them iteratively until we can't find any more opportunity for improvement.

**Building $\mathcal{S}$ and $\mathcal{G}$**. The graph $\mathcal{G}$ is obtained from $\mathcal{G}'$ by only keeping the edges that goes from a higher to a strictly lower cost (in order to render the graph acyclic), and by only keeping for each node the outgoing edges for the bundle that minimizes the cost $w_N$ in (1).

The set $\mathcal{S}$ is then finally deduced by harnessing all the differences corresponding to every node in $\mathcal{G}$ (one node in $\mathcal{G}$ will correspond to one difference in $\mathcal{S}$). In particular, if $\mathcal{G}'$ includes all nodes at depth at most $r$, then $\mathcal{S} = \{\delta_1 + \delta_2 + \dots + \delta_r | \delta_1, \delta_2, \dots, \delta_r \in \mathcal{D}\}$.

# 5 Application to MD5

Our techniques can easily be applied to MD5, to build an alternative chosen-prefix collision attack. We can't reach an attack complexity as low as $2^{39}$ (the best attack from [SSA$^+$09]), because this would require to build a set $\mathcal{S}$ and graph $\mathcal{G}$ of size roughly $2^{50}$, which is impractical. However, when the number of blocks available for the chosen-prefix collision is limited, the complexity of the best-known attack grows; for instance, the chosen-prefix collision used to create a rogue certificate was limited to 3 blocks, and this increased the complexity to

$$w_N = C_\beta + \sum_{j \in \beta | w_j < w_N} \left( p_j^\beta \cdot w_j \right) + \left( 1 - \sum_{j \in \beta | w_j < w_N} p_j^\beta \right) \cdot w_N$$

which leads to (1) with $c_j^\beta = C_\beta/p_j^\beta$.

<footnote n="9">⁹ In order to explain this formula, we consider that when the adversary uses a bundle $\beta$, he has to perform $C_\beta$ operations to find a pair conforming to the core differential trail up to some intermediate step, and those pairs lead to an output difference $j - N$ (i.e. to node $j$) with probability $p_j^\beta$ (with $p_j^\beta = C_\beta/c_j^\beta$). If none of the predetermined output differences is reached (or if the target node reached has a cost $w_j \ge w_N$), then he stays at node $N$ and will have to still pay $w_N$ to reach the colliding state. Thus, we have that:</footnote>
$2^{49}$. In this scenario we can improve the currently best-known attack with our multi-block technique using a single differential trail.

We start from the single-block chosen-prefix collision attack given in [SSA+09, Section 6]: this attack uses a high probability trail for MD5 collisions, where the last steps are relaxed to allow a set $\mathcal{D}$ of size $2^{23.3}$. Therefore the birthday stage has complexity roughly $\sqrt{\pi \cdot 2^{128}/2^{23.3}} \approx 2^{53.2}$, and the near-collision block is found with a complexity of $2^{40.8}$. In our analysis, we recomputed the set $\mathcal{D}$ used by Stevens et al., but we actually found a set of size $2^{24.2}$ using the same trail, with a maximum cost of $2^{26} \cdot 2^{14.8}$ (following [SSA+09], we only consider output differences with $\delta a = -2^5$, $\delta d = -2^5 + 2^{25}$, $\delta c = -2^5 \mod 2^{20}$). Then, we extend $\mathcal{D}$ by adding the zero value and the opposite of each value, to generate $\mathcal{D}' := \mathcal{D} \cup -\mathcal{D} \cup \{0\}$. Finally, we build the set $S$ and the graph $G'$ corresponding to an attack with at most 2 blocks, with $S := \{\delta_1 + \delta_2 \mid \delta_1, \delta_2 \in \mathcal{D}'\}$. Since the cost of the near-collision stage is negligible (at most $2 \cdot 2^{40.8}$), we do not need to use clustering, and we can just use the minimal cost paths of $G'$ as the graph $G$.

We find that the set $S$ contains $2^{37.1}$ elements, so that the birthday stage has a complexity of roughly $\sqrt{\pi \cdot 2^{128}/2^{37.1}} \approx 2^{46.3}$. Therefore, we have a simple chosen-prefix collision attack with two near-collision blocks with complexity $2^{46.3}$, while the best previous attack with two blocks or less requires $2^{53.2}$ MD5 computations, and even the best attack with three blocks requires $2^{49}$ MD5 computations.

# 6 Application to SHA-1

For the attack on **SHA-1**, we directly recycle the details of the collision attack from [SBK+17]: we will use the same linear part for our successive near-collision blocks (even though the very last steps might behave slightly differently as we will explain in this section). We assume that the attacker can generate non-linear parts on the fly and can apply amortization methods just like in [SBK+17]. In order to validate this assumption, we have tried to generate a non-linear part with several random input differences from $S$ and random input chaining values. In our experiments, we have successfully generated such non-linear part, and we could even make it limited to the very first **SHA-1** steps. We discuss this assumption and our experiments in more details in Section 6.3.

We now explain how to apply the framework of Section 4 to a chosen-prefix collision against **SHA-1**. As mentioned, our attack uses the best core trail known for attacks against **SHA-1**, as used in previous attacks [Ste13, Ste12, SBK+17]. This allows us to have a relatively good complexity estimation for the attack, because this trail has been well studied, and a full collision attack with this trail was recently implemented. In the following we denote the complexity to find a block conforming to the trail (with an optimal output difference) as $C_{\text{block}}$. In the case of the recent collision attack, this cost was estimated as $C_{\text{block}} = 2^{64.7}$ **SHA-1** evaluations on a GTX-970 GPU [SBK+17, Section 5.7]. In this work, we consider several hypothesis for the cost of finding near-collision blocks: an optimistic hypothesis with $C_{\text{block}} = 2^{64.7}$ (following [SBK+17]) and a conservative
hypothesis with $C_{\text{block}} = 2^{67.7}$. This parameter depends on the difficulty of linking an arbitrary input difference to the core trail, and will be discussed in more detail below.

As in the previous chosen-prefix collision attack on SHA-1 [Ste13], we consider
several variants of the core trail by changing some of the message constraints in
the last steps (in particular, we flip the sign of some message bits), and we relax
the last steps to reach a larger set of output difference. However, we do this more
exhaustively than Stevens: he only describes a set $\mathcal{D}$ of size 192 with cost at most
$1.15 \cdot C_{\text{block}}$, but we found a set of size 8768 with cost at most $8 \cdot C_{\text{block}}$, including
576 values with cost at most $1.15 \cdot C_{\text{block}}$. In particular, this directly leads to
an improvement of the single-block chosen-prefix collision from [Ste13], with
complexity roughly $\sqrt{\pi \cdot 2^{160}/8768} \approx 2^{74.3}$, rather than $\sqrt{\pi \cdot 2^{160}/192} \approx 2^{77}$
(ignoring some technical details of the birthday step).

More precisely, we allow the signs of the message differences to not necessarily follow local collision patterns in the last steps. Instead, we consider variants of the trail where each of those constraints is either followed or not. In addition, we fix the sign of some additional state bits to reduce the cost to reach a given output difference. Table 3 compares our message constraints with those used for the second-block of the attack from [SBK$^{+}$17]. This leads to 288 differences with optimal probability ($2^{-19.17}$ in steps 61 to 79), and 288 with almost optimal probability ($2^{-19.36}$ in steps 61 to 79), as listed in Table 4. Moreover, we consider output differences whose cost is higher than the optimal cost $C_{\text{block}}$, up to roughly $8 \cdot C_{\text{block}}$ (we allow a probability up to $2^{-22}$ in steps 61 to 79).

Instead of building the corresponding set of output differences and their prob-
ability analytically, we used a heuristic approach. For each choice of the message
constraints $z_i$ in Table 3 (up to some symmetries), we generated $2^{30}$ interme-
diate states at step 60, and we computed the corresponding output differences
in order to identify high probability ones. We also keep track of the differences
reached with the same constraints, to build the corresponding bundles of differ-
ences. Next, we used symmetries in the set of differences to verify the consistency
of the results, and to increase the precision of the heuristic probabilities. This
strategy leads to a set of 8768 possible output differences, grouped in 2304 bund-
dles. We list the output differences with (almost) optimal probability that we
have identified in Table 4, with the corresponding bundles (we do not give the
set with all considered differences due its large size).

Next, we build the set $\mathcal{S}$ of acceptable differences, and the graph $\mathcal{G}$ that indicates the sequences of near-collision blocks to use to cancel the differences in $\mathcal{S}$. We first build the graph $\mathcal{G}'$ as explained in Section 4.2. We use a limit on the cost of the nodes added to graph: we only consider nodes that have a path with cost at most $18 \cdot C_{\text{block}}$ in the graph $\mathcal{G}'$ (where this cost is computed with a single path, without using clustering). This yields a set of $2^{33.78}$ unique differences. After optimizing the cost with clustering, most of the nodes have a cost at most $4.5 \cdot C_{\text{block}}$, and we use a subset of the graph by bounding the cost of the near-collision stage. We describe various trade-offs in Table 5: a larger set
<table><caption>**Table 3.** Message constraints in the final steps. The $z_i$ are fixed to 0 or 1 to define variant of the trail with distinct output differences. We use three more constraints than [SBK$^{+}$17].</caption><thead><tr><th>Stevens et al. constraints [SBK<sup>+</sup>17]</th><th>Our constraints</th></tr></thead><tbody><tr><td>W<sub>68</sub><sup>[5]</sup> = W<sub>67</sub><sup>[0]</sup> ⊕ 1</td><td>W<sub>68</sub><sup>[5]</sup> = W<sub>67</sub><sup>[0]</sup> ⊕ 1</td></tr><tr><td>W<sub>72</sub><sup>[30]</sup> = W<sub>67</sub><sup>[0]</sup> ⊕ 1</td><td>W<sub>72</sub><sup>[30]</sup> = W<sub>67</sub><sup>[0]</sup> ⊕ 1</td></tr><tr><td>W<sub>71</sub><sup>[6]</sup> = W<sub>70</sub><sup>[1]</sup> ⊕ 1</td><td>W<sub>71</sub><sup>[6]</sup> = W<sub>70</sub><sup>[1]</sup> ⊕ 1</td></tr><tr><td>W<sub>72</sub><sup>[5]</sup> = W<sub>71</sub><sup>[0]</sup> ⊕ 1</td><td>W<sub>72</sub><sup>[5]</sup> = W<sub>71</sub><sup>[0]</sup> ⊕ 1</td></tr><tr><td>W<sub>76</sub><sup>[30]</sup> = W<sub>71</sub><sup>[0]</sup> ⊕ 1</td><td>W<sub>76</sub><sup>[30]</sup> = W<sub>71</sub><sup>[0]</sup> ⊕ 1</td></tr><tr><td>W<sub>74</sub><sup>[7]</sup> = W<sub>73</sub><sup>[2]</sup> ⊕ 1</td><td>W<sub>74</sub><sup>[7]</sup> = W<sub>73</sub><sup>[2]</sup> ⊕ 1, W<sub>73</sub><sup>[2]</sup> = z<sub>1</sub></td></tr><tr><td>W<sub>75</sub><sup>[6]</sup> = W<sub>74</sub><sup>[1]</sup> ⊕ 1</td><td>W<sub>75</sub><sup>[6]</sup> = W<sub>74</sub><sup>[1]</sup> ⊕ 1</td></tr><tr><td>W<sub>76</sub><sup>[6]</sup> = W<sub>75</sub><sup>[1]</sup> ⊕ 1</td><td>W<sub>76</sub><sup>[6]</sup> = W<sub>75</sub><sup>[1]</sup> ⊕ 1</td></tr><tr><td>W<sub>76</sub><sup>[1]</sup> = W<sub>76</sub><sup>[0]</sup> ⊕ 1</td><td>W<sub>76</sub><sup>[1]</sup> = z<sub>2</sub>, W<sub>76</sub><sup>[0]</sup> = z<sub>3</sub></td></tr><tr><td>W<sub>77</sub><sup>[1]</sup> = W<sub>77</sub><sup>[0]</sup> ⊕ z<sub>1</sub></td><td>W<sub>77</sub><sup>[1]</sup> = z<sub>4</sub>, W<sub>77</sub><sup>[0]</sup> = z<sub>5</sub></td></tr><tr><td>W<sub>77</sub><sup>[2]</sup> = W<sub>77</sub><sup>[1]</sup> ⊕ 1</td><td>W<sub>77</sub><sup>[2]</sup> = z<sub>6</sub></td></tr><tr><td>W<sub>77</sub><sup>[8]</sup> = W<sub>76</sub><sup>[3]</sup> ⊕ 1, W<sub>76</sub><sup>[3]</sup> = z<sub>2</sub></td><td>W<sub>76</sub><sup>[3]</sup> = z<sub>7</sub>, W<sub>77</sub><sup>[8]</sup> = z<sub>8</sub></td></tr><tr><td>W<sub>78</sub><sup>[0]</sup> = W<sub>74</sub><sup>[7]</sup></td><td>W<sub>78</sub><sup>[0]</sup> = z<sub>9</sub></td></tr><tr><td>W<sub>78</sub><sup>[3]</sup> = z<sub>3</sub></td><td>W<sub>78</sub><sup>[3]</sup> = z<sub>10</sub></td></tr><tr><td>W<sub>78</sub><sup>[7]</sup> = z<sub>4</sub></td><td>W<sub>78</sub><sup>[7]</sup> = z<sub>11</sub></td></tr><tr><td>W<sub>79</sub><sup>[2]</sup> = z<sub>5</sub></td><td>W<sub>79</sub><sup>[2]</sup> = z<sub>12</sub></td></tr><tr><td>W<sub>79</sub><sup>[4]</sup> = z<sub>6</sub></td><td>W<sub>79</sub><sup>[4]</sup> = z<sub>13</sub></td></tr></tbody></table>

reduces the cost of the birthday stage, but increases the cost of the near-collision stage.

We note that the memory requirements of our attack are rather limited: one just has to store the graph, and the chains for the birthday phase. With the parameters we propose, this represents less than 1TB.

## 6.1 Limiting the number of near-collision blocks

The attack above is optimized to minimize the time complexity of the attack, but this can result in long paths in the graph. For instance, when starting from a random difference with cost at most $3.0 \cdot C_{\text{block}}$, a random path has on average 15.7 near-collision blocks, but the maximal length is 26 near-collision blocks. This might be impractical for some applications of chosen-prefix collision attacks, and the work needed to generate all the differential trails for the near-collision blocks might also be an issue.

Therefore, we propose an alternative attack where we limit the length of the paths in the graph $\mathcal{G}$. This result in a slightly higher complexity, but might be better in practice. More precisely, we first construct a graph with only paths of length 1, and we iteratively build graphs by increasing the length of allowed paths. Note that a given difference can often be reached by many paths of varying length, and the cost of a node decreases when allowing longer paths.
<table><caption>**Table 4.** Bundles of trails with (near) optimal cost and the corresponding probability for steps 61–79. For each bundle $B_i$ in the table, there are 32 related bundles where we flip some of the messages bits, that can be constructed as:</caption><thead><tr><th>Bundle</th><th>Output difference</th><th>Proba (− log)</th></tr></thead><tbody><tr><td>B<sub>1</sub></td><td>0xffffedea 0xfffff70 0x00000000 0x00000002 0x80000000 19.17<br>0xffffdeee 0xfffff70 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefea 0xfffff80 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefee 0xfffff80 0x00000000 0x00000002 0x80000000 19.17<br>0xfffffe5ec 0xfffff30 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ec 0xfffff40 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>2</sub></td><td>0xffffedea 0xfffff70 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffdeee 0xfffff70 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefea 0xfffff80 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefee 0xfffff80 0x00000000 0xfffffffe 0x80000000 19.17<br>0xfffffe5ec 0xfffff30 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ec 0xfffff40 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>3</sub></td><td>0xffffedea 0xfffff70 0x00000000 0x00000002 0x80000000 19.17<br>0xffffdeee 0xfffff70 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefea 0xfffff80 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefee 0xfffff80 0x00000000 0x00000002 0x80000000 19.17<br>0xfffffe5ec 0xfffffb0 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ec 0xfffffc0 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>4</sub></td><td>0xffffedea 0xfffff70 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffdeee 0xfffff70 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefea 0xfffff80 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefee 0xfffff80 0x00000000 0xfffffffe 0x80000000 19.17<br>0xfffffe5ec 0xfffffb0 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ec 0xfffffc0 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>5</sub></td><td>0xffffedaa 0xfffff6e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffedae 0xfffff6e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefaa 0xfffff7e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefae 0xfffff7e 0x00000000 0x00000002 0x80000000 19.17<br>0xfffffe5ac 0xfffff2e 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ac 0xfffff3e 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>6</sub></td><td>0xffffedaa 0xfffff6e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffedae 0xfffff6e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefaa 0xfffff7e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefae 0xfffff7e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xfffffe5ac 0xfffff2e 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ac 0xfffff3e 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>7</sub></td><td>0xffffedaa 0xfffff6e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffedae 0xfffff6e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefaa 0xfffff7e 0x00000000 0x00000002 0x80000000 19.17<br>0xffffefae 0xfffff7e 0x00000000 0x00000002 0x80000000 19.17<br>0xfffffe5ac 0xfffffae 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ac 0xfffffbe 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr><tr><td>B<sub>8</sub></td><td>0xffffedaa 0xffffff6e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffedae 0xffffff6e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefaa 0xffffff7e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xffffefae 0xffffff7e 0x00000000 0xfffffffe 0x80000000 19.17<br>0xfffffe5ac 0xffffffae 0x80000000 0x00000002 0x80000000 19.36<br>0xfffffe7ac 0xffffffbe 0x80000000 0x00000002 0x80000000 19.36</td><td></td></tr></tbody></table>

$$B_0 = \{B_i\}$$

$$B_1 = \{\{\beta + (2^5, 0, 0, 0) | \beta \in \mathcal{B}\} | \mathcal{B} \in B_0\} \cup B_0$$

$$B_2 = \{\{\beta + (2^3, 0, 0, 0) | \beta \in \mathcal{B}\} | \mathcal{B} \in B_1\} \cup B_1$$

$$B_3 = \{\{\beta + (2^{13}, 2^8, 0, 0, 0) | \beta \in \mathcal{B}\} | \mathcal{B} \in B_2\} \cup B_2$$

$$B_4 = \{\{\beta + (2^9, 2^4, 0, 0, 0) | \beta \in \mathcal{B}\} | \mathcal{B} \in B_3\} \cup B_3$$

$$B_5 = \{\{\beta + (2^6, 2, 0, 0, 0) | \beta \in \mathcal{B}\} | \mathcal{B} \in B_4\} \cup B_4.$$

The set used in [Ste13] corresponds to bundles $B_1$ to $B_4$, with extension rules $B_1$ to $B_4$. Note that most output differences appears in several bundles.
We have constructed exactly the graph with all paths of length at most 4, and all paths of length at most 8 and cost at most $3.5 \cdot C_{\text{block}}$; for larger parameters, we cannot build the full graph, but we can build an approximation by limiting the set of values as in the previous construction. We give the size of the corresponding sub-graphs in Table 6. As we can see, with 8 near-collision blocks we already have a set $S$ almost as large as the set corresponding to the previous attack (cf. Table 5), so that limiting the attack to 8 blocks has a small impact on the complexity. We can even find chosen-prefix collisions with just 4 near-collision blocks with a small cost increase, using a larger threshold on the maximum cost per block. We evaluate the complexity of such attacks in detail in Table 7.

We can also study the sparseness of the values in $S$ to better understand the difficulty of building the differential trails for the near collision blocks. Using the set of size $2^{29.71}$ with a limit of 8 near-collision blocks and a maximum cost of $3.0 \cdot C_{\text{block}}$, the maximum weight in the differences is 26, and the average is 15.4 (using the non-adjacent form — NAF).

## 6.2 Birthday Stage

For the birthday stage of the attack, we follow the approach given in [Ste13]: we consider a truncation of the SHA-1 state by keeping bits which are likely to contain a difference, and we use the distinguished points technique of [vW99]. Parameters for the birthday step with various choice of $\mathcal{G}$ are given in Table 5; we now explain in detail the case where the maximum cost of the near-collision stage is set to $3.0 \cdot C_{\text{block}}$. First, we truncate the state to 98 bits<fnref n="10" /> so that for a random pair of values with their difference in $S$, there is a probability 0.78 that the values collide on 98 bits (this probability has been computed with the tools from [Leu12]). Reciprocally, if two truncated SHA-1 outputs are equal, then their difference is in the set $S$ with probability $2^{-31.97}$. Therefore, the birthday stage will require on average $2 \cdot 2^{31.97}$ collisions in the following function:

$$f(r) := \begin{cases} \tau(h(cv, \text{pad}(u))) & \text{if } u[0] = 1; \\ \tau(h(cv', \text{pad}(u))) & \text{else.} \end{cases}$$

In order to keep the cost of rerunning the trail low, we use chains of average length $2^{31}$ (i.e. a point $u$ is distinguished when $u < 2^{98-31}$). Therefore, the expected complexity of the birthday stage is<fnref n="11" />:

$$T = \sqrt{\pi/2 \cdot 2^{98} \cdot 2^{32.97}} \approx 2^{65.81} \text{ SHA-1 computations} \\ M = 2^{65.81}/2^{31} \cdot 19 \text{ bytes} \approx 570 \text{ GB},$$

and the cost to re-run the chains to locate collisions is only $2^{32.97} \cdot 2 \cdot 2^{31} \approx 2^{64.97}$. Finally, we can evaluate the complexity of the full attacks as: $2^{65.81} + 2^{64.97} + 3.0 \cdot C_{\text{block}}$.

<footnote n="10">¹⁰ Given by mask 0x7f800000, 0xfffc0001, 0x7ffff800, 0x7fffff80, 0x7fffffff</footnote>

<footnote n="11">¹¹ To store a chain, we use 40 bits for the starting point, 40 bits for the length, and 98 - 31 = 67 bits for the output, i.e. 19 bytes in total.</footnote>
<table><caption>**Table 5.** Trade-offs between the cost of birthday phase and the near-collision phase.</caption><thead><tr><th colspan="2">Set S</th><th colspan="6">Birthday parameters</th><th rowspan="2">Attack cost</th></tr><tr><th>Max cost</th><th>Size</th><th>Mask</th><th>Proba</th><th># coll.</th><th>Chain len.</th><th># chain</th></tr></thead><tbody><tr><td>2.0 · C<sub>block</sub></td><td>2<sup>24.66</sup></td><td>106 bits</td><td>0.71</td><td>2<sup>30.83</sup></td><td>2<sup>34</sup></td><td>2<sup>34.74</sup></td><td>2<sup>68.74</sup> + 2<sup>65.83</sup> + 2.0 · C<sub>block</sub></td><td></td></tr><tr><td>2.5 · C<sub>block</sub></td><td>2<sup>28.59</sup></td><td>102 bits</td><td>0.65</td><td>2<sup>31.03</sup></td><td>2<sup>32</sup></td><td>2<sup>34.84</sup></td><td>2<sup>66.84</sup> + 2<sup>64.03</sup> + 2.5 · C<sub>block</sub></td><td></td></tr><tr><td>3.0 · C<sub>block</sub></td><td>2<sup>30.95</sup></td><td>98 bits</td><td>0.76</td><td>2<sup>32.44</sup></td><td>2<sup>31</sup></td><td>2<sup>34.55</sup></td><td>2<sup>65.55</sup> + 2<sup>64.44</sup> + 3.0 · C<sub>block</sub></td><td></td></tr><tr><td>3.5 · C<sub>block</sub></td><td>2<sup>32.70</sup></td><td>98 bits</td><td>0.76</td><td>2<sup>30.70</sup></td><td>2<sup>30</sup></td><td>2<sup>34.68</sup></td><td>2<sup>64.68</sup> + 2<sup>61.70</sup> + 3.5 · C<sub>block</sub></td><td></td></tr><tr><td>4.0 · C<sub>block</sub></td><td>2<sup>33.48</sup></td><td>98 bits</td><td>0.74</td><td>2<sup>29.95</sup></td><td>2<sup>30</sup></td><td>2<sup>34.30</sup></td><td>2<sup>64.30</sup> + 2<sup>60.95</sup> + 4.0 · C<sub>block</sub></td><td></td></tr><tr><td>4.5 · C<sub>block</sub></td><td>2<sup>33.66</sup></td><td>98 bits</td><td>0.74</td><td>2<sup>29.77</sup></td><td>2<sup>30</sup></td><td>2<sup>34.21</sup></td><td>2<sup>64.21</sup> + 2<sup>60.77</sup> + 4.5 · C<sub>block</sub></td><td></td></tr></tbody></table>

<table><caption>**Table 6.** Size of the set S with various limits on the maximum cost and on the number of near-collision blocks. We give a lower bound when we couldn't compute the full set.</caption><thead><tr><th>Max Cost</th><th>1 bl.</th><th>2 bl.</th><th>3 bl.</th><th>4 bl.</th><th>5 bl.</th><th>6 bl.</th><th>7 bl.</th><th>8 bl.</th></tr></thead><tbody><tr><td>2.0 · C<sub>block</sub></td><td>2<sup>9.17</sup></td><td>2<sup>16.30</sup></td><td>2<sup>19.92</sup></td><td>2<sup>22.05</sup></td><td>2<sup>23.13</sup></td><td>2<sup>23.95</sup></td><td>2<sup>24.44</sup></td><td>2<sup>24.55</sup></td></tr><tr><td>2.5 · C<sub>block</sub></td><td>2<sup>10.17</sup></td><td>2<sup>16.62</sup></td><td>2<sup>21.04</sup></td><td>2<sup>23.76</sup></td><td>2<sup>25.50</sup></td><td>2<sup>26.58</sup></td><td>2<sup>27.38</sup></td><td>2<sup>27.92</sup></td></tr><tr><td>3.0 · C<sub>block</sub></td><td>2<sup>10.17</sup></td><td>2<sup>17.10</sup></td><td>2<sup>21.76</sup></td><td>2<sup>24.66</sup></td><td>2<sup>26.58</sup></td><td>2<sup>27.95</sup></td><td>2<sup>28.96</sup></td><td>2<sup>29.71</sup></td></tr><tr><td>3.5 · C<sub>block</sub></td><td>2<sup>12.53</sup></td><td>2<sup>17.89</sup></td><td>2<sup>22.47</sup></td><td>2<sup>25.62</sup></td><td>2<sup>27.70</sup></td><td>2<sup>29.18</sup></td><td>2<sup>30.29</sup></td><td>2<sup>31.22</sup></td></tr><tr><td>4.0 · C<sub>block</sub></td><td>2<sup>12.53</sup></td><td>2<sup>18.60</sup></td><td>2<sup>22.97</sup></td><td>2<sup>26.34</sup></td><td>≥ 2<sup>28.68</sup></td><td>≥ 2<sup>30.35</sup></td><td>≥ 2<sup>31.55</sup></td><td>≥ 2<sup>32.15</sup></td></tr><tr><td>5.0 · C<sub>block</sub></td><td>2<sup>12.53</sup></td><td>2<sup>19.65</sup></td><td>2<sup>24.18</sup></td><td>2<sup>27.44</sup></td><td>≥ 2<sup>29.83</sup></td><td>≥ 2<sup>31.64</sup></td><td>≥ 2<sup>32.95</sup></td><td>≥ 2<sup>33.04</sup></td></tr><tr><td>6.0 · C<sub>block</sub></td><td>2<sup>12.53</sup></td><td>2<sup>19.79</sup></td><td>2<sup>24.81</sup></td><td>2<sup>28.26</sup></td><td>≥ 2<sup>30.74</sup></td><td>≥ 2<sup>32.55</sup></td><td>≥ 2<sup>33.59</sup></td><td>≥ 2<sup>33.59</sup></td></tr><tr><td>7.0 · C<sub>block</sub></td><td>2<sup>13.09</sup></td><td>2<sup>20.37</sup></td><td>2<sup>25.30</sup></td><td>2<sup>28.82</sup></td><td>≥ 2<sup>31.33</sup></td><td>≥ 2<sup>32.93</sup></td><td>≥ 2<sup>33.77</sup></td><td>≥ 2<sup>33.77</sup></td></tr><tr><td>8.0 · C<sub>block</sub></td><td>2<sup>13.09</sup></td><td>2<sup>20.62</sup></td><td>2<sup>25.72</sup></td><td>2<sup>29.27</sup></td><td>≥ 2<sup>31.72</sup></td><td>≥ 2<sup>33.09</sup></td><td>≥ 2<sup>33.81</sup></td><td>≥ 2<sup>33.81</sup></td></tr></tbody></table>

<table><caption>**Table 7.** Trade-offs between the cost of birthday phase and the near-collision phase with a limited number of near-collision blocks (4 or 8).</caption><thead><tr><th colspan="3">Set S</th><th colspan="6">Birthday parameters</th><th rowspan="2">Attack cost</th></tr><tr><th>Max bl.</th><th>Max cost</th><th>Size</th><th>Mask</th><th>Proba</th><th># coll.</th><th>Chain len.</th><th># chain</th></tr></thead><tbody><tr><td>4</td><td>4.0 · C<sub>block</sub></td><td>2<sup>26.34</sup></td><td>106 bits</td><td>0.48</td><td>2<sup>29.70</sup></td><td>2<sup>33</sup></td><td>2<sup>35.18</sup></td><td>2<sup>68.18</sup> + 2<sup>63.70</sup> + 4.0 · C<sub>block</sub></td><td></td></tr><tr><td>4</td><td>5.0 · C<sub>block</sub></td><td>2<sup>27.44</sup></td><td>102 bits</td><td>0.67</td><td>2<sup>32.14</sup></td><td>2<sup>32</sup></td><td>2<sup>35.40</sup></td><td>2<sup>67.40</sup> + 2<sup>65.14</sup> + 5.0 · C<sub>block</sub></td><td></td></tr><tr><td>4</td><td>6.0 · C<sub>block</sub></td><td>2<sup>28.26</sup></td><td>102 bits</td><td>0.65</td><td>2<sup>31.35</sup></td><td>2<sup>32</sup></td><td>2<sup>35.00</sup></td><td>2<sup>67.00</sup> + 2<sup>64.35</sup> + 6.0 · C<sub>block</sub></td><td></td></tr><tr><td>4</td><td>7.0 · C<sub>block</sub></td><td>2<sup>28.82</sup></td><td>102 bits</td><td>0.64</td><td>2<sup>30.82</sup></td><td>2<sup>32</sup></td><td>2<sup>34.74</sup></td><td>2<sup>66.74</sup> + 2<sup>63.82</sup> + 7.0 · C<sub>block</sub></td><td></td></tr><tr><td>4</td><td>8.0 · C<sub>block</sub></td><td>2<sup>29.26</sup></td><td>102 bits</td><td>0.63</td><td>2<sup>30.39</sup></td><td>2<sup>32</sup></td><td>2<sup>34.52</sup></td><td>2<sup>66.52</sup> + 2<sup>63.39</sup> + 8.0 · C<sub>block</sub></td><td></td></tr><tr><td>8</td><td>2.0 · C<sub>block</sub></td><td>2<sup>24.55</sup></td><td>106 bits</td><td>0.71</td><td>2<sup>30.94</sup></td><td>2<sup>34</sup></td><td>2<sup>34.80</sup></td><td>2<sup>68.80</sup> + 2<sup>65.94</sup> + 2.0 · C<sub>block</sub></td><td></td></tr><tr><td>8</td><td>2.5 · C<sub>block</sub></td><td>2<sup>27.92</sup></td><td>102 bits</td><td>0.63</td><td>2<sup>31.75</sup></td><td>2<sup>32</sup></td><td>2<sup>35.20</sup></td><td>2<sup>67.20</sup> + 2<sup>64.75</sup> + 2.5 · C<sub>block</sub></td><td></td></tr><tr><td>8</td><td>3.0 · C<sub>block</sub></td><td>2<sup>29.71</sup></td><td>98 bits</td><td>0.73</td><td>2<sup>33.73</sup></td><td>2<sup>31</sup></td><td>2<sup>35.19</sup></td><td>2<sup>66.19</sup> + 2<sup>65.73</sup> + 3.0 · C<sub>block</sub></td><td></td></tr><tr><td>8</td><td>3.5 · C<sub>block</sub></td><td>2<sup>31.22</sup></td><td>98 bits</td><td>0.72</td><td>2<sup>32.23</sup></td><td>2<sup>30</sup></td><td>2<sup>35.44</sup></td><td>2<sup>65.44</sup> + 2<sup>63.23</sup> + 3.5 · C<sub>block</sub></td><td></td></tr></tbody></table>
## 6.3 Near-Collision Stage

<table><caption>**Table 8.** Example of a SHA-1 non-linear differential path generated for one of the differences in $S$. Notations follow [DMR07]. $\delta = [-2^{17} - 2^{15} + 2^{10} - 2^8 + 2^5 + 2^6 - 2^2 + 2^0, -2^{13} + 2^{11} + 2^{10} + 2^5 - 2^3, -2^5 + 2^0, -2^4 - 2^0, 0]$, with cost $2.954 \cdot C_{\text{block}}$.</caption><thead><tr><th>i</th><th>A<sub>i</sub></th><th>W<sub>i</sub></th></tr></thead><tbody><tr><td>-4:</td><td>10110011001011000101111011010101</td><td>1011un01010001010101111110-10-u0</td></tr><tr><td>-3:</td><td>110110001100001000100111un01un01</td><td>nu1110011101100011110-00-00n0110</td></tr><tr><td>-2:</td><td>001010100011010111011unnnn1011n11</td><td>u1nn0u000100010001010111---unn00</td></tr><tr><td>-1:</td><td>00101010111000011un1nn0010n0u111</td><td>00uuun1111010111100111010000-u1-</td></tr><tr><td>00:</td><td>1010111000111un1u0110n1u0nn0un1n</td><td>n0nunu00---001---0---1000uu0u1</td></tr><tr><td>01:</td><td>10100u101u0u10101n1nu0111n-u1-1u</td><td>10u-1--101110-000-1100-0110n-00-</td></tr><tr><td>02:</td><td>1u1u0nn010nunnu11011uuuu0001uu1</td><td>--u--u1-----------------0101uun--</td></tr><tr><td>03:</td><td>u1un01uunn1u1010u0u10110nu11uu1</td><td>xun-nu-----------------1-1---11u0u--</td></tr><tr><td>04:</td><td>n0110unnnnnnnnnnnnn11nu1000u1n1</td><td>---un----------------------u0</td></tr><tr><td>05:</td><td>un0n011100--11001--111-1u1uu1u11</td><td>xn------------------------0--n-0--</td></tr><tr><td>06:</td><td>1101-0-101101011110101-10nun01uu</td><td>x-nx-x-----------------1-------uxx--</td></tr><tr><td>07:</td><td>0nuu-00-----------------0100100uu</td><td>--u0nn-------------------1-1-u--</td></tr><tr><td>08:</td><td>---u01-----------------0--0n010-u</td><td>n-nxxu-------------------un--</td></tr><tr><td>09:</td><td>0n----------------------0--1-1--0u</td><td>x-uu-0----------------------u--</td></tr><tr><td>10:</td><td>1--1-1-------------------0--1--</td><td>---u-----------------------1-un--</td></tr><tr><td>11:</td><td>-1n----------------------0--</td><td>x-nxn-----------------------n--</td></tr><tr><td>12:</td><td>---0-----------------------1--</td><td>---u-----------------------nu--</td></tr><tr><td>13:</td><td>n--1-----------------------</td><td></td></tr><tr><td>14:</td><td>--n-----------------------</td><td></td></tr><tr><td>15:</td><td>u-1-1-----------------------</td><td></td></tr><tr><td>16:</td><td>un0-0-----------------------</td><td></td></tr></tbody></table>

An important parameter to evaluate the cost of the attack is $C_{\text{block}}$, the complexity to find near-collision blocks. An optimistic hypothesis is that we can find them with same complexity as in the attack of [SBK$^{+17}$], i.e. $C_{\text{block}} = 2^{64.7}$. As mentioned earlier, we have conducted tests to verify that one can easily find short non-linear differential paths, regardless of the input chaining difference and value, to allow for a good use of neutral bits (one path example is given in Table 8).

We note that our trails are somewhat more constrained than the trails used in the collision attack, because we have denser chaining value differences and we have a few more conditions in the last round, as seen in Table 3. This could lead to fewer degrees of freedom than in the collision attack of Stevens et al., and increase the cost of finding a conforming block. In particular, this can affect the use of accelerating techniques such as neutral bits and boomerangs; boomerangs are the most powerful technique, but they require significant degrees of freedom in the path construction. Therefore, we also consider a conservative complexity estimate, where we assume that boomerangs are no longer available. Since there are three boomerangs in the trail of [SBK$^{+17}$], this would give $C_{\text{block}} = 2^{67.7}$.

Our experiments show that those assumptions are reasonable. The path given in Table 8 is about as constrained as the path used for the second block of the collision attack [SBK$^{+17}$] in the first round. In particular, most condition are in the first 6 steps, and don't affect the use of neutral bits, and the same
three boomerang are available. In general we expect similar results with a few boomerangs, but this might of course vary depending on the exact chaining input difference/value.

Finally, with the optimistic hypothesis, the best trade-off is to use a limit of $3.5 \cdot C_{\text{block}}$, for a total complexity of

$$2^{64.68} + 2^{61.70} + 3.5 \cdot C_{\text{block}} \approx 2^{66.9} \quad (\text{using } C_{\text{block}} = 2^{64.7})$$

With the conservative hypothesis, the best trade-off is to set the limit at $2.5 \cdot C_{\text{block}}$, for a total complexity of

$$2^{66.84} + 2^{64.03} + 2.5 \cdot C_{\text{block}} \approx 2^{69.35} \quad (\text{using } C_{\text{block}} = 2^{67.7})$$

There are other trade-offs possible between the various parameters of attack. For instance, we discussed attacks with a limited number of near-collision blocks in Section 6.1; we can now evaluate the complexity of the resulting attacks. If we limit the attack to 8 near-collision blocks, the best trade-offs give the following complexities for the optimistic and conservative hypothesis respectively:

$$2^{65.44} + 2^{63.23} + 3.5 \cdot C_{\text{block}} \approx 2^{67.2} \quad (\text{using } C_{\text{block}} = 2^{64.7})$$

$$2^{67.20} + 2^{64.75} + 2.5 \cdot C_{\text{block}} \approx 2^{69.5} \quad (\text{using } C_{\text{block}} = 2^{67.7})$$

Even with a limit of only 4 near-collision blocks, we have a relatively small increase of the complexity, with the following trade-offs:

$$2^{66.74} + 2^{63.82} + 7.0 \cdot C_{\text{block}} \approx 2^{68.3} \quad (\text{using } C_{\text{block}} = 2^{64.7})$$

$$2^{68.18} + 2^{63.70} + 4.0 \cdot C_{\text{block}} \approx 2^{70.2} \quad (\text{using } C_{\text{block}} = 2^{67.7})$$

# 7 Conclusion and Future Works

This work puts another nail in the SHA-1 coffin, with almost practical chosen-prefix collisions, between five and twenty-six times more expensive than the identical-prefix collisions recently demonstrated. This shows that continued usage of SHA-1 for certificates or for authentication of handshake messages in TLS, SSH or IKE is dangerous, and could already be abused today by a well-motivated adversary. SHA-1 has been broken since 2004, but it is still used in many security systems; we strongly advise users to remove SHA-1 support to avoid downgrade attacks.

More generally, our results show that, for some hash functions, chosen-prefix collision attacks are much easier than previously expected, and potentially not much harder than a normal collision search.

Our research opens several new directions. Obviously, future work will have to implement this attack to demonstrate a real chosen-prefix collision for SHA-1. While the computation cost of our attack is somewhat practical, SHA-1 attacks still require a huge computation power (thousands of GPUs in order to obtain the chosen-prefix collision in a reasonable time) and a large implementation effort.
For a concrete demonstration, a good target would be to break a protocol such as TLS or IKE, or to build a rogue certificate authority.

Another research direction is to study how one can improve SHA-1 collision attacks, not only for minimising the cost of finding a simple collision, but to improve our chosen-prefix collision search complexity. In particular, our attack requires the ability to reach many distinct output differences for the compression function. In this paper, to simplify our analysis, we only considered the differential trail from [SBK+17] because a real collision was found with this trail, and a precise complexity evaluation was conducted. However, it should be possible to increase the pool of available differences, and further reduce the total complexity, by using other (slightly more costly) differential trails.

Finally, a last direction is to evaluate how our strategy actually applies to other hash functions, such as RIPEMD, (reduced-round) SHA-2, or even others. Again, this will require a deep knowledge of the functions studied, as many details might impact the overall complexity. We can however expect that our attack strategy will be applicable mostly on classical Davies-Meier constructions inside a single-pipe Merkle-Damgård operating mode.

In order to make our work easier to verify, we are publishing some additional data and code online at: https://github.com/Cryptosaurus/sha1-cp.

## Acknowledgements

The authors would like to thank the anonymous referees for their helpful comments. We also thank Paul Wouters (Red Hat) and Marc Stevens (CWI) for additional comments. The second author is supported by Temasek Laboratories, Singapore.

## References

[BC04] Eli Biham and Rafi Chen. Near-collisions of SHA-0. In Matthew Franklin, editor, *CRYPTO 2004*, volume 3152 of LNCS, pages 290–305. Springer, Heidelberg, August 2004.

[BCJ$^{+05}$] Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, and William Jalby. Collisions of SHA-0 and reduced SHA-1. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 36–57. Springer, Heidelberg, May 2005.

[BL16] Karthikeyan Bhargavan and Gaëtan Leurent. Transcript collision attacks: Breaking authentication in TLS, IKE and SSH. In *NDSS 2016*. The Internet Society, February 2016.

[Bra90] Gilles Brassard, editor. *CRYPTO*, volume 435 of *Lecture Notes in Computer Science*. Springer, 1990.

[CJ98] Florent Chabaud and Antoine Joux. Differential collisions in SHA-0. In Hugo Krawczyk, editor, *CRYPTO'98*, volume 1462 of LNCS, pages 56–71. Springer, Heidelberg, August 1998.

[Dam89] Ivan Damgård. A Design Principle for Hash Functions. In Brassard [Bra90], pages 416–427.
[Dam90] Ivan Damgård. A design principle for hash functions. In Gilles Brassard, editor, *CRYPTO'89*, volume 435 of LNCS, pages 416-427. Springer, Heidelberg, August 1990.

[dB94] Bert den Boer and Antoon Bosselaers. Collisions for the compressin function of MD5. In Tor Helleseth, editor, *EUROCRYPT'93*, volume 765 of LNCS, pages 293-304. Springer, Heidelberg, May 1994.

[DMR07] Christophe De Cannière, Florian Mendel, and Christian Rechberger. Collisions for 70-step SHA-1: On the full cost of collision search. In Carlisle M. Adams, Ali Miri, and Michael J. Wiener, editors, *SAC 2007*, volume 4876 of LNCS, pages 56-73. Springer, Heidelberg, August 2007.

[JP07] Antoine Joux and Thomas Peyrin. Hash functions and the (amplified) boomerang attack. In Alfred Menezes, editor, *CRYPTO 2007*, volume 4622 of LNCS, pages 244-263. Springer, Heidelberg, August 2007.

[Kli06] Vlastimil Klima. Tunnels in hash functions: MD5 collisions within a minute. Cryptology ePrint Archive, Report 2006/105, 2006. http://eprint.iacr.org/2006/105.

[KPS15] Pierre Karpman, Thomas Peyrin, and Marc Stevens. Practical free-start collision attacks on 76-step SHA-1. In Rosario Gennaro and Matthew J. B. Robshaw, editors, *CRYPTO 2015, Part I*, volume 9215 of LNCS, pages 623-642. Springer, Heidelberg, August 2015.

[Leu12] Gaëtan Leurent. Analysis of differential attacks in ARX constructions. In Xiaoyun Wang and Kazue Sako, editors, *ASIACRYPT 2012*, volume 7658 of LNCS, pages 226-243. Springer, Heidelberg, December 2012.

[LPRR07] Mario Lamberger, Norbert Pramstaller, Christian Rechberger, and Vincent Rijmen. Second preimages for SMASH. In Masayuki Abe, editor, *CT-RSA 2007*, volume 4377 of LNCS, pages 101-111. Springer, Heidelberg, February 2007.

[Mer89] Ralph C. Merkle. One Way Hash Functions and DES. In Brassard [Bra90], pages 428-446.

[Mer90] Ralph C. Merkle. One way hash functions and DES. In Gilles Brassard, editor, *CRYPTO'89*, volume 435 of LNCS, pages 428-446. Springer, Heidelberg, August 1990.

[MRS15] Florian Mendel, Vincent Rijmen, and Martin Schläffer. Collision attack on 5 rounds of Grøstl. In Carlos Cid and Christian Rechberger, editors, *FSE 2014*, volume 8540 of LNCS, pages 509-521. Springer, Heidelberg, March 2015.

[Nat93] National Institute of Standards and Technology. FIPS 180: Secure Hash Standard, May 1993.

[Nat95] National Institute of Standards and Technology. FIPS 180-1: Secure Hash Standard, April 1995.

[Nat02] National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard, August 2002.

[Nat15] National Institute of Standards and Technology. FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, August 2015.

[Pey07] Thomas Peyrin. Cryptanalysis of Grindahl. In Kaoru Kurosawa, editor, *ASIACRYPT 2007*, volume 4833 of LNCS, pages 551-567. Springer, Heidelberg, December 2007.

[Riv91] Ronald L. Rivest. The MD4 message digest algorithm. In Alfred J. Menezes and Scott A. Vanstone, editors, *CRYPTO'90*, volume 537 of LNCS, pages 303-311. Springer, Heidelberg, August 1991.
[Riv92] Ronald L. Rivest. *RFC 1321: The MD5 Message-Digest Algorithm*. Internet Activities Board, April 1992.

[SBK<sup>+</sup>17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. The first collision for full SHA-1. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part I*, volume 10401 of LNCS, pages 570–596. Springer, Heidelberg, August 2017.

[SKP16] Marc Stevens, Pierre Karpman, and Thomas Peyrin. Freestart collision for full SHA-1. In Marc Fischlin and Jean-Sébastien Coron, editors, *EUROCRYPT 2016, Part I*, volume 9665 of LNCS, pages 459–483. Springer, Heidelberg, May 2016.

[SLdW07] Marc Stevens, Arjen K. Lenstra, and Benne de Weger. Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In Moni Naor, editor, *EUROCRYPT 2007*, volume 4515 of LNCS, pages 1–22. Springer, Heidelberg, May 2007.

[SSA<sup>+</sup>09] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K. Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger. Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. In Shai Halevi, editor, *CRYPTO 2009*, volume 5677 of LNCS, pages 55–69. Springer, Heidelberg, August 2009.

[Ste12] Marc Stevens. *Attacks on Hash Functions and Applications*. PhD thesis, Leiden University, June 2012.

[Ste13] Marc Stevens. New collision attacks on SHA-1 based on optimal joint local-collision analysis. In Thomas Johansson and Phong Q. Nguyen, editors, *EUROCRYPT 2013*, volume 7881 of LNCS, pages 245–261. Springer, Heidelberg, May 2013.

[vW99] Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. *Journal of Cryptology*, 12(1):1–28, 1999.

[WLF<sup>+</sup>05] Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, and Xiuyuan Yu. Cryptanalysis of the hash functions MD4 and RIPEMD. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 1–18. Springer, Heidelberg, May 2005.

[WY05] Xiaoyun Wang and Hongbo Yu. How to break MD5 and other hash functions. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 19–35. Springer, Heidelberg, May 2005.

[WYY05a] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding collisions in the full SHA-1. In Victor Shoup, editor, *CRYPTO 2005*, volume 3621 of LNCS, pages 17–36. Springer, Heidelberg, August 2005.

[WYY05b] Xiaoyun Wang, Hongbo Yu, and Yiqun Lisa Yin. Efficient collision search attacks on SHA-0. In Victor Shoup, editor, *CRYPTO 2005*, volume 3621 of LNCS, pages 1–16. Springer, Heidelberg, August 2005.
# SHA-1 is a Shambles*

## First Chosen-Prefix Collision on SHA-1
and Application to the PGP Web of Trust

Gaëtan Leurent<fnref n="1" /> and Thomas Peyrin<fnref n="2" />,<fnref n="3" />

**Abstract.** The SHA-1 hash function was designed in 1995 and has been widely used during two decades. A theoretical collision attack was first proposed in 2004 [29], but due to its high complexity it was only implemented in practice in 2017, using a large GPU cluster [23]. More recently, an almost practical chosen-prefix collision attack against SHA-1 has been proposed [12]. This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more threatening for real protocols.

In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collision attacks against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity (expressed in terms of SHA-1 equivalents on this GPU) of $2^{61.2}$ rather than $2^{64.7}$, and chosen-prefix collisions with a complexity of $2^{63.4}$ rather than $2^{67.1}$. When renting cheap GPUs, this translates to a cost of US$ 11k for a collision, and US$ 45k for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid US$ 75k because GPU prices were higher, and we wasted some time preparing the attack).

Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH), if generated extremely quickly. We strongly advise to remove SHA-1 from those type of applications as soon as possible.

We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to an impersonation attack. This proves that SHA-1 signatures now offer virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).

**Keywords:** SHA-1 · Cryptanalysis · Chosen-prefix collision · HPC · GPU · PGP · GnuPG

<footnote n="1">¹ Inria, France</footnote>

<footnote n="2">² Nanyang Technological University, Singapore</footnote>

<footnote n="3">³ Temasek Laboratories, Singapore</footnote>

<footnote>gaëtan.leurent@inria.fr, thomas.peyrin@ntu.edu.sg</footnote>

<footnote>https://sha-mbles.github.io/</footnote>

<footnote>*This is the full version of the paper of the same title published at USENIX Security '20.</footnote>
# 1 Introduction

Cryptographic hash functions are present in countless security applications and protocols, used for various purposes such as building digital signature schemes, message authentication codes or password hashing functions. In the key application of digital signatures for example, hash functions are classically applied on the message before signing it, as a domain extender and also to provide security guarantees. Informally, a cryptographic hash function $H$ is a function that maps an arbitrarily long message $M$ to a fixed-length hash value (we denote $n$ its bit size). Collision resistance is the main security property expected from a hash function: it should be hard for an adversary to compute a collision (or identical-prefix collision), i.e. two distinct messages $M$ and $M'$ that map to the same hash value $H(M) = H(M')$, where by “hard” one means not faster than the generic $2^{n/2}$ computations birthday attack.

A cryptanalyst will try to find a collision for the hash function at a reduced cost, but ad-hoc collision attacks are hard to exploit in practice, because the attacker usually has little control over the value of the actual colliding messages (in particular where the differences are inserted, which are the interesting parts when attacking a digital signature scheme). Thus, one can consider stronger variants of the collision attack more relevant in practice, such as the so-called chosen-prefix collision [25] or CP collision. Two message prefixes $P$ and $P'$ are first given as challenge to the adversary, and his goal is to compute two messages $M$ and $M'$ such that $H(P \parallel M) = H(P' \parallel M')$, where $\parallel$ denotes concatenation. With such ability, the attacker can obtain a collision with arbitrarily chosen prefixes, potentially containing meaningful information. A CP collision can also be found generically with $2^{n/2}$ computations (thus $2^{80}$ for a 160-bit hash function like SHA-1), but ad-hoc CP collision attacks are much more difficult to find than plain collision attacks, because of the uncontrolled internal differences created by the prefixes. Yet, a CP collision attack was found for the MD5 hash function [25], eventually leading to the creation of colliding X.509 certificates, and later of a rogue Certificate Authority (CA) [27]. CP collisions have also been shown to break important internet protocols, including TLS, IKE, and SSH [1], because they allow forgeries of the handshake messages if they can be generated extremely quickly.

Largely inspired by MD4 [19] and then MD5 [20], SHA-1 [16] is one the most famous cryptographic hash functions in the world, having been the NIST and de-facto worldwide hash function standard for nearly two decades. It remained a NIST standard until its deprecation in 2011 (and was forbidden for digital signatures at the end of 2013). Indeed, even though its successors SHA-2 or SHA-3 are believed to be secure, SHA-1 has been broken by a theoretical collision attack in 2004 [29]. Due to its high technicality and computational complexity (originally estimated to about $2^{69}$ hash function calls), this attack was only implemented in practice in 2017, using a large GPU cluster [23]. Unfortunately, the SHA-1 deprecation process has been quite slow and one can still observe many uses of SHA-1 in the wild, because it took more than a decade to compute an actual collision, plain collisions are difficult to use directly to attack a protocol, and migration is expensive. Web browsers have recently started to reject certificates with SHA-1 signatures, but there are still many users with older browsers, and many protocols and software that allow SHA-1 signatures. As observed in [12], it is still possible to buy a SHA-1 certificate from a trusted CA, many email clients accept a SHA-1 certificate when opening a TLS connection, and SHA-1 is also widely supported to authenticate TLS handshake messages.

Very recently, a CP collision attack against SHA-1 has been described in [12] (but not implemented), which requires an estimated complexity between $2^{66.9}$ and $2^{69.4}$ SHA-1 computations. It works with a two-phase strategy: given the challenge prefixes and the random differences on the internal state it will induce, the first part of the attack uses a birthday approach to limit the internal state differences to a not-too-big subset (as done in [25, 22]). From this subset, reusing basic principles of the various collision search
<table><caption>**Table 1:** Comparison of previous and new cryptanalysis results on SHA-1. A free-start collision is a collision of the compression function only, where the attacker has full control on all the primitive's inputs. Complexities in the table are given in terms of SHA-1 equivalents on a GTX-970 GPU (when possible).</caption><thead><tr><th>Function</th><th>Collision type</th><th>Complexity</th><th>Ref.</th></tr></thead><tbody><tr><td rowspan="4">SHA-1</td><td rowspan="2">free-start collision</td><td>2<sup>57.5</sup></td><td>[24]</td></tr><tr><td>2<sup>69</sup></td><td>[29]</td></tr><tr><td rowspan="2">collision</td><td>2<sup>64.7</sup></td><td>[22, 23]<sup>a</sup></td></tr><tr><td>2<sup>61.2</sup></td><td>New</td></tr><tr><td rowspan="3">chosen-prefix collision</td><td>2<sup>77.1</sup></td><td>[22]</td></tr><tr><td>2<sup>67.1</sup></td><td>[12]</td></tr><tr><td>2<sup>63.4</sup></td><td>New</td></tr></tbody></table>

advances on SHA-1, one slowly adds successive message blocks to come closer to a collision, eventually reaching the goal after a dozen blocks. Even though these advances put the CP collisions within practical reach for very well-funded entities, it remains very expensive to conduct and also very difficult to implement as the attack contains many very technical parts.

## 1.1 Our Contributions

In this article, we exhibit the very first chosen-prefix collision against SHA-1, with a direct application to PGP/GnuPG security. Our contributions are threefold.

**Complexity improvements.** While the work of [12] was mostly about high-level techniques to turn a collision attack into a chosen-prefix collision attack, we have to look at the low-level details to actually implement the attack. This gave us a better understanding of the complexity of the attack, and we managed to significantly improve several parts of the attacks (See Table 1).

First, we have improved the use of degrees of freedom (neutral bits [3] and boomerangs [10]) during the search for near-collision blocks. This reduces the computational complexity for both plain and chosen-prefix collision attacks, leading to important savings: on an Nvidia GTX 970, plain collisions can now be computed with a complexity of 2<sup>61.2</sup> rather than 2<sup>64.7</sup> (expressed in terms of SHA-1 equivalents on this GPU). We note that the general ideas underlying these improvements might be interesting for cryptanalysis of algorithms beyond SHA-1.

Second, we improved the graph-based technique of [12] to compute a chosen-prefix collision. Using a larger graph and more heuristic techniques, we can significantly reduce the complexity of a chosen-prefix collision attack, taking full advantage of the improvements on the near-collision block search. This results in a chosen-prefix collision attack with a complexity of 2<sup>63.4</sup> rather than 2<sup>67.1</sup>.

**Record computation.** We have implemented the entire chosen-prefix collision attack from [12], with those improvements. This attack is extremely technical, contains many details, various steps, and requires a lot of engineering work. Performing such a large-scale computation is still quite expensive, but is accessible with an academic budget. More precisely, we can rent cheap GPUs from providers that use gaming or mining cards in consumer-grade PCs, rather than the datacenter-grade hardware used by big

<footnote>a Equivalent to 2<sup>61</sup> SHA-1 on CPU, 2<sup>64.7</sup> on GPU</footnote>
<caption>**Table 2:** Complexity of the attacks against SHA-1 reported in this paper on several GPUs. The complexity is given in SHA-1 equivalents (using hashcat benchmarks). For the cost evaluation we assume that one GTX 1060 GPU can be rented for a price of US$35/month (the two phases of the attack are easily parallelisable): https://web.archive.org/web/20191229164814/https://www.gpuserversrental.com/</caption>

To attack MD5 || SHA-1, we use the multicollision attack of Joux [9] with three phases: (i) a CP collision on SHA-1, (ii) 64 collisions on SHA-1, and (iii) 2<sup>64</sup> evaluations of MD5.

<table><thead><tr><th>Function</th><th>Collision type</th><th>GPU</th><th>Time</th><th>Complexity</th><th>Cost</th></tr></thead><tbody><tr><td rowspan="6">SHA-1</td><td rowspan="3">collision</td><td>GTX 970</td><td>22 years</td><td>2<sup>61.2</sup></td><td rowspan="3">US$ 11k</td></tr><tr><td>GTX 1060</td><td>27 years</td><td>2<sup>61.6</sup></td></tr><tr><td>GTX 1080 Ti</td><td>8 years</td><td>2<sup>61.6</sup></td></tr><tr><td rowspan="3">chosen-prefix</td><td>GTX 970</td><td>99 years</td><td>2<sup>63.4</sup></td><td rowspan="3">US$ 45k</td></tr><tr><td>GTX 1060</td><td>107 years</td><td>2<sup>63.5</sup></td></tr><tr><td>GTX 1080 Ti</td><td>34 years</td><td>2<sup>63.6</sup></td></tr><tr><td rowspan="3">MD5 || SHA-1</td><td rowspan="3">both (plain or CP)</td><td>GTX 970</td><td>1400 years</td><td>2<sup>67.2</sup></td><td rowspan="3">US$ 720k</td></tr><tr><td>GTX 1060</td><td>1700 years</td><td>2<sup>67.6</sup></td></tr><tr><td>GTX 1080 Ti</td><td>540 years</td><td>2<sup>67.6</sup></td></tr></tbody></table>

cloud providers. This gives a total cost significantly smaller than US$100k to compute a chosen-prefix collision. We give more detailed complexity and cost estimates in Table 2.

We have successfully run the computation over a period of two months, using 900 GPUs (Nvidia GTX 1060). Our attack uses one partial block for the birthday stage, and 9 near-collision blocks. We paid US$75k to rent the GPUs from GPUserversrental, but the actual price could be smaller because we lost some time tuning the attack. There is also a large variability depending on luck, and GPU rental prices fluctuate with cryptocurrency prices.

**PGP/GnuPG impersonation.** Finally, in order to demonstrate the practical impact of chosen-prefix collisions, we used our CP collision for a PGP/GnuPG impersonation attack. The chosen prefixes correspond to headers of two PGP identity certificates with keys of different sizes, an RSA-8192 key and an RSA-6144 key. By exploiting properties of the OpenPGP and JPEG format, we can create two public keys (and their corresponding private keys): key A with the victim name, and key B with the attacker name and picture, such that the identity certificate containing the attacker key and picture leads to the same SHA-1 hash as the identity certificate containing the victim key and name. Therefore, the attacker can request a signature of his key and picture from a third party (from the Web of Trust or from a CA) and transfer the signature to key A. The signature stays valid because of the collision, while the attacker controls key A with the name of the victim, and signed by the third party. Therefore, he can impersonate the victim and sign any document in her name.

## 1.2 SHA-1 Usage and Impact

Our work shows that SHA-1 is now fully and practically broken for use in digital signatures. GPU technology improvements and general computation cost decrease will further reduce the cost, making it affordable for any ill-intentioned attacker in the very near future.

SHA-1 usage has significantly decreased in the last years; in particular web browsers now reject certificates signed with SHA-1. However, SHA-1 signatures are still supported in a large number of applications. SHA-1 is the default hash function used for certifying PGP keys in the legacy branch of GnuPG (v 1.4), and those signatures were accepted by
the modern branch of GnuPG (v 2.2) before we reported our results. Many non-web TLS clients also accept SHA-1 certificates, and SHA-1 is still allowed for in-protocol signatures in TLS and SSH. Even if actual usage is low (a few percent), the fact that SHA-1 is allowed threatens the security because a man-in-the-middle attacker can downgrade the connection to SHA-1. SHA-1 is also the foundation of the GIT versioning system, and it is still in DNSSEC signatures. There are probably a lot of less known or proprietary protocols that still use SHA-1, but this is more difficult to evaluate.

## 1.3 Outline

We first recall SHA-1 inner workings and previous cryptanalysis on this hash function in Section 2. We then provide improvements over the state-of-the-art SHA-1 collision attacks in Section 3 and Section 4, and we describe the details of the SHA-1 chosen-prefix collision computation in Section 5. Finally, we show a direct application of our CP collision attack with a PGP/GnuPG impersonation (together with discussions on other possible applications) in Section 6. We discuss SHA-1 usage and the impact of our results in Section 7. Eventually, we conclude and propose future works in Section 8.

# 2 Preliminaries

In this section, we describe the SHA-1 hash function (we refer to [16] for all the complete details) and summarize the previous cryptanalysis relevant to our new work.

## 2.1 Description of SHA-1

SHA-1 is a 160-bit hash function that follows the well-known Merkle-Damgård [6, 15] paradigm. A padding is first applied to the message input (with message length encoded) so that we obtain a multiple of 512 bits, and this bit string is divided into blocks $m_i$ of 512 bits each. Then, each block $m_i$ is processed via the SHA-1 compression function (denoted $h$) to update a 160-bit chaining variable (denoted $cv_i$) that is initialised to a constant and public initial value (denoted IV): $cv_0 = IV$. More precisely, we have $cv_{i+1} = h(cv_i, m_{i+1})$. When all blocks have eventually been processed, the last chaining variable is the final hash output.

The SHA-1 compression function resembles other members of the MD-SHA family of hash functions. It uses the Davies-Meyer construction, that turns a block cipher $E$ into a compression function: $cv_{i+1} = E_{m_{i+1}}(cv_i) + cv_i$, where $E_k(y)$ is the encryption of the plaintext $y$ with the key $k$, and + is a word-wise modular addition.

The internal block cipher is composed of 4 rounds of 20 steps each (for a total of 80 steps), where one step follows a generalised Feistel network. More precisely, the internal state is divided into five registers ($A_i, B_i, C_i, D_i, E_i$) of 32-bit each and at each step, an extended message word $W_i$ updates the registers as follows:

$$ 
\left\{ 
\begin{aligned}
A_{i+1} &= (A_i \ll 5) + f_i(B_i, C_i, D_i) + E_i + K_i + W_i \\
B_{i+1} &= A_i \\
C_{i+1} &= B_i \gg 2 \\
D_{i+1} &= C_i \\
E_{i+1} &= D_i
\end{aligned}
\right. 
$$

where $K_i$ are predetermined constants and $f_i$ are boolean functions (in short: IF function for the first round, XOR for the second and fourth round, MAJ for the third round, see Table 3). Since only a single register value is updated, we can express the SHA-1 step function using a single variable:

$$ A_{i+1} = (A_i \ll 5) + f_i(A_{i-1}, A_{i-2} \gg 2, A_{i-3} \gg 2) + (A_{i-4} \gg 2) + K_i + W_i. $$
<table><caption>**Table 3:** Boolean functions and constants of SHA-1</caption><thead><tr><th>step i</th><th>f<sub>i</sub>(B, C, D)</th><th>K<sub>i</sub></th></tr></thead><tbody><tr><td>0 ≤ i &lt; 20</td><td>f<sub>IF</sub> = (B ∧ C) ⊕ (B̄ ∧ D)</td><td>0x5a827999</td></tr><tr><td>20 ≤ i &lt; 40</td><td>XOR = B ⊕ C ⊕ D</td><td>0x6ed6eba1</td></tr><tr><td>40 ≤ i &lt; 60</td><td>MAJ = (B ∧ C) ⊕ (B ∧ D) ⊕ (C ∧ D)</td><td>0x8fabbcdc</td></tr><tr><td>60 ≤ i &lt; 80</td><td>XOR = B ⊕ C ⊕ D</td><td>0xca62c1d6</td></tr></tbody></table>

For this reason, the differential trails figures in this article will only represent $A_i$, the other register values at a certain point of time can be deduced directly.

The extended message words $W_i$ are computed linearly from the incoming 512-bit message block $m$, the process being called message extension. One first splits $m$ into 16 32-bit words $M_0, \dots, M_{15}$, and then the $W_i$'s are computed as follows:

$$W_i = \begin{cases} M_i, & \text{for } 0 \le i \le 15 \\ (W_{i-3} \oplus W_{i-8} \oplus W_{i-14} \oplus W_{i-16}) \ll 1, & \text{for } 16 \le i \le 79 \end{cases}$$

In the rest of this article, we will use the notation $X[j]$ to refer to bit $j$ of word $X$.

## 2.2 Previous Works

We recall here the general state-of-the-art collision search strategies that we will use for our CP collision attack. Readers only interested by the applications of our CP collision attack can skip up to Section 6. In the rest of the article, unless stated otherwise, difference will refer to the XOR difference between two bits or the bitwise XOR difference between two words.

### 2.2.1 Differential Trails

The first results on SHA-0 (the predecessor of SHA-1) and SHA-1 were differential in nature and obtained by building differential paths from a linearization of the compression function (we call these *linear paths*, in opposition to *non-linear paths* which have been built without linearization): in order to simplify the analysis the attacker assumes that modular additions and boolean functions $f_i$ in the SHA-1 compression function are behaving as an XOR with regards to differential propagation. More precisely, the 32-bit modular addition is replaced by a 32-bit bitwise XOR and the $f_i$ functions are replaced by 3-input XOR operations. These assumptions are indeed happening with a certain probability, which will basically consist of the bulk of the final attack cost. Then, in order to further simplify the analysis while trying to minimize the number of differences present in the internal state (which will in turn increase the differential trail probability and therefore improve the final attack cost), these trails are generated with a succession of so-called local collisions: small message disturbances whose influence is immediately corrected with other message differences inserted in the subsequent SHA-1 steps, while following the SHA-1 message expansion. However, in this linearization model, impossibilities might appear in the first 20 steps of SHA-1 (as in some specific cases the $f_{IF}$ boolean function will never behave as a 3-input XOR with regards to differential propagation) and the cheapest trail candidates might not be the ones that start and end with the same difference (which is a property required to obtain directly a 1-block collision after the compression function feed-forward). This strategy could already break the collision resistance of SHA-0, but not yet for SHA-1 (due to a small rotation added in the message expansion of SHA-1, that forces disturbances to spread throughout the rounds).
<figure><img src="image_91.png" /><figcaption>**Figure 1:** 2-block collision attack using a linear trail $\delta_I \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and two non-linear trails $0 \rightsquigarrow \delta_I$ and $\delta_O \rightsquigarrow -\delta_I$ in the first 10~15 steps. Green values between bracket represent differences in the state.</figcaption></figure>

A huge breakthrough then happened in 2005: a team of researchers [29] showed that by generating non-linear differential trails (trails generated without linearizing the **SHA-1** step function) for the first 10~15 steps of the compression function, one could potentially connect any incoming input difference to any fixed difference $\delta_I$ at step 10~15. This flexibility allows to remove completely the impossibility issues one could face in the first steps due to the linearization (since this part is now non-linear). Even better, taking advantage of the Davies-Meyer construction used inside the compression function, it actually permits to perform the collision attack on **SHA-1** using only two blocks containing differences, while picking the cheapest differential trail from step 10~15 to 80. With two successive blocks using the same differential trails (just ensuring that the output difference of the two blocks have opposite signs: $0 \stackrel{\delta_M}{\rightleftharpoons} \delta_O$ and $\delta_O \stackrel{-\delta_M}{\rightleftharpoons} -\delta_O$), one can see in Figure 1 that a collision is obtained at the end of the second block because the internal state differences cancel out.

### 2.2.2 Improving the Efficiency of Collision Search

Once the differential trail is set the attacker must find a pair of messages that follows it. A simple strategy uses an early-abort tree exploration for the 16 first steps, taking advantage of the degrees of freedom in the message, while the remaining steps are probabilistic. More advanced amortization methods (neutral bits [3], boomerangs [11, 10] or message modification [29]) are used to control more than 16 steps. Because of this amortization, usually the first 20 or so steps (which hold with a low probability because of the non-linear trail) do not contribute to the final complexity of the attack.

**Neutral bits** were first introduced for the cryptanalysis of **SHA-0** [2, 3]. The idea is to find a small message modification (one or a few bits), that does not interact with necessary conditions in the differential path before a certain step $x$. Once a message pair following the differential path until step $x$ is found, one can get another pair valid until step $x$ by applying the modification. The probability that a modification is neutral until a step $x$ can be pre-analysed before running the attack. A key observation is that any combination of two of more neutral bits until step $x$ is likely to also be neutral until step $x$.

**Boomerangs [10] or tunnels [11]** are very similar amortization tools to neutral bits. Basically, they can be seen as neutral bits that are planned in advance. A perturbation built from one or a few local collisions (or relaxed versions) is neutral to the differential path after a few steps with a certain probability, but extra conditions are forced in the internal state and message to increase this probability. Boomerangs are generally more powerful than neutral bits (they can reach later steps than classical neutral bits), but consume more degrees of freedom. For this reason, only a few of them can be used, but their amortization gain is almost a factor 2.
Note that a lot of details have to be taken into account when using neutral bits or boomerangs, as many equations between internal state bits and message bits must be fulfilled in order for the differential path to be valid. Thus, they can only be placed at very particular bit positions and steps.

### 2.2.3 Chosen-prefix Collision Attacks

Chosen-prefix collision attacks are difficult to find for iterated hash functions such as SHA-1, because the attacker's task is then to find a collision while starting from a random difference in the internal state (due to the prefixes pair that is not controlled at all by him). This random difference prevents to use directly the collision search techniques for SHA-1 aforementioned, because the attacker has to erase this random difference somehow and the interesting differential paths are in fact a very small set, where all output differences $\delta_O$ only have a very low Hamming weight.

The first concrete application of a chosen-prefix collision attack was on MD5 [25] and this work was also the first to introduce a birthday search phase in order to partially avoid the random difference issue. The idea is to process random message blocks after the challenged prefixes, until the chaining variable difference $\delta$ belongs to a large predetermined set $S$. Since the message blocks after each prefix are chosen independently, this can be done with birthday complexity $\sqrt{\pi \cdot 2^n/|S|}$. Then, from that difference $\delta$, one can reach a collision by slowly erasing the remaining unwanted difference bits by successfully applying some near-collision blocks (see Figure 2). We note that the starting difference set $S$ during the birthday phase must not be too small, otherwise this phase would be too costly. Moreover, the near-collisions blocks must not be too expensive either, and this will of course depend on the cryptanalysis advancements of the compression function being studied. This two-phase strategy was applied in [22] to the full SHA-1, for a cost of $2^{77.1}$ hash calls. The improvement compared to the generic $2^{80}$ attack is not very large, due to the difficulty for an attacker to generate enough allowable differences that can later be erased efficiently with a near-collision block, which makes the birthday part by far the most expensive phase of the attack. In [22] a set $S$ of 192 allowable differences was used, by starting from one type of near collision block and then varying the signs of the message and output differences, and also by letting some uncontrolled differences spread during the very last steps of the compression function.

This was improved in [12] by generalising for SHA-1 the set of possible differences that can be obtained for a cheap cost with a single message block, increasing the set size to 8768 elements. Another crucial improvement from [12] is the utilization of a multi-block strategy for SHA-1 that allows to further greatly increase the size of the set $S$: the idea is that if an arbitrary input difference $\delta_R$ can be decomposed as $\delta_R = -(\delta_O^{(1)} + \delta_O^{(2)} + \dots + \delta_O^{(r)})$, where each $\delta_O^{(i)}$ can be reached as the output of a differential trail, the attacker just has to find near-collision blocks with output differences $\delta_O^{(1)}, \dots, \delta_O^{(r)}$, where each near-collision block will cancel one of the differences $\delta_O^{(i)}$ composing $\delta$ (see Figure 2). In particular, a clustering effect appears with this multi-block strategy, which can be leveraged by the attacker to select dynamically the allowable differences at the output of each successive block, to further reduce the attack complexity. This resulted in an estimated CP collision search complexity in the range of $2^{66.9}$ to $2^{69.4}$ hash evaluations, surprisingly not much greater than that of finding a simple collision.

## 3 Improving SHA-1 Collision Attack

Our first contribution is an improvement of the collision attack from Eurocrypt 2013 [22] and its GPU implementation from Crypto 2017 [23]. Through better use of degrees of freedom (message modifications and boomerangs) and code improvements, we gained a
<figure><img src="image_92.png" /></figure>
factor between 8 and 10 (depending on GPU architecture) on the time needed to find a
conforming block.

Since this part of our work is very technical, we only give an overview of our results in
this section. Technical details can be found in Appendix A and the corresponding code is
available at https://github.com/SHA-mbles/sha1-cp.

**3.1 Analysis of Previous Works**

First, we observed some differences between the theoretical analysis of [22] and the practical implementation of [23]. One of the boomerangs (on bit 6 of $M_6$) contradicts one of the conditions used to maximize the probability of the path. Using this boomerang still improves the attack, because the gain in efficiency is larger than the loss in probability, but this affect the complexity evaluation. Similarly, one of the neutral bits used in the GPU code (on bit 11 of $M_{13}$) contradicts another condition in the differential path, leading to an increase in complexity of a factor $2^{0.2}$.

In our analysis, we assume that the neutral bit on bit 11 of $M_{13}$ is not used, and that the boomerang on bit 6 of $M_6$ is only used for the last near-collision block, where the speed-up is most noticeable, and we have enough degrees of freedom to include all the boomerangs without difficulty. Therefore we can estimate more accurately the complexity of the previous CP attack [12] as $2^{67.1}$ SHA-1 computations, instead of the range of $2^{66.9}$ to $2^{69.4}$ reported previously.

**3.2 Additional Boomerangs**

We found some additional boomerangs that can be used to speed-up the attack, on bits 4, 5, and 6 of $M_{11}$. Those boomerangs are not used in previous attacks because they interact badly with conditions of the differential trail, but this can be fixed by changing the last correction of the boomerangs to be a modular addition correction instead of an XOR correction.

More precisely, boomerangs are based on local collisions: an initial message difference introduces a difference in the state and another message difference cancels the state difference at a later step. In previous works, both message differences affect a single bit, so that they can be considered either as an XOR difference or as a modular difference. In this work, we only enforce a fixed modular difference for some boomerangs; depending on the value of the initial message, this difference will affect one or several bits (due to carries). Therefore, we can relax some of the conditions and make the additional boomerangs compatible with the differential path.

**3.3 Precise Conditions of Neutral Bits**

We also improved the rate of partial solutions generated by looking more precisely at the effect of each neutral bit. In particular, we found that some neutral bits flip with very high probability a certain condition after the step for which they are considered neutral. Therefore, these bits can be used as message modifications rather than neutral bits: instead of considering both the initial message and the message with the neutral bit applied and to test both of them at the later step, we can directly test the condition and decide which message to consider. Using this bit as message modification instead of neutral bit is more efficient, as one invalid branch in the search tree will be rightfully not explored.

In some cases, we also found that a bit that is neutral up to step *i* can only break some of the conditions of step *i*, while the rest will never be impacted. Therefore, we can test the conditions that are not affected before using that neutral bit, so as to avoid unnecessary computations. This strategy can be seen as a more precise neutral bit approach, where
<caption>**Table 4:** Cost of collision attacks. One collision requires on average $2^{48.5} A_{33}$-solutions (those results include the boomerang on $M_6[8]$).</caption>

Note: we use the hashrate from hashcat, which is slightly over-optimistic (i.e. attack cost in SHA-1 computations is overestimated).

<table><thead><tr><th rowspan="2">GPU</th><th rowspan="2">arch</th><th rowspan="2">Hashrate</th><th colspan="2">Collision (old)</th><th colspan="2">Collision (new)</th><th rowspan="2">Gain</th></tr><tr><th>A<sub>33</sub> rate</th><th>SHA-1</th><th>A<sub>33</sub> rate (r)</th><th>SHA-1</th></tr></thead><tbody><tr><td>K20x (1 GPU)</td><td>Kepler</td><td>1.7GH/s</td><td>28k/s</td><td>2<sup>64.4</sup></td><td>255k/s</td><td>2<sup>61.2</sup></td><td>9.1</td></tr><tr><td>GTX 970</td><td>Maxwell</td><td>3.9GH/s</td><td>59k/s</td><td>2<sup>64.5</sup></td><td>570k/s</td><td>2<sup>61.2</sup></td><td>9.6</td></tr><tr><td>GTX 1060</td><td>Pascal</td><td>4.0GH/s</td><td>53k/s</td><td>2<sup>64.7</sup></td><td>470k/s</td><td>2<sup>61.6</sup></td><td>8.8</td></tr><tr><td>GTX 1080 Ti</td><td>Pascal</td><td>12.8GH/s</td><td>170k/s</td><td>2<sup>64.7</sup></td><td>1500k/s</td><td>2<sup>61.6</sup></td><td>8.8</td></tr></tbody></table>

the attacker doesn't work step-wise, but instead condition-wise: more fine-grained filtering will lead to computation savings.

All in all, these tricks result in a better exploration of the collision search tree by cutting branches earlier. We give detailed benchmarks results and complexity estimates in Table 4, after implementing our improvements in the code of [23] (where an $A_i$-solution refers to an input pair that is following the differential path until word $A_i$ inclusive).

## 3.4 Building Differential Trails

Following [12], we try to reuse as much as possible the previous works on SHA-1, and to keep our differential trail as close as possible to the attack of Stevens et al. [23], out of simplicity. More precisely, for each block of the collision phase, as starting point we reused exactly the same core differential path as in [23]: the difference positions in the message are the same, and the difference positions in the internal state are the same after the first 13 steps (roughly). We also tried to keep difference signs to be the same as much as possible. However, we made some modifications to the boomerangs and neutral bits as explained in the previous subsection.

The starting path skeleton is depicted in Figure 3. For each new block of the near-collision phase, we:

1. collect the incoming chaining variable and its differences and insert them inside the skeleton;

2. set the signs of the differences in the very last steps (chosen so as to minimize the final collision complexity according to the graph, see Section 4) and generate the linear system of all equations regarding the message words;

3. compute a valid non-linear differential path for the first steps;

4. generate base solutions, i.e. partial solutions up to $A_{14}$, possibly using help of neutral bits;

5. from the base solutions, search for a pair of messages that fulfils the entire differential path, using neutral bits, message modifications and boomerangs.

Steps 1 to 4 are done on CPU because they are not too computationally intensive, but step 5 runs on GPU.

We observe that in comparison with the classical collision attack [23], we have fewer degrees of freedom available in our differential paths, due to slightly more linear constraints we imposed on the late-step message bits. Moreover, for the first blocks of the near-collision phase, the attacker will have to handle a denser input difference on the chaining variable, which will render the non-linear part search a little more difficult and little more consuming in terms of freedom degrees. In any cases, we had enough degrees of freedom to find a conforming messages pair for all blocks during the attack.
<table><caption>**Figure 3:** Skeleton of starting differential path for all blocks during the near-collision phase of our CP collision attack on SHA-1 (only the first 20 steps are depicted). The MSB's are on the right and “-” stands for no constraint, while the notation “|” on two bits vertically adjacent means that these two bits must be equal. The other notations are similar to the ones used in [7]. This is only to give a general idea of the differential path used, as several conditions on the message and/or on the internal state are not represented here.</caption><thead><tr><th>i</th><th>A<sub>i</sub></th><th>W<sub>i</sub></th></tr></thead><tbody><tr><td>-4:</td><td></td><td></td></tr><tr><td>-3:</td><td></td><td></td></tr><tr><td>-2:</td><td>Incoming Chaining Variable</td><td></td></tr><tr><td>-1:</td><td></td><td></td></tr><tr><td>00:</td><td></td><td>---xx-----------------------x-</td></tr><tr><td>01:</td><td>??????????????????????????????--</td><td>xx-----------------------x---</td></tr><tr><td>02:</td><td>??????????????????????????????????</td><td>x-xx-x-----------------------xxx-</td></tr><tr><td>03:</td><td>??????????????????????????????????</td><td>--xxxx-----------------------x-</td></tr><tr><td>04:</td><td>??????????????????????????????????</td><td>x-xxxx-----------------------xx-x-</td></tr><tr><td>05:</td><td>??????????????????????????|?|????????</td><td>-x-----------------------x---</td></tr><tr><td>06:</td><td>??????????????????????????|?|????????</td><td>--x-x-----------------------0-0-xxx-</td></tr><tr><td>07:</td><td>????-----------------0-0-?????</td><td>xxx-xx-----------------1-1-x-x-</td></tr><tr><td>08:</td><td>??x-------------------|--0-0-?--?</td><td>---xx-----------------------x-</td></tr><tr><td>09:</td><td>??-------------------|--1?!-?--?</td><td>xx-----------------------0-x---</td></tr><tr><td>10:</td><td>??-------------------|0|?---??</td><td>x-xx-x-------------------1-xxx-</td></tr><tr><td>11:</td><td>??x-------------------|0|0---</td><td>--x-xx-------------------111-x-</td></tr><tr><td>12:</td><td>-----------------------111---</td><td>x-xxux-------------------xx-</td></tr><tr><td>13:</td><td>n-----------------------000--</td><td>x-xx-----------------------1u---</td></tr><tr><td>14:</td><td>--n----------------------111--</td><td>-----------------------1-xx-</td></tr><tr><td>15:</td><td>u-1-1----------------------</td><td>x-xxx-----------------------n---</td></tr><tr><td>16:</td><td>un0-0-----------------------</td><td>---u-----------------------nu---</td></tr><tr><td>17:</td><td>u-1-----------------------</td><td>-xxnn-----------------------n---</td></tr><tr><td>18:</td><td>u-u0-----------------------</td><td>--0-n-----------------------n-n-</td></tr><tr><td>19:</td><td>u-----------------------</td><td>-xuu-----------------------n---</td></tr><tr><td>20:</td><td>u-u-----------------------</td><td>x-nux-----------------------nnu-</td></tr></tbody></table>

We also remark that the incorporation of the additional short boomerangs reduces the number of neutral bits that can be used in comparison to [23]. Yet, this was not an issue as we still had enough to keep the GPU busy (in stage 5) while the CPU was producing the base solutions (in stage 4), even though our computation cluster is composed of low range CPUs.

# 4 Improving SHA-1 CP Collision Attack

In order to take advantage of the low-level improvements to collision attack techniques, we must also improve the high-level chosen-prefix collision attack.

The complexity of the birthday phase depends on the size of the set $S$ of differences that can be erased from the state, therefore we need a larger set. For the near-collision phase, the complexity depends on how we combine the near-collision blocks to erase the difference in the state. We improve the graph techniques of [12] and suggest a more heuristic approach, resulting in a lower average complexity, but without a guaranteed upper bound.

## 4.1 Graph Construction

In order to efficiently erase the differences from the set $S$, [12] uses a graph where vertices are the state difference in $S$, and there is an edge between $\delta$ and $\delta'$ if $\delta' - \delta$ can be obtained as the output difference of the compression function (using a near-collision block). The birthday phase designates a starting node in the graph and we just have to follow a path leading to the zero difference, as illustrated in Figure 4. For each edge, we search for
<figure><img src="image_93.png" /><figcaption>**Figure 4:** Graph search.</figcaption></figure>

<figure><img src="image_94.png" /><figcaption>**Figure 6:** Bi-directional.</figcaption></figure>

<figure><img src="image_95.png" /><figcaption>**Figure 5:** With clustering.</figcaption></figure>

<figure><img src="image_96.png" /><figcaption>**Figure 7:** Implicit.</figcaption></figure>

a block with the correct output difference, using near-collision search, with a cost that depends on the target difference. In the following, we denote the cost for the optimal output differences as $C_{\text{block}}$; it is equivalent to the cost of an identical-prefix collision.

**Large graph.** We started with the same approach as in [12], building a series of graphs with increasing limits on the number of blocks allowed. More precisely, we consider the set of all nodes that are reachable with a path of cost at most $24 C_{\text{block}}$ and up to 10 blocks. This results in a graph with $2^{36.2}$ nodes<fnref n="1" />, which requires 2TB of storage (storing only the nodes and their cost).

**Clustering.** In order to minimize the complexity of the near-collision phase of the attack, [12] uses a clustering technique to exploit multiple paths in the graph (see Figure 5). Indeed, the near-collision search does not have to commit to a fixed output difference. When two output differences correspond to useful paths in the graph and are compatible with the same differential path, the attacker can run the near-collision search and stop as soon as one of them is obtained.

Concretely, let us assume we have two output differences $\delta_1$ and $\delta_2$ compatible with the same differential trail, that can each be reached with a cost of $C_{\text{block}}$. There are two different ways to erase a difference $-\delta_1 - \delta_2$ in the state:

* a block with difference $\delta_1$, followed by a block with difference $\delta_2$;

* a block with difference $\delta_2$, followed by a block with difference $\delta_1$.

If we don't decide in advance the target difference for the first block, the search is expected to reach either $\delta_1$ or $\delta_2$ with a cost of only $0.5 C_{\text{block}}$, leading to an attack complexity of $1.5 C_{\text{block}}$ rather than $2 C_{\text{block}}$.

<footnote n="1">¹The largest graph suggested in [12] has size $2^{33.7}$.</footnote>
<table><caption>**Table 5:** Size of the set *S* with various limits on the maximum cost and on the number of near-collision blocks (log₂).</caption><thead><tr><th>Max Cost</th><th>1 bl.</th><th>2 bl.</th><th>3 bl.</th><th>4 bl.</th><th>5 bl.</th><th>6 bl.</th><th>7 bl.</th><th>8 bl.</th><th>9 bl.</th><th>10 bl.</th></tr></thead><tbody><tr><td>1 C<sub>block</sub></td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td><td>8.17</td></tr><tr><td>2 C<sub>block</sub></td><td>9.17</td><td>16.30</td><td>19.92</td><td>22.05</td><td>23.13</td><td>23.95</td><td>24.44</td><td>24.55</td><td>24.62</td><td>24.65</td></tr><tr><td>3 C<sub>block</sub></td><td>10.17</td><td>17.10</td><td>21.76</td><td>24.66</td><td>26.58</td><td>27.95</td><td>28.96</td><td>29.71</td><td>30.31</td><td>30.76</td></tr><tr><td>4 C<sub>block</sub></td><td>12.53</td><td>18.60</td><td>22.97</td><td>26.34</td><td>28.68</td><td>30.35</td><td>31.56</td><td>32.54</td><td>33.29</td><td>33.88</td></tr><tr><td>5 C<sub>block</sub></td><td>12.53</td><td>19.65</td><td>24.18</td><td>27.44</td><td>29.83</td><td>31.65</td><td>33.04</td><td>34.14</td><td>34.90</td><td>35.42</td></tr><tr><td>6 C<sub>block</sub></td><td>12.53</td><td>19.79</td><td>24.81</td><td>28.26</td><td>30.74</td><td>32.62</td><td>34.05</td><td>35.08</td><td>35.67</td><td>36.03</td></tr><tr><td>7 C<sub>block</sub></td><td>13.09</td><td>20.37</td><td>25.30</td><td>28.82</td><td>31.35</td><td>33.24</td><td>34.59</td><td>35.43</td><td>35.86</td><td>36.15</td></tr><tr><td>8 C<sub>block</sub></td><td>13.09</td><td>20.62</td><td>25.72</td><td>29.27</td><td>31.81</td><td>33.65</td><td>34.81</td><td>35.54</td><td>35.92</td><td>36.19</td></tr></tbody></table>

In our case, we initially consider nodes at distance up to 24 $C_{block}$ and we run the clustering technique to get a better estimate of the complexity when we don't specify in advance the sequence of differences. After several weeks of computation on a machine with 48 cores and 3TB of RAM, we find that almost 90% of the nodes are actually at distance 6 $C_{block}$ or less, as seen in Table 5.

All the differences in this set are active only on a 64-bit mask. Therefore, we use those bit positions for the birthday phase: we truncate SHA-1 to the remaining 96 bits<fnref n="2" /> and we generate a large number of partial collisions until one of them corresponds to a difference in the graph.

## 4.2 Bi-directional Graph

Since the CP collision attack is essentially a path search in a graph, we can use a bi-directional search to make the search more efficient. More precisely, when we evaluate the cost of a node, instead of just looking it up in the graph, we recompute all edges starting from the node to see if they reach the graph and compute the cost using the clustering formula. This corresponds to a bi-directional search where we pre-compute in the backwards direction the set of values that go to zero after at most 10 blocks, and during the online phase, we compute one block forward. This is illustrated by Figure 6, where black dots correspond to precomputed nodes stored in the graph, and white dots are only computed during the online phase.

This can be seen as a time-memory trade-off: we use nodes at a distance up to 11 blocks, but we only build explicitly the graph with 10 blocks. Moreover, we can use nodes that are not reachable with a single trail of cost below 24 $C_{block}$, and that are therefore excluded from our initial graph. Indeed, if there exists a trail such that the cost is below 24 $C_{block}$ when removing an edge, the forward search using that edge will hit the explicit graph, and we can evaluate the distance of the node.

We can't compute exactly the size of this implicit graph, but we can evaluate it experimentally by simulating the birthday phase of the attack. We found that we need on average $2^{26.4}$ attempts before hitting the graph, which corresponds to a graph size of roughly $2^{38}$ (assuming that we detect being in the graph with a probability of 0.75, as was the case with the parameters of [12]).

## 4.3 Implicit Nodes

Following [12], we build the graph using a set $\mathcal{D}$ of 8768 potential output differences with high probability (corresponding to a cost up to 8 $C_{block}$). However, there are many other

<footnote n="2">²Given by mask 0x7f000000, 0xff80001, 0x7ffff000, 0x7fffffc0, 0x7fffffff</footnote>
output differences that can be useful in our attack, even if they have a lower probability: we can use a block as long as the new state difference gets closer to a collision. Therefore, during the near-collision phase, instead of keeping only blocks with an output difference corresponding to an explicit edge of the graph, we keep all blocks that follow the trail up to step 61 and we look up the new state difference in the graph (using the bi-directional strategy above). With a larger number of usable output differences, the cost of each block decreases (Figure 7).

Again, we can't compute explicitly the complexity of this attack strategy, but we can run simulations. According to our experiments with the graph described above, the average cost of the near-collision phase is only $2C_{block}$, even though most of the nodes in the graph correspond to a cost of 6 $C_{block}$ when following edges that have been explicitly considered.

Finally, we can use this strategy to reduce the number of near-collision blocks used in the attack. In practice, we observed that most of the nodes in our graph can actually be reached with fewer than 11 blocks. In particular, when using output differences that do not correspond to edges of the graph, we often reach an output difference that can be erased with fewer blocks than expected, in particular for the first near-collision blocks.

# 5 Chosen-Prefix Collision Computation

Even though we managed to reduce the cost of the chosen-prefix collision for SHA-1 to only $2^{63.7}$ SHA-1 evaluations, performing such a large-scale computation remains very expensive. We show that it can be computed with an academic budget, for a total cost much lower than US$ 100k.

## 5.1 Attack Parameters

Using more blocks for the near-collision blocks part of the attack leads to improved attack complexity, but one can observe that the improvement becomes marginal as the number of block increases. Besides, in order to allow for a practical real-life use of our chosen-prefix collision (see next section), we had to enforce a limit on the total number of blocks.

Using the idea described in the previous section, we have the following parameters for the attack:

* We use a limit of at most 11 blocks, but we aim for 10 blocks at most for the attack (to fit in a 6144-bit key, see next section);

* The graph $\mathcal{G}$ has size roughly $2^{38}$, but it is not computed explicitly;

* The birthday stage is a parallel collision search algorithm (using the distinguished points technique of [28]) with a mask of 96 bits, and we need about $2^{26.4}$ partial collisions on those 96 bits. Therefore the expected complexity of the birthday phase is $\sqrt{\pi 2^{96} 2^{26.4}} \approx 2^{62}$;

* We use chains (consecutive iterations of the function from a starting point during the distinguished points technique) of length $2^{28}$, resulting in a data complexity of $1/2$ TB to store $2^{34}$ chains;

* We expect a cost of $2C_{block}$ for the near-collision phase.

In hindsight, we could have use longer chains to reduce the data storage, and to make sorting the data on our cluster easier. We could also have aimed for a lower number of blocks: our collision used only 9 blocks, and we could probably reach 8 or 7 without much impact on the complexity.

**Complexity estimate.** Overall, for the attack parameters chosen, the birthday part costs about $2^{62.05}$ SHA-1 computations, while the near-collision part is expected to require 1 $C_{block}$ for the last block, and 1 $C_{block}$ in total for the previous blocks.
As explained in Section A.1, we use the boomerang on $M_6[8]$ for the last block, so that the expected time to find a conforming block can be estimated directly from the figures of Table 4 as $C_{block} = 2^{48.5}/r$. For the intermediate blocks, we don't use this boomerang, so the rate is reduced to $r/1.9$ but we only require $2^{48.08} A_{33}$-solutions for one $C_{block}$. Our simulations show that the total cost for all intermediate blocks is roughly one $C_{block}$, therefore it will take time $C_{block} = 1.9 \cdot 2^{48.08}/r$. Finally, we can estimate the total attack time as

$$2^{62.05} \cdot h + \frac{2^{48.5} + 1.9 \cdot 2^{48.08}}{r},$$

with $r$ the $A_{33}$-solution rate (from Table 4), and $h$ the hash-rate for the birthday phase (from Section 5.3). We give concrete complexity estimates on several GPUs in Table 2. Our chosen-prefix collision attack is roughly four time as expensive as an identical-prefix attack.

## 5.2 A GPU Cluster

We originally estimated that our attack would cost around US$ 160k by renting GPUs from a cloud provider such as Amazon or Google (using spot or preemptible prices). However, since our computations do not need much communication between the GPUs, nor fancy inter-GPU task scheduling, we can consider renting cheaper GPUs from providers that use gaming or mining cards in consumer-grade PCs, rather than the datacenter-grade hardware used by big cloud providers. Services like gpuserversrental.com rent GTX 1060 or GTX 1080 GPUs for a price below 5 cents per month per CUDA core; which would give a total cost around US$ 75k to compute a chosen-prefix collision.

After some cost analysis, we have concluded that GTX 1060 GPUs offered a very good hashrate/cost ratio at the time of the chosen-prefix collision computation. GPU prices vary significantly depending on cryptocurrency prices, but at the time of writing, a GTX 1060 can be rented for about US$ 35 per month<fnref n="3" />. Our attack requires about 107 GPU-years using GTX 1060, which gives an estimated cost of $107 \times 35 \times 12 \approx US$ 45k$ to compute a chosen-prefix collision for SHA-1.

Our cluster was made of 150 machines with 6 GPU each (with a mix of GTX 1060 3G, and GTX 1060 6G), and one master node with two 2TB hard drives in a RAID configuration. The master node had a Core i7 CPU, but the GPU nodes had low-end Pentium or Celeron CPU with two cores. Each machine ran Ubuntu Linux, but there was no cluster management software installed (we used `clush` to run commands on all the nodes). We negotiated a price of US$ 37.8k per month (higher than current prices), and used the cluster for two months.

**Cost analysis.** We paid US$ 75.6k for our computation, but the cost could be as low as US$ 50k with currently lower GPU prices and less idle time. With the same methods, computing an identical-prefix SHA-1 collision would cost only about US$ 11k. This is clearly within reach of reasonable attackers.

Of course the underlying weakness of SHA-1 has always been present, even if it was not public (and maybe not discovered). We estimate that a PS3 cluster (as used by Stevens et al. [27], and as deployed by the US army<fnref n="4" />) could have implemented this attack for a cost of a few million dollars in 2010, when SHA-1 was still the most widely used hash function. This underlines that the deprecation process of SHA-1 should have been much faster after the publication of the first theoretical collision attack in 2004.

<footnote n="3">³More precisely, US$ 209 per month for 6 GTX 1060 3GB: https://web.archive.org/web/20191229164814/https://www.gpuserversrental.com/</footnote>

<footnote n="4">⁴https://phys.org/news/2010-12-air-playstation-3s-supercomputer.html</footnote>
<table><caption>**Table 6:** Timeline of the birthday phase.</caption><thead><tr><th>Date</th><th>Event</th><th>Complexity</th><th># collisions</th></tr></thead><tbody><tr><td>July 25</td><td>Starting cluster setup</td><td></td><td></td></tr><tr><td>July 27</td><td>Computation started</td><td></td><td></td></tr><tr><td>August 14</td><td>Step 2 unsuccessful</td><td>2<sup>61.9</sup></td><td>2<sup>25.8</sup></td></tr><tr><td>August 20</td><td>Step 2 unsuccessful</td><td>2<sup>62.4</sup></td><td>2<sup>26.6</sup></td></tr><tr><td>August 24</td><td>Step 2 unsuccessful</td><td>2<sup>62.6</sup></td><td>2<sup>27.1</sup></td></tr><tr><td>August 30</td><td>Step 2 successful!</td><td>2<sup>62.9</sup></td><td>2<sup>27.7</sup></td></tr></tbody></table>

Looking at the future, this attack will get even cheaper as computation costs decrease. Following Moore's law (that seems to be still valid for GPU<fnref n="5" />), we estimate that it should cost less than US$10k to generate a SHA-1 chosen-prefix collision by 2025.

## 5.3 Birthday Phase

In order to simplify the implementation, we implemented the birthday phase with two distinct steps: in the first step, each GPU computes independently a series of chains, and in the second step we gather all the results, sort them to find collisions in the end-points, and re-run the chain to locate the collisions. Our implementation runs at a speed of $h = 3.5$GH/s on GTX 1060 GPUs (respectively 3.2 GH/s on GTX 970 and 11 GH/s on GTX 1080 Ti). This is somewhat lower than the hashcat benchmarks reported in Table 2 because hashcat can skip some parts of SHA-1, and we have to keep two SHA-1 states in the registers to implement the birthday phase. Every time we run the second step, we then search the collisions in the graph, to determine whether we have reached a useful starting point (this is run on a separate machine with at least 1TB or RAM, and we let the cluster restart the first step in the meantime).

As shown in Table 6, we ran step 2 four times, and we have been quite unlucky in the birthday phase, only succeeded after finding $2^{27.7}$ collisions, rather than the estimated $2^{26.4}$. It took us 34 days to compute those chains, which corresponds to a hashrate 2.9 TH/s for our cluster (including downtime).

Interestingly, we got slightly fewer collisions than expected (after a given number of chains): we expected to compute $\sqrt{\pi 2^{96}C}$ SHA-1 to find C partial collisions, but our analysis is off by a factor roughly $2^{0.2}$. Given the small magnitude of the error, we didn't investigate further, but it could be due to an unknown bug in our code, or an issue in the analysis (such as a failed independence assumption, or an issue with chains that reach a cycle).

## 5.4 Near-collision Phase

The near-collision phase is very technical and very complex. Every time a block is found, we have to prepare the search for the next block. This first requires to traverse the graph $G$ to find the parameters for the next block: we have different constraints in the last steps depending on which output differences are desired. Then, we had to generate a new non-linear part for the early steps, as explained in Section 3.4. We used tools similar to [7], which take a lot of parametrization and trial-and-error to have a proper non-linear part that fits nicely with the core differential path. Finally, some testing and configuration of the GPU code was then required to check how neutral bits and boomerangs behaved in this new configuration. In particular, there were usually some adjustments to make in the

<footnote n="5">⁵https://blogs.nvidia.com/blog/2017/05/10/nvidia-accelerates-ai-launches-volta-dgx-workstation-robot-simulator-more/</footnote>
<table><caption>**Table 7:** Timeline of the near-collision phase. $C_{\text{block}}$ corresponds to $2^{19.17} A_{61}$-solutions, excepted for the last block where the use of an extra boomerang increases it to $2^{19.58}$</caption><thead><tr><th>Date</th><th>Event</th><th>#A<sub>61</sub>-sol</th><th>Complexity</th></tr></thead><tbody><tr><td>September 07</td><td>Block 1 found<sup>a</sup></td><td>2<sup>16</sup></td><td>0.11 C<sub>block</sub></td></tr><tr><td>September 09</td><td>Block 2 found</td><td>2<sup>13.5</sup></td><td>0.02 C<sub>block</sub></td></tr><tr><td>September 13</td><td>Block 3 found</td><td>2<sup>16.9</sup></td><td>0.21 C<sub>block</sub></td></tr><tr><td>September 14</td><td>Block 4 found</td><td>2<sup>10.8</sup></td><td>0.003 C<sub>block</sub></td></tr><tr><td>September 16</td><td>Block 5 found</td><td>2<sup>15.5</sup></td><td>0.08 C<sub>block</sub></td></tr><tr><td>September 18</td><td>Block 6 found</td><td>2<sup>15.5</sup></td><td>0.08 C<sub>block</sub></td></tr><tr><td>September 20</td><td>Block 7 found</td><td>2<sup>16</sup></td><td>0.11 C<sub>block</sub></td></tr><tr><td>September 21</td><td>Block 8 found</td><td>2<sup>14.5</sup></td><td>0.04 C<sub>block</sub></td></tr><tr><td>September 27</td><td>Block 9 found<sup>b</sup></td><td>2<sup>18.2</sup></td><td>0.38 C<sub>block</sub></td></tr></tbody></table>

GPU code for the more complex conditions in the path that involve several bit positions. The entire preparation process would have potentially to be performed again in case of any issue detected with the path found.

This was automated to some extent, but still took between a few hours and a few days of manual work to prepare for each block (it took more time for the first blocks because there are more constraints to build the path, and we were more experienced for the later blocks). Unfortunately, this means that the GPU cluster was not doing useful work during this time. We remark that our attack could have cost less if we had fully automated the entire cryptanalysis process, or if we had improved the search algorithm for the non-linear part of the differential path. This is definitely not impossible to achieve, but it would require a lot of tedious work.

For the last block, we started the computation without the boomerang on $M_6$[8], and modified the path and the code after one day to include it. As explained in Section 3, this extra boomerang reduces the quality of $A_{61}$-solutions, so that we need $4/3$ times the number of solutions ($2^{19.58}$ instead of $2^{19.17}$), but it almost doubles the production rate of these solutions. In total, this reduces the computation time by a factor $1.9/4/3 \approx 1.4$.

As expected, intermediate blocks cost much less than $C_{\text{block}}$ (the cost of a block with a pre-determined output difference) because we can target a large number of output differences. Only the last block is expected to cost $C_{\text{block}}$. However, we were quite lucky in this phase of attack, because we found all the blocks after only $0.9 C_{\text{block}}$, rather than the estimated $2 C_{\text{block}}$. In particular, the last block was found after only $2^{18.2} A_{61}$-solutions ($0.38 C_{\text{block}}$), instead of the expected $2^{19.58}$.

A timeline of the near-collision phase is given in Table 7, and the chosen-prefix collision is given in Appendix B (with the actual messages in Figure 13 and the intermediate differences in Table 9).

## 5.5 Resources Used

A quick overview of the resources used for each part is given in Table 8. If we evaluate the total useful GPU time spent for the attack, we have roughly:

* 78 years for the birthday phase

* 25 years for blocks 1 to 9

* 10 years for the last block

<footnote><sup>a</sup>Two solutions found</footnote>

<footnote><sup>b</sup>Using the $M_6$[8] boomerang</footnote>
<table><caption>**Table 8:** Resources used for the attack</caption><thead><tr><th>Phase</th><th>Step</th><th>Main resource</th><th>Repetitions</th><th>Wall time</th></tr></thead><tbody><tr><td>Setup</td><td>Preparation of the graph</td><td>CPU and RAM</td><td></td><td>≈ 1 month</td></tr><tr><td rowspan="4">Birthday</td><td>Computing chains</td><td>GPU</td><td></td><td>34 days</td></tr><tr><td>Sorting chains</td><td>Hard drive</td><td>4 ×</td><td>≈ 1 day</td></tr><tr><td>Locating collisions</td><td>GPU</td><td>4 ×</td><td>&lt; 1/2 day</td></tr><tr><td>Searching in graph</td><td>RAM</td><td>4 ×</td><td>&lt; 1/2 day</td></tr><tr><td rowspan="4">Blocks</td><td>Building trail & code</td><td>Human Time</td><td>9 ×</td><td>≈ 1 day</td></tr><tr><td>Finding block</td><td>GPU</td><td>8 ×</td><td>3 hours – 3 days</td></tr><tr><td>Checking results in graph</td><td>RAM</td><td>8 ×</td><td>&lt; 1/2 hour</td></tr><tr><td>Finding last block</td><td>GPU</td><td>1 ×</td><td>6 days</td></tr></tbody></table>

This means that roughly 75% of our GPU time was useful. If we convert the attack time to SHA-1 evaluations, we arrive at a total of $2^{63.6}$, which is quite close to the estimate of $2^{63.5}$ given in Table 2.

# 6 Application to PGP Web of Trust

Our demonstration of a chosen-prefix collision targets the PGP/GnuPG Web of Trust. This trust model relies on users signing each other's identity certificate, instead of using a central PKI. For compatibility reasons the legacy branch of GnuPG (version 1.4) still uses SHA-1 by default to sign identity certificates.

Therefore, we can impersonate a user using a SHA-1 chosen-prefix collision to forge the signature. More precisely, our goal is to create two PGP keys with different UserIDs, so that key B is a legitimate key for Bob (to be signed by the Web of Trust), but the signature can be transferred to key A which is a forged key with Alice's ID. This will succeed if the hash values of the identity certificates collide, as in previous attacks against X.509 MD5-based certificates [25, 27]. Moreover, due to details of the PGP/GnuPG certificate structure, our attack can reuse a single collision to target arbitrary users Alice and Bob: for each victim, the attacker only needs to create a new key embedding the collision, and to collect a SHA-1 signature. This is arguably the first practical attack against a real world security application using weaknesses of SHA-1.

We recall that a chosen-prefix collision attack works as follows: given two arbitrary prefixes $P$ and $P'$, an attacker can generate two messages $M$ and $M'$ such that $H(P \parallel M) = H(P' \parallel M')$. Note that in classical iterated hash functions such as SHA-1, given an arbitrary suffix $X$, we still have $H(P \parallel M \parallel X) = H(P' \parallel M' \parallel X)$.

## 6.1 Exploiting a Chosen-prefix Collision

We now focus on the identity certificates that will be hashed and signed. Following RFC 4880 [5], the hash computation done during certificate signing receives the public key packet, then a UserID or user attribute packet, and finally a signature packet and a trailer. The idea of the attack is to build two public keys of different sizes, so that the remaining fields to be signed are misaligned, and we can hide the UserID of key A in another field of key B. Following RFC 4880, the signature packet is protected by a length value at the beginning *and at the end*, so that we have to use the same signature packet in key A and key B (we cannot stuff data in the hashed subpacket). Therefore, we can only play with the UserID and/or user attribute packets. Still, a user attribute packet with a JPEG image gives us enough freedom to build colliding certificates, because typical JPEG readers
ignore any bytes after the End of Image marker (ff d9). This gives us some freedom to stuff arbitrary data in the certificate.

More precisely, we build keys A and B as follows. Key A contains an 8192-bit RSA public key, and a UserID field corresponding to Alice. On the other hand, key B contains a 6144-bit RSA public key, the UserID of Bob and a JPEG image. Therefore, when Bob gets a certification signature of his key, the signer will sign two certificates: one containing his public key and UserID, and another one containing the public key and the image. The public keys A and B and the image are crafted in such a way to generate a collision between the certificates with the key A and Alice's UserID, and the certificate with key B and the image.

### 6.1.1 Content of Identity Certificates

Figure 8 shows a template of the values included in the identity certificate: those values are hashed when signing a key, and we want the two hashes to collide. In this example, the UserID field of key A contains "Alice <alice@example.com>", and the image in key B is a valid JPEG image that will be padded with junk data after the End of Image marker. The real JPEG file is 181 bytes long<fnref n="6" /> (from ff d8 to ff d9), and it is padded with 81 bytes, so that the file included in the key is 262 bytes long (here the padding includes 46 bytes corresponding to the end of the modulus of key A, 5 bytes corresponding to the exponent of key A, and 30 bytes corresponding to Alice's UserID).

In Figure 8, we use the following symbols:

01 Bytes with a fixed value are fixed by the specifications, or chosen in advance by the attacker (length of fields, UserID, user attribute, ...)

?? Represent bytes that are determined by the chosen-prefix collision algorithm (the messages *M* and *M*′ to generate a collision)

!! Represent bytes that are selected after finding the collision, to generate an RSA modulus with known prime factors

.. Represent bytes that are copied from the other certificate

** Represent time-stamps chosen by the attacker

$$ Represent the time-stamp chosen by the signer

Underlined values correspond to packet headers (type and length).

### 6.1.2 Attack Procedure

To carry out the attack, we have to perform the following steps:

1. Build a chosen-prefix collision with prefixes "99 04 0d 04 ** ** ** ** 01 20 00" and "99 03 0d 04 ** ** ** ** 01 18 00", after filling the ** with two arbitrary time-stamps. The chosen-prefix collision must have at most 10 near-collision blocks. This determines the ?? bytes of the keys.

2. Choose a tiny JPEG image to include in key B (fixed orange bytes), and an arbitrary UserID to include in key A (fixed yellow bytes)

3. Select "!!" bytes in B to obtain a modulus with known factors

4. Select "!!" bytes in A to obtain a modulus with known factors

5. Generate key B with the modulus and the padded JPEG. Ask for a signature of the key.

6. Copy the signature to key A.

We point out that the chosen-prefix collision is computed *before* choosing the UserIDs and images that will be used in the attack. Therefore, a single CPC can be reused to

<footnote n="6">⁶Building a JPEG image smaller than 256 bytes is not easy, but it is possible</footnote>
<figure><img src="image_97.png" /><figcaption>**Figure 8:** Construction of colliding OpenPGP identity certificates. The colour corresponds to the packets hashed when computing the signature: first, the **public key packet** (with header), then the **UserID** or **user attribute**, and finally the **signature packet and trailer**. Arrows show when a value is chosen in one key and copied to the other.</figcaption></figure>
attack many different victims. This contrasts with attacks on X.509 certificates [25, 27],
where the identifier is hashed before the public key.

In order to build the modulus (steps 3 and 4 above), we use the same strategy as in
previous works [25, 27]. More precisely, the high order bits are fixed by previous steps,
and the low-order bits can be chosen freely. Therefore we have to find a modulus in an
interval [A, B] with a known factorisation. We select a random prime P (in the order of
B − A), and we compute Q = ⌊ B/P ⌋. If Q is a prime, we use P * Q as the modulus: we
have A ≤ P * Q ≤ B when P ≤ B − A + 1. This takes a few minutes in practice.

We note that the factors of the modulus are unbalanced. With the template of Figure 8,
we expect factors of 88 bits and 6056 bits for Key B, and 368 bits and 7824 bits for key A.
In practice we managed to find a CP collision with fewer blocks than in Figure 8, so that
key B actually has factors of 1112 bits and 5032 bits. This makes both keys hard to factor.
As mentioned in [14], it is possible to find modulus with somewhat larger factors using
more advanced techniques.

6.1.3 Example Keys

We show an example of a pair of keys generated with this procedure in Figures 11 and 12
from the Appendix. The keys can be examined with pgpdump -i to see that they include
the same signature. The files can be directly downloaded from these URLs:

Key A: https://SHA-mbles.github.io/alice.asc

Key B: https://SHA-mbles.github.io/bob.asc

In our demonstration, we chose a time-stamp far in the future to avoid malicious usage
of our collision. However, an attacker that can repeat our work will obviously use a valid
time-stamp.

6.1.4 Attack Variant

We also found an alternative attack, exploiting the PGP key format in a slightly different
way, where key B contains a short public key followed by a JPEG image. We would
consider both the public key and the image as the prefix, and stuff the CPC blocks inside
the image (after the EOI marker). This variant leaves a smaller space for the CPC blocks,
but the advantage is that key A is less suspicious because it doesn't need to contain a
valid JPEG file inside the modulus (the modulus is really made of random-looking blocks).
On the other hand, this variant requires to compute a new CPC for each key B.

Other variants might also be possible.

6.2 Impact

As explained in Section 7.1, the “classic” branch of GnuPG (v1.4) uses SHA-1 by default for
identity certifications, and there is still a non-negligible number of keys signed with SHA-1.
Before our attack was disclosed, SHA-1 signatures were also accepted by the “modern”
branch of GnuPG (v2.2). This made the attack usable in practice.

In addition, a single CPC can be reused to attack many different victims, so that the
cost of the CPC is just a one-off cost. Given our cost estimation around US$50k, this is
well within reach of strong adversaries.

7 SHA-1 Usage and Disclosure

SHA-1 is still used in a surprising number of security applications. It is supported in many
secure channel protocols (TLS, SSH), and remains actually used for some fraction of the
connections. It is also used for PGP identity certifications, and it is the foundation of GIT versioning system. We expect there are also an important number of proprietary systems using **SHA-1**, but getting actual data on this is difficult.

Collisions and chosen-prefix collisions do not threaten all those usages (in particular **HMAC-SHA-1** seems relatively safe), but there are several settings that are directly affected by chosen-prefix collisions:

* PGP identities can be impersonated if trusted third parties sign identity certificates with **SHA-1** (see 7.1)

* X.509 certificates could be broken if some CAs issue **SHA-1** certificates with predictable serial numbers (see 7.2)

* TLS and SSH connections using **SHA-1** signatures to authenticate the handshake could be attacked with the SLOTH attack [1] if the CP collision can be generated extremely quickly (see 7.3 and 7.4)

We stress that when a protocol supports several hash functions, those attacks are possible as long as **SHA-1** is *supported* by implementations, even if it is not selected during normal use. A man-in-the-middle attacker will just force the parties to use **SHA-1**.

More generally, as cryptographers, we recommend to deprecate **SHA-1** everywhere, even when there is no direct evidence that this weaknesses can be exploited. **SHA-1** has been broken regarding collision resistance for 15 years, and there are better alternatives available, well-studied, and standardized (**SHA-2** [17], **SHA-3** [18]). There is no good reason to use **SHA-1** in modern security software. Attacks only get better over time, and the goal of the cryptanalysis effort is to warn users so that they can deprecate algorithms *before* the attacks get practical.

As a stopgap measure, the collision-detection library of Stevens and Shumow [26] can be used to detect attack attempts (it successfully detects our attack).

**Responsible disclosure.** We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. We detail below the main affected products, some of the responses we received, and countermeasures deployed at the time of writing. More up to date information will be available on the website of the attack: https://sha-mbles.github.io.

## 7.1 SHA-1 Usage in GnuPG

There are currently two supported branches of GnuPG: GnuPGv1 is the “legacy” (or “classic”) branch, and GnuPGv2 is the “modern” branch. The first version of GnuPGv2 dates back to 2006, and the “legacy” branch is no longer recommended, but the transition took a long time. In particular, GnuPGv1 was still the default version in Fedora 29 (released in October 2018), and in Ubuntu 16.04 LTS (which is supported until April 2021).

GnuPG supports many different algorithms, including **SHA-1**. Moreover, **SHA-1** is the default algorithm for identity certification in GnuPGv1. This is why we targeted PGP in our demonstration of chosen-prefix collisions. After we disclosed our results to the GnuPG team, **SHA-1** signatures have been deprecated in the GnuPGv2 branch.

We have first discussed this attack with the GnuPG developers the 9th of May 2019 and eventually informed them of the newly found chosen-prefix collision the 1st of October 2019. The issue is tracked with CVE number CVE-2019-14855. A countermeasure has been implemented in commit `edc36f5`, included in GnuPG version 2.2.18 (released on the 25th of November 2019): **SHA-1**-based identity signatures created after 2019-01-19 are now considered invalid.
**Web of Trust.** The original trust model of PGP was the Web of Trust. Instead of using a central PKI, users sign each other's keys to attest of their identity (e.g. when attending a key signing party), and trust such certificates from third parties. A scan of the PGP Web of Trust (i.e. identity certifications on public key servers) shows that roughly 1% of the identity certifications issued in 2019 use SHA-1. This probably corresponds to usage of GnuPGv1 with the default settings, and would make our attack feasible.

However the Web of Trust does not seem to be widely used anymore. In particular, after the poisoning attack at the end of June 2019 [?], GnuPG 2.2.17 and later do not import identity certificates from public key servers by default. A major usage of GnuPG is now to authenticate software packages in Linux, but this typically relies on directly trusting the relevant keys without third parties.

**CAcert.** CAcert (http://cacert.org/) is one of the main CAs for PGP keys, and they still use SHA-1 to sign user keys. We have first contacted them by email on December 14th, and got an answer on January 6th acknowledging this issue. They are now planning a switch to a secure hash function for key certification.

We note that our attack is not directly applicable because CAcert does not sign JPEG images in PGP keys, but using SHA-1 signature is nonetheless an important security risk.

## 7.2 SHA-1 Usage in X.509 Certificates

The CA/Browser Forum decided to sunset SHA-1 in October 2014, and its members are not supposed to issue SHA-1 certificates after 2016. Web browsers have enforced similar rules, and all modern browsers now reject SHA-1 certificates.

However, SHA-1 certificates are still present for legacy purposes, on services that are used by older clients that can not be upgraded. In particular, it remains possible to buy a SHA-1 certificate today, and there are a few recently-issued certificates in use on the web<fnref n="7" />. There are also a few old SHA-1 certificates still in use⁸. Those certificates are rejected by modern web browsers, but they can be accepted by non-web TLS clients. For instance, it seems that the Mail application in Windows 10 can open an IMAP session secured with a SHA-1 certificate without warning. Similarly, OpenSSL still accepts SHA-1 certificates at security level 1 (the default level in most distributions – but Debian Buster has set the default level to 2, which prevents usage of SHA-1 certificates).

Chosen-prefix collisions against MD5 have been able to break the security of certificates in the past, with the creation of a Rogue CA by Stevens et al. [27], and in the wild by the flame malware [21]. If some of the CAs still issuing SHA-1 certificates use predictable serial numbers, a similar attack might be possible today (being located at the beginning of the “to-be-signed” part of the certificate, if the serial number is unpredictable then the CP collision attack is thwarted as a crucial part of the hashed input is not controlled by the attacker).

## 7.3 SHA-1 Usage in TLS

Besides certificates, there are two places where SHA-1 can be used in the TLS protocol: SHA-1 can be used to sign the handshake, and HMAC-SHA-1 can be used to authenticate data in the record protocol.

<footnote n="7">⁷Some examples can be found by searching through certificate transparency logs: http://web.archive.org/web/20191227165750/https://censys.io/certificates?q=tags%3Atrusted+AND+parsed signature_algorithm.name%3ASHA1%2A+AND+parsed validity.start%3A%5B2019-01-01+TO+%2A%5D

⁸As seen in this scan: http://web.archive.org/web/20191227165038/https://censys.io/ipv4? q=443.https.tls validation browser_trusted%3AYes+AND+443.https.tls certificate.parsed signature_algorithm.name%3ASHA1%2A</footnote>
**Handshake.** In order to authenticate the TLS handshake, the client and the server sign a copy of the transcript at the end of the handshake. If the hash function used in the signature is weak, an attacker can use chosen-prefix collisions to mount a man-in-the-middle attack and break various properties of the handshake, as shown by the SLOTH attacks [1]. However, this remains far from being a practical attack, because the CP collision has to be computed in a very short time frame, while the session is being established (timeout value is generally set to a few seconds, but can be up to several minutes).

In TLS 1.0 and 1.1, the handshake is hashed with the concatenation of SHA-1 and MD5. Using the multicollision attack from Joux [9], computing a CP collision for MD5 || SHA-1 is not much harder than for SHA-1. We give concrete figures in Table 2, showing that this is probably within reach of a well motivated adversary.

In TLS version 1.2, the hash function used is configurable, and is negotiated between the client and the server. MD5 was one of the possible options, but support has been removed after the SLOTH attack. However, SHA-1 is still widely supported, and many servers actually prefer to use SHA-1, even when the client offers better algorithms. Scan results of the top 1M websites show that 3% of them use SHA-1⁹, and this includes many high profile websites.<fnref n="10" /> The vast majority of TLS 1.0/1.1 clients offer SHA-1 as an option for the signature.

In TLS version 1.3, MD5 and SHA-1 have been removed.

**Ciphersuites.** The ciphersuite used in a TLS connection is the result of a negotiation between the client and server, so it is hard to predict exactly. However, the large majority of clients and servers support ciphersuites where HMAC-SHA-1 is used to authenticate the packets, at least for interoperability reasons. It seems that usage of HMAC-SHA-1 represents a few percent of all the connections. Telemetry results from Mozilla report about 2% of connections with a HMAC-SHA-1 ciphersuite.<fnref n="11" /> In addition, a scan of websites in the Alexa top 1M show that 8% of them would use a HMAC-SHA-1 ciphersuite with the client settings used for the scan<fnref n="12" />.

This usage is not threatened by our attack, but we recommend to avoid SHA-1 usage when possible.

**OpenSSL.** We have first contacted the OpenSSL developers on December 14th. The next version of OpenSSL will no longer allow X.509 certificates signed using SHA-1 at security level 1 and above (commit 68436f0). Since security level 1 is the default configuration for TLS/SSL, this will prevent SHA-1 usage for certificates.

Debian Linux had previously set the default configuration to security level 2 (defined as 112-bit security) in the latest release (Debian Buster); this already prevents dangerous usage of SHA-1 (for certificates and handshake signature).

## 7.4 SHA-1 Usage in SSH

SHA-1's usage in SSH is similar to its usage in TLS. The SSH-2 protocol supports usage of SHA-1 to sign the transcript (at the end of the key exchange), and HMAC-SHA-1 to authenticate the data in the record protocol. As in the TLS case, usage of SHA-1 to sign the transcript has been shown to be potentially vulnerable to the SLOTH attack [1], but

<footnote n="9">⁹http://web.archive.org/web/20191227174651/https://censys.io/domain/report?field=443. https.tls signature.hash_algorithm</footnote>

<footnote n="10">¹⁰http://web.archive.org/web/20191227174551/https://censys.io/domain?q=443.https.tls. signature.hash_algorithm%3Asha1</footnote>

<footnote n="11">¹¹See https://telemetry.mozilla.org/new-pipeline/dist.html#!measure=SSL_CIPHER_SUITE_FULL, were buckets 5, 61 and 63 correspond to HMAC-SHA-1 ciphersuites</footnote>

<footnote n="12">¹²http://web.archive.org/web/20191226134753/https://censys.io/domain/report?field=443. https.tls.cipher Suite.name.raw</footnote>
this is not practical given the timing constraints (usually just a few seconds, but can be
configured to a longer period of time).

Again, the choice of cryptographic algorithms depends on a negotiation between the
client and server, so it is hard to know exactly what will be selected. However, scans of
the IPv4 space from censys at the time of writing show that roughly 17% of servers use
SHA-1 to sign the transcript<fnref n="13" />, and 9% of servers use HMAC-SHA-1 in the record protocol<fnref n="14" />.
This mostly corresponds to servers running old versions of SSH daemons.

**OpenSSH.** Due to our results, since version 8.2 of OpenSSH a “future deprecation notice” is included, explaining that SHA-1 signatures will be disabled in the near-future.

## 7.5 Other Usages of SHA-1

**DNSSEC.** SHA-1 is still used in DNSSEC, with 18% of the top-level domains using SHA-1 at the time of writing<fnref n="15" />. Since DNSSEC signatures include user-supplied content, CP collisions could be used to attack the DNSSEC system.

**GIT.** GIT relies heavily on SHA-1 to identify all objects in a repository. It does not necessarily require cryptographic security from SHA-1, but there are certainly some attack scenarios where attacks on SHA-1 would matter. In particular, signed GIT commits are essentially signatures of a SHA-1 hash, so they would be sensitive to collision attacks.

The GIT developers have been working on replacing SHA-1 for a while<fnref n="16" />, and they use
a collision detection library [26] to mitigate the risks of collision attacks.

**Timestamping.** Many timestamping servers apparently support SHA-1, such as: https://sectigo.com/resources/time-stamping-server

# 8 Conclusion and Future Works

This work shows once and for all that SHA-1 should not be used in any security protocol where some kind of collision resistance is to be expected from the hash function. Continued usage of SHA-1 for certificates or for authentication of handshake messages in TLS or SSH is dangerous, and there is a concrete risk of abuse by a well-motivated adversary. SHA-1 has been broken regarding collision resistance since 2004, but it is still used in many security systems. We strongly advise users to remove SHA-1 support to avoid downgrade attacks. We exhibited a practical chosen-prefix collision attack on SHA-1, and performed an actual CP collision computation for a reasonable cost. This cost will decrease over time and in a close future will be so cheap that any ill-intentioned person could afford it.

Our work directly impacts the security of PGP/GnuPG Web of Trust: using our CP collision attack on SHA-1, we have created two PGP keys with different UserIDs and colliding certificates. This allows an attacker to impersonate any user, as long as trusted third parties sign identity certifications with SHA-1.

We also show that gaming or mining GPUs offer a cheap and efficient way to attack symmetric cryptography primitives. In particular, it now costs less than US$ 100k to rent GPUs and break cryptography with a security level of 64 bits (i.e. to compute $2^{64}$ operations of symmetric cryptography).

<footnote n="13">¹³http://web.archive.org/web/20191226130952/https://censys.io/ipv4/report?field=22.ssh.
v2selected.kex_algorithm</footnote>

<footnote n="14">¹⁴http://web.archive.org/web/20191226131928/https://censys.io/ipv4/report?field=22.ssh.
v2selected.client_to_server.mac</footnote>

<footnote n="15">¹⁵https://www.dns.cam.ac.uk/news/2020-02-14-sha-mbles.html</footnote>

<footnote n="16">¹⁶https://git-scm.com/docs/hash-function-transition/</footnote>
**Future works.** The cost of our attack is roughly four times the cost of a plain collision attack, so there is limited room for improvements in terms of complexity. The factor 4 could be slightly reduced by changing the parameters of the graph, but this is unlikely to result in an improvement of more than a factor 2. Alternatively, improvements to the near-collision search could improve simultaneously identical-prefix and chosen-prefix collision attacks.

On the other hand, we believe there is some possibility to reduce the number of blocks used in the attack without increasing the complexity much. Firstly, with a better use of the global parameters of the general chosen-prefix collision attack. By playing with the number of blocks, the allowable probabilities and the size of the graph, one could probably find a better configuration. Secondly, by not considering only the core differential trail from [23], but using other interesting ones(for example the ones already used in other previous SHA-1 attacks), we would increase the pool of available differences and in turn reduce the required number of blocks.

A natural future work would be to study other applications of practical chosen-prefix collisions on SHA-1. Different protocols would lead to different constraints for the attacker, and unfortunately SHA-1 remains used on field. What would then be the security impact of our findings on these applications ? What applications could be targeted ?

Finally, it remains to be studied how recent chosen-prefix collision attacks could potentially apply to other hash functions, such as RIPEMD, (reduced-round) SHA-2, or even others.

We are planning to publish code to make our claims easy to verify, but due to the strong impact of this attack, we will wait until counter-measures are more widely implemented.

## Acknowledgements

The authors are grateful to the USENIX Security 2020 reviewers and shepherd for their insightful comments that improved the quality of the paper.

The authors would like to thank Vesselin Velichkov for his help with regards to an initial analysis of neutral bits applicability on SHA-1 and Werner Koch for his comments on the applicability of our attacks on PGP. The authors would also like to thank gpuserversrental.com for their efficient service regarding the GPU cluster renting. The second author is supported by Temasek Laboratories, Singapore.

A small part of the experiments presented in this paper were carried out using the Grid'5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr). Development and small scale experiments before launching the main computation were carried out on the rioc cluster from Inria.

## References

[1] Karthikeyan Bhargavan and Gaëtan Leurent. Transcript collision attacks: Breaking authentication in TLS, IKE and SSH. In *NDSS 2016*. The Internet Society, February 2016.

[2] Eli Biham and Rafi Chen. Near-collisions of SHA-0. In *Franklin* [8], pages 290–305.

[3] Eli Biham, Rafi Chen, Antoine Joux, Patrick Carribault, Christophe Lemuet, and William Jalby. Collisions of SHA-0 and reduced SHA-1. In Ronald Cramer, editor, *EUROCRYPT 2005*, volume 3494 of LNCS, pages 36–57. Springer, Heidelberg, May 2005.
[4] Gilles Brassard, editor. *CRYPTO*, volume 435 of *Lecture Notes in Computer Science*. Springer, 1990.

[5] J. Callas, L. Donnerhacke, H. Finney, D. Shaw, and R. Thayer. *RFC 4880 - OpenPGP Message Format*. Internet Activities Board, November 2007.

[6] Ivan Damgård. A Design Principle for Hash Functions. In Brassard [4], pages 416–427.

[7] Christophe De Cannière and Christian Rechberger. Finding SHA-1 characteristics: General results and applications. In Xuejia Lai and Kefei Chen, editors, *ASI-ACRYPT 2006*, volume 4284 of LNCS, pages 1–20. Springer, Heidelberg, December 2006.

[8] Matthew Franklin, editor. *CRYPTO 2004*, volume 3152 of LNCS. Springer, Heidelberg, August 2004.

[9] Antoine Joux. Multicollisions in iterated hash functions. Application to cascaded constructions. In Franklin [8], pages 306–316.

[10] Antoine Joux and Thomas Peyrin. Hash functions and the (amplified) boomerang attack. In Alfred Menezes, editor, *CRYPTO 2007*, volume 4622 of LNCS, pages 244–263. Springer, Heidelberg, August 2007.

[11] Vlastimil Klima. Tunnels in hash functions: MD5 collisions within a minute. Cryptology ePrint Archive, Report 2006/105, 2006. http://eprint.iacr.org/2006/105.

[12] Gaëtan Leurent and Thomas Peyrin. From collisions to chosen-prefix collisions application to full SHA-1. In Yuval Ishai and Vincent Rijmen, editors, *EUROCRYPT 2019, Part III*, volume 11478 of LNCS, pages 527–555. Springer, Heidelberg, May 2019.

[13] Gaëtan Leurent and Thomas Peyrin. SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. Cryptology ePrint Archive, Report 2020/014, 2020. https://eprint.iacr.org/2020/014.

[14] Marc Stevens. Attacks on Hash Functions and Applications. PHD Thesis, Leiden University, June 2012.

[15] Ralph C. Merkle. One Way Hash Functions and DES. In Brassard [4], pages 428–446.

[16] National Institute of Standards and Technology. FIPS 180-1: Secure Hash Standard, April 1995.

[17] National Institute of Standards and Technology. FIPS 180-2: Secure Hash Standard, August 2002.

[18] National Institute of Standards and Technology. FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, August 2015.

[19] Ronald L. Rivest. The MD4 message digest algorithm. In Alfred J. Menezes and Scott A. Vanstone, editors, *CRYPTO'90*, volume 537 of LNCS, pages 303–311. Springer, Heidelberg, August 1991.

[20] Ronald L. Rivest. *RFC 1321: The MD5 Message-Digest Algorithm*. Internet Activities Board, April 1992.

[21] Marc Stevens. Counter-cryptanalysis. In Ran Canetti and Juan A. Garay, editors, *CRYPTO 2013, Part I*, volume 8042 of LNCS, pages 129–146. Springer, Heidelberg, August 2013.
[22] Marc Stevens. New collision attacks on SHA-1 based on optimal joint local-collision analysis. In Thomas Johansson and Phong Q. Nguyen, editors, *EUROCRYPT 2013*, volume 7881 of LNCS, pages 245-261. Springer, Heidelberg, May 2013.

[23] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov. The first collision for full SHA-1. In Jonathan Katz and Hovav Shacham, editors, *CRYPTO 2017, Part I*, volume 10401 of LNCS, pages 570-596. Springer, Heidelberg, August 2017.

[24] Marc Stevens, Pierre Karpman, and Thomas Peyrin. Freestart collision for full SHA-1. In Marc Fischlin and Jean-Sébastien Coron, editors, *EUROCRYPT 2016, Part I*, volume 9665 of LNCS, pages 459-483. Springer, Heidelberg, May 2016.

[25] Marc Stevens, Arjen K. Lenstra, and Benne de Weger. Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In Moni Naor, editor, *EUROCRYPT 2007*, volume 4515 of LNCS, pages 1-22. Springer, Heidelberg, May 2007.

[26] Marc Stevens and Daniel Shumow. Speeding up detection of SHA-1 collision attacks using unavoidable attack conditions. In Engin Kirda and Thomas Ristenpart, editors, *USENIX Security 2017*, pages 881-897. USENIX Association, August 2017.

[27] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K. Lenstra, David Molnar, Dag Arne Osvik, and Benne de Weger. Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. In Shai Halevi, editor, *CRYPTO 2009*, volume 5677 of LNCS, pages 55-69. Springer, Heidelberg, August 2009.

[28] Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. *Journal of Cryptology*, 12(1):1-28, January 1999.

[29] Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu. Finding collisions in the full SHA-1. In Victor Shoup, editor, *CRYPTO 2005*, volume 3621 of LNCS, pages 17-36. Springer, Heidelberg, August 2005.
# A Improving SHA-1 Collision Attack

We now give the technical details of the improvements introduced in Section 3, for readers that are familiar with previous works [22, 23, 12].

## A.1 Boomerangs and Neutral Bits

As explained in [12], an important factor to evaluate the cost of the attack is the number of boomerangs available when looking for a conforming message. The collision attack from Eurocrypt 2013 [22] and its GPU implementation from Crypto 2017 [23] (the “Shattered” attack) use three boomerangs, on bits 6 and 8 of $M_6$ (red type in Figure 9), and on bit 7 of $M_9$ (blue type in Figure 9). However, the boomerang on $M_6$ [8] actually flips the value of $W_{77}$[0] due to the message expansion, and breaks the condition $W_{77}$[0] $\oplus$ $W_{77}$[2] = 1$ listed on Table 5 of [23]. This reduces the probability of the trail on rounds 61–80 by a factor $3/4$, from $2^{-19.17}$ to $2^{-19.58}$. However, the boomerang almost doubles the number of partial solution produced, so that using it still improves the attack.

In addition, we realized that the “Shattered” attack [23] uses a neutral bit on $M_{13}$[11]. However, this breaks the condition $W_{76}$[0] $\oplus$ $W_{76}$[1] = 1, and reduces the probability of the trail by a factor roughly $2^{0.2}$. In our analysis, we assume that this neutral bit has been removed: since it has a very small effect on the number of partial solution produced, it reduces the complexity of the attack by a factor $2^{0.2}$. In particular, this is why we consider that a collision requires $2^{48.5} A_{33}$-solutions rather than $2^{48.7}$ (where an $A_i$-solution refers to an input pair that is following the differential path until word $A_i$ inclusive).

In our chosen-prefix attack, we also need conditions on $W_{77}$[0], and we decided to remove the boomerang on $M_6$[8] in order to keep more control on the output difference and to simplify the attack. In particular, removing this boomerang makes easier the construction of trails with the extra constraints (and we have successfully built trails with the two remaining boomerangs for all successive blocks). This implies that the cost of near-collision blocks increases by a factor $3/2$ compared to the “Shattered” attack, leading to $C_{\text{block}} = 2^{64.9}$ on a GTX 970 (after gaining a factor $2^{0.2}$ by removing $M_{13}$[11] as a neutral bit). Therefore we can estimate more accurately the complexity of the previous attack [12] as $2^{67.1}$ SHA-1 computations, instead of the range of $2^{66.9}$ to $2^{69.4}$ reported previously (the optimal attack parameter choice for [12] is then a maximum cost of 3.5 $C_{\text{block}}$).

As an optimization, we decided to use the boomerang on $M_6$[8] for the last block, because the computation of the last block is identical to the second block of an identical-prefix collision attack. In particular, we had no trouble building a path with this boomerang, and this results in a speed-up of a factor 1.9 in the rate of $A_{33}$-solutions. We need to increase the number of solutions by a factor $4/3$ because the solutions are of lower quality, but this still corresponds to a speed-up factor of roughly 1.4. Since the last block represents a significant part of the total computation, this is a worthwhile optimization.

## A.2 Additional Boomerangs and Modular Correction

We found out that in addition to previously mentioned boomerangs, we can use very short boomerangs on bits 4, 5, and 6 of $M_{11}$ (green type in Figure 9), with a single correction on $M_{12}$. These boomerangs are neutral until step 22, like the boomerang on $M_9$. The problem is that they will clash with existing small boomerangs starting at $M_6$[6], $M_6$[8] and $M_9$[7].

More precisely, the boomerang starting at $M_{11}$[4] will flip the message condition “$\bar{x}$” from the boomerang starting at $M_6$[6], corresponding to the last message correction of the local collision. In order to avoid this issue, we simply change the last correction of the $M_6$[6] boomerang to be a modular addition correction instead of an XOR correction. This
<table><thead><tr><th>i</th><th>A<sub>i</sub></th><th>W<sub>i</sub></th></tr></thead><tbody><tr><td>-1:</td><td></td><td></td></tr><tr><td>00:</td><td></td><td></td></tr><tr><td>01:</td><td></td><td></td></tr><tr><td>02:</td><td></td><td></td></tr><tr><td>03:</td><td></td><td></td></tr><tr><td>04:</td><td></td><td></td></tr><tr><td>05:</td><td></td><td></td></tr><tr><td>06:</td><td></td><td></td></tr><tr><td>07:</td><td></td><td></td></tr><tr><td>08:</td><td></td><td></td></tr><tr><td>09:</td><td></td><td></td></tr><tr><td>10:</td><td></td><td></td></tr><tr><td>11:</td><td></td><td></td></tr><tr><td>12:</td><td></td><td></td></tr><tr><td>13:</td><td></td><td></td></tr><tr><td>14:</td><td></td><td></td></tr><tr><td>15:</td><td></td><td></td></tr></tbody></table>

**Figure 9:** Boomerangs' differential paths used for SHA-1 with the corresponding constraints forced in order to have probability one in the 16 first steps. The red one (perturbation x) represents a small boomerang (named AP₁ in [?]) composed of a single local collision starting on M₆, here positioned at bit j = 2. The blue one (perturbation y) represents another small boomerang used in [22, 23], also composed of a single local collision, but starting on M₉, here positioned at bit j = 14. The green one (perturbation z) represents a new and even smaller boomerang built from a partial local collision starting on M₁₁, here positioned at bit j = 25. The MSB's are on the right and “-” stands for no constraint. The letters represent a bit value and its complement is denoted by an upper bar on the corresponding letter. The notation “|” on two bits vertically adjacent means that these two bits must be equal.

<table><thead><tr><th>i</th><th>A<sub>i</sub></th><th>W<sub>i</sub></th></tr></thead><tbody><tr><td>-1:</td><td></td><td></td></tr><tr><td>00:</td><td></td><td></td></tr><tr><td>01:</td><td></td><td></td></tr><tr><td>02:</td><td></td><td></td></tr><tr><td>03:</td><td></td><td></td></tr><tr><td>04:</td><td></td><td></td></tr><tr><td>05:</td><td></td><td></td></tr><tr><td>06:</td><td></td><td></td></tr><tr><td>07:</td><td></td><td></td></tr><tr><td>08:</td><td></td><td></td></tr><tr><td>09:</td><td></td><td></td></tr><tr><td>10:</td><td></td><td></td></tr><tr><td>11:</td><td></td><td></td></tr><tr><td>12:</td><td></td><td></td></tr><tr><td>13:</td><td></td><td></td></tr><tr><td>14:</td><td></td><td></td></tr><tr><td>15:</td><td></td><td></td></tr></tbody></table>

**Figure 10:** Exact conditions required to prepare all the boomerangs' differential paths used for our CP collision attack on SHA-1 with the corresponding constraints forced in order to have probability one in the 16 first steps. The MSB's are on the right and “-” stands for no constraint. The notation “|” on two bits vertically adjacent means that these two bits must be equal. These conditions basically correspond to very short boomerangs started at M₁₁[4], M₁₁[5] and M₁₁[6], and small boomerangs started at M₆[6], M₆[8] and M₉[7] (boomerang starting perturbations are marked in purple). We remark an extra condition M₁₃[5] = 1 in order to potentially correct the clash between boomerangs M₁₁[5] and M₉[7].
will naturally correct the perturbation as the step operation involved is indeed a modular
addition and the boomerang on $M_6[6]$ will behave as expected (the condition "$\bar{x}$" is actually
not needed anymore). This can be seen as a generalization of the boomerang strategy used
so far for SHA-1: boomerang corrections can be applied modular addition-wise instead
of XOR-wise. This will induce changes in subsequent bits in the corresponding message
words because of carry propagations that might naturally occur with a modular addition
operation, but as long as these bit changes do not mess with existing message conditions,
we are fine$^{17}$. This idea might also be interesting to analyse other hash functions.

Similarly, the boomerang starting at $M_{11}[6]$ will flip the message condition “$\bar{x}$” from the boomerang starting at $M_6[8]$, corresponding to the last message correction of the local collision. This is exactly the same situation and we avoid this issue by changing the last correction of the $M_6[8]$ boomerang to be a modular addition correction instead of an XOR correction.

Finally, the boomerang starting at $M_{11}[5]$ will flip the condition “1” in the internal state,
required for the boomerang starting at $M_9[7]$. This will create an uncontrolled difference
when we use the $M_9[7]$ boomerang, that we correct by introducing a new difference in
$M_{13}[5]$ (setting the extra condition $M_{13}[5] = M_9[7] \oplus 1$ will ensure a proper correction
using XOR correction). Note that we perform this further correction only in the case
where the boomerang starting at $M_{11}[5]$ was triggered. We observe furthermore that the
correction on $M_{13}[5]$ will maintain a good quality of neutrality for $M_{11}[5]$ boomerang. All
the conditions required to use the boomerangs are given in Figure 10.

<footnote n="17">¹⁷In more details, since the boomerangs on $M_{11}[4]$, $M_{11}[5]$ and $M_{11}[6]$ are very short and thus applied before boomerangs $M_6[6]$, $M_6[8]$ and $M_9[7]$, we don't actually care if the last ones break conditions of the first ones since they have already been used.</footnote>