Re: random number stuff

[George <jirka 5z com>]

On Thu, Sep 18, 2003 at 06:58:44AM -0400, Owen Taylor wrote:
> I think you mistyped the address gtk-devel-list gnome org 

Laying the hint pretty thick ... :)  It was 3 or so in the morning and plus I
procmail gtk-devel-list to /dev/null these days.  CCing there then ...

Note that the solution to #1 provides 32 (well 31.97) bits of entropy if you
can't guess seed time to within 68 minutes.  With the old method you get 32
bits of entropy if you can't quite guess the century, that is beyond 11 days
it's the same as using time (NULL) as seed

If done with the init_by_array, we actually get more then 32 bits of entropy
as we cross the 68 minitues of uncertainty.

In the /dev/urandom case, if init_by_array is implemented, then I'd suggest
using about 4 words from /dev/urandom.  That gets us 128 bits of entropy.
Since AFAIK the kernel does md5 here, it really works in 128 bit chunks
anyway.  It shouldn't be really much slower then reading 1 word, and it's
done just on seeding.

It may also be of interest to be able to 'copy' a random number generator
with a function like g_rand_copy.  The copy would then go through the same
sequence.

George

[Note again that I pipe gtk-devel-list to /dev/null these days, so CC me.]

> On Thu, 2003-09-18 at 06:19, George wrote:
> > I can't sleep so I was reading up on the MT random number generator (yeah I
> > know it's an obscession, that's why I'm getting a PhD).  Also looking through
> > the grand.c code.  And I have two suggestions:
> > 
> > 1) In case /dev/urandom doesn't exist, the code uses:
> >     tv.tv_sec ^ tv.tv_usec
> >    however that is kind of crap it turns out.  Guessing the microseconds is
> >    really kind of next to impossible so we get almost 20 bits of entropy from
> >    there.  However, then looking at seconds, the high order bits are quite
> >    uninteresting, but the lower order bits just get xored (and so effectively
> >    entropy is lost).  So if I can guess seed time to within 1 million
> >    seconds I am in the same position as if I can guess the seed time
> >    precisely to the second.  That is about 11 days.  Which is I suppose quite
> >    guessable.  Then I only still have 20 bits of entropy.  Also if one
> >    would use this for running some tests they get only 20 bits of seed
> >    really.  A simple fix is to shift the seconds and use the lower order
> >    bits of seconds in the space where the usec is always 0, that is:
> >     (tv.tv_sec << 20) ^ tv.tv_usec
> >    This way, each second adds to entropy rather then only starting to
> >    add after 11 days.  Could also be done this way:
> >     (tv.tv_sec << 20) ^ tv.tv_usec ^ tv.tv_sec
> >    Though we're only losing about 0.07 bits of info by the first method
> >    so I think that's quite ok.
> > 
> > 2) the MT random number generator can in fact have a seed space of 622
> >    words, but grand only allows a 32bit seed.  I would suggest using
> >    the function from their new implementation init_by_array.  This
> >    allows arbitrary size seeds (up to N obviously).  Note that if
> >    we allow this then the above problem can be solved by using some
> >    code like:
> > 
> >      guint32 seed[2] = { tv.tv_sec , tv.tv_usec };
> >      g_rand_init_by_array (rnd, seed, 2);
> > 
> >    Besides giving larger seed space, this gives the ability to combine
> >    several low entropy numbers in a safe way for the seed.  That is
> >    avoids problems like #1.
> > 
> >    Code is at:
> >      http://www.math.keio.ac.jp/matumoto/CODES/MT2002/mt19937ar.c
> > 
> >    I can provide a patch to glib for this ...
> > 
> > George

-- 
George <jirka 5z com>
   I finally figured out the only reason to be alive is to enjoy it.
                       -- Rita Mae Brown