Build an OpenPGP key based on ECC

This article is the first of a serie dealing with privacy on the Internet. In this one, I’m going to show you how to build an OpenPGP key based on Elliptic Curve Cryptography (ECC). Normally I shouldn’t have to explain what OpenPGP is for, but anyway, I’m going to do it for the latecomers and those at the back of the class.

Uh, I’ve already heard about PGP, GPG and OpenPGP, what are all these names?

Excellent question and it is true that the difference is not very clear if you have never been curious about this tool.

Pretty Good Privacy (PGP) is an encryption program that provides cryptographic privacy and authentication for data communication. PGP is used for signing, encrypting, and decrypting texts, e-mails, files, directories. Philip Zimmermann developed PGP in 1991.

GNU Privacy Guard (GnuPG or GPG) is a free-software replacement for Symantec’s PGP cryptographic software suite, and is compliant with RFC 4880, the IETF standards-track specification of OpenPGP. Modern versions of PGP are interoperable with GnuPG and other OpenPGP-compliant systems.

OpenPGP is an open source PGP encryption standard for public use.

Unlike a RSA key pair, the OpenPGP protocol allows you to create a digital identity that is verified by others and is decentralized. There is no authority that will control the identity. Users will verify other people’s identities.

Information and requirements

These elements are to be taken into consideration to follow this article:

Preliminary

Update the system

yay -Syyuu

Install required utilities

yay -S gnupg

Temporary working directory

Create a temporary directory and set it as the GnuPG directory.

set -x GNUPGHOME (mktemp -d)

Please note that if you don’t use fish shell like I do, you should execute the following command to export a variable.

export GNUPGHOME=$(mktemp -d)

Strengthen the configuration

Create a hardened configuration in the temporary working directory ($GNUPGHOME/gpg.conf) with the following options.

personal-cipher-preferences AES256 AES192 AES
personal-digest-preferences SHA512 SHA384 SHA256
personal-compress-preferences ZLIB BZIP2 ZIP Uncompressed
default-preference-list SHA512 SHA384 SHA256 AES256 AES192 AES ZLIB BZIP2 ZIP Uncompressed
cert-digest-algo SHA512
s2k-digest-algo SHA512
s2k-cipher-algo AES256
charset utf-8
no-comments
no-emit-version
keyid-format 0xlong
list-options show-uid-validity
verify-options show-uid-validity
with-fingerprint
require-cross-certification
no-symkey-cache
throw-keyids

Let’s dive right in the explanations of these options:

Master key

The first key to generate is the master key and has only the capability to certify. It will be used for certification only: to issue subkeys that are used for encryption, signing and authentication. The master key should be kept offline at all times and only accessed to revoke or issue new subkeys. You’ll be prompted to enter and verify a passphrase: keep it handy as you’ll need it multiple times later.

Generating a strong password can be done like follow. You can easily modify the password length by increasing or decreasing the -w flag value.

tr -cd '[:alnum:]' < /dev/urandom | fold -w 25 | head -n 1
vI1mqmyx0LnuA6Dl9clwMk65E

Generate

Choose to create an ECC key by choosing the option 11. It is important to choose set your own capabilities, because we want to select specific capabilities which is not available otherwise.

gpg --expert --full-generate-key
gpg (GnuPG) 2.2.23; Copyright (C) 2020 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: keybox '/tmp/tmp.EOmP2zbviM/pubring.kbx' 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)
   (7) DSA (set your own capabilities)
   (8) RSA (set your own capabilities)
   (9) ECC and ECC
  (10) ECC (sign only)
  (11) ECC (set your own capabilities)
  (13) Existing key
  (14) Existing key from card
Your selection? 11

Toggle capability

By toggling the sign capability, you keep only the certify one.

Possible actions for a ECDSA/EdDSA key: Sign Certify Authenticate
Current allowed actions: Sign Certify

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

Your selection? S

Possible actions for a ECDSA/EdDSA key: Sign Certify Authenticate
Current allowed actions: Certify

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

Your selection? Q

As you can see, the only allowed action is set to certify.

Choose the elliptic curve

Now you have to choose which elliptic curve you want. I (and I advise you to) choose Curve25519. It is an elliptic curve offering 128 bits of security (256 bits key size) and designed for use with the Elliptic-Curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest ECC curves and is not covered by any known patents.

Please select which elliptic curve you want:
   (1) Curve 25519
   (3) NIST P-256
   (4) NIST P-384
   (5) NIST P-521
   (6) Brainpool P-256
   (7) Brainpool P-384
   (8) Brainpool P-512
   (9) secp256k1
Your selection? 1

Set the key expiration

Do not set the master key to expire. Setting an expiry essentially forces you to manage your subkeys and announces to the rest of the world that you are doing so. Setting an expiry on a primary key is ineffective for protecting the key from loss - whoever has the primary key can simply extend its expiry period. Revocation certificates are better suited for this purpose. It may be appropriate for your use case to set expiry dates on subkeys.

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

Identify your key

Remember that the purpose of a key is to identify you, not to make you anonymous. If you hesitate concerning the information to give, this article proposes some points of reflection.

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

Real name: John Doe
Email address: john.doe@example.com
Comment:
You selected this USER-ID:
    "John Doe <john.doe@example.com>"

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

Once you choose O, GPG will generate the 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: /tmp/tmp.EOmP2zbviM/trustdb.gpg: trustdb created
gpg: key 0xB52326F13324098C marked as ultimately trusted
gpg: directory '/tmp/tmp.EOmP2zbviM/openpgp-revocs.d' created
gpg: revocation certificate stored as '/tmp/tmp.EOmP2zbviM/openpgp-revocs.d/0ED8F4861E57693EC1E34EBEB52326F13324098C.rev'
public and secret key created and signed.

pub   ed25519/0xB52326F13324098C 2020-10-11 [C]
      Key fingerprint = 0ED8 F486 1E57 693E C1E3  4EBE B523 26F1 3324 098C
uid                              John Doe <john.doe@example.com>

As you can see, GPG asks you to perform other actions (type on the keyboard, move the mouse, utilize the disks) during the prime generation. It gives the random number generator a better chance to gain enough entropy. If, like me, your system already generates a lot of entropy, this step will take less than a second. On the other hand it may be that you don’t have enough entropy if you use a virtual machine with poor performance, an old computer… You can verify the available entropy by using the following command.

cat /proc/sys/kernel/random/entropy_avail
3848

Tool like rng-tools monitors a set of entropy sources, and supplies entropy from them to the system kernel’s /dev/random machinery.

Export the key ID as shell variable

Later, when we make changes to the key it will be easier to call the key ID. You can find this key ID a little further up (gpg: key 0xB52326F13324098C marked as ultimately trusted).

set KEYID 0xB52326F13324098C

Subkeys

Now, we will create subkeys for signing, encrypting and authentificating. Edit your brand new key.

gpg --expert --edit-key $KEYID
gpg (GnuPG) 2.2.23; Copyright (C) 2020 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: marginals needed: 3  completes needed: 1  trust model: pgp
gpg: depth: 0  valid:   1  signed:   0  trust: 0-, 0q, 0n, 0m, 0f, 1u
sec  ed25519/0xB52326F13324098C
     created: 2020-10-11  expires: never       usage: C
     trust: ultimate      validity: ultimate
[ultimate] (1). John Doe <john.doe@example.com>

So here we are with a secret key composed of a main key (ed25519/0xB52326F13324098C) to certify (C) that it will never expire.

Note about the other information:

Signing

Create a signing key by choosing 11. Choose Q to keep the sign capability (the default). Select the Curve25519. Then, concerning the expiration, I advise you to read this answer on StackExchange.

gpg> addkey
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)
  (10) ECC (sign only)
  (11) ECC (set your own capabilities)
  (12) ECC (encrypt only)
  (13) Existing key
  (14) Existing key from card
Your selection? 11

Possible actions for a ECDSA/EdDSA key: Sign Authenticate
Current allowed actions: Sign

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

Your selection? Q
Please select which elliptic curve you want:
   (1) Curve 25519
   (3) NIST P-256
   (4) NIST P-384
   (5) NIST P-521
   (6) Brainpool P-256
   (7) Brainpool P-384
   (8) Brainpool P-512
   (9) secp256k1
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) 1y
Key expires at Mon 11 Oct 2021 03:34:37 PM CEST
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.

sec  ed25519/0xB52326F13324098C
     created: 2020-10-11  expires: never       usage: C
     trust: ultimate      validity: ultimate
ssb  ed25519/0x9B76AA52AF00EFEF
     created: 2020-10-11  expires: 2021-10-11  usage: S
[ultimate] (1). John Doe <john.doe@example.com>

A subkey (ssb) has been created which will expire in one year.

Encryption

Create an encryption key by choosing 12. Select the Curve25519. Then, concerning the expiration, same thing as earlier.

gpg> addkey
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)
  (10) ECC (sign only)
  (11) ECC (set your own capabilities)
  (12) ECC (encrypt only)
  (13) Existing key
  (14) Existing key from card
Your selection? 12
Please select which elliptic curve you want:
   (1) Curve 25519
   (3) NIST P-256
   (4) NIST P-384
   (5) NIST P-521
   (6) Brainpool P-256
   (7) Brainpool P-384
   (8) Brainpool P-512
   (9) secp256k1
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) 1y
Key expires at Mon 11 Oct 2021 03:36:36 PM CEST
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.

sec  ed25519/0xB52326F13324098C
     created: 2020-10-11  expires: never       usage: C
     trust: ultimate      validity: ultimate
ssb  ed25519/0x9B76AA52AF00EFEF
     created: 2020-10-11  expires: 2021-10-11  usage: S
ssb  cv25519/0xE3AC01686E511A38
     created: 2020-10-11  expires: 2021-10-11  usage: E
[ultimate] (1). John Doe <john.doe@example.com>

A new subkey (ssb) has been created which will expire in one year too.

Authentication

Create an authentication key by choosing 11. Select the Curve25519. Remove the sign capability and attach the authenticate one. And finally, concerning the expiration, also same thing as earlier.

gpg> addkey
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)
  (10) ECC (sign only)
  (11) ECC (set your own capabilities)
  (12) ECC (encrypt only)
  (13) Existing key
  (14) Existing key from card
Your selection? 11

Possible actions for a ECDSA/EdDSA key: Sign Authenticate
Current allowed actions: Sign

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

Your selection? S

Possible actions for a ECDSA/EdDSA key: Sign Authenticate
Current allowed actions:

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

Your selection? A

Possible actions for a ECDSA/EdDSA key: Sign Authenticate
Current allowed actions: Authenticate

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

Your selection? Q
Please select which elliptic curve you want:
   (1) Curve 25519
   (3) NIST P-256
   (4) NIST P-384
   (5) NIST P-521
   (6) Brainpool P-256
   (7) Brainpool P-384
   (8) Brainpool P-512
   (9) secp256k1
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) 1y
Key expires at Mon 11 Oct 2021 03:37:58 PM CEST
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.

sec  ed25519/0xB52326F13324098C
     created: 2020-10-11  expires: never       usage: C
     trust: ultimate      validity: ultimate
ssb  ed25519/0x9B76AA52AF00EFEF
     created: 2020-10-11  expires: 2021-10-11  usage: S
ssb  cv25519/0xE3AC01686E511A38
     created: 2020-10-11  expires: 2021-10-11  usage: E
ssb  ed25519/0x2BA042FD767F18C1
     created: 2020-10-11  expires: 2021-10-11  usage: A
[ultimate] (1). John Doe <john.doe@example.com>

A last subkey (ssb) has been created which will expire in one year also.

To summarize, we have a key for each action:

Save our gobbledygook

If you said to yourself: “it’s really fucking incomprehensible” while reading this title, it’s because you didn’t understand and it’s therefore a bad idea to continue. It would be much better to understand what you are doing before continuing.

However, if you have understood everything or don’t care about understanding anything, save everything we just did.

gpg> save

Verify

List the generated secret keys and verify the output. You can also use -K flag instead of --list-secret-keys.

gpg --list-secret-keys
/tmp/tmp.EOmP2zbviM/pubring.kbx
-------------------------------
sec   ed25519/0xB52326F13324098C 2020-10-11 [C]
      Key fingerprint = 0ED8 F486 1E57 693E C1E3  4EBE B523 26F1 3324 098C
uid                   [ultimate] John Doe <john.doe@example.com>
ssb   ed25519/0x9B76AA52AF00EFEF 2020-10-11 [S] [expires: 2021-10-11]
ssb   cv25519/0xE3AC01686E511A38 2020-10-11 [E] [expires: 2021-10-11]
ssb   ed25519/0x2BA042FD767F18C1 2020-10-11 [A] [expires: 2021-10-11]

Check keys for best practices

The output will display any problems with your key in red text. If everything is green, your key passes each of the tests. If it is red, your key has failed one of the tests.

This tool may warn (orange text) about cross certification for the authentication key. GPG’s Signing Subkey Cross-Certification documentation has more detail on cross certification. It may also indicate a problem (red text) with Key expiration times: [] on the primary key but we’ve already talked about that.

gpg --export $KEYID | hokey lint

Revocation certificate

Although we will backup and store the master key in a safe place, it is best practice to never rule out the possibility of losing it or having the backup fail. Without the master key, it will be impossible to renew or rotate subkeys or generate a revocation certificate, the PGP identity will be useless.

gpg --output $GNUPGHOME/revoke.asc --gen-revoke $KEYID
sec  ed25519/0xB52326F13324098C 2020-10-11 John Doe <john.doe@example.com>

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? 0
Enter an optional description; end it with an empty line:
>
Reason for revocation: No reason specified
(No description given)
Is this okay? (y/N) y
ASCII armored output forced.
Revocation certificate created.

The certificate file should be stored (or printed) in a (secondary) place that allows retrieval in case the main backup fails.

Export secret keys

The master key and subkeys will be encrypted with your passphrase when exported.

gpg --output $GNUPGHOME/mastersub.key --armor --export-secret-keys $KEYID
gpg --output $GNUPGHOME/sub.key --armor --export-secret-subkeys $KEYID

Backup

Create an encrypted backup of the keyring and consider using a paper copy of the keys as an additional backup measure.

Attach an external device (USB key) and check its label

sudo dmesg
sd 5:0:0:0: [sda] 7866368 512-byte logical blocks: (4.03 GB/3.75 GiB)

The [sda] gives me the information that my USB key is located at /dev/sda.

sudo fdisk -l /dev/sda
Disk /dev/sda: 3.75 GiB, 4027580416 bytes, 7866368 sectors
Disk model: Flash Disk
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes

Whether you have data or not, write random data inside to prepare for encryption.

First option

Shred will write random data (from /dev/urandom) 5 times to /dev/sda. You are sure that the storage is completely override.

sudo shred --verbose --iterations 5 --random-source /dev/urandom /dev/sda
shred: /dev/sda: pass 1/5 (random)...
shred: /dev/sda: pass 1/5 (random)...58MiB/3.8GiB 1%
[...]
shred: /dev/sda: pass 5/5 (random)...3.8GiB/3.8GiB 100%

Second option

More classical, with dd to copy random data (from /dev/urandom) to /dev/sda.

sudo dd if=/dev/urandom of=/dev/sda status=progress
7143936 bytes (7.1 MB, 6.8 MiB) copied, 1 s, 7.1 MB/s

Create a new partition table

sudo fdisk /dev/sda
Welcome to fdisk (util-linux 2.36).
Changes will remain in memory only, until you decide to write them.
Be careful before using the write command.

Device does not contain a recognized partition table.
Created a new DOS disklabel with disk identifier 0x1e7af207.

Command (m for help): o
Created a new DOS disklabel with disk identifier 0x78ed8d4c.

Command (m for help): w
The partition table has been altered.
Calling ioctl() to re-read partition table.
Syncing disks.

Create a new partition

Create a primary partition with a size of 25 MB.

sudo fdisk /dev/sda
Command (m for help): n
Partition type
   p   primary (0 primary, 0 extended, 4 free)
   e   extended (container for logical partitions)
Select (default p):

Using default response p.
Partition number (1-4, default 1):
First sector (2048-7866367, default 2048):
Last sector, +/-sectors or +/-size{K,M,G,T,P} (2048-7866367, default 7866367): +25M

Created a new partition 1 of type 'Linux' and of size 25 MiB.

Command (m for help): w
The partition table has been altered.
Calling ioctl() to re-read partition table.
Syncing disks.

Encrypt the partition

Choose a strong passphrase.

sudo cryptsetup luksFormat /dev/sda1

WARNING!
========
This will overwrite data on /dev/sda1 irrevocably.

Are you sure? (Type 'yes' in capital letters): YES
Enter passphrase for /dev/sda1:
Verify passphrase:

Mount the partition

By doing this, you map the encrypted partition to /dev/mapper/secret.

sudo cryptsetup open /dev/sda1 secret

Create a filesystem

The -L flag allows to set the volume label. Below I retrieve the date via date +%F (format: YYYY-). Don’t forget to prefix (date +%F) with $ if your are using bash…

sudo mkfs.ext4 /dev/mapper/secret -L gpg-(date +%F)
mke2fs 1.45.6 (20-Mar-2020)
Creating filesystem with 9216 1k blocks and 2304 inodes
Filesystem UUID: 7e52f8f9-3823-4845-9cfd-e308d00641c8
Superblock backups stored on blocks:
	8193

Allocating group tables: done
Writing inode tables: done
Creating journal (1024 blocks): done
Writing superblocks and filesystem accounting information: done

Mount the filesystem and copy the keyring

sudo mkdir /mnt/encrypted-storage
sudo mount /dev/mapper/secret /mnt/encrypted-storage
sudo cp -avi $GNUPGHOME /mnt/encrypted-storage
[...]
'/tmp/tmp.EOmP2zbviM/mastersub.key' -> '/mnt/encrypted-storage/tmp.EOmP2zbviM/mastersub.key'

Unmount, close and disconnect the encrypted volume

sudo umount /mnt/encrypted-storage
sudo cryptsetup close secret

Export public key

Without the public key, you will not be able to use GPG to encrypt, decrypt, nor sign messages.

Create a new partition

Create a primary partition with a size of 25 MB.

sudo fdisk /dev/sda
Command (m for help): n
Partition type
   p   primary (1 primary, 0 extended, 3 free)
   e   extended (container for logical partitions)
Select (default p):

Using default response p.
Partition number (2-4, default 2):
First sector (53248-7866367, default 53248):
Last sector, +/-sectors or +/-size{K,M,G,T,P} (53248-7866367, default 7866367): +25M

Created a new partition 2 of type 'Linux' and of size 25 MiB.

Command (m for help): w
The partition table has been altered.
Calling ioctl() to re-read partition table.
Syncing disks.

Create a filesystem

sudo mkfs.ext4 /dev/sda2
mke2fs 1.45.6 (20-Mar-2020)
Creating filesystem with 25600 1k blocks and 6400 inodes
Filesystem UUID: d17f360e-aab7-450f-94a4-55ea2d592dff
Superblock backups stored on blocks:
	8193, 24577

Allocating group tables: done
Writing inode tables: done
Creating journal (1024 blocks): done
Writing superblocks and filesystem accounting information: done

Mount the filesystem and copy the public key

sudo mkdir /mnt/public
sudo mount /dev/sda2 /mnt/public/
gpg --armor --export $KEYID | sudo tee /mnt/public/gpg-$KEYID-(date +%F).txt

Unmount and disconnect the volume

sudo umount /mnt/public

The first part is done. Now, we will see how to store OpenPGP keys on a YubiKey.