Recovering lost GPG public keys from your YubiKey

Have you ever generated GPG keys, loaded them into your YubiKey, and then thrown away/erased your computer? You’ll discover that when you take your YubiKey to a new computer, GPG refuses to automatically import your key when running --card-status.

The common wisdom on the Internet is that this is because YubiKeys (and Smart Cards in general) don’t store your public keys at all, they only store your private keys, so you must import your public keys from a backup or a public keyserver instead. If you don’t have such a backup, you’re screwed.

However, I investigated this and found that this common wisdom wasn’t true. I was able to recover my public keys from my YubiKey 4 even on a brand new, erased computer. Here’s how you can, too.

I recommend a GPG version 2.2.6 or newer (i.e. newer than the 2.2.4 version that ships with Ubuntu Bionic).

Install the required libraries to access your YubiKey with GPG, if you didn’t already (Linux):

# apt install gnupg2 scdaemon libpcsclite1

Check that your YubiKey is connected and recognised, and print out the keygrips and creation timestamps of your keys:

# gpg2 --card-status --with-keygrip

Application type .: OpenPGP
Version ..........: 2.1
Manufacturer .....: Yubico
Name of cardholder: Nicholas Sherlock
Language prefs ...: [not set]
Salutation .......: Mr.
URL of public key : https://pgp.mit.edu/pks/lookup?op=get&search=0xFA3AB02039C84FFF
Login data .......: [not set]
Signature PIN ....: not forced
Key attributes ...: rsa4096 rsa4096 rsa4096
Max. PIN lengths .: 127 127 127
PIN retry counter : 3 0 3
Signature counter : 12
Signature key ....: 0267 7982 0893 E197 0A75  C570 FA3A B020 39C8 4FFF
      created ....: 2018-08-08 05:34:44
      keygrip ....: 09FFD0653EDA2F5CD7822663E4C940FF28213041
Encryption key....: 086D A938 8FD1 263D 867A  08F5 45BE 6A42 B059 96C3
      created ....: 2018-08-08 05:34:44
      keygrip ....: AB14C602D003421167E9E938BCE1D2144E86B640
Authentication key: 3341 D0B2 5EE9 55DC 791D  65B0 4764 612F 8AAD FC87
      created ....: 2018-08-08 05:35:29
      keygrip ....: 05C0C6FB0877D89DDF387E41AE0C0FAFF68C0DCB
General key info..: [none]

First we’ll import your master (Signature) key from the YubiKey.

Because GPG key IDs are based in part on their creation time, we need to set a fake system time to match the “created” time for the Signature key shown above.

Convert the creation date format like so by removing punctuation, adding a “T” between the date and time, and adding an exclamation mark to the end:

2018-08-08 05:34:44

Becomes:

20180808T053444!

Then we can add that to our GPG arguments like so to start importing the key:

# gpg2 --faked-system-time "20180808T053444!" --full-generate-key

At the menu that pops up, pick the “existing key from card” option:

Please select what kind of key you want:
   (1) RSA and RSA (default)
   (2) DSA and Elgamal
   (3) DSA (sign only)
   (4) RSA (sign only)
  (14) Existing key from card
Your selection? 14

Next, pick the key which has the “cert” right enabled (1), and follow through the prompts to create your user ID:

Available keys:
   (1) 09FFD0653EDA2F5CD7822663E4C940FF28213041 OPENPGP.1 rsa4096 (cert,sign)
   (2) AB14C602D003421167E9E938BCE1D2144E86B640 OPENPGP.2 rsa4096 (encr)
   (3) 05C0C6FB0877D89DDF387E41AE0C0FAFF68C0DCB OPENPGP.3 rsa4096 (sign,auth)

Your selection? 1

Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 0
Key does not expire at all
Is this correct? (y/N) y

GnuPG needs to construct a user ID to identify your key.

Real name: Nicholas Sherlock
Email address: n.sherlock@gmail.com
Comment:
You selected this USER-ID:
    "Nicholas Sherlock <n.sherlock@gmail.com>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? O

gpg: key FA3AB02039C84FFF marked as ultimately trusted
gpg: revocation certificate stored as '/root/.gnupg/openpgp-revocs.d/026779820893E1970A75C570FA3AB02039C84FFF.rev'
public and secret key created and signed.

Note that this key cannot be used for encryption.  You may want to use
the command "--edit-key" to generate a subkey for this purpose.
pub   rsa4096 2018-08-08 [SC]
      026779820893E1970A75C570FA3AB02039C84FFF
uid                      Nicholas Sherlock <n.sherlock@gmail.com>

Now we’ll add the “encr” key as a subkey of this master key.

Use the ID of the master key that was printed in that final “pub rsa4096” block to start editing it, along with the creation date from the Encryption key you got from card-status:

# gpg2 --faked-system-time "20180808T053444!" --edit-key 026779820893E1970A75C570FA3AB02039C84FFF

gpg> addkey
Secret parts of primary key are stored on-card.
Please select what kind of key you want:
   (3) DSA (sign only)
   (4) RSA (sign only)
   (5) Elgamal (encrypt only)
   (6) RSA (encrypt only)
  (14) Existing key from card

Your selection? 14

Available keys:
   (1) 09FFD0653EDA2F5CD7822663E4C940FF28213041 OPENPGP.1 rsa4096 (cert,sign)
   (2) AB14C602D003421167E9E938BCE1D2144E86B640 OPENPGP.2 rsa4096 (encr)
   (3) 05C0C6FB0877D89DDF387E41AE0C0FAFF68C0DCB OPENPGP.3 rsa4096 (sign,auth)

At this menu, pick the (encr) key and follow through to add this subkey:

Your selection? 2

Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 0
Key does not expire at all
Is this correct? (y/N) y
Really create? (y/N) y

Quit and save:

gpg> quit
Save changes? (y/N) y

Repeat the process for the (sign,auth) key, note that the timestamp is different:

# gpg2 --faked-system-time "20180808T053529!" --edit-key 026779820893E1970A75C570FA3AB02039C84FFF

gpg> addkey

Secret parts of primary key are stored on-card.
Please select what kind of key you want:
   (3) DSA (sign only)
   (4) RSA (sign only)
   (5) Elgamal (encrypt only)
   (6) RSA (encrypt only)
  (14) Existing key from card

Your selection? 14

Available keys:
   (1) 09FFD0653EDA2F5CD7822663E4C940FF28213041 OPENPGP.1 rsa4096 (cert,sign)
   (2) AB14C602D003421167E9E938BCE1D2144E86B640 OPENPGP.2 rsa4096 (encr)
   (3) 05C0C6FB0877D89DDF387E41AE0C0FAFF68C0DCB OPENPGP.3 rsa4096 (sign,auth)

Your selection? 3

Please specify how long the key should be valid.
         0 = key does not expire
      <n>  = key expires in n days
      <n>w = key expires in n weeks
      <n>m = key expires in n months
      <n>y = key expires in n years
Key is valid for? (0) 0
Key does not expire at all
Is this correct? (y/N) y
Really create? (y/N) y

Finally, quit GPG and save changes:

gpg> quit
Save changes? (y/N) y

Now you should be able to see your imported key by running this command:

# gpg2 --list-secret-keys --with-keygrip

/root/.gnupg/pubring.kbx
------------------------
sec>  rsa4096 2018-08-08 [SC]
      026779820893E1970A75C570FA3AB02039C84FFF
      Keygrip = 09FFD0653EDA2F5CD7822663E4C940FF28213041
uid           [ultimate] Nicholas Sherlock <n.sherlock@gmail.com>
ssb>  rsa4096 2018-08-08 [E]
      Keygrip = AB14C602D003421167E9E938BCE1D2144E86B640
ssb>  rsa4096 2018-08-08 [SA]
      Keygrip = 05C0C6FB0877D89DDF387E41AE0C0FAFF68C0DCB

You can test out your recovered key by decrypting a GPG document you prepared earlier:

# gpg2 --decrypt hello-world.gpg
gpg: encrypted with 4096-bit RSA key, ID 45BE6A42B05996C3, created 2018-08-08
      "Nicholas Sherlock <n.sherlock@gmail.com>"
Hello, world!