Re: DEADBEEF vs SHA1

[David Shaw <[e-mail]>]

I think I wasn't as clear as I should have been, so let me try and clarify my thoughts a bit more.  There are two issues here:

I started looking at this in the context of the signing key collision issue that Daniel Gillmor had posted about.  He was concerned about the chance of a SHA-1 V4-to-V4 64-bit collision, and I pointed out there is also a risk of a V3-to-V4 collision, which is vastly easier to accomplish.  Now, Daniel's proposed fix handles both cases, so that would seem to be the end of it.  We've already discussed his fix, and so here's just another reason why it's a useful idea.  So, done.  No problem.  That's the standards part of the message.

However, wearing my implementation hat, we do have a different problem now.  In trying out the V3-to-V4 collision against current implementations in the field, it turns out to be a denial of service attack, as at least the implementations that I tried (PGP 9 and GPG 1.4) can't cope very well with two different keys with the same 64-bit key ID.  The "fingerprint in each signature" is intended to disambiguate between two different keys with the same key ID in order to find the real signer.  However, we don't even get to that point, as we can't import two different keys with the same key ID in the first place (the RFC even warns about this specifically).

The end result is that if someone makes this sort of collision, they can upload them to keyservers (perhaps ironically, SKS can handle multiple keys with the same 64-bit key ID just fine), thus "poisoning" certain keys.  Once a key is poisoned, requesting it from the keyserver will return both the good and bad keys in a (so far as I can tell) nondeterministic order, so anyone fetching that key risks importing the bad one, causing signature verifications from the real key to fail, blocking encryption to the real key, and generally making a nuisance.

My proposed fix for this is not an OpenPGP standard issue, as I'm not proposing removing V3 support from the standard.  Rather, I'm just taking advantage of the fact that many OpenPGP developers read this list to raise awareness of the issue, and point out that adding a knob to enable or disable V3 (as allowed for in the standard) is a fairly simple way to avoid this problem.

David