Patch: rework kernel random number subsystem

Thor Lancelot Simon <[email protected]> Fri, 21 Oct 2011 17:15:55 -0400
Newsgroups gmane.os.netbsd.devel.security,gmane.os.netbsd.devel.kernel,gmane.os.netbsd.devel.crypto
Message-ID <[email protected]>
The attached diff includes many changes to the kernel random number
subsystem.

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
rnd1.diff (text/plain, 176.2 KB) - not displayed