Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 25 Sep 2012 10:03:22 +0100
From:      Ben Laurie <benl@freebsd.org>
To:        Mariusz Gromada <mariusz.gromada@gmail.com>
Cc:        freebsd-security@freebsd.org, RW <rwmaillists@googlemail.com>, Jonathan Anderson <jonathan.anderson@cl.cam.ac.uk>, Pawel Jakub Dawidek <pjd@freebsd.org>, John Baldwin <jhb@freebsd.org>
Subject:   Re: Collecting entropy from device_attach() times.
Message-ID:  <CAG5KPzxf0Rfufk5K6Jt4e85xc7zXY_B3a2Sq0Uf_uVLHbV-baw@mail.gmail.com>
In-Reply-To: <5060D723.6020305@gmail.com>
References:  <20120918211422.GA1400@garage.freebsd.pl> <20120919231051.4bc5335b@gumby.homeunix.com> <20120920102104.GA1397@garage.freebsd.pl> <201209200758.51924.jhb@freebsd.org> <20120922080323.GA1454@garage.freebsd.pl> <20120922195325.GH1454@garage.freebsd.pl> <505E59DC.7090505@gmail.com> <20120923151706.GN1454@garage.freebsd.pl> <5060D723.6020305@gmail.com>

next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, Sep 24, 2012 at 10:56 PM, Mariusz Gromada
<mariusz.gromada@gmail.com> wrote:
> W dniu 2012-09-23 17:17, Pawel Jakub Dawidek pisze:
>
>> On Sun, Sep 23, 2012 at 02:37:48AM +0200, Mariusz Gromada wrote:
>>>
>>> W dniu 2012-09-22 21:53, Pawel Jakub Dawidek pisze:
>>>>
>>>> Mariusz, can you confirm my findings?
>>>
>>>
>>> Pawel,
>>>
>>> Your conclusions can be easily confirmed by shape analysis of the EDF.
>>> Usually maximum quantile difference (called D-statistic) gives you a
>>> kind of overview, function shape gives you a strong feeling, p-value
>>> gives you a formal proof.
>>> D-statistic values (your data):
>>>
>>>    6bit:   0.33%
>>>    7bit:   0.29%
>>>    8bit:   0.27%
>>>    9bit:   0.21%
>>> 10bit:   6.34%
>>> 11bit:  19.07%
>>> 12bit:  54.80%
>>>
>>> What I would say: increasing the number of bits from 6 to 9 does not
>>> affect distribution "uniformity", reaching the tenth bit results in
>>> sudden increase in the difference measure -  the more bits, the more
>>> difference is observed. Distribution shape analysis for the 10th bit
>>> shows non-linear function. Lack of "randomness" in the quntile
>>> difference curve - chart  shows completely lack of noise (pure
>>> functional relation).  These are very strong indicators that starting
>>> from 10th bit distribution was changed and is no longer uniform.
>>>
>>> To formally confirm above conclusion for i.e. 5% significance level,
>>> which means that confidence level is 95%, I need some extra data
>>> regarding sample sizes. Please pass to me number of collected
>>> observations in each 6-12 bit experiment.
>>
>>
>> Total number of observations was 162833.
>>
>
> Ok, finally I have some formal results. To be completely honest I need to
> point out that, in fact, we have a discrete data (for example integers 0, 1,
> ..., 63, but not continues numbers spread across 0 and 63). That is way  I
> am going to use two sample Kolmogorov-Smirnov test.  Methodology is simple:

...

> As you can see D-statistics are almost the same as calculated by Pawel
> (considering roundings). P-values are very interesting due to very high
> number of observations generated by Pawel. Between 6 bits and 9 bits
> estimated p-values are equal to 1, so it means that it is impossible (at any
> significance level) to reject null hypothesis stating that compared
> distributions are equal. Final conclusion: it has to be random, and for sure
> it is random!

You cannot conclude that - no test can tell you it, but this test
rather obviously does not, since what it tests is the equality of
probability distributions, so what you can now say is that the
distribution is square. A completely predictable sequence, say 0..63,
would satisfy that.

Empirically, it seems to me that these numbers are actually unlikely
to be correlated with each other, but that has not been tested.

Also untested is correlation between the numbers from different
devices on the same run - if they were strongly correlated, for
example, that would be bad.

Not that I dislike Pawel's approach, it seems promising, I'm just
pointing out the weakness of the analysis.



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAG5KPzxf0Rfufk5K6Jt4e85xc7zXY_B3a2Sq0Uf_uVLHbV-baw>