yarrow.c revision 62765
1255767Sdes/*- 298937Sdes * Copyright (c) 2000 Mark R V Murray 3124208Sdes * All rights reserved. 4124208Sdes * 5124208Sdes * Redistribution and use in source and binary forms, with or without 6124208Sdes * modification, are permitted provided that the following conditions 7124208Sdes * are met: 8124208Sdes * 1. Redistributions of source code must retain the above copyright 9124208Sdes * notice, this list of conditions and the following disclaimer 10124208Sdes * in this position and unchanged. 11124208Sdes * 2. Redistributions in binary form must reproduce the above copyright 12124208Sdes * notice, this list of conditions and the following disclaimer in the 13124208Sdes * documentation and/or other materials provided with the distribution. 14124208Sdes * 15124208Sdes * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16124208Sdes * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17124208Sdes * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18124208Sdes * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19124208Sdes * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20124208Sdes * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21124208Sdes * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22124208Sdes * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23124208Sdes * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24124208Sdes * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25124208Sdes * 26124208Sdes * $FreeBSD: head/sys/dev/random/yarrow.c 62765 2000-07-07 09:03:59Z markm $ 27124208Sdes */ 2898937Sdes 29124208Sdes/* NOTE NOTE NOTE - This is not finished! It will supply numbers, but 30124208Sdes it is not yet cryptographically secure!! */ 3198937Sdes 32124208Sdes#include <sys/param.h> 33124208Sdes#include <sys/systm.h> 34162852Sdes#include <sys/queue.h> 35162852Sdes#include <sys/taskqueue.h> 36162852Sdes#include <sys/linker.h> 37162852Sdes#include <sys/libkern.h> 38162852Sdes#include <sys/mbuf.h> 3998937Sdes#include <sys/random.h> 4098937Sdes#include <sys/time.h> 4198937Sdes#include <sys/types.h> 4298937Sdes#include <crypto/blowfish/blowfish.h> 4398937Sdes 44113908Sdes#include <dev/randomdev/yarrow.h> 45124208Sdes 46162852Sdes/* #define DEBUG */ 4798937Sdes 48124208Sdesstatic void generator_gate(void); 49124208Sdesstatic void reseed(int); 50124208Sdesstatic void random_harvest_internal(struct timespec *nanotime, u_int64_t entropy, u_int bits, u_int frac, u_int source); 51124208Sdes 52124208Sdes/* Structure holding the entropy state */ 53124208Sdesstruct random_state random_state; 54124208Sdes 55124208Sdes/* When enough entropy has been harvested, asynchronously "stir" it in */ 56137015Sdesstatic struct task regate_task; 57137015Sdes 58137015Sdesstatic struct context { 59137015Sdes u_int pool; 60124208Sdes} context = { 0 }; 61124208Sdes 62124208Sdesstatic void 63124208Sdesregate(void *context, int pending) 64124208Sdes{ 65124208Sdes#ifdef DEBUG 66124208Sdes printf("Regate task\n"); 67124208Sdes#endif 68124208Sdes reseed(((struct context *)context)->pool); 69124208Sdes} 70124208Sdes 71124208Sdesvoid 72124208Sdesrandom_init(void) 73124208Sdes{ 74124208Sdes#ifdef DEBUG 75124208Sdes printf("Random init\n"); 76124208Sdes#endif 77124208Sdes random_state.gengateinterval = 10; 78124208Sdes random_state.bins = 10; 79124208Sdes random_state.pool[0].thresh = 100; 80124208Sdes random_state.pool[1].thresh = 160; 81124208Sdes random_state.slowoverthresh = 2; 82124208Sdes random_state.which = FAST; 83124208Sdes TASK_INIT(®ate_task, 0, ®ate, (void *)&context); 84124208Sdes random_init_harvester(random_harvest_internal); 85124208Sdes} 86124208Sdes 87124208Sdesvoid 88124208Sdesrandom_deinit(void) 89124208Sdes{ 90215116Sdes#ifdef DEBUG 91215116Sdes printf("Random deinit\n"); 92215116Sdes#endif 93215116Sdes random_deinit_harvester(); 94215116Sdes} 95124208Sdes 96124208Sdesstatic void 97124208Sdesreseed(int fastslow) 98124208Sdes{ 99124208Sdes unsigned char v[TIMEBIN][KEYSIZE]; /* v[i] */ 100124208Sdes unsigned char hash[KEYSIZE]; /* h' */ 101124208Sdes BF_KEY hashkey; 102124208Sdes unsigned char ivec[8]; 103124208Sdes unsigned char temp[KEYSIZE]; 104124208Sdes struct entropy *bucket; 105124208Sdes int i, j; 106124208Sdes 107124208Sdes#ifdef DEBUG 108124208Sdes printf("Reseed type %d\n", fastslow); 109181111Sdes#endif 110181111Sdes 111181111Sdes /* 1. Hash the accumulated entropy into v[0] */ 112181111Sdes 113181111Sdes bzero((void *)&v[0], KEYSIZE); 114255767Sdes if (fastslow == SLOW) { 115255767Sdes /* Feed a hash of the slow pool into the fast pool */ 116255767Sdes for (i = 0; i < ENTROPYSOURCE; i++) { 117255767Sdes for (j = 0; j < ENTROPYBIN; j++) { 118124208Sdes bucket = &random_state.pool[SLOW].source[i].entropy[j]; 119124208Sdes if(bucket->nanotime.tv_sec || bucket->nanotime.tv_nsec) { 120124208Sdes BF_set_key(&hashkey, sizeof(struct entropy), 121124208Sdes (void *)bucket); 122124208Sdes BF_cbc_encrypt(v[0], temp, KEYSIZE, &hashkey, ivec, 123240075Sdes BF_ENCRYPT); 124124208Sdes memcpy(&v[0], temp, KEYSIZE); 125124208Sdes bucket->nanotime.tv_sec = 0; 126124208Sdes bucket->nanotime.tv_nsec = 0; 127124208Sdes } 128124208Sdes } 129124208Sdes } 130124208Sdes } 131124208Sdes 132124208Sdes for (i = 0; i < ENTROPYSOURCE; i++) { 133124208Sdes for (j = 0; j < ENTROPYBIN; j++) { 134124208Sdes bucket = &random_state.pool[FAST].source[i].entropy[j]; 135124208Sdes if(bucket->nanotime.tv_sec || bucket->nanotime.tv_nsec) { 136124208Sdes BF_set_key(&hashkey, sizeof(struct entropy), (void *)bucket); 137124208Sdes BF_cbc_encrypt(v[0], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 138124208Sdes memcpy(&v[0], temp, KEYSIZE); 139124208Sdes bucket->nanotime.tv_sec = 0; 140124208Sdes bucket->nanotime.tv_nsec = 0; 141124208Sdes } 142124208Sdes } 143124208Sdes } 144124208Sdes 145124208Sdes /* 2. Compute hash values for all v. _Supposed_ to be computationally */ 146255767Sdes /* intensive. */ 147124208Sdes 148124208Sdes if (random_state.bins > TIMEBIN) 149162852Sdes random_state.bins = TIMEBIN; 150162852Sdes for (i = 1; i < random_state.bins; i++) { 151162852Sdes bzero((void *)&v[i], KEYSIZE); 152162852Sdes /* v[i] #= h(v[i-1]) */ 153162852Sdes BF_set_key(&hashkey, KEYSIZE, v[i - 1]); 154124208Sdes BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 15598937Sdes memcpy(&v[i], temp, KEYSIZE); 15698937Sdes /* v[i] #= h(v[0]) */ 157248619Sdes BF_set_key(&hashkey, KEYSIZE, v[0]); 158181111Sdes BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 15998937Sdes memcpy(&v[i], temp, KEYSIZE); 160181111Sdes /* v[i] #= h(i) */ 16198937Sdes BF_set_key(&hashkey, sizeof(int), (unsigned char *)&i); 162124208Sdes BF_cbc_encrypt(v[i], temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 163124208Sdes memcpy(&v[i], temp, KEYSIZE); 164124208Sdes } 165124208Sdes 166124208Sdes /* 3. Compute a new Key. */ 167124208Sdes 168124208Sdes bzero((void *)hash, KEYSIZE); 169124208Sdes BF_set_key(&hashkey, KEYSIZE, (unsigned char *)&random_state.key); 170124208Sdes BF_cbc_encrypt(hash, temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 171181111Sdes memcpy(hash, temp, KEYSIZE); 172181111Sdes for (i = 1; i < random_state.bins; i++) { 173181111Sdes BF_set_key(&hashkey, KEYSIZE, v[i]); 174181111Sdes BF_cbc_encrypt(hash, temp, KEYSIZE, &hashkey, ivec, BF_ENCRYPT); 175181111Sdes memcpy(hash, temp, KEYSIZE); 176181111Sdes } 177181111Sdes BF_set_key(&random_state.key, KEYSIZE, hash); 178181111Sdes 179157016Sdes /* 4. Recompute the counter */ 180157016Sdes 181157016Sdes random_state.counter = 0; 182157016Sdes BF_cbc_encrypt((unsigned char *)&random_state.counter, temp, 183126274Sdes sizeof(random_state.counter), &random_state.key, 184162852Sdes random_state.ivec, BF_ENCRYPT); 185126274Sdes memcpy(&random_state.counter, temp, random_state.counter); 186126274Sdes 187124208Sdes /* 5. Reset entropy estimate accumulators to zero */ 188124208Sdes 189124208Sdes for (i = 0; i <= fastslow; i++) { 190124208Sdes for (j = 0; j < ENTROPYSOURCE; j++) { 191162852Sdes random_state.pool[i].source[j].bits = 0; 192124208Sdes random_state.pool[i].source[j].frac = 0; 193124208Sdes } 194157016Sdes } 195157016Sdes 196157016Sdes /* 6. Wipe memory of intermediate values */ 197157016Sdes 198248619Sdes bzero((void *)v, sizeof(v)); 199248619Sdes bzero((void *)temp, sizeof(temp)); 200248619Sdes bzero((void *)hash, sizeof(hash)); 201248619Sdes 202248619Sdes /* 7. Dump to seed file (XXX done by external process?) */ 203248619Sdes 204248619Sdes} 205248619Sdes 206149749Sdesu_int 207149749Sdesread_random(char *buf, u_int count) 208149749Sdes{ 209149749Sdes static int cur = 0; 210255767Sdes static int gate = 1; 211255767Sdes u_int i; 212255767Sdes u_int retval; 213255767Sdes u_int64_t genval; 214255767Sdes 215162852Sdes if (gate) { 216162852Sdes generator_gate(); 217162852Sdes random_state.outputblocks = 0; 218162852Sdes gate = 0; 219157016Sdes } 220157016Sdes if (count >= sizeof(random_state.counter)) { 221157016Sdes retval = 0; 222157016Sdes for (i = 0; i < count; i += sizeof(random_state.counter)) { 223124208Sdes random_state.counter++; 224124208Sdes BF_cbc_encrypt((unsigned char *)&random_state.counter, 225124208Sdes (unsigned char *)&genval, 226124208Sdes sizeof(random_state.counter), 227204917Sdes &random_state.key, random_state.ivec, BF_ENCRYPT); 228204917Sdes memcpy(&buf[i], &genval, sizeof(random_state.counter)); 229204917Sdes if (++random_state.outputblocks >= random_state.gengateinterval) { 230204917Sdes generator_gate(); 231204917Sdes random_state.outputblocks = 0; 232204917Sdes } 233204917Sdes retval += sizeof(random_state.counter); 234204917Sdes } 235221420Sdes } 236221420Sdes else { 237221420Sdes if (!cur) { 238221420Sdes random_state.counter++; 239124208Sdes BF_cbc_encrypt((unsigned char *)&random_state.counter, 240124208Sdes (unsigned char *)&genval, 241124208Sdes sizeof(random_state.counter), 242124208Sdes &random_state.key, random_state.ivec, 24398937Sdes BF_ENCRYPT); 244124208Sdes memcpy(buf, &genval, count); 24598937Sdes cur = sizeof(random_state.counter) - count; 24698937Sdes if (++random_state.outputblocks >= random_state.gengateinterval) { 24798937Sdes generator_gate(); 248124208Sdes random_state.outputblocks = 0; 249162852Sdes } 250162852Sdes retval = count; 25198937Sdes } 252162852Sdes else { 253162852Sdes retval = cur < count ? cur : count; 254162852Sdes memcpy(buf, 255149749Sdes (char *)&random_state.counter + 25698937Sdes (sizeof(random_state.counter) - retval), 257124208Sdes retval); 258 cur -= retval; 259 } 260 } 261 return retval; 262} 263 264static void 265generator_gate(void) 266{ 267 int i; 268 unsigned char temp[KEYSIZE]; 269 270#ifdef DEBUG 271 /* printf("Generator gate\n"); */ 272#endif 273 for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 274 random_state.counter++; 275 BF_cbc_encrypt((unsigned char *)&random_state.counter, 276 &(temp[i]), sizeof(random_state.counter), 277 &random_state.key, random_state.ivec, BF_ENCRYPT); 278 } 279 280 BF_set_key(&random_state.key, KEYSIZE, temp); 281 bzero((void *)temp, KEYSIZE); 282} 283 284/* Entropy harvesting routine. This is supposed to be fast; do */ 285/* not do anything slow in here! */ 286 287static void 288random_harvest_internal(struct timespec *nanotime, u_int64_t entropy, 289 u_int bits, u_int frac, u_int origin) 290{ 291 u_int insert; 292 int which; /* fast or slow */ 293 struct entropy *bucket; 294 struct source *source; 295 struct pool *pool; 296 297#ifdef DEBUG 298 printf("Random harvest\n"); 299#endif 300 if (origin < ENTROPYSOURCE) { 301 302 which = random_state.which; 303 pool = &random_state.pool[which]; 304 source = &pool->source[origin]; 305 306 insert = source->current + 1; 307 if (insert >= ENTROPYBIN) 308 insert = 0; 309 310 bucket = &source->entropy[insert]; 311 312 if (!bucket->nanotime.tv_sec && !bucket->nanotime.tv_nsec) { 313 314 /* nanotime provides clock jitter */ 315 bucket->nanotime = *nanotime; 316 317 /* the harvested entropy */ 318 bucket->data = entropy; 319 320 /* update the estimates - including "fractional bits" */ 321 source->bits += bits; 322 source->frac += frac; 323 if (source->frac >= 1024) { 324 source->bits += source->frac / 1024; 325 source->frac %= 1024; 326 } 327 context.pool = which; 328 if (source->bits >= pool->thresh) { 329 /* XXX Needs to be multiply queued? */ 330 taskqueue_enqueue(taskqueue_swi, ®ate_task); 331 } 332 333 /* bump the insertion point */ 334 source->current = insert; 335 336 /* toggle the pool for next time */ 337 random_state.which = !random_state.which; 338 339 } 340 } 341} 342