From: wcs@anchor.ho.att.com (bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
Date: Tue, 1 Feb 94 00:45:25 PST
To: cypherpunks@toad.com
Subject: PGP keyid collisions?
Message-ID: <9402010844.AA26415@anchor.ho.att.com>
MIME-Version: 1.0
Content-Type: text/plain


I had discussed the benefit of putting PGP keyID or fingerprint
in signatures to reduce spoofing for people who distribute by finger
or unreliable keyservers, though obviously signatures are what
gives you the confidence that a key is valid.

Hal points out that brute-forcing a 24-bit Key-ID isn't all that hard;
the usual formulas tell you what fraction of numbers are prime in the 
desired range, though without looking them up I'd expect it would take
around 2**30 - 2**35 tries to find a specific one; I suppose this 
means the NSA has already done it :-)

> I understand there is already at least one 24-bit collision on the
> public key servers, not unexpected given a few thousand keys.

I assume PGP does the right thing, except in cases of pilot error
(e.g. doing key lookup by KeyID) ?  Even if it does, this has
some design impact on systems using random public-private key generation
for meet-me remailer cutouts.
		Bill
		
# Bill Stewart  AT&T Global Information Systems, aka NCR Corp
# 6870 Koll Center Parkway, Pleasanton CA, 94566 Phone 1-510-484-6204
# email bill.stewart@pleasantonca.ncr.com billstewart@attmail.com
# ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465