Date: Sat, 07 Aug 1999 22:44:35 -0500
From: John Kelsey <[EMAIL PROTECTED]>
Now, I haven't looked closely at the design of /dev/random,
so I may be missing something. Is there something that
would protect it from this class of attack, if it were
overestimating the entropy collected by a, say, a factor of
two or three?
So if I understand your reasoning, your attack posits that you start at
the very beginning, where the pool has only (say) 50 bits of entropy,
but the pool *thinks* it has a few hundred bits of entropy. Basically,
the idea is you assume the pool's starting state, and can try all 2**50
possible inputs that might have been mixed into the pool, and try to
match it with the output to /dev/random, right?
One of the things which makes this difficult is that as soon as the
machine boots, every single disk access will be result in timing access
data which gets mixed into the pool. The timing is done using the
pentium cycle clock, so we get a fairly high resolution timing, which
will be affected by the pattern of disk access, the layout of files
accessed by the boot scripts on the disk, chaotic air turbulence in the
drive (which is admittedly very small), delay caused by interrupts being
blocked by the kernel, etc. So having the outside attacker model the
system is actually fairly difficult, and I believe would require
detailed knowledge of the configuration, setup, and filesystem layout of
the system.
Next, one of the other hurdles an attacker has to surmount is the
mixing of data from a previous boot. During the shutdown process, the
/etc/rc.d scripts ask /dev/urandom to generate a block of random data
equal to the size of the entropy pool, and this is stored in a file
readable only by root, typically /var/run/random-seed.
During the boot sequence, the contents of that file is mixed into the
entropy pool. *However*, the entropy count is not credited in this
operation. This is merely done to try to deny attackers a stable
starting point to begin the attack, assuming they can't gain physical
access to the machine and read the random-seed file before the machine
boots. Of course, immediately after that file is mixed into the entropy
pool, the file is cleared out by asking the /dev/urandom device to
generate a block of random data which is used to over-write the file.
(This also guarantees that the system won't start with the same random
seed file even if the system crashes without executing its shutdown
scripts.)
The random-seed file doesn't protect you from the very first time that
you boot the machine, but usually the first time when you boot the
machine is when you're installing the beast, and so usually there's at
least some (if not quite a bit) keyboard activity during the initial
system setup phase which typically happens before any services become
available that might leak the outputs of /dev/random.
And of course, the time at which /dev/random is read from is also mixed
into the pool (altough again no entropy is credited to this operation).
It does mean that the attacker has to not only gain access to the output
of /dev/random, but also no exactly when the reads on /dev/random
happened, down to the pentium clock cycle, in order to be able to carry
out the interative guessing attack forward.
I'll also note that in order for the interative guessing attack to work,
the attacker has to be able to see sufficient numbers of the output of
/dev/random to know that he/she is on track. This is one of the reasons
why I didn't recommend that IPSEC cookie generation be done using
/dev/random; first of all, it doesn't need that level of security in
terms of random generation, and secondly it is sent in the clear. If
you use /dev/random just to generate session keys, or to rekey secondary
PRNG, then the attacker never gets to see anything direct from the
output of /dev/random.
It looks to me like /dev/random, and the PGP and Cryptlib
PRNGs are all kind-of built on the assumption that there
will probably be enough entropy to generate all the output
bits we need (and we'll be able to tell if there is that
much or not), and if not, these PRNGs are designed to
hopefully give good pseudorandom outputs.
That's fair. Because of the position of /dev/random in the kernel, it
is in the position to grab a large quantity of timing data which will
contain at least *some* entropy. It's such that the pool fills
relatively quickly, and certainly once the pool is full, any
overestimation of the entropy count becomes corrected, since the entropy
estimate is capped by the size of the pool, but new values harvested
from the system continue to get mixed into the pool. So yes, part of
the design assumption is that /dev/random that it gets a very large
number of events whose timings can be measured and distilled for
entropy.
- Ted
