Re: PGP Signed Messages

["Kurt Seifried" <bugtraq () seifried org>]

> 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.

Yeah but once you have that store of forged keys.... Data storage is cheap.
I just bought a new 1gig athlon system for $600 (so I now have 3 at home..).
Key generation can be optimized (or just done arbitrarily, it's not like I'm
to worried about the actual strength of the key!). It's not a lot of work.
Plus there are many many interesting key ID's in use (i.e. vendor keys....).
I've often thought about this, what happens if someone creates a ton of fake
keys with the same properties (i.e. email/etc) and inter signs them to
replicate the legitimate keys and then uploads them all and injects them
into the internet through other means as well?

> I'm fairly certain that having the entire fingerprint on hand gives you
> pretty much full certainty that the key is legit.

Yup, the chances of finding a collision with MD5 are tiny, with SHA1 darn
near impossible.

> BTW, the GPG for pine plugins automatically verify signatures, and
displays
> the GPG output, ie either "Good signature from ... " or "BAD signature
from
> ..." every time you open the mail. The problems you mention are real, but
a
> problem of 1) bad mail client support, and 2) overly trusting people, not
> the PGP format itself.

This is true but it's a lot like the SSH clients that do NOT warn you that a
server key has changed. Notice that most crypto problems are not in the
algorithm/etc but in the implementation and user interface.

Kurt Seifried, kurt () seifried org
A15B BEE5 B391 B9AD B0EF
AEB0 AD63 0B4E AD56 E574
http://www.seifried.org/security/