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

[sacrificial-spam-address at horizon.com]

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.