[Cryptography] Google announces practical SHA-1 collision attack

[Mark Steward]

On Wed, Mar 1, 2017 at 2:52 AM, Kevin W. Wall <kevin.w.wall at gmail.com>
wrote:

> On Tue, Feb 28, 2017 at 9:18 AM, Theodore Ts'o <tytso at mit.edu> wrote:
> > On Sun, Feb 26, 2017 at 09:04:45PM -0600, Nikita Borisov wrote:
> >> On Sat, Feb 25, 2017 at 5:06 PM, Peter Gutmann <
> pgut001 at cs.auckland.ac.nz>
> >> wrote:
> >>
> >> > They announced an attack that requires a nation-state's worth of
> resources
> >> > and
> >> >
> >>
> >> The cost estimates were around $500K at normal EC2 prices and $100K at
> spot
> >> prices. I'd have imagined that nation states command rather more
> resources
> >> than that!
> >
> > If I'm not mistaken, those are the costs for the *second* phase of the
> > attack (110 GPU years).  However, you have to first carry out the
> > *first* phase of the attack, which takes 6200 CPU years.
> >
> > Aside from throwing out numbers which are much scarier, which make for
> > good headlines and scaring clients to score more consulting time, is
> > there a reason why people are fixated on the 110 GPU year "second
> > phase" number, and not the 6200 GPU years "first phase" number?
>
> I've wondered that as well, unless somehow it is expected that the
> first phase produces results that can somehow be reused for multiple
> collisions.
>
> But more specifically, a question that I've tried to get an answer to and
> so far have been unable to turn up is:
>     What exactly type of CPU / GPU is Google basing these ill-defined
>     "CPU year" and "GPU years" terms on?
>
>
It's all in the report PDF [1]:

> Theory predicts the first near-collision attack to be at least a factor 6
faster than the second attack

> run on a heterogeneous CPU cluster hosted by Google, spread over 8
physical locations...

> There was a variety of CPUs involved in this computation, but it is
reasonable to assume
> that they all were roughly equivalent in performance. On a single core of
a 2.3 GHz Xeon
> E5-2650v3...

> a GPU being far more powerful, it is actually much more efficient
> to run it on the latter: the attack of [18] takes only a bit more than
four days to run on
> a single GTX 970, which is much less than the estimated 150 days it would
take using a
> single quad-core CPU.

> We did not write a CPU implementation of our own attack for the search
> of the second block... it is reasonable to assume that the gap would be
of the same order.

If you invest in dedicated hardware you'd probably be able to provide a
hash collision service right now. The estimated global Bitcoin hash rate[2]
is currently 3-4 * 10^18 SHA-256 hashes per second, while the estimated
work for this collision is 9 * 10^18 SHA-1 hashes in total.


Mark

[1] http://shattered.it/static/shattered.pdf
[2] https://blockchain.info/charts/hash-rate
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170301/be9daa5d/attachment.html>