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: - Pawel旧 data will be called empirical one - Theoretical data will be generated as a sequence of unique integer numbers from 0 to 2**n -1, where n is the number of bits. Assumption - each number appears in theoretical data only once representing ideal uniform distribution. Calculations will be done in the R-cran package Loading empirical data form files: > e6 = read.table("E:\\pawel\\dhr2_6bit_sorted.txt") > e7 = read.table("E:\\pawel\\dhr2_7bit_sorted.txt") > e8 = read.table("E:\\pawel\\dhr2_8bit_sorted.txt") > e9 = read.table("E:\\pawel\\dhr2_9bit_sorted.txt") > e10 = read.table("E:\\pawel\\dhr2_10bit_sorted.txt") > e11 = read.table("E:\\pawel\\dhr2_11bit_sorted.txt") > e12 = read.table("E:\\pawel\\dhr2_12bit_sorted.txt") Generating ideal theoretical data: > t6 = c(0:(2**6-1)) > t7 = c(0:(2**7-1)) > t8 = c(0:(2**8-1)) > t9 = c(0:(2**9-1)) > t10 = c(0:(2**10-1)) > t11 = c(0:(2**11-1)) > t12 = c(0:(2**12-1)) Performing KS tests: > ks.test(e6, t6) D = 0.0032, p-value = 1 > ks.test(e7, t7) D = 0.0029, p-value = 1 > ks.test(e8, t8) D = 0.0027, p-value = 1 > ks.test(e9, t9) D = 0.0022, p-value = 1 > ks.test(e10, t10) D = 0.0634, p-value = 0.0005562 > ks.test(e11, t11) D = 0.1907, p-value < 2.2e-16 > ks.test(e12, t12) D = 0.5479, p-value < 2.2e-16 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! Additionally starting form 10 bits we can observe dramatic decrease of p-value (from 100% to c.a. 0,06% and much less for the 11-12 bits). So low p-value means that it is impossible not to reject null hypothesis stating that compared distributions are equal. Final conclusion: it cannot be random, and for sure it is not random. I did the same comparison for the previous real device attach data (2081 obs.). R code and the results are below: > e16 = read.table("E:\\pawel\\device_attach_16bit.log") > t16 = c(0:(2**16-1)) > ks.test(e16, t16) D = 0.0178, p-value = 0.5422 Again, D-statistic an p-value are almost the same as previously calculated "manually". P-value is very high (it is not as high as in the 6-12 bits tests, but consider much lower number of observations: 2081 vs 162833), giving almost sureness that you have captured real 16-bits entropy! Regards, Mariusz _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-security To unsubscribe, send any mail to "[email protected]"