yarrow.c revision 255362
162053Smarkm/*- 2255362Smarkm * Copyright (c) 2000-2013 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 255362 2013-09-07 14:15:13Z 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 40143418Sume#include <crypto/rijndael/rijndael-api-fst.h> 41100082Smarkm#include <crypto/sha2/sha2.h> 4269168Smarkm 4367112Smarkm#include <dev/random/hash.h> 44254147Sobrien#include <dev/random/random_adaptors.h> 45128059Smarkm#include <dev/random/randomdev_soft.h> 4667112Smarkm#include <dev/random/yarrow.h> 4762053Smarkm 48255362Smarkm#define TIMEBIN 16 /* max value for Pt/t */ 49255362Smarkm 50255362Smarkm#define FAST 0 51255362Smarkm#define SLOW 1 52255362Smarkm 53255362Smarkm/* This is the beastie that needs protecting. It contains all of the 54255362Smarkm * state that we are excited about. 55255362Smarkm * Exactly one is instantiated. 56255362Smarkm */ 57255362Smarkmstatic struct random_state { 58255362Smarkm union { 59255362Smarkm uint8_t byte[BLOCKSIZE]; 60255362Smarkm uint64_t qword[BLOCKSIZE/sizeof(uint64_t)]; 61255362Smarkm } counter; /* C */ 62255362Smarkm struct randomdev_key key; /* K */ 63255362Smarkm u_int gengateinterval; /* Pg */ 64255362Smarkm u_int bins; /* Pt/t */ 65255362Smarkm u_int outputblocks; /* count output blocks for gates */ 66255362Smarkm u_int slowoverthresh; /* slow pool overthreshhold reseed count */ 67255362Smarkm struct pool { 68255362Smarkm struct source { 69255362Smarkm u_int bits; /* estimated bits of entropy */ 70255362Smarkm u_int frac; /* fractional bits of entropy 71255362Smarkm (given as 1024/n) */ 72255362Smarkm } source[ENTROPYSOURCE]; 73255362Smarkm u_int thresh; /* pool reseed threshhold */ 74255362Smarkm struct randomdev_hash hash; /* accumulated entropy */ 75255362Smarkm } pool[2]; /* pool[0] is fast, pool[1] is slow */ 76255362Smarkm u_int which; /* toggle - sets the current insertion pool */ 77255362Smarkm} random_state; 78255362Smarkm 7974072SmarkmRANDOM_CHECK_UINT(gengateinterval, 4, 64); 8074072SmarkmRANDOM_CHECK_UINT(bins, 2, 16); 81255362SmarkmRANDOM_CHECK_UINT(fastthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */ 82255362SmarkmRANDOM_CHECK_UINT(slowthresh, (BLOCKSIZE*8)/4, (BLOCKSIZE*8)); /* Bit counts */ 8374072SmarkmRANDOM_CHECK_UINT(slowoverthresh, 1, 5); 8474072Smarkm 8562765Smarkmstatic void generator_gate(void); 8674072Smarkmstatic void reseed(u_int); 8762053Smarkm 8865686Smarkm/* The reseed thread mutex */ 89153575Spsstruct mtx random_reseed_mtx; 9062765Smarkm 91255362Smarkm/* 128-bit C = 0 */ 92255362Smarkm/* Nothing to see here, folks, just an ugly mess. */ 93255362Smarkmstatic void 94255362Smarkmclear_counter(void) 95255362Smarkm{ 96255362Smarkm random_state.counter.qword[0] = 0UL; 97255362Smarkm random_state.counter.qword[1] = 0UL; 98255362Smarkm} 99255362Smarkm 100255362Smarkm/* 128-bit C = C + 1 */ 101255362Smarkm/* Nothing to see here, folks, just an ugly mess. */ 102255362Smarkmstatic void 103255362Smarkmincrement_counter(void) 104255362Smarkm{ 105255362Smarkm random_state.counter.qword[0]++; 106255362Smarkm if (!random_state.counter.qword[0]) 107255362Smarkm random_state.counter.qword[1]++; 108255362Smarkm} 109255362Smarkm 11074072Smarkm/* Process a single stochastic event off the harvest queue */ 11174072Smarkmvoid 11274072Smarkmrandom_process_event(struct harvest *event) 11362765Smarkm{ 11491600Smarkm u_int pl, overthreshhold[2]; 11565686Smarkm struct source *source; 11691600Smarkm enum esource src; 11765686Smarkm 11874072Smarkm /* Unpack the event into the appropriate source accumulator */ 11974072Smarkm pl = random_state.which; 12074072Smarkm source = &random_state.pool[pl].source[event->source]; 121255362Smarkm randomdev_hash_iterate(&random_state.pool[pl].hash, event->entropy, 12274072Smarkm sizeof(event->entropy)); 123255362Smarkm randomdev_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, 12474072Smarkm sizeof(event->somecounter)); 12574072Smarkm source->frac += event->frac; 126255362Smarkm source->bits += event->bits + (source->frac >> 12); /* bits + frac/0x1000 */ 127255362Smarkm source->frac &= 0xFFF; /* Keep the fractional bits */ 12865686Smarkm 12974072Smarkm /* Count the over-threshold sources in each pool */ 13074072Smarkm for (pl = 0; pl < 2; pl++) { 13174072Smarkm overthreshhold[pl] = 0; 13291600Smarkm for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 13374072Smarkm if (random_state.pool[pl].source[src].bits 13474072Smarkm > random_state.pool[pl].thresh) 13574072Smarkm overthreshhold[pl]++; 13665686Smarkm } 13774072Smarkm } 13865686Smarkm 13974072Smarkm /* if any fast source over threshhold, reseed */ 14074072Smarkm if (overthreshhold[FAST]) 14174072Smarkm reseed(FAST); 14265686Smarkm 14374072Smarkm /* if enough slow sources are over threshhold, reseed */ 14474072Smarkm if (overthreshhold[SLOW] >= random_state.slowoverthresh) 14574072Smarkm reseed(SLOW); 14665686Smarkm 14774072Smarkm /* Invert the fast/slow pool selector bit */ 14874072Smarkm random_state.which = !random_state.which; 14962765Smarkm} 15062765Smarkm 15174072Smarkmvoid 152254147Sobrienrandom_yarrow_init_alg(struct sysctl_ctx_list *clist) 15362053Smarkm{ 15474072Smarkm int i; 155170025Srwatson struct sysctl_oid *random_yarrow_o; 15665686Smarkm 15772364Smarkm /* Yarrow parameters. Do not adjust these unless you have 15872364Smarkm * have a very good clue about what they do! 15972364Smarkm */ 160170025Srwatson random_yarrow_o = SYSCTL_ADD_NODE(clist, 161254147Sobrien SYSCTL_STATIC_CHILDREN(_kern_random), 162128059Smarkm OID_AUTO, "yarrow", CTLFLAG_RW, 0, 163128059Smarkm "Yarrow Parameters"); 164128059Smarkm 165170025Srwatson SYSCTL_ADD_PROC(clist, 166128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 167128059Smarkm "gengateinterval", CTLTYPE_INT|CTLFLAG_RW, 168128059Smarkm &random_state.gengateinterval, 10, 169128059Smarkm random_check_uint_gengateinterval, "I", 170128059Smarkm "Generation gate interval"); 171128059Smarkm 172170025Srwatson SYSCTL_ADD_PROC(clist, 173128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 174128059Smarkm "bins", CTLTYPE_INT|CTLFLAG_RW, 175128059Smarkm &random_state.bins, 10, 176128059Smarkm random_check_uint_bins, "I", 177128059Smarkm "Execution time tuner"); 178128059Smarkm 179170025Srwatson SYSCTL_ADD_PROC(clist, 180128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 181128059Smarkm "fastthresh", CTLTYPE_INT|CTLFLAG_RW, 182255362Smarkm &random_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4, 183128059Smarkm random_check_uint_fastthresh, "I", 184128059Smarkm "Fast reseed threshold"); 185128059Smarkm 186170025Srwatson SYSCTL_ADD_PROC(clist, 187128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 188128059Smarkm "slowthresh", CTLTYPE_INT|CTLFLAG_RW, 189255362Smarkm &random_state.pool[1].thresh, (BLOCKSIZE*8), 190128059Smarkm random_check_uint_slowthresh, "I", 191128059Smarkm "Slow reseed threshold"); 192128059Smarkm 193170025Srwatson SYSCTL_ADD_PROC(clist, 194128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 195128059Smarkm "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW, 196128059Smarkm &random_state.slowoverthresh, 2, 197128059Smarkm random_check_uint_slowoverthresh, "I", 198128059Smarkm "Slow over-threshold reseed"); 199128059Smarkm 20062765Smarkm random_state.gengateinterval = 10; 20162765Smarkm random_state.bins = 10; 202255362Smarkm random_state.pool[0].thresh = (3*(BLOCKSIZE*8))/4; 203255362Smarkm random_state.pool[1].thresh = (BLOCKSIZE*8); 20462765Smarkm random_state.slowoverthresh = 2; 20562765Smarkm random_state.which = FAST; 20665686Smarkm 20774072Smarkm /* Initialise the fast and slow entropy pools */ 20874072Smarkm for (i = 0; i < 2; i++) 209255362Smarkm randomdev_hash_init(&random_state.pool[i].hash); 21065686Smarkm 21174072Smarkm /* Clear the counter */ 212255362Smarkm clear_counter(); 21369526Smarkm 21474072Smarkm /* Set up a lock for the reseed process */ 215255362Smarkm mtx_init(&random_reseed_mtx, "Yarrow reseed", NULL, MTX_DEF); 21662053Smarkm} 21762053Smarkm 21862053Smarkmvoid 219128059Smarkmrandom_yarrow_deinit_alg(void) 22062053Smarkm{ 22165686Smarkm mtx_destroy(&random_reseed_mtx); 22262765Smarkm} 22362765Smarkm 22462765Smarkmstatic void 22574072Smarkmreseed(u_int fastslow) 22662765Smarkm{ 22765686Smarkm /* Interrupt-context stack is a limited resource; make large 22865686Smarkm * structures static. 22963771Smarkm */ 230255362Smarkm static uint8_t v[TIMEBIN][KEYSIZE]; /* v[i] */ 231255362Smarkm static struct randomdev_hash context; 232255362Smarkm uint8_t hash[KEYSIZE]; /* h' */ 233255362Smarkm uint8_t temp[KEYSIZE]; 23491600Smarkm u_int i; 23591600Smarkm enum esource j; 23662053Smarkm 23765686Smarkm /* The reseed task must not be jumped on */ 23872200Sbmilekic mtx_lock(&random_reseed_mtx); 23965686Smarkm 24062053Smarkm /* 1. Hash the accumulated entropy into v[0] */ 24162053Smarkm 242255362Smarkm randomdev_hash_init(&context); 24365686Smarkm /* Feed the slow pool hash in if slow */ 24465686Smarkm if (fastslow == SLOW) 245255362Smarkm randomdev_hash_iterate(&context, 24674072Smarkm &random_state.pool[SLOW].hash, 247255362Smarkm sizeof(struct randomdev_hash)); 248255362Smarkm randomdev_hash_iterate(&context, 249255362Smarkm &random_state.pool[FAST].hash, sizeof(struct randomdev_hash)); 250255362Smarkm randomdev_hash_finish(&context, v[0]); 25162765Smarkm 25263771Smarkm /* 2. Compute hash values for all v. _Supposed_ to be computationally 25363771Smarkm * intensive. 25463771Smarkm */ 25562053Smarkm 25662765Smarkm if (random_state.bins > TIMEBIN) 25762765Smarkm random_state.bins = TIMEBIN; 25862765Smarkm for (i = 1; i < random_state.bins; i++) { 259255362Smarkm randomdev_hash_init(&context); 26074072Smarkm /* v[i] #= h(v[i - 1]) */ 261255362Smarkm randomdev_hash_iterate(&context, v[i - 1], KEYSIZE); 26262765Smarkm /* v[i] #= h(v[0]) */ 263255362Smarkm randomdev_hash_iterate(&context, v[0], KEYSIZE); 26462765Smarkm /* v[i] #= h(i) */ 265255362Smarkm randomdev_hash_iterate(&context, &i, sizeof(u_int)); 26665686Smarkm /* Return the hashval */ 267255362Smarkm randomdev_hash_finish(&context, v[i]); 26862053Smarkm } 26962053Smarkm 27065686Smarkm /* 3. Compute a new key; h' is the identity function here; 27165686Smarkm * it is not being ignored! 27265686Smarkm */ 27362053Smarkm 274255362Smarkm randomdev_hash_init(&context); 275255362Smarkm randomdev_hash_iterate(&context, &random_state.key, KEYSIZE); 27665686Smarkm for (i = 1; i < random_state.bins; i++) 277255362Smarkm randomdev_hash_iterate(&context, &v[i], KEYSIZE); 278255362Smarkm randomdev_hash_finish(&context, temp); 279255362Smarkm randomdev_encrypt_init(&random_state.key, temp); 28062053Smarkm 28162053Smarkm /* 4. Recompute the counter */ 28262053Smarkm 283255362Smarkm clear_counter(); 284255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, temp, BLOCKSIZE); 285255362Smarkm memcpy(random_state.counter.byte, temp, BLOCKSIZE); 28662053Smarkm 28762765Smarkm /* 5. Reset entropy estimate accumulators to zero */ 28862053Smarkm 28962765Smarkm for (i = 0; i <= fastslow; i++) { 29091600Smarkm for (j = RANDOM_START; j < ENTROPYSOURCE; j++) { 29174072Smarkm random_state.pool[i].source[j].bits = 0; 29274072Smarkm random_state.pool[i].source[j].frac = 0; 29362765Smarkm } 29462765Smarkm } 29562053Smarkm 29662053Smarkm /* 6. Wipe memory of intermediate values */ 29762053Smarkm 29865686Smarkm memset((void *)v, 0, sizeof(v)); 29965686Smarkm memset((void *)temp, 0, sizeof(temp)); 30065686Smarkm memset((void *)hash, 0, sizeof(hash)); 30162053Smarkm 30265686Smarkm /* 7. Dump to seed file */ 30365686Smarkm /* XXX Not done here yet */ 30462053Smarkm 305153575Sps /* Unblock the device if it was blocked due to being unseeded */ 306255362Smarkm randomdev_unblock(); 307153575Sps 30865686Smarkm /* Release the reseed mutex */ 30972200Sbmilekic mtx_unlock(&random_reseed_mtx); 31062053Smarkm} 31162053Smarkm 312100082Smarkm/* Internal function to return processed entropy from the PRNG */ 31391600Smarkmint 314128059Smarkmrandom_yarrow_read(void *buf, int count) 31562053Smarkm{ 31662053Smarkm static int cur = 0; 31762053Smarkm static int gate = 1; 318255362Smarkm static uint8_t genval[KEYSIZE]; 319107789Smarkm size_t tomove; 32091600Smarkm int i; 32191600Smarkm int retval; 32262053Smarkm 32362875Smarkm /* The reseed task must not be jumped on */ 32472200Sbmilekic mtx_lock(&random_reseed_mtx); 32562875Smarkm 32662053Smarkm if (gate) { 32762053Smarkm generator_gate(); 32862765Smarkm random_state.outputblocks = 0; 32962053Smarkm gate = 0; 33062053Smarkm } 331255362Smarkm if (count > 0 && (size_t)count >= BLOCKSIZE) { 33262053Smarkm retval = 0; 333255362Smarkm for (i = 0; i < count; i += BLOCKSIZE) { 334255362Smarkm increment_counter(); 335255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 336255362Smarkm tomove = MIN(count - i, BLOCKSIZE); 337107789Smarkm memcpy((char *)buf + i, genval, tomove); 338255362Smarkm if (++random_state.outputblocks >= random_state.gengateinterval) { 33962053Smarkm generator_gate(); 34062765Smarkm random_state.outputblocks = 0; 34162053Smarkm } 342107789Smarkm retval += (int)tomove; 343174073Ssimon cur = 0; 34462053Smarkm } 34562053Smarkm } 34662053Smarkm else { 34762053Smarkm if (!cur) { 348255362Smarkm increment_counter(); 349255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 35091600Smarkm memcpy(buf, genval, (size_t)count); 351255362Smarkm cur = BLOCKSIZE - count; 352255362Smarkm if (++random_state.outputblocks >= random_state.gengateinterval) { 35362053Smarkm generator_gate(); 35462765Smarkm random_state.outputblocks = 0; 35562053Smarkm } 35662053Smarkm retval = count; 35762053Smarkm } 35862053Smarkm else { 359128059Smarkm retval = MIN(cur, count); 360255362Smarkm memcpy(buf, &genval[BLOCKSIZE - cur], (size_t)retval); 36162053Smarkm cur -= retval; 36262053Smarkm } 36362053Smarkm } 36472200Sbmilekic mtx_unlock(&random_reseed_mtx); 36562053Smarkm return retval; 36662053Smarkm} 36762053Smarkm 36862765Smarkmstatic void 36962053Smarkmgenerator_gate(void) 37062053Smarkm{ 37174072Smarkm u_int i; 372255362Smarkm uint8_t temp[KEYSIZE]; 37362053Smarkm 374255362Smarkm for (i = 0; i < KEYSIZE; i += BLOCKSIZE) { 375255362Smarkm increment_counter(); 376255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, temp + i, BLOCKSIZE); 37762053Smarkm } 37862053Smarkm 379255362Smarkm randomdev_encrypt_init(&random_state.key, temp); 38065686Smarkm memset((void *)temp, 0, KEYSIZE); 38162053Smarkm} 38262765Smarkm 38369172Smarkm/* Helper routine to perform explicit reseeds */ 38469172Smarkmvoid 385128059Smarkmrandom_yarrow_reseed(void) 38669172Smarkm{ 387100082Smarkm reseed(SLOW); 38869172Smarkm} 389