Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)

[Jeff King <peff@peff.net>]

On Tue, Oct 16, 2012 at 11:32:38AM -0700, david@lang.hm wrote:

> >I don't see much point in it. If we want to add new backup pointers to
> >commit objects, it is very easy to do so by adding new header fields.
> >
> >A much bigger problem is the other places we reference sha1s. The
> >obvious place is trees, which have no room for backup pointers (either
> >in headers, or with a NUL trick). But it also means that any time you
> >have a sha1 that you arrive at in some other way than traversal from a
> >signature, you are vulnerable to attack. E.g., if I record a sha1 in an
> >external system, today I can be sure that when I fetch the object for
> >that sha1, it is valid (or I can check that it is valid by hashing it).
> >With sha1 collisions, I am vulnerable to attack.
> 
> If you have two hashes of the same contents (SHA1 and SHA3) and they
> both agree that the file has not been tampered with, you should still
> be in good shape just using the SHA1 as a reference.

But tampering is only part of it. We care about a chain of authenticity
from some known point (either a gpg signature, or a sha1 that you know
to be good because you recorded it from a trusted source). The
references between objects are the links in that chain.

Whether an internal hash would help you would depend on the exact
details of the collision attack. Let's imagine you have a signed tag
that points to commit sha1 X. The pointed-to commit contains a trailer
that says "btw, my sha-3 is Y". An attacker doing a brute-force birthday
attack would do:

  1. Generate some potential contents for the object (generally, take a good
     and malicious version of the object, and add some random bits at
     the end).

  2. Generate the sha-3 trailer for each object and tack it on.

  3. Generate the sha1 for object+trailer.

  4. Remember the sha1 and contents of each object. If the sha1 matches
     something we generated before, we have a collision. Otherwise, goto
     step 1.

So each object, good or malicious, remains consistent with respect to
the sha-3 hash. We know it has not been tampered with since its
generation, but do we not know if it is the same object that the tagger
originally referenced.  We had to compute the sha-3 as part of
generating the object, but it was not actually part of the collision
attack; it just makes it a little more expensive to compute each
iteration. We still have to do only 2^80 iterations.

But nobody is worried about this 2^80 brute force attack. The problem
with sha-1 (as I understand it) is that there are tricks you can do when
making the modifications in step 1 that will make the sha1 from step 3
more likely to find a collision with something you've already generated.
The modifications you make in step 1 will affect the sha-3 hash in step
2, which ultimately impacts the sha1 hash in step 3. Whether and how
that affects your attack would depend on the exact details of the
tricks.

I don't keep up on the state of the art in sha-1 cracking, so maybe the
techniques happen in such a way that the extra hash would be a
significant impediment. Even if it is sufficient to stop current (or
whatever is "current" when sha1 is broken enough to worry about)
attacks, it is a weak point for future attacks.

-Peff