Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does the kernel entropy pool work?

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?

like image 375
Antoninarto Avatar asked Nov 14 '13 15:11

Antoninarto


People also ask

What is kernel entropy pool?

The kernel maintains an entropy pool which is used to store random data generated from events like inter-keypress timings, inter-interrupt timings, etc. Randomness from these interfaces are fixed with the entropy pool using a sort of cyclic redundancy check-like function.

What is entropy pool Linux?

On Linux, the root of all randomness is something called the kernel entropy pool. This is a large (4,096 bit) number kept privately in the kernel's memory. There are 24096 possibilities for this number so it can contain up to 4,096 bits of entropy.

What is Linux kernel entropy?

The Linux kernel generates entropy from keyboard timings, mouse movements, and IDE timings and makes the random character data available to other operating system processes through the special files /dev/random and /dev/urandom. This capability was introduced in Linux version 1.3. 30.

How do computers generate entropy?

In computing, entropy is the randomness collected by an operating system or application for use in cryptography or other uses that require random data. This randomness is often collected from hardware sources, either pre-existing ones such as mouse movements or specially provided randomness generators.


1 Answers

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.

like image 174
jbr Avatar answered Sep 21 '22 04:09

jbr