`On Tue, Aug 20, 2002 at 11:59:49AM +0300, Tommi Kyntola wrote:> On Mon, 19 Aug 2002, Oliver Xymoron wrote:> > On Mon, Aug 19, 2002 at 01:43:59AM -0400, Theodore Ts'o wrote:> > > On Sat, Aug 17, 2002 at 09:15:22PM -0500, Oliver Xymoron wrote:> > >> > > >  Assuming the interrupt actually has a nice gamma-like distribution> > > >  (which is unlikely in practice), then this is indeed true. The> > > >  trouble is that Linux assumes that if a delta is 13 bits, it contains> > > >  12 bits of actual entropy. A moment of thought will reveal that> > > >  binary numbers of the form 1xxxx can contain at most 4 bits of> > > >  entropy - it's a tautology that all binary numbers start with 1 when> > > >  you take off the leading zeros. This is actually a degenerate case of> > > >  Benford's Law (http://mathworld.wolfram.com/BenfordsLaw.html), which> > > >  governs the distribution of leading digits in scale invariant> > > >  distributions.> > > > > > > >  What we're concerned with is the entropy contained in digits> > > >  following the leading 1, which we can derive with a simple extension> > > >  of Benford's Law (and some Python):> I think you have it slightly wrong there. By snipping away the first digit > from a number leaves you with, not Benford's distribution, but > uniform distribution, for which the Shannon entropy is naturally roughly> the bitcount.No, it's much more complicated than that - that doesn't give us scaleinvariance. Observe that the distribution of the first and seconddigits in base n is the same as the distribution of the first digit inbase n*2. The probability of finding a 0 as the second digitbase 10 is simply the sum of the probabilities of finding 10, 20,30,..90 as the first digit, base 100, see? It's .1197, rather than theexpected .1. In base 2, the odds of the second digit being 0 is .58.My original message included the code I used to calculate thedistribution, along with the calculated entropy content of n-digitstrings.> Wether the bit count of the smallest of the three deltas is> actually sufficient to guarantee us that amount of randomness in the > choice is another question. Like stated here already, it can be easily > fooled, and there's a strong possibility that it gets "fooled" already.That's why my code makes a distinction between trusted and untrustedsources. We will only trust sources that can't be used to spoof us.Detecting spoofing is impossible.> Some level of fourier analysis would be necessary to go further than what > we can with the deltas.There's no point in going further. If an attacker is trusted, he cansend timing streams that would fool _any_ filter. An example is somesubset of the digits of pi, which appear perfectly evenly distributedbut are of course completely deterministic.--  "Love the dolphins," she advised him. "Write by W.A.S.T.E.." -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/`