Linux RNG paper

[William Allen Simpson]

Had a bit of time waiting for a file to download, and just read the paper
that's been sitting on my desktop.  The analysis of the weakness is new,
but sadly many of the problems werre already known, and several previously
discussed on this list!

The forward secrecy problem was identified circa 1995 by Phil Karn, who
therefore saved the changed state after generating each random key --
something similar to the paper's suggestion.

The lack of jitter in millisecond event time was also identified by Karn,
and he developed i386 code to determine microseconds from processor timing.
Sorry, I cannot remember whether it only worked on 386 and above, or also
186/286 we were using in cell phones at the time.  But I certainly used
it in a number of routers over the years....

We also noticed the event jitter was more important for unpredictability
than the actual event values, and all my code just added the value to the
microsecond time.  The code was fast enough to handle very rapid interrupt
time events by leaving complex functions for later.  This assumes a
cryptographically strong output function will sufficiently hash the bits
that calculating and saving the jitter itself is a waste of effort.

We also always used any network checksum that came across the transom,
including packets, IP, UDP, and TCP.  Yes, it is externally visible, but
the microsecond time is not, and adding them makes the actual pool values
less predictable (although within a constrained range).

Also, rather than deciding the pool was "full" of entropy, we just kept
XOR'ing the new values with the old, as a circular buffer (again similar
to the paper's suggestion).

Finally, a lot of this was discussed in public, and both Karn's and my
code variants were publicly available.  I don't have my old email
backups online, but I'm sure it was discussed at places such as the
tcp-group and ipsec circa 1995.

After the first Yarrow draft, it was discussed on the old linux-ipsec list
circa 1999 April 22, and on this list circa 1999 August 17.

After much discussion, Theodore Y. Ts'o wrote
(<199908160346.XAA09070 at tsx-prime.MIT.EDU>):
 >    Date: Sun, 15 Aug 1999 10:00:01 -0400
 >    From: William Allen Simpson <wsimpson at greendragon.com>
 >    Catching up, and after talking with John Kelsey and Sandy Harris at
 >    SAC'99, it seems clear that there is some consensus on these lists that
 >    the semantics of /dev/urandom need improvement, and that some principles
 >    of Yarrow should be incorporated.  I think that most posters can be
 >    satisfied by making the functionality of /dev/random and /dev/urandom
 >    more orthogonal.
 >
 > Bill, you're not the IETF working group chairman on /dev/random, and
 > /dev/random isn't a working group subject to consensus.  I'm the author,
 > with the sole responsibility to make decisions about what's best for the
 > device driver.  Of course, if someone else wants to make an alternative
 > /dev/random driver, they're free to use it in their system.  They can
 > even petition Linus Torvalds to replace theirs with mine, although I
 > doubt they'd get very far.
 >
Unfortunately, the fact that Linux remains vulnerable to the iterative
guessing attack was really due to Ted's intransigence, and some personal
relationship that he enjoys with Linus.

Thank you for the independent analysis once again bringing this topic to
everybody's attention.  Hard to believe that another 7 years have passed.

-- 
William Allen Simpson
     Key fingerprint =  17 40 5E 67 15 6F 31 26  DD 0D B9 9B 6A 15 2C 32

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com