Why do we need random numbers? There are a lot of reasons. You might be designing a communications protocol and need random timing parameters to prevent system lockups. You might be conducting a massive Monte Carlo simulation and need random numbers for various parameters. Or you might be designing a computer game and need random numbers to determine the results of different actions.
As common as they are, random numbers can be infuriatingly hard to generate on a computer. The very nature of a computer--a deterministic, digital Turing machine--is contrary to the notion of randomness.
One application where random numbers are essential is in cryptography. The security of a cryptographic system often hinges on the randomness of its keys. In this month's "Algorithm Alley," Colin Plumb discusses the random-number generator in the Pretty Good Privacy (PGP) e-mail security program. Colin is one of the designers and programmers of PGP, and has spent a lot of time thinking about this problem. His solution is elegant, efficient, effective, and has applications well beyond e-mail security.
The ANSI C rand() function does not return random numbers. This is not a bug; it's required by the ANSI C standard. Instead, the values returned are determined by the seed supplied to srand(). If you run the same program with the same seed, you get the same "random" numbers. The pattern may not be obvious to the casual observer, but if Las Vegas ran this way, there'd be fewer bright lights in the big city.
John von Neumann once said that "anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin." Sometimes you want truly random numbers. Any number of security and cryptographic applications require them. When it comes to checking for viruses, for example, CRCs are convenient and fast, but you can easily fake out a known polynomial. The Strongbox secure loader from Carnegie Mellon University, however, uses a random polynomial to achieve security while keeping the speed advantages of a CRC (see Camelot and Avalon: A Distributed Transaction Facility, edited by Jeffrey L. Eppinger).
There are ways to produce random bits in hardware; sampling a quantum effect such as radioactive decay, for instance. However, this is hard to calibrate and involves special hardware.
On the other hand, software in a properly working computer is deterministic--the antithesis of random. Still, a computer generally has to interact and receive input from real-world events, so it is possible to make use of a very unpredictable part of most computer systems: the person typing at the keyboard.
Although keystrokes are somewhat random, compression utilities illustrate just how predictable most text is. While it would be foolish to ignore this entropy, anticipating what someone types is akin to password guessing: difficult, but if you have the computational horsepower, conceivable.
A more fruitful source is timing. Many computers can time events down to the microsecond. And while typing patterns on familiar words or phrases are repeatable enough to be used for identification, there is still a large window of available noise. Our basic source for entropy comes from sampling system timers on every keystroke.
The problem that remains is to turn these timer values, which have a nonuniform distribution, into uniformly distributed random bits. This is where the software comes in.
Theory of Operation
The file randpool.c (see Listing Four) uses cryptographic techniques to "distill" the essential randomness from an arbitrary amount of sort-of-random seed material. As the file name suggests, the program maintains a pool of hopefully random bits, into which additional information is "stirred." The goal here is that if you have n bits of entropy in the pool ("Shannon information," if you're familiar with information theory), any n bits of the output are truly random.
Listing Four
/* randpool.h -- declarations for randpool.c */
#include "usuals.h"
#define RANDPOOLBITS 3072 /* Whatever size you need (must be > 512) */
void randPoolStir(void);
void randPoolAddBytes(byte const *buf, unsigned len);
void randPoolGetBytes(byte *buf, unsigned len);
byte randPoolGetByte(void);
/* randpool.c -- True random number computation and storage
* This is adapted from code in the Pretty Good Privacy (PGP) package.
* Written by Colin Plumb. */
#include <stdlib.h>
#include <string.h>
#include "randpool.h"
#include "md5.h"
#define RANDKEYWORDS 16 /* This is a parameter of the the MD5 algorithm */
/* The pool must be a multiple of the 16-byte (128-bit) MD5 block size */
#define RANDPOOLWORDS ((RANDPOOLBITS+127 & ~127) >> 5)
#if RANDPOOLWORDS <= RANDKEYWORDS
#error Random pool too small - please increase RANDPOOLBITS in randpool.h
#endif
/* Must be word-aligned, so make it words. Cast to bytes as needed. */
static word32 randPool[RANDPOOLWORDS]; /* Random pool */
static word32 randKey[RANDKEYWORDS]; /* Next stirring key */
static unsigned randPoolGetPos = sizeof(randPool); /* Position to get from */
static unsigned randKeyAddPos = 0; /* Position to add to */
/* "Stir in" any random seed material before removing any random bytes. */
void
randPoolStir(void)
{
int i;
word32 iv[4];
byteSwap(randPool, RANDPOOLWORDS); /* convert to word32s */
byteSwap(randKey, RANDKEYWORDS);
/* Start IV from last block of randPool */
memcpy(iv, randPool+RANDPOOLWORDS-4, sizeof(iv));
/* CFB pass */
for (i = 0; i < RANDPOOLWORDS; i += 4) {
MD5Transform(iv, randKey);
iv[0] = randPool[i ] ^= iv[0];
iv[1] = randPool[i+1] ^= iv[1];
iv[2] = randPool[i+2] ^= iv[2];
iv[3] = randPool[i+3] ^= iv[3];
}
memset(iv, 0, sizeof(iv)); /* Wipe IV from memory */
byteSwap(randPool, RANDPOOLWORDS); /* Convert back to bytes */
memcpy(randKey, randPool, sizeof(randKey)); /* Get new key */
randKeyAddPos = 0; /* Set up pointers for future use. */
randPoolGetPos = sizeof(randKey);
}
/* Make a deposit of information (entropy) into the pool. */
void
randPoolAddBytes(byte const *buf, unsigned len)
{
byte *p = (byte *)randKey+randKeyAddPos;
unsigned t = sizeof(randKey) - randKeyAddPos;
while (len > t) {
len -= t;
while (t--)
*p++ ^= *buf++;
randPoolStir(); /* sets randKeyAddPos to 0 */
p = (byte *)randKey;
t = sizeof(randKey);
}
if (len) {
randKeyAddPos += len;
do
*p++ ^= *buf++;
while (--len);
randPoolGetPos = sizeof(randPool); /* Force stir on get */
}
}
/* Withdraw some bits from the pool. */
void
randPoolGetBytes(byte *buf, unsigned len)
{
unsigned t;
while (len > (t = sizeof(randPool) - randPoolGetPos)) {
memcpy(buf, (byte const *)randPool+randPoolGetPos, t);
buf += t;
len -= t;
randPoolStir();
}
memcpy(buf, (byte const *)randPool+randPoolGetPos, len);
randPoolGetPos += len;
}
/* Get a single byte */
byte
randPoolGetByte(void)
{
if (randPoolGetPos == sizeof(randPool))
randPoolStir();
return ((byte const *)randPool)[randPoolGetPos++];
}
The stirring operation (actually nothing more than an encryption pass) is central. If you know the key and initial vector, you can reverse it to get back the initial state. Since the encryption is reversible, stirring the pool obviously does not lose information. So all the information in the initial state is there, it's just masked by the encryption.
Since we don't need to reverse the encryption, the key is then destroyed. The information is then reinitialized with data taken from the pool that was just stirred. This makes it essentially impossible to determine the previous state of the random-number pool from what is left in memory.
The cipher is Peter Gutmann's Message Digest Cipher using MD5 as a base. This is fast and simple (as strong ciphers go), especially on 32-bit machines. In this application, the large key size also helps efficiency. (For another application of this cipher, see Gutmann's shareware MS-DOS disk encryptor, "SFS." Every commercial MS-DOS disk encryptor I've seen--Norton Diskreet, for example--has appalling cryptography. Their only advantage is that you can get the data back with a few weeks' work if you lose the key. If you lose the key with SFS, it's lost.)
The output of the generator is taken from the pool, starting after the 64 bytes used for the next stirring key. If you reach the end of the pool, stir again and restart. After that, it is theoretically possible to examine the output and determine the key, which would reveal the complete state of the generator and let you predict its output forever. That, however, would require breaking the cipher by deriving the key from the data before and after encryption, an adequate guarantee of security.
Input is more interesting. To ensure that each bit of seed material affects the entire pool, the seed material is added (using XOR) to the key buffer. When you reach the end of the key buffer, stir the pool and start over. The difficulty of cryptanalysis (deriving the key from the prior and following states of the pool) ensures that regularities in the seed material do not produce regularities in the pool.
Adding bytes to the key sets the take position to the end of the pool, so the newly added data will be stirred in before any bytes are returned. Thus, you can add and remove bytes in any order.
The code mostly works with bytes, but since MD5 works with 32-bit words, a standard byte ordering is used. This way you can use it as a pseudorandom number generator seeded with a passphrase.
If you want to use the hash directly, md5.c (see Listing Two) includes a full implementation of the MD5 algorithm. (It is similar to the hash presented in "SHA: The Secure Hash Algorithm," by William Stallings, DDJ, April 1994.) If you have a large amount of low-grade seed material, you can use MD5 to pre-reduce it. For example, you can feed mouse-position reports into MD5, then periodically add the resultant 16-byte digest to the pool. Even faster algorithms are possible--based on CRCs and scrambler polynomials--if you have real-time constraints.
Listing Two
/* md5.h -- declarations for md5.c */
#ifndef MD5_H
#define MD5_H
#include "usuals.h"
struct MD5Context {
word32 hash[4];
word32 bytes[2];
word32 input[16];
};
void byteSwap(word32 *buf, unsigned words);
void MD5Init(struct MD5Context *context);
void MD5Update(struct MD5Context *context, byte const *buf, unsigned len);
void MD5Final(byte digest[16], struct MD5Context *context);
void MD5Transform(word32 hash[4], word32 const input[16]);
#endif /* !MD5_H */
/* md5.c -- An implementation of Ron Rivest's MD5 message-digest algorithm.
* Written by Colin Plumb in 1993, no copyright is claimed. This code is in the
* public domain; do with it what you wish. Equivalent code is available from
* RSA Data Security, Inc. This code does not oblige you to include legal
* boilerplate in the documentation. To compute the message digest of a string
* of bytes, declare an MD5Context structure, pass it to MD5Init, call
* MD5Update as needed on buffers full of bytes, and then call MD5Final, which
* will fill a supplied 16-byte array with the digest.
*/
#include <string.h> /* for memcpy() */
#include "md5.h"
/* Byte-swap an array of words to little-endian. (Byte-sex independent) */
void
byteSwap(word32 *buf, unsigned words)
{
byte *p = (byte *)buf;
do {
*buf++ = (word32)((unsigned)p[3]<<8 | p[2]) << 16 |
((unsigned)p[1]<<8 | p[0]);
p += 4;
} while (--words);
}
/* Start MD5 accumulation. */
void
MD5Init(struct MD5Context *ctx)
{
ctx->hash[0] = 0x67452301; ctx->hash[1] = 0xefcdab89;
ctx->hash[2] = 0x98badcfe; ctx->hash[3] = 0x10325476;
ctx->bytes[1] = ctx->bytes[0] = 0;
}
/* Update ctx to reflect the addition of another buffer full of bytes. */
void
MD5Update(struct MD5Context *ctx, byte const *buf, unsigned len)
{
word32 t = ctx->bytes[0];
if ((ctx->bytes[0] = t + len) < t) /* Update 64-bit byte count */
ctx->bytes[1]++; /* Carry from low to high */
t = 64 - (t & 0x3f); /* Bytes available in ctx->input (>= 1) */
if (t > len) {
memcpy((byte *)ctx->input+64-t, buf, len);
return;
}
/* First chunk is an odd size */
memcpy((byte *)ctx->input+64-t, buf, t);
byteSwap(ctx->input, 16);
MD5Transform(ctx->hash, ctx->input);
buf += t;
len -= t;
/* Process data in 64-byte chunks */
while (len >= 64) {
memcpy(ctx->input, buf, 64);
byteSwap(ctx->input, 16);
MD5Transform(ctx->hash, ctx->input);
buf += 64;
len -= 64;
}
/* Buffer any remaining bytes of data */
memcpy(ctx->input, buf, len);
}
/* Final wrapup - pad to 64-byte boundary with the bit pattern
* 1 0* (64-bit count of bits processed, LSB-first) */
void
MD5Final(byte digest[16], struct MD5Context *ctx)
{
int count = ctx->bytes[0] & 0x3F; /* Bytes mod 64 */
byte *p = (byte *)ctx->input + count;
/* Set the first byte of padding to 0x80. There is always room. */
*p++ = 0x80;
/* Bytes of zero padding needed to make 56 bytes (-8..55) */
count = 56 - 1 - count;
if (count < 0) { /* Padding forces an extra block */
memset(p, 0, count+8);
byteSwap(ctx->input, 16);
MD5Transform(ctx->hash, ctx->input);
p = (byte *)ctx->input;
count = 56;
}
memset(p, 0, count);
byteSwap(ctx->input, 14);
/* Append 8 bytes of length in *bits* and transform */
ctx->input[14] = ctx->bytes[0] << 3;
ctx->input[15] = ctx->bytes[1] << 3 | ctx->bytes[0] >> 29;
MD5Transform(ctx->hash, ctx->input);
byteSwap(ctx->hash, 4);
memcpy(digest, ctx->hash, 16);
memset(ctx, 0, sizeof(*ctx)); /* In case it's sensitive */
}
/* The four core functions */
#define F1(x, y, z) (z ^ (x & (y ^ z)))
#define F2(x, y, z) F1(z, x, y)
#define F3(x, y, z) (x ^ y ^ z)
#define F4(x, y, z) (y ^ (x | ~z))
/* This is the central step in the MD5 algorithm. */
#define MD5STEP(f,w,x,y,z,in,s) (w += f(x,y,z)+in, w = (w<<s | w>>32-s) + x)
/* The heart of the MD5 algorithm. */
void
MD5Transform(word32 hash[4], word32 const input[16])
{
register word32 a = hash[0], b = hash[1], c = hash[2], d = hash[3];
MD5STEP(F1, a, b, c, d, input[ 0]+0xd76aa478, 7);
MD5STEP(F1, d, a, b, c, input[ 1]+0xe8c7b756, 12);
MD5STEP(F1, c, d, a, b, input[ 2]+0x242070db, 17);
MD5STEP(F1, b, c, d, a, input[ 3]+0xc1bdceee, 22);
MD5STEP(F1, a, b, c, d, input[ 4]+0xf57c0faf, 7);
MD5STEP(F1, d, a, b, c, input[ 5]+0x4787c62a, 12);
MD5STEP(F1, c, d, a, b, input[ 6]+0xa8304613, 17);
MD5STEP(F1, b, c, d, a, input[ 7]+0xfd469501, 22);
MD5STEP(F1, a, b, c, d, input[ 8]+0x698098d8, 7);
MD5STEP(F1, d, a, b, c, input[ 9]+0x8b44f7af, 12);
MD5STEP(F1, c, d, a, b, input[10]+0xffff5bb1, 17);
MD5STEP(F1, b, c, d, a, input[11]+0x895cd7be, 22);
MD5STEP(F1, a, b, c, d, input[12]+0x6b901122, 7);
MD5STEP(F1, d, a, b, c, input[13]+0xfd987193, 12);
MD5STEP(F1, c, d, a, b, input[14]+0xa679438e, 17);
MD5STEP(F1, b, c, d, a, input[15]+0x49b40821, 22);
MD5STEP(F2, a, b, c, d, input[ 1]+0xf61e2562, 5);
MD5STEP(F2, d, a, b, c, input[ 6]+0xc040b340, 9);
MD5STEP(F2, c, d, a, b, input[11]+0x265e5a51, 14);
MD5STEP(F2, b, c, d, a, input[ 0]+0xe9b6c7aa, 20);
MD5STEP(F2, a, b, c, d, input[ 5]+0xd62f105d, 5);
MD5STEP(F2, d, a, b, c, input[10]+0x02441453, 9);
MD5STEP(F2, c, d, a, b, input[15]+0xd8a1e681, 14);
MD5STEP(F2, b, c, d, a, input[ 4]+0xe7d3fbc8, 20);
MD5STEP(F2, a, b, c, d, input[ 9]+0x21e1cde6, 5);
MD5STEP(F2, d, a, b, c, input[14]+0xc33707d6, 9);
MD5STEP(F2, c, d, a, b, input[ 3]+0xf4d50d87, 14);
MD5STEP(F2, b, c, d, a, input[ 8]+0x455a14ed, 20);
MD5STEP(F2, a, b, c, d, input[13]+0xa9e3e905, 5);
MD5STEP(F2, d, a, b, c, input[ 2]+0xfcefa3f8, 9);
MD5STEP(F2, c, d, a, b, input[ 7]+0x676f02d9, 14);
MD5STEP(F2, b, c, d, a, input[12]+0x8d2a4c8a, 20);
MD5STEP(F3, a, b, c, d, input[ 5]+0xfffa3942, 4);
MD5STEP(F3, d, a, b, c, input[ 8]+0x8771f681, 11);
MD5STEP(F3, c, d, a, b, input[11]+0x6d9d6122, 16);
MD5STEP(F3, b, c, d, a, input[14]+0xfde5380c, 23);
MD5STEP(F3, a, b, c, d, input[ 1]+0xa4beea44, 4);
MD5STEP(F3, d, a, b, c, input[ 4]+0x4bdecfa9, 11);
MD5STEP(F3, c, d, a, b, input[ 7]+0xf6bb4b60, 16);
MD5STEP(F3, b, c, d, a, input[10]+0xbebfbc70, 23);
MD5STEP(F3, a, b, c, d, input[13]+0x289b7ec6, 4);
MD5STEP(F3, d, a, b, c, input[ 0]+0xeaa127fa, 11);
MD5STEP(F3, c, d, a, b, input[ 3]+0xd4ef3085, 16);
MD5STEP(F3, b, c, d, a, input[ 6]+0x04881d05, 23);
MD5STEP(F3, a, b, c, d, input[ 9]+0xd9d4d039, 4);
MD5STEP(F3, d, a, b, c, input[12]+0xe6db99e5, 11);
MD5STEP(F3, c, d, a, b, input[15]+0x1fa27cf8, 16);
MD5STEP(F3, b, c, d, a, input[ 2]+0xc4ac5665, 23);
MD5STEP(F4, a, b, c, d, input[ 0]+0xf4292244, 6);
MD5STEP(F4, d, a, b, c, input[ 7]+0x432aff97, 10);
MD5STEP(F4, c, d, a, b, input[14]+0xab9423a7, 15);
MD5STEP(F4, b, c, d, a, input[ 5]+0xfc93a039, 21);
MD5STEP(F4, a, b, c, d, input[12]+0x655b59c3, 6);
MD5STEP(F4, d, a, b, c, input[ 3]+0x8f0ccc92, 10);
MD5STEP(F4, c, d, a, b, input[10]+0xffeff47d, 15);
MD5STEP(F4, b, c, d, a, input[ 1]+0x85845dd1, 21);
MD5STEP(F4, a, b, c, d, input[ 8]+0x6fa87e4f, 6);
MD5STEP(F4, d, a, b, c, input[15]+0xfe2ce6e0, 10);
MD5STEP(F4, c, d, a, b, input[ 6]+0xa3014314, 15);
MD5STEP(F4, b, c, d, a, input[13]+0x4e0811a1, 21);
MD5STEP(F4, a, b, c, d, input[ 4]+0xf7537e82, 6);
MD5STEP(F4, d, a, b, c, input[11]+0xbd3af235, 10);
MD5STEP(F4, c, d, a, b, input[ 2]+0x2ad7d2bb, 15);
MD5STEP(F4, b, c, d, a, input[ 9]+0xeb86d391, 21);
hash[0] += a; hash[1] += b; hash[2] += c; hash[3] += d;
}
Practice of Operation
The file noise.c (see Listing Three) samples a variety of system timers and adds them to the random-number pool. It also returns the number of highest-resolution ticks since the previous call, which you can use to estimate the entropy of this sample. On an IBM PC, only 16 bits are returned; this underestimates the result if the calls are more than 1/18.2 seconds apart, but that is not a security problem.
Listing Three
/* noise.h -- get environmental noise for RNG */
#include "usuals.h"
word32 noise(void);
/* noise.c -- Get environmental noise.
* This is adapted from code in the Pretty Good Privacy (PGP) package.
* Written by Colin Plumb. */
#include <time.h>
#include "usuals.h"
#include "randpool.h"
#include "noise.h"
#if defined(MSDOS) || defined(__MSDOS__) /* Use 1.19 MHz PC timer */
#include <dos.h> /* for enable() and disable() */
#include <conio.h> /* for inp() and outp() */
/* This code gets as much information as possible out of 8253/8254 timer 0,
* which ticks every .84 microseconds. There are three cases:
* 1) Original 8253. 15 bits available, as the low bit is unused.
* 2) 8254, in mode 3. The 16th bit is available from the status register.
* 3) 8254, in mode 2. All 16 bits of the counters are available.
* (This is not documented anywhere, but I've seen it!)
* This code repeatedly tries to latch the status (ignored by an 8253) and
* sees if it looks like xx1101x0. If not, it's definitely not an 8254.
* Repeat this a few times to make sure it is an 8254. */
static int
has8254(void)
{
int i, s1, s2;
for (i = 0; i < 5; i++) {
disable();
outp(0x43, 0xe2); /* Latch status for timer 0 */
s1 = inp(0x40); /* If 8253, read timer low byte */
outp(0x43, 0xe2); /* Latch status for timer 0 */
s2 = inp(0x40); /* If 8253, read timer high byte */
enable();
if ((s1 & 0x3d) != 0x34 || (s2 & 0x3d) != 0x34)
return 0; /* Ignoring status latch; 8253 */
}
return 1; /* Status reads as expected; 8254 */
}
static unsigned
read8254(void)
{
unsigned status, count;
disable();
outp(0x43, 0xc2); /* Latch status and count for timer 0 */
status = inp(0x40);
count = inp(0x40);
count |= inp(0x40) << 8;
enable();
/* The timer is usually in mode 3, but some BIOSes use mode 2. */
if (status & 2)
count = count>>1 | (status & 0x80)<<8;
return count;
}
static unsigned
read8253(void)
{
unsigned count;
disable();
outp(0x43, 0x00); /* Latch count for timer 0 */
count = (inp(0x40) & 0xff);
count |= (inp(0x40) & 0xff) << 8;
enable();
return count >> 1;
}
#endif /* MSDOS || __MSDOS__ */
#ifdef UNIX
#include <sys/types.h>
#include <sys/time.h> /* For gettimeofday() */
#include <sys/times.h> /* for times() */
#include <stdlib.h> /* For qsort() */
#define N 15 /* Number of deltas to try (at least 5, preferably odd) */
/* Function needed for qsort() */
static int
noiseCompare(void const *p1, void const *p2)
{ return *(int const *)p1 - *(int const *)p2; }
/* Find the resolution of the gettimeofday() clock */
static unsigned
noiseTickSize(void)
{
int i = 0, j = 0, d[N];
struct timeval tv0, tv1, tv2;
gettimeofday(&tv0, (struct timezone *)0);
tv1 = tv0;
do {
gettimeofday(&tv2, (struct timezone *)0);
if (tv2.tv_usec > tv1.tv_usec+2) {
d[i++] = tv2.tv_usec - tv0.tv_usec +
1000000 * (tv2.tv_sec - tv0.tv_sec);
tv0 = tv2;
j = 0;
} else if (++j > 10000) /* Always getting <= 2 us, */
return 2; /* so assume 2us ticks */
tv1 = tv2;
} while (i < N);
/* Return average of middle 5 values (rounding up) */
qsort(d, N, sizeof(d[0]), noiseCompare);
return (d[N/2-2]+d[N/2-1]+d[N/2]+d[N/2+1]+d[N/2+2]+4)/5;
}
#endif /* UNIX */
/* Add as much time-dependent random noise to the randPool as possible. */
word32
noise(void)
{
static word32 lastcounter;
word32 delta;
time_t tnow;
clock_t cnow;
#if defined(MSDOS) || defined(__MSDOS__)
static unsigned deltamask = 0;
unsigned t;
if (deltamask == 0)
deltamask = has8254() ? 0xffff : 0x7fff;
t = (deltamask & 0x8000) ? read8254() : read8253();
randPoolAddBytes((byte const *)&t, sizeof(t));
delta = deltamask & (t - (unsigned)lastcounter);
lastcounter = t;
#elif defined(VMS)
word32 t[2];
SYS$GETTIM(t); /* VMS hardware clock increments by 100000 per tick */
randPoolAddBytes((byte const *)t, sizeof(t));
delta = (t[0]-lastcounter)/100000;
lastcounter = t[0];
#elif defined(UNIX)
static unsigned ticksize = 0;
struct timeval tv;
struct tms tms;
gettimeofday(&tv, (struct timezone *)0);
randPoolAddBytes((byte const *)&tv, sizeof(tv));
cnow = times(&tms);
randPoolAddBytes((byte const *)&tms, sizeof(tms));
randPoolAddBytes((byte const *)&cnow, sizeof(cnow));
tv.tv_usec += tv.tv_sec * 1000000; /* Unsigned, so wrapping is okay */
if (!ticksize)
ticksize = noiseTickSize();
delta = (tv.tv_usec-lastcounter)/ticksize;
lastcounter = tv.tv_usec;
#else
#error Unknown operating system
#endif
cnow = clock();
randPoolAddBytes((byte const *)&cnow, sizeof(cnow));
tnow = time((time_t *)0); /* Read slowest clock last */
randPoolAddBytes((byte const *)&tnow, sizeof(tnow));
return delta;
}
The code also works under UNIX. You may have to find the frequency of a timer that only returns ticks; noiseTickSize() finds the resolution of a timer (the gettimeofday() function) that only returns seconds.
The main driver is in randtest.c (see Listing One). A flash effect is provided by funnyprint(). Of more value is randRange(), which illustrates a way to generate uniformly distributed random numbers in a range not provided by the generator. The problem is akin to generating numbers from 1 to 5 using a six-sided die. The solution amounts to rerolling if you get a 6.
Listing One
/* usuals.h -- Useful typedefs */
#ifndef USUALS_H
#define USUALS_H
#include <limits.h>
#if UCHAR_MAX == 0xFF
typedef unsigned char byte; /* 8-bit byte */
#else
#error No 8-bit type found
#endif
#if UINT_MAX == 0xFFFFFFFF
typedef unsigned int word32; /* 32-bit word */
#elif ULONG_MAX == 0xFFFFFFFF
typedef unsigned long word32;
#else
#error No 32-bit type found
#endif
#endif /* USUALS_H */
/* randtest.c -- Test application for the random-number routines */
#include <stdio.h>
#include <string.h>
#include <stdlib.h> /* For rand(), srand() and RAND_MAX */
#include "randpool.h"
#include "noise.h"
/* This function returns pseudo-random numbers uniformly from 0..range-1. */
static unsigned
randRange(unsigned range)
{
unsigned result, div = ((unsigned)RAND_MAX+1)/range;
while ((result = rand()/div) == range)
/* retry */ ;
return result;
}
/* Cute Wargames-like random effect thrown in for fun */
static void
funnyprint(char const *string)
{
static const char alphabet[] =
"ABCDEFGHIJKLMNOPWRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890";
char c, flag[80] = {0}; /* 80 is maximum line length */
unsigned i, tumbling = 0, len = strlen(string);
/* We don't need good random numbers, so just use a good seed */
randPoolGetBytes((byte *)i, sizeof(i));
srand(i); /* Sometimes simple PRNGs are useful! */
/* Truncate longer strings (unless you have a better idea) */
if (len > sizeof(flag))
len = sizeof(flag);
/* Count letters that we can tumble (letters in the alphabet) */
for (i = 0; i < len; i++) {
if (strchr(alphabet, string[i])) {
flag[i] = 1; /* Increase this for more tumbling */
tumbling++;
}
}
/* Print until all characters are stable. */
do {
putchar('\r');
for (i = 0; i < len; i++) {
if (flag[i]) {
c = alphabet[randRange(sizeof(alphabet)-1)];
if (c == string[i] && --flag[i] == 0)
tumbling--;
} else {
c = string[i];
}
putchar(c);
}
fflush(stdout);
} while (tumbling);
putchar('\n');
}
#include <conio.h> /* For getch() */
#define FRACBITS 4 /* We count in 1/16 of a bit increments. */
/* Gather entropy from keyboard timing. This is currently MS-DOS specific. */
static void
randAccum(int bits)
{
word32 delta;
int c, oldc = 0, olderc = 0;
if (bits > RANDPOOLBITS)
bits = RANDPOOLBITS;
bits <<= FRACBITS;
puts("We are generating some truly random bits by timing your\n"
"keystrokes. Please type until the counter reaches 0.\n");
while (bits > 0) {
printf("\r%4d ", (bits-1 >> FRACBITS) + 1);
c = getch();
delta = noise()/6; /* Add time of keystroke */
if (c == 0)
c = 0x100 + getch(); /* Handle function keys */
randPoolAddBytes((byte const *)&c, sizeof(c));
/* Normal typing has double letters, but discard triples */
if (c == oldc && c == olderc)
continue;
olderc = oldc;
oldc = c;
if (delta) { /* Subtract log2(delta) from bits */
/* Integer bits first, normalizing */
bits -= 31<<FRACBITS;
while (delta < 1ul<<31) {
bits += 1<<FRACBITS;
delta <<= 1;
}
/* Fractional bits, using integer log algorithm */
for (c = 1 << FRACBITS-1; c; c >>= 1) {
delta >>= 16;
delta *= delta;
if (delta >= 1ul<<31)
bits -= c;
else
delta <<= 1;
}
}
}
puts("\r 0 Thank you, that's enough.");
}
/* When invoked with the argument "foo", this should start with:
* Adding "foo\0" to pool. Pseudo-random bytes:
* 4c 9d 41 ba 44 41 63 a1 db 1c ab 3f 52 a1 a2 84 c3 e5 dc bc 57 4c d9 f3 38
* d7 45 50 f9 94 36 96 a3 df 90 ff 23 e5 ec 3c 76 1f ce 1c bc d6 79 8b 5e e7
* aa 97 16 c0 50 c6 95 0b c1 62 42 e5 5b 8f d7 bd d7 70 1f c6 60 6a 5f f3 74
* 8d 35 ad 51 5a 4a 0c 02 cd d5 36 7e d4 c2 d9 f0 d3 49 ed 2d fa 4e 2b 70 3f
*/
int
main(int argc, char **argv)
{
int i;
while (--argc) {
printf("Adding \"%s\\0\" to the pool.\n", *++argv);
randPoolAddBytes((byte const *)*argv, strlen(*argv)+1);
}
puts("\nPseudo-random bytes:");
i = 100;
while (i--)
printf("%02x%c", randPoolGetByte(), i % 25 ? ' ' : '\n');
putchar('\n');
funnyprint("This will be deterministic on a given system.");
putchar('\n');
noise(); /* Establish a baseline for the deltas */
randAccum(800); /* 800 random bits = 100 random bytes */
puts("\nTruly random bytes:");
i = 100;
while (i--)
printf("%02x%c", randPoolGetByte(), i % 25 ? ' ' : '\n');
putchar('\n');
funnyprint("This will be unpredictable.");
return 0;
}
The most interesting part is rand-Accum(), which accumulates a specified amount of entropy from the keyboard. It uses the number of ticks returned by the noise() function to estimate the entropy. It assumes that inter-keystroke times vary pretty uniformly over a range of 15 percent or so. Thus, it divides the tick count by 6 to get the fraction of the interval that is random, then takes the logarithm to get the number of bits of entropy.
The integer number of bits comes from normalizing the number and counting the shifts. The entropy is kept to four fractional bits using a few iterations of an integer-logarithm algorithm.
Weaknesses
I don't know of any exploitable holes in this approach to generating random numbers, but in cryptography, only a fool is sure he has a good algorithm. I believe the following points need further examination:
- The divide-by-six approximation in randAccum(). This was chosen so a machine with only a 60-Hz clock would produce at least one bit per keystroke; not a very good reason. A much better technique is suggested by Ueli Maurer's paper from Crypto '90, "A Universal Statistical Test For Random Bit Generators." However, this technique is slow to decide that the input is trustworthy and requires large tables.
- The "leakage" rate of information from the pool. Because the stirring key is drawn from the pool itself, collisions are possible. These are states of the pool which, after stirring, result in the same output state. This reduces the information content of the pool.
- The use of MD5 as a cipher. If you are using this as a cryptographic PRNG and producing large amounts of output from a smaller seed, the cipher at the heart of the stirring may be broken. The amount of known plaintext available from any given stirring is quite low (a few hundred bytes), the key space is dauntingly large (512 bits), and no such attacks on MD5 have appeared in the civilian literature; however, MD5 was not designed for use as a cipher and has had less study in this mode.
References
Eppinger, Jeffrey L., Lily B. Mummert, and Alfred Z. Spector, eds. Camelot and Avalon: A Distributed Transaction Facility. San Mateo, CA: Morgan Kaufman, 1991.
Maurer, Ueli M. "A Universal Statistical Test for Random Bit Generators," in Advances in Cryptology--Crypto '90. Berlin: Springer-Verlag, 1991.
Davis, Donald T., Ross Ihaka, and Philip Fenstermacher. "Cryptographic Randomness From Air Turbulence in Disk Drives," in Advances in Cryptology--Crypto '94. Berlin: Springer-Verlag, 1994.
Knuth, Donald E. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. Reading, MA: Addison-Wesley, 1981.
Colin, a student from Toronto, was introduced to modern cryptography by the Pretty Good Privacy package. He can be contacted at [email protected].
