kern/lib/random/fortuna.c - akaros - Git at Google

 /*
  * 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.
  *
  * contrib/pgcrypto/fortuna.c
  */

 #include <arch/arch.h>
 #include <time.h>

 #include <random/fortuna.h>
 #include <random/rijndael.h>
 #include <random/sha2.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
  */

 /*
  * How many pools.
  *
  * Original Fortuna uses 32 pools, that means 32'th pool is
  * used not earlier than in 13th year.	This is a waste in
  * pgcrypto, as we have very low-frequancy seeding.  Here
  * is preferable to have all entropy usable in reasonable time.
  *
  * With 23 pools, 23th pool is used after 9 days which seems
  * more sane.
  *
  * In our case the minimal cycle time would be bit longer
  * than the system-randomness feeding frequency.
  */
 enum { numPools = 23,

        /* in microseconds */
        reseedInterval = 100000, /* 0.1 sec */

        /* for one big request, reseed after this many bytes */
        reseedBytes = (1024 * 1024),

        /*
 	* Skip reseed if pool 0 has less than this many
 	* bytes added since last reseed.
 	*/
        pool0Fill = (256 / 8),

        /*
 	* Algorithm constants
 	*/

        /* Both cipher key size and hash result size */
        block = 32,

        /* cipher block size */
        ciphBlock = 16 };

 /* for internal wrappers */
 typedef SHA256Ctx mdCtx;
 typedef rijndaelCtx ciphCtx;

 struct FState {
 	uint8_t counter[ciphBlock];
 	uint8_t result[ciphBlock];
 	uint8_t key[block];
 	mdCtx pool[numPools];
 	ciphCtx ciph;
 	unsigned reseedCount;
 	int32_t lastReseedTime;
 	unsigned pool0Bytes;
 	unsigned rndPos;
 	int tricksDone;
 };
 typedef struct FState 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(ciphCtx *ctx, const uint8_t *key, int klen)
 {
 	rijndael_set_key(ctx, (const uint32_t *)key, klen, 1);
 }

 static void ciph_encrypt(ciphCtx *ctx, const uint8_t *in, uint8_t *out)
 {
 	rijndael_encrypt(ctx, (const uint32_t *)in, (uint32_t *)out);
 }

 static void md_init(mdCtx *ctx)
 {
 	SHA256_Init(ctx);
 }

 static void md_update(mdCtx *ctx, const uint8_t *data, int len)
 {
 	SHA256_Update(ctx, data, len);
 }

 static void md_result(mdCtx *ctx, uint8_t *dst)
 {
 	SHA256Ctx tmp;

 	memmove(&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 < numPools; 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, uint8_t *dst)
 {
 	ciph_encrypt(&st->ciph, st->counter, dst);
 	inc_counter(st);
 }

 /*
  * The time between reseed must be at least reseedInterval
  * microseconds.
  */
 static int enough_time_passed(FState *st)
 {
 	int ok;
 	int32_t now;
 	int32_t last = st->lastReseedTime;

 	now = tsc2sec(read_tsc());

 	/* check how much time has passed */
 	ok = 0;
 	if (now - last >= reseedInterval)
 		ok = 1;

 	/* reseed will happen, update lastReseedTime */
 	if (ok)
 		st->lastReseedTime = now;

 	return ok;
 }

 /*
  * generate new key from all the pools
  */
 static void reseed(FState *st)
 {
 	unsigned k;
 	unsigned n;
 	mdCtx key_md;
 	uint8_t buf[block];

 	/* set pool as empty */
 	st->pool0Bytes = 0;

 	/*
 	 * Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
 	 */
 	n = ++st->reseedCount;

 	/*
 	 * The goal: use k-th pool only 1/(2^k) of the time.
 	 */
 	md_init(&key_md);
 	for (k = 0; k < numPools; 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->rndPos] % numPools;

 	st->rndPos++;
 	if (st->rndPos >= block)
 		st->rndPos = 0;

 	return rnd;
 }

 /*
  * update pools
  */
 static void add_entropy(FState *st, const uint8_t *data, unsigned len)
 {
 	unsigned pos;
 	uint8_t hash[block];
 	mdCtx 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->reseedCount == 0)
 		pos = 0;
 	else
 		pos = get_rand_pool(st);
 	md_update(&st->pool[pos], hash, block);

 	if (pos == 0)
 		st->pool0Bytes += 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 + ciphBlock);
 	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;
 	uint8_t buf[block];

 	/* Use next block as counter. */
 	encrypt_counter(st, st->counter);

 	/* Now shuffle pools, excluding #0 */
 	for (i = 1; i < numPools; i++) {
 		encrypt_counter(st, buf);
 		encrypt_counter(st, buf + ciphBlock);
 		md_update(&st->pool[i], buf, block);
 	}
 	memset(buf, 0, block);

 	/* Hide the key. */
 	rekey(st);

 	/* This can be done only once. */
 	st->tricksDone = 1;
 }

 static void extract_data(FState *st, unsigned count, uint8_t *dst)
 {
 	unsigned n;
 	unsigned block_nr = 0;

 	/* Should we reseed? */
 	if (st->pool0Bytes >= pool0Fill || st->reseedCount == 0)
 		if (enough_time_passed(st))
 			reseed(st);

 	/* Do some randomization on first call */
 	if (!st->tricksDone)
 		startup_tricks(st);

 	while (count > 0) {
 		/* produce bytes */
 		encrypt_counter(st, st->result);

 		/* copy result */
 		if (count > ciphBlock)
 			n = ciphBlock;
 		else
 			n = count;
 		memmove(dst, st->result, n);
 		dst += n;
 		count -= n;

 		/* must not give out too many bytes with one key */
 		block_nr++;
 		if (block_nr > (reseedBytes / ciphBlock)) {
 			rekey(st);
 			block_nr = 0;
 		}
 	}
 	/* Set new key for next request. */
 	rekey(st);
 }

 static FState mainState;
 static int initDone;

 static void init()
 {
 	init_state(&mainState);
 	initDone = 1;
 }

 /*
  * public interface
  */

 void fortuna_add_entropy(const uint8_t *data, unsigned len)
 {
 	if (!initDone)
 		init();

 	if (!data || !len)
 		return;
 	add_entropy(&mainState, data, len);
 }

 void fortuna_get_bytes(unsigned len, uint8_t *dst)
 {
 	if (!initDone)
 		init();

 	if (!dst || !len)
 		return;
 	extract_data(&mainState, len, dst);
 }
	/*
	* 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.
	*
	* contrib/pgcrypto/fortuna.c
	*/

	#include <arch/arch.h>
	#include <time.h>

	#include <random/fortuna.h>
	#include <random/rijndael.h>
	#include <random/sha2.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
	*/

	/*
	* How many pools.
	*
	* Original Fortuna uses 32 pools, that means 32'th pool is
	* used not earlier than in 13th year. This is a waste in
	* pgcrypto, as we have very low-frequancy seeding. Here
	* is preferable to have all entropy usable in reasonable time.
	*
	* With 23 pools, 23th pool is used after 9 days which seems
	* more sane.
	*
	* In our case the minimal cycle time would be bit longer
	* than the system-randomness feeding frequency.
	*/
	enum { numPools = 23,

	/* in microseconds */
	reseedInterval = 100000, /* 0.1 sec */

	/* for one big request, reseed after this many bytes */
	reseedBytes = (1024 * 1024),

	/*
	* Skip reseed if pool 0 has less than this many
	* bytes added since last reseed.
	*/
	pool0Fill = (256 / 8),

	/*
	* Algorithm constants
	*/

	/* Both cipher key size and hash result size */
	block = 32,

	/* cipher block size */
	ciphBlock = 16 };

	/* for internal wrappers */
	typedef SHA256Ctx mdCtx;
	typedef rijndaelCtx ciphCtx;

	struct FState {
	uint8_t counter[ciphBlock];
	uint8_t result[ciphBlock];
	uint8_t key[block];
	mdCtx pool[numPools];
	ciphCtx ciph;
	unsigned reseedCount;
	int32_t lastReseedTime;
	unsigned pool0Bytes;
	unsigned rndPos;
	int tricksDone;
	};
	typedef struct FState 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(ciphCtx ctx, const uint8_t key, int klen)
	{
	rijndael_set_key(ctx, (const uint32_t *)key, klen, 1);
	}

	static void ciph_encrypt(ciphCtx ctx, const uint8_t in, uint8_t *out)
	{
	rijndael_encrypt(ctx, (const uint32_t )in, (uint32_t )out);
	}

	static void md_init(mdCtx *ctx)
	{
	SHA256_Init(ctx);
	}

	static void md_update(mdCtx ctx, const uint8_t data, int len)
	{
	SHA256_Update(ctx, data, len);
	}

	static void md_result(mdCtx ctx, uint8_t dst)
	{
	SHA256Ctx tmp;

	memmove(&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 < numPools; 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, uint8_t dst)
	{
	ciph_encrypt(&st->ciph, st->counter, dst);
	inc_counter(st);
	}

	/*
	* The time between reseed must be at least reseedInterval
	* microseconds.
	*/
	static int enough_time_passed(FState *st)
	{
	int ok;
	int32_t now;
	int32_t last = st->lastReseedTime;

	now = tsc2sec(read_tsc());

	/* check how much time has passed */
	ok = 0;
	if (now - last >= reseedInterval)
	ok = 1;

	/* reseed will happen, update lastReseedTime */
	if (ok)
	st->lastReseedTime = now;

	return ok;
	}

	/*
	* generate new key from all the pools
	*/
	static void reseed(FState *st)
	{
	unsigned k;
	unsigned n;
	mdCtx key_md;
	uint8_t buf[block];

	/* set pool as empty */
	st->pool0Bytes = 0;

	/*
	* Both #0 and #1 reseed would use only pool 0. Just skip #0 then.
	*/
	n = ++st->reseedCount;

	/*
	* The goal: use k-th pool only 1/(2^k) of the time.
	*/
	md_init(&key_md);
	for (k = 0; k < numPools; 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->rndPos] % numPools;

	st->rndPos++;
	if (st->rndPos >= block)
	st->rndPos = 0;

	return rnd;
	}

	/*
	* update pools
	*/
	static void add_entropy(FState st, const uint8_t data, unsigned len)
	{
	unsigned pos;
	uint8_t hash[block];
	mdCtx 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->reseedCount == 0)
	pos = 0;
	else
	pos = get_rand_pool(st);
	md_update(&st->pool[pos], hash, block);

	if (pos == 0)
	st->pool0Bytes += 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 + ciphBlock);
	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;
	uint8_t buf[block];

	/* Use next block as counter. */
	encrypt_counter(st, st->counter);

	/* Now shuffle pools, excluding #0 */
	for (i = 1; i < numPools; i++) {
	encrypt_counter(st, buf);
	encrypt_counter(st, buf + ciphBlock);
	md_update(&st->pool[i], buf, block);
	}
	memset(buf, 0, block);

	/* Hide the key. */
	rekey(st);

	/* This can be done only once. */
	st->tricksDone = 1;
	}

	static void extract_data(FState st, unsigned count, uint8_t dst)
	{
	unsigned n;
	unsigned block_nr = 0;

	/* Should we reseed? */
	if (st->pool0Bytes >= pool0Fill \|\| st->reseedCount == 0)
	if (enough_time_passed(st))
	reseed(st);

	/* Do some randomization on first call */
	if (!st->tricksDone)
	startup_tricks(st);

	while (count > 0) {
	/* produce bytes */
	encrypt_counter(st, st->result);

	/* copy result */
	if (count > ciphBlock)
	n = ciphBlock;
	else
	n = count;
	memmove(dst, st->result, n);
	dst += n;
	count -= n;

	/* must not give out too many bytes with one key */
	block_nr++;
	if (block_nr > (reseedBytes / ciphBlock)) {
	rekey(st);
	block_nr = 0;
	}
	}
	/* Set new key for next request. */
	rekey(st);
	}

	static FState mainState;
	static int initDone;

	static void init()
	{
	init_state(&mainState);
	initDone = 1;
	}

	/*
	* public interface
	*/

	void fortuna_add_entropy(const uint8_t *data, unsigned len)
	{
	if (!initDone)
	init();

	if (!data \|\| !len)
	return;
	add_entropy(&mainState, data, len);
	}

	void fortuna_get_bytes(unsigned len, uint8_t *dst)
	{
	if (!initDone)
	init();

	if (!dst \|\| !len)
	return;
	extract_data(&mainState, len, dst);
	}