Re: Key IDs

[Hal Finney <hal@xxxxxxxx>]

Jim Gillogly, <jim@xxxxxxx>, 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