From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark H Weaver Newsgroups: gmane.lisp.guile.devel Subject: Re: Improve `seed->random-state' in stable-2.0? Date: Fri, 20 Jan 2012 13:52:55 -0500 Message-ID: <878vl2w6ig.fsf@netris.org> References: <87d3afvyr6.fsf@netris.org> <87ipk6tof0.fsf@pobox.com> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: dough.gmane.org 1327085645 30282 80.91.229.12 (20 Jan 2012 18:54:05 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Fri, 20 Jan 2012 18:54:05 +0000 (UTC) Cc: guile-devel@gnu.org To: Andy Wingo Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Fri Jan 20 19:53:58 2012 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1RoJb3-0001NQ-OR for guile-devel@m.gmane.org; Fri, 20 Jan 2012 19:53:57 +0100 Original-Received: from localhost ([::1]:48901 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RoJb3-00026i-E7 for guile-devel@m.gmane.org; Fri, 20 Jan 2012 13:53:57 -0500 Original-Received: from eggs.gnu.org ([140.186.70.92]:58294) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RoJb0-00024F-1M for guile-devel@gnu.org; Fri, 20 Jan 2012 13:53:55 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RoJas-0000z6-M5 for guile-devel@gnu.org; Fri, 20 Jan 2012 13:53:53 -0500 Original-Received: from world.peace.net ([96.39.62.75]:38884) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RoJas-0000yu-JF for guile-devel@gnu.org; Fri, 20 Jan 2012 13:53:46 -0500 Original-Received: from c-98-216-245-176.hsd1.ma.comcast.net ([98.216.245.176] helo=yeeloong) by world.peace.net with esmtpsa (TLS1.0:DHE_RSA_AES_128_CBC_SHA1:16) (Exim 4.69) (envelope-from ) id 1RoJam-000815-Ih; Fri, 20 Jan 2012 13:53:41 -0500 In-Reply-To: <87ipk6tof0.fsf@pobox.com> (Andy Wingo's message of "Fri, 20 Jan 2012 15:54:27 +0100") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.0.92 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 96.39.62.75 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.lisp.guile.devel:13601 Archived-At: Andy Wingo writes: > On Fri 20 Jan 2012 04:28, Mark H Weaver writes: > >> `seed->random-state' is poorly implemented when passed a numeric >> argument. It converts the number to a decimal string, and then >> `scm_i_init_rstate' takes over and basically adds every 8th byte >> together to form the 64-bit internal state. > > Is that what it does? > > I agree that it's a pretty bad initializer to a pretty bad PRNG, but > from what I can tell, it does use all of the bytes in the input. Sorry, my explanation was not clear. What I mean is that the result of number->string (suppose it is "12345678901234567890") gets processed like this: 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38 0x39 0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38 0x39 0x30 (those are the ASCII values of digits 0-9) and then the sum of each column is taken, yielding 64-bits. That's what I meant when I wrote "adds every 8th byte together". So yes, indeed every byte is used. > They aren't very dense bytes, entropy-wise, but there are more of > them, so I think the amount of entropy added to the seed is the same. No, adding numbers does _not_ preserve their total entropy, not even close. Suppose you start with two truly random 8-bit numbers, with all 256 values equally likely. So that's a total of 16 bits of entropy. If you add them together, you end up with a 9-bit number whose possible values are _not_ equally likely, so that's less than 9 bits of entropy. This is what's happening here. We have a 64-bit PRNG, but even if you make sure to seed it with a number that has plenty of entropy, `seed->random-state' will only preserve around 32 bits of it. That's not good. We should fix it if we possibly can. UUIDs really can't afford to have only 32 bits of entropy and still be reliable. If we cannot fix `seed->random-state', we'll have to avoid using it in UUID initialization. Mark