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

[Bart Preneel]

On Sun, 11 Oct 2015, Philipp Jovanovic wrote:
> 
>> 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]
>

To provide a slightly broader perspective:

Bert den Boer, Antoon Bosselaers:
Collisions for the Compression Function of MD5. EUROCRYPT 1993: 293-304
(these collisions also give free start collisions for MD5, but with the 
same message and two different IVs).
http://link.springer.com/chapter/10.1007%2F3-540-48285-7_26

Dobbertin's work finds collisions for a single IV that is different from 
the IV of the MD5 specs (semi-free start collision)

Free-start and semi-freestart collision attacks have
been defined in
Xuejia Lai, James L. Massey:
Hash Function Based on Block Ciphers. EUROCRYPT 1992: 55-70
http://link.springer.com/chapter/10.1007%2F3-540-47555-9_5

--Bart

> 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 wont take another 8 
> years as in the case of MD5.
> 
> All the best,
> Philipp
>