Re: /dev/random is probably not
Charles M. Hannum wrote:
Most implementations of /dev/random (or so-called "entropy gathering daemons")
rely on disk I/O timings as a primary source of randomness. This is based on
a CRYPTO '94 paper[1] that analyzed randomness from air turbulence inside the
drive case.
At least on Linux, the entropy pool is not only filled with data
from I/O timings, but also from networking I/O, user input events,
etc etc.[1]
Which specific implementations do you mean with "most implementations"?
Tom
[1] man 4 random
I was recently introduced to Don Davis and, being the sort of person who
rethinks everything, I began to question the correctness of this methodology.
While I have found no fault with the original analysis (and have not actually
considered it much), I have found three major problems with the way it is
implemented in current systems. I have not written exploits for these
problems, but I believe it is readily apparent that such exploits could be
written.
a) Most modern IDE drives, at least, ship with write-behind caching enabled.
This means that a typical write returns a successful status after the data is
written into the drive's buffer, before the drive even begins the process of
writing the data to the medium. Therefore, if we do not overflow the buffer
and get stuck waiting for previous data to be flushed, the timing will not
include any air turbulence whatsoever, and should have nearly constant time.
b) At least one implementation uses *all* "disk" type devices -- including
flash devices, which we expect to have nearly constant time -- for timing.
This is obviously a bogus source of entropy.
c) Even if we turned off write-behind caching, and so our timings did include
air turbulence, consider how a typical application is written. It waits for,
say, a read() to complete and then immediately does something else. By
timing how long this higher-level operation (read(), or possibly even a
remote request via HTTP, SMTP, etc.) takes, we can apply an adjustment factor
and determine with a reasonable probability how long the actual disk I/O
took.
Using any of these strategies, it is possible for us to know the input data to
the RNG -- either by measurement or by stuffing -- and, therefore, quite
possibly determine the future output of the RNG.
Have a nice holiday weekend.
[1] D. Davis, R. Ihaka, P.R. Fenstermacher, "Cryptographic Randomness from Air
Turbulence in Disk Drives", in Advances in Cryptology -- CRYPTO '94
Conference Proceedings, edited by Yvo G. Desmedt, pp.114--120. Lecture Notes
in Computer Science #839. Heidelberg: Springer-Verlag, 1994.