[openpgp] Deriving an OpenPGP secret key from a human readable seed

[Kai Engert <[e-mail]>]

Today, saving a backup of an OpenPGP secret key usually requires storing
a file.

It could be useful to standardize an an additional recovery mechanism,
that doesn't require the secure storage of a file, but is based on a
list of words written to paper.

The high level idea is:

- key generation requires a source of entropy

- instead of using the entropy directly, the entropy could
  be used to seed a CSPRNG (like HMAC_DRBG), which is then used
  to obtain the random data that is needed for key generation.

- the entropy, plus any meta data required to generate the key,
  could be encoded as a list of words, which the user can write down.

- at a later time, the user could recover by using OpenPGP key
  generation software that supports this recovery mechanism,
  could provide the word list, which is decoded to obtain the original
  entropy bits.

- after creating the initial key, if additional keys need to be
  generated (e.g. a subkey), the CSPRNG is used to fetch all additional
  random numbers that are required.

During the OpenPGP summit last weekend it was mentioned that having this
kind of mechanism available could be useful, without going into detail.

Tobias Müller pointed me to an existing implementation of a similar idea
for creating OpenPGP keys : https://github.com/skeeto/passphrase2pgp

A definition of such an approach exists for the kind of private keys
that are used in the Bitcoin world, and IIUC several applications
implement it:
https://en.bitcoin.it/wiki/BIP_0039

(For creating additional child keys, an additional standard exists for
creating them, just for completeness, I don't know (yet) if the OpenPGP
mechanism might require (or could use) something similar for sub keys:
https://en.bitcoin.it/wiki/BIP_0032 )

Would you be interested to discuss how to standardize such a recovery
mechanism, and would you be interested to implement it in your applications?

Besides the raw entropy, what other meta information would we have to be
included, to ensure that key generation can be repeated?

I see the primary purpose for this recovery mechanism as desaster recovery:
- ensure the recovered primary key can be used to decrypt an
  archive of old data, like the encrypted emails in a sent folder
- allow the use of the recovered primary key to create a revocation
  statement

If the guts of the BIP_0039 specification is considered equivalent to
the needs of a mechanism for OpenPGP secret keys, maybe it could be a
useful shortcut to use the same approach.

It uses lists with 2048 words, and encodes each word as 11 bits.
A seed of 128 bits with a checksum of 4 bits is encoded into 12 words.

Potentially the metadata required to encode a public key could be
encoded into additional words.

Here's a result of some initial brainstorming, but I'm unsure if I've
identified all the meta information that would be necessary to repeat
the key generation, but as a starting point for discussion, we could
encode the following meta/descriptor information into 33 bits, which
could then be encoded into three additional words.

1 bit
    Version of this descriptor prefix, always 0.

7 bits
    Number of entropy bytes that will be encoded as a mnemonic.
    Encoded as a multiple of 32 minus 1.
    Smallest value possible is 32, encoded as 0: (0 + 1) * 32 = 32
    Largest value possible is 4096, encoded as 127:
      ((127 + 1) * 32) = 4096
    (Maybe 4096 is unnecessarily large, and we could use a smaller
     amount of bits for this.)

7 bits
    Identifier of the public key algorithm, as defined in RFC 4880
    section 9.1
    (Assumption that this implies the usual associated sub key
     algorithm. If not possible, we'd need additional bits to
     encode the sub key algorithm.)

18 bits
    Key size plus 1
    Smallest value possible, encoded as 0: 1
    Largest value possible, encoded as 262143: 262144
    (Maybe again that's unnecessarily large and we could use the
     bits for something else.)

A full recovery mnemonic based on a 128 bit seed could consist of 15
words, 3 bytes for the descriptor prefix and 12 bytes for the seed.

I hope some of this message makes sense.

Regards
Kai