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

From: Kai Engert <[email-masked]>
Date: Tue, 15 Oct 2019 14:16:31 +0200

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

---

From: Kai Engert <[email-masked]>
Date: Tue, 15 Oct 2019 14:23:32 +0200

> words, 3 bytes for the descriptor prefix and 12 bytes for the seed.

3 words and 12 words (not bytes)

---

From: Michael Richardson <[email-masked]>
Date: Tue, 15 Oct 2019 18:21:53 +0200

> - 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.

PHB's MMM offers a similar mechanism.
Might as well have a single solution.

See draft-hallambaker-mesh-* and 
    https://mailarchive.ietf.org/arch/msg/mathmesh/GF1d5X4F0eqAk6x7T9qQu6khAIw

    > 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

A secondary use is for keys that are generally kept offline.
Instead of bringing them back from the "cold storage", the key is just
renegerated each time from a printed piece of paper.   My original PGPv3
[email-masked] went through five kinds of media (5.25" floppy, 
3.5" floppy, CDROM, DVD, USB key...)... 

-- 
]               Never tell me the odds!                 | ipv6 mesh networks [ 
]   Michael Richardson, Sandelman Software Works        | network architect  [ 
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 15 Oct 2019 13:24:54 -0400

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 <[email-masked]> wrote:

> _______________________________________________
> openpgp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/openpgp
>

---

From: Jon Callas <[email-masked]>
Date: Tue, 15 Oct 2019 13:15:15 -0700

> I hope some of this message makes sense.

I think it makes sense. You're looking at having a way to seed a DRBG (PRNG), so that that seed can be used to deterministically generate a key, and that seed being reasonably small, and can be encoded in a way that's easy to store on paper as well as use for generating the same key later.

This sounds like a good idea, but as others have said, it's more general than OpenPGP. Really what you want is a standardized, loadable DRBG, and then that DRBG could be bolted into some OpenPGP implementation for key generation.

That latter part is software issue and really ought to be generalized beyond OpenPGP, and then some implementation of OpenPGP could have the feature of creating a key from such a loadable seed.

It sounds useful to some people, but outside the scope of OpenPGP documents, just as the design of other RNGs is beyond the scope of OpenPGP documents.

	Jon

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Wed, 16 Oct 2019 15:27:51 -0400

Thanks for writing this up, Kai!

>     Largest value possible is 4096, encoded as 127:

I'm not sure i see the value of any of the above fields for such a seed.
If they're needed for OpenPGP, i think they're incomplete (lacking key
creation timestamp at least) -- but i don't think they're needed.

For initial secret key generation, these parameters -- key algo, key
size, creation timestamp, etc -- can be made at key creation time and
don't need to be recorded in the phrase.

For secret key recovery, presumably the user has the OpenPGP certificate
("transferable public key") available to them already, which contains
all the above information already.  I'd imagine that the recovery
process in the OpenPGP context would take the certificate and the
mnemonic, deriving all of the above fields from the certificate.

I think there are at least three ideas in this e-mail:

 a) The general idea of a loadable seed to a well-defined, well-known
    DRBG.  This requires declaring the size of the seed, and choosing
    the DRBG algorithm.  This might also include "stretching"
    (e.g. argon2) needed to make the seed resistant to large-scale
    automated attack when parts of the seed are accidentally revealed
    (e.g. imagine muttering memorized words/phrases while sleeping).

 b) The (bi-directional?) mapping between that seed and a string that
    humans can handle (record easily? commit to and recall from memory?
    replay without ambiguity?).  This requires defining the goals of the
    mapping (is it for recovery? daily use? verification?), and a
    (language-specific?)  vocabulary list that offers the relevant
    properties.  (this sounds a little like p≡p's "Trust Words"
    proposal, except that that proposal isn't bi-directional and the
    vocabulary lists don't appear to have any analysis for dealing with
    phonetic or orthographic ambiguity)

 c) The use of such a DRBG to generate OpenPGP secret key material,
    given baseline parameters (or deriving those parameters from a
    certificate, in the case of recovery)

I'm not personally very convinced about this general approach -- it's
the equivalent of an unchangeable password that you've committed to
publicly (so anyone who thinks they have a good guess at your password
can verify it offline against your public key fingerprint).

I know it's something that some folks are excited about, though, and
part (c) might be in-scope for this mailing list, particularly the
OpenPGP-specific parameters.  I'd encourage anyone excited about this
work to try to write down how to do (c) alone in a way that could be
interoperably implemented.

It sounds like Phil's UDF draft outlines the general idea for raw
cryptographic objects, but doesn't have a mechanism specified yet, or a
mapping between them and OpenPGP.

     --dkg

---

From: Kai Engert <[email-masked]>
Date: Thu, 17 Oct 2019 11:01:58 +0200

> creation timestamp at least) -- but i don't think they're needed.

We could add the creation timestamp. To save bits, we could introduce a
new epoch, that starts in october 2019. This new recovery mechanism
wouldn't support older keys.

With a 33 bit unsigned integer, we get 272 years. To compute, calculate
the regular 64bit unix epoch (since 1970). Then substract the new epoch
start timestamp (e.g. 1572000000 for 2019-10-25). Encode that as a 33
bit unsigned integer. Will work until year 2272.

> mnemonic, deriving all of the above fields from the certificate.

What about a user who owns just a single computer, it breaks, and
they've lost all their files, and only the IMAP mail archive is left?

Maybe the user never uploaded their key to a key server, there's no backup.

Maybe the user has an email with the attached public key somewhere, but
can it be found reliably?

If we don't record any key information in the Mnemonic, the user must
perform some bootstrap action, prior to being able to regenerate the key:

- look at existing encrypted email, an extract the key ID, to understand
which key needs to be recovered. But that might be a subkey ID, so
further searching is required to identify the ID of the master key?

- search through existing email, in the hope that the full public key is
attached somewhere, either regular attachment, or maybe an outgoing
autocrypt header (only if user's client had autocrypt headers enabled).
Maybe there's no such email?

- contact one of the correspondents, and ask them to send the public key
back. Maybe the user doesn't want to do that?

It might be useful if recovery didn't depend on the above.

> publicly

Why do you consider it equivalent, if the seed was randomly generated,
and the list of words isn't influenced by the user?

Thanks
Kai

---

From: Kai Engert <[email-masked]>
Date: Thu, 17 Oct 2019 11:13:02 +0200

On 15.10.19 22:15, Jon Callas wrote:
> This sounds like a good idea, but as others have said, it's more general than OpenPGP.

Agreed. And it seems to me that BIP 0039 already specifies a generic way
to record a seed as a Mnemonic, that we could reuse. However, I think
it's incomplete.

> Really what you want is a standardized, loadable DRBG, and then that DRBG could be bolted into some OpenPGP implementation for key generation.
> 

The seed is insufficient for recreating the OpenPGP key. We need
additional meta information.

The suggestion is to specify the meta information that is required to
recreate the OpenPGP key. In Daniel's response, he mentioned that as
part (c).

It seems that part (c) would contain information that is specific to
OpenPGP.

Daniel pointed out that I had missed the "key creation time" in my
enumeration.

So in addition to the seed, if we want a recovery mechanism that doesn't
require the OpenPGP transferrable public key to be readily available,
we'd have to combine:
- the general seed
- OpenPGP key creation time
- OpenPGP key algo
- OpenPGP key key size
- ...?

Kai

---

From: Kai Engert <[email-masked]>
Date: Thu, 17 Oct 2019 11:26:45 +0200

On 17.10.19 11:20, Peter Todd wrote:
> Do we really need something that doesn't require the public key? Those are
> fairly widely distributed; when would you be unable to get a copy yet still
> need to recover the secret key?

Please see my other response to Daniel, which illustrates a scenario in
which a user might no longer have that available.

The scenario is an email application, which targets users that only use
end-to-end-encryption because it's readily and easily available in an
email application they're using, who aren't diligent with their files,
but still don't want to lose their archive of old (encrypted) emails.

Kai

---

From: Michael Richardson <[email-masked]>
Date: Thu, 17 Oct 2019 12:13:20 +0200

> mnemonic, deriving all of the above fields from the certificate.

I think that this makes sense.
And it's already signed :-)

    > can verify it offline against your public key fingerprint).

That's a good point; however sometimes perfect is the enemy of good enough,
and that has been the case for encrypted email for a long time.

A recoverable key would be an option, not a requirement.

{An interesting (mathematical, density of primes) question would be whether
one would be able to determine from looking at the public key whether it was
recoverable or not.  That is, can one recognize some pattern in the expanded
DRBG. It might still be statistically secure, yet since the amount of entropy
in the key is less than the entropy in the input, it might leave a pattern}

--
Michael Richardson <[email-masked]>, Sandelman Software Works
 -= IPv6 IoT consulting =-

---

From: Michael Richardson <[email-masked]>
Date: Thu, 17 Oct 2019 12:21:27 +0200

> further searching is required to identify the ID of the master key?

Maybe they can't get access to their IMAP folder until they decrypt their
backup, so I think that this is a more reasonable concern.

But, I think you have over-constrained the problem space.

    > and the list of words isn't influenced by the user?

It's equivalent to a system generated password.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Thu, 17 Oct 2019 13:42:30 -0400

> A recoverable key would be an option, not a requirement.

yep, that's why i'm trying to help think this through, even though i'm
not particularly excited about it. :)

> in the key is less than the entropy in the input, it might leave a pattern}

Can you give an example of this?  I haven't tried to prove this, but i
think if the generated public key (whether a curve25519 point or an RSA
modulus) is distinguishable from other public keys, there is a strong
argument to be made that either the DRBG or the secret key derivation
mechanism is deeply flawed.

       --dkg

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 17 Oct 2019 21:40:14 -0400

On Tue, Oct 15, 2019 at 4:15 PM Jon Callas <joncallas=
[email-masked]> wrote:

> I think it makes sense. You're looking at having a way to seed a DRBG
> (PRNG), so that that seed can be used to deterministically generate a key,
> and that seed being reasonably small, and can be encoded in a way that's
> easy to store on paper as well as use for generating the same key later.
>
> This sounds like a good idea, but as others have said, it's more general
> than OpenPGP. Really what you want is a standardized, loadable DRBG, and
> then that DRBG could be bolted into some OpenPGP implementation for key
> generation.
>
> That latter part is software issue and really ought to be generalized
> beyond OpenPGP, and then some implementation of OpenPGP could have the
> feature of creating a key from such a loadable seed.
>
> It sounds useful to some people, but outside the scope of OpenPGP
> documents, just as the design of other RNGs is beyond the scope of OpenPGP
> documents.
>

IETF already has such a function HMAC-KDF. RFC 5869.

The current UDF document does not have the text. I am just finishing up the
code and should have a new draft out tomorrow with the text.

---

From: Michael Richardson <[email-masked]>
Date: Fri, 18 Oct 2019 08:54:12 +0200

>> {An interesting (mathematical, density of primes) question would be
    >> whether one would be able to determine from looking at the public key
    >> whether it was recoverable or not.  That is, can one recognize some
    >> pattern in the expanded DRBG. It might still be statistically secure,
    >> yet since the amount of entropy in the key is less than the entropy in
    >> the input, it might leave a pattern}

    > mechanism is deeply flawed.

If I could prove such a thing then I'd have a Fields Medal for having
discovered something new and interesting about the density of primes :-)

If the input to our KDF is 120 bits and the output is 256 bits,
then there must be a bunch of numbers that we can't derive from the KDF.
But, as PHB says, 2^120 is a big enough work factor that it's okay.
(5bits * 5 groups * 4 characters/group = 120)

For ECDSA, any number will do, AFAIK.
{When producing numbers RSA, I think we have to start with the random number
and then search deterministically for a suitable prime.  I was more thinking
that this process might leave detectable traces}

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 18 Oct 2019 09:14:09 -0400

> that this process might leave detectable traces}

For RSA-2048, it is arguable that 112 bits are enough as that is the work
factor of the key according to the best known attack.

Reuse of KDF in the generation function was chosen since it is already
examined and widely used so if it is hosed, the system is already
compromised. We are not introducing a new vulnerability.

As for the proof part... When I first started thinking about this, it was
because right now my specifications generate new keypairs every time they
are generated and since parts III and IV try to reference the keys
generated in part I... this is confusing. So I began thinking of this as a
hack. But as I have continued, I have started to think that it is actually
a much better way to generate keys.

A big problem testing cryptographic systems is that any system that has a
hidden secret can use it to conceal a side channel attack. (See Moti Yung's
kleptography schemes.) What I really like about these deterministic schemes
is that they allow the random component of the system to be isolated.

---

From: Marcus Brinkmann <[email-masked]>
Date: Fri, 18 Oct 2019 15:37:30 +0200

> mechanism is deeply flawed.

Svenda, et al: "The Million-Key Question – Investigating the Origins of
RSA Public Keys", USENIX Security Symposium 2016.

https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_svenda.pdf

"We analysed over 60 million freshly generated key pairs from 22 open-
and closed-source libraries and from 16 different smartcards, revealing
significant leakage."

Thanks,
Marcus

-- 
Dipl.-Math. Marcus Brinkmann

Lehrstuhl für Netz- und Datensicherheit
Ruhr Universität Bochum
Universitätsstr. 150, Geb. ID 2/461
D-44780 Bochum

Telefon: +49 (0) 234 / 32-25030
http://www.nds.rub.de/chair/people/mbrinkmann

---

From: "brian m. carlson" <[email-masked]>
Date: Fri, 18 Oct 2019 22:51:00 +0000

> - OpenPGP key creation time

In addition, you require a deterministic key generation process.  This
is straightforward for EC keys (generate a random byte string of the
appropriate length as the secret key), but it's trickier for RSA and DSA
keys.

If the random number you pick for p is not prime, should you pick
another random one?  Increase it by two and try again?  What random
numbers are you going to pick for Miller-Rabin and how do you extract
those from the DRBG?  How many times do you iterate Miller-Rabin?

For DSA keys, how do you pick the generator?  For RSA keys, what values
of e do you allow?  If p is not less than q, do you swap them, or do you
generate a new q?

And yes, the Miller-Rabin numbers matter, because it's a probabilistic
technique, and it is possible to generate keys based off pseudoprimes,
which you would want to be able to reproduce, even if they are insecure.
Or you'd have to tell people that the process might produce a totally
different key if their original one was not really secure.

In order to get this right for non-EC keys, you really need a separate
document that defines things down the details, much like RFC 6979 does
for deterministic signatures.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 18 Oct 2019 23:40:03 -0400

Someone just said we need a spec. Here is a spec:
https://www.ietf.org/id/draft-hallambaker-mesh-udf-07.txt

It is in the new format which is intended to be read as HTML. Until the
tools catch up, you can read it here:
http://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

The draft does not specify the value of e which it should but I am pretty
sure we have standardized on 65537. I see no reference to p being greater
than q and it is a mystery to me why we would care when the RSA parameters
are the modulus and the private exponent d. Knowledge of p and q is only
used to determine d, they are not req

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Fri, 18 Oct 2019 23:50:57 -0400

Carrying on after gmail sent the message before I wanted to...

> used to determine d, they are not req

As I was saying, I am not aware of a requirement to know p or q after d is
calculated let alone sort them. There are requirements to do with co-primes
being of particular lengths. But NIST states these are optional so I am
thinking of simply saying that to generate a key pair you use the
derivation mechanism specified until you arrive at a pair you like.

Given the density of prime numbers and given that the smallest keys we are
using are 1024 bits, the work factor for any schemes based on guessing the
prime parameters is going to be above 2^1000 which is more than a google.

I did not bother with DSA. But that could be added. It has serious problems
at this point and is probably just better deprecated.

---

From: "brian m. carlson" <[email-masked]>
Date: Sat, 19 Oct 2019 04:40:08 +0000

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

This doesn't specify any method of primality testing which means
different implementations can produce different values[0] (and is
therefore not deterministic), unless you literally interpret the text
"smallest prime integer" as requiring an actual prime.  That could be
implemented by using the Miller test instead of Miller-Rabin, but that
would be much, much slower.

In this particular case, the approach to invalid keys (where p and q are
unsuitable) is "try again with a different seed", which is probably okay
in terms of RSA, because the number of retries necessary will be low.

It also doesn't specify DSA keys, which, while uncommon, are still a
part of the spec.  The "try again" approach will probably be a little
more difficult here.

> used to determine d, they are not req

The OpenPGP secret key contains u, the multiplicative inverse of p mod
q, which is used along with p and q for the Chinese Remainder Theorem.
RFC 4880 specifically mentions that p must be less than q, which is
required for u to exist.  (This is backwards from most other specs,
which require the opposite and define u as the multiplicative inverse of
q mod p.)

It is, of course, possible to retain only n and d and eat the
performance penalty, but that would not produce a valid OpenPGP secret
key.

[0] Yes, people should pick a suitable number of iterations for
primality testing, but there are people that pick 1 iteration for
PBKDF2, which is a demonstration of why we can't have nice things.  We
actually have to tell people how to write things in an interoperable
and secure way.
-- 
brian m. carlson: Houston, Texas, US
OpenPGP: https://keybase.io/bk2204

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 19 Oct 2019 01:44:37 -0400

> would be much, much slower.

I am trying to work out what the necessary criteria should be. It is
certainly something to think about.

If someone is using a random primality test with 128 rounds, there is an
infinitesimal chance it isn't a prime, 2^-128.

The work factor for picking such a prime is 2^128 so it should not happen
by accident either.

Right now, my feeling is that if someone is going to use a broken primality
test, the risk of not recovering their key might be the least of their
concerns...

I think I might have a solution though...

> in terms of RSA, because the number of retries necessary will be low.

The only problem with that approach is that it prevents generating RSA keys
from shared secrets...

> part of the spec.  The "try again" approach will probably be a little

I can add them. Which DSA key sizes are still relevant?

> which require the opposite and define u as the multiplicative inverse of

OK, so I will rework that part and merely specify that it outputs two
primes X and Y which implementations are free to use for either p or q as
they please.

So long as the resulting value of d is the same...

> actually have to tell people how to write things in an interoperable

Absolutely. And there are folk who have calculated their RSA parameters by
setting the upper n bits of their RSA modulus to be the encrypted value of
their seed value, choosing a random p and then working out what their q
should be. Then sold the result to a foreign adversary...

There are two possible situations.

1) User generates a strong key, recovery fails on a bad implementation with
insufficient testing.

2) User generates a broken key due to insufficient testing, cannot recover
it.

The first is the least worst. We can still recover the key on a good
implementation.

The second is trickier. But since we have specified the search pattern, we
can still recover the key provided that we know the fingerprint.

In either case, we can blame and shame the bad implementation!

---

From: Heiko Stamer <[email-masked]>
Date: Sat, 19 Oct 2019 13:05:38 +0200

> I can add them. Which DSA key sizes are still relevant?

2048/256 and 3072/256 (cf. FIPS 186-4)

--
Heiko

---

From: Michael Richardson <[email-masked]>
Date: Sat, 19 Oct 2019 09:01:45 -0400

> at this point and is probably just better deprecated.

I think that you are right to ignore DSA.

---

From: Michael Richardson <[email-masked]>
Date: Sat, 19 Oct 2019 09:04:08 -0400

> test, the risk of not recovering their key might be the least of their

Yes, but the issue is bugs.

If someone fixes (or introduces...) a bug in a primality test, then I might
recover a different key.  This doesn't happen if I generate and key the
private key.

If I lose my system and I install a new system, the odds of new/patched
software compared to when I first generated is high.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sat, 19 Oct 2019 14:22:54 -0400

OK so I have not implemented DSA but it turns out that it the spec mandates
the entire process:
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf

The main consequence of DSA is that it mandates the entire process
including prime generation *and* provides a mechanism for validation of all
the parameters.

This discussion now has me thinking that we should have been validating
parameters for RSA before importing them into an application all along.

> software compared to when I first generated is high.

Absolutely!

And I can provide a recovery mechanism that does just that. So the set of
requirements I see are:

A) Generation/Import of keypairs meeting BCP criteria of NIST and IETF from
fingerprint
B) Identification of faulty implementations
C) Recovery of mis-generated key pairs.
D) Verifiable generation processes with separation of duties.

It is not necessary for every implementation to do all of these. An SSH /
OpenPGP / S/MIME app only needs to implement A and allow B and only if it
actually implements keygen at all.

I can meet the full set of requirements with the Mesh management tool. This
is open source, MIT license. The code for the UDF stuff is not complicated
though. Concentrating all the key management functions in a single app
allows them to be done better and more comprehensively.

*A) Generate*

The commands for generating, exporting and importing a key from the CLI
would probably look something like the following. Since I am thinking of
the general case, the key fingerprints used as UDF content digests rather
than OpenPGP but this is largely because it was easier to cut and paste
from my docs rather than find another.

> myapp generate [email-masked] --udf
Generated key:  MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
Ready.
> myapp export [email-masked] --udf
ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
Ready.
> myapp import [email-masked]
--udf=ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
Ready.

*B) Detecting a faulty key*

myapp import [email-masked]
--udf=ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
--check=MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-ZZZZ
Error-ABEND-0243: Recovered key did not match

We can get a better test of the generated key checking with a different
application

mesh verify ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
WARNING: Key does not match

*C) Recovery of mis-generated key pairs*

Recovery of a misgenerated key pair is easiest if we know the modulus. In
that case we can generate the starting points for the primality search for
either P or Q and then just do trial divisions until we get a exact match.
So the first thing the mesh recovery tool would do is to attempt to obtain
the public key parameters from the fingerprint.

If we only have the fingerprint, we have to assume at least one of the
parameters is prime, generate a trial key for each prime candidate in the
search and test to see if it matches the fingerprint:
> mesh recover ZAEA-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L-V5Y
MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4
WARNING: Key recovered is NOT SECURE
Primality testing failed.
Recovered key written to MB5S-R4AJ-3FBT-7NHO-T26Z-2E6Y-WFH4.p12

*D) Verifiable generation processes with separation of duties. *

NB: This is not the sort of process I see many individuals performing for
themselves. But it is exactly the sort of procedure I might want to use as
the basis for separation of duties in a key ceremony type situation. Every
one of the input shares affects every bit of the output. The splitting (but
not the generated key!) is information theoretic secure.

UDF gives us the ability to use Shamir secret sharing to split a secret. We
can also use this in reverse to create a secret from random contributions
generated on separate machines.

So let us imagine we begin by generating the following nonce values on
independent machines.
NAQC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I
NAED-CRXH-IASE-5ZYS-ZS2D-PQT4-6O6P-G
NCRB-6YXF-R5RA-ZFGY-W6TB-4H6Q-3O6Y-E

We can combine them to form a single secret for a specific purpose. Since
we need to encode some information into the first three bytes of the result
and we have one type code, we have 32 bits fixed in the output:

ZAAQ-AWMQ-6Z4O-RRMM-Y72J-CGWI-ZC7L

We can now generate a set of Shamir secrets that closely resemble but are
not exactly the same as our nonce inputs:

SAEC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I
SAED-CRXH-IASE-5ZYS-ZS2D-PQT4-6O6P-G
SAMB-R3XF-R5RA-ZFGY-W6TB-4H6Q-3O6Y-E

Note that only the first three characters of the first two shares and the
first six characters of the last changed here.

We can verify that the above secrets combine to create ZAAQ-AWMQ-... and we
can even generate additional shares if we so choose. We can't change the
quorum unless we reshare the secret.

So now imagine we are generating these from QR codes being read by a
camera. We run the scheme some number of times with full observability.
Then we cover one of the inputs so the observers can only see the other
three and run the system some randomly chosen number of times with a
different input covered on each round.

---

From: Michael Richardson <[email-masked]>
Date: Sun, 20 Oct 2019 13:18:45 -0400

> from my docs rather than find another.

Being able to split off the private key generation for PGP, SSH, certificates,
etc. might be a serious boon to the ecosystem I think.

    > not the generated key!) is information theoretic secure.

So, we don't do generate keys for our home networks today.  But in the future
we ought to, and we ought to be splitting it across a bunch of family
members, neighbours, etc.   Being able to leave a spare key (with some
limited authority) with your trusted neighbour would remain important in the
future.

    > NAQC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I
->

    > SAEC-GKXI-6DTJ-COKM-4HBF-CZJJ-BO6G-I

Yes, is see :-)

    > different input covered on each round.

Interesting.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Sun, 20 Oct 2019 15:10:37 -0400

> etc. might be a serious boon to the ecosystem I think.

I am planning to layer in ACME support in the mesh key management tool. So
it will be able to automate generation and distribution of the certs for
all your embedded devices.

This will use meta-cryptography. Which means that once the device has been
connected up to the management system, it never needs to do additional
keygen. The key presented to the CA is the composite of the device key and
the cert manager key.

Centralizing key management in one tool works both ways. It allows people
who are managing their SSH keys with the tool can also add PGP easily.