From 91adebe749beb0dc23cacaea316cb2b724776aad Mon Sep 17 00:00:00 2001 From: Andrew Bartlett Date: Wed, 13 Jun 2007 05:44:24 +0000 Subject: r23456: Update Samba4 to current lorikeet-heimdal. Andrew Bartlett (This used to be commit ae0f81ab235c72cceb120bcdeb051a483cf3cc4f) --- source4/heimdal/lib/hcrypto/rand-fortuna.c | 563 +++++++++++++++++++++++++++++ 1 file changed, 563 insertions(+) create mode 100644 source4/heimdal/lib/hcrypto/rand-fortuna.c (limited to 'source4/heimdal/lib/hcrypto/rand-fortuna.c') diff --git a/source4/heimdal/lib/hcrypto/rand-fortuna.c b/source4/heimdal/lib/hcrypto/rand-fortuna.c new file mode 100644 index 0000000000..6cc4267c13 --- /dev/null +++ b/source4/heimdal/lib/hcrypto/rand-fortuna.c @@ -0,0 +1,563 @@ +/* + * fortuna.c + * Fortuna-like PRNG. + * + * Copyright (c) 2005 Marko Kreen + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $PostgreSQL: pgsql/contrib/pgcrypto/fortuna.c,v 1.8 2006/10/04 00:29:46 momjian Exp $ + */ + +#ifdef HAVE_CONFIG_H +#include +#endif + +RCSID("$Id: rand-fortuna.c 20029 2007-01-21 09:55:42Z lha $"); + +#include +#include +#include + +#include + +#include "randi.h" +#include "aes.h" +#include "sha.h" + +/* + * Why Fortuna-like: There does not seem to be any definitive reference + * on Fortuna in the net. Instead this implementation is based on + * following references: + * + * http://en.wikipedia.org/wiki/Fortuna_(PRNG) + * - Wikipedia article + * http://jlcooke.ca/random/ + * - Jean-Luc Cooke Fortuna-based /dev/random driver for Linux. + */ + +/* + * There is some confusion about whether and how to carry forward + * the state of the pools. Seems like original Fortuna does not + * do it, resetting hash after each request. I guess expecting + * feeding to happen more often that requesting. This is absolutely + * unsuitable for pgcrypto, as nothing asynchronous happens here. + * + * J.L. Cooke fixed this by feeding previous hash to new re-initialized + * hash context. + * + * Fortuna predecessor Yarrow requires ability to query intermediate + * 'final result' from hash, without affecting it. + * + * This implementation uses the Yarrow method - asking intermediate + * results, but continuing with old state. + */ + + +/* + * Algorithm parameters + */ + +#define NUM_POOLS 32 + +/* in microseconds */ +#define RESEED_INTERVAL 100000 /* 0.1 sec */ + +/* for one big request, reseed after this many bytes */ +#define RESEED_BYTES (1024*1024) + +/* + * Skip reseed if pool 0 has less than this many + * bytes added since last reseed. + */ +#define POOL0_FILL (256/8) + +/* + * Algorithm constants + */ + +/* Both cipher key size and hash result size */ +#define BLOCK 32 + +/* cipher block size */ +#define CIPH_BLOCK 16 + +/* for internal wrappers */ +#define MD_CTX SHA256_CTX +#define CIPH_CTX AES_KEY + +struct fortuna_state +{ + unsigned char counter[CIPH_BLOCK]; + unsigned char result[CIPH_BLOCK]; + unsigned char key[BLOCK]; + MD_CTX pool[NUM_POOLS]; + CIPH_CTX ciph; + unsigned reseed_count; + struct timeval last_reseed_time; + unsigned pool0_bytes; + unsigned rnd_pos; + int tricks_done; +}; +typedef struct fortuna_state FState; + + +/* + * Use our own wrappers here. + * - Need to get intermediate result from digest, without affecting it. + * - Need re-set key on a cipher context. + * - Algorithms are guaranteed to exist. + * - No memory allocations. + */ + +static void +ciph_init(CIPH_CTX * ctx, const unsigned char *key, int klen) +{ + AES_set_encrypt_key(key, klen * 8, ctx); +} + +static void +ciph_encrypt(CIPH_CTX * ctx, const unsigned char *in, unsigned char *out) +{ + AES_encrypt(in, out, ctx); +} + +static void +md_init(MD_CTX * ctx) +{ + SHA256_Init(ctx); +} + +static void +md_update(MD_CTX * ctx, const unsigned char *data, int len) +{ + SHA256_Update(ctx, data, len); +} + +static void +md_result(MD_CTX * ctx, unsigned char *dst) +{ + SHA256_CTX tmp; + + memcpy(&tmp, ctx, sizeof(*ctx)); + SHA256_Final(dst, &tmp); + memset(&tmp, 0, sizeof(tmp)); +} + +/* + * initialize state + */ +static void +init_state(FState * st) +{ + int i; + + memset(st, 0, sizeof(*st)); + for (i = 0; i < NUM_POOLS; i++) + md_init(&st->pool[i]); +} + +/* + * Endianess does not matter. + * It just needs to change without repeating. + */ +static void +inc_counter(FState * st) +{ + uint32_t *val = (uint32_t *) st->counter; + + if (++val[0]) + return; + if (++val[1]) + return; + if (++val[2]) + return; + ++val[3]; +} + +/* + * This is called 'cipher in counter mode'. + */ +static void +encrypt_counter(FState * st, unsigned char *dst) +{ + ciph_encrypt(&st->ciph, st->counter, dst); + inc_counter(st); +} + + +/* + * The time between reseed must be at least RESEED_INTERVAL + * microseconds. + */ +static int +enough_time_passed(FState * st) +{ + int ok; + struct timeval tv; + struct timeval *last = &st->last_reseed_time; + + gettimeofday(&tv, NULL); + + /* check how much time has passed */ + ok = 0; + if (tv.tv_sec > last->tv_sec + 1) + ok = 1; + else if (tv.tv_sec == last->tv_sec + 1) + { + if (1000000 + tv.tv_usec - last->tv_usec >= RESEED_INTERVAL) + ok = 1; + } + else if (tv.tv_usec - last->tv_usec >= RESEED_INTERVAL) + ok = 1; + + /* reseed will happen, update last_reseed_time */ + if (ok) + memcpy(last, &tv, sizeof(tv)); + + memset(&tv, 0, sizeof(tv)); + + return ok; +} + +/* + * generate new key from all the pools + */ +static void +reseed(FState * st) +{ + unsigned k; + unsigned n; + MD_CTX key_md; + unsigned char buf[BLOCK]; + + /* set pool as empty */ + st->pool0_bytes = 0; + + /* + * Both #0 and #1 reseed would use only pool 0. Just skip #0 then. + */ + n = ++st->reseed_count; + + /* + * The goal: use k-th pool only 1/(2^k) of the time. + */ + md_init(&key_md); + for (k = 0; k < NUM_POOLS; k++) + { + md_result(&st->pool[k], buf); + md_update(&key_md, buf, BLOCK); + + if (n & 1 || !n) + break; + n >>= 1; + } + + /* add old key into mix too */ + md_update(&key_md, st->key, BLOCK); + + /* now we have new key */ + md_result(&key_md, st->key); + + /* use new key */ + ciph_init(&st->ciph, st->key, BLOCK); + + memset(&key_md, 0, sizeof(key_md)); + memset(buf, 0, BLOCK); +} + +/* + * Pick a random pool. This uses key bytes as random source. + */ +static unsigned +get_rand_pool(FState * st) +{ + unsigned rnd; + + /* + * This slightly prefers lower pools - thats OK. + */ + rnd = st->key[st->rnd_pos] % NUM_POOLS; + + st->rnd_pos++; + if (st->rnd_pos >= BLOCK) + st->rnd_pos = 0; + + return rnd; +} + +/* + * update pools + */ +static void +add_entropy(FState * st, const unsigned char *data, unsigned len) +{ + unsigned pos; + unsigned char hash[BLOCK]; + MD_CTX md; + + /* hash given data */ + md_init(&md); + md_update(&md, data, len); + md_result(&md, hash); + + /* + * Make sure the pool 0 is initialized, then update randomly. + */ + if (st->reseed_count == 0) + pos = 0; + else + pos = get_rand_pool(st); + md_update(&st->pool[pos], hash, BLOCK); + + if (pos == 0) + st->pool0_bytes += len; + + memset(hash, 0, BLOCK); + memset(&md, 0, sizeof(md)); +} + +/* + * Just take 2 next blocks as new key + */ +static void +rekey(FState * st) +{ + encrypt_counter(st, st->key); + encrypt_counter(st, st->key + CIPH_BLOCK); + ciph_init(&st->ciph, st->key, BLOCK); +} + +/* + * Hide public constants. (counter, pools > 0) + * + * This can also be viewed as spreading the startup + * entropy over all of the components. + */ +static void +startup_tricks(FState * st) +{ + int i; + unsigned char buf[BLOCK]; + + /* Use next block as counter. */ + encrypt_counter(st, st->counter); + + /* Now shuffle pools, excluding #0 */ + for (i = 1; i < NUM_POOLS; i++) + { + encrypt_counter(st, buf); + encrypt_counter(st, buf + CIPH_BLOCK); + md_update(&st->pool[i], buf, BLOCK); + } + memset(buf, 0, BLOCK); + + /* Hide the key. */ + rekey(st); + + /* This can be done only once. */ + st->tricks_done = 1; +} + +static void +extract_data(FState * st, unsigned count, unsigned char *dst) +{ + unsigned n; + unsigned block_nr = 0; + + /* Should we reseed? */ + if (st->pool0_bytes >= POOL0_FILL || st->reseed_count == 0) + if (enough_time_passed(st)) + reseed(st); + + /* Do some randomization on first call */ + if (!st->tricks_done) + startup_tricks(st); + + while (count > 0) + { + /* produce bytes */ + encrypt_counter(st, st->result); + + /* copy result */ + if (count > CIPH_BLOCK) + n = CIPH_BLOCK; + else + n = count; + memcpy(dst, st->result, n); + dst += n; + count -= n; + + /* must not give out too many bytes with one key */ + block_nr++; + if (block_nr > (RESEED_BYTES / CIPH_BLOCK)) + { + rekey(st); + block_nr = 0; + } + } + /* Set new key for next request. */ + rekey(st); +} + +/* + * public interface + */ + +static FState main_state; +static int init_done; +static int have_entropy; + +/* + * Try our best to do an inital seed + */ +#define INIT_BYTES 128 + +static int +fortuna_reseed(void) +{ + int entropy_p = 0; + + if (!init_done) + abort(); + + { + unsigned char buf[INIT_BYTES]; + if ((*hc_rand_unix_method.bytes)(buf, sizeof(buf)) == 1) { + add_entropy(&main_state, buf, sizeof(buf)); + entropy_p = 1; + memset(buf, 0, sizeof(buf)); + } + } +#ifdef HAVE_ARC4RANDOM + { + uint32_t buf[INIT_BYTES / sizeof(uint32_t)]; + int i; + + for (i = 0; i < sizeof(buf)/sizeof(buf[0]); i++) + buf[i] = arc4random(); + add_entropy(&main_state, (void *)buf, sizeof(buf)); + entropy_p = 1; + } +#endif + /* + * Only to get egd entropy if /dev/random or arc4rand failed since + * it can be horribly slow to generate new bits. + */ + if (!entropy_p) { + unsigned char buf[INIT_BYTES]; + if ((*hc_rand_egd_method.bytes)(buf, sizeof(buf)) == 1) { + add_entropy(&main_state, buf, sizeof(buf)); + entropy_p = 1; + memset(buf, 0, sizeof(buf)); + } + } + { + pid_t pid = getpid(); + add_entropy(&main_state, (void *)&pid, sizeof(pid)); + } + { + struct timeval tv; + gettimeofday(&tv, NULL); + add_entropy(&main_state, (void *)&tv, sizeof(tv)); + } + { + uid_t u = getuid(); + add_entropy(&main_state, (void *)&u, sizeof(u)); + } + return entropy_p; +} + +static int +fortuna_init(void) +{ + if (!init_done) + { + init_state(&main_state); + init_done = 1; + } + if (!have_entropy) + have_entropy = fortuna_reseed(); + return (init_done && have_entropy); +} + + + +static void +fortuna_seed(const void *indata, int size) +{ + fortuna_init(); + add_entropy(&main_state, indata, size); + if (size >= INIT_BYTES) + have_entropy = 1; +} + +static int +fortuna_bytes(unsigned char *outdata, int size) +{ + if (!fortuna_init()) + return 0; + extract_data(&main_state, size, outdata); + return 1; +} + +static void +fortuna_cleanup(void) +{ + init_done = 0; + have_entropy = 0; + memset(&main_state, 0, sizeof(main_state)); +} + +static void +fortuna_add(const void *indata, int size, double entropi) +{ + fortuna_seed(indata, size); +} + +static int +fortuna_pseudorand(unsigned char *outdata, int size) +{ + return fortuna_bytes(outdata, size); +} + +static int +fortuna_status(void) +{ + return fortuna_init() ? 1 : 0; +} + +const RAND_METHOD hc_rand_fortuna_method = { + fortuna_seed, + fortuna_bytes, + fortuna_cleanup, + fortuna_add, + fortuna_pseudorand, + fortuna_status +}; + +const RAND_METHOD * +RAND_fortuna_method(void) +{ + return &hc_rand_fortuna_method; +} -- cgit