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

[Simon Josefsson]

sacrificial-spam-address at horizon.com writes:

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

Why's that?  If the entropy estimation are wrong, you may have too
little or no entropy.  /dev/urandom can't give you more entropy than
/dev/random in that case.

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

Right, although this is irrelevant if the seed doesn't contain
sufficient entropy.  If the attacker can guess (or exhaustively try) all
the N bits of seed entropy, using it as a seed for a PRNG won't improve
things.

However, my main concern with Linux's /dev/urandom is that it is too
slow, not that the entropy estimate may be wrong.  I don't see why it
couldn't be a fast PRNG with good properties (forward secrecy) seeded by
a continuously refreshed strong seed, and that reading GB's of data from
/dev/urandom would not deplete the /dev/random entropy pool.  This would
help 'dd if=/dev/urandom of=/dev/hda' as well.

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

I'm concerned that the approach could be weak -- the quality of data
from /dev/urandom can be low if your system was just rebooted, and no
entropy has been gathered yet.  This is especially true for embedded
systems.  As it happens, GnuTLS could be involved in sending email early
in the boot process, so this is a practical scenario.

A seeds file would help here, and has been the suggestion from Werner.
If certtool used a libgcrypt seeds file, I believe it would have solved
your problem as well.

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

I've been in a few discussions with David about /dev/random, for example
<http://thread.gmane.org/gmane.comp.encryption.general/11397/focus=11456>,
and I haven't noticed that we had any different opinions about this.

I don't think there is any research problem here, it is a matter of
applying old and known techniques in a good way, which is an engineering
assignment.

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

Yes, that could be discussed.  This problem is really in libgcrypt, so
the best would be if you were successful in fixing this problem at the
root.  Alternatively, work on improving /dev/urandom in Linux so that
GnuTLS can read from it directly and use it as the PRNG instead of
libgcrypt.  Until any of that materialize, I would certainly review and
consider patches to gnutls.

However, this problem has been brought up many times before (see the
BTS, btw, this bug should probably be merged with the other bugs) and
libgcrypt doesn't seem to provide a good interface yet.  The development
series of GnuTLS allows applications to replace the RNG code used, and
could thus use something else instead.

A patch against gnutls that implement a strong PRNG seeded by reading
256 bits or so from a file would be useful.  People could point it to
/dev/random, /dev/urandom or to a local seeds file if they want.

/Simon