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.9 2009/06/11 14:48:52 momjian Exp $
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:
47 * http://en.wikipedia.org/wiki/Fortuna_(PRNG)
49 * http://jlcooke.ca/random/
50 * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux.
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.
60 * J.L. Cooke fixed this by feeding previous hash to new re-initialized
63 * Fortuna predecessor Yarrow requires ability to query intermediate
64 * 'final result' from hash, without affecting it.
66 * This implementation uses the Yarrow method - asking intermediate
67 * results, but continuing with old state.
72 * Algorithm parameters
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.
83 * With 23 pools, 23th pool is used after 9 days which seems
86 * In our case the minimal cycle time would be bit longer
87 * than the system-randomness feeding frequency.
92 #define RESEED_INTERVAL 100000 /* 0.1 sec */
94 /* for one big request, reseed after this many bytes */
95 #define RESEED_BYTES (1024*1024)
98 * Skip reseed if pool 0 has less than this many
99 * bytes added since last reseed.
101 #define POOL0_FILL (256/8)
104 * Algorithm constants
107 /* Both cipher key size and hash result size */
110 /* cipher block size */
111 #define CIPH_BLOCK 16
113 /* for internal wrappers */
114 #define MD_CTX SHA256_CTX
115 #define CIPH_CTX rijndael_ctx
119 uint8 counter[CIPH_BLOCK];
120 uint8 result[CIPH_BLOCK];
122 MD_CTX pool[NUM_POOLS];
124 unsigned reseed_count;
125 struct timeval last_reseed_time;
126 unsigned pool0_bytes;
130 typedef struct fortuna_state FState;
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.
142 ciph_init(CIPH_CTX * ctx, const uint8 *key, int klen)
144 rijndael_set_key(ctx, (const uint32 *) key, klen, 1);
148 ciph_encrypt(CIPH_CTX * ctx, const uint8 *in, uint8 *out)
150 rijndael_encrypt(ctx, (const uint32 *) in, (uint32 *) out);
154 md_init(MD_CTX * ctx)
160 md_update(MD_CTX * ctx, const uint8 *data, int len)
162 SHA256_Update(ctx, data, len);
166 md_result(MD_CTX * ctx, uint8 *dst)
170 memcpy(&tmp, ctx, sizeof(*ctx));
171 SHA256_Final(dst, &tmp);
172 memset(&tmp, 0, sizeof(tmp));
179 init_state(FState *st)
183 memset(st, 0, sizeof(*st));
184 for (i = 0; i < NUM_POOLS; i++)
185 md_init(&st->pool[i]);
189 * Endianess does not matter.
190 * It just needs to change without repeating.
193 inc_counter(FState *st)
195 uint32 *val = (uint32 *) st->counter;
207 * This is called 'cipher in counter mode'.
210 encrypt_counter(FState *st, uint8 *dst)
212 ciph_encrypt(&st->ciph, st->counter, dst);
218 * The time between reseed must be at least RESEED_INTERVAL
222 enough_time_passed(FState *st)
226 struct timeval *last = &st->last_reseed_time;
228 gettimeofday(&tv, NULL);
230 /* check how much time has passed */
232 if (tv.tv_sec > last->tv_sec + 1)
234 else if (tv.tv_sec == last->tv_sec + 1)
236 if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
239 else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL)
242 /* reseed will happen, update last_reseed_time */
244 memcpy(last, &tv, sizeof(tv));
246 memset(&tv, 0, sizeof(tv));
252 * generate new key from all the pools
262 /* set pool as empty */
266 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
268 n = ++st->reseed_count;
271 * The goal: use k-th pool only 1/(2^k) of the time.
274 for (k = 0; k < NUM_POOLS; k++)
276 md_result(&st->pool[k], buf);
277 md_update(&key_md, buf, BLOCK);
284 /* add old key into mix too */
285 md_update(&key_md, st->key, BLOCK);
287 /* now we have new key */
288 md_result(&key_md, st->key);
291 ciph_init(&st->ciph, st->key, BLOCK);
293 memset(&key_md, 0, sizeof(key_md));
294 memset(buf, 0, BLOCK);
298 * Pick a random pool. This uses key bytes as random source.
301 get_rand_pool(FState *st)
306 * This slightly prefers lower pools - thats OK.
308 rnd = st->key[st->rnd_pos] % NUM_POOLS;
311 if (st->rnd_pos >= BLOCK)
321 add_entropy(FState *st, const uint8 *data, unsigned len)
327 /* hash given data */
329 md_update(&md, data, len);
330 md_result(&md, hash);
333 * Make sure the pool 0 is initialized, then update randomly.
335 if (st->reseed_count == 0)
338 pos = get_rand_pool(st);
339 md_update(&st->pool[pos], hash, BLOCK);
342 st->pool0_bytes += len;
344 memset(hash, 0, BLOCK);
345 memset(&md, 0, sizeof(md));
349 * Just take 2 next blocks as new key
354 encrypt_counter(st, st->key);
355 encrypt_counter(st, st->key + CIPH_BLOCK);
356 ciph_init(&st->ciph, st->key, BLOCK);
360 * Hide public constants. (counter, pools > 0)
362 * This can also be viewed as spreading the startup
363 * entropy over all of the components.
366 startup_tricks(FState *st)
371 /* Use next block as counter. */
372 encrypt_counter(st, st->counter);
374 /* Now shuffle pools, excluding #0 */
375 for (i = 1; i < NUM_POOLS; i++)
377 encrypt_counter(st, buf);
378 encrypt_counter(st, buf + CIPH_BLOCK);
379 md_update(&st->pool[i], buf, BLOCK);
381 memset(buf, 0, BLOCK);
386 /* This can be done only once. */
391 extract_data(FState *st, unsigned count, uint8 *dst)
394 unsigned block_nr = 0;
396 /* Should we reseed? */
397 if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0)
398 if (enough_time_passed(st))
401 /* Do some randomization on first call */
402 if (!st->tricks_done)
408 encrypt_counter(st, st->result);
411 if (count > CIPH_BLOCK)
415 memcpy(dst, st->result, n);
419 /* must not give out too many bytes with one key */
421 if (block_nr > (RESEED_BYTES / CIPH_BLOCK))
427 /* Set new key for next request. */
435 static FState main_state;
436 static int init_done = 0;
439 fortuna_add_entropy(const uint8 *data, unsigned len)
443 init_state(&main_state);
448 add_entropy(&main_state, data, len);
452 fortuna_get_bytes(unsigned len, uint8 *dst)
456 init_state(&main_state);
461 extract_data(&main_state, len, dst);