Patch: rework kernel random number subsystem

[Thor Lancelot Simon <tls%panix.com@localhost>]

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