Re: Improve `seed->random-state' in stable-2.0?

[Mark H Weaver]

Andy Wingo <address@hidden> writes:

> On Fri 20 Jan 2012 04:28, Mark H Weaver <address@hidden> 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