vendor/heimdal/1.5

1 files changed, 655 insertions, 0 deletions

diff --git a/lib/hcrypto/rand-fortuna.c b/lib/hcrypto/rand-fortuna.c
new file mode 100644
index 000000000000..11027b46cf4a
--- /dev/null
+++ b/lib/hcrypto/rand-fortuna.c
@@ -0,0 +1,655 @@
+/*
+ * 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 <stdio.h>
+#include <stdlib.h>
+#include <rand.h>
+#include <heim_threads.h>
+
+#ifdef KRB5
+#include <krb5-types.h>
+#endif
+#include <roken.h>
+
+#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(&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(&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(&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;
+    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 inital 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(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
+#ifndef NO_RAND_EGD_METHOD
+    /*
+     * 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));
+	}
+    }
+#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(&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(&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;
+}
+
+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;
+}