Re: [saag] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1

[Robert Moskowitz <[e-mail]>]

I got to be at the conference.  A lot of very good material.  And note 
the attack on OCB2.  Thank you Russ for CCM to dodge the patent fight 
and thus NOT do OCB for 802.11i!   Of course we were looking at OCB1 at 
the time, but who knows what may have been in the final standard.  The 
timing was right for it to have been OCB2...

Anyway on to the SHA1 presentation and the Levchin award for it.

Quite interesting.  Unfortunately the video for it is not being provided at

https://totalwebcasting.com/view/?func=VOFF&id=columbia&date=2020-01-08&seq=1

But check out the Enterprise Cryptography talk from ABN AMRO and their 
moving away from SHA1 certs.

The CRLite talk was also interesting (and talk available).

As to the cost, we are in an exploded bubble right now due to the 
collapse of crypto coin mining. Too much available GPU farms idle 
looking for revenue.  But if this is the cost from public GPU farms 
looking for revenue (and 1 month leases), what is out there dark to our 
reseachers with a little bit of grant money to spend?

The 15 years from theory to practice is something to take away. Don't 
just ignore a theoretical attack, but don't immediately panic and then 
become complacent when nothing seems to come from it (the theory) in a 
year or two.



On 1/7/20 10:23 AM, Russ Housley wrote:
> https://eprint.iacr.org/2020/014
>
>> SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and
>> Application to the PGP Web of Trust
>>
>> Gaëtan Leurent and Thomas Peyrin
>>
>> Abstract: The SHA-1 hash function was designed in 1995 and has been
>> widely used during two decades. A theoretical collision attack was first
>> proposed in 2004 [WYY05], but due to its high complexity it was only
>> implemented in practice in 2017, using a large GPU cluster [SBK+17].
>> More recently, an almost practical chosen-prefix collision attack
>> against SHA-1 has been proposed [LP19]. This more powerful attack allows
>> to build colliding messages with two arbitrary prefixes, which is much
>> more threatening for real protocols.
>>
>> In this paper, we report the first practical implementation of this
>> attack, and its impact on real-world security with a PGP/GnuPG
>> impersonation attack. We managed to significantly reduce the complexity
>> of collisions attack against SHA-1: on an Nvidia GTX 970,
>> identical-prefix collisions can now be computed with a complexity of
>> 2^61.2 rather than 2^64.7, and chosen-prefix collisions with a complexity
>> of 2^63.4 rather than 2^67.1. When renting cheap GPUs, this translates to
>> a cost of 11k US$ for a collision, and 45k US$ for a chosen-prefix
>> collision, within the means of academic researchers. Our actual attack
>> required two months of computations using 900 Nvidia GTX 1060 GPUs (we
>> paid 75k US$ because GPU prices were higher, and we wasted some time
>> preparing the attack).
>>
>> Therefore, the same attacks that have been practical on MD5 since 2009
>> are now practical on SHA-1. In particular, chosen-prefix collisions can
>> break signature schemes and handshake security in secure channel
>> protocols (TLS, SSH). We strongly advise to remove SHA-1 from those type
>> of applications as soon as possible. We exemplify our cryptanalysis by
>> creating a pair of PGP/GnuPG keys with different identities, but
>> colliding SHA-1 certificates. A SHA-1 certification of the first key can
>> therefore be transferred to the second key, leading to a forgery. This
>> proves that SHA-1 signatures now offers virtually no security in
>> practice. The legacy branch of GnuPG still uses SHA-1 by default for
>> identity certifications, but after notifying the authors, the modern
>> branch now rejects SHA-1 signatures (the issue is tracked as
>> CVE-2019-14855).
> _______________________________________________
> saag mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/saag