Very large makeover of the /dev/random driver.

o Separate the kernel stuff from the Yarrow algorithm. Yarrow is now
  well contained in one source file and one header.

o Replace the Blowfish-based crypto routines with Rijndael-based ones.
  (Rijndael is the new AES algorithm). The huge improvement in
  Rijndael's key-agility over Blowfish means that this is an
  extremely dramatic improvement in speed, and makes a heck of
  a difference in its (lack of) CPU load.

o Clean up the sysctl's. At BDE's prompting, I have gone back to
  static sysctls.

o Bug fixes. The streamlining of the crypto stuff enabled me to
  find and fix some bugs. DES also found a bug in the reseed routine
  which is fixed.

o Change the way reseeds clear "used" entropy. Previously, only the
  source(s) that caused a reseed were cleared. Now all sources in the
  relevant pool(s) are cleared.

o Code tidy-up. Mostly to make it (nearly) 80-column compliant.

1 files changed, 107 insertions, 274 deletions

diff --git a/sys/dev/random/yarrow.c b/sys/dev/random/yarrow.c
index 6313587..542bece 100644
--- a/sys/dev/random/yarrow.c
+++ b/sys/dev/random/yarrow.c
@@ -29,229 +29,128 @@
 #include <sys/param.h>
 #include <sys/systm.h>
 #include <sys/kernel.h>
-#include <sys/kthread.h>
 #include <sys/libkern.h>
 #include <sys/mutex.h>
 #include <sys/selinfo.h>
 #include <sys/random.h>
+#include <sys/sysctl.h>
 #include <sys/types.h>
-#include <sys/unistd.h>
 
-#include <machine/atomic.h>
-#include <machine/cpu.h>
-
-#include <crypto/blowfish/blowfish.h>
+#include <crypto/rijndael/rijndael.h>
 
 #include <dev/random/hash.h>
+#include <dev/random/randomdev.h>
 #include <dev/random/yarrow.h>
 
 /* #define DEBUG */
 
-static void generator_gate(void);
-static void reseed(int);
-static void random_harvest_internal(u_int64_t, void *, u_int, u_int, u_int, enum esource);
+RANDOM_CHECK_UINT(gengateinterval, 4, 64);
+RANDOM_CHECK_UINT(bins, 2, 16);
+RANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE);
+RANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE);
+RANDOM_CHECK_UINT(slowoverthresh, 1, 5);
+
+SYSCTL_NODE(_kern_random, OID_AUTO, yarrow, CTLFLAG_RW, 0, "Yarrow Parameters");
+SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, gengateinterval,
+	CTLTYPE_INT|CTLFLAG_RW, &random_state.gengateinterval, 10,
+	random_check_uint_gengateinterval, "I", "Generator Gate Interval");
+SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, bins,
+	CTLTYPE_INT|CTLFLAG_RW, &random_state.bins, 10,
+	random_check_uint_bins, "I", "Execution time tuner");
+SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, fastthresh,
+	CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[0].thresh, (3*BLOCKSIZE)/4,
+	random_check_uint_fastthresh, "I", "Fast reseed threshold");
+SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowthresh,
+	CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[1].thresh, BLOCKSIZE,
+	random_check_uint_slowthresh, "I", "Slow reseed threshold");
+SYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowoverthresh,
+	CTLTYPE_INT|CTLFLAG_RW, &random_state.slowoverthresh, 2,
+	random_check_uint_slowoverthresh, "I", "Slow over-threshold reseed");
 
-static void random_kthread(void *);
+static void generator_gate(void);
+static void reseed(u_int);
 
 /* Structure holding the entropy state */
 struct random_state random_state;
 
-/* These are used to queue harvested packets of entropy. The entropy
- * buffer size is pretty arbitrary.
- */
-struct harvest {
-	u_int64_t somecounter;		/* fast counter for clock jitter */
-	u_char entropy[HARVESTSIZE];	/* the harvested entropy */
-	u_int size, bits, frac;		/* stats about the entropy */
-	enum esource source;		/* stats about the entropy */
-};
-
-/* Ring buffer holding harvested entropy */
-static struct harvestring {
-	volatile int	head;
-	volatile int	tail;
-	struct harvest	data[HARVEST_RING_SIZE];
-} harvestring;
-
 /* The reseed thread mutex */
 static struct mtx random_reseed_mtx;
 
-/* <0 to end the kthread, 0 to let it run */
-static int random_kthread_control = 0;
-
-static struct proc *random_kthread_proc;
-
-static void
-random_kthread(void *arg /* NOTUSED */)
+/* Process a single stochastic event off the harvest queue */
+void
+random_process_event(struct harvest *event)
 {
-	int pl, src, overthreshhold[2], newtail;
-	struct harvest *event;
+	u_int pl, src, overthreshhold[2];
 	struct source *source;
 
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("OWNERSHIP Giant == %d sched_lock == %d\n",
-		mtx_owned(&Giant), mtx_owned(&sched_lock));
-	mtx_unlock(&Giant);
-#endif
-
-	for (pl = 0; pl < 2; pl++)
-		yarrow_hash_init(&random_state.pool[pl].hash, NULL, 0);
-
-	for (;;) {
-
-		if (harvestring.tail == harvestring.head)
-			tsleep(&harvestring, PUSER, "rndslp", hz/10);
-
-		else {
-
-			/* Suck the harvested entropy out of the queue and hash
-			 * it into the appropriate pool.
-			 */
-
-			newtail = (harvestring.tail + 1) & HARVEST_RING_MASK;
-			event = &harvestring.data[harvestring.tail];
-
-			/* Bump the ring counter. This action is assumed
-			 * to be atomic.
-			 */
-			harvestring.tail = newtail;
-
-			pl = random_state.which = !random_state.which;
-
-			source = &random_state.pool[pl].source[event->source];
-			yarrow_hash_iterate(&random_state.pool[pl].hash,
-				event->entropy, sizeof(event->entropy));
-			yarrow_hash_iterate(&random_state.pool[pl].hash,
-				&event->somecounter, sizeof(event->somecounter));
-			source->frac += event->frac;
-			source->bits += event->bits + source->frac/1024;
-			source->frac %= 1024;
-
-			/* Count the over-threshold sources in each pool */
-			for (pl = 0; pl < 2; pl++) {
-				overthreshhold[pl] = 0;
-				for (src = 0; src < ENTROPYSOURCE; src++) {
-					if (random_state.pool[pl].source[src].bits
-						> random_state.pool[pl].thresh)
-						overthreshhold[pl]++;
-				}
-			}
-
-			/* if any fast source over threshhold, reseed */
-			if (overthreshhold[FAST])
-				reseed(FAST);
-	
-			/* if enough slow sources are over threshhold, reseed */
-			if (overthreshhold[SLOW] >= random_state.slowoverthresh)
-				reseed(SLOW);
-
+	/* Unpack the event into the appropriate source accumulator */
+	pl = random_state.which;
+	source = &random_state.pool[pl].source[event->source];
+	yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy,
+		sizeof(event->entropy));
+	yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter,
+		sizeof(event->somecounter));
+	source->frac += event->frac;
+	source->bits += event->bits + source->frac/1024;
+	source->frac %= 1024;
+
+	/* Count the over-threshold sources in each pool */
+	for (pl = 0; pl < 2; pl++) {
+		overthreshhold[pl] = 0;
+		for (src = 0; src < ENTROPYSOURCE; src++) {
+			if (random_state.pool[pl].source[src].bits
+				> random_state.pool[pl].thresh)
+				overthreshhold[pl]++;
 		}
+	}
 
-		/* Is the thread scheduled for a shutdown? */
-		if (random_kthread_control != 0) {
-#ifdef DEBUG
-			mtx_lock(&Giant);
-			printf("Random kthread setting terminate\n");
-			mtx_unlock(&Giant);
-#endif
-			random_set_wakeup_exit(&random_kthread_control);
-			/* NOTREACHED */
-			break;
-		}
+	/* if any fast source over threshhold, reseed */
+	if (overthreshhold[FAST])
+		reseed(FAST);
 
-	}
+	/* if enough slow sources are over threshhold, reseed */
+	if (overthreshhold[SLOW] >= random_state.slowoverthresh)
+		reseed(SLOW);
 
+	/* Invert the fast/slow pool selector bit */
+	random_state.which = !random_state.which;
 }
 
-int
+void
 random_init(void)
 {
-	int error;
-
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random initialise\n");
-	mtx_unlock(&Giant);
-#endif
-
-	/* This can be turned off by the very paranoid
-	 * a reseed will turn it back on.
-	 */
-	random_state.seeded = 1;
+	int i;
 
 	/* Yarrow parameters. Do not adjust these unless you have
 	 * have a very good clue about what they do!
 	 */
 	random_state.gengateinterval = 10;
 	random_state.bins = 10;
-	random_state.pool[0].thresh = 100;
-	random_state.pool[1].thresh = 160;
+	random_state.pool[0].thresh = (3*BLOCKSIZE)/4;
+	random_state.pool[1].thresh = BLOCKSIZE;
 	random_state.slowoverthresh = 2;
 	random_state.which = FAST;
 
-	mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF);
-
-	harvestring.head = 0;
-	harvestring.tail = 0;
-
-	/* Start the hash/reseed thread */
-	error = kthread_create(random_kthread, NULL,
-		&random_kthread_proc, RFHIGHPID, "random");
-	if (error != 0)
-		return error;
+	/* Initialise the fast and slow entropy pools */
+	for (i = 0; i < 2; i++)
+		yarrow_hash_init(&random_state.pool[i].hash);
 
-	/* Register the randomness harvesting routine */
-	random_init_harvester(random_harvest_internal, read_random_real);
+	/* Clear the counter */
+	for (i = 0; i < 4; i++)
+		random_state.counter[i] = 0;
 
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random initialise finish\n");
-	mtx_unlock(&Giant);
-#endif
-
-	return 0;
+	/* Set up a lock for the reseed process */
+	mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF);
 }
 
 void
 random_deinit(void)
 {
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random deinitialise\n");
-	mtx_unlock(&Giant);
-#endif
-
-	/* Deregister the randomness harvesting routine */
-	random_deinit_harvester();
-
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random deinitialise waiting for thread to terminate\n");
-	mtx_unlock(&Giant);
-#endif
-
-	/* Command the hash/reseed thread to end and wait for it to finish */
-	random_kthread_control = -1;
-	tsleep((void *)&random_kthread_control, PUSER, "rndend", 0);
-
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random deinitialise removing mutexes\n");
-	mtx_unlock(&Giant);
-#endif
-
 	mtx_destroy(&random_reseed_mtx);
-
-#ifdef DEBUG
-	mtx_lock(&Giant);
-	printf("Random deinitialise finish\n");
-	mtx_unlock(&Giant);
-#endif
 }
 
 static void
-reseed(int fastslow)
+reseed(u_int fastslow)
 {
 	/* Interrupt-context stack is a limited resource; make large
 	 * structures static.
@@ -260,7 +159,7 @@ reseed(int fastslow)
 	static struct yarrowhash context;
 	u_char hash[KEYSIZE];			/* h' */
 	u_char temp[KEYSIZE];
-	int i, j;
+	u_int i, j;
 
 #ifdef DEBUG
 	mtx_lock(&Giant);
@@ -273,14 +172,15 @@ reseed(int fastslow)
 
 	/* 1. Hash the accumulated entropy into v[0] */
 
-	yarrow_hash_init(&context, NULL, 0);
+	yarrow_hash_init(&context);
 	/* Feed the slow pool hash in if slow */
 	if (fastslow == SLOW)
 		yarrow_hash_iterate(&context,
-			&random_state.pool[SLOW].hash, sizeof(struct yarrowhash));
-
+			&random_state.pool[SLOW].hash,
+			sizeof(struct yarrowhash));
 	yarrow_hash_iterate(&context,
 		&random_state.pool[FAST].hash, sizeof(struct yarrowhash));
+	yarrow_hash_finish(&context, v[0]);
 
 	/* 2. Compute hash values for all v. _Supposed_ to be computationally
 	 *    intensive.
@@ -289,13 +189,13 @@ reseed(int fastslow)
 	if (random_state.bins > TIMEBIN)
 		random_state.bins = TIMEBIN;
 	for (i = 1; i < random_state.bins; i++) {
-		yarrow_hash_init(&context, NULL, 0);
-		/* v[i] #= h(v[i-1]) */
+		yarrow_hash_init(&context);
+		/* v[i] #= h(v[i - 1]) */
 		yarrow_hash_iterate(&context, v[i - 1], KEYSIZE);
 		/* v[i] #= h(v[0]) */
 		yarrow_hash_iterate(&context, v[0], KEYSIZE);
 		/* v[i] #= h(i) */
-		yarrow_hash_iterate(&context, &i, sizeof(int));
+		yarrow_hash_iterate(&context, &i, sizeof(u_int));
 		/* Return the hashval */
 		yarrow_hash_finish(&context, v[i]);
 	}
@@ -304,29 +204,26 @@ reseed(int fastslow)
 	 *    it is not being ignored!
 	 */
 
-	yarrow_hash_init(&context, NULL, 0);
+	yarrow_hash_init(&context);
 	yarrow_hash_iterate(&context, &random_state.key, KEYSIZE);
 	for (i = 1; i < random_state.bins; i++)
 		yarrow_hash_iterate(&context, &v[i], KEYSIZE);
 	yarrow_hash_finish(&context, temp);
-	yarrow_encrypt_init(&random_state.key, temp, KEYSIZE);
+	yarrow_encrypt_init(&random_state.key, temp);
 
 	/* 4. Recompute the counter */
 
-	random_state.counter = 0;
-	yarrow_encrypt(&random_state.key, &random_state.counter, temp,
-		sizeof(random_state.counter));
-	memcpy(&random_state.counter, temp, random_state.counter);
+	for (i = 0; i < 4; i++)
+		random_state.counter[i] = 0;
+	yarrow_encrypt(&random_state.key, random_state.counter, temp);
+	memcpy(random_state.counter, temp, sizeof(random_state.counter));
 
 	/* 5. Reset entropy estimate accumulators to zero */
 
 	for (i = 0; i <= fastslow; i++) {
 		for (j = 0; j < ENTROPYSOURCE; j++) {
-			if (random_state.pool[i].source[j].bits >
-				random_state.pool[i].thresh) {
-				random_state.pool[i].source[j].bits = 0;
-				random_state.pool[i].source[j].frac = 0;
-			}
+			random_state.pool[i].source[j].bits = 0;
+			random_state.pool[i].source[j].frac = 0;
 		}
 	}
 
@@ -348,14 +245,13 @@ reseed(int fastslow)
 	mtx_unlock(&Giant);
 #endif
 
-	if (!random_state.seeded) {
-		random_state.seeded = 1;
-		selwakeup(&random_state.rsel);
-		wakeup(&random_state);
-	}
-
+	/* Unblock the device if it was blocked due to being unseeded */
+	random_unblock();
 }
 
+/* Internal function to do return processed entropy from the
+ * Yarrow PRNG
+ */
 u_int
 read_random_real(void *buf, u_int count)
 {
@@ -376,12 +272,13 @@ read_random_real(void *buf, u_int count)
 	if (count >= sizeof(random_state.counter)) {
 		retval = 0;
 		for (i = 0; i < count; i += sizeof(random_state.counter)) {
-			random_state.counter++;
-			yarrow_encrypt(&random_state.key, &random_state.counter,
-				&genval, sizeof(random_state.counter));
+			random_state.counter[0]++;
+			yarrow_encrypt(&random_state.key, random_state.counter,
+				&genval);
 			memcpy((char *)buf + i, &genval,
 				sizeof(random_state.counter));
-			if (++random_state.outputblocks >= random_state.gengateinterval) {
+			if (++random_state.outputblocks >=
+				random_state.gengateinterval) {
 				generator_gate();
 				random_state.outputblocks = 0;
 			}
@@ -390,12 +287,13 @@ read_random_real(void *buf, u_int count)
 	}
 	else {
 		if (!cur) {
-			random_state.counter++;
-			yarrow_encrypt(&random_state.key, &random_state.counter,
-				&genval, sizeof(random_state.counter));
+			random_state.counter[0]++;
+			yarrow_encrypt(&random_state.key, random_state.counter,
+				&genval);
 			memcpy(buf, &genval, count);
 			cur = sizeof(random_state.counter) - count;
-			if (++random_state.outputblocks >= random_state.gengateinterval) {
+			if (++random_state.outputblocks >=
+				random_state.gengateinterval) {
 				generator_gate();
 				random_state.outputblocks = 0;
 			}
@@ -414,38 +312,10 @@ read_random_real(void *buf, u_int count)
 	return retval;
 }
 
-void
-write_random(void *buf, u_int count)
-{
-	u_int i;
-
-	/* Break the input up into HARVESTSIZE chunks.
-	 * The writer has too much control here, so "estimate" the
-	 * the entropy as zero.
-	 */
-	for (i = 0; i < count; i += HARVESTSIZE) {
-		random_harvest_internal(get_cyclecount(), (char *)buf + i,
-			HARVESTSIZE, 0, 0, RANDOM_WRITE);
-	}
-
-	/* Maybe the loop iterated at least once */
-	if (i > count)
-		i -= HARVESTSIZE;
-
-	/* Get the last bytes even if the input length is not
-	 * a multiple of HARVESTSIZE.
-	 */
-	count %= HARVESTSIZE;
-	if (count) {
-		random_harvest_internal(get_cyclecount(), (char *)buf + i,
-			count, 0, 0, RANDOM_WRITE);
-	}
-}
-
 static void
 generator_gate(void)
 {
-	int i;
+	u_int i;
 	u_char temp[KEYSIZE];
 
 #ifdef DEBUG
@@ -455,12 +325,12 @@ generator_gate(void)
 #endif
 
 	for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) {
-		random_state.counter++;
-		yarrow_encrypt(&random_state.key, &random_state.counter,
-			&(temp[i]), sizeof(random_state.counter));
+		random_state.counter[0]++;
+		yarrow_encrypt(&random_state.key, random_state.counter,
+			&(temp[i]));
 	}
 
-	yarrow_encrypt_init(&random_state.key, temp, KEYSIZE);
+	yarrow_encrypt_init(&random_state.key, temp);
 	memset((void *)temp, 0, KEYSIZE);
 
 #ifdef DEBUG
@@ -470,43 +340,6 @@ generator_gate(void)
 #endif
 }
 
-/* Entropy harvesting routine. This is supposed to be fast; do
- * not do anything slow in here!
- */
-
-static void
-random_harvest_internal(u_int64_t somecounter, void *entropy, u_int count,
-	u_int bits, u_int frac, enum esource origin)
-{
-	struct harvest *harvest;
-	int newhead;
-
-	newhead = (harvestring.head + 1) & HARVEST_RING_MASK;
-
-	if (newhead != harvestring.tail) {
-
-		/* Add the harvested data to the ring buffer */
-
-		harvest = &harvestring.data[harvestring.head];
-
-		/* Stuff the harvested data into the ring */
-		harvest->somecounter = somecounter;
-		count = count > HARVESTSIZE ? HARVESTSIZE : count;
-		memcpy(harvest->entropy, entropy, count);
-		harvest->size = count;
-		harvest->bits = bits;
-		harvest->frac = frac;
-		harvest->source = origin < ENTROPYSOURCE ? origin : 0;
-
-		/* Bump the ring counter. This action is assumed
-		 * to be atomic.
-		 */
-		harvestring.head = newhead;
-
-	}
-
-}
-
 /* Helper routine to perform explicit reseeds */
 void
 random_reseed(void)