How does the kernel entropy pool work?

Question

I'm using /dev/urandom to generate random data for my programs. I learned that /dev/random can be empty because, unlike /dev/urandom, it doesn't use SHA when there are not enough bytes generated. /dev/random uses "the kernel entropy pool". Apparently it relies on keyboard timings, mouse movements, and IDE timings.

But how does this really work?
And wouldn't it be possible to "feed" the entropy pool making the /dev/random output predictable?

Answer 1

What you are saying is spot on, yes theoretically it is possible to feed entropy into /dev/random, but you'd need to control a lot of the kernel "noise" sources for it to be significant. You can look at the source for random.c, to see where /dev/random picks up noise from. Basically, if you control a significant number of the noises sources, then you can guess what the others are contributing to the entropy pool.

Since /dev/urandom is a Hash chain seeded from /dev/random, then you could actually predict the next numbers, if you knew the seed. If you have enough control over the entropy pool, then from the output of /dev/urandom you might be able to guess this seed, which would enable you to predict all the next numbers from /dev/urandom, but only if you keep /dev/random exhausted, otherwise /dev/urandom will be reseeded.

That being said, I haven't seen anyone actually do it, not even in a controlled environment. Of course this isn't a guarantee, but I wouldn't worry.

So I'd rather use /dev/urandom and guarantee that my program doesn't block while waiting for entropy, instead of using /dev/random and asking the user to do silly things, like moving the mouse or bang on the keyboard.

I think you should read On entropy and randomness from LWN, hopefully it will calm your worries :-).

Should you still be worried, then get yourself a HRNG.

Edit Here is a small note on entropy:

I think the concept of entropy is generally difficult to grasp. There is an article with more information on Wikipedia. But basically, in this case, you can read entropy as randomness.

So how I see it, is that you have a big bag of coloured balls, the higher entropy in this bag the harder it is to predict the next colour drawn from the bag.

In this context, your entropy pool is just a bunch of random bytes, where one cannot be derived from the previous, or any of the others. Which means you have high entropy.

Answer 2

I appreciate the depth of jbr's answer.

Adding a practical update for anyone currently staring at a ipsec pki command or something similar blocking on empty entropy pool:

I just installed rng-tools in another window and my pki command completed.

apt-get install rng-tools

Answer 3

I am in the midst of reading a paper at factorable and made note of the section where it says:

"For library developers: Default to the most secure configuration. Both OpenSSL and Dropbear default to using /dev/urandom instead of /dev/random, and Dropbear defaults to using a less secure DSA signature randomness technique even though a more secure technique is available as an option."

The authors address the tradeoff of an application hanging while waiting for entropy to build /dev/random to get better security compared to a quick, but less secure, result from /dev/urandom.

Answer 4

Some additional Info:

IRQF_SAMPLE_RANDOM : This interrupt flag specifies that interrupts generated by a device should contribute to kernel entropy pool

Interrupt are what devices like mouse, keyboard etc (devices) are sending asynchronously.