excessive usage of /dev/random?

[Daniel Kahn Gillmor]

On Fri 2015-05-01 15:52:13 -0400, Robert J. Hansen wrote:
>> Drawing ~300 bytes from /dev/random to create a ~2048 bit keypair
>> seems entirely reasonable.
>
> I had a response to this that I thought was a neat digression into why
> this may not be a reasonable assumption: by the end of it I realized I'd
> just shown that ultimately it may be reasonable, too.  For that reason
> I'm not sharing it, because ultimately it amounted to no contribution at
> all.
>
> But if anyone wants to see a high school math overview of large number
> theory and what it tells us about asymmetric key generation and how to
> break asymmetric keys, email me *OFF-LIST* and I'll share it.  :)


On Fri 2015-05-01 17:37:26 -0400, Peter Gutmann wrote:
> Werner Koch <wk at gnupg.org> writes:
>
>>300 bytes are only 2400 bit which is sufficient for a 2048 bit RSA key. For a
>>4096 bit RSA key, which many people started to use, this is not sufficient.
>
> It should be plenty.  Cryptographic numerology (http://www.keylength.com/)
> tells us that a 2048-bit RSA key needs about 103 bits of entropy, and a 4096
> bit key needs about 142 bits (with a bit of variation depending on whose
> numerology you're using).  So take 150 bits of RNG output, feed it into a PRF,
> and you're done.

We now have two apparently contrary assertions made to gnupg-devel about
what the right/necessary thing to do is in this circumstance.

One assertion (from Robert J. Hansen) implies that a "high school math
overview of large number theory" suggests that it may well be reasonable
to require 2400 bits of entropy to generate a 2048-bit RSA key.

The other assertion (From Peter Gutmann) says that it's not necessary
(with a sarcastic allusion to "numerology"), and seems to roughly echo
the perspective found in random(4), while citing (indirectly) several
major surveys of cryptographic strength.

Robert, i know you might think this is "cluttering" the list, but please
show your work if you think it invalidates Peter's assertion.  I think
this dicsussion is clearly relevant to the development of gpg, even if
the result of the discussion is a conensus to keep the current behavior.

Peter, if your "numerology" remark is actually ironic (that is, if you
do not believe the literal conclusion you've drawn but are instead
critiquing what you see as bogus equivalences between classes of
cryptographic algorithms), could you please clarify that?  Sorry for
having to ask...


My basic understanding of the argument from random(4) as applied to
asymmetric key generation for integer factorization, DLOG, and related
problems is this:

 0) the best attacks we know about for this class of problems are much
    cheaper than a brute force search of the entire keyspace.  The cost
    to break a 2048-bit RSA key is a bit more than 2^100 "operations"
    (this rough equivalence estimate is what Peter calls "numerology").

 1) key generation routines for these problems need an unpredictable
    source of entropy with which to search the space of possible values
    to produce a proper secret key.

 2) we can produce an arbitrary amount of unpredictable data from a
    CSPRNG seeded with 256 bits of entropy.  If the CSPRNG behaves
    according to expectations, an attacker can guess at this pool (where
    2^x guesses cover x bits of the initial seed entropy) but if they
    don't stumble across the exact seed in that search, they won't be
    able to use this to learn anything about the actual key.

 3) An attacker capable of searching a large amount of the seed space
    (covering 100 bits of the seed space should cost about 2^100
    "operations") has enough compute power to instead mount one of the
    typical attacks against the underlying asymmetric problem, since
    it's the same cost.

One possible hole in this argument (that i can think of) would be if
there were some sort of "meet in the middle" attack, where with
knowledge of the CSPRNG and the secret key search strategy, an attacker
could combine the speedups of the traditional attack with a
somehow-constrained search of the initial seed entropy to mount a more
computationally effective attack than either attack individually.

I have no idea what this kind of combined attack would look like; i
certainly don't know whether it exists or not.

If other folks think this discussion is seriously off-topic here, could
you suggest a preferred place for it?

Regards,

  --dkg