random: Remove SA_SAMPLE_RANDOM from network drivers
The thing to do, on modern machines, is to stop relying on external sources and start using the timer interrupt.
Since there is a gigahertz-rate clock available, the jitter between it and another clock can be a fruitful source of entropy. Frankly, I think there's > 1 bit of entropy available per sample, but even at 0.01 bits per sample (which is saying that it's exactly predictable at least 99.914% of the time), that's still 128 bits of key in 13 seconds.
Even though both the processor clock and the timer clock are ultimately derived from the same crystal, the phase-locked loops which do the frequency multiplying have quite detectable noise. And that's ignoring the "spread-spectrum" frequency modulation that many modern PC motherboards do.
In these days of wireless keyboards and mice, /dev/random's faith in those sources is probably misplaced, but with much faster processor clocks, a new, purely internal source becomes much more practical.
Machines without TSCs are still a challenge. For PCs, I'd suggest using the 32 kHz-crystal-driven RTC and beating that against the 2 MHz PIT. On other platforms, I'm a little unclear.
If you want to test this, collect the appropriate data points on an otherwise idle machine, with speread-spectrum clocking turned off in the BIOS of possible, subtract the slope, and delete all the outlyers. Then look at the scatter of the remaining data and subject it to various randomness tests. Note that if there is a PLL connecting the two clocks, a sufficiently high-resolution slope measurement will reveal the rational number ratio.
For those intersted, the entropy (in bits) of a based coin is related to the chance of its landing heads (or tails) as follows:
Entropy Probability
1 0.5
0.999 0.518614
0.99 0.558802
0.9 0.683981
0.8 0.756996
0.7 0.810702
0.6 0.853898
0.5 0.889972
0.4 0.920617
0.3 0.946761
0.2 0.968876
0.1 0.987013
0.09 0.988590
0.08 0.990119
0.07 0.991598
0.06 0.993024
0.05 0.994393
0.04 0.995699
0.03 0.996936
0.02 0.998090
0.01 0.999140
0.009 0.999237
0.008 0.999333
0.007 0.999427
0.006 0.999519
0.005 0.999608
0.004 0.999695
0.003 0.999779
0.002 0.999860
0.001 0.999935
If there are more secondary alternatives than just "tails", the numbers - either the entropy for a certain probability of heads, or the probability of heads to get a certain entropy - go up.
As for the discussion of hash functions "broken", /dev/random is very conservative about its use of the hash function.
There are three major kinds of attacks against hash functions. In increasing order of difficulty:
1) Collision attack. Find x and y such that H(x) == H(y)
2) Second pre-image attack. Given y, find x so H(x) == H(y).
3) (First) pre-image attack. Given y, find x so H(x) == y.
There is an obvious brute-force solution to a collision attack for an n-bit hash in O(2^(n/2)) steps. (Basically, compute the hashes of 2^(n/2) random strings; you will alsmost certainly find a collision. There re clever ways to avoid storing 2^(n/2) input values.)
Generally, when collsions are easy to find in a hash function, it is considered broken for practical purposes. For example, if I know a collision for two values x and y, suppose I give you $x in return for a digitally signed negotiable instrument for $x. Then I can change it to read $y and present it for payment. Assuming that x < y, this has potential for profit. (Reality is a bit more complicated, but hopefully you get the idea.)
A pre-image attack, where there is a *single* hash value you want to match, is far more difficult. For example, even for the generally laughable MD4, a second pre-image attack is only known for a class of "weak" messages consituting 2^-122 of possible inputs. (Xiaoyun Wang et. al, "Cryptanalysis of the Hash Functions MD4 and RIPEMD", 2005)
To break /dev/urandom with cryptanalysis, the basic difficulty lies in deducing the internal random pool state. The pool is by default 1024 bits in size, but you only get 80 bits of hash function output at a time. So the first thing you have to do is read at least as many bits from the pool as there is entropy, and then solve a pre-image problem. But not just ANY pre-image will do; you have to find the one of the 2^1024 states that simultaneously satisfies your a priori knowledge of the pool state and the (possibly multiple) hash function pre-image conditions. This is vastly harder than a simple pre-image attack, which is much much harder than a collision attack.
Even if the hash function is so thoroughly broken that it's are useless for most purposes, it can still shield /dev/urandom's internal state.
It's a very conservative and robust design.
Eek! I just realized that my earlier posting about the entropy from biased coin flips was wrong. More dangerous than obviously wrong, it was subtly wrong.
The table I posted was based on the common Shannon entropy measure. However, it is well known in the theory of "randomness extractors" that Shannon entropy is not the appropriate measure to use when judging an entropy source which you are going to derive key material from; you need to use the more conservative min-entropy.
For a reminder, if your random variable has a number of possible states 1..n, with corresponding probabilities p[1]..p[n], then the Shannon entropy of this variable is
sum -p[i] * log(p[i]), for i = 1..n
while the min-entropy is simply
min -log(p[i]), for i = 1..n
(For entropy in bits, we will use the base-2 logarithm.) These are identical if all the p[i] are equal, but the min-entropy is lower in all other cases.
The classic example of a bad source with good Shannon entropy is a 256-bit key that has 255 bits of randomness half the time, but has a single fixed value the other half of the time. If you plug this distribution into the Shannon entropy formula, you get 128.5 bits of entropy. That should be enough to keep out an attacker, right?
Well, except for the half of the time when you're using the single fixed value! The problem is that the fact that you have much more than the required 128 bits half of the time doesn't make up for the drastic loss the other half of the time.
For an entropy-accumulation example, suppose you have a source which produces 31 truly random bits (0..07fffffff) half of the time, and a fixed value of -1 the other half of the time. Again, the Shannon entropy of this source is easily computed as 16.5 bits per sample.
Just to work through the math for the Shannon entropy, we have p[-1] = 1/2, and p[0] = p[1] = ... = p[0x7fffffff] = 2^-32.
sum -p[i] * log(p[i]), for i = -1..0x7fffffff = (-(1/2) * log(1/2) ) + The i = -1 case sum -(2^-32) * log(2^-32), for i = 0..0x7fffffff
= -1/2 * -1 + 2^31 * -(2^-32 * -32)
= 1/2 + 1/2 * 32
= 1/2 + 16
= 16.5
So taking 8 such samples should produce 132 bits of entropy, which can be hashed into a good 128-bit key, right?
Well, except for the 1/256 of the time when the key is the hash of 8 copies of -1. And an additional 8/256 = 1/32 of the time, the key has 34 bits of entropy. (31 bits in one of the 8 seeds, plus 3 bits of uncertainty as to which seed.)
Again, even though on average the input has more than 128 bits of entropy, the hashing throws away the excess, while the naive Shannon estimate averages that wasted excess with the cases that are severly lacking.
Unsing the min-entropy estimate, the source has 1 bit if min-entropy, so 8 samples have 8 bits of min-entropy, and a good hash won't change that much. (It can't make it better, and collisions will make it slightly worse.) The highest-probability key will occur 2^-8 = 1/256 of the time.
In particular, the table of the probabilities needed to achieve a particular entropy should be amended as follows:
Entropy Probability min-entropy of
(bits) Shannon min Shannon prob
1 0.5 0.5 1
0.999 0.518614 0.500347 0.947267
0.99 0.558802 0.503478 0.839591
0.9 0.683981 0.535887 0.547972 0.8 0.756996 0.574349 0.401642 0.7 0.810702 0.615572 0.302756 0.6 0.853898 0.659754 0.227864 0.5 0.889972 0.707107 0.168168 0.4 0.920617 0.757858 0.119327 0.3 0.946761 0.812252 0.078928 0.2 0.968876 0.870551 0.045616 0.1 0.987013 0.933033 0.018859 0.09 0.988590 0.939523 0.016556 0.08 0.990119 0.946058 0.014326 0.07 0.991598 0.952638 0.012173 0.06 0.993024 0.959264 0.010100 0.05 0.994393 0.965936 0.008112 0.04 0.995699 0.972655 0.006218 0.03 0.996936 0.979420 0.004427 0.02 0.998090 0.986233 0.002758 0.01 0.999140 0.993092 0.001241 0.009 0.999237 0.993781 0.001101 0.008 0.999333 0.994470 0.000963 0.007 0.999427 0.995160 0.000827 0.006 0.999519 0.995850 0.000694 0.005 0.999608 0.996540 0.000566 0.004 0.999695 0.997231 0.000440 0.003 0.999779 0.997923 0.000319 0.002 0.999860 0.998615 0.000202 0.001 0.999935 0.999307 0.000094
(WRONG) (RIGHT) (RIGHT entropy of WRONG probability)
You need a most-likely probability less than the "min probability" column to achieve the min-entropy given in the first column. The fourth column gives the actual min-entropy you'd get if you used the Shannon-derived probability. Note that it's off by a factor of >10 near the bottom of the list. (1-p = e*ln(2) is a very close approximation when e is much less than 1.)
Also, unlike the Shannon entropy, the number and probabilities of less-likely alternatives do not matter. This actually makes analysis of interrupt timing easier, because you don't have to worry about outliers. Just see how often you can predict the EXACT timestamp of an interrupt and ignore the rest.
(This in turn leads to the possibility of real-time entropy measurement of timer interrupts. Assuming both are derived from a common crystal via PLLs, the slope of the interrupt number vs. timestamp should be a simple exact rational number. You can build a histogram of the measured timestamps around the predicted slope, discarding outliers, and use the maximum value to compute the min-entropy. To be conservative, take the sum of the largest two in case the wiggle between them is modelable.)