Huge cleanup of random(4) code.

* GENERAL
- Update copyright.
- Make kernel options for RANDOM_YARROW and RANDOM_DUMMY. Set
  neither to ON, which means we want Fortuna
- If there is no 'device random' in the kernel, there will be NO
  random(4) device in the kernel, and the KERN_ARND sysctl will
  return nothing. With RANDOM_DUMMY there will be a random(4) that
  always blocks.
- Repair kern.arandom (KERN_ARND sysctl). The old version went
  through arc4random(9) and was a bit weird.
- Adjust arc4random stirring a bit - the existing code looks a little
  suspect.
- Fix the nasty pre- and post-read overloading by providing explictit
  functions to do these tasks.
- Redo read_random(9) so as to duplicate random(4)'s read internals.
  This makes it a first-class citizen rather than a hack.
- Move stuff out of locked regions when it does not need to be
  there.
- Trim RANDOM_DEBUG printfs. Some are excess to requirement, some
  behind boot verbose.
- Use SYSINIT to sequence the startup.
- Fix init/deinit sysctl stuff.
- Make relevant sysctls also tunables.
- Add different harvesting "styles" to allow for different requirements
  (direct, queue, fast).
- Add harvesting of FFS atime events. This needs to be checked for
  weighing down the FS code.
- Add harvesting of slab allocator events. This needs to be checked for
  weighing down the allocator code.
- Fix the random(9) manpage.
- Loadable modules are not present for now. These will be re-engineered
  when the dust settles.
- Use macros for locks.
- Fix comments.

* src/share/man/...
- Update the man pages.

* src/etc/...
- The startup/shutdown work is done in D2924.

* src/UPDATING
- Add UPDATING announcement.

* src/sys/dev/random/build.sh
- Add copyright.
- Add libz for unit tests.

* src/sys/dev/random/dummy.c
- Remove; no longer needed. Functionality incorporated into randomdev.*.

* live_entropy_sources.c live_entropy_sources.h
- Remove; content moved.
- move content to randomdev.[ch] and optimise.

* src/sys/dev/random/random_adaptors.c src/sys/dev/random/random_adaptors.h
- Remove; plugability is no longer used. Compile-time algorithm
  selection is the way to go.

* src/sys/dev/random/random_harvestq.c src/sys/dev/random/random_harvestq.h
- Add early (re)boot-time randomness caching.

* src/sys/dev/random/randomdev_soft.c src/sys/dev/random/randomdev_soft.h
- Remove; no longer needed.

* src/sys/dev/random/uint128.h
- Provide a fake uint128_t; if a real one ever arrived, we can use
  that instead. All that is needed here is N=0, N++, N==0, and some
  localised trickery is used to manufacture a 128-bit 0ULLL.

* src/sys/dev/random/unit_test.c src/sys/dev/random/unit_test.h
- Improve unit tests; previously the testing human needed clairvoyance;
  now the test will do a basic check of compressibility. Clairvoyant
  talent is still a good idea.
- This is still a long way off a proper unit test.

* src/sys/dev/random/fortuna.c src/sys/dev/random/fortuna.h
- Improve messy union to just uint128_t.
- Remove unneeded 'static struct fortuna_start_cache'.
- Tighten up up arithmetic.
- Provide a method to allow eternal junk to be introduced; harden
  it against blatant by compress/hashing.
- Assert that locks are held correctly.
- Fix the nasty pre- and post-read overloading by providing explictit
  functions to do these tasks.
- Turn into self-sufficient module (no longer requires randomdev_soft.[ch])

* src/sys/dev/random/yarrow.c src/sys/dev/random/yarrow.h
- Improve messy union to just uint128_t.
- Remove unneeded 'staic struct start_cache'.
- Tighten up up arithmetic.
- Provide a method to allow eternal junk to be introduced; harden
  it against blatant by compress/hashing.
- Assert that locks are held correctly.
- Fix the nasty pre- and post-read overloading by providing explictit
  functions to do these tasks.
- Turn into self-sufficient module (no longer requires randomdev_soft.[ch])
- Fix some magic numbers elsewhere used as FAST and SLOW.

Differential Revision: https://reviews.freebsd.org/D2025
Reviewed by: vsevolod,delphij,rwatson,trasz,jmg
Approved by: so (delphij)

1 files changed, 289 insertions, 131 deletions

diff --git a/sys/dev/random/randomdev.c b/sys/dev/random/randomdev.c
index 9d41aed..1d9dcbe 100644
--- a/sys/dev/random/randomdev.c
+++ b/sys/dev/random/randomdev.c
@@ -1,6 +1,5 @@
 /*-
- * Copyright (c) 2000-2013 Mark R V Murray
- * Copyright (c) 2013 Arthur Mesh <arthurmesh@gmail.com>
+ * Copyright (c) 2000-2015 Mark R V Murray
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
@@ -26,28 +25,9 @@
  *
  */
 
-/*
- * NOTE NOTE NOTE
- *
- * This file is compiled into the kernel unconditionally. Any random(4)
- * infrastructure that needs to be in the kernel by default goes here!
- *
- * Except ...
- *
- * The adaptor code all goes into random_adaptor.c, which is also compiled
- * the kernel by default. The module in that file is initialised before
- * this one.
- *
- * Other modules must be initialised after the above two, and are
- * software random processors which plug into random_adaptor.c.
- *
- */
-
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
 
-#include "opt_random.h"
-
 #include <sys/param.h>
 #include <sys/systm.h>
 #include <sys/bus.h>
@@ -59,27 +39,42 @@ __FBSDID("$FreeBSD$");
 #include <sys/lock.h>
 #include <sys/module.h>
 #include <sys/malloc.h>
+#include <sys/poll.h>
 #include <sys/proc.h>
 #include <sys/random.h>
+#include <sys/sbuf.h>
+#include <sys/selinfo.h>
 #include <sys/sysctl.h>
 #include <sys/systm.h>
 #include <sys/uio.h>
 #include <sys/unistd.h>
 
+#include <crypto/rijndael/rijndael-api-fst.h>
+#include <crypto/sha2/sha2.h>
+
+#include <dev/random/hash.h>
 #include <dev/random/randomdev.h>
-#include <dev/random/random_adaptors.h>
 #include <dev/random/random_harvestq.h>
 
-#define RANDOM_MINOR	0
+#include "opt_random.h"
+
+#if defined(RANDOM_DUMMY) && defined(RANDOM_YARROW)
+#error "Cannot define both RANDOM_DUMMY and RANDOM_YARROW"
+#endif
 
+#define	RANDOM_MINOR	0
+
+static d_read_t randomdev_read;
+static d_write_t randomdev_write;
+static d_poll_t randomdev_poll;
 static d_ioctl_t randomdev_ioctl;
 
 static struct cdevsw random_cdevsw = {
 	.d_name = "random",
 	.d_version = D_VERSION,
-	.d_read = random_adaptor_read,
-	.d_write = random_adaptor_write,
-	.d_poll = random_adaptor_poll,
+	.d_read = randomdev_read,
+	.d_write = randomdev_write,
+	.d_poll = randomdev_poll,
 	.d_ioctl = randomdev_ioctl,
 };
 
@@ -87,163 +82,326 @@ static struct cdevsw random_cdevsw = {
 static struct cdev *random_dev;
 
 /* Set up the sysctl root node for the entropy device */
-SYSCTL_NODE(_kern, OID_AUTO, random, CTLFLAG_RW, 0, "Random Number Generator");
+SYSCTL_NODE(_kern, OID_AUTO, random, CTLFLAG_RW, 0, "Cryptographically Secure Random Number Generator");
 
 MALLOC_DEFINE(M_ENTROPY, "entropy", "Entropy harvesting buffers and data structures");
 
-/* ARGSUSED */
-static int
-randomdev_ioctl(struct cdev *dev __unused, u_long cmd, caddr_t addr __unused,
-    int flags __unused, struct thread *td __unused)
-{
-	int error = 0;
-
-	switch (cmd) {
-		/* Really handled in upper layer */
-	case FIOASYNC:
-	case FIONBIO:
-		break;
+#if defined(RANDOM_DUMMY)
 
-	default:
-		error = ENOTTY;
+/*-
+ * Dummy "always block" pseudo algorithm, used when there is no real
+ * random(4) driver to provide a CSPRNG.
+ */
 
-	}
+static u_int
+dummy_random_zero(void)
+{
 
-	return (error);
+	return (0);
 }
 
-/* Helper routine to enable kproc_exit() to work while the module is
- * being (or has been) unloaded.
- * This routine is in this file because it is always linked into the kernel,
- * and will thus never be unloaded. This is critical for unloadable modules
- * that have threads.
- */
-void
-randomdev_set_wakeup_exit(void *control)
+static void
+dummy_random(void)
 {
-
-	wakeup(control);
-	kproc_exit(0);
-	/* NOTREACHED */
 }
 
-/* ARGSUSED */
-static int
-randomdev_modevent(module_t mod __unused, int type, void *data __unused)
-{
-	int error = 0;
+struct random_algorithm random_alg_context = {
+	.ra_ident = "Dummy",
+	.ra_reseed = dummy_random,
+	.ra_seeded = (random_alg_seeded_t *)dummy_random_zero,
+	.ra_pre_read = dummy_random,
+	.ra_read = (random_alg_read_t *)dummy_random_zero,
+	.ra_post_read = dummy_random,
+	.ra_write = (random_alg_write_t *)dummy_random_zero,
+	.ra_event_processor = NULL,
+	.ra_poolcount = 0,
+};
 
-	switch (type) {
-	case MOD_LOAD:
-		printf("random: entropy device infrastructure driver\n");
-		random_dev = make_dev_credf(MAKEDEV_ETERNAL_KLD, &random_cdevsw,
-		    RANDOM_MINOR, NULL, UID_ROOT, GID_WHEEL, 0644, "random");
-		make_dev_alias(random_dev, "urandom"); /* compatibility */
-		random_adaptors_init();
-		break;
+#else /* !defined(RANDOM_DUMMY) */
 
-	case MOD_UNLOAD:
-		random_adaptors_deinit();
-		destroy_dev(random_dev);
-		break;
+LIST_HEAD(sources_head, random_sources);
+static struct sources_head source_list = LIST_HEAD_INITIALIZER(source_list);
+static u_int read_rate;
 
-	case MOD_SHUTDOWN:
-		break;
+#endif /* defined(RANDOM_DUMMY) */
 
-	default:
-		error = EOPNOTSUPP;
-		break;
+static struct selinfo rsel;
 
+/*
+ * This is the read uio(9) interface for random(4).
+ */
+/* ARGSUSED */
+static int
+randomdev_read(struct cdev *dev __unused, struct uio *uio, int flags)
+{
+	uint8_t *random_buf;
+	int c, error;
+	ssize_t nbytes;
+
+	random_buf = malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK);
+	random_alg_context.ra_pre_read();
+	/* (Un)Blocking logic */
+	error = 0;
+	while (!random_alg_context.ra_seeded() && error == 0) {
+		if (flags & O_NONBLOCK)	{
+			error = EWOULDBLOCK;
+			break;
+		}
+		tsleep(&random_alg_context, 0, "randrd", hz/10);
+		/* keep tapping away at the pre-read until we seed/unblock. */
+		random_alg_context.ra_pre_read();
+		printf("random: %s unblock (error = %d)\n", __func__, error);
 	}
-
+	if (error == 0) {
+#if !defined(RANDOM_DUMMY)
+		/* XXX: FIX!! Next line as an atomic operation? */
+		read_rate += (uio->uio_resid + sizeof(uint32_t))/sizeof(uint32_t);
+#endif
+		nbytes = uio->uio_resid;
+		while (uio->uio_resid && !error) {
+			c = MIN(uio->uio_resid, PAGE_SIZE);
+			random_alg_context.ra_read(random_buf, c);
+			error = uiomove(random_buf, c, uio);
+		}
+		random_alg_context.ra_post_read();
+		if (nbytes != uio->uio_resid && (error == ERESTART || error == EINTR) )
+			/* Return partial read, not error. */
+			error = 0;
+	}
+	free(random_buf, M_ENTROPY);
 	return (error);
 }
 
-DEV_MODULE_ORDERED(randomdev, randomdev_modevent, NULL, SI_ORDER_SECOND);
-MODULE_VERSION(randomdev, 1);
-
-/* ================
- * Harvesting stubs
- * ================
+/*-
+ * Kernel API version of read_random().
+ * This is similar to random_alg_read(),
+ * except it doesn't interface with uio(9).
+ * It cannot assumed that random_buf is a multiple of
+ * RANDOM_BLOCKSIZE bytes.
  */
+u_int
+read_random(void *random_buf, u_int len)
+{
+	u_int read_len, total_read, c;
+	uint8_t local_buf[len + RANDOM_BLOCKSIZE];
+
+	KASSERT(random_buf != NULL, ("No suitable random buffer in %s", __func__));
+	random_alg_context.ra_pre_read();
+	/* (Un)Blocking logic; if not seeded, return nothing. */
+	if (random_alg_context.ra_seeded()) {
+#if !defined(RANDOM_DUMMY)
+		/* XXX: FIX!! Next line as an atomic operation? */
+		read_rate += (len + sizeof(uint32_t))/sizeof(uint32_t);
+#endif
+		read_len = len;
+		total_read = 0;
+		while (read_len) {
+			c = MIN(read_len, PAGE_SIZE);
+			random_alg_context.ra_read(&local_buf[total_read], c);
+			read_len -= c;
+			total_read += c;
+		}
+		memcpy(random_buf, local_buf, len);
+	} else
+		len = 0;
+	random_alg_context.ra_post_read();
+	return (len);
+}
 
-/* Internal stub/fake routine for when no entropy processor is loaded.
- * If the entropy device is not loaded, don't act on harvesting calls
- * and just return.
- */
 /* ARGSUSED */
-static void
-random_harvest_phony(const void *entropy __unused, u_int count __unused,
-    u_int bits __unused, enum random_entropy_source origin __unused)
+static int
+randomdev_write(struct cdev *dev __unused, struct uio *uio, int flags __unused)
 {
+	uint8_t *random_buf;
+	int c, error = 0;
+	ssize_t nbytes;
+
+	random_buf = malloc(PAGE_SIZE, M_ENTROPY, M_WAITOK);
+	nbytes = uio->uio_resid;
+	while (uio->uio_resid > 0 && error == 0) {
+		c = MIN(uio->uio_resid, PAGE_SIZE);
+		error = uiomove(random_buf, c, uio);
+		if (error)
+			break;
+		random_alg_context.ra_write(random_buf, c);
+		tsleep(&random_alg_context, 0, "randwr", hz/10);
+	}
+	if (nbytes != uio->uio_resid && (error == ERESTART || error == EINTR))
+		/* Partial write, not error. */
+		error = 0;
+	free(random_buf, M_ENTROPY);
+	return (error);
 }
 
-/* Hold the address of the routine which is actually called */
-static void (*reap_func)(const void *, u_int, u_int, enum random_entropy_source) = random_harvest_phony;
+/* ARGSUSED */
+static int
+randomdev_poll(struct cdev *dev __unused, int events, struct thread *td __unused)
+{
 
-/* Initialise the harvester when/if it is loaded */
+	if (events & (POLLIN | POLLRDNORM)) {
+		if (random_alg_context.ra_seeded())
+			events &= (POLLIN | POLLRDNORM);
+		else
+			selrecord(td, &rsel);
+	}
+	return (events);
+}
+
+/* This will be called by the entropy processor when it seeds itself and becomes secure */
 void
-randomdev_init_harvester(void (*reaper)(const void *, u_int, u_int, enum random_entropy_source))
+randomdev_unblock(void)
 {
 
-	reap_func = reaper;
+	selwakeuppri(&rsel, PUSER);
+	wakeup(&random_alg_context);
+	printf("random: unblocking device.\n");
+	/* Do random(9) a favour while we are about it. */
+	(void)atomic_cmpset_int(&arc4rand_iniseed_state, ARC4_ENTR_NONE, ARC4_ENTR_HAVE);
 }
 
-/* Deinitialise the harvester when/if it is unloaded */
-void
-randomdev_deinit_harvester(void)
+/* ARGSUSED */
+static int
+randomdev_ioctl(struct cdev *dev __unused, u_long cmd, caddr_t addr __unused,
+    int flags __unused, struct thread *td __unused)
 {
+	int error = 0;
+
+	switch (cmd) {
+		/* Really handled in upper layer */
+	case FIOASYNC:
+	case FIONBIO:
+		break;
+	default:
+		error = ENOTTY;
+	}
 
-	reap_func = random_harvest_phony;
+	return (error);
 }
 
-/* Entropy harvesting routine.
- * Implemented as in indirect call to allow non-inclusion of
- * the entropy device.
- */
 void
-random_harvest(const void *entropy, u_int count, u_int bits, enum random_entropy_source origin)
+random_source_register(struct random_source *rsource)
 {
+#if defined(RANDOM_DUMMY)
+	(void)rsource;
+#else /* !defined(RANDOM_DUMMY) */
+	struct random_sources *rrs;
 
-	(*reap_func)(entropy, count, bits, origin);
-}
+	KASSERT(rsource != NULL, ("invalid input to %s", __func__));
 
-/* ================================
- * Internal reading stubs and fakes
- * ================================
- */
+	rrs = malloc(sizeof(*rrs), M_ENTROPY, M_WAITOK);
+	rrs->rrs_source = rsource;
 
-/* Hold the address of the routine which is actually called */
-static void (*read_func)(uint8_t *, u_int) = dummy_random_read_phony;
+	printf("random: registering fast source %s\n", rsource->rs_ident);
+	LIST_INSERT_HEAD(&source_list, rrs, rrs_entries);
+#endif /* defined(RANDOM_DUMMY) */
+}
 
-/* Initialise the reader when/if it is loaded */
 void
-randomdev_init_reader(void (*reader)(uint8_t *, u_int))
+random_source_deregister(struct random_source *rsource)
 {
-
-	read_func = reader;
+#if defined(RANDOM_DUMMY)
+	(void)rsource;
+#else /* !defined(RANDOM_DUMMY) */
+	struct random_sources *rrs = NULL;
+
+	KASSERT(rsource != NULL, ("invalid input to %s", __func__));
+	LIST_FOREACH(rrs, &source_list, rrs_entries)
+		if (rrs->rrs_source == rsource) {
+			LIST_REMOVE(rrs, rrs_entries);
+			break;
+		}
+	if (rrs != NULL)
+		free(rrs, M_ENTROPY);
+#endif /* defined(RANDOM_DUMMY) */
 }
 
-/* Deinitialise the reader when/if it is unloaded */
+#if !defined(RANDOM_DUMMY)
+/*
+ * Run through all fast sources reading entropy for the given
+ * number of rounds, which should be a multiple of the number
+ * of entropy accumulation pools in use; 2 for Yarrow and 32
+ * for Fortuna.
+ *
+ * BEWARE!!!
+ * This function runs inside the RNG thread! Don't do anything silly!
+ */
 void
-randomdev_deinit_reader(void)
+random_sources_feed(void)
 {
+	uint32_t entropy[HARVESTSIZE];
+	struct random_sources *rrs;
+	u_int i, n, local_read_rate;
+
+	/*
+	 * Step over all of live entropy sources, and feed their output
+	 * to the system-wide RNG.
+	 */
+	/* XXX: FIX!! Next lines as an atomic operation? */
+	local_read_rate = read_rate;
+	read_rate = RANDOM_ALG_READ_RATE_MINIMUM;
+	LIST_FOREACH(rrs, &source_list, rrs_entries) {
+		for (i = 0; i < random_alg_context.ra_poolcount*local_read_rate; i++) {
+			n = rrs->rrs_source->rs_read(entropy, sizeof(entropy));
+			KASSERT((n > 0 && n <= sizeof(entropy)), ("very bad return from rs_read (= %d) in %s", n, __func__));
+			random_harvest_direct(entropy, n, (n*8)/2, rrs->rrs_source->rs_source);
+		}
+	}
+	explicit_bzero(entropy, sizeof(entropy));
+}
 
-	read_func = dummy_random_read_phony;
+static int
+random_source_handler(SYSCTL_HANDLER_ARGS)
+{
+	struct random_sources *rrs;
+	struct sbuf sbuf;
+	int error, count;
+
+	sbuf_new_for_sysctl(&sbuf, NULL, 64, req);
+	count = 0;
+	LIST_FOREACH(rrs, &source_list, rrs_entries) {
+		sbuf_cat(&sbuf, (count++ ? ",'" : "'"));
+		sbuf_cat(&sbuf, rrs->rrs_source->rs_ident);
+		sbuf_cat(&sbuf, "'");
+	}
+	error = sbuf_finish(&sbuf);
+	sbuf_delete(&sbuf);
+	return (error);
 }
+SYSCTL_PROC(_kern_random, OID_AUTO, random_sources, CTLTYPE_STRING | CTLFLAG_RD | CTLFLAG_MPSAFE,
+	    NULL, 0, random_source_handler, "A",
+	    "List of active fast entropy sources.");
+#endif /* !defined(RANDOM_DUMMY) */
 
-/* Kernel API version of read_random().
- * Implemented as in indirect call to allow non-inclusion of
- * the entropy device.
- */
-int
-read_random(void *buf, int count)
+/* ARGSUSED */
+static int
+randomdev_modevent(module_t mod __unused, int type, void *data __unused)
 {
+	int error = 0;
 
-	if (count < 0)
-		return 0;
+	switch (type) {
+	case MOD_LOAD:
+		printf("random: entropy device external interface\n");
+		random_dev = make_dev_credf(MAKEDEV_ETERNAL_KLD, &random_cdevsw,
+		    RANDOM_MINOR, NULL, UID_ROOT, GID_WHEEL, 0644, "random");
+		make_dev_alias(random_dev, "urandom"); /* compatibility */
+		break;
+	case MOD_UNLOAD:
+		destroy_dev(random_dev);
+		break;
+	case MOD_SHUTDOWN:
+		break;
+	default:
+		error = EOPNOTSUPP;
+		break;
+	}
+	return (error);
+}
 
-	read_func(buf, count);
+static moduledata_t randomdev_mod = {
+	"random_device",
+	randomdev_modevent,
+	0
+};
 
-	return count;
-}
+DECLARE_MODULE(random_device, randomdev_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST);
+MODULE_VERSION(random_device, 1);