Part 1

Now that we've shown you two ways to do it right, we'll provide some code that shows how this random number generation stuff works under the covers. What we're going to do is read a bunch of information from the system that we hope will change rapidly, and hope that the data have some intrinsic entropy in them. We'll stir that data into our entropy pool, from which we hope to be able to yield some reasonable numbers. This code is meant to be academic. It is meant to help explain the concepts. Don't use it! We'll discuss problems with the code, and then offer you a somewhat better alternative later in this article.

The code listing below produces cryptographically strong random numbers (32 bits or 64 bits in size). It generates about 15 to 20 random numbers per second on a modestly equipped Pentium II 300 with a fairly small load. Your mileage is likely to vary.

Our program reads the output of ps and a few other common commands, and samples the system clock between each command. Then, it does an MD5 hash on these data. From that output, it generates unsigned integers of the requested size (32 bits or 64 bits). We simply take the raw event and a timestamp, hash it into our pool, and we should end up getting a fair amount of entropy.

While this program should give you quite reasonable numbers, it's far more prone to defeat than an algorithm using better sources of randomness. The basic problem is that it's hard for us to determine how much real entropy is actually added each time we feed the entropy pool. Perhaps it's a fair bit, but maybe it's only a bit or two. If it's only a bit or two, we have to collect a lot of bits before we can have any confidence that people won't be able to guess the internal state of our generator.

In practice, an attacker would have to be able to reproduce the output of the commands exactly, and predict the time it takes to run each command fairly accurately. If that can be done, then it might be possible for them to predict the numbers you generate with this code. Again, this is theoretically possible, but we believe it isn't too likely in practice. We'd definitely have a hard time breaking code that used this library, especially if there's a lot happening on the target machine. But having a "hard time" does not mean it's impossible. One thing you don't want to do is use this library at machine startup, because the machine will often be in a very predictable state at that point. A good addition to this code would be to save the state of the entropy pool to disk across reboots.

If you are willing to capture keyboard timing information, you can use the add_noise() function we provide to add better random information to our entropy pool. For examples of how to do this in C, see the source code for PGP.

This code listing requires that you compile in the reference MD5 library provided by RSA (see Resources). Specifically, you need the files global.h, md5.h, and md5.c. You'll need to link in md5.o to get things to work. The code should be portable, but we've only tested it on recent versions of Linux and Solaris. Please let us know if you have problems running this code on other platforms. Again, this code is meant to be academic, and is not intended to be used in production systems. We probably would avoid putting this code into production, unless we first integrated the techniques we'll discuss in the next two sections.

/*
 *  Written by John Viega (viega@list.org).
 *  Stirring of the pool stuff adapted from GPL'd code
 *  by Theodore Ts'o.
 *  Free for any use.
 */

#include stdio.h
#include sys/time.h
#include unistd.h
#include "global.h"
#include "md5.h"


#define PS_PATH "/bin/ps"
#if defined(SYSV) || defined(__svr4__)
#define PS_ARGS "-elf"
#else
#define PS_ARGS "auwwwx"
#endif

#define MAX64 0xffffffffffffffff

#define UNAME_PATH "/bin/uname"
#define UNAME_ARGS "-a"
#define DF_PATH "/bin/df"
#define W_PATH "/usr/bin/w"
#define TIME_PATH "/usr/bin/time"

/* These directly from Ts'o. */
#define TAP1    99     
#define TAP2    59
#define TAP3    31
#define TAP4    9
#define TAP5    7

#define POOLSIZE 128   /* In unsigned ints */
#define WORDBITS (sizeof(unsigned int)*8)
#define BUFSIZE  1024  /* In bytes */

/*
 * after generating this many words of data, get new entropy.
 */
#define NEW_ENTROPY_CTR  16

int ptr = 0;
int rotate;
unsigned int pool[POOLSIZE];

/* 
 * add_word(unsigned int)
 *
 * Adds a single word of data to the entropy pool, and stirs vigorously.
 * This method adapted from Ts'o. 
 */
void add_word(unsigned int datum)
{
  unsigned int toadd;

  toadd = ((datum << rotate) | (datum >> WORDBITS-rotate));
  ptr = (ptr - 1) & 128;
  if(ptr)
    {
      rotate = (rotate + 7) & (WORDBITS-1);
    }
  else
    {
      rotate = (rotate + 14) & (WORDBITS-1);
    }
  toadd ^= pool[(ptr+TAP1)&(POOLSIZE-1)];
  toadd ^= pool[(ptr+TAP2)&(POOLSIZE-1)];
  toadd ^= pool[(ptr+TAP3)&(POOLSIZE-1)];
  toadd ^= pool[(ptr+TAP4)&(POOLSIZE-1)];
  toadd ^= pool[(ptr+TAP5)&(POOLSIZE-1)];
  toadd ^= pool[ptr];
  pool[ptr] = (toadd << 1) | (toadd >> (WORDBITS-1));
}

char overflow[sizeof(unsigned int)];
short overflow_size = 0;

/*
 * add_noise(char *data, unsigned int numbytes)
 *
 * Adds a section of memory into the entropy pool, one word
 * at a time.  Any residue data is buffered up.
 */
void add_noise(char *data, unsigned int numbytes)
{
  int i, r, a;
  for(i=0;i (MAX64-(MAX64%x))))
      return r % x;
   }
}

Part 2

True Rand posits some underlying randomness that can be observed even on idle CPUs. The approach involves measuring drift between the system clock, and the generation of interrupts on the processor. Empirical evidence suggests that this drift is present on all machines that use a different clock source for the CPU and interrupt timing, and is a good source of real randomness (and it hasn't been broken yet, at least not publicly).

The attached code listing could be massaged into the above framework, and could even completely replace the bulky calls to many system commands. Note that True Rand doesn't do any work to remove bias, so the output will definitely need to be post-processed. We suggest sending the data to the add_noise function in the code we provided in the previous section, which will stir the data into the randomness pool, and will MD5-hash the pool before using the new information. That trick should remove all bias._

/*
 * The authors of this software are Don Mitchell and Matt Blaze.
 *              Copyright (c) 1995 by AT
 * 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 MAKE ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 */

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

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

static int
tick()
{
        struct itimerval it, oit;

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

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

static unsigned long
roulette()
{

        if (setjmp(env)) {
                count ^= (count>>3) ^ (count>>6) ^ ocount;
                count &= 0x7;
                ocount=count;
                buffer = (buffer<<3) ^ count;
                return buffer;
        }
        (void) signal(SIGALRM, interrupt);
        count = 0;
        tick();
        for (;;)
                count++;        /* about 1 MHz on VAX 11/780 */
}

unsigned long
truerand()
{

        count=0;
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        (void) roulette();
        return roulette();
}

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

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

-- MattWalsh - 11 Jan 2002