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

[sacrificial-spam-address at horizon.com]

Simon Josefsson <simon at josefsson.org> wrote:
> 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.

That paper deserves a longer reply, but even granting every claim it
makes, the only things it complains about are forward secrecy (is it
feasible to reproduce earlier /dev/*random outputs after capturing the
internal state of the pool from kernel memory?) and entropy estimation
(is there really as much seed entropy as /dev/random estimates?).

The latter is only relevant to /dev/random.  But more importantly,
neither complaint (nor any other claim anyone has ever made) questions
the ability of /dev/*random's output compression function to produce N
totally random bits if it truly has N bits of seed entropy.

That may be a bit subtle, so let me state it clearly: If there are
actually N bits of seed entropy in the /dev/urandom pool (even if
the kernel entropy estimator has computed a different incorrect
value), then a M-bit read from /dev/urandom will produce a uniformly
distributed min(N,M)-bit value.  (Minus some negligible epsilon due to
hash compression.)

In either case, if you want K bits worth of seed entropy for your PRNG,
it is completely and utterly pointless to read more than K bits from
/dev/urandom.  If N >= K, you will get K bits of entropy with a K-bit
read.  If N < K, you will not get more than N bits of entropy no
matter how much you read.

(If you're reading from /dev/random, then you are using the kernel's
entropy estimator and you can apply a derating factor to it.  But
that doesn't apply to reads from /dev/urandom.)

> 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.

The problem is that asking /dev/urandom for more seed bits than the
security rating of your PRNG is, to use Linus's phrase, "ugly and stupid".
And assuming that your PRNG is more than 256-bits secure is also stupid,
because computational complexity theory is not sufficiently developed to
make such assertions.  (And most cryptographers will tell you that even
256 bits is really pushing it.  We understand 64-bit security because
we've actually done 2^64-step computations.  We're pretty comfortable
extraolating to 128 bits, 192 bits involves increasing amounts of
handwaving, and 256 bits is frankly wishful thinking.)

So libgcrypt's seeding is "ugly and stupid" and is in desperate need of
fixing.  Reading more bits and distilling them down only works on physical
entropy sources, and /dev/urandom has already done that.  Doing it again
is a complete and total waste of time.  If there are only 64 bits of
entropy in /dev/urandom, then it doesn't matter whether you read 8 bytes,
8 kilobytes, or 8 gigabytes; there are only 2^64 possible outputs.

Like openssl, it should read 256 bits from /dev/urandom and stop.
There is zero benefit to asking for more.

(If you want confirmation, please ask someone you trust.  David Wagner
at Berkeley and Ian Goldberg at Waterloo are both pretty approachable.)

> 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).

Fair enough.  Are you saying that you prefer a patch to gnutls rather than
one to libgcrypt?