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


Differential collisions in SHA-0 by Chabaud F., Joux A. have collisions in SHA-0 in $2^{61}$ calls.
Near Collision in SHA-0 by Biham E., Chen R. at CRYPTO 2004
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
Finding Collisions in the Full SHA-1 by Wang et al. at CRYPTO 2005
Practical Free-Start Collision Attacks on 76-step SHA-1 by Pierre Karpman, Thomas Peyrin and Marc Stevens at CRYPTO 2015
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: