On the safety of Linux random numbers [LWN.net]

On the safety of Linux random numbers

Posted May 11, 2006 17:21 UTC (Thu) by Ross (guest, #4065)
In reply to: On the safety of Linux random numbers by zooko
Parent article: On the safety of Linux random numbers

I don't see how /dev/random can be called pseudorandom. It uses a fixed algorithm to produce the output, sure, but the amount of output is no greater than the amount of physically random input. It's not just a seemingly-random number sequence with an unknown starting point.

Now /dev/urandom is also more than a pseudorandom number generator, but unlike /dev/random, it doesn't keep track of entropy, so it may dengenerate into a pseudorandom sequence at any time without warning.

to post comments

On the safety of Linux random numbers

Posted May 11, 2006 17:47 UTC (Thu) by zooko (guest, #2589) [Link] (1 responses)

What you say is indeed the widespread belief, and the original motivation for the distinction between /dev/random and /dev/urandom, but the truth of this belief has not been proven.

For starters, there is no guarantee that /dev/random is outputting an amount no greater than the amount of random input. (Indeed, it is impossible to prove that it did without being able to read the mind of your attacker.) For example, the patches which form the subject of this LWN story are one attempt to tweak the estimate of the randomness input because someone (Matt Mackall) thought that the current estimator was estimating something incorrectly.

My point isn't that the estimator is particularly bad -- my point is that the existence of the estimator demonstrates that there is no hard guarantee that the amount of output is no greater than the amount of input.

In theory, it is an open question whether /dev/random or /dev/urandom is more secure against cryptanalysis. In practice, they are very likely both secure, except that the blocking behavior of /dev/random introduces different vulnerabilities. (And except for a few unfortunate flaws in /dev/urandom...).

On the safety of Linux random numbers

Posted May 11, 2006 18:44 UTC (Thu) by Ross (guest, #4065) [Link]

I see what you are saying. Yes, it is an open question just how closely the entropy estimates match the actual gathered entropy. Certainly the double-counting (like corrected in the floppy driver patch) doesn't make one feel secure. However the counts are in general very conservative so it is more likely they are an underestimate than an overestimate.

About comparing the security of /dev/random and /dev/urandom: I don't understand the problem. They are equivalent under cryptanalysis because they use exactly the same mechanism to produce output, or at least that was my understanding. The only difference, which is not cryptographic, is the blocking behavior of /dev/random. Blocking readers when the estimated entropy is too low can not make it easier to reverse the hashing or otherwise attempt to determine the contents of the entropy pool. Now it may not make it any harder, but that is a different statement. That possibility is probably acceptable because the only disadvantage to blocking is as you said earlier: denial of service and slowed performance. But the system where both methods are present is good because system administrators can use /dev/urandom (or even change the /dev entry) all the time if that is what they really want.