From owner-freebsd-security@FreeBSD.ORG Wed Sep 19 22:57:52 2012 Return-Path: Delivered-To: freebsd-security@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 941B8106564A; Wed, 19 Sep 2012 22:57:52 +0000 (UTC) (envelope-from mariusz.gromada@gmail.com) Received: from mail-wg0-f50.google.com (mail-wg0-f50.google.com [74.125.82.50]) by mx1.freebsd.org (Postfix) with ESMTP id E85E08FC08; Wed, 19 Sep 2012 22:57:51 +0000 (UTC) Received: by wgi16 with SMTP id 16so1194724wgi.31 for ; Wed, 19 Sep 2012 15:57:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=nEbJi2p+HJc9sF5WUwDIRDmQsu+DGlEcy85lbKQCsTU=; b=lV2mczt+0S2MpOPYL2SVMaV5w+xTl2EzbwWuppbGrAgngAF7KsErkg8PWPdLFzrnCW X3D0lhk+h9gPqque07LmYbM1qSa8dE3/HM9t9uQN3icVIcNHlpknhVYZm8QlueXU3laj 0vHfvJ7shvO4m16kRd3M5jhMGP5k41NOCAFmpPr1mkp4D1WVpHAmmRRGKjxPwrG3Qt7k F818D6MsxrYNmqVNpXttj1aEGUlFFrQ32BHUkzczgB2ZiEZ6at35z7OYSo0+nFccEgAw fPOkFTwj1CkfJRfJnbAgjMfEH4PR/CAFFJQY4rSGfuMKbKrDZC5ykD4f3DlKf0QWRQyF znMA== Received: by 10.180.95.193 with SMTP id dm1mr1579875wib.10.1348095470977; Wed, 19 Sep 2012 15:57:50 -0700 (PDT) Received: from [127.0.0.1] (89-76-147-86.dynamic.chello.pl. [89.76.147.86]) by mx.google.com with ESMTPS id eu4sm29808150wib.2.2012.09.19.15.57.49 (version=SSLv3 cipher=OTHER); Wed, 19 Sep 2012 15:57:50 -0700 (PDT) Message-ID: <505A4DE7.3040304@gmail.com> Date: Thu, 20 Sep 2012 00:57:43 +0200 From: Mariusz Gromada User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:15.0) Gecko/20120907 Thunderbird/15.0.1 MIME-Version: 1.0 To: Pawel Jakub Dawidek References: <20120918211422.GA1400@garage.freebsd.pl> <20120919192923.GA1416@garage.freebsd.pl> <20120919205331.GE1416@garage.freebsd.pl> In-Reply-To: <20120919205331.GE1416@garage.freebsd.pl> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Thu, 20 Sep 2012 01:02:26 +0000 Cc: freebsd-security@freebsd.org, Jonathan Anderson 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: Wed, 19 Sep 2012 22:57:52 -0000 > On Wed, Sep 19, 2012 at 09:29:23PM +0200, Pawel Jakub Dawidek wrote: > Here's how the distribution looks like for device_attach() times of my > sound card. The times were 26bit numbers, so this is after discarding > top ten bits, which leave us with 16 lower bits of pure entropy:) > http://people.freebsd.org/~pjd/misc/harvest_device_attach.png Kudos to > my friend Mariusz (CCed) who is mathematician and who helped me with > visualization and also promissed to prepare formal proof:) Hi All, I am not a mathematician :-) Below you will find some initial formal proof. Problem definition: checking if data sample comes from uniform distribution. Data sample: 2081 empirical observations (after discarding top ten bits) One-sample Kolmogorv-Smirnov test Hypothesis (based on the Cumulative Distribution Functions) H0: Empirical CDF given by 2081 obs. = theoretical uniform CDF H1: (alternatively) Empirical CDF is different than theoretical uniform CDF K-S Statistic: D = 0.017405527 p-value = 0.535 Interpretation: if p-value is much higher than significance level (alpha) then there is no reason to reject H0 hypothesis, if p-value is much smaller than significance level (alpha) then we strongly reject H0 hypothesis. So take any reasonable significance level (i.e. alpha = 0.05 which is far less than 0.535) and you have a proof that empirical observations are in fact given by random uniform numbers. Additionally please take a look on the linked chart http://bamper.vot.pl/ks.jpg It shows: Good fit in general Best fit for the range 0 - c.a 3000 Worse fit for the range c.a. 3000 - 65536 It means that numbers between 0 - 3000 are more random than numbers between 3000 - 6536 Best regards, Mariusz