Faster vanity key mining with GnuPG

My last post described my work making GnuPG look for keys with memorable keyids. It works, but it's slow, presumably because a lot of work gets repeated between each test, and because each test is expensive. With regular expressions and system calls in the mining loop, GnuPG doesn't get to spend much time computing hashes over the generated public key.

But not anymore! I have a better patch now, that allows GnuPG to spend more time hashing and less time doing things which don't contribute to finding a desired keyid. The kernel / user space context switch is now amortized over millions of hashes, and the loop mining for hashes is tight: nearly all it does now is hashing the public key material.

diff --git a/g10/keygen.c b/g10/keygen.c index 8c3e9f6..a250914 100644 --- a/g10/keygen.c +++ b/g10/keygen.c @@ -19,6 +19,7 @@ */ #include <config.h> +#include <fcntl.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -120,6 +121,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]; @@ -1424,6 +1453,7 @@ gen_rsa (int algo, unsigned nbits, KBNODE pub_root, KBNODE sec_root, DEK *dek, STRING2KEY *s2k, PKT_secret_key **ret_sk, u32 timestamp, u32 expireval, int is_subkey) { + extern int searchmode; int rc; PACKET *pkt; PKT_secret_key *sk; @@ -1463,7 +1493,37 @@ 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; + if (getenv("GNUPG_KEYSEARCH")) { + switch (fork()) { + int status; + case -1: + /* Fall back to normal behaviour. */ + break; + case 0: + /* Set search mode and continue executing. */ + searchmode = 1; + break; + default: + wait(&status); + log_debug("Child returned %d\n", WEXITSTATUS(status)); + if (WEXITSTATUS(status)) { + /* Can't find a matching key - just continue. */ + } else { + /* Key matches - fudge timestamp. */ + int fd; + fd = open("/tmp/keysearch", O_RDONLY); + if (fd != -1) { + read(fd, &delta, sizeof (delta)); + close(fd); + log_debug("Continuing with delta=%d\n", delta); + } else { + log_debug("Couldn't open /tmp/keysearch\n"); + } + } + break; + } + } + sk->timestamp = pk->timestamp = timestamp + delta; sk->version = pk->version = 4; if (expireval) { diff --git a/g10/keyid.c b/g10/keyid.c index d7a877b..4d5d370 100644 --- a/g10/keyid.c +++ b/g10/keyid.c @@ -19,6 +19,7 @@ */ #include <config.h> +#include <fcntl.h> #include <stdio.h> #include <stdlib.h> #include <string.h> @@ -124,15 +125,63 @@ hash_public_key( gcry_md_hd_t md, PKT_public_key *pk ) } } -static gcry_md_hd_t +int searchmode = 0; + +gcry_md_hd_t do_fingerprint_md( PKT_public_key *pk ) { gcry_md_hd_t md; + int delta; + const byte *dp; + unsigned char keyid[8]; + char const *keysearch = getenv("GNUPG_KEYSEARCH"); + int keysearch_len = keysearch ? strlen(keysearch) : 0; + int spread = searchmode && keysearch ? 33554432-1 : 0; + u32 original_timestamp = pk->timestamp; - if (gcry_md_open (&md, DIGEST_ALGO_SHA1, 0)) - BUG (); - hash_public_key(md,pk); - gcry_md_final( md ); + if (searchmode && keysearch) { + int i; + + memset(keyid, 0, sizeof (keyid)); + for (i = 0; i < keysearch_len/2; i++) { + sscanf(keysearch + i*2 + keysearch_len%2, "%02hhx", keyid+i); + } + log_debug("Searching for key fingerprints ending in %02X%02X%02X%02X%02X%02X%02X%02X\n", + keyid[0], keyid[1], keyid[2], keyid[3], keyid[4], keyid[5], keyid[6], keyid[7]); + } + for (delta = -spread; delta <= 0; delta++) { + if (gcry_md_open (&md, DIGEST_ALGO_SHA1, 0)) + BUG (); + pk->timestamp = original_timestamp + delta; + hash_public_key(md,pk); + gcry_md_final( md ); + if (searchmode && keysearch) { + dp = gcry_md_read(md, 0); + if (memcmp(dp + 20 - keysearch_len/2, keyid, keysearch_len/2)) { + if (delta % 1000000 == 0) { + log_debug("Trying delta = %d\n", delta); + } + } else { + int fd; + fd = open("/tmp/keysearch", O_CREAT|O_WRONLY, 0666); + if (fd == -1) { + log_debug("Couldn't open /tmp/keysearch\n"); + continue; + } + write(fd, &delta, sizeof (delta)); + close(fd); + log_debug("Found delta = %d\n", delta); + exit(0); + } + gcry_md_close(md); + } + } + + if (searchmode) { + /* Failed to find a matching key. */ + log_debug("Never found a matching key\n"); + exit(1); + } return md; }

I now have 0x5EAF00D5 and 0x0B5E55ED, and I'm not sure what else I want to mine. Maybe I'll just stick with 0xDEC0DED1 for now.