yarrow.c revision 69168
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 69168 2000-11-25 17:09:01Z 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/libkern.h> 39#include <sys/malloc.h> 40#include <sys/mutex.h> 41#include <sys/select.h> 42#include <sys/random.h> 43#include <sys/types.h> 44#include <sys/unistd.h> 45 46#include <machine/cpu.h> 47 48#include <crypto/blowfish/blowfish.h> 49 50#include <dev/random/hash.h> 51#include <dev/random/yarrow.h> 52 53/* #define DEBUG */ 54/* #define DEBUG1 */ /* Very noisy - prints plenty harvesting stats */ 55 56static void generator_gate(void); 57static void reseed(int); 58static void random_harvest_internal(u_int64_t, void *, u_int, u_int, u_int, enum esource); 59 60static void random_kthread(void *); 61 62/* Structure holding the entropy state */ 63struct random_state random_state; 64 65/* Queue holding harvested entropy */ 66TAILQ_HEAD(harvestqueue, harvest) harvestqueue, 67 initqueue = TAILQ_HEAD_INITIALIZER(harvestqueue); 68 69/* These are used to queue harvested packets of entropy. The entropy 70 * buffer size is pretty arbitrary. 71 */ 72struct harvest { 73 u_int64_t somecounter; /* fast counter for clock jitter */ 74 u_char entropy[HARVESTSIZE]; /* the harvested entropy */ 75 u_int size, bits, frac; /* stats about the entropy */ 76 enum esource source; /* stats about the entropy */ 77 u_int pool; /* which pool this goes into */ 78 TAILQ_ENTRY(harvest) harvest; /* link to next */ 79}; 80 81/* The reseed thread mutex */ 82static struct mtx random_reseed_mtx; 83 84/* The entropy harvest mutex, as well as the mutex associated 85 * with the msleep() call during deinit 86 */ 87static struct mtx random_harvest_mtx; 88 89/* <0 to end the kthread, 0 to let it run */ 90static int random_kthread_control = 0; 91 92static struct proc *random_kthread_proc; 93 94static void 95random_kthread(void *arg /* NOTUSED */) 96{ 97 int pl, src, overthreshhold[2]; 98 struct harvest *event; 99 struct source *source; 100#ifdef DEBUG1 101 int queuecount; 102#endif 103 104#ifdef DEBUG 105 printf("At %s, line %d: mtx_owned(&Giant) == %d, mtx_owned(&sched_lock) == %d\n", __FILE__, __LINE__, mtx_owned(&Giant), mtx_owned(&sched_lock)); 106#endif 107 108 for (pl = 0; pl < 2; pl++) 109 yarrow_hash_init(&random_state.pool[pl].hash, NULL, 0); 110 111 for (;;) { 112 113 if (TAILQ_EMPTY(&harvestqueue)) { 114 115 /* Sleep for a second to give the system a chance */ 116 mtx_enter(&Giant, MTX_DEF); 117 tsleep(&harvestqueue, PUSER, "rndslp", hz); 118 mtx_exit(&Giant, MTX_DEF); 119 120 } 121 else { 122 123 /* Suck the harvested entropy out of the queue and hash 124 * it into the fast and slow pools. 125 */ 126#ifdef DEBUG1 127 queuecount = 0; 128#endif 129 while (!TAILQ_EMPTY(&harvestqueue)) { 130#ifdef DEBUG1 131 queuecount++; 132#endif 133 mtx_enter(&random_harvest_mtx, MTX_DEF); 134 135 event = TAILQ_FIRST(&harvestqueue); 136 TAILQ_REMOVE(&harvestqueue, event, harvest); 137 138 mtx_exit(&random_harvest_mtx, MTX_DEF); 139 140 source = &random_state.pool[event->pool].source[event->source]; 141 yarrow_hash_iterate(&random_state.pool[event->pool].hash, 142 event->entropy, sizeof(event->entropy)); 143 yarrow_hash_iterate(&random_state.pool[event->pool].hash, 144 &event->somecounter, sizeof(event->somecounter)); 145 source->frac += event->frac; 146 source->bits += event->bits + source->frac/1024; 147 source->frac %= 1024; 148 free(event, M_TEMP); 149 150 } 151#ifdef DEBUG1 152 printf("Harvested %d events\n", queuecount); 153#endif 154 155 /* Count the over-threshold sources in each pool */ 156 for (pl = 0; pl < 2; pl++) { 157 overthreshhold[pl] = 0; 158 for (src = 0; src < ENTROPYSOURCE; src++) { 159 if (random_state.pool[pl].source[src].bits 160 > random_state.pool[pl].thresh) 161 overthreshhold[pl]++; 162 } 163 } 164 165 /* if any fast source over threshhold, reseed */ 166 if (overthreshhold[FAST]) 167 reseed(FAST); 168 169 /* if enough slow sources are over threshhold, reseed */ 170 if (overthreshhold[SLOW] >= random_state.slowoverthresh) 171 reseed(SLOW); 172 173 } 174 175 /* Is the thread scheduled for a shutdown? */ 176 if (random_kthread_control != 0) { 177 if (!TAILQ_EMPTY(&harvestqueue)) { 178#ifdef DEBUG 179 printf("Random cleaning extraneous events\n"); 180#endif 181 mtx_enter(&random_harvest_mtx, MTX_DEF); 182 TAILQ_FOREACH(event, &harvestqueue, harvest) { 183 TAILQ_REMOVE(&harvestqueue, event, harvest); 184 free(event, M_TEMP); 185 } 186 mtx_exit(&random_harvest_mtx, MTX_DEF); 187 } 188#ifdef DEBUG 189 printf("Random kthread setting terminate\n"); 190#endif 191 random_set_wakeup_exit(&random_kthread_control); 192 /* NOTREACHED */ 193 break; 194 } 195 196 } 197 198} 199 200int 201random_init(void) 202{ 203 int error; 204 205#ifdef DEBUG 206 printf("Random initialise\n"); 207#endif 208 209 random_state.gengateinterval = 10; 210 random_state.bins = 10; 211 random_state.pool[0].thresh = 100; 212 random_state.pool[1].thresh = 160; 213 random_state.slowoverthresh = 2; 214 random_state.which = FAST; 215 216 harvestqueue = initqueue; 217 218 /* Initialise the mutexes */ 219 mtx_init(&random_reseed_mtx, "random reseed", MTX_DEF); 220 mtx_init(&random_harvest_mtx, "random harvest", MTX_DEF); 221 222 /* Start the hash/reseed thread */ 223 error = kthread_create(random_kthread, NULL, 224 &random_kthread_proc, RFHIGHPID, "random"); 225 if (error != 0) 226 return error; 227 228 /* Register the randomness harvesting routine */ 229 random_init_harvester(random_harvest_internal, read_random_real); 230 231#ifdef DEBUG 232 printf("Random initalise finish\n"); 233#endif 234 235 return 0; 236} 237 238void 239random_deinit(void) 240{ 241#ifdef DEBUG 242 printf("Random deinitalise\n"); 243#endif 244 245 /* Deregister the randomness harvesting routine */ 246 random_deinit_harvester(); 247 248#ifdef DEBUG 249 printf("Random deinitalise waiting for thread to terminate\n"); 250#endif 251 252 /* Command the hash/reseed thread to end and wait for it to finish */ 253 mtx_enter(&random_harvest_mtx, MTX_DEF); 254 random_kthread_control = -1; 255 msleep((void *)&random_kthread_control, &random_harvest_mtx, PUSER, 256 "rndend", 0); 257 mtx_exit(&random_harvest_mtx, MTX_DEF); 258 259#ifdef DEBUG 260 printf("Random deinitalise removing mutexes\n"); 261#endif 262 263 /* Remove the mutexes */ 264 mtx_destroy(&random_reseed_mtx); 265 mtx_destroy(&random_harvest_mtx); 266 267#ifdef DEBUG 268 printf("Random deinitalise finish\n"); 269#endif 270} 271 272static void 273reseed(int fastslow) 274{ 275 /* Interrupt-context stack is a limited resource; make large 276 * structures static. 277 */ 278 static u_char v[TIMEBIN][KEYSIZE]; /* v[i] */ 279 static struct yarrowhash context; 280 u_char hash[KEYSIZE]; /* h' */ 281 u_char temp[KEYSIZE]; 282 int i, j; 283 284#ifdef DEBUG 285 printf("Reseed type %d\n", fastslow); 286#endif 287 288 /* The reseed task must not be jumped on */ 289 mtx_enter(&random_reseed_mtx, MTX_DEF); 290 291 /* 1. Hash the accumulated entropy into v[0] */ 292 293 yarrow_hash_init(&context, NULL, 0); 294 /* Feed the slow pool hash in if slow */ 295 if (fastslow == SLOW) 296 yarrow_hash_iterate(&context, 297 &random_state.pool[SLOW].hash, sizeof(struct yarrowhash)); 298 299 yarrow_hash_iterate(&context, 300 &random_state.pool[FAST].hash, sizeof(struct yarrowhash)); 301 302 /* 2. Compute hash values for all v. _Supposed_ to be computationally 303 * intensive. 304 */ 305 306 if (random_state.bins > TIMEBIN) 307 random_state.bins = TIMEBIN; 308 for (i = 1; i < random_state.bins; i++) { 309 yarrow_hash_init(&context, NULL, 0); 310 /* v[i] #= h(v[i-1]) */ 311 yarrow_hash_iterate(&context, v[i - 1], KEYSIZE); 312 /* v[i] #= h(v[0]) */ 313 yarrow_hash_iterate(&context, v[0], KEYSIZE); 314 /* v[i] #= h(i) */ 315 yarrow_hash_iterate(&context, &i, sizeof(int)); 316 /* Return the hashval */ 317 yarrow_hash_finish(&context, v[i]); 318 } 319 320 /* 3. Compute a new key; h' is the identity function here; 321 * it is not being ignored! 322 */ 323 324 yarrow_hash_init(&context, NULL, 0); 325 yarrow_hash_iterate(&context, &random_state.key, KEYSIZE); 326 for (i = 1; i < random_state.bins; i++) 327 yarrow_hash_iterate(&context, &v[i], KEYSIZE); 328 yarrow_hash_finish(&context, temp); 329 yarrow_encrypt_init(&random_state.key, temp, KEYSIZE); 330 331 /* 4. Recompute the counter */ 332 333 random_state.counter = 0; 334 yarrow_encrypt(&random_state.key, &random_state.counter, temp, 335 sizeof(random_state.counter)); 336 memcpy(&random_state.counter, temp, random_state.counter); 337 338 /* 5. Reset entropy estimate accumulators to zero */ 339 340 for (i = 0; i <= fastslow; i++) { 341 for (j = 0; j < ENTROPYSOURCE; j++) { 342 if (random_state.pool[i].source[j].bits > 343 random_state.pool[i].thresh) { 344 random_state.pool[i].source[j].bits = 0; 345 random_state.pool[i].source[j].frac = 0; 346 } 347 } 348 } 349 350 /* 6. Wipe memory of intermediate values */ 351 352 memset((void *)v, 0, sizeof(v)); 353 memset((void *)temp, 0, sizeof(temp)); 354 memset((void *)hash, 0, sizeof(hash)); 355 356 /* 7. Dump to seed file */ 357 /* XXX Not done here yet */ 358 359 /* Release the reseed mutex */ 360 mtx_exit(&random_reseed_mtx, MTX_DEF); 361 362#ifdef DEBUG 363 printf("Reseed finish\n"); 364#endif 365 366 if (!random_state.seeded) { 367 random_state.seeded = 1; 368 selwakeup(&random_state.rsel); 369 wakeup(&random_state); 370 } 371 372} 373 374u_int 375read_random_real(void *buf, u_int count) 376{ 377 static u_int64_t genval; 378 static int cur = 0; 379 static int gate = 1; 380 u_int i; 381 u_int retval; 382 383 /* The reseed task must not be jumped on */ 384 mtx_enter(&random_reseed_mtx, MTX_DEF); 385 386 if (gate) { 387 generator_gate(); 388 random_state.outputblocks = 0; 389 gate = 0; 390 } 391 if (count >= sizeof(random_state.counter)) { 392 retval = 0; 393 for (i = 0; i < count; i += sizeof(random_state.counter)) { 394 random_state.counter++; 395 yarrow_encrypt(&random_state.key, &random_state.counter, 396 &genval, sizeof(random_state.counter)); 397 memcpy((char *)buf + i, &genval, 398 sizeof(random_state.counter)); 399 if (++random_state.outputblocks >= random_state.gengateinterval) { 400 generator_gate(); 401 random_state.outputblocks = 0; 402 } 403 retval += sizeof(random_state.counter); 404 } 405 } 406 else { 407 if (!cur) { 408 random_state.counter++; 409 yarrow_encrypt(&random_state.key, &random_state.counter, 410 &genval, sizeof(random_state.counter)); 411 memcpy(buf, &genval, count); 412 cur = sizeof(random_state.counter) - count; 413 if (++random_state.outputblocks >= random_state.gengateinterval) { 414 generator_gate(); 415 random_state.outputblocks = 0; 416 } 417 retval = count; 418 } 419 else { 420 retval = cur < count ? cur : count; 421 memcpy(buf, 422 (char *)&genval + 423 (sizeof(random_state.counter) - cur), 424 retval); 425 cur -= retval; 426 } 427 } 428 mtx_exit(&random_reseed_mtx, MTX_DEF); 429 return retval; 430} 431 432void 433write_random(void *buf, u_int count) 434{ 435 u_int i; 436 437 /* Break the input up into HARVESTSIZE chunks. 438 * The writer has too much control here, so "estimate" the 439 * the entropy as zero. 440 */ 441 for (i = 0; i < count; i += HARVESTSIZE) { 442 random_harvest_internal(get_cyclecount(), (char *)buf + i, 443 HARVESTSIZE, 0, 0, RANDOM_WRITE); 444 } 445 446 /* Maybe the loop iterated at least once */ 447 if (i > count) 448 i -= HARVESTSIZE; 449 450 /* Get the last bytes even if the input length is not 451 * a multiple of HARVESTSIZE. 452 */ 453 count %= HARVESTSIZE; 454 if (count) { 455 random_harvest_internal(get_cyclecount(), (char *)buf + i, count, 456 0, 0, RANDOM_WRITE); 457 } 458 459 /* Explicit reseed */ 460 reseed(FAST); 461} 462 463static void 464generator_gate(void) 465{ 466 int i; 467 u_char temp[KEYSIZE]; 468 469#ifdef DEBUG 470 printf("Generator gate\n"); 471#endif 472 473 for (i = 0; i < KEYSIZE; i += sizeof(random_state.counter)) { 474 random_state.counter++; 475 yarrow_encrypt(&random_state.key, &random_state.counter, 476 &(temp[i]), sizeof(random_state.counter)); 477 } 478 479 yarrow_encrypt_init(&random_state.key, temp, KEYSIZE); 480 memset((void *)temp, 0, KEYSIZE); 481 482#ifdef DEBUG 483 printf("Generator gate finish\n"); 484#endif 485} 486 487/* Entropy harvesting routine. This is supposed to be fast; do 488 * not do anything slow in here! 489 */ 490 491static void 492random_harvest_internal(u_int64_t somecounter, void *entropy, u_int count, 493 u_int bits, u_int frac, enum esource origin) 494{ 495 struct harvest *event; 496 497#ifdef DEBUG1 498 printf("Random harvest\n"); 499#endif 500 event = malloc(sizeof(struct harvest), M_TEMP, M_NOWAIT); 501 502 if (origin < ENTROPYSOURCE && event != NULL) { 503 504 /* fast counter provides clock jitter */ 505 event->somecounter = somecounter; 506 507 /* the harvested entropy */ 508 count = count > sizeof(event->entropy) 509 ? sizeof(event->entropy) 510 : count; 511 memcpy(event->entropy, entropy, count); 512 513 event->size = count; 514 event->bits = bits; 515 event->frac = frac; 516 event->source = origin; 517 518 /* protect the queue from simultaneous updates */ 519 mtx_enter(&random_harvest_mtx, MTX_DEF); 520 521 /* toggle the pool for next insertion */ 522 event->pool = random_state.which; 523 random_state.which = !random_state.which; 524 525 TAILQ_INSERT_TAIL(&harvestqueue, event, harvest); 526 527 mtx_exit(&random_harvest_mtx, MTX_DEF); 528 } 529} 530