yarrow.c revision 119418
162053Smarkm/*- 262765Smarkm * Copyright (c) 2000 Mark R V Murray 362053Smarkm * All rights reserved. 462053Smarkm * 562053Smarkm * Redistribution and use in source and binary forms, with or without 662053Smarkm * modification, are permitted provided that the following conditions 762053Smarkm * are met: 862053Smarkm * 1. Redistributions of source code must retain the above copyright 962053Smarkm * notice, this list of conditions and the following disclaimer 1062053Smarkm * in this position and unchanged. 1162053Smarkm * 2. Redistributions in binary form must reproduce the above copyright 1262053Smarkm * notice, this list of conditions and the following disclaimer in the 1362053Smarkm * documentation and/or other materials provided with the distribution. 1462053Smarkm * 1562053Smarkm * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 1662053Smarkm * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 1762053Smarkm * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 1862053Smarkm * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 1962053Smarkm * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 2062053Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2162053Smarkm * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2262053Smarkm * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2362053Smarkm * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 2462053Smarkm * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2562053Smarkm * 2662053Smarkm */ 2762053Smarkm 28119418Sobrien#include <sys/cdefs.h> 29119418Sobrien__FBSDID("$FreeBSD: head/sys/dev/random/yarrow.c 119418 2003-08-24 17:55:58Z obrien $"); 30119418Sobrien 3162053Smarkm#include <sys/param.h> 3262053Smarkm#include <sys/systm.h> 3365686Smarkm#include <sys/kernel.h> 3474914Sjhb#include <sys/lock.h> 3567365Sjhb#include <sys/mutex.h> 3662053Smarkm#include <sys/random.h> 3774072Smarkm#include <sys/sysctl.h> 3869168Smarkm 3974072Smarkm#include <crypto/rijndael/rijndael.h> 40100082Smarkm#include <crypto/sha2/sha2.h> 4169168Smarkm 4267112Smarkm#include <dev/random/hash.h> 4374072Smarkm#include <dev/random/randomdev.h> 4467112Smarkm#include <dev/random/yarrow.h> 4562053Smarkm 4662765Smarkm/* #define DEBUG */ 4762053Smarkm 4874072SmarkmRANDOM_CHECK_UINT(gengateinterval, 4, 64); 4974072SmarkmRANDOM_CHECK_UINT(bins, 2, 16); 5074072SmarkmRANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE); 5174072SmarkmRANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE); 5274072SmarkmRANDOM_CHECK_UINT(slowoverthresh, 1, 5); 5374072Smarkm 5489170Smsmith/* Structure holding the entropy state */ 5589170Smsmithstatic struct random_state random_state; 5689170Smsmith 5774072SmarkmSYSCTL_NODE(_kern_random, OID_AUTO, yarrow, CTLFLAG_RW, 0, "Yarrow Parameters"); 5874072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, gengateinterval, 5974072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.gengateinterval, 10, 6074072Smarkm random_check_uint_gengateinterval, "I", "Generator Gate Interval"); 6174072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, bins, 6274072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.bins, 10, 6374072Smarkm random_check_uint_bins, "I", "Execution time tuner"); 6474072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, fastthresh, 6574072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[0].thresh, (3*BLOCKSIZE)/4, 6674072Smarkm random_check_uint_fastthresh, "I", "Fast reseed threshold"); 6774072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowthresh, 6874072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[1].thresh, BLOCKSIZE, 6974072Smarkm random_check_uint_slowthresh, "I", "Slow reseed threshold"); 7074072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowoverthresh, 7174072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.slowoverthresh, 2, 7274072Smarkm random_check_uint_slowoverthresh, "I", "Slow over-threshold reseed"); 7374072Smarkm 7462765Smarkmstatic void generator_gate(void); 7574072Smarkmstatic void reseed(u_int); 7662053Smarkm 7765686Smarkm/* The reseed thread mutex */ 7865856Sjhbstatic struct mtx random_reseed_mtx; 7962765Smarkm 8074072Smarkm/* Process a single stochastic event off the harvest queue */ 8174072Smarkmvoid 8274072Smarkmrandom_process_event(struct harvest *event) 8362765Smarkm{ 8491600Smarkm u_int pl, overthreshhold[2]; 8565686Smarkm struct source *source; 8691600Smarkm enum esource src; 8765686Smarkm 8874072Smarkm /* Unpack the event into the appropriate source accumulator */ 8974072Smarkm pl = random_state.which; 9074072Smarkm source = &random_state.pool[pl].source[event->source]; 9174072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy, 9274072Smarkm sizeof(event->entropy)); 9374072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, 9474072Smarkm sizeof(event->somecounter)); 9574072Smarkm source->frac += event->frac; 9674072Smarkm source->bits += event->bits + source->frac/1024; 9774072Smarkm source->frac %= 1024; 9865686Smarkm 9974072Smarkm /* Count the over-threshold sources in each pool */ 10074072Smarkm for (pl = 0; pl < 2; pl++) { 10174072Smarkm overthreshhold[pl] = 0; 10291600Smarkm for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 10374072Smarkm if (random_state.pool[pl].source[src].bits 10474072Smarkm > random_state.pool[pl].thresh) 10574072Smarkm overthreshhold[pl]++; 10665686Smarkm } 10774072Smarkm } 10865686Smarkm 10974072Smarkm /* if any fast source over threshhold, reseed */ 11074072Smarkm if (overthreshhold[FAST]) 11174072Smarkm reseed(FAST); 11265686Smarkm 11374072Smarkm /* if enough slow sources are over threshhold, reseed */ 11474072Smarkm if (overthreshhold[SLOW] >= random_state.slowoverthresh) 11574072Smarkm reseed(SLOW); 11665686Smarkm 11774072Smarkm /* Invert the fast/slow pool selector bit */ 11874072Smarkm random_state.which = !random_state.which; 11962765Smarkm} 12062765Smarkm 12174072Smarkmvoid 12262765Smarkmrandom_init(void) 12362053Smarkm{ 12474072Smarkm int i; 12565686Smarkm 12672364Smarkm /* Yarrow parameters. Do not adjust these unless you have 12772364Smarkm * have a very good clue about what they do! 12872364Smarkm */ 12962765Smarkm random_state.gengateinterval = 10; 13062765Smarkm random_state.bins = 10; 13174072Smarkm random_state.pool[0].thresh = (3*BLOCKSIZE)/4; 13274072Smarkm random_state.pool[1].thresh = BLOCKSIZE; 13362765Smarkm random_state.slowoverthresh = 2; 13462765Smarkm random_state.which = FAST; 13565686Smarkm 13674072Smarkm /* Initialise the fast and slow entropy pools */ 13774072Smarkm for (i = 0; i < 2; i++) 13874072Smarkm yarrow_hash_init(&random_state.pool[i].hash); 13965686Smarkm 14074072Smarkm /* Clear the counter */ 14174072Smarkm for (i = 0; i < 4; i++) 14274072Smarkm random_state.counter[i] = 0; 14369526Smarkm 14474072Smarkm /* Set up a lock for the reseed process */ 14593818Sjhb mtx_init(&random_reseed_mtx, "random reseed", NULL, MTX_DEF); 14662053Smarkm} 14762053Smarkm 14862053Smarkmvoid 14962765Smarkmrandom_deinit(void) 15062053Smarkm{ 15165686Smarkm mtx_destroy(&random_reseed_mtx); 15262765Smarkm} 15362765Smarkm 15462765Smarkmstatic void 15574072Smarkmreseed(u_int fastslow) 15662765Smarkm{ 15765686Smarkm /* Interrupt-context stack is a limited resource; make large 15865686Smarkm * structures static. 15963771Smarkm */ 16065686Smarkm static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 16165686Smarkm static struct yarrowhash context; 16265686Smarkm u_char hash[KEYSIZE]; /* h' */ 16365686Smarkm u_char temp[KEYSIZE]; 16491600Smarkm u_int i; 16591600Smarkm enum esource j; 16662053Smarkm 16762765Smarkm#ifdef DEBUG 16862765Smarkm printf("Reseed type %d\n", fastslow); 16962765Smarkm#endif 17062765Smarkm 17165686Smarkm /* The reseed task must not be jumped on */ 17272200Sbmilekic mtx_lock(&random_reseed_mtx); 17365686Smarkm 17462053Smarkm /* 1. Hash the accumulated entropy into v[0] */ 17562053Smarkm 17674072Smarkm yarrow_hash_init(&context); 17765686Smarkm /* Feed the slow pool hash in if slow */ 17865686Smarkm if (fastslow == SLOW) 17965686Smarkm yarrow_hash_iterate(&context, 18074072Smarkm &random_state.pool[SLOW].hash, 18174072Smarkm sizeof(struct yarrowhash)); 18265686Smarkm yarrow_hash_iterate(&context, 18365686Smarkm &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 18474072Smarkm yarrow_hash_finish(&context, v[0]); 18562765Smarkm 18663771Smarkm /* 2. Compute hash values for all v. _Supposed_ to be computationally 18763771Smarkm * intensive. 18863771Smarkm */ 18962053Smarkm 19062765Smarkm if (random_state.bins > TIMEBIN) 19162765Smarkm random_state.bins = TIMEBIN; 19262765Smarkm for (i = 1; i < random_state.bins; i++) { 19374072Smarkm yarrow_hash_init(&context); 19474072Smarkm /* v[i] #= h(v[i - 1]) */ 19565686Smarkm yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 19662765Smarkm /* v[i] #= h(v[0]) */ 19765686Smarkm yarrow_hash_iterate(&context, v[0], KEYSIZE); 19862765Smarkm /* v[i] #= h(i) */ 19974072Smarkm yarrow_hash_iterate(&context, &i, sizeof(u_int)); 20065686Smarkm /* Return the hashval */ 20165686Smarkm yarrow_hash_finish(&context, v[i]); 20262053Smarkm } 20362053Smarkm 20465686Smarkm /* 3. Compute a new key; h' is the identity function here; 20565686Smarkm * it is not being ignored! 20665686Smarkm */ 20762053Smarkm 20874072Smarkm yarrow_hash_init(&context); 20965686Smarkm yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 21065686Smarkm for (i = 1; i < random_state.bins; i++) 21165686Smarkm yarrow_hash_iterate(&context, &v[i], KEYSIZE); 21265686Smarkm yarrow_hash_finish(&context, temp); 21374072Smarkm yarrow_encrypt_init(&random_state.key, temp); 21462053Smarkm 21562053Smarkm /* 4. Recompute the counter */ 21662053Smarkm 21774072Smarkm for (i = 0; i < 4; i++) 21874072Smarkm random_state.counter[i] = 0; 21974072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, temp); 22074072Smarkm memcpy(random_state.counter, temp, sizeof(random_state.counter)); 22162053Smarkm 22262765Smarkm /* 5. Reset entropy estimate accumulators to zero */ 22362053Smarkm 22462765Smarkm for (i = 0; i <= fastslow; i++) { 22591600Smarkm for (j = RANDOM_START; j < ENTROPYSOURCE; j++) { 22674072Smarkm random_state.pool[i].source[j].bits = 0; 22774072Smarkm random_state.pool[i].source[j].frac = 0; 22862765Smarkm } 22962765Smarkm } 23062053Smarkm 23162053Smarkm /* 6. Wipe memory of intermediate values */ 23262053Smarkm 23365686Smarkm memset((void *)v, 0, sizeof(v)); 23465686Smarkm memset((void *)temp, 0, sizeof(temp)); 23565686Smarkm memset((void *)hash, 0, sizeof(hash)); 23662053Smarkm 23765686Smarkm /* 7. Dump to seed file */ 23865686Smarkm /* XXX Not done here yet */ 23962053Smarkm 24065686Smarkm /* Release the reseed mutex */ 24172200Sbmilekic mtx_unlock(&random_reseed_mtx); 24265686Smarkm 24365686Smarkm#ifdef DEBUG 24465686Smarkm printf("Reseed finish\n"); 24565686Smarkm#endif 24665686Smarkm 24774072Smarkm /* Unblock the device if it was blocked due to being unseeded */ 24874072Smarkm random_unblock(); 24962053Smarkm} 25062053Smarkm 251100082Smarkm/* Internal function to return processed entropy from the PRNG */ 25291600Smarkmint 25391600Smarkmread_random_real(void *buf, int count) 25462053Smarkm{ 25562053Smarkm static int cur = 0; 25662053Smarkm static int gate = 1; 25774908Smarkm static u_char genval[KEYSIZE]; 258107789Smarkm size_t tomove; 25991600Smarkm int i; 26091600Smarkm int retval; 26162053Smarkm 26262875Smarkm /* The reseed task must not be jumped on */ 26372200Sbmilekic mtx_lock(&random_reseed_mtx); 26462875Smarkm 26562053Smarkm if (gate) { 26662053Smarkm generator_gate(); 26762765Smarkm random_state.outputblocks = 0; 26862053Smarkm gate = 0; 26962053Smarkm } 27091600Smarkm if (count > 0 && (size_t)count >= sizeof(random_state.counter)) { 27162053Smarkm retval = 0; 27291600Smarkm for (i = 0; i < count; i += (int)sizeof(random_state.counter)) { 27374072Smarkm random_state.counter[0]++; 27474072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 27574908Smarkm genval); 276107789Smarkm tomove = min(count - i, sizeof(random_state.counter)); 277107789Smarkm memcpy((char *)buf + i, genval, tomove); 27874072Smarkm if (++random_state.outputblocks >= 27974072Smarkm random_state.gengateinterval) { 28062053Smarkm generator_gate(); 28162765Smarkm random_state.outputblocks = 0; 28262053Smarkm } 283107789Smarkm retval += (int)tomove; 28462053Smarkm } 28562053Smarkm } 28662053Smarkm else { 28762053Smarkm if (!cur) { 28874072Smarkm random_state.counter[0]++; 28974072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 29074908Smarkm genval); 29191600Smarkm memcpy(buf, genval, (size_t)count); 29291600Smarkm cur = (int)sizeof(random_state.counter) - count; 29374072Smarkm if (++random_state.outputblocks >= 29474072Smarkm random_state.gengateinterval) { 29562053Smarkm generator_gate(); 29662765Smarkm random_state.outputblocks = 0; 29762053Smarkm } 29862053Smarkm retval = count; 29962053Smarkm } 30062053Smarkm else { 30162053Smarkm retval = cur < count ? cur : count; 30291600Smarkm memcpy(buf, 30391600Smarkm &genval[(int)sizeof(random_state.counter) - cur], 30491600Smarkm (size_t)retval); 30562053Smarkm cur -= retval; 30662053Smarkm } 30762053Smarkm } 30872200Sbmilekic mtx_unlock(&random_reseed_mtx); 30962053Smarkm return retval; 31062053Smarkm} 31162053Smarkm 31262765Smarkmstatic void 31362053Smarkmgenerator_gate(void) 31462053Smarkm{ 31574072Smarkm u_int i; 31665686Smarkm u_char temp[KEYSIZE]; 31762053Smarkm 31862765Smarkm#ifdef DEBUG 31962875Smarkm printf("Generator gate\n"); 32062765Smarkm#endif 32162875Smarkm 32262765Smarkm for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 32374072Smarkm random_state.counter[0]++; 32474072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 32574072Smarkm &(temp[i])); 32662053Smarkm } 32762053Smarkm 32874072Smarkm yarrow_encrypt_init(&random_state.key, temp); 32965686Smarkm memset((void *)temp, 0, KEYSIZE); 33062875Smarkm 33165686Smarkm#ifdef DEBUG 33265686Smarkm printf("Generator gate finish\n"); 33365686Smarkm#endif 33462053Smarkm} 33562765Smarkm 33669172Smarkm/* Helper routine to perform explicit reseeds */ 33769172Smarkmvoid 33869172Smarkmrandom_reseed(void) 33969172Smarkm{ 340100082Smarkm reseed(SLOW); 34169172Smarkm} 342