Appropriate sources of entropy

A steady stream of random events allows the kernel to keep its entropy pool stocked up, which in turn allows processes to use the strongest random numbers that Linux can provide. Exactly which events qualify as random—and just how much randomness they provide—is sometimes difficult to decide. A recent move to eliminate a source of contributions to the entropy pool has worried some, especially in the embedded community.

The kernel samples unpredictable events for use in generating random numbers, storing that data in the entropy pool. Entropy is a measure of the unpredictability or randomness of a data set, so the kernel estimates the amount of entropy each of those events contributes to the pool. Many kernels run on hardware that is lacking some of the traditional sources of entropy. In those cases, the timing of interrupts from network devices has been used as a source of entropy, but it has always been controversial, so it was recently proposed for removal.

Two of the best sources of random data for the entropy pool—user interaction via a keyboard or mouse and disk interrupts—are often not present in embedded devices. In addition, some disk interfaces, notably ATA, do not add entropy, which extends the problem to many "headless" servers. But network interrupts are seen as a dubious source of entropy because they may be able to be observed, or manipulated, by an attacker. In addition, as network traffic rises, many network drivers turn off receive interrupts from the hardware, allowing the kernel to poll periodically for incoming packets. This would reduce entropy collection just at the time when it might be needed for encrypting the traffic.

This is not the first time eliminating the IRQF_SAMPLE_RANDOM flag from network drivers has come up; we looked at the issue two years ago (though the flag was called SA_SAMPLE_RANDOM at that time). It has come up again, starting with a query on linux-kernel from Chris Peterson: "Should network devices be allowed to contribute entropy to /dev/random?" Jeff Garzik, kernel network device driver maintainer, answered: "I tend to push people to /not/ add IRQF_SAMPLE_RANDOM to new drivers, but I'm not interested in going on a pogrom with existing code."

For anyone that is interested in such a pogrom, Peterson proposed a patch to eliminate the flag from the twelve network drivers that still use it. This sparked a long discussion on how to provide entropy for those devices that do not have anything else to use. While the actual contribution of entropy from network devices is questionable, mixing that data into the pool does not harm it, as long as no entropy credit—the current estimate of entropy in the pool—is awarded. Alan Cox proposed a new flag to track sources like that:

Some were in favor of an approach like this, but Adrian Bunk notes that:

Part of the problem stems from a misconception about random numbers gotten from /dev/random versus those that are read from /dev/urandom, which we described in a Security page article last December. In general, applications should read from /dev/urandom. Only the most sensitive uses of random numbers—keys for GPG for example—need the entropy guarantee that /dev/random provides. In a system that is getting regular entropy updates, the quality of the random numbers from both sources is the same.

There is still an initialization problem for some systems, though, as Ted Ts'o points out:

A potential entropy source, even for embedded systems, is to sample other kernel and system parameters that are not predictable externally. Garzik suggests:

Another source is from hardware random number generators. The kernel already has support for some, including the VIA Padlock that seems to be well thought of. Not all processors have such support, however. The Trusted Platform Module (TPM) does have random number generation and is becoming more widespread, especially in laptops, but there is no kernel hw_random driver for TPM.

Garzik advocates adding a kernel driver for what he calls the "Treacherous Platform Module", but as others pointed out, it can all be done in user space using the TrouSerS library. Even for the hardware random number generators that are supported in the kernel there is no automatic entropy collection, as it is left up to user space to decide whether to do that. This is done to try and keep policy decisions about the quality of the random data out of kernel code.

Systems that wish to sample that data should use rngd to feed the kernel entropy pool. rngd will apply FIPS 140-2 tests to verify the randomness of the data before passing it to the kernel. Andi Kleen is not in favor of that approach:

There is concern that some of the hardware random number generators are poorly implemented or could malfunction, so it would be dangerous to automatically add that data into the pool. Doing the FIPS testing in the kernel is not an option, leaving it up to user space applications to make the decision. There is nothing stopping any superuser process from adding bits to the entropy pool—no matter how weak—but the consensus is that the kernel itself must use sources it knows it can trust.

Another instance of this problem—in a different guise—appears in a discussion about random numbers for virtualized I/O, with Garzik asking: "Has anyone yet written a "hw" RNG module for virt, that reads the host's random number pool?" Rusty Russell responded with a patch for a virtio "hardware" random number generator as well as one that adds it into his lguest hypervisor. The lguest patch reads data from the host's /dev/urandom, which is not where H. Peter Anvin thinks it should come from:

The virtio implementation only provides the hw_random implementation, thus it requires user space help to get entropy data into the kernel. Much like any process that can read /dev/random, lguest could exhaust the host entropy pool, so there was some discussion of limiting how much random data guests can request from the device. A guest implementation could then use a small pool of entropy read from the host to seed its own random number generator for the simulated hardware device.

Removing the last remaining uses of IRQF_SAMPLE_RANDOM in network drivers seems likely, though some way to mix that data into the entropy pool without giving it any credit is still a possibility. With luck, that will encourage more effort into incorporating new sources of entropy using tools like EGD or, for systems that have it available, random number hardware. For systems that lack the traditional entropy sources, this should lead to a better initialized and fuller pool, while eliminating a potential attack by way of network packet manipulation.

> Removing the last remaining uses of IRQF_SAMPLE_RANDOM in network drivers seems likely,
though some way to mix that data into the entropy pool without giving it any credit is still a
possibility.

Why is it just a possibility? I don't get it -- what could possibly be said against that? By
following that route, you'd make dubious data hopefully a bit less dubious, but you wouldn't
make it more dubious than it is already. So what's the downside? "All or nothing" syndrome?

> Why is it just a possibility? I don't get it -- what could possibly be said against that?

I think they mean a possibility in terms of "it's possible to write code that isn't too ugly",
rather than "possible" in the theoretical sense. Of course, the worst it can do is not
increase the entropy. To actually decrease the entropy, if would need to be correlated to some
other information in pool and cause really weird interactions (highly unlikely IMO).

The downside was just demonstrated by Debian.

Mixing good randomness with dubious randomness seems harmless right?  But what happens if the
good randomness dries up?  Will you notice?  Will you end up using dubious randomness for
something that matters?

This is not like the Debian's situation. If dubious randomness isn't accounted for as incoming
entropy bits, /dev/random would block the same way as it would be blocking without any dubious
randomness at all. As for /dev/urandom, without any external randomness /dev/urandom would be
looping inside sha1 feedback, acting as a pure PRNG. Any kind of external randomness injected
into that loop would only make its randomness better, it can't possible make it worse (due to
crypto properties of sha1 you can't forge any correlation here). Point is, when good
randomness dries up, what you're getting from /dev/urandom is a PRNG output. Any dubious
randomness mixed in could only improve this situation. So, to answer your question, you really
won't notice in both cases, but your randomness would be a bit better if you mix in some
dubious stuff there as well. In the latter case, your chances of using dubious randomness
(pure PRNG) are actually smaller.

My point is, either you care about the strength of your random numbers or you don't.

If you care, you're using /dev/random and you only mix in strong entropy.  Mixing in weak
entropy seems harmless but will mask problems that would otherwise be obvious.  The Debian
situation.

If you don't care, then you're happy with a strong, well-seeded PRNG and there's no need to
mix in dubious random data.

Is there a middle ground?  I don't see one.

Any cryptographic PRNG needs to be reseeded once in a while, and some dubious data will do
just fine for that, given that it is mixed in in a cryptographically secure way. A box with
only a network connection is a good example of that -- it does not have much real entropy
coming in. You say that in absence of any trusted entropy a crypto PRNG is never to be
reseeded. I would disagree. One of the problem is what would happen if a seed file, which
stores state across reboots, is compromised. Another acoounts for any sort of weaknesses found
in a PRNG itself. If you need more details, see Schneier's Yarrow design paper, I could only
agree with what he had to say. The point is, sticking to the one initial seeding forever is a
bad idea.

if there is no other traffic involved then you may have a point, but if there is no other
activity happening on the server other then what's initiated by the bad guy, there's nothing
interesting on the server for the bad guy to get.

if the server is doing anything else (talking to anyone else on the network, doing processing
of some kind, etc) then you start having things happen on the server that are not controlled
by the bad guy

This is something I don't quite understand. Yes, the packets might be registered at the
network card exactly N nanoseconds apart, but between the time that the packet is registered
by the card and when entropy might be added there is:

- Waiting for the PCI bus to be free to check the status of the card
- The CPU finding the code to run which may involve looking up page tables, pulling code out
which may be in any number of caches, each of which take an unpredicatable amount of time to
respond.
- The process of DMAing the data to main memory takes an unpredictable amount of time,
depending on the state of the DRAM.
- The busses are shared between various CPUs which are doing other things at the same time.
- The execution time of CPU instructions is affected by branch prediction logic and
instruction scheduling algorithms. Hyperthreading makes it worse.

And you're saying that at the end of this there's not even a single bit of entropy? If the
machine were otherwise completely idle I might understand it but if you just register lots of
dubious sources and use as entropy the time between different dubious sources I don't see how
it could be in any way predictable.

If I had any idea how to do it, I'd create a device that tried to extract entropy from the
timer interrupt and see if there is any correlation to be found...

Another source of randomness for daemons like EGD or rngd could be to periodically wget
news.google.com or random.org's numbers and pipe it into /dev/urandom.

> wget ... | xxd -r ... > /dev/random

I believe that this will mix new data into the entropy pool, but not actually increase the
entropy estimate.  In other words, any process blocking on /dev/random will remain blocked
until some other, accounted for, entropy is added.

I believe you'll need to ioctl(RNDADDENTROPY) in order to fix that.

> But isn't that what's happening all the time anyway, with the "environmental noise from
device drivers and other sources"

No.  The various sources of entropy add entropy to the random pool and increase the entropy
estimate by some small value.

You may want to see for yourself in the kernel sources -- they end up calling
add_timer_randomness (drivers/char/random.c line 571) which calls add_entropy_words and then
credit_entropy_store.  This increases the value of entropy_count, and may cause processes
blocking on /dev/random to wake up.

the sysadmin can add randomness, but the system will not trust that it is random (without
tweaking things via the ioctl), even if the sysadmin sends completely predictable data to
/dev/random it won't do any harm.

> My intuition was that /dev/random is (root) writable so that the sysadmin can incorporate
additional sources of entropy.

The distinction between mixing in new data into the random pool and adding to the entropy
estimate is what the article is about.

The in-kernel RNG maintains a pool of random data and an estimate of how much entropy is in
the pool.

When you read from /dev/(u)random, the entropy estimate is reduced.  When it reaches 0, reads
from /dev/random will block.  That's the easy part.

The difficult part is deciding when to increase the entropy estimate.  When you write 100
bytes to /dev/random, unless the 100 bytes are perfectly random, they should not add 800 bits
to the entropy estimate, but some lower value that only the person who generated the data is
able to choose reasonably.

For that reason, merely writing to /dev/random does not add to the entropy estimate; you need
to explicitly increase it by using the ioctl.

> So how is me writing bytes to /dev/random via a script any different than what my distro
(Slackware 12.0) does in rc.S (also a script) when the "carry-over" entropy file
(/etc/random-seed) is written to the random device?

It's no different.  Your distribution is mixing the old data into the random pool, but not
increasing the entropy estimate.  This way if the carry-over data is not truly random, no
serious security vulnerability will ensue.

[reposted as the initial submission timed out without confirmation]

Viewing the previous replies to your script posting, I'd say it's a good 
thing you don't increase the entropy count based on that script.  After 
all, you're using an unencrypted http: connection.  As such, it'd be a 
(relatively) simple matter for an attacker, indeed, even a remote 
attacker, to do a MitM attack and substitute whatever he wanted into 
the "response from random.org", which for all you know is anything but.

So yes, in line with the theme of the article, adding the bits shouldn't 
do any harm, as long as you don't count it as added entropy.  However, it 
certainly can't be counted on to /help/ either, since you've really no 
idea where the data is coming from or how predictable it might be, so it's 
a good thing your script does /not/ have the system count it as added 
entropy.

Of course, the first instinct would then be to use an encrypted/ssl 
connection.  However, I believe that'd be defeating the purpose to some 
extent, since creating the encrypted connection will (I assume, I'm no 
authority and really haven't a clue, only a guess) consume entropy in the 
first place.  Assuming it's allowed, one could then grab more entropy from 
random.org than was consumed, but there'd still need to be some entropy 
available initially or the encrypted connection itself would be suspect.

I'm really surprised nobody else noted this in their replies... <shrug>

Duncan

Search for "randomness extractor" for information on turning an unknown 
random distribution into a known one.  It's quite difficult, but often 
possible.  Cool combinatorics at work, and also closely related to error 
correcting codes and hashing.  (They're all related by the concept of 
distance between and distinguishability of the sampled points.)

Is it maybe possible to receive randomness through an encrypted connection from a 'randomness'
server?

Hmm... your post asking the question, posted May 29, a comment subthread 
discussing basically that, initial post May 22...

It might be worthwhile reading or at least scanning the existing comments 
before you ask a question in your own comment...

That said, the subthread in question proposed an /unencrypted/ connection 
to such a server (random.org).  You at least get credit for not 
making /that/ mistake.  However, as I just pointed out in a reply to that 
subthread, an encrypted connection probably (I'm no expert, but I believe 
the usual SSL method does anyway) requires some initial entropy to setup 
in the first place, so unless you fetch more than that, it's hardly worth 
it, and even then, you'd have to have at least some initial good quality 
entropy to setup the connection or anything received on it could hardly be 
trustworthy in the first place, so it's a bit of a chicken an egg problem.

Of course, if the encryption entropy is pregenerated and stored, such as 
with one-time-pads or the like, it's possible.  OTOH, the longer such 
pregenerated entropy is held, the more opportunity there has been to 
compromise it by some means or other, so that's not a perfect solution 
either.  Still, it may be "good enough", but then again, the unencrypted 
http solution discussed above, or indeed, the "enriched" PRNG solution 
of /dev/urandom, is likely "good enough" for most general use cases as 
well.

Duncan