Generating vanity OpenPGP keys - high level

Showing 1-1 of 1 messages
Generating vanity OpenPGP keys - high level Aaron Toponce 9/12/12 6:46 PM
So, this is something I've been interested in, and thought I would share.
Maybe it will generate some discussion. Lately, I've been interested in
generating a vanity OpenPGP key id. In case you're curious, the lower
32-bits of your key's fingerprint are your "key id". So, my fingerprint is:

    E041 3539 273A 6534 A3E1  9259 22EE E048 8086 060F

This means my key id is "8086 060F". Cool (it has 8086 in it after all),
but wouldn't it be better to do something like "DEAD D00D" OR "BEEF CAFE"
as my key id? Can you do it?

Yes, you can. You have two options:

1) Brute force. This requires generating a GnuPG key, checking the key id,
and if it matches quit. If not, generate a new key, and check again.
Unfortunately, GnuPG draws extensively on the entropy pool, and if it
empties, it will wait for more entropy before continuing. This is very,
_very_ slow.

So, you need more entropy. This means purchasing a hardware true random
number generator, such as the Entropy Key from http://www.entropykey.co.uk,
or making your own. However, there is also haveged from
http://www.issihosts.com/haveged/ which uses interrupts on your
motherboard, among other things, to generate true random numbers.

After one of these is keeping your entropy pool filled, you can move at a
much quicker pace. Currently, I'm moving at about 50 keys per second on a
single box. Throwing 3 additional boxes at it (with varying hardware
specs), and I'm moving at a pace of about 10 million per 24 hours. At this
rate, it will take me about 430 days to completely exhaust the search space
(2^32 keys) assuming a uniform distribution.

... or ...

2) Packet mangling. This requires a thorough understanding of RFC 4880,
specifically sections 5.2.2 and 12.2. The underlying idea, is that you
generate one private key (it can be a full keypair- doesn't matter). Then,
using a programming language, you look at the private key packets. In
OpenPGP, keys, signatures, ciphertext, etc. is built using "packets". These
packets contain timestamps, algorithms, etc.

In our case, we're interested in the packet that generates the private key
fingerprint. The fingerprint is nothing more than a SHA1 checksum of this
packet, and some static data. Part of that packet is the timestamp in
seconds from Jan 1, 1970 when the key was created (the UNIX epoch). If I
loop over the timestamp, I can regerate the fingerprint with SHA1, and
check the lower 32-bits of the SHA1 hexadecimal output.

I can generate SHA1 checksums _substantially_ faster than generating new
OpenPGP keys. So much faster, I can be guaranteed to find my vanity key id
in a few hours on a simple netbook. Much better than 430 days.

Once the SHA1 checksum is found, I simply modify the packet of the private
key to contain the timestamp I want, then (re)generate the public key. At
this point, I have my vanity 32-bit key id

CONCLUSION:
If it's not immediately obvious, members of the OpenPGP community should
not be relying on 32-bit key ids for uniqueness, seeing as though it's
trivial to collide a 32-bit key id with someone else's. Instead, the lower
64-bits would be a much better proposal, and in fact just relying on the
full 160-bit fingerprint would be best. But, if you're only interested in
generating vanity 32-bit key ids, without causing havoc, then this is the
way you would do it.

Cheers!

--
. o .   o . o   . . o   o . .   . o .
. . o   . o o   o . o   . o o   . . o
o o o   . o .   . o o   o o .   o o o