yarrow.c revision 74072
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 * $FreeBSD: head/sys/dev/random/yarrow.c 74072 2001-03-10 12:51:55Z markm $ 2762053Smarkm */ 2862053Smarkm 2962053Smarkm#include <sys/param.h> 3062053Smarkm#include <sys/systm.h> 3165686Smarkm#include <sys/kernel.h> 3262053Smarkm#include <sys/libkern.h> 3367365Sjhb#include <sys/mutex.h> 3470834Swollman#include <sys/selinfo.h> 3562053Smarkm#include <sys/random.h> 3674072Smarkm#include <sys/sysctl.h> 3762053Smarkm#include <sys/types.h> 3869168Smarkm 3974072Smarkm#include <crypto/rijndael/rijndael.h> 4069168Smarkm 4167112Smarkm#include <dev/random/hash.h> 4274072Smarkm#include <dev/random/randomdev.h> 4367112Smarkm#include <dev/random/yarrow.h> 4462053Smarkm 4562765Smarkm/* #define DEBUG */ 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 5374072SmarkmSYSCTL_NODE(_kern_random, OID_AUTO, yarrow, CTLFLAG_RW, 0, "Yarrow Parameters"); 5474072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, gengateinterval, 5574072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.gengateinterval, 10, 5674072Smarkm random_check_uint_gengateinterval, "I", "Generator Gate Interval"); 5774072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, bins, 5874072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.bins, 10, 5974072Smarkm random_check_uint_bins, "I", "Execution time tuner"); 6074072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, fastthresh, 6174072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[0].thresh, (3*BLOCKSIZE)/4, 6274072Smarkm random_check_uint_fastthresh, "I", "Fast reseed threshold"); 6374072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowthresh, 6474072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.pool[1].thresh, BLOCKSIZE, 6574072Smarkm random_check_uint_slowthresh, "I", "Slow reseed threshold"); 6674072SmarkmSYSCTL_PROC(_kern_random_yarrow, OID_AUTO, slowoverthresh, 6774072Smarkm CTLTYPE_INT|CTLFLAG_RW, &random_state.slowoverthresh, 2, 6874072Smarkm random_check_uint_slowoverthresh, "I", "Slow over-threshold reseed"); 6974072Smarkm 7062765Smarkmstatic void generator_gate(void); 7174072Smarkmstatic void reseed(u_int); 7262053Smarkm 7362765Smarkm/* Structure holding the entropy state */ 7462765Smarkmstruct random_state random_state; 7562765Smarkm 7665686Smarkm/* The reseed thread mutex */ 7765856Sjhbstatic struct mtx random_reseed_mtx; 7862765Smarkm 7974072Smarkm/* Process a single stochastic event off the harvest queue */ 8074072Smarkmvoid 8174072Smarkmrandom_process_event(struct harvest *event) 8262765Smarkm{ 8374072Smarkm u_int pl, src, overthreshhold[2]; 8465686Smarkm struct source *source; 8565686Smarkm 8674072Smarkm /* Unpack the event into the appropriate source accumulator */ 8774072Smarkm pl = random_state.which; 8874072Smarkm source = &random_state.pool[pl].source[event->source]; 8974072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, event->entropy, 9074072Smarkm sizeof(event->entropy)); 9174072Smarkm yarrow_hash_iterate(&random_state.pool[pl].hash, &event->somecounter, 9274072Smarkm sizeof(event->somecounter)); 9374072Smarkm source->frac += event->frac; 9474072Smarkm source->bits += event->bits + source->frac/1024; 9574072Smarkm source->frac %= 1024; 9665686Smarkm 9774072Smarkm /* Count the over-threshold sources in each pool */ 9874072Smarkm for (pl = 0; pl < 2; pl++) { 9974072Smarkm overthreshhold[pl] = 0; 10074072Smarkm for (src = 0; src < ENTROPYSOURCE; src++) { 10174072Smarkm if (random_state.pool[pl].source[src].bits 10274072Smarkm > random_state.pool[pl].thresh) 10374072Smarkm overthreshhold[pl]++; 10465686Smarkm } 10574072Smarkm } 10665686Smarkm 10774072Smarkm /* if any fast source over threshhold, reseed */ 10874072Smarkm if (overthreshhold[FAST]) 10974072Smarkm reseed(FAST); 11065686Smarkm 11174072Smarkm /* if enough slow sources are over threshhold, reseed */ 11274072Smarkm if (overthreshhold[SLOW] >= random_state.slowoverthresh) 11374072Smarkm reseed(SLOW); 11465686Smarkm 11574072Smarkm /* Invert the fast/slow pool selector bit */ 11674072Smarkm random_state.which = !random_state.which; 11762765Smarkm} 11862765Smarkm 11974072Smarkmvoid 12062765Smarkmrandom_init(void) 12162053Smarkm{ 12274072Smarkm int i; 12365686Smarkm 12472364Smarkm /* Yarrow parameters. Do not adjust these unless you have 12572364Smarkm * have a very good clue about what they do! 12672364Smarkm */ 12762765Smarkm random_state.gengateinterval = 10; 12862765Smarkm random_state.bins = 10; 12974072Smarkm random_state.pool[0].thresh = (3*BLOCKSIZE)/4; 13074072Smarkm random_state.pool[1].thresh = BLOCKSIZE; 13162765Smarkm random_state.slowoverthresh = 2; 13262765Smarkm random_state.which = FAST; 13365686Smarkm 13474072Smarkm /* Initialise the fast and slow entropy pools */ 13574072Smarkm for (i = 0; i < 2; i++) 13674072Smarkm yarrow_hash_init(&random_state.pool[i].hash); 13765686Smarkm 13874072Smarkm /* Clear the counter */ 13974072Smarkm for (i = 0; i < 4; i++) 14074072Smarkm random_state.counter[i] = 0; 14169526Smarkm 14274072Smarkm /* Set up a lock for the reseed process */ 14374072Smarkm mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF); 14462053Smarkm} 14562053Smarkm 14662053Smarkmvoid 14762765Smarkmrandom_deinit(void) 14862053Smarkm{ 14965686Smarkm mtx_destroy(&random_reseed_mtx); 15062765Smarkm} 15162765Smarkm 15262765Smarkmstatic void 15374072Smarkmreseed(u_int fastslow) 15462765Smarkm{ 15565686Smarkm /* Interrupt-context stack is a limited resource; make large 15665686Smarkm * structures static. 15763771Smarkm */ 15865686Smarkm static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 15965686Smarkm static struct yarrowhash context; 16065686Smarkm u_char hash[KEYSIZE]; /* h' */ 16165686Smarkm u_char temp[KEYSIZE]; 16274072Smarkm u_int i, j; 16362053Smarkm 16462765Smarkm#ifdef DEBUG 16572200Sbmilekic mtx_lock(&Giant); 16662765Smarkm printf("Reseed type %d\n", fastslow); 16772200Sbmilekic mtx_unlock(&Giant); 16862765Smarkm#endif 16962765Smarkm 17065686Smarkm /* The reseed task must not be jumped on */ 17172200Sbmilekic mtx_lock(&random_reseed_mtx); 17265686Smarkm 17362053Smarkm /* 1. Hash the accumulated entropy into v[0] */ 17462053Smarkm 17574072Smarkm yarrow_hash_init(&context); 17665686Smarkm /* Feed the slow pool hash in if slow */ 17765686Smarkm if (fastslow == SLOW) 17865686Smarkm yarrow_hash_iterate(&context, 17974072Smarkm &random_state.pool[SLOW].hash, 18074072Smarkm sizeof(struct yarrowhash)); 18165686Smarkm yarrow_hash_iterate(&context, 18265686Smarkm &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 18374072Smarkm yarrow_hash_finish(&context, v[0]); 18462765Smarkm 18563771Smarkm /* 2. Compute hash values for all v. _Supposed_ to be computationally 18663771Smarkm * intensive. 18763771Smarkm */ 18862053Smarkm 18962765Smarkm if (random_state.bins > TIMEBIN) 19062765Smarkm random_state.bins = TIMEBIN; 19162765Smarkm for (i = 1; i < random_state.bins; i++) { 19274072Smarkm yarrow_hash_init(&context); 19374072Smarkm /* v[i] #= h(v[i - 1]) */ 19465686Smarkm yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 19562765Smarkm /* v[i] #= h(v[0]) */ 19665686Smarkm yarrow_hash_iterate(&context, v[0], KEYSIZE); 19762765Smarkm /* v[i] #= h(i) */ 19874072Smarkm yarrow_hash_iterate(&context, &i, sizeof(u_int)); 19965686Smarkm /* Return the hashval */ 20065686Smarkm yarrow_hash_finish(&context, v[i]); 20162053Smarkm } 20262053Smarkm 20365686Smarkm /* 3. Compute a new key; h' is the identity function here; 20465686Smarkm * it is not being ignored! 20565686Smarkm */ 20662053Smarkm 20774072Smarkm yarrow_hash_init(&context); 20865686Smarkm yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 20965686Smarkm for (i = 1; i < random_state.bins; i++) 21065686Smarkm yarrow_hash_iterate(&context, &v[i], KEYSIZE); 21165686Smarkm yarrow_hash_finish(&context, temp); 21274072Smarkm yarrow_encrypt_init(&random_state.key, temp); 21362053Smarkm 21462053Smarkm /* 4. Recompute the counter */ 21562053Smarkm 21674072Smarkm for (i = 0; i < 4; i++) 21774072Smarkm random_state.counter[i] = 0; 21874072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, temp); 21974072Smarkm memcpy(random_state.counter, temp, sizeof(random_state.counter)); 22062053Smarkm 22162765Smarkm /* 5. Reset entropy estimate accumulators to zero */ 22262053Smarkm 22362765Smarkm for (i = 0; i <= fastslow; i++) { 22462765Smarkm for (j = 0; j < ENTROPYSOURCE; j++) { 22574072Smarkm random_state.pool[i].source[j].bits = 0; 22674072Smarkm random_state.pool[i].source[j].frac = 0; 22762765Smarkm } 22862765Smarkm } 22962053Smarkm 23062053Smarkm /* 6. Wipe memory of intermediate values */ 23162053Smarkm 23265686Smarkm memset((void *)v, 0, sizeof(v)); 23365686Smarkm memset((void *)temp, 0, sizeof(temp)); 23465686Smarkm memset((void *)hash, 0, sizeof(hash)); 23562053Smarkm 23665686Smarkm /* 7. Dump to seed file */ 23765686Smarkm /* XXX Not done here yet */ 23862053Smarkm 23965686Smarkm /* Release the reseed mutex */ 24072200Sbmilekic mtx_unlock(&random_reseed_mtx); 24165686Smarkm 24265686Smarkm#ifdef DEBUG 24372200Sbmilekic mtx_lock(&Giant); 24465686Smarkm printf("Reseed finish\n"); 24572200Sbmilekic mtx_unlock(&Giant); 24665686Smarkm#endif 24765686Smarkm 24874072Smarkm /* Unblock the device if it was blocked due to being unseeded */ 24974072Smarkm random_unblock(); 25062053Smarkm} 25162053Smarkm 25274072Smarkm/* Internal function to do return processed entropy from the 25374072Smarkm * Yarrow PRNG 25474072Smarkm */ 25562053Smarkmu_int 25667112Smarkmread_random_real(void *buf, u_int count) 25762053Smarkm{ 25863855Smarkm static u_int64_t genval; 25962053Smarkm static int cur = 0; 26062053Smarkm static int gate = 1; 26162053Smarkm u_int i; 26262053Smarkm u_int retval; 26362053Smarkm 26462875Smarkm /* The reseed task must not be jumped on */ 26572200Sbmilekic mtx_lock(&random_reseed_mtx); 26662875Smarkm 26762053Smarkm if (gate) { 26862053Smarkm generator_gate(); 26962765Smarkm random_state.outputblocks = 0; 27062053Smarkm gate = 0; 27162053Smarkm } 27262765Smarkm if (count >= sizeof(random_state.counter)) { 27362053Smarkm retval = 0; 27462765Smarkm for (i = 0; i < count; i += sizeof(random_state.counter)) { 27574072Smarkm random_state.counter[0]++; 27674072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 27774072Smarkm &genval); 27863855Smarkm memcpy((char *)buf + i, &genval, 27963855Smarkm sizeof(random_state.counter)); 28074072Smarkm if (++random_state.outputblocks >= 28174072Smarkm random_state.gengateinterval) { 28262053Smarkm generator_gate(); 28362765Smarkm random_state.outputblocks = 0; 28462053Smarkm } 28562765Smarkm retval += sizeof(random_state.counter); 28662053Smarkm } 28762053Smarkm } 28862053Smarkm else { 28962053Smarkm if (!cur) { 29074072Smarkm random_state.counter[0]++; 29174072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 29274072Smarkm &genval); 29362053Smarkm memcpy(buf, &genval, count); 29462765Smarkm cur = sizeof(random_state.counter) - count; 29574072Smarkm if (++random_state.outputblocks >= 29674072Smarkm random_state.gengateinterval) { 29762053Smarkm generator_gate(); 29862765Smarkm random_state.outputblocks = 0; 29962053Smarkm } 30062053Smarkm retval = count; 30162053Smarkm } 30262053Smarkm else { 30362053Smarkm retval = cur < count ? cur : count; 30462053Smarkm memcpy(buf, 30563855Smarkm (char *)&genval + 30663855Smarkm (sizeof(random_state.counter) - cur), 30762053Smarkm retval); 30862053Smarkm cur -= retval; 30962053Smarkm } 31062053Smarkm } 31172200Sbmilekic mtx_unlock(&random_reseed_mtx); 31262053Smarkm return retval; 31362053Smarkm} 31462053Smarkm 31562765Smarkmstatic void 31662053Smarkmgenerator_gate(void) 31762053Smarkm{ 31874072Smarkm u_int i; 31965686Smarkm u_char temp[KEYSIZE]; 32062053Smarkm 32162765Smarkm#ifdef DEBUG 32272200Sbmilekic mtx_lock(&Giant); 32362875Smarkm printf("Generator gate\n"); 32472200Sbmilekic mtx_unlock(&Giant); 32562765Smarkm#endif 32662875Smarkm 32762765Smarkm for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 32874072Smarkm random_state.counter[0]++; 32974072Smarkm yarrow_encrypt(&random_state.key, random_state.counter, 33074072Smarkm &(temp[i])); 33162053Smarkm } 33262053Smarkm 33374072Smarkm yarrow_encrypt_init(&random_state.key, temp); 33465686Smarkm memset((void *)temp, 0, KEYSIZE); 33562875Smarkm 33665686Smarkm#ifdef DEBUG 33772200Sbmilekic mtx_lock(&Giant); 33865686Smarkm printf("Generator gate finish\n"); 33972200Sbmilekic mtx_unlock(&Giant); 34065686Smarkm#endif 34162053Smarkm} 34262765Smarkm 34369172Smarkm/* Helper routine to perform explicit reseeds */ 34469172Smarkmvoid 34569172Smarkmrandom_reseed(void) 34669172Smarkm{ 34769172Smarkm reseed(FAST); 34869172Smarkm} 349