crypto/external/bsd/heimdal/dist/lib/hcrypto/rand-fortuna.c

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