How random is random enough? [LWN.net]

Oliver Xymoron posted a set of /dev/random patches this week, introducing them with:

I've done an analysis of entropy collection and accounting in current Linux kernels and founds some major weaknesses and bugs. As entropy accounting is only one part of the security of the random number device, it's unlikely that these flaws are compromisable, nonetheless it makes sense to fix them.

Entropy, of course, can be thought of as the amount of random data the kernel currently has available for the creation of random numbers. The entropy pool is filled by looking at (hopefully) random events as seen by the processor - such as the timing of device interrupts. Oliver's claim is that the kernel is vastly overestimating the amount of entropy it is accumulating, and thus handing out numbers that are not as random as expected.

Some of the trouble comes from over-optimistic assumptions of the amount of randomness really contained in interrupt timings. Simply put, the resolution of interrupt timing is not what the kernel thinks it is. Oliver also claims that interrupt timing is often observable or controllable by hostile users. The timing of network packets has long been considered suspect for this very reason; Oliver says that disk timing is subject to the same sort of manipulation. Oliver has also pointed out a bug in the way timing samples are merged into the entropy pool.

Finally, Oliver claims:

Worst of all, the accounting of entropy transfers between the primary and secondary pools has been broken for quite some time and produces thousands of bits of entropy out of thin air.

Interestingly, this last one may not be a real bug - read Ted Ts'o's explanation of why things are done this way for the details. Generating random numbers that are resistant to guessing is a difficult task.

Oliver's fixes have the result of greatly reducing the amount of entropy available to the system, and thus the number of random numbers that can be obtained from /dev/random. Linus doesn't like this aspect of the patch; he fears that making /dev/random difficult to use will just cause people to not use it.

Randomness is like security: if you make it too hard to use, then you're shooting yourself in the foot, since people end up unable to practically use it.

If /dev/random can not obtain enough entropy to be useful, says Linus, it's probably better to just get rid of it altogether.

This discussion has reached no real resolution as of this writing, and the entropy patches have not been merged. Some sort of fix will likely go in at some point, once a compromise between "proper" entropy accounting and usefulness has been reached.

(Log in to post comments)