[Cfrg] Notice on chosen-prefix collisions for SHA-1

[Thomas Peyrin <[e-mail]>]

Dear CFRG members,

We, Gaetan Leurent and myself, would like to emphasize some results we
will present in a few days at Eurocrypt 2019 [LP19]. ePrint version
available here: https://eprint.iacr.org/2019/459.pdf

[TL;DR] Chosen-prefix collisions for SHA-1 hash function are now
practical (cost lower than 100K $), all hope is lost.

As you might know, SHA-1 hash function has been broken theoretically
since 2005 [W+05] and an actual collision was computed in 2017 [S+17].
This clearly makes SHA-1 a function to avoid, but even though
deprecation efforts have been conducted since many years, SHA-1 is
still used in several security products and RFC standards (TLS 1.2,
git, ...)

Finding a collision attack breaks the hash function, but the actual
damage that can be done with such a collision is somewhat limited as
the attacker will have little to no control on the actual data that
collides. A much more interesting attack is to find a so-called
chosen-prefix collision, where the attacker can freely choose the
prefix for the two colliding messages. This was for example used to
create rogue-CA for MD5 [S+09] and in general chosen-prefix collision
attacks have a huge impact on security [BL16].

Yet, these chosen-prefix collisions are believed to be much harder to
find than classical collisions. For SHA-1, the best previous search
method required 2^77 SHA-1 evaluations [S13], which remained out of
reach in practice. In our article, we explain how to drastically
reduce the cost of finding chosen-prefix collisions for SHA-1, down to
almost the same cost as finding a classical collision. With some
additional improvements that we are currently working on, we evaluate
that one can find a chosen-prefix collision for SHA-1 with a budget of
less than 100K US$. We therefore recommend to avoid SHA-1 at all cost,
especially for use in certificates/digital signatures.

[BL16] Karthikeyan Bhargavan, Gaëtan Leurent, "Transcript Collision
Attacks: Breaking Authentication in TLS, IKE and SSH", NDSS 2016
[LP19] Gaetan Leurent Thomas Peyrin, “From Collisions to Chosen-Prefix
Collisions - Application to Full SHA-1”, Eurocrypt 2019
[S+09] Marc Stevens, Alexander Sotirov, Jacob Appelbaum, Arjen K.
Lenstra, David Molnar, Dag Arne Osvik, Benne de Weger, “Short
Chosen-Prefix Collisions for MD5 and the Creation of a Rogue CA
Certificate”, Crypto 2009
[S13] Marc Stevens, “New Collision Attacks on SHA-1 Based on Optimal
Joint Local-Collision Analysis”, Eurocrypt 2013
[S+17] Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini,
Yarik Markov, "The first collision for full SHA-1", Crypto 2017
[W+05] Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu, “Finding Collisions
in the Full SHA-1”, Crypto 2005

Regards,

Thomas.