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

[Phillip Hallam-Baker <[e-mail]>]

On Sat, Oct 19, 2019 at 12:40 AM brian m. carlson <
[e-mail]> wrote:

> On 2019-10-19 at 03:40:03, Phillip Hallam-Baker wrote:
> > 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
>
> 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.
>

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

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


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

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

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

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

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

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!