Jack Lloyd <lloydat_private> 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.
This archive was generated by hypermail 2b30 : Wed Oct 17 2001 - 11:21:19 PDT