Re: /dev/random on Linux
From: Kyle Moffett
Date: Tue May 16 2006 - 04:15:09 EST
On May 15, 2006, at 22:50, Muli Ben-Yehuda wrote:
On Mon, May 15, 2006 at 11:41:07PM +0100, Alan Cox wrote:
A paper by people who can't work out how to mail linux-kernel or
vendor-sec, or follow "REPORTING-BUGS" in the source,
Zvi did contact Matt Mackall, the current /dev/random maintainer,
and was very keen on discussing the paper with him. I don't think
he got any response.
So he's demanding that one person spend time responding to his
paper? The "maintainer" for any given piece of the kernel is the
entry in MAINTAINERS *and* linux-kernel@xxxxxxxxxxxxxxx *and* the
appropriate sub-mailing-list. If you want a quick response, it's
typically correct to CC all 2 or 3, although that certainly doesn't
guarantee one if people find your emails rude or unhelpful.
I know there have been patches around for ages to improve the
entropy of the random number generator, but how active is work on
this section of the code?
Going through the claims
I would dismiss 2.2 for the cases of things like Knoppix because
CDs introduce significant randomness because each time you boot
the CD is subtly differently positioned. The OpenWRT case seems
more credible. The hard disk patching one is basically irrelevant,
at that point you already own the box and its game over since you
can just do a virtualization attack or patch the OS to record
anything you want.
Any system with a cycle counter has a vast amount of entropy
available by the time the system even gets through the BIOS. Various
things like memory timing, power initialization, BIOS tests, etc are
all sufficiently variable in terms of CPU clock cycles that the value
of the cycle counter at the first bootloader instruction executed has
several bits of randomness. By the time the bootloader has
optionally waited for user input and loaded the kernel off the disk,
chaotic variability in the disk access for HDDs, CDROMs, etc will
make many bits of the cycle counter sufficiently random. At that
point there's a decently random seed, especially once you start
getting further-randomized cycle-counter-based disk interrupts. I
believe there was a paper that discussed how air turbulence in a disk
drive was sufficient on a several hundered MHz CPU to provide lots of
entropy per interrupt from the cycle counter alone.
This is totally untrue for an embedded flash-based system; but for
such a system the only way to get any kind of entropy at all is with
a hardware RNG anyways, so I don't really see this as being a problem.
I was unsure about the purported forward-security-breakage claims
because I don't know how to validate those, but I seem to recall
(from personal knowledge and the paper) that the kernel does an SHA1
hash of the contents of the pool and the current cycle-counter when
reading, uses that as input for the next pool state and returns it
as /dev/random output. Since the exact cycle-counter value is never
exposed outside the kernel and only a small window of the previous
pool state is exposed, I don't see how you could compute an SHA1
preimage that would reveal a significant portion of the previous
pool's state, especially given that the best known attack against
SHA1 is an extremely hard first-preimage attack which only gets a
single possible preimage, not the set of all possible preimages as
required to break the kernel algorithm.
2.3 Collecting Entropy
Appears to misdescribe the behaviour of get_random_bytes. The
authors description is incorrect. The case where cycle times are
not available is processors lacking TSC support (pre pentium).
This is of course more relevant for some embedded platforms which
do lack cycle times and thus show the behaviour described. There
are some platforms that therefore show the properties they are
commenting on so it is still a relevant discussion in those cases.
Agreed. I talked to this some above.
3.4 Security Engineering
The denial of service when no true entropy exists is intentional
and long discussed. User consumption of entropy can be controlled
by conventional file permissions, acls and SELinux already, or by
a policy daemon or combinations thereof. It is clearly better to
refuse to give out entropy to people than to give false entropy.
Agreed. If you really want to secure random-number-generation from
userspace, make a userspace daemon that opens a /dev/user_random
socket and uses a private root-only /dev/random device. Then
implement user quotas and such on the socket; requiring credential-
passing or whatever other security mechanism you require. Then you
can even have the daemon read from /dev/hwrng and from user data
sources and verify the randomness of the input data before sending it
to the kernel. None of that is the kernel's business and could be
more securely and efficiently done in userspace.
Likewise the talk in the paper about shipping a daemon with the
kernel is bogus; people will use whatever daemons they want to. If
it really matters for your system and the kernel doesn't provide a
good enough interrupt-based RNG, then you should use one of the many
available RNG daemons (or write your own) based on your exact
Somone asked me why I work on this free (http://www.fsf.org/
philosophy/) software stuff and not get a real job. Charles Schulz
had the best answer:
"Why do musicians compose symphonies and poets write poems? They do
it because life wouldn't have any meaning for them if they didn't.
That's why I draw cartoons. It's my life."
-- Charles Schulz
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/