[Cryptography] Collisions w/SHA-1 ~$100,000 TODAY

[Philipp Jovanovic]

> I guess the next question would be, how long we expect the freestart limitation to last as a meaningful barrier to full SHA1 collision attacks.

To provide some perspective:

- 1996: Dobbertin publishes the first free-start collisions on MD5 [1] 
- 2004: Wang et. all present the first true collision on MD5 [2]

Note that in the case of MD5, nobody knew how to construct collisions back in the day. For SHA1, however, we already know how to do it, see Marc Stevens PhD thesis [3], with an estimated complexity between 2^{60.3} and 2^{65.3} operations (see also [4]). 

As usual with such things, it is hard to reliably predict how much the recently published SHA1 free-start collision helps to construct an actual SHA1 collision. I would expect though that it won’t take another 8 years as in the case of MD5.

All the best,
Philipp

[1] http://cseweb.ucsd.edu/~bsy/dobbertin.ps <http://cseweb.ucsd.edu/~bsy/dobbertin.ps>
[2] https://eprint.iacr.org/2004/199 <https://eprint.iacr.org/2004/199>
[3] https://marc-stevens.nl/research/papers/PhD%20Thesis%20Marc%20Stevens%20-%20Attacks%20on%20Hash%20Functions%20and%20Applications.pdf <https://marc-stevens.nl/research/papers/PhD%20Thesis%20Marc%20Stevens%20-%20Attacks%20on%20Hash%20Functions%20and%20Applications.pdf>
[4] https://en.wikipedia.org/wiki/SHA-1 <https://en.wikipedia.org/wiki/SHA-1>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20151011/89e7bc1a/attachment.html>