From bda6631159d812341f6580e946c1018370472ca5 Mon Sep 17 00:00:00 2001 From: markm Date: Sun, 10 Sep 2000 13:52:19 +0000 Subject: Large upgrade to the entropy device; mainly inspired by feedback from many folk. o The reseed process is now a kthread. With SMPng, kthreads are pre-emptive, so the annoying jerkiness of the mouse is gone. o The data structures are protected by mutexes now, not splfoo()/splx(). o The cryptographic routines are broken out into their own subroutines. this facilitates review, and possible replacement if that is ever found necessary. Thanks to: kris, green, peter, jasone, grog, jhb Forgotten to thank: You know who you are; no offense intended. --- sys/dev/random/yarrow.c | 444 ++++++++++++++++++++++++++++++------------------ 1 file changed, 283 insertions(+), 161 deletions(-) (limited to 'sys/dev/random/yarrow.c') diff --git a/sys/dev/random/yarrow.c b/sys/dev/random/yarrow.c index 9611436..d882480 100644 --- a/sys/dev/random/yarrow.c +++ b/sys/dev/random/yarrow.c @@ -33,125 +33,275 @@ #include #include #include -#include +#include +#include #include #include +#include #include +#include #include #include #include +#include #include +#include #include /* #define DEBUG */ +/* #define DEBUG1 */ /* Very noisy - prints plenty harvesting stats */ static void generator_gate(void); static void reseed(int); static void random_harvest_internal(struct timespec *, void *, u_int, u_int, u_int, enum esource); +static void random_kthread(void *); +void random_set_wakeup(int *, int); +void random_set_wakeup_exit(int *, int, int); + /* Structure holding the entropy state */ struct random_state random_state; -/* When enough entropy has been harvested, asynchronously "stir" it in. - * The regate task is run at splsofttq() +/* Queue holding harvested entropy */ +TAILQ_HEAD(harvestqueue, harvest) harvestqueue, + initqueue = TAILQ_HEAD_INITIALIZER(harvestqueue); + +/* These are used to queue harvested packets of entropy. The entropy + * buffer size of 16 is pretty arbitrary. */ -static struct task regate_task[2]; +struct harvest { + struct timespec time; /* nanotime for clock jitter */ + u_char entropy[16]; /* the harvested entropy */ + u_int size, bits, frac; /* stats about the entropy */ + enum esource source; /* stats about the entropy */ + u_int pool; /* which pool this goes into */ + TAILQ_ENTRY(harvest) harvest; /* link to next */ +}; + +/* The reseed thread mutex */ +static mtx_t random_reseed_mtx; + +/* The entropy harvest mutex */ +static mtx_t random_harvest_mtx; -struct context { - u_int pool; -} context[2] = { - { 0 }, - { 1 } - }; +/* <0 until the kthread starts, 0 for running */ +static int random_kthread_status = -1; + +/* <0 to end the kthread, 0 to let it run */ +static int random_kthread_control = 0; + +static struct proc *random_kthread_proc; static void -regate(void *context, int pending) +random_kthread(void *status) { + int pl, src, overthreshhold[2]; + struct harvest *event; + struct source *source; +#ifdef DEBUG1 + int queuecount; +#endif + #ifdef DEBUG - printf("Regate task\n"); + printf("At %s, line %d: mtx_owned(&Giant) == %d\n", __FILE__, __LINE__, mtx_owned(&Giant)); + printf("At %s, line %d: mtx_owned(&sched_lock) == %d\n", __FILE__, __LINE__, mtx_owned(&sched_lock)); +#endif + random_set_wakeup((int *)status, 0); + + for (pl = 0; pl < 2; pl++) + yarrow_hash_init(&random_state.pool[pl].hash, NULL, 0); + + for (;;) { + + if (TAILQ_EMPTY(&harvestqueue)) { + + /* Sleep for a second to give the system a chance */ + mtx_enter(&Giant, MTX_DEF); + tsleep(&harvestqueue, PUSER, "rndslp", hz); + mtx_exit(&Giant, MTX_DEF); + + } + else { + + /* Suck the harvested entropy out of the queue and hash + * it into the fast and slow pools. + */ +#ifdef DEBUG1 + queuecount = 0; +#endif + TAILQ_FOREACH(event, &harvestqueue, harvest) { +#ifdef DEBUG1 + queuecount++; #endif - reseed(((struct context *)context)->pool); + mtx_enter(&random_harvest_mtx, MTX_DEF); + + event = TAILQ_FIRST(&harvestqueue); + TAILQ_REMOVE(&harvestqueue, event, harvest); + + mtx_exit(&random_harvest_mtx, MTX_DEF); + + source = &random_state.pool[event->pool].source[event->source]; + yarrow_hash_iterate(&random_state.pool[event->pool].hash, + event->entropy, sizeof(event->entropy)); + yarrow_hash_iterate(&random_state.pool[event->pool].hash, + &event->time, sizeof(event->time)); + source->frac += event->frac; + source->bits += event->bits + source->frac/1024; + source->frac %= 1024; + free(event, M_TEMP); + + /* XXX abuse tsleep() to get at mi_switch() */ + /* tsleep(&harvestqueue, PUSER, "rndprc", 1); */ + + } +#ifdef DEBUG1 + printf("Harvested %d events\n", queuecount); +#endif + + /* 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); + + } + + /* Is the thread scheduled for a shutdown? */ + if (random_kthread_control < 0) { + if (!TAILQ_EMPTY(&harvestqueue)) { +#ifdef DEBUG + printf("Random cleaning extraneous events\n"); +#endif + mtx_enter(&random_harvest_mtx, MTX_DEF); + TAILQ_FOREACH(event, &harvestqueue, harvest) { + TAILQ_REMOVE(&harvestqueue, event, harvest); + free(event, M_TEMP); + } + mtx_exit(&random_harvest_mtx, MTX_DEF); + } +#ifdef DEBUG + printf("Random kthread setting terminate\n"); +#endif + random_set_wakeup_exit((int *)status, -1, 0); + break; + } + + } + } -void +int random_init(void) { + int error; + #ifdef DEBUG - printf("Random init\n"); + printf("Random initialise\n"); #endif + random_state.gengateinterval = 10; random_state.bins = 10; random_state.pool[0].thresh = 100; random_state.pool[1].thresh = 160; random_state.slowoverthresh = 2; random_state.which = FAST; - TASK_INIT(®ate_task[FAST], FAST, ®ate, (void *)&context[FAST]); - TASK_INIT(®ate_task[SLOW], SLOW, ®ate, (void *)&context[SLOW]); + + harvestqueue = initqueue; + + /* Initialise the mutexes */ + mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF); + mtx_init(&random_harvest_mtx, "random harvest", MTX_DEF); + + /* Start the hash/reseed thread */ + error = kthread_create(random_kthread, &random_kthread_status, + &random_kthread_proc, 0, "random"); + if (error != 0) + return error; + + /* Register the randomness harvesting routine */ random_init_harvester(random_harvest_internal); + +#ifdef DEBUG + printf("Random initalise finish\n"); +#endif + + return 0; } void random_deinit(void) { #ifdef DEBUG - printf("Random deinit\n"); + printf("Random deinitalise\n"); #endif + + /* Deregister the randomness harvesting routine */ random_deinit_harvester(); + +#ifdef DEBUG + printf("Random deinitalise waiting for thread to terminate\n"); +#endif + + /* Command the hash/reseed thread to end and wait for it to finish */ + random_kthread_control = -1; + while (random_kthread_status != -1) + tsleep(&random_kthread_status, PUSER, "rndend", hz); + +#ifdef DEBUG + printf("Random deinitalise removing mutexes\n"); +#endif + + /* Remove the mutexes */ + mtx_destroy(&random_reseed_mtx); + mtx_destroy(&random_harvest_mtx); + +#ifdef DEBUG + printf("Random deinitalise finish\n"); +#endif } static void reseed(int fastslow) { - /* Interrupt-context stack is a limited resource; make static - * large structures; XXX Revisit - needs to move to the large - * random_state structure. + /* Interrupt-context stack is a limited resource; make large + * structures static. */ - static unsigned char v[TIMEBIN][KEYSIZE]; /* v[i] */ - unsigned char hash[KEYSIZE]; /* h' */ - static BF_KEY hashkey; - unsigned char ivec[8]; - unsigned char temp[KEYSIZE]; - struct entropy *bucket; + static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ + static struct yarrowhash context; + u_char hash[KEYSIZE]; /* h' */ + u_char temp[KEYSIZE]; int i, j; #ifdef DEBUG printf("Reseed type %d\n", fastslow); #endif + /* The reseed task must not be jumped on */ + mtx_enter(&random_reseed_mtx, MTX_DEF); + /* 1. Hash the accumulated entropy into v[0] */ - bzero((void *)&v[0], KEYSIZE); - if (fastslow == SLOW) { - /* Feed a hash of the slow pool into the fast pool */ - for (i = 0; i < ENTROPYSOURCE; i++) { - for (j = 0; j < ENTROPYBIN; j++) { - bucket = &random_state.pool[SLOW].source[i].entropy[j]; - if(bucket->nanotime.tv_sec || bucket->nanotime.tv_nsec) { - BF_set_key(&hashkey, sizeof(struct entropy), - (void *)bucket); - BF_cbc_encrypt(v[0], temp, KEYSIZE, &hashkey, ivec, - BF_ENCRYPT); - memcpy(&v[0], temp, KEYSIZE); - bucket->nanotime.tv_sec = 0; - bucket->nanotime.tv_nsec = 0; - } - } - } - } + yarrow_hash_init(&context, NULL, 0); + /* Feed the slow pool hash in if slow */ + if (fastslow == SLOW) + yarrow_hash_iterate(&context, + &random_state.pool[SLOW].hash, sizeof(struct yarrowhash)); - for (i = 0; i < ENTROPYSOURCE; i++) { - for (j = 0; j < ENTROPYBIN; j++) { - bucket = &random_state.pool[FAST].source[i].entropy[j]; - if(bucket->nanotime.tv_sec || bucket->nanotime.tv_nsec) { - BF_set_key(&hashkey, sizeof(struct entropy), (void *)bucket); - BF_cbc_encrypt(v[0], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(&v[0], temp, KEYSIZE); - bucket->nanotime.tv_sec = 0; - bucket->nanotime.tv_nsec = 0; - } - } - } + yarrow_hash_iterate(&context, + &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); /* 2. Compute hash values for all v. _Supposed_ to be computationally * intensive. @@ -160,73 +310,76 @@ reseed(int fastslow) if (random_state.bins > TIMEBIN) random_state.bins = TIMEBIN; for (i = 1; i < random_state.bins; i++) { - bzero((void *)&v[i], KEYSIZE); + yarrow_hash_init(&context, NULL, 0); /* v[i] #= h(v[i-1]) */ - BF_set_key(&hashkey, KEYSIZE, v[i - 1]); - BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(&v[i], temp, KEYSIZE); + yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); /* v[i] #= h(v[0]) */ - BF_set_key(&hashkey, KEYSIZE, v[0]); - BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(&v[i], temp, KEYSIZE); + yarrow_hash_iterate(&context, v[0], KEYSIZE); /* v[i] #= h(i) */ - BF_set_key(&hashkey, sizeof(int), (unsigned char *)&i); - BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(&v[i], temp, KEYSIZE); + yarrow_hash_iterate(&context, &i, sizeof(int)); + /* Return the hashval */ + yarrow_hash_finish(&context, v[i]); } - /* 3. Compute a new Key. */ + /* 3. Compute a new key; h' is the identity function here; + * it is not being ignored! + */ - bzero((void *)hash, KEYSIZE); - BF_set_key(&hashkey, KEYSIZE, (unsigned char *)&random_state.key); - BF_cbc_encrypt(hash, temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(hash, temp, KEYSIZE); - for (i = 1; i < random_state.bins; i++) { - BF_set_key(&hashkey, KEYSIZE, v[i]); - BF_cbc_encrypt(hash, temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); - memcpy(hash, temp, KEYSIZE); - } - BF_set_key(&random_state.key, KEYSIZE, hash); + yarrow_hash_init(&context, NULL, 0); + 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); /* 4. Recompute the counter */ random_state.counter = 0; - BF_cbc_encrypt((unsigned char *)&random_state.counter, temp, - sizeof(random_state.counter), &random_state.key, - random_state.ivec, BF_ENCRYPT); + yarrow_encrypt(&random_state.key, &random_state.counter, temp, + sizeof(random_state.counter)); memcpy(&random_state.counter, temp, random_state.counter); /* 5. Reset entropy estimate accumulators to zero */ for (i = 0; i <= fastslow; i++) { for (j = 0; j < ENTROPYSOURCE; j++) { - random_state.pool[i].source[j].bits = 0; - random_state.pool[i].source[j].frac = 0; + 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; + } } } /* 6. Wipe memory of intermediate values */ - bzero((void *)v, sizeof(v)); - bzero((void *)temp, sizeof(temp)); - bzero((void *)hash, sizeof(hash)); + memset((void *)v, 0, sizeof(v)); + memset((void *)temp, 0, sizeof(temp)); + memset((void *)hash, 0, sizeof(hash)); - /* 7. Dump to seed file (done by external process) */ + /* 7. Dump to seed file */ + /* XXX Not done here yet */ + + /* Release the reseed mutex */ + mtx_exit(&random_reseed_mtx, MTX_DEF); + +#ifdef DEBUG + printf("Reseed finish\n"); +#endif } u_int -read_random(void *buf, u_int count) +read_random(struct proc *proc, void *buf, u_int count) { static u_int64_t genval; static int cur = 0; static int gate = 1; u_int i; u_int retval; - intrmask_t mask; /* The reseed task must not be jumped on */ - mask = splsofttq(); + mtx_enter(&random_reseed_mtx, MTX_DEF); if (gate) { generator_gate(); @@ -237,10 +390,8 @@ read_random(void *buf, u_int count) retval = 0; for (i = 0; i < count; i += sizeof(random_state.counter)) { random_state.counter++; - BF_cbc_encrypt((unsigned char *)&random_state.counter, - (unsigned char *)&genval, - sizeof(random_state.counter), - &random_state.key, random_state.ivec, BF_ENCRYPT); + yarrow_encrypt(&random_state.key, &random_state.counter, + &genval, sizeof(random_state.counter)); memcpy((char *)buf + i, &genval, sizeof(random_state.counter)); if (++random_state.outputblocks >= random_state.gengateinterval) { @@ -253,11 +404,8 @@ read_random(void *buf, u_int count) else { if (!cur) { random_state.counter++; - BF_cbc_encrypt((unsigned char *)&random_state.counter, - (unsigned char *)&genval, - sizeof(random_state.counter), - &random_state.key, random_state.ivec, - BF_ENCRYPT); + yarrow_encrypt(&random_state.key, &random_state.counter, + &genval, sizeof(random_state.counter)); memcpy(buf, &genval, count); cur = sizeof(random_state.counter) - count; if (++random_state.outputblocks >= random_state.gengateinterval) { @@ -275,7 +423,7 @@ read_random(void *buf, u_int count) cur -= retval; } } - splx(mask); + mtx_exit(&random_reseed_mtx, MTX_DEF); return retval; } @@ -283,20 +431,19 @@ void write_random(void *buf, u_int count) { u_int i; - intrmask_t mask; struct timespec timebuf; - /* The reseed task must not be jumped on */ - mask = splsofttq(); /* arbitrarily break the input up into 8-byte chunks */ for (i = 0; i < count; i += 8) { nanotime(&timebuf); random_harvest_internal(&timebuf, (char *)buf + i, 8, 0, 0, RANDOM_WRITE); } + /* Maybe the loop iterated at least once */ if (i > count) i -= 8; + /* Get the last bytes even if the input length is not a multiple of 8 */ count %= 8; if (count) { @@ -304,35 +451,33 @@ write_random(void *buf, u_int count) random_harvest_internal(&timebuf, (char *)buf + i, count, 0, 0, RANDOM_WRITE); } + + /* Explicit reseed */ reseed(FAST); - splx(mask); } static void generator_gate(void) { int i; - unsigned char temp[KEYSIZE]; - intrmask_t mask; + u_char temp[KEYSIZE]; #ifdef DEBUG printf("Generator gate\n"); #endif - /* The reseed task must not be jumped on */ - mask = splsofttq(); - for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { random_state.counter++; - BF_cbc_encrypt((unsigned char *)&random_state.counter, - &(temp[i]), sizeof(random_state.counter), - &random_state.key, random_state.ivec, BF_ENCRYPT); + yarrow_encrypt(&random_state.key, &random_state.counter, + &(temp[i]), sizeof(random_state.counter)); } - BF_set_key(&random_state.key, KEYSIZE, temp); - bzero((void *)temp, KEYSIZE); + yarrow_encrypt_init(&random_state.key, temp, KEYSIZE); + memset((void *)temp, 0, KEYSIZE); - splx(mask); +#ifdef DEBUG + printf("Generator gate finish\n"); +#endif } /* Entropy harvesting routine. This is supposed to be fast; do @@ -343,64 +488,41 @@ static void random_harvest_internal(struct timespec *timep, void *entropy, u_int count, u_int bits, u_int frac, enum esource origin) { - u_int insert; - int which; /* fast or slow */ - struct entropy *bucket; - struct source *source; - struct pool *pool; - intrmask_t mask; + struct harvest *event; u_int64_t entropy_buf; +#if 0 #ifdef DEBUG printf("Random harvest\n"); #endif - if (origin < ENTROPYSOURCE) { - - /* Called inside irq handlers; protect from interference */ - mask = splhigh(); - - which = random_state.which; - pool = &random_state.pool[which]; - source = &pool->source[origin]; - - insert = source->current + 1; - if (insert >= ENTROPYBIN) - insert = 0; +#endif + event = malloc(sizeof(struct harvest), M_TEMP, M_NOWAIT); - bucket = &source->entropy[insert]; + if (origin < ENTROPYSOURCE && event != NULL) { - if (!bucket->nanotime.tv_sec && !bucket->nanotime.tv_nsec) { + /* nanotime provides clock jitter */ + event->time = *timep; - /* nanotime provides clock jitter */ - bucket->nanotime = *timep; + /* the harvested entropy */ + count = count > sizeof(entropy_buf) + ? sizeof(entropy_buf) + : count; + memcpy(event->entropy, entropy, count); - /* the harvested entropy */ - count = count > sizeof(entropy_buf) - ? sizeof(entropy_buf) - : count; - memcpy(&entropy_buf, entropy, count); - /* XOR it in to really foul up the works */ - bucket->data ^= entropy_buf; + event->size = count; + event->bits = bits; + event->frac = frac; + event->source = origin; - /* update the estimates - including "fractional bits" */ - source->bits += bits; - source->frac += frac; - if (source->frac >= 1024) { - source->bits += source->frac / 1024; - source->frac %= 1024; - } - if (source->bits >= pool->thresh) { - /* XXX Slowoverthresh needs to be considered */ - taskqueue_enqueue(taskqueue_swi, ®ate_task[which]); - } + /* protect the queue from simultaneous updates */ + mtx_enter(&random_harvest_mtx, MTX_DEF); - /* bump the insertion point */ - source->current = insert; + /* toggle the pool for next insertion */ + event->pool = random_state.which; + random_state.which = !random_state.which; - /* toggle the pool for next insertion */ - random_state.which = !random_state.which; + TAILQ_INSERT_TAIL(&harvestqueue, event, harvest); - } - splx(mask); + mtx_exit(&random_harvest_mtx, MTX_DEF); } } -- cgit v1.1