summaryrefslogtreecommitdiffstats
path: root/third_party/heimdal/lib/hcrypto/rand-fortuna.c
diff options
context:
space:
mode:
Diffstat (limited to 'third_party/heimdal/lib/hcrypto/rand-fortuna.c')
-rw-r--r--third_party/heimdal/lib/hcrypto/rand-fortuna.c649
1 files changed, 649 insertions, 0 deletions
diff --git a/third_party/heimdal/lib/hcrypto/rand-fortuna.c b/third_party/heimdal/lib/hcrypto/rand-fortuna.c
new file mode 100644
index 0000000..313b86f
--- /dev/null
+++ b/third_party/heimdal/lib/hcrypto/rand-fortuna.c
@@ -0,0 +1,649 @@
+/*
+ * 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 $
+ */
+
+#include <config.h>
+#include <roken.h>
+#include <rand.h>
+#include <heim_threads.h>
+
+#ifdef KRB5
+#include <krb5-types.h>
+#endif
+
+#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;
+ pid_t pid;
+};
+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_s(&tmp, sizeof(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]);
+ st->pid = getpid();
+}
+
+/*
+ * 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_s(&tv, sizeof(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);
+
+ /* add pid to make output diverse after fork() */
+ md_update(&key_md, (const unsigned char *)&st->pid, sizeof(st->pid));
+
+ /* now we have new key */
+ md_result(&key_md, st->key);
+
+ /* use new key */
+ ciph_init(&st->ciph, st->key, BLOCK);
+
+ memset_s(&key_md, sizeof(key_md), 0, sizeof(key_md));
+ memset_s(buf, sizeof(buf), 0, sizeof(buf));
+}
+
+/*
+ * 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_s(hash, sizeof(hash), 0, sizeof(hash));
+ memset_s(&md, sizeof(hash), 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_s(buf, sizeof(buf), 0, sizeof(buf));
+
+ /* 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;
+ pid_t pid = getpid();
+
+ /* 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);
+
+ /* If we forked, force a reseed again */
+ if (pid != st->pid) {
+ st->pid = pid;
+ reseed(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;
+#define FORTUNA_RESEED_BYTE 10000
+static unsigned resend_bytes;
+
+/*
+ * This mutex protects all of the above static elements from concurrent
+ * access by multiple threads
+ */
+static HEIMDAL_MUTEX fortuna_mutex = HEIMDAL_MUTEX_INITIALIZER;
+
+/*
+ * Try our best to do an initial seed
+ */
+#define INIT_BYTES 128
+
+/*
+ * fortuna_mutex must be held across calls to this function
+ */
+
+static int
+fortuna_reseed(void)
+{
+ int entropy_p = 0;
+
+ if (!init_done)
+ abort();
+
+#ifndef NO_RAND_UNIX_METHOD
+ {
+ 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_s(buf, sizeof(buf), 0, sizeof(buf));
+ }
+ }
+#endif
+#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
+ /*
+ * Fall back to gattering data from timer and secret files, this
+ * is really the last resort.
+ */
+ if (!entropy_p) {
+ /* to save stackspace */
+ union {
+ unsigned char buf[INIT_BYTES];
+ unsigned char shad[1001];
+ } u;
+ int fd;
+
+ /* add timer info */
+ if ((*hc_rand_timer_method.bytes)(u.buf, sizeof(u.buf)) == 1)
+ add_entropy(&main_state, u.buf, sizeof(u.buf));
+ /* add /etc/shadow */
+ fd = open("/etc/shadow", O_RDONLY, 0);
+ if (fd >= 0) {
+ ssize_t n;
+ rk_cloexec(fd);
+ /* add_entropy will hash the buf */
+ while ((n = read(fd, (char *)u.shad, sizeof(u.shad))) > 0)
+ add_entropy(&main_state, u.shad, sizeof(u.shad));
+ close(fd);
+ }
+
+ memset_s(&u, sizeof(u), 0, sizeof(u));
+
+ entropy_p = 1; /* sure about this ? */
+ }
+ {
+ 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));
+ }
+#ifdef HAVE_GETUID
+ {
+ uid_t u = getuid();
+ add_entropy(&main_state, (void *)&u, sizeof(u));
+ }
+#endif
+ return entropy_p;
+}
+
+/*
+ * fortuna_mutex must be held by callers of this function
+ */
+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)
+{
+ HEIMDAL_MUTEX_lock(&fortuna_mutex);
+
+ fortuna_init();
+ add_entropy(&main_state, indata, size);
+ if (size >= INIT_BYTES)
+ have_entropy = 1;
+
+ HEIMDAL_MUTEX_unlock(&fortuna_mutex);
+}
+
+static int
+fortuna_bytes(unsigned char *outdata, int size)
+{
+ int ret = 0;
+
+ HEIMDAL_MUTEX_lock(&fortuna_mutex);
+
+ if (!fortuna_init())
+ goto out;
+
+ resend_bytes += size;
+ if (resend_bytes > FORTUNA_RESEED_BYTE || resend_bytes < size) {
+ resend_bytes = 0;
+ fortuna_reseed();
+ }
+ extract_data(&main_state, size, outdata);
+ ret = 1;
+
+out:
+ HEIMDAL_MUTEX_unlock(&fortuna_mutex);
+
+ return ret;
+}
+
+static void
+fortuna_cleanup(void)
+{
+ HEIMDAL_MUTEX_lock(&fortuna_mutex);
+
+ init_done = 0;
+ have_entropy = 0;
+ memset_s(&main_state, sizeof(main_state), 0, sizeof(main_state));
+
+ HEIMDAL_MUTEX_unlock(&fortuna_mutex);
+}
+
+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)
+{
+ int result;
+
+ HEIMDAL_MUTEX_lock(&fortuna_mutex);
+ result = fortuna_init();
+ HEIMDAL_MUTEX_unlock(&fortuna_mutex);
+
+ return result ? 1 : 0;
+}
+
+#if defined(__GNUC__) || (defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901)
+const RAND_METHOD hc_rand_fortuna_method = {
+ .seed = fortuna_seed,
+ .bytes = fortuna_bytes,
+ .cleanup = fortuna_cleanup,
+ .add = fortuna_add,
+ .pseudorand = fortuna_pseudorand,
+ .status = fortuna_status
+};
+#else
+const RAND_METHOD hc_rand_fortuna_method = {
+ fortuna_seed,
+ fortuna_bytes,
+ fortuna_cleanup,
+ fortuna_add,
+ fortuna_pseudorand,
+ fortuna_status
+};
+#endif
+
+const RAND_METHOD *
+RAND_fortuna_method(void)
+{
+ return &hc_rand_fortuna_method;
+}