On 2012-03-29, Seth David Schoen <[email protected]> wrote: > There's a nice description of the possibility of creating a public key > with a chosen set of bits at the beginning or end at > > http://www.asheesh.org/note/debian/short-key-ids-are-bad-news.html > > although note that the Tor hidden service identifiers are 80 bits, while > PGP short key IDs are only 32 bits, so it's 2⁴⁸ times as hard to fake a > hidden service as it is to make a colliding PGP short key ID. (Full PGP > fingerprints are 160 bits.)
In the old-style (PGP 2.x) key ID format, a portion of the public RSA modulus was directly used as the key ID. The most difficult-to-implement algorithm that you could possibly want to use to attack that involves a lattice computation, and succeeds far faster than brute-force. New-style (OpenPGP) key IDs are hashes of the public key; the only attack that can produce a desired key ID is brute-force search. (That's not hard though -- for RSA, generate a keypair in the usual manner, then change the public exponent (as Shallot does); for DSA or ElGamal, generate a keypair and then search for powers of the group generator and of the public key which lead to the desired hash. Both attacks allow the brute-force search to be performed on computers which cannot be trusted to know the private key.) So yes, short PGP key IDs are very bad news. Avoid them if you can (but I doubt that you can). Robert Ransom _______________________________________________ tor-talk mailing list [email protected] https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
