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