Jim Gillogly, <jim(_at_)acm(_dot_)org>, writes:
- 5.5.2 alludes to the 0xDEADBEEF problem with respect to v3 keys.
Geoff Keating posted a message Monday in
comp.security.pgp.tech entitled "Two different DSA keys with
identical key IDs", but I haven't been able to confirm them:
pgpk -a goes haring off to the Netherlands to try to install
them (I didn't realize PGP had a browser built in!). Doing the
fingerprinting "by hand" results in different IDs than the ones
shown in his message -- at least for me. If somebody else can
confirm his result, the v4 key explanation might need to include
a similar caveat.
I have confirmed that the two keys he showed do in fact generate matching
64-bit keyids.
The 64 bit keyid of a DSA key is simply the rightmost 64 bits of the
fingerprint, which is the SHA-1 hash of the key. Generating two keys
with matching keyids is then a matter of finding a 64 bit hash collision.
This requires approximately 2^32 keys to be generated.
You can generate multiple DSA keys quickly if they all share the same
p, q and g values. You pick a random x and calculate the public value
from y = g^x mod p. Then you hash p, q, g and y to form the fingerprint.
Artificially generating two keys with matching keyids is therefore
relatively easy. It is much more difficult to generate a key which
matches the keyid of a given key, which was the original so-called
"0xDEADBEEF attack" that Jim mentions, and which the spec alludes to
in section 5.5.2. That would require generating approximately 2^64 keys,
which would be a huge effort.
Hal