<<< Date Index >>>     <<< Thread Index >>>

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.