From: Hal <74076.1041@CompuServe.COM>
Date: Sun, 9 May 93 11:47:17 PDT
To: CYPHERPUNKS <CYPHERPUNKS@toad.com>
Subject: Random TSR
Message-ID: <930509183959_74076.1041_FHD48-1@CompuServe.COM>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

We had some discussion on the list a few months ago about hardware
RNG's.  As I recall, there were problems feared with the Zener diode noise
generators involving coupling to other EM signals that might add regularity
to the noise.

Hardware random numbers are useful, not so much to fill one time pads,
with their attendant problems with distribution, but rather as session
key generators for Diffie-Hellman key exchange or RSA-type public key
programs.  This is one of the weak points of PGP, in my opinion; it times
keystrokes when you first generate your public key, but then from then
on it just uses and re-uses those same random numbers.  (It does mix
in the time of day for each message sent, but as pointed out on the
PGP developers' list, this may not add that much randomness.)

Each time you send a message, it has to generate a random session key,
which it uses to encrypt your message, sending this random key RSA-
encrypted at the head of your message.  How random are these session keys?
PGP is still re-using the same random information I supplied many months
ago.  There is no KNOWN way to exploit this lack of randomness but it is
still worrisome.

Perry Metzger mentioned that he deletes his randseed.bin file every night.
This causes PGP to ask him for new keystroke timings every morning when
he first runs it.  This adds a new daily dose of randomness to the program
but it is kind of a pain to do.

This is where a hardware RNG would be really useful.  Use it to generate
your session keys and you don't have to worry too much about someone
breaking your message by intelligent key guessing.

RIPEM goes to greater lengths than PGP in trying to find good random
bits.  It has options to scan your filesystem or to use network information,
both of which are presumed to be randomly changing.  These approaches are
more suitable for a multi-user workstation than for a regular PC, though.

I had an idea for the PC environment which I don't think I've seen before.
(Apologies if I'm regurgitating someone else's idea.)

Have a TSR which just extracted random information from your use of the
PC.  Do keystroke timing all the time, check disk block contents and
locations.  Record this information and periodically pass it through MD5
then store it in a file.  This file would basically hold entropy extracted
from how you use your PC.  PGP could then read this file (you could even
have the file be PC's randseed.bin, making it compatible with current
versions of PGP) to get its random bits for session keys.

This does not sound like it would be that hard, although the few attempts
I have made to write TSR programs which hooked into DOS calls have not
been terribly robust.  One technical issue is how much randomness or
entropy exists in each event.  This has been discussed in some detail on
the PGP developers' list, but a simple solution would be to just ignore
that problem and constantly merge in your new random bits with those in
the file.  Once you've gotten enough "true" randomness your file will be
fully random.  You won't know when that's happened but if your file isn't too
big and you use the computer quite a bit it will hopefully be fast enough.

Or, if you wanted to be more ambitious, I gather from the discussion on
pgp-dev that you could collect statistics on the intervals between key-
strokes and use these to estimate the amount of random information per
keystroke.  Then you could have a call to the TSR to tell how much random
information is available in the file.

This program could be constantly running in the background, unobtrusively,
collecting and distilling the randomness you are discarding all the time.
Randomness is precious; it's time to stop wasting these bits!

Hal Finney
74076.1041@compuserve.com

-----BEGIN PGP SIGNATURE-----
Version: 2.2

iQCVAgUBK+0lWqgTA69YIUw3AQGPbQP/TUSbeusbaPQ3DF6wpr+tY5H8IcVTzJUb
p78E+IZHx8pMSQP/fu8SnBGWuINnurq9fssJT9o7DQJnXBmcEgK+48OHbunHi9OV
VrheN8tXHTY5OBd4pvKV9nh200+OalRny5lL4ZviMqGl+iYVJEU5PdZIPnPeRAzV
AaZ2gvVBdbE=
=gww0
-----END PGP SIGNATURE-----