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$"); 30119418Sobrien 31256381Smarkm#include "opt_random.h" 32256381Smarkm 3362053Smarkm#include <sys/param.h> 3465686Smarkm#include <sys/kernel.h> 3574914Sjhb#include <sys/lock.h> 36122871Smarkm#include <sys/malloc.h> 3767365Sjhb#include <sys/mutex.h> 3862053Smarkm#include <sys/random.h> 3974072Smarkm#include <sys/sysctl.h> 40122871Smarkm#include <sys/systm.h> 4169168Smarkm 42143418Sume#include <crypto/rijndael/rijndael-api-fst.h> 43100082Smarkm#include <crypto/sha2/sha2.h> 4469168Smarkm 4567112Smarkm#include <dev/random/hash.h> 46254147Sobrien#include <dev/random/random_adaptors.h> 47128059Smarkm#include <dev/random/randomdev_soft.h> 4867112Smarkm#include <dev/random/yarrow.h> 4962053Smarkm 50255362Smarkm#define TIMEBIN 16 /* max value for Pt/t */ 51255362Smarkm 52255362Smarkm#define FAST 0 53255362Smarkm#define SLOW 1 54255362Smarkm 55255362Smarkm/* This is the beastie that needs protecting. It contains all of the 56255362Smarkm * state that we are excited about. 57255362Smarkm * Exactly one is instantiated. 58255362Smarkm */ 59255362Smarkmstatic struct random_state { 60255362Smarkm union { 61255362Smarkm uint8_t byte[BLOCKSIZE]; 62255362Smarkm uint64_t qword[BLOCKSIZE/sizeof(uint64_t)]; 63255362Smarkm } counter; /* C */ 64255362Smarkm struct randomdev_key key; /* K */ 65255362Smarkm u_int gengateinterval; /* Pg */ 66255362Smarkm u_int bins; /* Pt/t */ 67255362Smarkm u_int outputblocks; /* count output blocks for gates */ 68255362Smarkm u_int slowoverthresh; /* slow pool overthreshhold reseed count */ 69255362Smarkm struct pool { 70255362Smarkm struct source { 71255362Smarkm u_int bits; /* estimated bits of entropy */ 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. */ 102256381Smarkm/* TODO: Make a Galois counter instead? */ 103255362Smarkmstatic void 104255362Smarkmincrement_counter(void) 105255362Smarkm{ 106255362Smarkm random_state.counter.qword[0]++; 107255362Smarkm if (!random_state.counter.qword[0]) 108255362Smarkm random_state.counter.qword[1]++; 109255362Smarkm} 110255362Smarkm 11174072Smarkm/* Process a single stochastic event off the harvest queue */ 11274072Smarkmvoid 11374072Smarkmrandom_process_event(struct harvest *event) 11462765Smarkm{ 11591600Smarkm u_int pl, overthreshhold[2]; 11665686Smarkm struct source *source; 11791600Smarkm enum esource src; 11865686Smarkm 119256381Smarkm#if 0 120256381Smarkm /* Do this better with DTrace */ 121256381Smarkm { 122256381Smarkm int i; 123256381Smarkm 124256381Smarkm printf("Harvest:%16jX ", event->somecounter); 125256381Smarkm for (i = 0; i < event->size; i++) 126256381Smarkm printf("%02X", event->entropy[i]); 127256381Smarkm for (; i < 16; i++) 128256381Smarkm printf(" "); 129256381Smarkm printf(" %2d %2d %02X\n", event->size, event->bits, event->source); 130256381Smarkm } 131256381Smarkm#endif 132256381Smarkm 133256381Smarkm /* Accumulate the event into the appropriate pool */ 13474072Smarkm pl = random_state.which; 13574072Smarkm source = &random_state.pool[pl].source[event->source]; 136256381Smarkm randomdev_hash_iterate(&random_state.pool[pl].hash, event, 137256381Smarkm sizeof(*event)); 138256381Smarkm source->bits += event->bits; 13965686Smarkm 14074072Smarkm /* Count the over-threshold sources in each pool */ 14174072Smarkm for (pl = 0; pl < 2; pl++) { 14274072Smarkm overthreshhold[pl] = 0; 14391600Smarkm for (src = RANDOM_START; src < ENTROPYSOURCE; src++) { 14474072Smarkm if (random_state.pool[pl].source[src].bits 14574072Smarkm > random_state.pool[pl].thresh) 14674072Smarkm overthreshhold[pl]++; 14765686Smarkm } 14874072Smarkm } 14965686Smarkm 15074072Smarkm /* if any fast source over threshhold, reseed */ 15174072Smarkm if (overthreshhold[FAST]) 15274072Smarkm reseed(FAST); 15365686Smarkm 15474072Smarkm /* if enough slow sources are over threshhold, reseed */ 15574072Smarkm if (overthreshhold[SLOW] >= random_state.slowoverthresh) 15674072Smarkm reseed(SLOW); 15765686Smarkm 15874072Smarkm /* Invert the fast/slow pool selector bit */ 15974072Smarkm random_state.which = !random_state.which; 16062765Smarkm} 16162765Smarkm 16274072Smarkmvoid 163254147Sobrienrandom_yarrow_init_alg(struct sysctl_ctx_list *clist) 16462053Smarkm{ 16574072Smarkm int i; 166170025Srwatson struct sysctl_oid *random_yarrow_o; 16765686Smarkm 16872364Smarkm /* Yarrow parameters. Do not adjust these unless you have 16972364Smarkm * have a very good clue about what they do! 17072364Smarkm */ 171170025Srwatson random_yarrow_o = SYSCTL_ADD_NODE(clist, 172254147Sobrien SYSCTL_STATIC_CHILDREN(_kern_random), 173128059Smarkm OID_AUTO, "yarrow", CTLFLAG_RW, 0, 174128059Smarkm "Yarrow Parameters"); 175128059Smarkm 176170025Srwatson SYSCTL_ADD_PROC(clist, 177128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 178128059Smarkm "gengateinterval", CTLTYPE_INT|CTLFLAG_RW, 179128059Smarkm &random_state.gengateinterval, 10, 180128059Smarkm random_check_uint_gengateinterval, "I", 181128059Smarkm "Generation gate interval"); 182128059Smarkm 183170025Srwatson SYSCTL_ADD_PROC(clist, 184128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 185128059Smarkm "bins", CTLTYPE_INT|CTLFLAG_RW, 186128059Smarkm &random_state.bins, 10, 187128059Smarkm random_check_uint_bins, "I", 188128059Smarkm "Execution time tuner"); 189128059Smarkm 190170025Srwatson SYSCTL_ADD_PROC(clist, 191128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 192128059Smarkm "fastthresh", CTLTYPE_INT|CTLFLAG_RW, 193255362Smarkm &random_state.pool[0].thresh, (3*(BLOCKSIZE*8))/4, 194128059Smarkm random_check_uint_fastthresh, "I", 195128059Smarkm "Fast reseed threshold"); 196128059Smarkm 197170025Srwatson SYSCTL_ADD_PROC(clist, 198128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 199128059Smarkm "slowthresh", CTLTYPE_INT|CTLFLAG_RW, 200255362Smarkm &random_state.pool[1].thresh, (BLOCKSIZE*8), 201128059Smarkm random_check_uint_slowthresh, "I", 202128059Smarkm "Slow reseed threshold"); 203128059Smarkm 204170025Srwatson SYSCTL_ADD_PROC(clist, 205128059Smarkm SYSCTL_CHILDREN(random_yarrow_o), OID_AUTO, 206128059Smarkm "slowoverthresh", CTLTYPE_INT|CTLFLAG_RW, 207128059Smarkm &random_state.slowoverthresh, 2, 208128059Smarkm random_check_uint_slowoverthresh, "I", 209128059Smarkm "Slow over-threshold reseed"); 210128059Smarkm 21162765Smarkm random_state.gengateinterval = 10; 21262765Smarkm random_state.bins = 10; 213255362Smarkm random_state.pool[0].thresh = (3*(BLOCKSIZE*8))/4; 214255362Smarkm random_state.pool[1].thresh = (BLOCKSIZE*8); 21562765Smarkm random_state.slowoverthresh = 2; 21662765Smarkm random_state.which = FAST; 21765686Smarkm 21874072Smarkm /* Initialise the fast and slow entropy pools */ 21974072Smarkm for (i = 0; i < 2; i++) 220255362Smarkm randomdev_hash_init(&random_state.pool[i].hash); 22165686Smarkm 22274072Smarkm /* Clear the counter */ 223255362Smarkm clear_counter(); 22469526Smarkm 22574072Smarkm /* Set up a lock for the reseed process */ 226255362Smarkm mtx_init(&random_reseed_mtx, "Yarrow reseed", NULL, MTX_DEF); 22762053Smarkm} 22862053Smarkm 22962053Smarkmvoid 230128059Smarkmrandom_yarrow_deinit_alg(void) 23162053Smarkm{ 23265686Smarkm mtx_destroy(&random_reseed_mtx); 23362765Smarkm} 23462765Smarkm 23562765Smarkmstatic void 23674072Smarkmreseed(u_int fastslow) 23762765Smarkm{ 23865686Smarkm /* Interrupt-context stack is a limited resource; make large 23965686Smarkm * structures static. 24063771Smarkm */ 241255362Smarkm static uint8_t v[TIMEBIN][KEYSIZE]; /* v[i] */ 242255362Smarkm static struct randomdev_hash context; 243255362Smarkm uint8_t hash[KEYSIZE]; /* h' */ 244255362Smarkm uint8_t temp[KEYSIZE]; 24591600Smarkm u_int i; 24691600Smarkm enum esource j; 24762053Smarkm 248256381Smarkm#if 0 249256381Smarkm printf("Yarrow: %s reseed\n", fastslow == FAST ? "fast" : "slow"); 250256381Smarkm#endif 251256381Smarkm 25265686Smarkm /* The reseed task must not be jumped on */ 25372200Sbmilekic mtx_lock(&random_reseed_mtx); 25465686Smarkm 25562053Smarkm /* 1. Hash the accumulated entropy into v[0] */ 25662053Smarkm 257255362Smarkm randomdev_hash_init(&context); 25865686Smarkm /* Feed the slow pool hash in if slow */ 25965686Smarkm if (fastslow == SLOW) 260255362Smarkm randomdev_hash_iterate(&context, 26174072Smarkm &random_state.pool[SLOW].hash, 262255362Smarkm sizeof(struct randomdev_hash)); 263255362Smarkm randomdev_hash_iterate(&context, 264255362Smarkm &random_state.pool[FAST].hash, sizeof(struct randomdev_hash)); 265255362Smarkm randomdev_hash_finish(&context, v[0]); 26662765Smarkm 26763771Smarkm /* 2. Compute hash values for all v. _Supposed_ to be computationally 26863771Smarkm * intensive. 26963771Smarkm */ 27062053Smarkm 27162765Smarkm if (random_state.bins > TIMEBIN) 27262765Smarkm random_state.bins = TIMEBIN; 27362765Smarkm for (i = 1; i < random_state.bins; i++) { 274255362Smarkm randomdev_hash_init(&context); 27574072Smarkm /* v[i] #= h(v[i - 1]) */ 276255362Smarkm randomdev_hash_iterate(&context, v[i - 1], KEYSIZE); 27762765Smarkm /* v[i] #= h(v[0]) */ 278255362Smarkm randomdev_hash_iterate(&context, v[0], KEYSIZE); 27962765Smarkm /* v[i] #= h(i) */ 280255362Smarkm randomdev_hash_iterate(&context, &i, sizeof(u_int)); 28165686Smarkm /* Return the hashval */ 282255362Smarkm randomdev_hash_finish(&context, v[i]); 28362053Smarkm } 28462053Smarkm 28565686Smarkm /* 3. Compute a new key; h' is the identity function here; 28665686Smarkm * it is not being ignored! 28765686Smarkm */ 28862053Smarkm 289255362Smarkm randomdev_hash_init(&context); 290255362Smarkm randomdev_hash_iterate(&context, &random_state.key, KEYSIZE); 29165686Smarkm for (i = 1; i < random_state.bins; i++) 292255362Smarkm randomdev_hash_iterate(&context, &v[i], KEYSIZE); 293255362Smarkm randomdev_hash_finish(&context, temp); 294255362Smarkm randomdev_encrypt_init(&random_state.key, temp); 29562053Smarkm 29662053Smarkm /* 4. Recompute the counter */ 29762053Smarkm 298255362Smarkm clear_counter(); 299255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, temp, BLOCKSIZE); 300255362Smarkm memcpy(random_state.counter.byte, temp, BLOCKSIZE); 30162053Smarkm 30262765Smarkm /* 5. Reset entropy estimate accumulators to zero */ 30362053Smarkm 304256381Smarkm for (i = 0; i <= fastslow; i++) 305256381Smarkm for (j = RANDOM_START; j < ENTROPYSOURCE; j++) 30674072Smarkm random_state.pool[i].source[j].bits = 0; 30762053Smarkm 30862053Smarkm /* 6. Wipe memory of intermediate values */ 30962053Smarkm 31065686Smarkm memset((void *)v, 0, sizeof(v)); 31165686Smarkm memset((void *)temp, 0, sizeof(temp)); 31265686Smarkm memset((void *)hash, 0, sizeof(hash)); 31362053Smarkm 31465686Smarkm /* 7. Dump to seed file */ 31565686Smarkm /* XXX Not done here yet */ 31662053Smarkm 317153575Sps /* Unblock the device if it was blocked due to being unseeded */ 318255362Smarkm randomdev_unblock(); 319153575Sps 32065686Smarkm /* Release the reseed mutex */ 32172200Sbmilekic mtx_unlock(&random_reseed_mtx); 32262053Smarkm} 32362053Smarkm 324100082Smarkm/* Internal function to return processed entropy from the PRNG */ 32591600Smarkmint 326128059Smarkmrandom_yarrow_read(void *buf, int count) 32762053Smarkm{ 32862053Smarkm static int cur = 0; 32962053Smarkm static int gate = 1; 330255362Smarkm static uint8_t genval[KEYSIZE]; 331107789Smarkm size_t tomove; 33291600Smarkm int i; 33391600Smarkm int retval; 33462053Smarkm 335256381Smarkm /* Check for final read request */ 336256381Smarkm if (buf == NULL && count == 0) 337256381Smarkm return (0); 338256381Smarkm 33962875Smarkm /* The reseed task must not be jumped on */ 34072200Sbmilekic mtx_lock(&random_reseed_mtx); 34162875Smarkm 34262053Smarkm if (gate) { 34362053Smarkm generator_gate(); 34462765Smarkm random_state.outputblocks = 0; 34562053Smarkm gate = 0; 34662053Smarkm } 347255362Smarkm if (count > 0 && (size_t)count >= BLOCKSIZE) { 34862053Smarkm retval = 0; 349255362Smarkm for (i = 0; i < count; i += BLOCKSIZE) { 350255362Smarkm increment_counter(); 351255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 352255362Smarkm tomove = MIN(count - i, BLOCKSIZE); 353107789Smarkm memcpy((char *)buf + i, genval, tomove); 354255362Smarkm if (++random_state.outputblocks >= random_state.gengateinterval) { 35562053Smarkm generator_gate(); 35662765Smarkm random_state.outputblocks = 0; 35762053Smarkm } 358107789Smarkm retval += (int)tomove; 359174073Ssimon cur = 0; 36062053Smarkm } 36162053Smarkm } 36262053Smarkm else { 36362053Smarkm if (!cur) { 364255362Smarkm increment_counter(); 365255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, genval, BLOCKSIZE); 36691600Smarkm memcpy(buf, genval, (size_t)count); 367255362Smarkm cur = BLOCKSIZE - count; 368255362Smarkm if (++random_state.outputblocks >= random_state.gengateinterval) { 36962053Smarkm generator_gate(); 37062765Smarkm random_state.outputblocks = 0; 37162053Smarkm } 37262053Smarkm retval = count; 37362053Smarkm } 37462053Smarkm else { 375128059Smarkm retval = MIN(cur, count); 376255362Smarkm memcpy(buf, &genval[BLOCKSIZE - cur], (size_t)retval); 37762053Smarkm cur -= retval; 37862053Smarkm } 37962053Smarkm } 38072200Sbmilekic mtx_unlock(&random_reseed_mtx); 381256381Smarkm return (retval); 38262053Smarkm} 38362053Smarkm 38462765Smarkmstatic void 38562053Smarkmgenerator_gate(void) 38662053Smarkm{ 38774072Smarkm u_int i; 388255362Smarkm uint8_t temp[KEYSIZE]; 38962053Smarkm 390255362Smarkm for (i = 0; i < KEYSIZE; i += BLOCKSIZE) { 391255362Smarkm increment_counter(); 392255362Smarkm randomdev_encrypt(&random_state.key, random_state.counter.byte, temp + i, BLOCKSIZE); 39362053Smarkm } 39462053Smarkm 395255362Smarkm randomdev_encrypt_init(&random_state.key, temp); 39665686Smarkm memset((void *)temp, 0, KEYSIZE); 39762053Smarkm} 39862765Smarkm 39969172Smarkm/* Helper routine to perform explicit reseeds */ 40069172Smarkmvoid 401128059Smarkmrandom_yarrow_reseed(void) 40269172Smarkm{ 403256381Smarkm#ifdef RANDOM_DEBUG 404256381Smarkm int i; 405256381Smarkm 406256381Smarkm printf("%s(): fast:", __func__); 407256381Smarkm for (i = RANDOM_START; i < ENTROPYSOURCE; ++i) 408256381Smarkm printf(" %d", random_state.pool[FAST].source[i].bits); 409256381Smarkm printf("\n"); 410256381Smarkm printf("%s(): slow:", __func__); 411256381Smarkm for (i = RANDOM_START; i < ENTROPYSOURCE; ++i) 412256381Smarkm printf(" %d", random_state.pool[SLOW].source[i].bits); 413256381Smarkm printf("\n"); 414256381Smarkm#endif 415100082Smarkm reseed(SLOW); 41669172Smarkm} 417