contrib/pgcrypto/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.9 2009/06/11 14:48:52 momjian Exp $
  30  */
  31
  32 #include "postgres.h"
  33
  34 #include <sys/time.h>
  35 #include <time.h>
  36
  37 #include "rijndael.h"
  38 #include "sha2.h"
  39 #include "fortuna.h"
  40
  41
  42 /*
  43  * Why Fortuna-like: There does not seem to be any definitive reference
  44  * on Fortuna in the net.  Instead this implementation is based on
  45  * following references:
  46  *
  47  * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
  48  *       - Wikipedia article
  49  * http://jlcooke.ca/random/
  50  *       - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
  51  */
  52
  53 /*
  54  * There is some confusion about whether and how to carry forward
  55  * the state of the pools.      Seems like original Fortuna does not
  56  * do it, resetting hash after each request.  I guess expecting
  57  * feeding to happen more often that requesting.   This is absolutely
  58  * unsuitable for pgcrypto, as nothing asynchronous happens here.
  59  *
  60  * J.L. Cooke fixed this by feeding previous hash to new re-initialized
  61  * hash context.
  62  *
  63  * Fortuna predecessor Yarrow requires ability to query intermediate
  64  * 'final result' from hash, without affecting it.
  65  *
  66  * This implementation uses the Yarrow method - asking intermediate
  67  * results, but continuing with old state.
  68  */
  69
  70
  71 /*
  72  * Algorithm parameters
  73  */
  74
  75 /*
  76  * How many pools.
  77  *
  78  * Original Fortuna uses 32 pools, that means 32'th pool is
  79  * used not earlier than in 13th year.  This is a waste in
  80  * pgcrypto, as we have very low-frequancy seeding.  Here
  81  * is preferable to have all entropy usable in reasonable time.
  82  *
  83  * With 23 pools, 23th pool is used after 9 days which seems
  84  * more sane.
  85  *
  86  * In our case the minimal cycle time would be bit longer
  87  * than the system-randomness feeding frequency.
  88  */
  89 #define NUM_POOLS               23
  90
  91 /* in microseconds */
  92 #define RESEED_INTERVAL 100000  /* 0.1 sec */
  93
  94 /* for one big request, reseed after this many bytes */
  95 #define RESEED_BYTES    (1024*1024)
  96
  97 /*
  98  * Skip reseed if pool 0 has less than this many
  99  * bytes added since last reseed.
 100  */
 101 #define POOL0_FILL              (256/8)
 102
 103 /*
 104  * Algorithm constants
 105  */
 106
 107 /* Both cipher key size and hash result size */
 108 #define BLOCK                   32
 109
 110 /* cipher block size */
 111 #define CIPH_BLOCK              16
 112
 113 /* for internal wrappers */
 114 #define MD_CTX                  SHA256_CTX
 115 #define CIPH_CTX                rijndael_ctx
 116
 117 struct fortuna_state
 118 {
 119         uint8           counter[CIPH_BLOCK];
 120         uint8           result[CIPH_BLOCK];
 121         uint8           key[BLOCK];
 122         MD_CTX          pool[NUM_POOLS];
 123         CIPH_CTX        ciph;
 124         unsigned        reseed_count;
 125         struct timeval last_reseed_time;
 126         unsigned        pool0_bytes;
 127         unsigned        rnd_pos;
 128         int                     tricks_done;
 129 };
 130 typedef struct fortuna_state FState;
 131
 132
 133 /*
 134  * Use our own wrappers here.
 135  * - Need to get intermediate result from digest, without affecting it.
 136  * - Need re-set key on a cipher context.
 137  * - Algorithms are guaranteed to exist.
 138  * - No memory allocations.
 139  */
 140
 141 static void
 142 ciph_init(CIPH_CTX * ctx, const uint8 *key, int klen)
 143 {
 144         rijndael_set_key(ctx, (const uint32 *) key, klen, 1);
 145 }
 146
 147 static void
 148 ciph_encrypt(CIPH_CTX * ctx, const uint8 *in, uint8 *out)
 149 {
 150         rijndael_encrypt(ctx, (const uint32 *) in, (uint32 *) out);
 151 }
 152
 153 static void
 154 md_init(MD_CTX * ctx)
 155 {
 156         SHA256_Init(ctx);
 157 }
 158
 159 static void
 160 md_update(MD_CTX * ctx, const uint8 *data, int len)
 161 {
 162         SHA256_Update(ctx, data, len);
 163 }
 164
 165 static void
 166 md_result(MD_CTX * ctx, uint8 *dst)
 167 {
 168         SHA256_CTX      tmp;
 169
 170         memcpy(&tmp, ctx, sizeof(*ctx));
 171         SHA256_Final(dst, &tmp);
 172         memset(&tmp, 0, sizeof(tmp));
 173 }
 174
 175 /*
 176  * initialize state
 177  */
 178 static void
 179 init_state(FState *st)
 180 {
 181         int                     i;
 182
 183         memset(st, 0, sizeof(*st));
 184         for (i = 0; i < NUM_POOLS; i++)
 185                 md_init(&st->pool[i]);
 186 }
 187
 188 /*
 189  * Endianess does not matter.
 190  * It just needs to change without repeating.
 191  */
 192 static void
 193 inc_counter(FState *st)
 194 {
 195         uint32     *val = (uint32 *) st->counter;
 196
 197         if (++val[0])
 198                 return;
 199         if (++val[1])
 200                 return;
 201         if (++val[2])
 202                 return;
 203         ++val[3];
 204 }
 205
 206 /*
 207  * This is called 'cipher in counter mode'.
 208  */
 209 static void
 210 encrypt_counter(FState *st, uint8 *dst)
 211 {
 212         ciph_encrypt(&st->ciph, st->counter, dst);
 213         inc_counter(st);
 214 }
 215
 216
 217 /*
 218  * The time between reseed must be at least RESEED_INTERVAL
 219  * microseconds.
 220  */
 221 static int
 222 enough_time_passed(FState *st)
 223 {
 224         int                     ok;
 225         struct timeval tv;
 226         struct timeval *last = &st->last_reseed_time;
 227
 228         gettimeofday(&tv, NULL);
 229
 230         /* check how much time has passed */
 231         ok = 0;
 232         if (tv.tv_sec > last->tv_sec + 1)
 233                 ok = 1;
 234         else if (tv.tv_sec == last->tv_sec + 1)
 235         {
 236                 if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
 237                         ok = 1;
 238         }
 239         else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
 240                 ok = 1;
 241
 242         /* reseed will happen, update last_reseed_time */
 243         if (ok)
 244                 memcpy(last, &tv, sizeof(tv));
 245
 246         memset(&tv, 0, sizeof(tv));
 247
 248         return ok;
 249 }
 250
 251 /*
 252  * generate new key from all the pools
 253  */
 254 static void
 255 reseed(FState *st)
 256 {
 257         unsigned        k;
 258         unsigned        n;
 259         MD_CTX          key_md;
 260         uint8           buf[BLOCK];
 261
 262         /* set pool as empty */
 263         st->pool0_bytes = 0;
 264
 265         /*
 266          * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
 267          */
 268         n = ++st->reseed_count;
 269
 270         /*
 271          * The goal: use k-th pool only 1/(2^k) of the time.
 272          */
 273         md_init(&key_md);
 274         for (k = 0; k < NUM_POOLS; k++)
 275         {
 276                 md_result(&st->pool[k], buf);
 277                 md_update(&key_md, buf, BLOCK);
 278
 279                 if (n & 1 || !n)
 280                         break;
 281                 n >>= 1;
 282         }
 283
 284         /* add old key into mix too */
 285         md_update(&key_md, st->key, BLOCK);
 286
 287         /* now we have new key */
 288         md_result(&key_md, st->key);
 289
 290         /* use new key */
 291         ciph_init(&st->ciph, st->key, BLOCK);
 292
 293         memset(&key_md, 0, sizeof(key_md));
 294         memset(buf, 0, BLOCK);
 295 }
 296
 297 /*
 298  * Pick a random pool.  This uses key bytes as random source.
 299  */
 300 static unsigned
 301 get_rand_pool(FState *st)
 302 {
 303         unsigned        rnd;
 304
 305         /*
 306          * This slightly prefers lower pools - thats OK.
 307          */
 308         rnd = st->key[st->rnd_pos] % NUM_POOLS;
 309
 310         st->rnd_pos++;
 311         if (st->rnd_pos >= BLOCK)
 312                 st->rnd_pos = 0;
 313
 314         return rnd;
 315 }
 316
 317 /*
 318  * update pools
 319  */
 320 static void
 321 add_entropy(FState *st, const uint8 *data, unsigned len)
 322 {
 323         unsigned        pos;
 324         uint8           hash[BLOCK];
 325         MD_CTX          md;
 326
 327         /* hash given data */
 328         md_init(&md);
 329         md_update(&md, data, len);
 330         md_result(&md, hash);
 331
 332         /*
 333          * Make sure the pool 0 is initialized, then update randomly.
 334          */
 335         if (st->reseed_count == 0)
 336                 pos = 0;
 337         else
 338                 pos = get_rand_pool(st);
 339         md_update(&st->pool[pos], hash, BLOCK);
 340
 341         if (pos == 0)
 342                 st->pool0_bytes += len;
 343
 344         memset(hash, 0, BLOCK);
 345         memset(&md, 0, sizeof(md));
 346 }
 347
 348 /*
 349  * Just take 2 next blocks as new key
 350  */
 351 static void
 352 rekey(FState *st)
 353 {
 354         encrypt_counter(st, st->key);
 355         encrypt_counter(st, st->key + CIPH_BLOCK);
 356         ciph_init(&st->ciph, st->key, BLOCK);
 357 }
 358
 359 /*
 360  * Hide public constants. (counter, pools > 0)
 361  *
 362  * This can also be viewed as spreading the startup
 363  * entropy over all of the components.
 364  */
 365 static void
 366 startup_tricks(FState *st)
 367 {
 368         int                     i;
 369         uint8           buf[BLOCK];
 370
 371         /* Use next block as counter. */
 372         encrypt_counter(st, st->counter);
 373
 374         /* Now shuffle pools, excluding #0 */
 375         for (i = 1; i < NUM_POOLS; i++)
 376         {
 377                 encrypt_counter(st, buf);
 378                 encrypt_counter(st, buf + CIPH_BLOCK);
 379                 md_update(&st->pool[i], buf, BLOCK);
 380         }
 381         memset(buf, 0, BLOCK);
 382
 383         /* Hide the key. */
 384         rekey(st);
 385
 386         /* This can be done only once. */
 387         st->tricks_done = 1;
 388 }
 389
 390 static void
 391 extract_data(FState *st, unsigned count, uint8 *dst)
 392 {
 393         unsigned        n;
 394         unsigned        block_nr = 0;
 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         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 = 0;
 437
 438 void
 439 fortuna_add_entropy(const uint8 *data, unsigned len)
 440 {
 441         if (!init_done)
 442         {
 443                 init_state(&main_state);
 444                 init_done = 1;
 445         }
 446         if (!data || !len)
 447                 return;
 448         add_entropy(&main_state, data, len);
 449 }
 450
 451 void
 452 fortuna_get_bytes(unsigned len, uint8 *dst)
 453 {
 454         if (!init_done)
 455         {
 456                 init_state(&main_state);
 457                 init_done = 1;
 458         }
 459         if (!dst || !len)
 460                 return;
 461         extract_data(&main_state, len, dst);
 462 }