lib/hcrypto/rand-fortuna.c

   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
 105 struct 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 };
 119 typedef 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
 130 static void
 131 ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
 132 {
 133     AES_set_encrypt_key(key, klen * 8, ctx);
 134 }
 135
 136 static void
 137 ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
 138 {
 139     AES_encrypt(in, out, ctx);
 140 }
 141
 142 static void
 143 md_init(MD_CTX * ctx)
 144 {
 145     SHA256_Init(ctx);
 146 }
 147
 148 static void
 149 md_update(MD_CTX * ctx, const unsigned char *data, int len)
 150 {
 151     SHA256_Update(ctx, data, len);
 152 }
 153
 154 static void
 155 md_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  */
 167 static void
 168 init_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  */
 182 static void
 183 inc_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  */
 199 static void
 200 encrypt_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  */
 211 static int
 212 enough_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  */
 244 static void
 245 reseed(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  */
 293 static unsigned
 294 get_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  */
 313 static void
 314 add_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  */
 344 static void
 345 rekey(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  */
 358 static void
 359 startup_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
 383 static void
 384 extract_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
 435 static FState   main_state;
 436 static int      init_done;
 437 static int      have_entropy;
 438 #define FORTUNA_RESEED_BYTE     10000
 439 static unsigned resend_bytes;
 440
 441 /*
 442  * Try our best to do an inital seed
 443  */
 444 #define INIT_BYTES      128
 445
 446 static int
 447 fortuna_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
 531 static int
 532 fortuna_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
 546 static void
 547 fortuna_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
 555 static int
 556 fortuna_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
 569 static void
 570 fortuna_cleanup(void)
 571 {
 572     init_done = 0;
 573     have_entropy = 0;
 574     memset(&main_state, 0, sizeof(main_state));
 575 }
 576
 577 static void
 578 fortuna_add(const void *indata, int size, double entropi)
 579 {
 580     fortuna_seed(indata, size);
 581 }
 582
 583 static int
 584 fortuna_pseudorand(unsigned char *outdata, int size)
 585 {
 586     return fortuna_bytes(outdata, size);
 587 }
 588
 589 static int
 590 fortuna_status(void)
 591 {
 592     return fortuna_init() ? 1 : 0;
 593 }
 594
 595 const 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
 604 const RAND_METHOD *
 605 RAND_fortuna_method(void)
 606 {
 607     return &hc_rand_fortuna_method;
 608 }