International Association
for Cryptologic Research

We present in this article a freestart collision example for SHA-1, i.e., a

collision for its internal compression function. This is the first practical

break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days

of computation on a 64 GPU cluster were necessary to perform the attack.

This work builds on a continuous series of cryptanalytic advancements on SHA-1

since the theoretical collision attack breakthrough in 2005.

In particular, we extend the recent freestart collision work on reduced-round

SHA-1 from CRYPTO 2015 that leverages the computational power of graphic cards

and adapt it to allow the use of boomerang speed-up techniques.

We also leverage the cryptanalytic techniques by Stevens from EUROCRYPT 2013

to obtain optimal attack conditions,

which required further refinements for this work.

Freestart collisions, like the one presented here, do not directly imply a

collision for SHA-1.

However, this work is an important milestone towards an actual SHA-1 collision

and it further shows how graphics cards can be used very efficiently for these

kind of attacks.

Based on the state-of-the-art collision attack on SHA-1 by Stevens from

EUROCRYPT 2013, we are able to present new projections on the

computational/financial cost required by a SHA-1 collision computation.

These projections are significantly lower than previously anticipated by the

industry, due to the use of the more cost efficient graphics cards compared to

regular CPUs.

We therefore recommend the industry, in particular Internet browser vendors

and Certification Authorities, to retract SHA-1 soon.

We hope the industry has learned from the events surrounding the cryptanalytic

breaks of MD5 and will retract SHA-1 before example signature forgeries appear

in the near future.

With our new cost projections in mind, we strongly and urgently recommend

against a recent proposal to extend the issuance of SHA-1 certificates with a

year in the CAB/forum (vote closes October 9 2015).