From owner-freebsd-security@FreeBSD.ORG Tue Sep 25 09:03:24 2012 Return-Path: Delivered-To: freebsd-security@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 08049106564A; Tue, 25 Sep 2012 09:03:24 +0000 (UTC) (envelope-from benlaurie@gmail.com) Received: from mail-vc0-f182.google.com (mail-vc0-f182.google.com [209.85.220.182]) by mx1.freebsd.org (Postfix) with ESMTP id 80E158FC0C; Tue, 25 Sep 2012 09:03:23 +0000 (UTC) Received: by vcbfw7 with SMTP id fw7so9408980vcb.13 for ; Tue, 25 Sep 2012 02:03:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date :x-google-sender-auth:message-id:subject:from:to:cc:content-type; bh=bkM9MypI/0DsK/9GPKPQRSYC1pOVUHijJ8Ln46xyOh4=; b=U7oSbKf8TxSlS/E7n4XVO4Cn8A3Nr4DlZ9IroSRdjOGNuStSwx+4bZVEKyklusZjBH 0jUK5bZXcWX/IE4qbWOXo3py1eaHUDpSc7QG14NyTGDMKA3k3HahTXjBLOkIU2VaYs+0 5T/d1wtW6UtK2tn7A4LTlWY1+e84IXt6lpw4ZFYIUCTCPE4g3FK4+UA98GFuc0R7FK0y AKCUqLJpgiaNO3QwLZfpBeGoXrAsH67HJ1cKv7/6n77TLJUZjNXVUJTDZwOYYQTe8Wpl DWurULlhmxwVQVrDnThBc3uE1OHgo5p41bPwtODwJZEwLYTrHTTY4FXEiKJR2iFclTWI ScXg== MIME-Version: 1.0 Received: by 10.220.157.65 with SMTP id a1mr8815203vcx.39.1348563802277; Tue, 25 Sep 2012 02:03:22 -0700 (PDT) Sender: benlaurie@gmail.com Received: by 10.58.79.243 with HTTP; Tue, 25 Sep 2012 02:03:22 -0700 (PDT) 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> Date: Tue, 25 Sep 2012 10:03:22 +0100 X-Google-Sender-Auth: YV7f9e883Et0KHJku8XQ6UMbMPs Message-ID: From: Ben Laurie To: Mariusz Gromada Content-Type: text/plain; charset=ISO-8859-1 Cc: freebsd-security@freebsd.org, RW , Jonathan Anderson , Pawel Jakub Dawidek , John Baldwin Subject: Re: Collecting entropy from device_attach() times. X-BeenThere: freebsd-security@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Security issues \[members-only posting\]" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 25 Sep 2012 09:03:24 -0000 On Mon, Sep 24, 2012 at 10:56 PM, Mariusz Gromada 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.