Re: random number stuff

[Sebastian Wilhelmi <seppi seppi de>]

Hi George,

I think, you should open a bugzilla bug and attach a patch. Most of the
changes, you propose seem very reasonable to me. I allready had some
people suggesting adding the 'init_by_array' functions, but didn't have
time to implement it. As for the seeding by tv.tv_sec ^ tv.tv_usec I
must admit, that I did it without diving further into the matter, so
your proposal makes sense, especially when adding 'init_by_array'.

> 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
-- 
Sebastian Wilhelmi                 |            här ovanför alla molnen
mailto:seppi seppi de              |     är himmlen så förunderligt blå
http://seppi.de                    |