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

[Michael Richardson <[e-mail]>]

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}

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