yarrow.c revision 65686
1/*- 2 * Copyright (c) 2000 Mark R V Murray 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer 10 * in this position and unchanged. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 25 * 26 * $FreeBSD: head/sys/dev/random/yarrow.c 65686 2000-09-10 13:52:19Z markm $ 27 */ 28 29/* NOTE NOTE NOTE - This is not finished! It will supply numbers, but 30 * it is not yet cryptographically secure!! 31 */ 32 33#include <sys/param.h> 34#include <sys/systm.h> 35#include <sys/queue.h> 36#include <sys/kernel.h> 37#include <sys/kthread.h> 38#include <sys/linker.h> 39#include <sys/libkern.h> 40#include <sys/malloc.h> 41#include <sys/mbuf.h> 42#include <sys/proc.h> 43#include <sys/random.h> 44#include <sys/time.h> 45#include <sys/types.h> 46#include <machine/mutex.h> 47#include <crypto/blowfish/blowfish.h> 48 49#include <dev/randomdev/hash.h> 50#include <dev/randomdev/yarrow.h> 51 52/* #define DEBUG */ 53/* #define DEBUG1 */ /* Very noisy - prints plenty harvesting stats */ 54 55static void generator_gate(void); 56static void reseed(int); 57static void random_harvest_internal(struct timespec *, void *, u_int, u_int, u_int, enum esource); 58 59static void random_kthread(void *); 60void random_set_wakeup(int *, int); 61void random_set_wakeup_exit(int *, int, int); 62 63/* Structure holding the entropy state */ 64struct random_state random_state; 65 66/* Queue holding harvested entropy */ 67TAILQ_HEAD(harvestqueue, harvest) harvestqueue, 68 initqueue = TAILQ_HEAD_INITIALIZER(harvestqueue); 69 70/* These are used to queue harvested packets of entropy. The entropy 71 * buffer size of 16 is pretty arbitrary. 72 */ 73struct harvest { 74 struct timespec time; /* nanotime for clock jitter */ 75 u_char entropy[16]; /* the harvested entropy */ 76 u_int size, bits, frac; /* stats about the entropy */ 77 enum esource source; /* stats about the entropy */ 78 u_int pool; /* which pool this goes into */ 79 TAILQ_ENTRY(harvest) harvest; /* link to next */ 80}; 81 82/* The reseed thread mutex */ 83static mtx_t random_reseed_mtx; 84 85/* The entropy harvest mutex */ 86static mtx_t random_harvest_mtx; 87 88/* <0 until the kthread starts, 0 for running */ 89static int random_kthread_status = -1; 90 91/* <0 to end the kthread, 0 to let it run */ 92static int random_kthread_control = 0; 93 94static struct proc *random_kthread_proc; 95 96static void 97random_kthread(void *status) 98{ 99 int pl, src, overthreshhold[2]; 100 struct harvest *event; 101 struct source *source; 102#ifdef DEBUG1 103 int queuecount; 104#endif 105 106#ifdef DEBUG 107 printf("At %s, line %d: mtx_owned(&Giant) == %d\n", __FILE__, __LINE__, mtx_owned(&Giant)); 108 printf("At %s, line %d: mtx_owned(&sched_lock) == %d\n", __FILE__, __LINE__, mtx_owned(&sched_lock)); 109#endif 110 random_set_wakeup((int *)status, 0); 111 112 for (pl = 0; pl < 2; pl++) 113 yarrow_hash_init(&random_state.pool[pl].hash, NULL, 0); 114 115 for (;;) { 116 117 if (TAILQ_EMPTY(&harvestqueue)) { 118 119 /* Sleep for a second to give the system a chance */ 120 mtx_enter(&Giant, MTX_DEF); 121 tsleep(&harvestqueue, PUSER, "rndslp", hz); 122 mtx_exit(&Giant, MTX_DEF); 123 124 } 125 else { 126 127 /* Suck the harvested entropy out of the queue and hash 128 * it into the fast and slow pools. 129 */ 130#ifdef DEBUG1 131 queuecount = 0; 132#endif 133 TAILQ_FOREACH(event, &harvestqueue, harvest) { 134#ifdef DEBUG1 135 queuecount++; 136#endif 137 mtx_enter(&random_harvest_mtx, MTX_DEF); 138 139 event = TAILQ_FIRST(&harvestqueue); 140 TAILQ_REMOVE(&harvestqueue, event, harvest); 141 142 mtx_exit(&random_harvest_mtx, MTX_DEF); 143 144 source = &random_state.pool[event->pool].source[event->source]; 145 yarrow_hash_iterate(&random_state.pool[event->pool].hash, 146 event->entropy, sizeof(event->entropy)); 147 yarrow_hash_iterate(&random_state.pool[event->pool].hash, 148 &event->time, sizeof(event->time)); 149 source->frac += event->frac; 150 source->bits += event->bits + source->frac/1024; 151 source->frac %= 1024; 152 free(event, M_TEMP); 153 154 /* XXX abuse tsleep() to get at mi_switch() */ 155 /* tsleep(&harvestqueue, PUSER, "rndprc", 1); */ 156 157 } 158#ifdef DEBUG1 159 printf("Harvested %d events\n", queuecount); 160#endif 161 162 /* Count the over-threshold sources in each pool */ 163 for (pl = 0; pl < 2; pl++) { 164 overthreshhold[pl] = 0; 165 for (src = 0; src < ENTROPYSOURCE; src++) { 166 if (random_state.pool[pl].source[src].bits 167 > random_state.pool[pl].thresh) 168 overthreshhold[pl]++; 169 } 170 } 171 172 /* if any fast source over threshhold, reseed */ 173 if (overthreshhold[FAST]) 174 reseed(FAST); 175 176 /* if enough slow sources are over threshhold, reseed */ 177 if (overthreshhold[SLOW] >= random_state.slowoverthresh) 178 reseed(SLOW); 179 180 } 181 182 /* Is the thread scheduled for a shutdown? */ 183 if (random_kthread_control < 0) { 184 if (!TAILQ_EMPTY(&harvestqueue)) { 185#ifdef DEBUG 186 printf("Random cleaning extraneous events\n"); 187#endif 188 mtx_enter(&random_harvest_mtx, MTX_DEF); 189 TAILQ_FOREACH(event, &harvestqueue, harvest) { 190 TAILQ_REMOVE(&harvestqueue, event, harvest); 191 free(event, M_TEMP); 192 } 193 mtx_exit(&random_harvest_mtx, MTX_DEF); 194 } 195#ifdef DEBUG 196 printf("Random kthread setting terminate\n"); 197#endif 198 random_set_wakeup_exit((int *)status, -1, 0); 199 break; 200 } 201 202 } 203 204} 205 206int 207random_init(void) 208{ 209 int error; 210 211#ifdef DEBUG 212 printf("Random initialise\n"); 213#endif 214 215 random_state.gengateinterval = 10; 216 random_state.bins = 10; 217 random_state.pool[0].thresh = 100; 218 random_state.pool[1].thresh = 160; 219 random_state.slowoverthresh = 2; 220 random_state.which = FAST; 221 222 harvestqueue = initqueue; 223 224 /* Initialise the mutexes */ 225 mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF); 226 mtx_init(&random_harvest_mtx, "random harvest", MTX_DEF); 227 228 /* Start the hash/reseed thread */ 229 error = kthread_create(random_kthread, &random_kthread_status, 230 &random_kthread_proc, 0, "random"); 231 if (error != 0) 232 return error; 233 234 /* Register the randomness harvesting routine */ 235 random_init_harvester(random_harvest_internal); 236 237#ifdef DEBUG 238 printf("Random initalise finish\n"); 239#endif 240 241 return 0; 242} 243 244void 245random_deinit(void) 246{ 247#ifdef DEBUG 248 printf("Random deinitalise\n"); 249#endif 250 251 /* Deregister the randomness harvesting routine */ 252 random_deinit_harvester(); 253 254#ifdef DEBUG 255 printf("Random deinitalise waiting for thread to terminate\n"); 256#endif 257 258 /* Command the hash/reseed thread to end and wait for it to finish */ 259 random_kthread_control = -1; 260 while (random_kthread_status != -1) 261 tsleep(&random_kthread_status, PUSER, "rndend", hz); 262 263#ifdef DEBUG 264 printf("Random deinitalise removing mutexes\n"); 265#endif 266 267 /* Remove the mutexes */ 268 mtx_destroy(&random_reseed_mtx); 269 mtx_destroy(&random_harvest_mtx); 270 271#ifdef DEBUG 272 printf("Random deinitalise finish\n"); 273#endif 274} 275 276static void 277reseed(int fastslow) 278{ 279 /* Interrupt-context stack is a limited resource; make large 280 * structures static. 281 */ 282 static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 283 static struct yarrowhash context; 284 u_char hash[KEYSIZE]; /* h' */ 285 u_char temp[KEYSIZE]; 286 int i, j; 287 288#ifdef DEBUG 289 printf("Reseed type %d\n", fastslow); 290#endif 291 292 /* The reseed task must not be jumped on */ 293 mtx_enter(&random_reseed_mtx, MTX_DEF); 294 295 /* 1. Hash the accumulated entropy into v[0] */ 296 297 yarrow_hash_init(&context, NULL, 0); 298 /* Feed the slow pool hash in if slow */ 299 if (fastslow == SLOW) 300 yarrow_hash_iterate(&context, 301 &random_state.pool[SLOW].hash, sizeof(struct yarrowhash)); 302 303 yarrow_hash_iterate(&context, 304 &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 305 306 /* 2. Compute hash values for all v. _Supposed_ to be computationally 307 * intensive. 308 */ 309 310 if (random_state.bins > TIMEBIN) 311 random_state.bins = TIMEBIN; 312 for (i = 1; i < random_state.bins; i++) { 313 yarrow_hash_init(&context, NULL, 0); 314 /* v[i] #= h(v[i-1]) */ 315 yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 316 /* v[i] #= h(v[0]) */ 317 yarrow_hash_iterate(&context, v[0], KEYSIZE); 318 /* v[i] #= h(i) */ 319 yarrow_hash_iterate(&context, &i, sizeof(int)); 320 /* Return the hashval */ 321 yarrow_hash_finish(&context, v[i]); 322 } 323 324 /* 3. Compute a new key; h' is the identity function here; 325 * it is not being ignored! 326 */ 327 328 yarrow_hash_init(&context, NULL, 0); 329 yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 330 for (i = 1; i < random_state.bins; i++) 331 yarrow_hash_iterate(&context, &v[i], KEYSIZE); 332 yarrow_hash_finish(&context, temp); 333 yarrow_encrypt_init(&random_state.key, temp, KEYSIZE); 334 335 /* 4. Recompute the counter */ 336 337 random_state.counter = 0; 338 yarrow_encrypt(&random_state.key, &random_state.counter, temp, 339 sizeof(random_state.counter)); 340 memcpy(&random_state.counter, temp, random_state.counter); 341 342 /* 5. Reset entropy estimate accumulators to zero */ 343 344 for (i = 0; i <= fastslow; i++) { 345 for (j = 0; j < ENTROPYSOURCE; j++) { 346 if (random_state.pool[i].source[j].bits > 347 random_state.pool[i].thresh) { 348 random_state.pool[i].source[j].bits = 0; 349 random_state.pool[i].source[j].frac = 0; 350 } 351 } 352 } 353 354 /* 6. Wipe memory of intermediate values */ 355 356 memset((void *)v, 0, sizeof(v)); 357 memset((void *)temp, 0, sizeof(temp)); 358 memset((void *)hash, 0, sizeof(hash)); 359 360 /* 7. Dump to seed file */ 361 /* XXX Not done here yet */ 362 363 /* Release the reseed mutex */ 364 mtx_exit(&random_reseed_mtx, MTX_DEF); 365 366#ifdef DEBUG 367 printf("Reseed finish\n"); 368#endif 369 370} 371 372u_int 373read_random(struct proc *proc, void *buf, u_int count) 374{ 375 static u_int64_t genval; 376 static int cur = 0; 377 static int gate = 1; 378 u_int i; 379 u_int retval; 380 381 /* The reseed task must not be jumped on */ 382 mtx_enter(&random_reseed_mtx, MTX_DEF); 383 384 if (gate) { 385 generator_gate(); 386 random_state.outputblocks = 0; 387 gate = 0; 388 } 389 if (count >= sizeof(random_state.counter)) { 390 retval = 0; 391 for (i = 0; i < count; i += sizeof(random_state.counter)) { 392 random_state.counter++; 393 yarrow_encrypt(&random_state.key, &random_state.counter, 394 &genval, sizeof(random_state.counter)); 395 memcpy((char *)buf + i, &genval, 396 sizeof(random_state.counter)); 397 if (++random_state.outputblocks >= random_state.gengateinterval) { 398 generator_gate(); 399 random_state.outputblocks = 0; 400 } 401 retval += sizeof(random_state.counter); 402 } 403 } 404 else { 405 if (!cur) { 406 random_state.counter++; 407 yarrow_encrypt(&random_state.key, &random_state.counter, 408 &genval, sizeof(random_state.counter)); 409 memcpy(buf, &genval, count); 410 cur = sizeof(random_state.counter) - count; 411 if (++random_state.outputblocks >= random_state.gengateinterval) { 412 generator_gate(); 413 random_state.outputblocks = 0; 414 } 415 retval = count; 416 } 417 else { 418 retval = cur < count ? cur : count; 419 memcpy(buf, 420 (char *)&genval + 421 (sizeof(random_state.counter) - cur), 422 retval); 423 cur -= retval; 424 } 425 } 426 mtx_exit(&random_reseed_mtx, MTX_DEF); 427 return retval; 428} 429 430void 431write_random(void *buf, u_int count) 432{ 433 u_int i; 434 struct timespec timebuf; 435 436 /* arbitrarily break the input up into 8-byte chunks */ 437 for (i = 0; i < count; i += 8) { 438 nanotime(&timebuf); 439 random_harvest_internal(&timebuf, (char *)buf + i, 8, 0, 0, 440 RANDOM_WRITE); 441 } 442 443 /* Maybe the loop iterated at least once */ 444 if (i > count) 445 i -= 8; 446 447 /* Get the last bytes even if the input length is not a multiple of 8 */ 448 count %= 8; 449 if (count) { 450 nanotime(&timebuf); 451 random_harvest_internal(&timebuf, (char *)buf + i, count, 0, 0, 452 RANDOM_WRITE); 453 } 454 455 /* Explicit reseed */ 456 reseed(FAST); 457} 458 459static void 460generator_gate(void) 461{ 462 int i; 463 u_char temp[KEYSIZE]; 464 465#ifdef DEBUG 466 printf("Generator gate\n"); 467#endif 468 469 for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 470 random_state.counter++; 471 yarrow_encrypt(&random_state.key, &random_state.counter, 472 &(temp[i]), sizeof(random_state.counter)); 473 } 474 475 yarrow_encrypt_init(&random_state.key, temp, KEYSIZE); 476 memset((void *)temp, 0, KEYSIZE); 477 478#ifdef DEBUG 479 printf("Generator gate finish\n"); 480#endif 481} 482 483/* Entropy harvesting routine. This is supposed to be fast; do 484 * not do anything slow in here! 485 */ 486 487static void 488random_harvest_internal(struct timespec *timep, void *entropy, u_int count, 489 u_int bits, u_int frac, enum esource origin) 490{ 491 struct harvest *event; 492 u_int64_t entropy_buf; 493 494#if 0 495#ifdef DEBUG 496 printf("Random harvest\n"); 497#endif 498#endif 499 event = malloc(sizeof(struct harvest), M_TEMP, M_NOWAIT); 500 501 if (origin < ENTROPYSOURCE && event != NULL) { 502 503 /* nanotime provides clock jitter */ 504 event->time = *timep; 505 506 /* the harvested entropy */ 507 count = count > sizeof(entropy_buf) 508 ? sizeof(entropy_buf) 509 : count; 510 memcpy(event->entropy, entropy, count); 511 512 event->size = count; 513 event->bits = bits; 514 event->frac = frac; 515 event->source = origin; 516 517 /* protect the queue from simultaneous updates */ 518 mtx_enter(&random_harvest_mtx, MTX_DEF); 519 520 /* toggle the pool for next insertion */ 521 event->pool = random_state.which; 522 random_state.which = !random_state.which; 523 524 TAILQ_INSERT_TAIL(&harvestqueue, event, harvest); 525 526 mtx_exit(&random_harvest_mtx, MTX_DEF); 527 } 528} 529