[Cryptography] [FORGED] Re: Google announces practical SHA-1 collision attack

Mark Steward marksteward at gmail.com
Wed Mar 1 20:35:39 EST 2017


On Wed, Mar 1, 2017 at 10:55 PM, Peter Gutmann <pgut001 at cs.auckland.ac.nz>
wrote:

> Mark Steward <marksteward at gmail.com> writes:
>
> >We do, it's all in the report and referenced papers.
>
> As several people have pointed out, it's not in the report.  Or perhaps
> more
> accurately there is disagreement between the authors of the report and the
> people reading it as to what's in there.  From my multiple re-readings it
> appears that the 6500 CPU-years is the one-off computation for a given
> document and the 100 GPU years (100 GPU years, not 110 GPU hours) is for
> each
> new collision with that document.
>
>
Yep, my reading is that you'd need to repeat all the work of crafting the
path, optimising, finding a suitable first block, crafting the second path,
optimising again, and then crunching to get a second block, for each
different document.

The first block isn't a one-off for a given document (they found another
suitable first block) but there's no point repeating that work if you only
want to find more collisions. The second block is the more expensive one,
though, so it's not like they fall out like gumballs.

I realise that USD 110k is a headline number - they point out that the
expected time to find a second-stage collision is 2.5 times what it took.
But even if you're really unlucky, and the first stage once converted to
GPU takes as much processing power as the second stage, we'd still only be
looking at an average of USD 550k of processing time per prefix on a
universally available resource.



> Another thing that the report is insufficiently clear about is that this
> isn't
> about creating a collision with an existing document, it's about creating a
> document from scratch that can be manipulated to have two different forms
> but
> the same hash.  So it's more a badly-designed-repository-stress-tester
> than a
> signature-forgery attack.
>
>
I think the report makes it clear that it's a chosen-prefix attack, and
while Web PKI is less vulnerable these days, are people outside that
ecosystem as stringent about not signing subverted data? And even a
badly-designed repository might be an app store with automated validation,
or someone's reimplementation of a docker registry.


Mark
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170302/657e1f0d/attachment.html>


More information about the cryptography mailing list