yarrow.c revision 128059
162053Smarkm/*- 2128059Smarkm * Copyright (c) 2000-2004 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 128059 2004-04-09 15:47:10Z markm $"); 30119418Sobrien 3162053Smarkm#include <sys/param.h> 3265686Smarkm#include <sys/kernel.h> 3374914Sjhb#include <sys/lock.h> 34122871Smarkm#include <sys/malloc.h> 3567365Sjhb#include <sys/mutex.h> 3662053Smarkm#include <sys/random.h> 3774072Smarkm#include <sys/sysctl.h> 38122871Smarkm#include <sys/systm.h> 3969168Smarkm 4074072Smarkm#include <crypto/rijndael/rijndael.h> 41100082Smarkm#include <crypto/sha2/sha2.h> 4269168Smarkm 4367112Smarkm#include <dev/random/hash.h> 44128059Smarkm#include <dev/random/randomdev_soft.h> 4567112Smarkm#include <dev/random/yarrow.h> 4662053Smarkm 4774072SmarkmRANDOM_CHECK_UINT(gengateinterval, 4, 64); 4874072SmarkmRANDOM_CHECK_UINT(bins, 2, 16); 4974072SmarkmRANDOM_CHECK_UINT(fastthresh, BLOCKSIZE/4, BLOCKSIZE); 5074072SmarkmRANDOM_CHECK_UINT(slowthresh, BLOCKSIZE/4, BLOCKSIZE); 5174072SmarkmRANDOM_CHECK_UINT(slowoverthresh, 1, 5); 5274072Smarkm 5389170Smsmith/* Structure holding the entropy state */ 5489170Smsmithstatic struct random_state random_state; 5589170Smsmith 5662765Smarkmstatic void generator_gate(void); 5774072Smarkmstatic void reseed(u_int); 5862053Smarkm 5965686Smarkm/* The reseed thread mutex */ 6065856Sjhbstatic struct mtx random_reseed_mtx; 6162765Smarkm 6274072Smarkm/* Process a single stochastic event off the harvest queue */ 6374072Smarkmvoid 6474072Smarkmrandom_process_event(struct harvest *event) 6562765Smarkm{ 6691600Smarkm u_int pl, overthreshhold[2]; 6765686Smarkm struct source *source; 6891600Smarkm enum esource src; 6965686Smarkm 7074072Smarkm /* Unpack the event into the appropriate source accumulator */ 7174072Smarkm pl = random_state.which; 7274072Smarkm source = &random_state.pool[pl].source[event->source]; 7374072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy, 7474072Smarkm sizeof(event->entropy)); 7574072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, 7674072Smarkm sizeof(event->somecounter)); 7774072Smarkm source->frac += event->frac; 7874072Smarkm source->bits += event->bits + source->frac/1024; 7974072Smarkm source->frac %= 1024; 8065686Smarkm 8174072Smarkm /* Count the over-threshold sources in each pool */ 8274072Smarkm for (pl = 0; pl < 2; pl++) { 8374072Smarkm overthreshhold[pl] = 0; 8491600Smarkm for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 8574072Smarkm if (random_state.pool[pl].source[src].bits 8674072Smarkm > random_state.pool[pl].thresh) 8774072Smarkm overthreshhold[pl]++; 8865686Smarkm } 8974072Smarkm } 9065686Smarkm 9174072Smarkm /* if any fast source over threshhold, reseed */ 9274072Smarkm if (overthreshhold[FAST]) 9374072Smarkm reseed(FAST); 9465686Smarkm 9574072Smarkm /* if enough slow sources are over threshhold, reseed */ 9674072Smarkm if (overthreshhold[SLOW] >= random_state.slowoverthresh) 9774072Smarkm reseed(SLOW); 9865686Smarkm 9974072Smarkm /* Invert the fast/slow pool selector bit */ 10074072Smarkm random_state.which = !random_state.which; 10162765Smarkm} 10262765Smarkm 10374072Smarkmvoid 104128059Smarkmrandom_yarrow_init_alg(struct sysctl_ctx_list *clist, struct sysctl_oid *in_o) 10562053Smarkm{ 10674072Smarkm int i; 107128059Smarkm struct sysctl_oid *o, *random_yarrow_o; 10865686Smarkm 10972364Smarkm /* Yarrow parameters. Do not adjust these unless you have 11072364Smarkm * have a very good clue about what they do! 11172364Smarkm */ 112128059Smarkm o = SYSCTL_ADD_NODE(clist, 113128059Smarkm SYSCTL_CHILDREN(in_o), 114128059Smarkm OID_AUTO, "yarrow", CTLFLAG_RW, 0, 115128059Smarkm "Yarrow Parameters"); 116128059Smarkm 117128059Smarkm random_yarrow_o = o; 118128059Smarkm 119128059Smarkm o = SYSCTL_ADD_PROC(clist, 120128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 121128059Smarkm "gengateinterval", CTLTYPE_INT|CTLFLAG_RW, 122128059Smarkm &random_state.gengateinterval, 10, 123128059Smarkm random_check_uint_gengateinterval, "I", 124128059Smarkm "Generation gate interval"); 125128059Smarkm 126128059Smarkm o = SYSCTL_ADD_PROC(clist, 127128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 128128059Smarkm "bins", CTLTYPE_INT|CTLFLAG_RW, 129128059Smarkm &random_state.bins, 10, 130128059Smarkm random_check_uint_bins, "I", 131128059Smarkm "Execution time tuner"); 132128059Smarkm 133128059Smarkm o = SYSCTL_ADD_PROC(clist, 134128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 135128059Smarkm "fastthresh", CTLTYPE_INT|CTLFLAG_RW, 136128059Smarkm &random_state.pool[0].thresh, (3*BLOCKSIZE)/4, 137128059Smarkm random_check_uint_fastthresh, "I", 138128059Smarkm "Fast reseed threshold"); 139128059Smarkm 140128059Smarkm o = SYSCTL_ADD_PROC(clist, 141128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 142128059Smarkm "slowthresh", CTLTYPE_INT|CTLFLAG_RW, 143128059Smarkm &random_state.pool[1].thresh, BLOCKSIZE, 144128059Smarkm random_check_uint_slowthresh, "I", 145128059Smarkm "Slow reseed threshold"); 146128059Smarkm 147128059Smarkm o = SYSCTL_ADD_PROC(clist, 148128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 149128059Smarkm "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW, 150128059Smarkm &random_state.slowoverthresh, 2, 151128059Smarkm random_check_uint_slowoverthresh, "I", 152128059Smarkm "Slow over-threshold reseed"); 153128059Smarkm 15462765Smarkm random_state.gengateinterval = 10; 15562765Smarkm random_state.bins = 10; 15674072Smarkm random_state.pool[0].thresh = (3*BLOCKSIZE)/4; 15774072Smarkm random_state.pool[1].thresh = BLOCKSIZE; 15862765Smarkm random_state.slowoverthresh = 2; 15962765Smarkm random_state.which = FAST; 16065686Smarkm 16174072Smarkm /* Initialise the fast and slow entropy pools */ 16274072Smarkm for (i = 0; i < 2; i++) 16374072Smarkm yarrow_hash_init(&random_state.pool[i].hash); 16465686Smarkm 16574072Smarkm /* Clear the counter */ 16674072Smarkm for (i = 0; i < 4; i++) 16774072Smarkm random_state.counter[i] = 0; 16869526Smarkm 16974072Smarkm /* Set up a lock for the reseed process */ 17093818Sjhb mtx_init(&random_reseed_mtx, "random reseed", NULL, MTX_DEF); 17162053Smarkm} 17262053Smarkm 17362053Smarkmvoid 174128059Smarkmrandom_yarrow_deinit_alg(void) 17562053Smarkm{ 17665686Smarkm mtx_destroy(&random_reseed_mtx); 17762765Smarkm} 17862765Smarkm 17962765Smarkmstatic void 18074072Smarkmreseed(u_int fastslow) 18162765Smarkm{ 18265686Smarkm /* Interrupt-context stack is a limited resource; make large 18365686Smarkm * structures static. 18463771Smarkm */ 18565686Smarkm static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 18665686Smarkm static struct yarrowhash context; 18765686Smarkm u_char hash[KEYSIZE]; /* h' */ 18865686Smarkm u_char temp[KEYSIZE]; 18991600Smarkm u_int i; 19091600Smarkm enum esource j; 19162053Smarkm 19265686Smarkm /* The reseed task must not be jumped on */ 19372200Sbmilekic mtx_lock(&random_reseed_mtx); 19465686Smarkm 19562053Smarkm /* 1. Hash the accumulated entropy into v[0] */ 19662053Smarkm 19774072Smarkm yarrow_hash_init(&context); 19865686Smarkm /* Feed the slow pool hash in if slow */ 19965686Smarkm if (fastslow == SLOW) 20065686Smarkm yarrow_hash_iterate(&context, 20174072Smarkm &random_state.pool[SLOW].hash, 20274072Smarkm sizeof(struct yarrowhash)); 20365686Smarkm yarrow_hash_iterate(&context, 20465686Smarkm &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 20574072Smarkm yarrow_hash_finish(&context, v[0]); 20662765Smarkm 20763771Smarkm /* 2. Compute hash values for all v. _Supposed_ to be computationally 20863771Smarkm * intensive. 20963771Smarkm */ 21062053Smarkm 21162765Smarkm if (random_state.bins > TIMEBIN) 21262765Smarkm random_state.bins = TIMEBIN; 21362765Smarkm for (i = 1; i < random_state.bins; i++) { 21474072Smarkm yarrow_hash_init(&context); 21574072Smarkm /* v[i] #= h(v[i - 1]) */ 21665686Smarkm yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 21762765Smarkm /* v[i] #= h(v[0]) */ 21865686Smarkm yarrow_hash_iterate(&context, v[0], KEYSIZE); 21962765Smarkm /* v[i] #= h(i) */ 22074072Smarkm yarrow_hash_iterate(&context, &i, sizeof(u_int)); 22165686Smarkm /* Return the hashval */ 22265686Smarkm yarrow_hash_finish(&context, v[i]); 22362053Smarkm } 22462053Smarkm 22565686Smarkm /* 3. Compute a new key; h' is the identity function here; 22665686Smarkm * it is not being ignored! 22765686Smarkm */ 22862053Smarkm 22974072Smarkm yarrow_hash_init(&context); 23065686Smarkm yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 23165686Smarkm for (i = 1; i < random_state.bins; i++) 23265686Smarkm yarrow_hash_iterate(&context, &v[i], KEYSIZE); 23365686Smarkm yarrow_hash_finish(&context, temp); 23474072Smarkm yarrow_encrypt_init(&random_state.key, temp); 23562053Smarkm 23662053Smarkm /* 4. Recompute the counter */ 23762053Smarkm 23874072Smarkm for (i = 0; i < 4; i++) 23974072Smarkm random_state.counter[i] = 0; 24074072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, temp); 24174072Smarkm memcpy(random_state.counter, temp, sizeof(random_state.counter)); 24262053Smarkm 24362765Smarkm /* 5. Reset entropy estimate accumulators to zero */ 24462053Smarkm 24562765Smarkm for (i = 0; i <= fastslow; i++) { 24691600Smarkm for (j = RANDOM_START; j < ENTROPYSOURCE; j++) { 24774072Smarkm random_state.pool[i].source[j].bits = 0; 24874072Smarkm random_state.pool[i].source[j].frac = 0; 24962765Smarkm } 25062765Smarkm } 25162053Smarkm 25262053Smarkm /* 6. Wipe memory of intermediate values */ 25362053Smarkm 25465686Smarkm memset((void *)v, 0, sizeof(v)); 25565686Smarkm memset((void *)temp, 0, sizeof(temp)); 25665686Smarkm memset((void *)hash, 0, sizeof(hash)); 25762053Smarkm 25865686Smarkm /* 7. Dump to seed file */ 25965686Smarkm /* XXX Not done here yet */ 26062053Smarkm 26165686Smarkm /* Release the reseed mutex */ 26272200Sbmilekic mtx_unlock(&random_reseed_mtx); 26365686Smarkm 26474072Smarkm /* Unblock the device if it was blocked due to being unseeded */ 265128059Smarkm random_yarrow_unblock(); 26662053Smarkm} 26762053Smarkm 268100082Smarkm/* Internal function to return processed entropy from the PRNG */ 26991600Smarkmint 270128059Smarkmrandom_yarrow_read(void *buf, int count) 27162053Smarkm{ 27262053Smarkm static int cur = 0; 27362053Smarkm static int gate = 1; 27474908Smarkm static u_char genval[KEYSIZE]; 275107789Smarkm size_t tomove; 27691600Smarkm int i; 27791600Smarkm int retval; 27862053Smarkm 27962875Smarkm /* The reseed task must not be jumped on */ 28072200Sbmilekic mtx_lock(&random_reseed_mtx); 28162875Smarkm 28262053Smarkm if (gate) { 28362053Smarkm generator_gate(); 28462765Smarkm random_state.outputblocks = 0; 28562053Smarkm gate = 0; 28662053Smarkm } 28791600Smarkm if (count > 0 && (size_t)count >= sizeof(random_state.counter)) { 28862053Smarkm retval = 0; 28991600Smarkm for (i = 0; i < count; i += (int)sizeof(random_state.counter)) { 29074072Smarkm random_state.counter[0]++; 29174072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 29274908Smarkm genval); 293107789Smarkm tomove = min(count - i, sizeof(random_state.counter)); 294107789Smarkm memcpy((char *)buf + i, genval, tomove); 29574072Smarkm if (++random_state.outputblocks >= 29674072Smarkm random_state.gengateinterval) { 29762053Smarkm generator_gate(); 29862765Smarkm random_state.outputblocks = 0; 29962053Smarkm } 300107789Smarkm retval += (int)tomove; 30162053Smarkm } 30262053Smarkm } 30362053Smarkm else { 30462053Smarkm if (!cur) { 30574072Smarkm random_state.counter[0]++; 30674072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 30774908Smarkm genval); 30891600Smarkm memcpy(buf, genval, (size_t)count); 30991600Smarkm cur = (int)sizeof(random_state.counter) - count; 31074072Smarkm if (++random_state.outputblocks >= 31174072Smarkm random_state.gengateinterval) { 31262053Smarkm generator_gate(); 31362765Smarkm random_state.outputblocks = 0; 31462053Smarkm } 31562053Smarkm retval = count; 31662053Smarkm } 31762053Smarkm else { 318128059Smarkm retval = MIN(cur, count); 31991600Smarkm memcpy(buf, 32091600Smarkm &genval[(int)sizeof(random_state.counter) - cur], 32191600Smarkm (size_t)retval); 32262053Smarkm cur -= retval; 32362053Smarkm } 32462053Smarkm } 32572200Sbmilekic mtx_unlock(&random_reseed_mtx); 32662053Smarkm return retval; 32762053Smarkm} 32862053Smarkm 32962765Smarkmstatic void 33062053Smarkmgenerator_gate(void) 33162053Smarkm{ 33274072Smarkm u_int i; 33365686Smarkm u_char temp[KEYSIZE]; 33462053Smarkm 33562765Smarkm for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 33674072Smarkm random_state.counter[0]++; 33774072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 33874072Smarkm &(temp[i])); 33962053Smarkm } 34062053Smarkm 34174072Smarkm yarrow_encrypt_init(&random_state.key, temp); 34265686Smarkm memset((void *)temp, 0, KEYSIZE); 34362875Smarkm 34462053Smarkm} 34562765Smarkm 34669172Smarkm/* Helper routine to perform explicit reseeds */ 34769172Smarkmvoid 348128059Smarkmrandom_yarrow_reseed(void) 34969172Smarkm{ 350100082Smarkm reseed(SLOW); 35169172Smarkm} 352