I have placed a patch at http://www.panix.com/~tls/rnd1.diff which
implements many changes to the generation and use of randomness
in the kernel (I previously sent it to these lists directly but
it seems to be too large).
It is (most of) the first step in a three step process I envision for major
overhaul of this subsystem:
1) Provide infrastructure needed to separate entropy
harvesting from random stream generation. Clean up
interfaces between existing kernel components that
deal with random number generation and consumption.
2) Replace all direct read access to the entropy pool with
an appropriate random stream generator, keyed from the pool.
Clean up the current mess in which the same source files
implement the entropy pool and the userspace pseudodevices
/dev/random and /dev/urandom.
3) Replace the entropy pool itself with a more modern design
such as Fortuna.
Here are the changes you will find in this patch:
1) Two new components are provided, "rngtest" (subr_rngtest.c)
and "nist_ctr_drbg" (crypto/nist_ctr_drbg). The rngtest component
implements the FIPS 140-2 statistical RNG test. It is based on
work by Greg Rose at Qualcomm. The nist_ctr_drbg component
implements the NIST SP800-90 CTR_DRBG, which uses AES in a
modified counter mode to generate a backtracking-resistant random
stream. It is based on work by Henric Jungheim.
Additionally, an abstration layer "cprng" (subr_cprng.c) is
provided for in-kernel consumers of randomness; see below.
2) A generic interface, "rndsink", for stream generators to request
that they be re-keyed with good quality entropy from the pool
as soon as it is available, is provided.
3) The arc4random/arc4randbytes implementation in libkern is
adjusted to use the rndsink interface for rekeying, which
helps address the problem of low quality keys at boot time.
4) The arc4random/arc4randbytes API is deprecated for in-kernel
use. It is replaced by "cprng_fast". The rnd_extract_data
interface is deprecated for in-kernel use. It is replaced
by "cprng_strong". The current cprng_fast implementation
wraps the existing arc4random implementation. The current
cprng_strong implementation wraps the CTR_DRBG implementation,
allowing as many private instances of the CTR_DRBG as desired.
Both interfaces are rekeyed from the entropy pool automatically
at intervals justifiable from best current cryptographic practice.
*When these generators are rekeyed, the 'rngtest' test is run
on their output and the kernel will panic if it fails.* It
is not the long-term intent to panic on a rngtest failure,
but rather to rekey; but this is a good way to detect bugs in
the implementation (see below).
5) The AES code in src/crypto/rijndael is no longer an optional
kernel component, as it is required by cprng_strong, which is
not an optional kernel component.
6) The entropy pool output is subjected to the rngtest tests at
startup time. Entropy pool _input_ from hardware random
number generators is subjected to the rngtest tests at attach
time, as well as the FIPS continuous-output test, to detect
bad or stuck hardware RNGs.
7) The sysctl node kern.urandom is now connected to cprng_strong
rather than the entropy pool (this allows cprng_strong testing
from userspace without replacing the pseudodevice yet).
8) The set of printfs triggered by RND_VERBOSE has been expanded.
WARNING: #7 and #8 reveal some kind of synchronization or locking
bug in this patch. #8 causes the entropy pool to log to
the console whenever it supplies rekeying entropy. #7
causes 'sysctl kern.urandom' to read from a cprng_strong
instance.
Performing around 1000 consecutive such sysctl calls will
reveal corruption of the cprng_strong state: it is not
rekeyed (nor should it yet be), but is corrupted in such
a way that it thinks it has been, triggering the rngtest
statistical test, which then fails.
Score 1 for the test, detecting a bug I can't sort out
yet; score 0 for me for not seeing what happens. Help
with this one (it's easy to reproduce!) much appreciated.
9) some API mess in rnd.c/rnd.h is cleaned up, such as exposing
structures with in-kernel void * to userspace in arrays, thus
causing compat32 issues.
10) I have made a start at letting the entropy pool supply useful
output *much* earlier in the boot process. There is a lot
more to do here.
This patch is against last night's sources and builds release successfully
for amd64. Works, too, except the bug noted at WARNING above. I am
aware there are KNF issues and would prefer to fix them later. Help,
comments, criticism much appreciated.
Thanks!
Thor
