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.

migrated from security.stackexchange.com Feb 23 '17 at 14:25

This question came from our site for information security professionals.

up vote 74 down vote accepted

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

enter image description here

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.

enter image description here

$\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:

enter image description here

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:

enter image description here

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.