5 * Copyright (c) 2005 Marko Kreen
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
29 * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $
37 #include <heim_threads.h>
40 #include <krb5-types.h>
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:
53 * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
55 * http://jlcooke.ca/random/
56 * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
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.
66 * J.L. Cooke fixed this by feeding previous hash to new re-initialized
69 * Fortuna predecessor Yarrow requires ability to query intermediate
70 * 'final result' from hash, without affecting it.
72 * This implementation uses the Yarrow method - asking intermediate
73 * results, but continuing with old state.
78 * Algorithm parameters
84 #define RESEED_INTERVAL 100000 /* 0.1 sec */
86 /* for one big request, reseed after this many bytes */
87 #define RESEED_BYTES (1024*1024)
90 * Skip reseed if pool 0 has less than this many
91 * bytes added since last reseed.
93 #define POOL0_FILL (256/8)
99 /* Both cipher key size and hash result size */
102 /* cipher block size */
103 #define CIPH_BLOCK 16
105 /* for internal wrappers */
106 #define MD_CTX SHA256_CTX
107 #define CIPH_CTX AES_KEY
111 unsigned char counter[CIPH_BLOCK];
112 unsigned char result[CIPH_BLOCK];
113 unsigned char key[BLOCK];
114 MD_CTX pool[NUM_POOLS];
116 unsigned reseed_count;
117 struct timeval last_reseed_time;
118 unsigned pool0_bytes;
123 typedef struct fortuna_state FState;
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.
135 ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen)
137 AES_set_encrypt_key(key, klen * 8, ctx);
141 ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out)
143 AES_encrypt(in, out, ctx);
147 md_init(MD_CTX * ctx)
153 md_update(MD_CTX * ctx, const unsigned char *data, int len)
155 SHA256_Update(ctx, data, len);
159 md_result(MD_CTX * ctx, unsigned char *dst)
163 memcpy(&tmp, ctx, sizeof(*ctx));
164 SHA256_Final(dst, &tmp);
165 memset(&tmp, 0, sizeof(tmp));
172 init_state(FState * st)
176 memset(st, 0, sizeof(*st));
177 for (i = 0; i < NUM_POOLS; i++)
178 md_init(&st->pool[i]);
183 * Endianess does not matter.
184 * It just needs to change without repeating.
187 inc_counter(FState * st)
189 uint32_t *val = (uint32_t *) st->counter;
201 * This is called 'cipher in counter mode'.
204 encrypt_counter(FState * st, unsigned char *dst)
206 ciph_encrypt(&st->ciph, st->counter, dst);
212 * The time between reseed must be at least RESEED_INTERVAL
216 enough_time_passed(FState * st)
220 struct timeval *last = &st->last_reseed_time;
222 gettimeofday(&tv, NULL);
224 /* check how much time has passed */
226 if (tv.tv_sec > last->tv_sec + 1)
228 else if (tv.tv_sec == last->tv_sec + 1)
230 if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
233 else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
236 /* reseed will happen, update last_reseed_time */
238 memcpy(last, &tv, sizeof(tv));
240 memset(&tv, 0, sizeof(tv));
246 * generate new key from all the pools
254 unsigned char buf[BLOCK];
256 /* set pool as empty */
260 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
262 n = ++st->reseed_count;
265 * The goal: use k-th pool only 1/(2^k) of the time.
268 for (k = 0; k < NUM_POOLS; k++)
270 md_result(&st->pool[k], buf);
271 md_update(&key_md, buf, BLOCK);
278 /* add old key into mix too */
279 md_update(&key_md, st->key, BLOCK);
281 /* add pid to make output diverse after fork() */
282 md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid));
284 /* now we have new key */
285 md_result(&key_md, st->key);
288 ciph_init(&st->ciph, st->key, BLOCK);
290 memset(&key_md, 0, sizeof(key_md));
291 memset(buf, 0, BLOCK);
295 * Pick a random pool. This uses key bytes as random source.
298 get_rand_pool(FState * st)
303 * This slightly prefers lower pools - thats OK.
305 rnd = st->key[st->rnd_pos] % NUM_POOLS;
308 if (st->rnd_pos >= BLOCK)
318 add_entropy(FState * st, const unsigned char *data, unsigned len)
321 unsigned char hash[BLOCK];
324 /* hash given data */
326 md_update(&md, data, len);
327 md_result(&md, hash);
330 * Make sure the pool 0 is initialized, then update randomly.
332 if (st->reseed_count == 0)
335 pos = get_rand_pool(st);
336 md_update(&st->pool[pos], hash, BLOCK);
339 st->pool0_bytes += len;
341 memset(hash, 0, BLOCK);
342 memset(&md, 0, sizeof(md));
346 * Just take 2 next blocks as new key
351 encrypt_counter(st, st->key);
352 encrypt_counter(st, st->key + CIPH_BLOCK);
353 ciph_init(&st->ciph, st->key, BLOCK);
357 * Hide public constants. (counter, pools > 0)
359 * This can also be viewed as spreading the startup
360 * entropy over all of the components.
363 startup_tricks(FState * st)
366 unsigned char buf[BLOCK];
368 /* Use next block as counter. */
369 encrypt_counter(st, st->counter);
371 /* Now shuffle pools, excluding #0 */
372 for (i = 1; i < NUM_POOLS; i++)
374 encrypt_counter(st, buf);
375 encrypt_counter(st, buf + CIPH_BLOCK);
376 md_update(&st->pool[i], buf, BLOCK);
378 memset(buf, 0, BLOCK);
383 /* This can be done only once. */
388 extract_data(FState * st, unsigned count, unsigned char *dst)
391 unsigned block_nr = 0;
392 pid_t pid = getpid();
394 /* Should we reseed? */
395 if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
396 if (enough_time_passed(st))
399 /* Do some randomization on first call */
400 if (!st->tricks_done)
403 /* If we forked, force a reseed again */
404 if (pid != st->pid) {
412 encrypt_counter(st, st->result);
415 if (count > CIPH_BLOCK)
419 memcpy(dst, st->result, n);
423 /* must not give out too many bytes with one key */
425 if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
431 /* Set new key for next request. */
439 static FState main_state;
440 static int init_done;
441 static int have_entropy;
442 #define FORTUNA_RESEED_BYTE 10000
443 static unsigned resend_bytes;
446 * This mutex protects all of the above static elements from concurrent
447 * access by multiple threads
449 static HEIMDAL_MUTEX fortuna_mutex = HEIMDAL_MUTEX_INITIALIZER;
452 * Try our best to do an inital seed
454 #define INIT_BYTES 128
457 * fortuna_mutex must be held across calls to this function
468 #ifndef NO_RAND_UNIX_METHOD
470 unsigned char buf[INIT_BYTES];
471 if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) {
472 add_entropy(&main_state, buf, sizeof(buf));
474 memset(buf, 0, sizeof(buf));
478 #ifdef HAVE_ARC4RANDOM
480 uint32_t buf[INIT_BYTES / sizeof(uint32_t)];
483 for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++)
484 buf[i] = arc4random();
485 add_entropy(&main_state, (void *)buf, sizeof(buf));
489 #ifndef NO_RAND_EGD_METHOD
491 * Only to get egd entropy if /dev/random or arc4rand failed since
492 * it can be horribly slow to generate new bits.
495 unsigned char buf[INIT_BYTES];
496 if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) {
497 add_entropy(&main_state, buf, sizeof(buf));
499 memset(buf, 0, sizeof(buf));
504 * Fall back to gattering data from timer and secret files, this
505 * is really the last resort.
508 /* to save stackspace */
510 unsigned char buf[INIT_BYTES];
511 unsigned char shad[1001];
516 if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1)
517 add_entropy(&main_state, u.buf, sizeof(u.buf));
518 /* add /etc/shadow */
519 fd = open("/etc/shadow", O_RDONLY, 0);
523 /* add_entropy will hash the buf */
524 while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0)
525 add_entropy(&main_state, u.shad, sizeof(u.shad));
529 memset(&u, 0, sizeof(u));
531 entropy_p = 1; /* sure about this ? */
534 pid_t pid = getpid();
535 add_entropy(&main_state, (void *)&pid, sizeof(pid));
539 gettimeofday(&tv, NULL);
540 add_entropy(&main_state, (void *)&tv, sizeof(tv));
545 add_entropy(&main_state, (void *)&u, sizeof(u));
552 * fortuna_mutex must be held by callers of this function
559 init_state(&main_state);
563 have_entropy = fortuna_reseed();
564 return (init_done && have_entropy);
570 fortuna_seed(const void *indata, int size)
572 HEIMDAL_MUTEX_lock(&fortuna_mutex);
575 add_entropy(&main_state, indata, size);
576 if (size >= INIT_BYTES)
579 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
583 fortuna_bytes(unsigned char *outdata, int size)
587 HEIMDAL_MUTEX_lock(&fortuna_mutex);
592 resend_bytes += size;
593 if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
597 extract_data(&main_state, size, outdata);
601 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
607 fortuna_cleanup(void)
609 HEIMDAL_MUTEX_lock(&fortuna_mutex);
613 memset(&main_state, 0, sizeof(main_state));
615 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
619 fortuna_add(const void *indata, int size, double entropi)
621 fortuna_seed(indata, size);
625 fortuna_pseudorand(unsigned char *outdata, int size)
627 return fortuna_bytes(outdata, size);
635 HEIMDAL_MUTEX_lock(&fortuna_mutex);
636 result = fortuna_init();
637 HEIMDAL_MUTEX_unlock(&fortuna_mutex);
639 return result ? 1 : 0;
642 const RAND_METHOD hc_rand_fortuna_method = {
652 RAND_fortuna_method(void)
654 return &hc_rand_fortuna_method;