/* * 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 #include #include #include #include #include #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); }