/* $NetBSD: rand-fortuna.c,v 1.3 2019/12/15 22:50:48 christos Exp $ */
/*
* 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 <krb5/roken.h>
#include <rand.h>
#include <heim_threads.h>
#ifdef KRB5
#include <krb5/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 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_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;
}