NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/crypt/7065

Internet Message Format | 1993-01-21 | 3.6 KB

Path: sparky!uunet!elroy.jpl.nasa.gov!sdd.hp.com!hp-cv!ogicse!verdix!islabs!fasttech!zeke
From: [e-mail] (Bohdan Tashchuk)
Newsgroups: sci.crypt
Subject: Re: Getting random numbers from timing events?
Message-ID: <[e-mail]>
Date: 21 Jan 93 09:45:10 GMT
Article-I.D.: fasttech.1993Jan21.094510.2963
References: <[e-mail]> <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Fast Technology   Beaverton, OR
Lines: 62

In <[e-mail]> [e-mail] (James Gustave) writes:

>  I need a source for truly random numbers for an encryption program I'm
>working on.  I was thinking of using PGP's approach and time keyboard input
>with a fast timer, then use the low-order 8-bits as a random number.  I'm
>working on a Mac, so I'd like to use key and mouse events.  How can I tell
>if the numbers I'm getting are good enough to be considered cryptographically
>random?

When I wanted some random hex digits I wrote myself a similar little program
that ran under dos. It's a little easier for me to understand than pgp's,
because it doesn't have so many #ifdefs (ie, not as portable). Fortunately
TurboC has calls that allow a spin variable to be incremented between key
presses. Here is the inner loop:

    for (;;) {
        for (spins = 0; bioskey(1) == 0; spins++)
        ;
        if (spins > 10000)
        printf("%X %c", (spins & 0xf), (count++ % 16) ? ' ' : '\n');
        else
        printf("\a");
        bioskey(0);
    }

This code tests for > 10000 spins of the wait loop. If the key is pressed
before then, the digit is invalid. Someone more pedantic than I will
probably be concerned about the inherent bias, since I use the low 4 bits
of the number of spins, and 10000 isn't divided evenly by 16.

The important thing to me is that value of 10000. On my machine it works out
to about 1 second of real time per random digit. I don't know how much lower
this value could go before I was uncomfortable with the non-randomness.
I'd be worried with values less than about 1000. I haven't studied pgp
carefully enough to figure out the threshold below which it discards values
with the similar method it uses.

But the real reason I'm writing this is to basically agree with you about
the mouse and key events. You should hook in some sort of similar routine
in your Mac, and discard input events that occur too close together. The
result should be quite random. You need to make sure that Multifinder
and init's don't switch away control at inappropriate times and somehow
bias this method.

Since I read netnews so much each day, the ideal for me would be to hack
something like this into nn. Each time I hit a key I generate a few more
random bits.

I too would like to hear comments about this. Specifically, given a method
like this, how long of a delay is "long enough" for very good randomness?
I realize there are specific tests that can be run on the resulting numbers,
but I'd like to hear people's intuition about it.

Another idea would be to take all the Usenet traffic that comes into my
machine and continuously xor it into a file that's about 1 MB in size.
Things would be pretty random after a few weeks of news. You would need
to correct for various biases. For example, almost all traffic is ascii,
so that means that hi bits won't be set and control characters will be
pretty much non-existent. But the end result should still be pretty
darned random. The purists won't like this method since it should
theoretically be possible for someone monitoring my uucp line to figure
out the result file.