/*
 *	Almost "true" random numbers (very nearly uniform)
 *	Based on code by D. P. Mitchell
 *	Modified by Matt Blaze 7/95, 11/96
 *	Version 2.1
 *
 *	This is completely unsupported software.
 *
 */
/*
 * The authors of this software are Don Mitchell and Matt Blaze.
 *              Copyright (c) 1995, 1996 by AT&T.
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software and in all copies of the supporting
 * documentation for such software.
 
 *
 * This software may be subject to United States export controls.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

/*
 * Truerand is a dubious, unproven hack for generating "true" random
 * numbers in software.  It is at best a good "method of last resort"
 * for generating key material in environments where there is no (or
 * only an insufficient) source of better-understood randomness.  It
 * can also be used to augment unreliable randomness sources (such as
 * input from a human operator).
 *
 * The basic idea behind truerand is that between clock "skew" and
 * various hard-to-predict OS event arrivals, counting a tight loop
 * will yield a little bit (maybe one bit or so) of "good" randomness
 * per interval clock tick.  This seems to work well in practice even
 * on unloaded machines.  If there is a human operator at the machine,
 * you should augment trand with other measurements, such as keyboard
 * event timing.  On server machines (e.g., where you need to generate
 * a Diffie-Hellman secret but have no operator to type keys) trand
 * alone may (or may not) be sufficient.
 *
 * Because the randomness source is not well-understood, I've made
 * fairly conservative assumptions about how much randomness can be
 * extracted in any given interval.  Based on a cursory analysis of
 * the BSD kernel, there seem to be about 100-200 bits of unexposed
 * "state" that changes each time a system call occurs and that affect
 * the exact handling of interrupt scheduling, plus a great deal of
 * slower-changing but still hard-to-model state based on, e.g., the
 * process table, the VM state, etc.  There is no proof or guarantee
 * that some of this state couldn't be easily reconstructed, modeled
 * or influenced by an attacker, however, so we keep a large margin
 * for error.  The truerand API assumes only 0.3 bits of entropy per
 * interval interrupt, amortized over 24 intervals and whitened with
 * SHA.
 *
 * The trurand API is in randbyte.c, and consists of trand8(),
 * trand16(), and trand32().  Do not use raw_truerand() directly.
 * 
 * WARNING: depending on the particular platform, raw_truerand()
 * output may be biased or correlated.  In general, you can expect no
 * more than 8-16 bits of "pseudo-entropy" out of each 32 bit word.
 * Always run the output through a good post-whitening function (like
 * SHA, MD5 or DES or whatever) before using it to generate key
 * material.  The API does this for you, providing 8, 16, and 32 bit
 * properly "whitened" random numbers (trand8(), trand16(), and
 * trand32(), respectively).  Use the trand calls instead of calling
 * raw_truerand() directly.
 *
 * Test truerand on your own platform before fielding a system based
 * on this software or these techniques.
 *
 * This software seems to work well (at 10 or so bits per
 * raw_truerand() call) on a Sun Sparc-20 under SunOS 4.1.3 and on a
 * P100 under BSDI 2.0.  You're on your own elsewhere.
 *
 * This version of truerand doesn't clobber the ITIMER, so any
 * scheduled alarms will still occur (though alarms cannot occur while
 * raw_truerand is running and will be delayed by about 250ms per
 * raw_truerand call.
 */

#include <signal.h>
#include <setjmp.h>
#include <sys/time.h>
#include <math.h>
#include <stdio.h>

#include <inttypes.h>

#include "truerand.h"

static jmp_buf env;
static unsigned count;
static unsigned ocount;
static unsigned buffer;

static void
tick(void)
{
	struct itimerval it;

	timerclear(&it.it_interval);
	it.it_value.tv_sec = 0;
	it.it_value.tv_usec = 16665;
	if (setitimer(ITIMER_REAL, &it, NULL) < 0)
		perror("tick");
}

static void
interrupt(int junk)
{
	if (count)
		longjmp(env, 1);
	(void) signal(SIGALRM, interrupt);
	tick();
}

static uint32_t
roulette(void)
{
	if (setjmp(env))
		return count;
	(void) signal(SIGALRM, interrupt);
	count = 0;
	tick();
	for (;;)
		count++;	/* about 1 MHz on VAX 11/780 */
}

/*
 * basic interface to 32 bit truerand.
 * note that any scheduled SIGALRM will be delayed by about .3 secs.
 */
uint32_t
raw_truerand(void)
{
	void (*oldalrm)();
	struct itimerval it;
	uint32_t counts[12];
	unsigned char *qshs();
	unsigned char *r;
	uint32_t buf;
	int i;

	getitimer(ITIMER_REAL, &it);
	oldalrm = signal(SIGALRM, SIG_IGN);
	for (i=0; i<12; i++) {
		counts[i]=0;
		while ((counts[i] += roulette()) < 512)
			;
	}
	signal(SIGALRM, oldalrm);
	setitimer(ITIMER_REAL, &it, NULL);

	r = qshs(counts,sizeof(counts));
	buf = *((uint32_t *) r);

	return buf;
}

int
raw_n_truerand(int n)
{
	int slop, v;

	slop = 0x7FFFFFFF % n;
	do {
		v = raw_truerand() >> 1;
	} while (v <= slop);
	return v % n;
}



/*
 *	Random byte interface to truerand()
 *	Matt Blaze 9/95
 *	8, 16, 32 really random bits, at about .35 bits per clock
 *      interrupt.
 *
 *	usage: 
 *		unsigned char r8;
 *		unsigned short r16;
 *		uint32_t r32;
 *		uint32_t trand8(), trand16(), trand32();
 *		r8=trand8();
 *		r16=trand16();
 *		r32=trand32();
 *
 *	randbyte() is the same as trand8().
 *	trand8() takes about .3 seconds on most machines.
 */
/*
 * The author of this software is Matt Blaze.
 *              Copyright (c) 1995 by AT&T.
 * Permission to use, copy, and modify this software without fee
 * is hereby granted, provided that this entire notice is included in
 * all copies of any software which is or includes a copy or
 * modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

uint32_t
randbyte(void)
{
	uint32_t raw_truerand();
	unsigned char *qshs();
	uint32_t r[2];
	unsigned char *hash;

	r[0]=raw_truerand(); r[1]=raw_truerand();
	hash = qshs(r,sizeof(r));
	return ((int) (*hash)) & 0xff;
}

uint32_t
trand8(void)
{
	return randbyte();
}

uint32_t
trand16(void)
{
	return randbyte() ^ (randbyte()<<8);
}

uint32_t
trand32(void)
{
	return randbyte() ^ (randbyte()<<8)
		^ (randbyte()<<16) ^ (randbyte()<<24);
}

