mailing list archives
PGP CPU time wasta (never refer to pgp key using 32bit key-id)
From: halfdog <me () halfdog net>
Date: Tue, 11 May 2010 00:13:39 +0000
-----BEGIN PGP SIGNED MESSAGE-----
When I created a new pgp key lately, I wanted to have something personal and
easy to remember in the fingerprint, or more precisely the lower 32 bits
(KeyID). The demo code at
http://www.halfdog.net/Projects/PgpKeyTools/KeyGenDSA.java allows to search for
pgp keys with nice KeyID patterns. The program uses data from a given private
key template and varies it. Most of the variation occurs in the "creation time -
secs since 1970" field, so that computation is fast enough (gives ~5 hits/day
for every target KeyId with 1024bit DSA on moderate hardware).
At first I wanted to target 0xdeadbeef of course (because it is that famous),
but when I prepared to upload key, I found out that someone else has already
done that years ago, but it seems that no one has attempted it since then. I do
not know which method was used back than, but since difficulty of public key
fingerprint optimization depends on public key block version, it might have been
harder or easier back then (apart from the CPU speed issues).
To honor the creator of these keys, I refrained from searching for deadbeef
KeyIDs and targeted words in the opposite direction.
Searching the keyservers, I found that many good KeyIDs are still free, e.g.
words/phrases "a bad deed", "defaced" and many regular patterns (41414141, 0)
The KeyID 0x0 might be interesting, because at least one server had a problem
searching for such a key:
Since the KeyID is only a part of the total fingerprint, this program does not
lessen pgp security as such. When e.g. gpg is checking signatures, the whole
fingerprint is used. But it might be a very bad idea to refer to/compare
essential keys using only the 32bit KeyID and textual information from the
self-signature of a key.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
-----END PGP SIGNATURE-----
Full-Disclosure - We believe in it.
Hosted and sponsored by Secunia - http://secunia.com/
- PGP CPU time wasta (never refer to pgp key using 32bit key-id) halfdog (May 11)