Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:16 ADT
Bill Frantz (frantz@netcom.com)
Sat, 11 Jul 1998 16:22:16 -0800
To toss my had into the current discussion of randomness, and to get a
public vetting, let me describe a recent secure random generator I
implemented.
Assumptions and ground rules:
(1) If we can get 160 bits of entropy, and keep it secret, we can maintain
security on the DSA and DES keys we generate for the life of the
application (20 years).
(2) Since we probably can't keep a secret for 20 years, we continuously
stir new entropy into the generator.
(3) We don't pretend to protect against hacked computers (e.g. keyboard
sniffers).
(4) We want to maintain perfect forward security on the DES keys we
generate (thru Diffie-Hellman exchange), even if the computer system is
later penetrated.
(5) We aren't permitted to bother the user. I.e. no, "wave the mouse
around while we gather entropy."
(6) We assume that mixing bad entropy with good entropy results in good
entropy.
Basic entropy mixing logic:
When the application starts up, it loads entropy from disk. When it shuts
down, it saves entropy on disk. To provide for perfect forward security,
saving the entropy uses the same, getRandom() call that other uses use (see
below). The entropy can be encrypted on disk as an user option.
Entropy is mixed using MD5. (The collision weakness reported should not
effect its use as a mixing function.) The entropy pool consists of an
array of 16 MD5 hashes. Each time new entropy is added to the pool, we
replace the next hash (in a circular manner) with MD5(entire pool || new
entropy || current value of the CPU cycle counter).
On initial startup we do not return entropy until we have accumulated 160
bits (see below).
When we generate a random number, we compute enough MD5(entire pool || 8
byte sequence counter) to meet fill the requested size. The 8 byte
sequence counter is incremented for each new calculation. Preparing to
save entropy on disk withdraws 256 bytes of entropy using this logic.
We currently use two sources of entropy:
(1) UI events, mouse and keyboard. Every UI event is hashed into the pool.
If the mouse has moved on at least one axis since the last event, we score
1 bit of entropy (no motion scores zero bits). If the key pressed is
different that the last 4 key presses, we score 1 bit of entropy. During
the startup phase, we continuously monitor mouse position. After we have
160 bits, we only measure mouse position on mouse down and mouse up events.
(2) Timer jitter. Experiments show that raw data which comes from using
the calender clock in the Intel PC vs. the CPU cycle counter passes
FIPS-140. We gather the data as follows (in Java):
long start = System.currentTimeMillis();
while (start == System.currentTimeMillis()); //Loop till clock ticks
use (current time || CPU cycle counter) to update the pool and score 1 bit
of entropy.
The clock ticks approximately once every 1/20 of a second. We reduce the
CPU load by sleeping for most of that 1/20 of a second and only starting
the loop when we think the clock will tick soon.
-------------------------------------------------------------------------
Bill Frantz | If hate must be my prison | Periwinkle -- Consulting
(408)356-8506 | lock, then love must be | 16345 Englewood Ave.
frantz@netcom.com | the key. - Phil Ochs | Los Gatos, CA 95032, USA
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:16 ADT