Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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 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}$.
SHA-1 (and the broken SHA-0) have been under the following attacks over the past few years:
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.
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.
