Subject: Key Generation Security Flaw in PGP 5.0

From: Don Davis <[email-masked]>
Date: Wed, 24 May 2000 12:14:36 -0400

> So the intervals between individual key presses remain as a source
> of randomness.
> Assuming that the user types at a rate of about 120 characters per
> minute, we have an interval of approximately 0.5 seconds between two
> key presses. Dropping the upmost non-random bit of the interval
> length, we get about 18 bits of random timing information per key
> press.

i'm sorry, but i think your estimate here is badly
flawed. you seem to assume that keyboard-timings
come in microsecond-scale resolutions.  it turns
out, though, that keyboard controllers check the
keyboard for input only every few milliseconds
(10 msec, if i remember correctly).  thus, your
keyboard-timings come in hundredth-sec increments,
and you get at most 6 or 7 bits of variability per
keystroke.  further. these timings are not uniformly
distributed, but probably show a normal distribution
centered at, say, 500 msec.  my guess is you're
getting only 3 or 4 bits of entropy per keystroke,
at most. i can calculate the entropy more precisely,
if you want.

> This estimate gets worse for experienced and
> fast-typing users.

much worse, because their keystroke timings will
be highly correlated with the textual content.
english text carries only around 1 bit of entropy
per character.

i congratulate you upon your discovery, and i thank
you for your diligence.  fwiw, i'm the author of a
paper about extracting randomness from disk timings,
which appeared at crypto '94, and which is cited in
rfc 1750 "recommendations for randomness."

				- don davis
				  http://world.std.com/~dtd

-