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