11
$\begingroup$

SHA-1 security has been discussed since an algorithm for finding collisions was first published at CRYPTO 2004 and has been subsequently improved.

Wikipedia lists a couple of references, however it seems the latest research published (and later withdrawn) on this subject was in 2009 (Cameron McDonald, Philip Hawkes and Josef Pieprzyk "Differential Path for SHA-1 with complexity O(2^52)").

Since then, has any significant progress been made on reducing the effort for a hash collision attack on SHA-1?

A link to specific research accompanied with a short summary would be appreciated.

$\endgroup$
9
$\begingroup$

SHA-1 was SHattered by Stevens et al. They demonstrated that collisions in SHA-1 are practical. They give the first instance of a collision for SHA-1.

It is an identical-prefix collision attack that enabled the attacker to forge two distinct PDF documents that have the same SHA-1 hash value. I.e. They extended a given prefix $p$ with two distinct near-collision block pairs for any suffix $s$ that collides.

$$\operatorname{SHA-1}(p \mathbin\Vert m_0 \mathbin\Vert m_1 \mathbin\Vert s) = \operatorname{SHA-1}(p \mathbin\Vert m'_0 \mathbin\Vert m'_1 \mathbin\Vert s)$$ for any suffix $s$, where $(m_0, m_1) \neq (m'_0, m'_1)$

The computational requirement is estimated to $2^{63.1}$

The first first-block near collision was found after spending about 3583 core years that had produced 180 711 partial solutions up to step 61. A second near collision block was then later computed; it required an additional 2987 core years and 148 975 partial solutions.1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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