Overview

There are a lot of guides on the internet about GPG best practice, some outdated, some wrong, some right etc. I don't pretend to be an expert in this area, but I have done a lot of reading so I hope this guide is as accurate as it can be for the time it was published. Do feel feel to contact me if you find errors.
This guide aims to get you secure GPG keys by making use of subkeys and off-line machines.

There will be a follow up post later on about how to move your subkeys to Yubikey (NEO) and how to publish to key servers. Consider this part one.

Requirements

Your going to need a few things for this :

Off-line machine
2x USB sticks
LiveCD
GnuPG 2.0.22 or above (as part of the LiveCD and your workstation)

Steps

Booting a Live media

First things first, do not ever create your master keys on a machine that is online, or on a machine you use daily or anything but a pure clean state. Ignoring things like firmware level hacks (BadUSB, boot loader hacks as there is very little I can do about that) this should give us a secure clean machine. Do note that a VM and a LiveCD is not good enough.

For this task I boot my laptop up via a SystemRescue CD. No network connections should be enabled, nothing but power should be plugged in. Once the live environment has booted disable all wifi/bluetooth and any other network-ish devices. Also kill network manager :

/etc/init.d/NetworkManager stop

Check that its dead via ps, if its still running issue kill -9 to the pid.

USB stick prep

Why two USB sticks? Simple one will be an off-line backup, it will only be ever connected to the LiveCD machine.
The other USB stick we will use to transfer between the off-line machine and your daily work machine.

Now you need to prep your USB sticks. On the LiveCD machine plug in each USB stick. Format each USB stick, I use EXT4 but most file system should be fine. (Avoid vfat/fat if you can)

Next mount the USB sticks, for System Rescue CD I like to mount the two USB sticks like this

/mnt/custom <-- Master
/mnt/backup <-- Backup

However you mount them it won't matter as long as you know which is master/backup.

Next we redirect the gnupghome variable. This will ensure the GPG keys/data are created on the USB stick and not on the LiveCD. Run the following commands but ensure you edit the path to match your USB stick

export GNUPGHOME=/mnt/custom/gnupghome
mkdir $GNUPGHOME
chmod 700 $GNUPGHOME

GPG conf file

Next up create a file called "$GNUPGHOME/gpg.conf" In that file put the following :

default-preference-list SHA512 SHA384 SHA256 SHA224 AES256 AES192 AES CAMELLIA256 CAMELLIA192 CAMELLIA128 TWOFISH
cert-digest-algo SHA512

Lets take a look at what the above does.

default-preference-list

This setting lets us set a preferred list of cyphers It will not stop weaker cyphers been created, All it does is set what cypher order we prefer. So if both parties support SHA512, then the message will be encrypted with that cypher and not a weaker cypher that is listed.

cert-digest-algo

This will sign all subkeys with the set cypher (SHA512 in my case). This effects backwards compatibility a little bit. For example if your using software that can not understand SHA512, then my singed subkeys will be of no use to you. Since I am aiming for higher security I will take the possible loss of some backwards compatibility.

Creating the master key

There are a lot of discussions on whats the best practice for a master key.
The two main points of contention seem to be :

key size
expiry time

Let me address "key size" first. Since this is my master key it won't be used for daily work I don't mind if it takes longer to sign keys. The main arguments I see are there is little point in keys over 3xxx in size. Or that by using 4096 you may get more focus on people cracking key size in power of two's, since 4096 is more common than say 3072. Since this is a not a area I know in depth I had decided to select the biggest key supported now. I can not see an negative of selecting this higher key size, if there is any benefit over 3xxx I can't say.

For the "expiry time". Once again this is a topic of great divide. For me it came down to what is the chance I will lose my master key and my revocation certificate. This was simple for me my master key and revocation certificate are stored off-line in three different places, one of them not even the same country as where I reside. The chance I will lose all three at the same time is very low. There is a small trade off, since my master key will never expire unless you are refreshing your keys from a key server (and you should be) you will have no way to know my master key has been revoked. On the other hand if you can't store you master key and revocation certificate in a safe manner then it would be a good idea to set an expiry time on your master key.

The example below will not be using an expiry.

One small note, do not include a Comment in your User ID it will cause you more problems then you think.

Run the following command "gpg --gen-key" and follow the steps below.

gpg (GnuPG) 2.0.26; Copyright (C) 2013 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

gpg: keyring `/mnt/custom/gnupghome/secring.gpg' created
gpg: keyring `/mnt/custom/gnupghome/pubring.gpg' created
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)
Your selection? 4
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048) 4096
Requested keysize is 4096 bits
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: Brendan Horan
Email address: brendanhoran@basstech.net
Comment:
You selected this USER-ID:
    "Brendan Horan <brendanhoran@basstech.net>"

Change (N)ame, (C)omment, (E)mail or (O)kay/(Q)uit? o
You need a Passphrase to protect your secret key.

We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
gpg: /mnt/custom/gnupghome/trustdb.gpg: trustdb created
gpg: key 76E0A15A marked as ultimately trusted
public and secret key created and signed.

gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
pub   4096R/76E0A15A 2015-09-22
      Key fingerprint = 174D 1B90 066F F847 7A95  E69E 7FB0 D040 76E0 A15A
uid       [ultimate] Brendan Horan <brendanhoran@basstech.net>

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.

At this point GPG will exit. Your master key is done. Do make sure you used a strong pessphrase. Large keysize and week passphrase is still week protection.

Adding extra ID's

You may or may not have multiple e-mail address. If you do and if you want them added to the master key your going to need to add extra ID's. In my case I would like to add "brendan@horan.hk" to the master key. To add extra ID's You need the key ID from when you generated the master key, in my case that is "76E0A15A".

Use the edit-key syntax to add an ID for example I would use "gpg --edit-key 76E0A15A"

gpg (GnuPG) 2.0.26; Copyright (C) 2013 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Secret key is available.

pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
[ultimate] (1). Brendan Horan <brendanhoran@basstech.net>

gpg> adduid
Real name: Brendan Horan
Email address: brendan@horan.hk
Comment:
You selected this USER-ID:
    "Brendan Horan <brendan@horan.hk>"

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

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22


pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
[ultimate] (1)  Brendan Horan <brendanhoran@basstech.net>
[ unknown] (2). Brendan Horan <brendan@horan.hk>

gpg> uid 1

pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
[ultimate] (1)* Brendan Horan <brendanhoran@basstech.net>
[ unknown] (2). Brendan Horan <brendan@horan.hk>

gpg> primary

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22


pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
[ultimate] (1)* Brendan Horan <brendanhoran@basstech.net>
[ unknown] (2)  Brendan Horan <brendan@horan.hk>

gpg> save

What you have done now is added a extra ID and set which is your primary key. Primary key should be the one created in the "gen-key" step above. In my case uid 1 is the most trusted , so I set it to the primary key.

Creating a revocation certificate

Do not ever skip this step. If you lose access to your master key this is the ONLY way to revoke it, unless you also set an expiry time. Still its a wise move to create a revocation certificate even if you did set an expiry time. This will allow you to revoke the master key right away rather then wait for it to expire.

Once again you need your key ID. I would run the command "gpg --output $GNUPGHOME/../master-revocation-cirt --gen-revoke 76E0A15A "

This would save a revocation certificate to /mnt/custom/master-revocation-cirt You can see the steps I used below to create the revocation certificate.

sec  4096R/76E0A15A 2015-09-22 Brendan Horan <brendanhoran@basstech.net>

Create a revocation certificate for this key? (y/N) y
Please select the reason for the revocation:
  0 = No reason specified
  1 = Key has been compromised
  2 = Key is superseded
  3 = Key is no longer used
  Q = Cancel
(Probably you want to select 1 here)
Your decision? 1
Enter an optional description; end it with an empty line:
> Emergency use only.
>
Reason for revocation: Key has been compromised
Emergency use only.
Is this okay? (y/N) y

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22

ASCII armored output forced.
Revocation certificate created.

Please move it to a medium which you can hide away; if Mallory gets
access to this certificate he can use it to make your key unusable.
It is smart to print this certificate and store it away, just in case
your media become unreadable.  But have some caution:  The print system of
your machine might store the data and make it available to others!

You want to keep a printed copy of this revocation certificate in off-line location(s).

Initial backup

Since I don't trust computers, its a good idea to backup the work we have done. Firstly lets export the master key for save keeping. Replace the key ID in the below command with your own.

gpg -a --export-secret-keys 76E0A15A > $GNUPGHOME/../masterkey.txt

This will save a copy of the master key at /mnt/custom/masterkey.txt

Next I like to take a whole copy of the gnupg home folder, just to be sure.

cp -a $GNUPGHOME $GNUPGHOME-inital_backup

All done, lets move on.

Adding subkeys

Subkeys are very handy. They allow us to go about our normal day to day business of encryption/signing with out ever needing the master key. Further more we can set expiration dates on each sub key since they are more likely to get lost/compromised. Subkeys also allow us to store some of the keys on devices like the Yubikey neo and others. This is much safer then using a USB stick or leaving your subkeys on your work machines.

In the next step we will create one subkey for signing, encryption and authenticate capability.

Run the command "gpg --expert --edit-key 76E0A15A" once again replace the key ID with your own.

gpg (GnuPG) 2.0.26; Copyright (C) 2013 Free Software Foundation, Inc.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Secret key is available.

gpg: checking the trustdb
gpg: 3 marginal(s) needed, 1 complete(s) needed, PGP trust model
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
[ultimate] (1). Brendan Horan <brendanhoran@basstech.net>
[ultimate] (2)  Brendan Horan <brendan@horan.hk>

gpg> addkey
Key is protected.

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22

Please select what kind of key you want:
   (3) DSA (sign only)
   (4) RSA (sign only)
   (5) Elgamal (encrypt only)
   (6) RSA (encrypt only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)
Your selection? 4
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048)
Requested keysize is 2048 bits
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) 6m
Key expires at Sun Mar 20 06:54:02 2016 UTC
Is this correct? (y/N) yy
Key is valid for? (0) 6m
Key expires at Sun Mar 20 06:55:26 2016 UTC
Is this correct? (y/N) y
Really create? (y/N) y
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
sub  2048R/0B16AD9B  created: 2015-09-22  expires: 2016-03-20  usage: S
[ultimate] (1). Brendan Horan <brendanhoran@basstech.net>
[ultimate] (2)  Brendan Horan <brendan@horan.hk>

gpg> addkey
Key is protected.

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22

Please select what kind of key you want:
   (3) DSA (sign only)
   (4) RSA (sign only)
   (5) Elgamal (encrypt only)
   (6) RSA (encrypt only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)
Your selection? 6
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048)
Requested keysize is 2048 bits
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) 6m
Key expires at Sun Mar 20 07:00:55 2016 UTC
Is this correct? (y/N) y
Really create? (y/N) y
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
sub  2048R/0B16AD9B  created: 2015-09-22  expires: 2016-03-20  usage: S
sub  2048R/1360580A  created: 2015-09-22  expires: 2016-03-20  usage: E
[ultimate] (1). Brendan Horan <brendanhoran@basstech.net>
[ultimate] (2)  Brendan Horan <brendan@horan.hk>

gpg> addkey
Key is protected.

You need a passphrase to unlock the secret key for
user: "Brendan Horan <brendanhoran@basstech.net>"
4096-bit RSA key, ID 76E0A15A, created 2015-09-22

Please select what kind of key you want:
   (3) DSA (sign only)
   (4) RSA (sign only)
   (5) Elgamal (encrypt only)
   (6) RSA (encrypt only)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)
Your selection? 8

Possible actions for a RSA key: Sign Encrypt Authenticate
Current allowed actions: Sign Encrypt

   (S) Toggle the sign capability
   (E) Toggle the encrypt capability
   (A) Toggle the authenticate capability
   (Q) Finished

Your selection? s

Possible actions for a RSA key: Sign Encrypt Authenticate
Current allowed actions: Encrypt

   (S) Toggle the sign capability
   (E) Toggle the encrypt capability
   (A) Toggle the authenticate capability
   (Q) Finished

Your selection? e

Possible actions for a RSA key: Sign Encrypt Authenticate
Current allowed actions:

   (S) Toggle the sign capability
   (E) Toggle the encrypt capability
   (A) Toggle the authenticate capability
   (Q) Finished

Your selection? a

Possible actions for a RSA key: Sign Encrypt Authenticate
Current allowed actions: Authenticate

   (S) Toggle the sign capability
   (E) Toggle the encrypt capability
   (A) Toggle the authenticate capability
   (Q) Finished

Your selection? q
RSA keys may be between 1024 and 4096 bits long.
What keysize do you want? (2048)
Requested keysize is 2048 bits
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) 6m
Key expires at Sun Mar 20 07:03:43 2016 UTC
Is this correct? (y/N) y
Really create? (y/N) y
We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.

pub  4096R/76E0A15A  created: 2015-09-22  expires: never       usage: SC
                     trust: ultimate      validity: ultimate
sub  2048R/0B16AD9B  created: 2015-09-22  expires: 2016-03-20  usage: S
sub  2048R/1360580A  created: 2015-09-22  expires: 2016-03-20  usage: E
sub  2048R/0EECD0AE  created: 2015-09-22  expires: 2016-03-20  usage: A
[ultimate] (1). Brendan Horan <brendanhoran@basstech.net>
[ultimate] (2)  Brendan Horan <brendan@horan.hk>

gpg> save

You can see I have three sub keys, one each for Signing, Encryption and Authentication. Each key will be valid for 6 months. Each key has a size of 2048 since that is the maximum the Yubikey supports right now. If that was to change I could simply revoke the subkeys and reissue again.

Final backup

Since we have hit a milestone in our key creation process its a wise idea to take a backup. I will export the master key + subkey and then export the subkeys separately.

To export the keys run the following:

% gpg -a --export-secret-keys 76E0A15A > $GNUPGHOME/../master_sub_keys.txt
% gpg -a --export-secret-subkeys 76E0A15A > $GNUPGHOME/../subkeys.txt

Lastly I like to take another copy of the whole gnupg home folder. Can't hurt, storage is cheap.

cp -a $GNUPGHOME $GNUPGHOME-backup-master_sub

You now have one USB stick with all the keys and revocation certificate. This will be the master USB stick, it should never be plugged into a non LiveCD/secure machine.

Final steps

This is not the end, we are not yet ready to make use of our new keys. There are few more steps to go! In the next post I will show you how to strip out the master key and transfer the subkeys to your second USB stick and Yubikey device. This will ensure that your master key is never exposed to an internet connected machine.

Lastly I will show you how to push your public keys to a key server in a secure manner.

Make sure you never plug the master USB stick into any machine you don't fully trust!

References

Off-line master keys and yubikey neo
Rise up GPG best practices
Debian guide to subkeys
Alex Cabel, perfect GPG keypair
Debian guide to key creation

Creating secure GPG keys with subkeys