In the Damgard-Merkle construction for hash functions the compression function takes as input:
- a message block and
- a chaining value.
For the very first block there is not previous "chaining value". Instead a particular value, called an initialisation vector (IV) is given.
A freestart collision is a collision where the attacker can choose the IV.
In particular in their paper (page 3, Table 2-1), authors found two, slightly, different IVs (only two bits are different):
$IV_1:$ 50 6b 01 78 ff 6d 18 90 20 22 91 fd 3a de 38 71 b2 c6 65 ea
$IV_2:$ 50 6b 01 78 ff 6d 18 91 a0 22 91 fd 3a de 38 71 b2 c6 65 ea
Their attack, as they claim in their work, is the first one to break the whole 80 rounds of the SHA-1 compression function.
Even if a freestart collision does not immediately give a standard collision, it could be used in multiblock collision search. The chaining value indeed is the compression function output of the previous block.
It is not clear
(or at least not to me) how easy the path from a freestart collision to a standard collision is.
As an example: It took 8 years for MD5. The first freestart collision for MD5 was found in 1996 (Dobbertin, Eurocrypt Rump Session) but the first standard collision on MD5 was published only in 2004.
Future work [Next step (from a freestart collision to a full collision)]
Finding out a freestart collision on an hash function does not break completely the function but shows a great weakness. With a freestart collision researchers exhibit the second half of two colliding messages. One could say that we now know how the path leading to the collision but we do not know, yet, where it starts.
Last step left to research is find out a block message $m_0$ which $SHA$-$1(m_0)$ is equal to the freestart IV.
When such message is found, the collision is served. It has to been said that finding out a message that is hashed into a given value is infeasible (it is still an hard problem for the broken MD5 hash function).
UPDATE: The full collision has been found: https://shattered.it/