ONLamp.com
oreilly.comSafari Books Online.Conferences.

advertisement


Secure Programming Techniques, Part 4
Pages: 1, 2, 3

A Good Random Seed Generator

As we've mentioned, one way of generating a random seed is to use a source message digest algorithm such as MD5 or SHA-1. As input, give it as much data as you can based on temporary state. This data might include the output of ps -efl, the environment variables for the current process, its PID and PPID, the current time and date, the output of the random number generator given your seed, the seed itself, the state of network connections, and perhaps a directory listing of the current directory. The output of the function will be a string of bits that an attacker cannot likely duplicate, but that is likely to meet all the other conditions of randomness you might desire.



The Perl program in Example 16-1 is an example of such a program. It uses several aspects of system state, network status, virtual memory statistics, and process state as input to MD5. These numbers change very quickly on most computers and cannot be anticipated, even by programs running as superuser on the same computer. The entropy (randomness) of these values is spread throughout the result by the hashing function of MD5, resulting in an output that should be sufficiently random for most uses.

Example 16-1. Generating a random seed string

#!/usr/bin/perl -w
#
# randbits -- Gene Spafford <spaf@purdue.edu>
# Generate a random seed string based on state of system.
#
# Inspired by a program from Bennett Todd, derived
# from original by Larry Wall
#
# Uses state of various kernel structures as random "seed"
# Mashes them together and uses MD5 to spread around
#
# Usage:  randbits [-n] [-h | -H ] [keylen]
#      In which
#         -n means to emit no trailing linefeed
#         -h means to give output in hex (default)
#         -H means hex output, but use uppercase letters
#             -s means to give output in base 64
#         keylen is the number of bytes to the random key (default is 8)

# If you run this on a different kind of system, you should adjust the
# setting in the "noise" string to system-specific strings. 
# Do it as another case in the "if...else" and email me the 
# modification so I can keep a merged copy. (Hint: check in your manual
# for any programs with "stat" in the name or description.) 
#
# You will need to install the Digest::MD5 module from CPAN if 
# it is not already present.

use Digest::MD5;
use Getopt::Std;

# Augment the path to something that should contain all needed commands.

$ENV{'PATH'} .= "/bin:/usr/bin:/usr/etc:/usr/ucb:/etc:";

# We start with the observation that most machines have either a BSD-ish
# core command set, or a System V-ish command set. We'll build from those.

$BSD = "ps -agxlww ; netstat -s ; vmstat -s ;";
$SYSV = "ps -eflj ; netstat -s ; nfsstat -nr ;";


if ( -e "/sdmach" ) {
    $_ = "NeXT";
} elsif ( -x "/usr/bin/uname" || -x "/bin/uname") {
    $_ = `uname -sr`;
} elsif ( -x "/etc/version" ) {
    $_ = `/etc/version`;
} else {
    die "How do I tell what OS this is?";
}

/^AIX /       &&  (   $noise = $BSD . 'pstat -fs')   ||
/^CYGWIN/     &&  (   $noise = "ps -alW ; netstat -a ; netstat -s")  ||
/^Darwin/     &&  (   $noise = "ps -agxlww ; netstat -s ; pstat -fsvt")  ||
/^FreeBSD/    &&  (   $noise = $BSD . 'vmstat -i')   ||
/^HP-UX 7/    &&  (   $noise = $SYSV)   ||
/^HP-UX A.09/ &&  (   $noise = $SYSV . "vmstat -s")  ||
/^IRIX(64)? [56]/   &&  (   $noise = $SYSV)   ||
/^Linux/      &&  (   $noise = "ps -agxlww ; netstat -i ; 
                                       netstat -s; vmstat")    ||
/^NeXT/       &&  (   $noise = 'ps agxlww; netstat -s; vm_stat')  ||
/^OSF1/       &&  (   $noise = $SYSV . 'vmstat -i')    ||
/^SunOS 4/    &&  (   $noise = $BSD . 'pstat -afipSsT;vmstat -i')   ||
/^SunOS 5/    &&  (   $noise = $SYSV . 'vmstat -i;vmstat -s; nfsstat')   ||
/^ULTRIX 4/   &&  (   $noise = $BSD . 'vmstat -s')   ||
    die "No 'noise' commands defined for this OS.  Edit and retry!";


 #### End of things you may need to modify

($prog = $0) =~ s|.*/||;

$usage = "usage: $prog [-n] [-h | -H | -s] [keylength]\n";
getopt('nhHs', \%opts) || die $usage;

defined($keylen = shift) || ($keylen = 8);
die $usage if ($keylen =~ /\D/);
die $usage if (($opts{s} and $opts{h} || $opts{H}) or 
               ($opts{h} && $opts{H}));

die "Maximum keylength is 16 bytes (32 hex digits)\n" if ($keylen > 16);

# Run the noise command and include whatever other state we
# can conveniently (portably) find.

$hash = Digest::MD5->new;

$noise .= ";ls -lai . /tmp";
-d "/dev" and $noise .= " /dev";
open(NOISE, "$noise |") || die("Couldn't run noise commands: $!");
$hash->add(<NOISE>);
close(NOISE);

$hash->add(times(), $$, getppid(), time, join('+', %ENV));

# Format the output and finish.

$buf = $opts{s} ? $hash->b64digest : $hash->hexdigest;

($buf =~ y/a-f/A-F/) if $opts{H};
print substr($buf, 0, 2*$keylen);
print "\n" unless $opts{n};

Note that the techniques used in this script are similar to the approaches used by some Unix systems to implement /dev/random; they are also similar to the techniques used by EGD. As these functions are not present on all systems, we have decided to include this script here. (It is also educational to see how such a script is written.)

This script is also an excellent method for generating Xauthority keys if you need them. Simply execute it with an argument of 14 (you need 28 hex characters of key) and use the result as your key.

/dev/random and /dev/urandom

Some versions of Unix have integrated kernel random number sources available through the device file abstractions of /dev/random and /dev/urandom. When present, these devices combine a cryptographically secure random number generator using non-deterministic sources of bits with seed information from many random sources, such as network interrupts, user input, and other external events.

/dev/random generally returns random bytes until it exhausts the available noise in its entropy pool, and then blocks until more entropy has been gathered. It is thus suitable for cryptographic applications and one-time pads, but the time required to generate a given number of random bytes may not be predictable. For security applications, this is generally the best source of random numbers available in the operating system without attaching special hardware.

/dev/urandom returns as many bytes as requested; when it has exhausted the available noise, the bytes it returns are only pseudorandom. It never blocks, and thus has predictable time requirements, but may not be suitable for cryptographic use.

Systems that don't have /dev/random can try the Entropy Gathering Daemon (http://egd.sourceforge.net), a user-space daemon that performs a similar function.


Footnotes

[20] This functionality can be accessed from a shell script using the program /usr/lib/makekey or /usr/libexec/makekey if you have it.

[21] Perhaps you've noticed the chicken and egg problem here. The best seed for a pseudorandom number generator is a random value. But if you can reliably produce truly random values, why do you need a pseudo-random number generator?

[22] John Markoff, "Security Flaw Is Discovered in Software Used in Shopping," The New York Times, September 19, 1995, p. 1.

[23] Precursor to the curent CERIAS center.


Return to ONLamp.com.





Sponsored by: