# What is the new attack on SHA-1 “SHAttered” and how does it work?

There's a new recent Attack on SHA-1 named "SHAttered" by Google and some researchers. I understand that it uses some fancy new techniques, but not the details.

My question is: How?

How does the attack work (on a high level)? How does it compare to previous attacks?

Note: The matter of implications is already handled by this other question, so don't focus on it please.

• In the advisory they say they'll release code in 90 days. Not sure why you got downvotes, question looks legit to me. – paj28 Feb 23 '17 at 13:44
• – SEJPM Feb 23 '17 at 14:40
• @paj28 as SEJPM mentioned paper is already online. In fact, you can even craft pdfs to have collisions using alf.nu/SHA1 – BKC Feb 25 '17 at 7:21

In order to get a collision on a $n$ bit Random Oracle using the birthday paradox, one needs $\sqrt{\pi / 2} \cdot 2^{n/2}$ calls. In other words, in the case of the 160 output bits of SHA-1 the limit is in the order of $2^{160/2} = 2^{80}$.

# Previous Attacks

SHA-1 (and the broken SHA-0) have been under the following attacks over the past few years:

1. Differential collisions in SHA-0 by Chabaud F., Joux A. have collisions in SHA-0 in $2^{61}$ calls.
2. Near Collision in SHA-0 by Biham E., Chen R. at CRYPTO 2004
3. Collision of SHA-0 and Round reduced SHA-1 by Biham E., Chen R., Joux A., Carribault P., Lemuet C., Jalby W. at EUROCRYPT 2005
4. Finding Collisions in the Full SHA-1 by Wang et al. at CRYPTO 2005
5. Practical Free-Start Collision Attacks on 76-step SHA-1 by Pierre Karpman, Thomas Peyrin and Marc Stevens at CRYPTO 2015
6. New Collision Attacks on SHA-1 Based on Optimal Joint Local-Collision Analysis by Stevens M. at EUROCRYPT 2013

The 4th paper presented an attack in $2^{69}$ calls showing the weaknesses of SHA-1. The 6th paper will be the ground work of the SHAttered attack.

The main idea behind these attacks relies on Differential cryptanalysis. You have two inputs $t_0$ and $t'_0$ with a difference of $\Delta_0$. Once these two inputs have gone through the function $f$ (the compression function in the case of SHA-1) you get a difference $\Delta_1$ and so on (see following picture)...

The goal here is to find a difference in the input $\Delta_0$ such that after some iterations you get $\Delta_2 = 0$, in other words no difference.

# the SHAttered Attack

Because of the Merkle–Damgård construction of SHA-1, one can choose to alter the differences between the iterations in order to improve the differences to match his needs. In the case of the SHAttered Attack, they chose an initial prefix ($P$), then later on the next blocks they introduce a difference ($M^{(1)}_1$,$M^{(2)}_1$) and remove it ($M^{(1)}_2$ and $M^{(2)}_2$). At this point they already have their collision. They just need to continue with the same following blocks ($S$), leading to a collision on the whole input.

$\mathrm{SHA-1}(P||M^{(1)}_1\mathbin\Vert M^{(1)}_2\mathbin\Vert S)=\mathrm{SHA-1}(P||M^{(2)}_1\mathbin\Vert M^{(2)}_2\mathbin\Vert S)$

The values of $M^{(1)}_1$, $M^{(2)}_1$, $M^{(1)}_2$ and $M^{(2)}_2$ are as follows:

The difficulty is thus to find the correct $M_i$ that satisfy the chosen prefix criteria $P$ and that cancel themselves nicely afterwards. The probabilities of such to occur are really small, thus the need of massive amount of calls to SHA-1 compression function ($2^{63.1}$).

In the case of the provided PDFs, they also give a nice infographic which explain where the difference is located in the PDFs:

It is an approximately1 $2^{64}$ time identical-prefix collision attack on SHA-1 based on the same principles as Marc Stevens' earlier attacks on SHA-1. It is the first practical collision attack on the full SHA-1 function, so obviously notable and a great achievement, even though SHA-1 was known to be broken for years.

The attack itself works in two parts, generating two pairs of differing blocks that take a given message prefix to the same SHA-1 state by canceling out each other. (The difficult part was apparently efficiently implementing this on a heterogenous CPU+GPU architecture.)

As an identical-prefix collision attack it allows you to create two messages starting with the same predetermined prefix, followed by the "random" part the attack finds, and then optionally any amount of identical data. While this is less powerful than the chosen-prefix attacks known for MD5 (those allow choosing the prefixes arbitrarily) and costs quite a bit, it certainly confirms SHA-1 is broken for good.

1Exact cost depends on whether you are interested in the number of calls required, total time taken or theoretical expected time.