OpenPGP vanity keys with a patched GnuPG

I'm vain, but also lazy to remember long strings of arbitrary hexadecimal digits. Generating vanity keys for GnuPG would address both needs (wants): a vanity key fingerprint would be meaningful, and therefore more memorable.

What is a memorable key fingerprint? This is not one:

pub 1024D/0DA1756824EEB426 2001-01-15 [expired: 2006-01-14] uid Bernd Jendrissek (or owner of this keypair) <Bernd.Jendrissek@mailbox.co.za> uid Bernd Jendrissek <Bernd.Jendrissek@mailbox.co.za>

That is one of my old keys, and it happens that I did memorize at least the short-form keyid - but what a nerdy thing to do. And not something I can expect other people to remember - to them it's just an arbitrary hex string, with little personal relevance.

The obvious solution is to generate a key whose fingerprint carries some meaning, that's easier to remember. A word maybe, spelled in l33tspeak, or some recognizeable number like pi or e (a shibboleth for fellow nerds).

Something like this:

pub 4096R/FAC02779DEC0DED1 2014-01-21 [expires: 2024-01-19] uid Bernd Jendrissek

That's my now-current key that should have propagated to a keyserver near you.

By what black magic did I do this? It took me a while to get to a solution that works well enough to find worthwhile vanity keys. At first I just ran gpg in a shell loop, generating keys one by one. But that's ridiculously slow - it generates a whole new key from scratch each time, which exhausts the entropy pool (arguably a bug in GnuPG - /dev/urandom is really good enough) and does a whole bunch of CPU-intensive computing for every key.

Unfortunately, it takes minutes for standard GnuPG to generate just one key (although most of that is probably in waiting for more entropy). I'd be dead 500 times over before I had a good sampling of word-like key fingerprints. No, I would have to get my hands dirty by patching GnuPG and the libraries it uses. Here's one for libgcrypt:

diff --git a/cipher/rsa.c b/cipher/rsa.c index ccc9f96..319c001 100644 --- a/cipher/rsa.c +++ b/cipher/rsa.c @@ -177,6 +177,7 @@ check_exponent (void *arg, gcry_mpi_t a) * TRANSIENT_KEY: If true, generate the primes using the standard RNG. * Returns: 2 structures filled with all needed values */ +int delta __attribute__((visibility("default"))); static gpg_err_code_t generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, int transient_key) @@ -324,6 +328,26 @@ generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, return GPG_ERR_SELFTEST_FAILED; } + if (getenv("LIBGCRYPT_MINE")) { + int spread = atoi(getenv("LIBGCRYPT_MINE")); + for (delta = -spread; delta <= 0; delta++) { + switch (fork()) { + case -1: + log_debug("failed to fork\n"); + exit(1); + break; + case 0: + /* Child. */ + return 0; + default: + /* Parent. */ + wait(NULL); + break; + } + } + exit(0); + } + return 0; } diff --git a/src/libgcrypt.vers b/src/libgcrypt.vers index 5a617cc..fd18fc2 100644 --- a/src/libgcrypt.vers +++ b/src/libgcrypt.vers @@ -104,6 +104,7 @@ GCRYPT_1.2 { gcry_mpi_set_ui; gcry_mpi_snew; gcry_mpi_sub; gcry_mpi_sub_ui; gcry_mpi_subm; gcry_mpi_swap; gcry_mpi_test_bit; gcry_mpi_lshift; +delta; local: *;

This bit of code forks the process after it has generated a precious prime pair and exposes a different fudge value (delta) which gets used later in GnuPG proper. Speaking of which:

diff --git a/g10/keygen.c b/g10/keygen.c index 8c3e9f6..64cc2d6 100644 --- a/g10/keygen.c +++ b/g10/keygen.c @@ -120,6 +120,7 @@ struct opaque_data_usage_and_pk { PKT_public_key *pk; }; +extern int delta; static int prefs_initialized = 0; static byte sym_prefs[MAX_PREFS]; @@ -1435,7 +1463,7 @@ gen_rsa (int algo, unsigned nbits, KBNODE pub_root, KBNODE sec_root, DEK *dek, if (!nbits) nbits = DEFAULT_STD_KEYSIZE; - if (nbits < 1024) + if (!getenv("GNUPG_MINE") && nbits < 1024) /* XXX I'm not sure if this is important. */ { nbits = 1024; log_info (_("keysize invalid; using %u bits\n"), nbits ); @@ -1463,7 +1491,7 @@ gen_rsa (int algo, unsigned nbits, KBNODE pub_root, KBNODE sec_root, DEK *dek, sk = xmalloc_clear( sizeof *sk ); pk = xmalloc_clear( sizeof *pk ); - sk->timestamp = pk->timestamp = timestamp; + sk->timestamp = pk->timestamp = timestamp + delta; sk->version = pk->version = 4; if (expireval) { @@ -3350,6 +3378,65 @@ start_tree(KBNODE *tree) delete_kbnode(*tree); } +static char const *check_vanity(KBNODE pub_root, char keyid[static 17]) +{ + PKT_public_key *pk; + gcry_md_hd_t md; + + gcry_md_hd_t do_fingerprint_md(PKT_public_key *pk); + + if (pub_root) { + pk = find_kbnode (pub_root, PKT_PUBLIC_KEY)->pkt->pkt.public_key; + md = do_fingerprint_md(pk); + } + if (!pub_root || md) { + const byte *dp; + char const *vanity_patterns[] = { + /* Simple repetitions and sequences. */ + "(.)\\1.*\\1\\1.*\\1\\1", + "(.)\\1\\1.*\\1.*(.)\\2\\2|(.)\\1\\1.*(.).*\\2\\2\\2", + "(.)\\1\\1\\1$", + "123456|234567|345678|456789|56789A|6789AB|789ABC|89ABCD|9ABCDE|ABCDEF", + /* Math/physics constants. */ + "314159|271828|60221|1380[67]|8314[45]|299792|6626[01]|66738|9109[34]|40490FDB|27315", + /* Biographical details. */ + "^(..)*1976|^(..)*760518|^(..)*1805|^(..)*5231080", + /* 13375p34k. */ + "^([05ABCDEF]*[0AE]){2,}[05ABCDEF]*$", + "CA5CADE|0DE55A|ACCE55|A55E55|BA0BAB|CA5CADE|DECADE|DEC0DE|D0D0E5|FACADE|0B5E55|5EABED|5EAF00D|5EED", + /* Former keys. */ + "24EEB426|FCDE4B8C|804177F8|AAE76E8E|D7CBA633|D5B8044C|1726CB60", + /* Famous words. */ + "DEADBEEF|C0FFEE", + /* ASCII. */ + "^(2[0DEF]|3[0-9F]|[46].|[57][0-A])*$", + "^(..)*[46]2[46]5[57]2[46]e[46]4|[46]2[57]0[46]a|[46]a[46]5[46]e[46]4[57]2[46]9[57]3", + NULL + }; + int i; + int check_regexp(const char *expr,const char *string, int sanitize); + + if (pub_root) { + dp = gcry_md_read(md, 0); + + sprintf(keyid, "%02X%02X%02X%02X%02X%02X%02X%02X", + dp[12], dp[13], dp[14], dp[15], dp[16], dp[17], dp[18], dp[19]); + } else { + keyid[0] = 0; + } + + for (i = 0; vanity_patterns[i]; i++) { + if (check_regexp(vanity_patterns[i], keyid, 0)) { + return vanity_patterns[i]; + } + } + if (!vanity_patterns[i]) { + return NULL; + } + } + + return NULL; +} static void do_generate_keypair (struct para_data_s *para, @@ -3363,6 +3450,7 @@ do_generate_keypair (struct para_data_s *para, int rc; int did_sub = 0; u32 timestamp; + char keyid[17]; if( outctrl->dryrun ) { @@ -3453,13 +3541,15 @@ do_generate_keypair (struct para_data_s *para, linked list. The first packet is a dummy packet which we flag as deleted. The very first packet must always be a KEY packet. */ - start_tree (&pub_root); - start_tree (&sec_root); - timestamp = get_parameter_u32 (para, pKEYCREATIONDATE); if (!timestamp) timestamp = make_timestamp (); + check_vanity(NULL, keyid); + + start_tree (&pub_root); + start_tree (&sec_root); + /* Note that, depending on the backend (i.e. the used scdaemon version), the card key generation may update TIMESTAMP for each key. Thus we need to pass TIMESTAMP to all signing function to @@ -3492,6 +3582,17 @@ do_generate_keypair (struct para_data_s *para, } } + /* Check key for vanity value. */ + if (!rc && getenv("GNUPG_MINE")) { + char const *matching_pattern = check_vanity(pub_root, keyid); + if (matching_pattern) { + log_debug("Found key %s with %s, delta = %d\n", + keyid, matching_pattern, delta); + } else { + exit(0); + } + } + if(!rc && (revkey=get_parameter_revkey(para,pREVOKER))) { rc = write_direct_sig (pub_root, pub_root, pri_sk, revkey, timestamp); @@ -3637,7 +3751,7 @@ do_generate_keypair (struct para_data_s *para, keydb_release (pub_hd); keydb_release (sec_hd); - if (!rc) + if (!rc && !getenv("GNUPG_MINE")) { int no_enc_rsa; PKT_public_key *pk; diff --git a/g10/trustdb.c b/g10/trustdb.c index dedb18c..f8c2dda 100644 --- a/g10/trustdb.c +++ b/g10/trustdb.c @@ -1852,8 +1852,8 @@ sanitize_regexp(const char *old) /* Used by validate_one_keyblock to confirm a regexp within a trust signature. Returns 1 for match, and 0 for no match or regex error. */ -static int -check_regexp(const char *expr,const char *string) +int +check_regexp(const char *expr,const char *string, int sanitize) { #ifdef DISABLE_REGEX /* When DISABLE_REGEX is defined, assume all regexps do not @@ -1863,19 +1863,59 @@ check_regexp(const char *expr,const char *string) int ret; char *regexp; - regexp=sanitize_regexp(expr); + regexp=sanitize?sanitize_regexp(expr):xstrdup(expr); #ifdef __riscos__ ret=riscos_check_regexp(expr, string, DBG_TRUST); #else { + static struct { + char *pattern; + regex_t pat; + } pat_cache[100]; + static int initialized = 0; regex_t pat; + int i, i_empty; + + if (!initialized) { + for (i = 0; i < 100; i++) { + pat_cache[i].pattern = 0; + } + initialized = 1; + } + + for (i = 0, i_empty = -1; i < 100; i++) { + if (i_empty < 0 && !pat_cache[i].pattern) { + i_empty = i; + } + if (strcmp(pat_cache[i].pattern, regexp) == 0) { + break; + } + } - ret=regcomp(&pat,regexp,REG_ICASE|REG_NOSUB|REG_EXTENDED); + if (i < 100) { + memcpy(&pat, &pat_cache[i].pat, sizeof (pat)); + ret = 0; + } else { + ret=regcomp(&pat,regexp,REG_ICASE|REG_NOSUB|REG_EXTENDED); + } if(ret==0) { + if (i_empty < 0) { + for (; i < 100; i++) { + if (!pat_cache[i].pattern) { + i_empty = i; + } + } + } + if (i_empty >= 0) { + pat_cache[i_empty].pattern = xstrdup(regexp); + memcpy(&pat_cache[i_empty].pat, &pat, sizeof (pat)); + } ret=regexec(&pat,string,0,NULL,0); - regfree(&pat); + if (i_empty < 0) { + regfree(&pat); + } ret=(ret==0); } } @@ -1970,7 +2010,7 @@ validate_one_keyblock (KBNODE kb, struct key_item *klist, || opt.trust_model != TM_PGP || (uidnode && check_regexp(kr->trust_regexp, - uidnode->pkt->pkt.user_id->name)))) + uidnode->pkt->pkt.user_id->name, 1)))) { /* Are we part of a trust sig chain? We always favor the latest trust sig, rather than the greater or

This bit uses the fudge value set earlier in each variant process. (I'm lucky here in that GnuPG's keyring seems to be concurrency-safe - although the loop does wait for each child process to finish, appending its key to the keyring, before continuing to fork more child processes.) The fudge value is a delta that modifies the apparent timestamp of the key, adjusting it by up to $LIBGCRYPT_MINE seconds into the past. The timestamp affects the key fingerprint, so this is an easy way to diversify the single pair of primes that gets reused usefully up to thousands of times. (Beyond that, super-linear scaling in GnuPG's keyring access imposes the law of diminishing returns, and it's better to just generate a new pair of primes and write the resulting keys into a fresh keyring.)

The result is a stream of fast, identical keys (with just a differing timestamp), which I then filter with a few regular expressions (compiling them just once, in the parent process, and caching the compiled form for re-use in the child processes). to get a slightly slower stream of candidate keys whose fingerprint is, in some way, memorable and/or meaningful.

I chose one (FAC02779DEC0DED1) fairly arbitrarily - there were several others that took me a long while to reject. I don't need them anymore, so if anyone wants them, I'll sell them for 5mBTC per unique key. You really shouldn't take up this offer though, since these keys would come to you pre-compromised: I have access to the private keys. You'd have to just take my word for it that I'll delete each keyring that I can sell. It's really just for fun, a novelty that you could use for unimportant things. A few cool ones from a total of more than a million:

8F0230444444444C A8111111111C2A72 AB4F37D43CA5CADE 5F2833DEAD52BEEF BB3418DC0FFEEBAD AAA3B57C1CADA555 E30E7A290B314159 9CBC000011112CE1 1251D7C715EAF00D