[Cryptography] /dev/random has issues

[John Denker]

Here is an experiment you can do, if you have a Linux system:
  cat /proc/sys/kernel/random/entropy_avail

I predict that it is likely to be a smallish number, less than 192
bits, not enough to cut a PGP key.  This seems to conflict with
the stated purpose of having /dev/random, and with the purpose
of having buffers within the device.

On 10/17/2013 06:08 AM, Theodore Ts'o wrote:
> using a Yarrow-like approach,

I find the current version of /dev/random to be partly yarrow-like 
and partly not.  It is yarrow-like in the sense that it performs 
updates in batches, with a substantial minimum batch-size. It 
is non-yarrow-like in that it presents far too much load on the 
upstream source of entropy.

=================

On 10/13/2013 05:03 PM, Jerry Leichter wrote:
> Hundreds of eyeballs may have been on the Linux code, but we still
> ended up fielding a system with a completely crippled RNG and not
> noticing for months.

I'm not at all convinced that hundreds of eyeballs have ever 
looked at the source code for Linux /dev/random.  In any case, 
a small number of careful eyeballs would be far more valuable 
than a huge number of cursory eyeballs.

Suppose we provide /dev/random with a good source of entropy,
including (!) a reliable estimate of the amount of entropy
(hint: turbid).  Even then, it is not at all obvious that the 
current version of the Linux /dev/random is a good custodian
of the entropy it is given.

I noticed this when working on the upcoming new version of
turbid.  It contains a subsystem that feeds entropy into
/dev/random.  I didn't want to look at /dev/random at all,
but eventually I had to, because I couldn't figure out a
way to feed it entropy without huge amounts of waste.
AFAICT that isn't possible in the current version, although
this is a fixable problem.

A non-exhaustive list of questions and issues -- some quite 
deep and some quite superficial -- can be found at
  http://www.av8n.com/turbid/paper/devrandom.htm

I have a prototype ("alpha") version of random.c that 
addresses most of these issues.  If there are any
misunderstandings about what /dev/random is doing, it
would be good to clear them up sooner rather than later.

=====================================

A word about the article by Dodis et al. claiming that 
/dev/random is "not robust".  IMHO that is a red herring.
It raises issues that have little direct importance.  For 
one thing, there is no consensus that their definition of 
"robust" is relevant in a practical engineering sense.
Perhaps more importantly, we must object to the assertions 
about «how hard (or, perhaps, impossible?) it is to design 
a sound entropy estimation procedure».

It is a truism in many fields, including sculpture as well as
programming, that it is easy to do things wrong and hard to do
things right.  However, that does not mean that things /cannot/
be done right.  In particular, it is definitely *not* impossible
to implement an entropy estimator based on the second law of
thermodynamics, which is far more reliable than several other
assumptions that form the basis of modern cryptography.  Such
a thing requires effort and depth of understanding and attention 
to detail, but it can be done.  Hint: turbid.

The existence of unimportant issues should not blind us to 
more-important issues.