[Cryptography] [RNG] /dev/random initialisation

[Sandy Harris]

There can be problems with inadequate initialisation of the Linux
random(4) driver, as demonstrated by the research that found many RSA
keys using duplicate primes and attributed their creation mainly to
badly configured routers. As several people have pointed out,
discussion of crypto without a threat model tends to be pointless.
This is an attempt to provide an explicit model for those threats.

This deals only with threats from weak initialisation; I do not
discuss general entropy gathering and estimation or the new threats
that may arise with virtualisation.

If Linux is configured in the usual way, there is a file of saved
random data that is pushed into /dev/random by boot scripts. On some
systems there is a high-volume entropy source -- RdRand
(http://en.wikipedia.org/wiki/RdRand), Denker's Turbid
(http://www.av8n.com/turbid/paper/turbid.htm), Havege
(http://www.issihosts.com/haveged/), my maxwell
(ftp://ftp.cs.sjtu.edu.cn:990/sandy/maxwell/), Mueller's jitter-based
generator (http://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.pdf) ...

In those cases, provided that the file or source is secure, the
initialisation question is simple; all we need to determine is whether
urandom should block until the system gets enough entropy to put it
into a secure state. I think it should, but that is not the question
here.

What I want to model here is the harder case where none of the above
is in place or urandom starts producing output without waiting for
them. In an ideal world, this case would never arise but in the real
world it has and likely will again. The problem involves avoiding
duplicate outputs, so the birthday paradox works against us. If we
need a low risk of collision for 2^n cases, then we need about 2n bits
of input entropy.

There are two separate cases to consider: avoiding duplicate outputs
when a single device is rebooted many times and avoiding it when many
identical devices are deployed.

Multiple reboots of the same device are the easy case. One threat
involves a computer that is rebooted often (perhaps several times a
day) and whose outputs are monitored continuously over a fairly long
period (perhaps a year). Another involves an enemy that can force many
reboots of a network device without the administrators noticing and
blocking the attack. Neither threat looks at all likely to involve
more than a few thousand reboots, so a dozen or so bits of timing
information per reboot should be enough to block them.

Timing data appears to be the only thing we can use against this
threat; more-or-less everything else is constant across reboots. Linux
random already mixes in some timing information, but I am not certain
how much.

Many identical devices are a harder case. A manufacturer might produce
tens or hundreds of thousands of the same device and a Linux distro
might send out some huge number of installation images; allowing for
the birthday effect, we then need a fairly large amount of entropy.
For example, if there are 64K (2^16) devices, we need at least 32 bits
to make duplication unlikely. Something like 48 bits would probably be
enough for all cases that seem at all likely, though of course if we
can get more good bits, we should.

More-or-less anything that is unique per system will help here. System
serial number if there is one accessible, MAC addresses, IP addresses,
....

Just including a file of stored entropy does not solve this problem if
that file is the same on all devices or in all images. There is
available code to add different files to CD/USB images:
http://www.mail-archive.com/cryptography@metzdowd.com/msg11552.html

However, it is not clear that this could be applied at reasonable cost
in manufacturing and in the case of downloadable images using this
would make every image unique which would complicate the use of hashes
to verify the downloads. For large numbers of images it might also
involve significant loads on the server.

Also, keeping a stored entropy file secure is much harder if it is
burned into a CD or flash image and can be attacked anywhere in the
distribution chain than for a file that changes on every boot and can
be attacked only with root privileges on the target system. Using
different files looks like a fine solution in some cases -- for
example if you are creating USB keys to set up a few dozen servers
within an organisation -- but it cannot help with all cases.

There are two ways one might get suitable material into the driver
state. One can build it into the kernel's device initialisation code
or do it externally with a script along the lines of:

    ifconfig > /dev/random
    netstat > /dev/random
    uname -a > /dev/random
    ....

Gutmann has written a full RNG along these lines as part of Cryptlib:
http://www.cs.auckland.ac.nz/~pgut001/cryptlib/
That works just fine on a reasonably complex multi-user multi-process
system, but it is not clear that it would be adequate on a very
limited system such as a router which might have no users and small
non-varying sets of devices and processes.

However, if all we need is a few bits to help initialise the random
device, then something like the script above may fit. We do not need
any mixing since the driver does that. Nor do we need the full range
of entropy sources that Gutmann's code uses, or its careful error
checking. No doubt my first-guess code above could be improved by
taking ideas from Gutmann, but we do not need his whole system.

In general, building such operations into the device initialisation
code in the kernel is preferable to leaving it to an external script.
The environment is better known; there is no chance of writing a
script that relies on some program the target system turns out not to
have. Also, there is less chance of user error; the system
administrator cannot just disable the script in search of efficiency
or to get rid of an annoying error message.

There may be an exception. The random driver is generally initialised
early in the boot sequence so that it is ready before other programs
need it; that is best done within the driver. On the other hand,
initialisation based on overall system state may be best done later,
after everything else has been set up. Recognising that situation may
be hard to do from within the kernel, but it is trivial in the init
scripts; making a script along the lines above the very last thing the
init scripts do is straightforward. It is not clear that this would be
useful, but it is easily done if it is.

It looks as though getting 64 bits or more is possible. One of the
FreeBSD guys wrote on the other crypto list:
http://lists.randombit.net/pipermail/cryptography/2013-October/005689.html

" We also added entropy based on device attach times. Measurements show this
gives at least 4 bits of entropy per device (usually a lot more), and in
the worst case we saw, 32 devices were measured.

Ted is aware of this and says looking at something similar for Linux
is on his ToDo list. If something along those lines can be built and
the claim of four bits per device (or even two) is correct for Linux,
it appears that it would solve the problem.

If not, there may be other options. Any volatile kernel table --
processes, open files, devices ... -- might provide some entropy and
it would be possible to instrument some system processes (init?) or
system calls so they did as well.