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

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

On Fri, Oct 18, 2019 at 2:53 AM Michael Richardson <[e-mail]> wrote:

>
> Daniel Kahn Gillmor <[e-mail]> wrote:
>     > yep, that's why i'm trying to help think this through, even though
> i'm
>     > not particularly excited about it. :)
>
>     >> {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}
>
>     > 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.
>
> 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}
>

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.