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 111struct 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}; 125typedef 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 136static void 137ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen) 138{ 139 AES_set_encrypt_key(key, klen * 8, ctx); 140} 141 142static void 143ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out) 144{ 145 AES_encrypt(in, out, ctx); 146} 147 148static void 149md_init(MD_CTX * ctx) 150{ 151 SHA256_Init(ctx); 152} 153 154static void 155md_update(MD_CTX * ctx, const unsigned char *data, int len) 156{ 157 SHA256_Update(ctx, data, len); 158} 159 160static void 161md_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 */ 173static void 174init_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 */ 188static void 189inc_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 */ 205static void 206encrypt_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 */ 217static int 218enough_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 */ 250static void 251reseed(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 */ 299static unsigned 300get_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 */ 319static void 320add_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 */ 350static void 351rekey(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 */ 364static void 365startup_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 389static void 390extract_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 441static FState main_state; 442static int init_done; 443static int have_entropy; 444#define FORTUNA_RESEED_BYTE 10000 445static unsigned resend_bytes; 446 447/* 448 * This mutex protects all of the above static elements from concurrent 449 * access by multiple threads 450 */ 451static 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 462static int 463fortuna_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 */ 556static int 557fortuna_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 571static void 572fortuna_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 584static int 585fortuna_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 602out: 603 HEIMDAL_MUTEX_unlock(&fortuna_mutex); 604 605 return ret; 606} 607 608static void 609fortuna_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 620static void 621fortuna_add(const void *indata, int size, double entropi) 622{ 623 fortuna_seed(indata, size); 624} 625 626static int 627fortuna_pseudorand(unsigned char *outdata, int size) 628{ 629 return fortuna_bytes(outdata, size); 630} 631 632static int 633fortuna_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 644const 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 653const RAND_METHOD * 654RAND_fortuna_method(void) 655{ 656 return &hc_rand_fortuna_method; 657} 658