Re: Patch: rework kernel random number subsystem

[christos%astron.com@localhost (Christos Zoulas)]

In article <20111022023226.A923B14A155%mail.netbsd.org@localhost>,
Thor Lancelot Simon  <tls%panix.com@localhost> wrote:
>
>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.

1) +    memset(r, 0, sizeof(r)); needs (*r)

2) The code around the above memset has whitespace issues.

3) Why do we have loops that have both a count sentinel and the list pointer
   sentinel? Shouldn't/couldn't those always be synced?

4) What's the hardcoded 16 in the name compares?

5) sizeof(type) in memcpy() should be sizeof(*dst

6) Isn't it possible to use the list foreach macros instead of open-coding?

7) instead of printfs shouldn't we use aprint?

8) some continuation lines are not knf.

9) cprng_strong_t *cprng_strong_create(const char *const name, int ipl) is
   not knf

christos