ietf-openpgp
[Top] [All Lists]

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

2019-10-15 12:25:24
I have been thinking on very similar lines after being prompted by Michael
Richardson. I don't have that mechanism specified in the draft yet but
already proposed a scheme to do exactly this sort of thing as part of UDF.

http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

The basic idea is to add a KeyGen UDF type (200) with an initial character
Z. So a key generation identifier will look something like:

ZAAA-DJUY-H7TF-SFLK-CWAW-TKC4-O5HQ

The breakdown I see is

Byte 0 = 200
Byte 1-2 = a 16 bit key type identifier
Byte 3-n = the KDF master secret.

I suggest using only 15 bits of the key type identifier giving 32K possible
2 byte keys and extension to 4 bytes should it prove necessary

So lets say the keyid above is 12 and that is for an Ed25519 key. To
derive the private key from that,

Private = KDF, ( UnBase32 (DJUY-H7TF-SFLK-CWAW-TKC4-O5HQ), UDF-Z-12, 256)

That is the master secret is whatever the binary blob part of that string
is, the kdf salt is  "UDF-Z-12" (or something unique) and we want 256 bits
of output. This obviously requires a bit more effort for RSA keys etc.

Note that since we are using a KDF, the UDF does not need to be as long as
the generated key. It only needs to be long enough to present a
sufficiently difficult work factor to prevent a brute force attack. So 256
bits is sufficient for an Ed 448 key.

This construction has some interesting security advantages that I haven't
fully mapped out yet. It enforces a rigid construction for a start. The
scope for the type of games Moti Yung likes to play are greatly reduced
because they are forced to work forward from a random value.


The advantages of building on UDF are

1) It is designed to be generic so someone can use the same key generator
for SSH, OpenPGP, S/MIME, their own stuff.

2) There are bindings for URIs and QR codes already defined.

3) We can make use of Shamir Secret sharing to split the key into 2/3 or
3/5 shares already defined.

4) There is a BOF on the MathMesh already planned for Singapore.

Besides using Shamir secrets for splitting a random key, we can use them
for generation.

So lets start off by generating two random shares: Everything after the
first two bytes is random noise:

Share 0: SAQG-A7BL-6YQ6-G5K3-HYKQ-I54D-VWHG-C
Share 1: SAQZ-2TRR-KQB6-BENB-CIKI-PBK6-72SX-G

We can now 'recover' the key:

Key:     EAR2-UJUY-H7TF-SFLK-CWAW-TKC4-O5HQ

We need at least as many seed shares as our quorum of course. In this case
it is 2. If we require more than 2 shares, we can generate the additional
shares in the normal fashion:

Share 2: SARN-UIBW-WHS5-3LPG-4YKA-VEZ2-J66I-K

Why is this useful? Well lets say you want to be really sure that your key
has randomness from more than one original source. This approach lets you
do it without recourse to the meta-cryptography used in Mesh device key
provisioning.


While the Mesh makes use of UDF, it is not necessary to implement the whole
of the Mesh just to use the UDF piece. But the Mesh does bring a lot more
to the table.

In particular, the Mesh provides a single point of management for all of
Alice's keys across all her devices. So if she loses her device or she has
it confiscated in an airport, she can shut down ALL her apps with a single
message to her Mesh Service.

The Mesh is also using some crypto that is not in the regular canon of
industry crypto like threshold cryptography and key combination. These
allow for much tighter control of crypto across devices. Using the Mesh to
manage her keys, Alice can prevent her phone being able to decrypt any of
her data while she is travelling through an airport and only re-enable
those capabilities under very specific conditions.


On Tue, Oct 15, 2019 at 8:16 AM Kai Engert <kaie(_at_)kuix(_dot_)de> wrote:

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

_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp

_______________________________________________
openpgp mailing list
openpgp(_at_)ietf(_dot_)org
https://www.ietf.org/mailman/listinfo/openpgp