Bugtraq mailing list archives
/dev/random is probably not
From: "Charles M. Hannum" <mycroft () netbsd org>
Date: Fri, 1 Jul 2005 17:10:35 +0000
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. 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.
Current thread:
- /dev/random is probably not Charles M. Hannum (Jul 01)
- Re: /dev/random is probably not Thomas Wana (Jul 02)
- Re: /dev/random is probably not McLain Causey (Jul 04)
- Re: /dev/random is probably not Chiaki (Jul 02)
- Re: /dev/random is probably not exon (Jul 04)
- Re: /dev/random is probably not Darren Reed (Jul 05)
- Re: /dev/random is probably not devnull (Jul 06)
- Re: /dev/random is probably not Thomas (Jul 06)
- Re: /dev/random is probably not Darren Reed (Jul 06)
- Re: /dev/random is probably not Thomas (Jul 06)
- Re: /dev/random is probably not Kai Howells (Jul 08)
- Re: /dev/random is probably not exon (Jul 04)
- Re: /dev/random is probably not Thomas Wana (Jul 02)