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