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