`I'd like to apologise for the harsh tone of my earlier message.I was frustrated, and it showed.I hope I can be more gentle as I continue to elaborate on the shortcomingsof that scheme.Concentrating entropy is hard.  To paraphrase Princess Leia, "the moreyou tighten your grip, the more entropy will slip through your fingers."While it's true that the entropy of two independent bit strings is atleast as high as the entropy of either one, it's not necessarily muchhigher, either.I'm going to discuss two things here.  First, what happens if you assumethat the inpuit samples are made up of independent and identicallydistributed (i.i.d.) random bits, and second why they're not i.i.d.When talking about single bits, all that matters is the probabilitiesof the two values.  I'm going to assume that the bits are 1 with someprobability p <= 0.5, and 0 with probability p >= 0.5, but that's justfor convenience.You can XOR any attacker-known pattern into those bits and it doesn'tchange the entropy.  What matters is the probability that they match anattacker's prediction, and the probability that they don't match.For example, if an attacker knows that a bit is 75% likely to matchsome other bit, then I'll describe it with p=0.25.i.i.d. bits of course all have the same entropy.  Suppose that we have 32bits, with 0.1 bits of entropy each, making 3.2 bits of entropy in total.This is a pretty good sample; it shoud be easy to get one bit with highentropy out of this, right?Well, no.0.1 bits of Shannon entropy means that a bit is 0 with probability 98.7%,and 1 with probability p = 1.3%.If you XOR two such bits together, the result is 1 with probability2 * p * (1-p) (which is also less than 0.5).Let's work out the entropy assuming we start with 0.1 of a bit of Shannonentropy per bit, and 0.1 of a bit of min-entropy per bit, and thenform the XOR of increasingly large blocks:Starting with 32/10 bits of Shannon entropy 1: p=0.012987  Shannon=0.100000 (sum 3.200000)  Min=0.018859 (sum 0.603482) 2: p=0.025636  Shannon=0.172013 (sum 2.752203)  Min=0.037468 (sum 0.599486) 4: p=0.049958  Shannon=0.286220 (sum 2.289760)  Min=0.073937 (sum 0.591499) 8: p=0.094925  Shannon=0.452699 (sum 1.810795)  Min=0.143891 (sum 0.575563)16: p=0.171829  Shannon=0.661871 (sum 1.323741)  Min=0.271999 (sum 0.543997)32: p=0.284607  Shannon=0.861653 (sum 0.861653)  Min=0.483192 (sum 0.483192)The last line is the probability that the XOR of 32 such bits is 1.28.46% is still some distance from 50/50, isn't it?The min-entropy per bit comes close to doubling each time, since itsuffers less from saturation effects as it approaches 1 bit per bit,but still 20% of the entropy is lost.Starting with 32/10 bits of min-entropy 1: p=0.066967  Shannon=0.354502 (sum 11.344068)  Min=0.100000 (sum 3.200000) 2: p=0.124965  Shannon=0.543466 (sum  8.695452)  Min=0.192587 (sum 3.081394) 4: p=0.218697  Shannon=0.757782 (sum  6.062253)  Min=0.356046 (sum 2.848372) 8: p=0.341738  Shannon=0.926472 (sum  3.705887)  Min=0.603265 (sum 2.413061)16: p=0.449906  Shannon=0.992747 (sum  1.985494)  Min=0.862250 (sum 1.724500)32: p=0.494981  Shannon=0.999927 (sum  0.999927)  Min=0.985591 (sum 0.985591)Because min-entropy is a more conservaitve estimate, the starting probabilityis much closer to 50/50, and we got very close to unbiased.  But it took11 bits of Shannon entropy to do it!Working the formula backward, we can deduce that to get 0.95 bits ofShannon entropy by XORing 32 i.i.d. bits, each of the input bits needsto have p = 0.020511, 0.1443 bits of entropy, a total of 4.62 bits.In fact, if the maximum entropy per bit is low enough then theprobability of getting the all-zero word is greater than 50% andthat imposes an upper limit on the entropy produces by *any* hashingscheme.For 0.1 bits of Shannon entropy per bit, (1-p)^32 = 0.658164 so even ifyou reduced to one bit using !, you couldn't get closer to 50:50than that.  (0.926565 bit Shannon, 0.603482 bits min-entropy.)It turns out that lots of weakly random i.i.d. bits are a worst case forthis sort of reduction; if divide entropy in a "triangular" way, wherebit i gets (i+1) parts of the entropy (dividing by (32*33/2) to normalize)then we get a final XOR ofp=0.338856  Shannon=0.923720  Min=0.596964which is better than the p=0.284607 we got from i.i.d. bits.Is it, then, perhaps the case that the i.i.d. assumption is not a good one?The bit patterns we're talking about don't seem to resemble realistictimestamps.It's a very bad one, as I'll explain.*Independence* can exist in a vacuum: not correlated with anything.That's what /dev/random is trying to produce.  But the seed materialis anything but.There are two major sources of information to an attacker about theseed entropy:1) An attacker is assumed to know all prior seed inputs.   That's because we're trying to quantify the *additional* entropy   contributed by this sample.  The difficulty of guessing the   previous seed material has already been accounted for in the   entropy assigned to it.  So any correlation with any previous   seed material must be considered non-random.2) An attacker is assumed to be able to run programs on the   machine collecting entropy.  This is because we want different   users' random bits to be secure from each other.For the second issue, note that on my Ivy Bridge, I can do rdtsc(),subtract from the previous and compare to a threshold in 24 cycles.If I notice a sudden jump in rdtsc() deltas, I know an interrupthappened, and I know when it happened within a window of 24 clockcycles.There's some delay to run the interrupt handler, but that'shighly predictable.If interrupt arrival time is quantized, by a lower APIC clock speed,PCI bus clock speed, or the like, then it's possible there's lessthan log2(24) = 4.6 bits of uncertainty there.(It may be possible to ignore this threat during early boot whennothing is running, to speed up entropy accumulation.)Getting to the first, much more important case, this is why the bits ina captured timestamp are neither independent nor identically distributed.What we care about those statements is *relative to the knowledge of theattacker*.  Deterministic whitening is easy and completely pointless; theonly thing we're interested in measuring is what an attacker cannot know.First of all, the correlation with the *previous* timestamp is strongerthe higher you go in the bits.The chance of a higher-order bit having the predicted value is higher thanfor a lower-order bit.  Thus, the bits aren't identically distributed.If bit 31 toggles, bit 30 is almost certainly 0 now.  Thus, the bitsaren't independent.There are many more counterexamples, but just those two will sufficeto show that the i.i.d. assumption is fatally flawed.  It makes the matheasy, but that's not what the available entropy is like.The way to think about handling entropy is minimizing collisions.No collisions means no entropy loss.  Collisions mean entropy loss.This is not a huge problem when you're extracting from a pool and thepool remains; all that happens is the remaining entropy stays in the pool.Two possible inputs that result in the same pool state afterward is likecrossing the streams: it Would Be Bad.  You can't eliminate the possibilitywith a finite-sized pool, but you should work to minimize it.`