1 /* $NetBSD: rand-fortuna.c,v 1.1.1.1 2011/04/13 18:14:50 elric Exp $ */ 2 3 /* 4 * fortuna.c 5 * Fortuna-like PRNG. 6 * 7 * Copyright (c) 2005 Marko Kreen 8 * All rights reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 * 31 * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $ 32 */ 33 34 #include <config.h> 35 36 #include <stdio.h> 37 #include <stdlib.h> 38 #include <rand.h> 39 #include <heim_threads.h> 40 41 #ifdef KRB5 42 #include <krb5/krb5-types.h> 43 #endif 44 #include <krb5/roken.h> 45 46 #include "randi.h" 47 #include "aes.h" 48 #include "sha.h" 49 50 /* 51 * Why Fortuna-like: There does not seem to be any definitive reference 52 * on Fortuna in the net. Instead this implementation is based on 53 * following references: 54 * 55 * http://en.wikipedia.org/wiki/Fortuna_(PRNG) 56 * - Wikipedia article 57 * http://jlcooke.ca/random/ 58 * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux. 59 */ 60 61 /* 62 * There is some confusion about whether and how to carry forward 63 * the state of the pools. Seems like original Fortuna does not 64 * do it, resetting hash after each request. I guess expecting 65 * feeding to happen more often that requesting. This is absolutely 66 * unsuitable for pgcrypto, as nothing asynchronous happens here. 67 * 68 * J.L. Cooke fixed this by feeding previous hash to new re-initialized 69 * hash context. 70 * 71 * Fortuna predecessor Yarrow requires ability to query intermediate 72 * 'final result' from hash, without affecting it. 73 * 74 * This implementation uses the Yarrow method - asking intermediate 75 * results, but continuing with old state. 76 */ 77 78 79 /* 80 * Algorithm parameters 81 */ 82 83 #define NUM_POOLS 32 84 85 /* in microseconds */ 86 #define RESEED_INTERVAL 100000 /* 0.1 sec */ 87 88 /* for one big request, reseed after this many bytes */ 89 #define RESEED_BYTES (1024*1024) 90 91 /* 92 * Skip reseed if pool 0 has less than this many 93 * bytes added since last reseed. 94 */ 95 #define POOL0_FILL (256/8) 96 97 /* 98 * Algorithm constants 99 */ 100 101 /* Both cipher key size and hash result size */ 102 #define BLOCK 32 103 104 /* cipher block size */ 105 #define CIPH_BLOCK 16 106 107 /* for internal wrappers */ 108 #define MD_CTX SHA256_CTX 109 #define CIPH_CTX AES_KEY 110 111 struct fortuna_state 112 { 113 unsigned char counter[CIPH_BLOCK]; 114 unsigned char result[CIPH_BLOCK]; 115 unsigned char key[BLOCK]; 116 MD_CTX pool[NUM_POOLS]; 117 CIPH_CTX ciph; 118 unsigned reseed_count; 119 struct timeval last_reseed_time; 120 unsigned pool0_bytes; 121 unsigned rnd_pos; 122 int tricks_done; 123 pid_t pid; 124 }; 125 typedef struct fortuna_state FState; 126 127 128 /* 129 * Use our own wrappers here. 130 * - Need to get intermediate result from digest, without affecting it. 131 * - Need re-set key on a cipher context. 132 * - Algorithms are guaranteed to exist. 133 * - No memory allocations. 134 */ 135 136 static void 137 ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen) 138 { 139 AES_set_encrypt_key(key, klen * 8, ctx); 140 } 141 142 static void 143 ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out) 144 { 145 AES_encrypt(in, out, ctx); 146 } 147 148 static void 149 md_init(MD_CTX * ctx) 150 { 151 SHA256_Init(ctx); 152 } 153 154 static void 155 md_update(MD_CTX * ctx, const unsigned char *data, int len) 156 { 157 SHA256_Update(ctx, data, len); 158 } 159 160 static void 161 md_result(MD_CTX * ctx, unsigned char *dst) 162 { 163 SHA256_CTX tmp; 164 165 memcpy(&tmp, ctx, sizeof(*ctx)); 166 SHA256_Final(dst, &tmp); 167 memset(&tmp, 0, sizeof(tmp)); 168 } 169 170 /* 171 * initialize state 172 */ 173 static void 174 init_state(FState * st) 175 { 176 int i; 177 178 memset(st, 0, sizeof(*st)); 179 for (i = 0; i < NUM_POOLS; i++) 180 md_init(&st->pool[i]); 181 st->pid = getpid(); 182 } 183 184 /* 185 * Endianess does not matter. 186 * It just needs to change without repeating. 187 */ 188 static void 189 inc_counter(FState * st) 190 { 191 uint32_t *val = (uint32_t *) st->counter; 192 193 if (++val[0]) 194 return; 195 if (++val[1]) 196 return; 197 if (++val[2]) 198 return; 199 ++val[3]; 200 } 201 202 /* 203 * This is called 'cipher in counter mode'. 204 */ 205 static void 206 encrypt_counter(FState * st, unsigned char *dst) 207 { 208 ciph_encrypt(&st->ciph, st->counter, dst); 209 inc_counter(st); 210 } 211 212 213 /* 214 * The time between reseed must be at least RESEED_INTERVAL 215 * microseconds. 216 */ 217 static int 218 enough_time_passed(FState * st) 219 { 220 int ok; 221 struct timeval tv; 222 struct timeval *last = &st->last_reseed_time; 223 224 gettimeofday(&tv, NULL); 225 226 /* check how much time has passed */ 227 ok = 0; 228 if (tv.tv_sec > last->tv_sec + 1) 229 ok = 1; 230 else if (tv.tv_sec == last->tv_sec + 1) 231 { 232 if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL) 233 ok = 1; 234 } 235 else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL) 236 ok = 1; 237 238 /* reseed will happen, update last_reseed_time */ 239 if (ok) 240 memcpy(last, &tv, sizeof(tv)); 241 242 memset(&tv, 0, sizeof(tv)); 243 244 return ok; 245 } 246 247 /* 248 * generate new key from all the pools 249 */ 250 static void 251 reseed(FState * st) 252 { 253 unsigned k; 254 unsigned n; 255 MD_CTX key_md; 256 unsigned char buf[BLOCK]; 257 258 /* set pool as empty */ 259 st->pool0_bytes = 0; 260 261 /* 262 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then. 263 */ 264 n = ++st->reseed_count; 265 266 /* 267 * The goal: use k-th pool only 1/(2^k) of the time. 268 */ 269 md_init(&key_md); 270 for (k = 0; k < NUM_POOLS; k++) 271 { 272 md_result(&st->pool[k], buf); 273 md_update(&key_md, buf, BLOCK); 274 275 if (n & 1 || !n) 276 break; 277 n >>= 1; 278 } 279 280 /* add old key into mix too */ 281 md_update(&key_md, st->key, BLOCK); 282 283 /* add pid to make output diverse after fork() */ 284 md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid)); 285 286 /* now we have new key */ 287 md_result(&key_md, st->key); 288 289 /* use new key */ 290 ciph_init(&st->ciph, st->key, BLOCK); 291 292 memset(&key_md, 0, sizeof(key_md)); 293 memset(buf, 0, BLOCK); 294 } 295 296 /* 297 * Pick a random pool. This uses key bytes as random source. 298 */ 299 static unsigned 300 get_rand_pool(FState * st) 301 { 302 unsigned rnd; 303 304 /* 305 * This slightly prefers lower pools - thats OK. 306 */ 307 rnd = st->key[st->rnd_pos] % NUM_POOLS; 308 309 st->rnd_pos++; 310 if (st->rnd_pos >= BLOCK) 311 st->rnd_pos = 0; 312 313 return rnd; 314 } 315 316 /* 317 * update pools 318 */ 319 static void 320 add_entropy(FState * st, const unsigned char *data, unsigned len) 321 { 322 unsigned pos; 323 unsigned char hash[BLOCK]; 324 MD_CTX md; 325 326 /* hash given data */ 327 md_init(&md); 328 md_update(&md, data, len); 329 md_result(&md, hash); 330 331 /* 332 * Make sure the pool 0 is initialized, then update randomly. 333 */ 334 if (st->reseed_count == 0) 335 pos = 0; 336 else 337 pos = get_rand_pool(st); 338 md_update(&st->pool[pos], hash, BLOCK); 339 340 if (pos == 0) 341 st->pool0_bytes += len; 342 343 memset(hash, 0, BLOCK); 344 memset(&md, 0, sizeof(md)); 345 } 346 347 /* 348 * Just take 2 next blocks as new key 349 */ 350 static void 351 rekey(FState * st) 352 { 353 encrypt_counter(st, st->key); 354 encrypt_counter(st, st->key + CIPH_BLOCK); 355 ciph_init(&st->ciph, st->key, BLOCK); 356 } 357 358 /* 359 * Hide public constants. (counter, pools > 0) 360 * 361 * This can also be viewed as spreading the startup 362 * entropy over all of the components. 363 */ 364 static void 365 startup_tricks(FState * st) 366 { 367 int i; 368 unsigned char buf[BLOCK]; 369 370 /* Use next block as counter. */ 371 encrypt_counter(st, st->counter); 372 373 /* Now shuffle pools, excluding #0 */ 374 for (i = 1; i < NUM_POOLS; i++) 375 { 376 encrypt_counter(st, buf); 377 encrypt_counter(st, buf + CIPH_BLOCK); 378 md_update(&st->pool[i], buf, BLOCK); 379 } 380 memset(buf, 0, BLOCK); 381 382 /* Hide the key. */ 383 rekey(st); 384 385 /* This can be done only once. */ 386 st->tricks_done = 1; 387 } 388 389 static void 390 extract_data(FState * st, unsigned count, unsigned char *dst) 391 { 392 unsigned n; 393 unsigned block_nr = 0; 394 pid_t pid = getpid(); 395 396 /* Should we reseed? */ 397 if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0) 398 if (enough_time_passed(st)) 399 reseed(st); 400 401 /* Do some randomization on first call */ 402 if (!st->tricks_done) 403 startup_tricks(st); 404 405 /* If we forked, force a reseed again */ 406 if (pid != st->pid) { 407 st->pid = pid; 408 reseed(st); 409 } 410 411 while (count > 0) 412 { 413 /* produce bytes */ 414 encrypt_counter(st, st->result); 415 416 /* copy result */ 417 if (count > CIPH_BLOCK) 418 n = CIPH_BLOCK; 419 else 420 n = count; 421 memcpy(dst, st->result, n); 422 dst += n; 423 count -= n; 424 425 /* must not give out too many bytes with one key */ 426 block_nr++; 427 if (block_nr > (RESEED_BYTES / CIPH_BLOCK)) 428 { 429 rekey(st); 430 block_nr = 0; 431 } 432 } 433 /* Set new key for next request. */ 434 rekey(st); 435 } 436 437 /* 438 * public interface 439 */ 440 441 static FState main_state; 442 static int init_done; 443 static int have_entropy; 444 #define FORTUNA_RESEED_BYTE 10000 445 static unsigned resend_bytes; 446 447 /* 448 * This mutex protects all of the above static elements from concurrent 449 * access by multiple threads 450 */ 451 static HEIMDAL_MUTEX fortuna_mutex = HEIMDAL_MUTEX_INITIALIZER; 452 453 /* 454 * Try our best to do an inital seed 455 */ 456 #define INIT_BYTES 128 457 458 /* 459 * fortuna_mutex must be held across calls to this function 460 */ 461 462 static int 463 fortuna_reseed(void) 464 { 465 int entropy_p = 0; 466 467 if (!init_done) 468 abort(); 469 470 #ifndef NO_RAND_UNIX_METHOD 471 { 472 unsigned char buf[INIT_BYTES]; 473 if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) { 474 add_entropy(&main_state, buf, sizeof(buf)); 475 entropy_p = 1; 476 memset(buf, 0, sizeof(buf)); 477 } 478 } 479 #endif 480 #ifdef HAVE_ARC4RANDOM 481 { 482 uint32_t buf[INIT_BYTES / sizeof(uint32_t)]; 483 int i; 484 485 for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++) 486 buf[i] = arc4random(); 487 add_entropy(&main_state, (void *)buf, sizeof(buf)); 488 entropy_p = 1; 489 } 490 #endif 491 #ifndef NO_RAND_EGD_METHOD 492 /* 493 * Only to get egd entropy if /dev/random or arc4rand failed since 494 * it can be horribly slow to generate new bits. 495 */ 496 if (!entropy_p) { 497 unsigned char buf[INIT_BYTES]; 498 if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) { 499 add_entropy(&main_state, buf, sizeof(buf)); 500 entropy_p = 1; 501 memset(buf, 0, sizeof(buf)); 502 } 503 } 504 #endif 505 /* 506 * Fall back to gattering data from timer and secret files, this 507 * is really the last resort. 508 */ 509 if (!entropy_p) { 510 /* to save stackspace */ 511 union { 512 unsigned char buf[INIT_BYTES]; 513 unsigned char shad[1001]; 514 } u; 515 int fd; 516 517 /* add timer info */ 518 if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1) 519 add_entropy(&main_state, u.buf, sizeof(u.buf)); 520 /* add /etc/shadow */ 521 fd = open("/etc/shadow", O_RDONLY, 0); 522 if (fd >= 0) { 523 ssize_t n; 524 rk_cloexec(fd); 525 /* add_entropy will hash the buf */ 526 while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0) 527 add_entropy(&main_state, u.shad, sizeof(u.shad)); 528 close(fd); 529 } 530 531 memset(&u, 0, sizeof(u)); 532 533 entropy_p = 1; /* sure about this ? */ 534 } 535 { 536 pid_t pid = getpid(); 537 add_entropy(&main_state, (void *)&pid, sizeof(pid)); 538 } 539 { 540 struct timeval tv; 541 gettimeofday(&tv, NULL); 542 add_entropy(&main_state, (void *)&tv, sizeof(tv)); 543 } 544 #ifdef HAVE_GETUID 545 { 546 uid_t u = getuid(); 547 add_entropy(&main_state, (void *)&u, sizeof(u)); 548 } 549 #endif 550 return entropy_p; 551 } 552 553 /* 554 * fortuna_mutex must be held by callers of this function 555 */ 556 static int 557 fortuna_init(void) 558 { 559 if (!init_done) 560 { 561 init_state(&main_state); 562 init_done = 1; 563 } 564 if (!have_entropy) 565 have_entropy = fortuna_reseed(); 566 return (init_done && have_entropy); 567 } 568 569 570 571 static void 572 fortuna_seed(const void *indata, int size) 573 { 574 HEIMDAL_MUTEX_lock(&fortuna_mutex); 575 576 fortuna_init(); 577 add_entropy(&main_state, indata, size); 578 if (size >= INIT_BYTES) 579 have_entropy = 1; 580 581 HEIMDAL_MUTEX_unlock(&fortuna_mutex); 582 } 583 584 static int 585 fortuna_bytes(unsigned char *outdata, int size) 586 { 587 int ret = 0; 588 589 HEIMDAL_MUTEX_lock(&fortuna_mutex); 590 591 if (!fortuna_init()) 592 goto out; 593 594 resend_bytes += size; 595 if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) { 596 resend_bytes = 0; 597 fortuna_reseed(); 598 } 599 extract_data(&main_state, size, outdata); 600 ret = 1; 601 602 out: 603 HEIMDAL_MUTEX_unlock(&fortuna_mutex); 604 605 return ret; 606 } 607 608 static void 609 fortuna_cleanup(void) 610 { 611 HEIMDAL_MUTEX_lock(&fortuna_mutex); 612 613 init_done = 0; 614 have_entropy = 0; 615 memset(&main_state, 0, sizeof(main_state)); 616 617 HEIMDAL_MUTEX_unlock(&fortuna_mutex); 618 } 619 620 static void 621 fortuna_add(const void *indata, int size, double entropi) 622 { 623 fortuna_seed(indata, size); 624 } 625 626 static int 627 fortuna_pseudorand(unsigned char *outdata, int size) 628 { 629 return fortuna_bytes(outdata, size); 630 } 631 632 static int 633 fortuna_status(void) 634 { 635 int result; 636 637 HEIMDAL_MUTEX_lock(&fortuna_mutex); 638 result = fortuna_init(); 639 HEIMDAL_MUTEX_unlock(&fortuna_mutex); 640 641 return result ? 1 : 0; 642 } 643 644 const RAND_METHOD hc_rand_fortuna_method = { 645 fortuna_seed, 646 fortuna_bytes, 647 fortuna_cleanup, 648 fortuna_add, 649 fortuna_pseudorand, 650 fortuna_status 651 }; 652 653 const RAND_METHOD * 654 RAND_fortuna_method(void) 655 { 656 return &hc_rand_fortuna_method; 657 } 658