Re: [PATCH] Implement fast hash-collision detection

On Tue, Nov 29, 2011 at 01:56:28PM -0800, Bill Zaumen wrote:

Only if the attack actually involves creating a collision on both. But I think the important attacks bypass your CRC anyway. Consider this attack scenario:

  1. Linus signs a tag (or a commit) and pushes it to kernel.org.

  2. kernel.org gets hacked, and the attacker replaces an object with
     an evil colliding version[1].

  3. I clone from kernel.org, and run "git tag --verify". Git says it's
     OK, because the signature checks out, but I have a bogus object.

How does your CRC help? If I understand your scheme correctly, kernel.org will have told me the CRC of all of the objects during the clone. But that isn't part of what Linus signed, so the attacker in step 2 could just as easily have overwritten kernel.org's crc file, and the signature will remain valid.

[1] This is an over-simplification, of course. Because the only even
    remotely feasible attacks on sha1 are birthday attacks, not pre-image
    attacks, there is a step 0 in which the attacker generates a
    colliding pair, convinces Linus to commit it, and then waits.

    Which is probably really hard, but for the purposes of this
    discussion, we assume the attacker is capable of inserting a
    colliding object maliciously into a repo you will fetch from.
    Otherwise, the integrity of sha1 isn't an issue at all.

This is wrong, for two reasons.

  1. The method for generating an object that collides in both sha-1 and
     CRC is not necessarily to generate a colliding sha-1 and then do a
     pre-image attack on the CRC. It is to do a birthday attack on the
     sha-1 and the CRC together. Which halves the bit-strength of the
     CRC to 16 bits (just as we can generally find collisions in 160-bit
     sha1s in 2^80). 16 bits isn't a lot to add when you are trying to
     fix a broken cryptosystem (it's not broken yet, obviously, but when
     it does get broken, will it be because computing reaches the 2^57
     or so that sha1 is broken at, or will it be because a new weakness
     is found that drops sha1's bit-strength to something much lower?).

     This assumes that you can combine the two in a birthday attack.
     Certainly this analysis works against brute-force 2^80 sha1
     collision attacks. But I haven't actually read the details of the
     sha1 attacks, so maybe some of the tweaking they do to get those
     results makes it harder. On the other hand, attacking CRC is far
     from hard, so I certainly wouldn't stake money that sha1 reseachers
     couldn't tweak their attacks in a way that also allows finding CRC
     collisions. You say that an algorithm to do both simultaneously
     does not yet exist. But is that because it's hard, or simply
     because nobody has bothered trying?

     Anyway, all of that is just reiterating that CRC should not be used
     as a security function. It can easily be replaced in your scheme by
     sha-256, which does have the desired properties.

  2. Your attack seems to be "find the sha-1 collision, publish one of
     your colliding objects (i.e., the innocent-looking half), then try
     to break the CRC". And then you claim that by the time you find the
     CRC, everybody will already have the object.

     But wouldn't a smarter attack be to first find the collision, including
     the CRC, and only _then_ start the attack? Then nobody will have
     the object.

     Moreover, it's not true that after a year everyone will have the
     object. People still run "git clone" against kernel.org. Those
     repos do not have the object.

Right. I don't claim that your scheme makes git any weaker. I just claim that it fails to solve the problems people are actually concerned about, and it adds a lot of complexity while doing so.

Right, but we are assuming that sha1 is broken. That's the whole security problem. So the existing digest is not worth much.

But if I don't already have the object, then I have nothing to compare against. So when I get it from kernel.org, I have to simply accept that the object I'm getting is good, and write it into my object db.

Yes, the header has to go at the end of the existing headers. But I don't see any reason that would be a problem for the scheme I described.

Yes, git will helpfully trim whitespace in commit messages. With the current code, you can hide arbitrary bytes in a commit message after a NUL, but don't do that. It's not guaranteed to stay that way, and the appropriate place to add new information is in a header.

Current git should ignore headers that it doesn't understand. I haven't tested this, but Junio recently has been experimenting with gpg-signature lines in commits, and I'm pretty sure he checked that older gits properly ignore them.

-Peff