[Pkg-gnutls-maint] Bug#475168: Bug#475168: Bug#475168: Bug#475168: certtool --generate-dh-params is ridiculously wasteful of entropy

[Simon Josefsson]

sacrificial-spam-address at horizon.com writes:

> Marc Haber <mh+debian-packages at zugschlus.de> wrote:
>
>> On Thu, Apr 10, 2008 at 12:09:47PM -0400, sacrificial-spam-address at horizon.com wrote:
>>> Yes, /dev/urandom is itself a PRNG,
>>
>> That's actually wrong. /dev/urandom will first deplete the kernel
>> entropy pool and will ony fall back to a PRNG when there is no more
>> true entropy available and where /dev/random would block instead.
>>
>> This is clearly documented in random(4).
>
> I have sent a more detailed explanation privately, but no, what I wrote
> is correct and I believe if you re-read the random(4) man page more
> carefully, you will see that it agrees.  (As does drivers/char/random.c.)
>
> The phrase "fall back" implies that /dev/urandom operates in two different
> modes, which is extremely misleading.  /dev/random and /dev/urandom
> are identical cryptographic PRNGs, work in exactly the same way, and
> under normal circumstances produce the same output.  The difference is
> that /dev/random estimates the amount of entropy in its seed sources,
> and refuses to deliver more output than it has input entropy.  Thus,
> someone observing its output can never reach the unicity distance (q.v.),
> and cryptanalysis is impossible even assuming an attacker with infinite
> computational power.
>
> /dev/urandom, on the other hand, does not check for "entropy underrun" and
> will produce more output than it has input.  Although the cryptographic
> PRNG is extremely robust and cryptanalysis is spectacularly unlikely,
> enough output is available that it is theoretically possible for an
> attacker with infinite computational power to figure out its internal
> state and thus reconstruct earlier outputs or predict later ones.
>
> Put another way, /dev/urandom will produce results that are as close
> to perfect as possible.  /dev/random does exactly the same thing,
> but first blocks until perfection is possible.

The Linux RNG have some issues, see <http://eprint.iacr.org/2006/086>.
Libgcrypt's estimates of the quality of the /dev/*random data is
pessimistic.

However, I think libgcrypt's design here doesn't fit GnuTLS's needs
well.  The problem is that libgcrypt needs to seed its internal
randomness pool before it begins.  This is why it is reading 3kb of
data.  One solution is for application to have a seed file, but I would
prefer if the crypto library that GnuTLS uses would take care of that.
Changing each and every application that uses GnuTLS to use a seeds file
is not a good design, IMHO.

Possibly gnutls should implement an internal PRNG, since neither
libgcrypt or the kernel's RNG APIs appear to be sufficient.  Patches are
always welcome (if you transfer the copyright on it to the FSF).

/Simon