Subject: Re: Sources of randomness (RSAREF random generator flaw)

From: [email-masked] (Paul C. Kocher)
Date: Tue, 28 Nov 1995 11:37:39 GMT

David Gentzel <[email-masked]> wrote:
>I am in the process of improving the random number generation for secure
>key exchange in a client-server product.  After the fiasco with NetScape,
>the powers that be wish to ensure that they are not subject to the same
>predictability.
>
>The current scheme is not bad, and I have implemented some improvements,
>but am looking for "better" sources of randomness.  Here are the parameters:
>
>    o	The operating system is Windows NT 3.51 for Intel.
>    o	There is no hardware "true" random number generator available.
>    o	There is no source of UI noise (the server could sit for weeks
>	with no mouse or keyboard activity).

I've dealt with this sort problem several times in the past, and
generally prefer a solution that covers as many bases as possible.

The first (and most important) thing to do is make sure you use 
a good secure random number generator, preferably based on SHA 
and/or MD5.  (If you're worried about possible failures in one 
hash function, you can make two random number generators and XOR 
the results.)

To seed the generator, you should always include the hash of the
seed from last time.  For additional "freshess", you need to get
some information from the hardware.  For timing information you
can try reading the high-resolution timer (input port 64 decimal; 
read twice to get the full 16 bit value), though I don't know if
you'll be able to access this under NT.  Network packet arrival
times and hard disk latency are also useful.

Once you've got the random number generated seeded properly, in
theory you don't really need any more seed information (though
additional seeding never hurts).  If you have some user input
during start-up, that may well be enough.  (With event-driven
operating systems, a simple and effective way to feed the user 
input into the hash function is to just use all operating system 
messages, which including mouse movement commands).

WARNING: RSAREF has a bug where seeding with A then with B
is the same as seeding with B then A.  For example, a program
that seeded with a large number of random 0s and 1s would be
trivial to break.

Cheers,
Paul Kocher

__________________________________________________________________________
Paul C. Kocher           Independent cryptography/data security consultant
E-mail: [email-masked]          Voicemail: 415-354-8004, FAX: 415-321-1483