The two V3 attacks

[David Shaw]

For the curious, I found pointers to the two big fingerprint/keyID spoofing attacks in V3:

DEADBEEF (spoofs key IDs, but not fingerprints):
    http://groups.google.com/group/sci.crypt/browse_thread/thread/25248ce8d6dfc1e4/e5372a1bd972dc07

Bit sliding (spoofs fingerprints, but mangles the size in the process):
    http://groups.google.com/group/nl.comp.crypt/browse_thread/thread/770e8cc32fb222c7/175823454f2649dc

So neither of these are terribly new attacks (both dating from the 1990s).  I had a brainstorm last year about using a DEADBEEF V3 key to collide with a V4 key, as the only way to tell which key was required (for verifying a signature, for example) was via the 64-bit key ID and inside the signature, there was no way to tell if it was a V3 or V4 key making the signature.  That may have been the first mention of that particular variant - I don't know.  There was some discussion about this on the IETF WG list at the time, but it's really an implementation issue (by the spec, implementations are not required to accept V3 keys if they don't want to).

Note one of the caveats about using DEADBEEF to collide with V4: even numbered keys.  Since the key ID is the lower 64 bits of p*q, and p and q are large primes, the key ID for a valid key will always be odd.   Offhand I can't think of a simple way around this without the key being either extremely weak, or invalid (a nice thing about DEADBEEF is that it's a collision, but it's a real usable key as well).  I suppose if the intent is to just create trouble, then those restrictions are less important.

The other thing to note about DEADBEEF is that this sort of collision can happen V4-V4 as well.  It's just very unlikely.  Someone astutely pointed out in the original discussion that the possibility of V3-V4 collisions sort of keeps us honest - that banning V3 may mean we won't fix the V4-V4 problem because it's so hard to cause.  I look at banning V3 as buying us time to fix V4 (or go to V5).

David