46
$\begingroup$

In their work on SHA-1 collisions (cf. the EUROCRYPT-2016 paper “Freestart collision on full SHA-1” by Stevens, Karpman, and Peyrin) Stevens et al show that they are able to generate "freestart collisions" on SHA-1. They say:

Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections.

What is a "freestart collision" on a hash function?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
33
$\begingroup$

Definition

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.

Effect

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.freestartCollision 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/

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The last sentence is a little misleading; first, the freestart collision due to Stevens et al. uses two distinct IVs, and second, finding a message that hashes to a particular number (i.e., obtaining a preimage) is likely to remain infeasible for the foreseeable future. (E.g., obtaining a preimage on MD5 is still infeasible: crypto.stackexchange.com/questions/13303/…). Instead, research will likely progress by making it easier to find collisions without controlling the IV. $\endgroup$
    – Nikita Borisov
    Oct 23, 2015 at 21:31
  • $\begingroup$ Thanks, I'll try to rephrase it. Or you can also suggest an edit if you wish $\endgroup$
    – ddddavidee
    Oct 24, 2015 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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