crypto/dist/heimdal/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 #ifdef HAVE_CONFIG_H
  33 #include <config.h>
  34 #endif
  35
  36 __RCSID("$Heimdal: rand-fortuna.c 21196 2007-06-20 05:08:58Z lha $"
  37         "$NetBSD$");
  38
  39 #include <stdio.h>
  40 #include <stdlib.h>
  41 #include <rand.h>
  42
  43 #include <roken.h>
  44
  45 #include "randi.h"
  46 #include "aes.h"
  47 #include "sha.h"
  48
  49 /*
  50  * Why Fortuna-like: There does not seem to be any definitive reference
  51  * on Fortuna in the net.  Instead this implementation is based on
  52  * following references:
  53  *
  54  * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
  55  *       - Wikipedia article
  56  * http://jlcooke.ca/random/
  57  *       - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
  58  */
  59
  60 /*
  61  * There is some confusion about whether and how to carry forward
  62  * the state of the pools.      Seems like original Fortuna does not
  63  * do it, resetting hash after each request.  I guess expecting
  64  * feeding to happen more often that requesting.   This is absolutely
  65  * unsuitable for pgcrypto, as nothing asynchronous happens here.
  66  *
  67  * J.L. Cooke fixed this by feeding previous hash to new re-initialized
  68  * hash context.
  69  *
  70  * Fortuna predecessor Yarrow requires ability to query intermediate
  71  * 'final result' from hash, without affecting it.
  72  *
  73  * This implementation uses the Yarrow method - asking intermediate
  74  * results, but continuing with old state.
  75  */
  76
  77
  78 /*
  79  * Algorithm parameters
  80  */
  81
  82 #define NUM_POOLS               32
  83
  84 /* in microseconds */
  85 #define RESEED_INTERVAL 100000  /* 0.1 sec */
  86
  87 /* for one big request, reseed after this many bytes */
  88 #define RESEED_BYTES    (1024*1024)
  89
  90 /*
  91  * Skip reseed if pool 0 has less than this many
  92  * bytes added since last reseed.
  93  */
  94 #define POOL0_FILL              (256/8)
  95
  96 /*
  97  * Algorithm constants
  98  */
  99
 100 /* Both cipher key size and hash result size */
 101 #define BLOCK                   32
 102
 103 /* cipher block size */
 104 #define CIPH_BLOCK              16
 105
 106 /* for internal wrappers */
 107 #define MD_CTX                  SHA256_CTX
 108 #define CIPH_CTX                AES_KEY
 109
 110 struct fortuna_state
 111 {
 112     unsigned char       counter[CIPH_BLOCK];
 113     unsigned char       result[CIPH_BLOCK];
 114     unsigned char       key[BLOCK];
 115     MD_CTX              pool[NUM_POOLS];
 116     CIPH_CTX            ciph;
 117     unsigned            reseed_count;
 118     struct timeval      last_reseed_time;
 119     unsigned            pool0_bytes;
 120     unsigned            rnd_pos;
 121     int                 tricks_done;
 122 };
 123 typedef struct fortuna_state FState;
 124
 125
 126 /*
 127  * Use our own wrappers here.
 128  * - Need to get intermediate result from digest, without affecting it.
 129  * - Need re-set key on a cipher context.
 130  * - Algorithms are guaranteed to exist.
 131  * - No memory allocations.
 132  */
 133
 134 static void
 135 ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
 136 {
 137     AES_set_encrypt_key(key, klen * 8, ctx);
 138 }
 139
 140 static void
 141 ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
 142 {
 143     AES_encrypt(in, out, ctx);
 144 }
 145
 146 static void
 147 md_init(MD_CTX * ctx)
 148 {
 149     SHA256_Init(ctx);
 150 }
 151
 152 static void
 153 md_update(MD_CTX * ctx, const unsigned char *data, int len)
 154 {
 155     SHA256_Update(ctx, data, len);
 156 }
 157
 158 static void
 159 md_result(MD_CTX * ctx, unsigned char *dst)
 160 {
 161     SHA256_CTX  tmp;
 162
 163     memcpy(&tmp, ctx, sizeof(*ctx));
 164     SHA256_Final(dst, &tmp);
 165     memset(&tmp, 0, sizeof(tmp));
 166 }
 167
 168 /*
 169  * initialize state
 170  */
 171 static void
 172 init_state(FState * st)
 173 {
 174     int                 i;
 175
 176     memset(st, 0, sizeof(*st));
 177     for (i = 0; i < NUM_POOLS; i++)
 178         md_init(&st->pool[i]);
 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     /* 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
 389     /* Should we reseed? */
 390     if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
 391         if (enough_time_passed(st))
 392             reseed(st);
 393
 394     /* Do some randomization on first call */
 395     if (!st->tricks_done)
 396         startup_tricks(st);
 397
 398     while (count > 0)
 399     {
 400         /* produce bytes */
 401         encrypt_counter(st, st->result);
 402
 403         /* copy result */
 404         if (count > CIPH_BLOCK)
 405             n = CIPH_BLOCK;
 406         else
 407             n = count;
 408         memcpy(dst, st->result, n);
 409         dst += n;
 410         count -= n;
 411
 412         /* must not give out too many bytes with one key */
 413         block_nr++;
 414         if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
 415         {
 416             rekey(st);
 417             block_nr = 0;
 418         }
 419     }
 420     /* Set new key for next request. */
 421     rekey(st);
 422 }
 423
 424 /*
 425  * public interface
 426  */
 427
 428 static FState   main_state;
 429 static int      init_done;
 430 static int      have_entropy;
 431 #define FORTUNA_RESEED_BYTE     10000
 432 static unsigned resend_bytes;
 433
 434 /*
 435  * Try our best to do an inital seed
 436  */
 437 #define INIT_BYTES      128
 438
 439 static int
 440 fortuna_reseed(void)
 441 {
 442     int entropy_p = 0;
 443
 444     if (!init_done)
 445         abort();
 446
 447     {
 448         unsigned char buf[INIT_BYTES];
 449         if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) {
 450             add_entropy(&main_state, buf, sizeof(buf));
 451             entropy_p = 1;
 452             memset(buf, 0, sizeof(buf));
 453         }
 454     }
 455 #ifdef HAVE_ARC4RANDOM
 456     {
 457         uint32_t buf[INIT_BYTES / sizeof(uint32_t)];
 458         int i;
 459
 460         for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
 461             buf[i] = arc4random();
 462         add_entropy(&main_state, (void *)buf, sizeof(buf));
 463         entropy_p = 1;
 464     }
 465 #endif
 466     /*
 467      * Only to get egd entropy if /dev/random or arc4rand failed since
 468      * it can be horribly slow to generate new bits.
 469      */
 470     if (!entropy_p) {
 471         unsigned char buf[INIT_BYTES];
 472         if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) {
 473             add_entropy(&main_state, buf, sizeof(buf));
 474             entropy_p = 1;
 475             memset(buf, 0, sizeof(buf));
 476         }
 477     }
 478     /*
 479      * Fall back to gattering data from timer and secret files, this
 480      * is really the last resort.
 481      */
 482     if (!entropy_p) {
 483         /* to save stackspace */
 484         union {
 485             unsigned char buf[INIT_BYTES];
 486             unsigned char shad[1001];
 487         } u;
 488         int fd;
 489
 490         /* add timer info */
 491         if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1)
 492             add_entropy(&main_state, u.buf, sizeof(u.buf));
 493         /* add /etc/shadow */
 494         fd = open("/etc/shadow", O_RDONLY, 0);
 495         if (fd >= 0) {
 496             ssize_t n;
 497             /* add_entropy will hash the buf */
 498             while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0)
 499                 add_entropy(&main_state, u.shad, sizeof(u.shad));
 500             close(fd);
 501         }
 502
 503         memset(&u, 0, sizeof(u));
 504
 505         entropy_p = 1; /* sure about this ? */
 506     }
 507     {
 508         pid_t pid = getpid();
 509         add_entropy(&main_state, (void *)&pid, sizeof(pid));
 510     }
 511     {
 512         struct timeval tv;
 513         gettimeofday(&tv, NULL);
 514         add_entropy(&main_state, (void *)&tv, sizeof(tv));
 515     }
 516     {
 517         uid_t u = getuid();
 518         add_entropy(&main_state, (void *)&u, sizeof(u));
 519     }
 520     return entropy_p;
 521 }
 522
 523 static int
 524 fortuna_init(void)
 525 {
 526     if (!init_done)
 527     {
 528         init_state(&main_state);
 529         init_done = 1;
 530     }
 531     if (!have_entropy)
 532         have_entropy = fortuna_reseed();
 533     return (init_done && have_entropy);
 534 }
 535
 536
 537
 538 static void
 539 fortuna_seed(const void *indata, int size)
 540 {
 541     fortuna_init();
 542     add_entropy(&main_state, indata, size);
 543     if (size >= INIT_BYTES)
 544         have_entropy = 1;
 545 }
 546
 547 static int
 548 fortuna_bytes(unsigned char *outdata, int size)
 549 {
 550     if (!fortuna_init())
 551         return 0;
 552     resend_bytes += size;
 553     if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
 554         resend_bytes = 0;
 555         fortuna_reseed();
 556     }
 557     extract_data(&main_state, size, outdata);
 558     return 1;
 559 }
 560
 561 static void
 562 fortuna_cleanup(void)
 563 {
 564     init_done = 0;
 565     have_entropy = 0;
 566     memset(&main_state, 0, sizeof(main_state));
 567 }
 568
 569 static void
 570 fortuna_add(const void *indata, int size, double entropi)
 571 {
 572     fortuna_seed(indata, size);
 573 }
 574
 575 static int
 576 fortuna_pseudorand(unsigned char *outdata, int size)
 577 {
 578     return fortuna_bytes(outdata, size);
 579 }
 580
 581 static int
 582 fortuna_status(void)
 583 {
 584     return fortuna_init() ? 1 : 0;
 585 }
 586
 587 const RAND_METHOD hc_rand_fortuna_method = {
 588     fortuna_seed,
 589     fortuna_bytes,
 590     fortuna_cleanup,
 591     fortuna_add,
 592     fortuna_pseudorand,
 593     fortuna_status
 594 };
 595
 596 const RAND_METHOD *
 597 RAND_fortuna_method(void)
 598 {
 599     return &hc_rand_fortuna_method;
 600 }