`Eek!  I just realized that my earlier posting about the entropy frombiased coin flips was wrong.  More dangerous than obviously wrong, itwas 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" thatShannon entropy is not the appropriate measure to use when judging anentropy source which you are going to derive key material from; you needto use the more conservative min-entropy.For a reminder, if your random variable has a number of possible states1..n, with corresponding probabilities p[1]..p[n], then the Shannon entropyof this variable is	sum -p[i] * log(p[i]), for i = 1..nwhile 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 islower in all other cases.The classic example of a bad source with good Shannon entropy is a 256-bitkey that has 255 bits of randomness half the time, but has a single fixedvalue the other half of the time.  If you plug this distribution intothe Shannon entropy formula, you get 128.5 bits of entropy.  That shouldbe enough to keep out an attacker, right?Well, except for the half of the time when you're using the singlefixed value!  The problem is that the fact that you have much more thanthe required 128 bits half of the time doesn't make up for the drasticloss the other half of the time.For an entropy-accumulation example, suppose you have a source whichproduces 31 truly random bits (0..07fffffff) half of the time, anda fixed value of -1 the other half of the time.  Again, the Shannonentropy 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.5So taking 8 such samples should produce 132 bits of entropy, whichcan be hashed into a good 128-bit key, right?Well, except for the 1/256 of the time when the key is thehash 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 estimateaverages 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 changethat much.  (It can't make it better, and collisions will make it slightlyworse.)  The highest-probability key will occur 2^-8 = 1/256 of the time.In particular, the table of the probabilities needed to achievea particular entropy should be amended as follows:Entropy	     Probability		min-entropy of(bits)	Shannon		min		Shannon prob1	0.5		0.5		10.999	0.518614        0.500347	0.9472670.99	0.558802        0.503478        0.8395910.9	0.683981        0.535887        0.5479720.8	0.756996        0.574349        0.4016420.7	0.810702        0.615572        0.3027560.6	0.853898        0.659754        0.2278640.5	0.889972        0.707107        0.1681680.4	0.920617        0.757858        0.1193270.3	0.946761        0.812252        0.0789280.2	0.968876        0.870551        0.0456160.1	0.987013        0.933033        0.0188590.09	0.988590        0.939523        0.0165560.08	0.990119        0.946058        0.0143260.07	0.991598        0.952638        0.0121730.06	0.993024        0.959264        0.0101000.05	0.994393        0.965936        0.0081120.04	0.995699        0.972655        0.0062180.03	0.996936        0.979420        0.0044270.02	0.998090        0.986233        0.0027580.01	0.999140        0.993092        0.0012410.009	0.999237        0.993781        0.0011010.008	0.999333        0.994470        0.0009630.007	0.999427        0.995160        0.0008270.006	0.999519        0.995850        0.0006940.005	0.999608        0.996540        0.0005660.004	0.999695        0.997231        0.0004400.003	0.999779        0.997923        0.0003190.002	0.999860        0.998615        0.0002020.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" columnto achieve the min-entropy given in the first column.  The fourth columngives the actual min-entropy you'd get if you used the Shannon-derivedprobability.  Note that it's off by a factor of >10 near the bottom ofthe list.  (1-p = e*ln(2) is a very close approximation when e ismuch less than 1.)Also, unlike the Shannon entropy, the number and probabilities ofless-likely alternatives do not matter.  This actually makes analysis ofinterrupt timing easier, because you don't have to worry about outliers.Just see how often you can predict the EXACT timestamp of an interruptand ignore the rest.(This in turn leads to the possibility of real-time entropy measurementof timer interrupts.  Assuming both are derived from a common crystalvia PLLs, the slope of the interrupt number vs. timestamp should be asimple exact rational number.  You can build a histogram of the measuredtimestamps around the predicted slope, discarding outliers, and use themaximum value to compute the min-entropy.  To be conservative, take thesum of the largest two in case the wiggle between them is modelable.)-To unsubscribe from this list: send the line "unsubscribe linux-kernel" inthe body of a message to majordomo@vger.kernel.orgMore majordomo info at  http://vger.kernel.org/majordomo-info.htmlPlease read the FAQ at  http://www.tux.org/lkml/`