Re: PGP Signed Messages

[pgut001 () cs auckland ac nz (Peter Gutmann)]

Jack Lloyd <lloyd () acm jhu edu> writes:

> In the case of the old (PGP 2.6.2) key format, yes, PGP key ids are easily
> spoofable (the key id was the low 32 bits of the modulus). However, the newer
> format (used for all(?) DSA/Elgamal and some RSA keys) uses the low 32 bits of
> the fingerprint, which is a cryptographic hash of the entire key.  Thus one
> must generate about 2^31 keys to find a single one which matches the key id
> (by the usual birthday paradox attack on a hash function). Lets say you can
> generate and test 100 keys per second (my 1 Ghz Athlon can generate 1 key in
> about 10 seconds with gnupg 1.0.6). In that case, assuming my math isn't
> wrong, it would take you about 250 days to forge a key id. Certainly possible,
> but quite a bit of work.

It's actually much easier than that,  The OpenPGP spec hashes in all sorts of
other stuff (including information completely unrelated to the key, which makes
it more or less impossible to generate a key ID for a key not stored in PGP
format such as on a smart card, grumble complain), and by varying that you can
get away with generating just one key for every 2^32 checks.  As a result, the
search time is limited by the hashing speed.  You can then do the same thing I
did with my attack on MS PKCS #12 files ages ago and precompute the partial
hash of the fixed information, so that all you have left to hash is a few SHA
blocks at the end.  If whatever you have can do 100/sec with keygen then you
might be able to do (say) 1M/sec with partial hashing, which would make it
reasonably practical.

Peter.