Subject: Re: Kernel random number generator
To: Rick Byers <>
From: David Brownlee <>
List: current-users
Date: 04/30/1997 18:20:30
	The openbsd people have done some interesting things with putting
	random number generators into the kernel - using the
	unpredicability of kernbel events to provide a 'pool' of

	Its probably very much worth looking at what they've done,
	possibly even integrating it into netbsd...


    		       - Oakwood apartments -
     - $1300 a month and people steal your laundry - What a place -

On Wed, 30 Apr 1997, Rick Byers wrote:

> James,
> I thought about using crypt as well, but decided that it wasn't really the
> random number generator (or crypt) that was the problem, but the initial
> seed.  I.E. the possible end result is still dependant on the resolution
> of the clock.  Now given that a certain function (crypt in this example)
> won't take the exact same amount of time, it might work.  That is where
> the resolution of the timer comes in.  If the timer resolution is so bad
> that the time for crypt to run can be predicted within the accuracy of the
> clock, then it's no good.  Even if someone could calculate 100 possible
> values for the time difference, then it's still not good enough.  You
> could loop that n times, and end up with 100^n possible values, but I'm
> sure there would be other ways to narrow down the possibilities (i.e.
> subsequent calls to crypt are going to be very close in timing to other
> recent calls to crypt due to a similar load on the system at that time).
> You do have a good idea about the conditions though, I'm not sure if the
> crypt call helps though.  Crypt just produces a different values based on
> it's input, but given the same imput, it creates the same value.  In this
> application, it doesn't matter WHAT the value is, just how many
> possibilities it has, and the number of possibile outputs of crypt is the
> number of possible inputs you give it.  For example, if tv_usec can only
> have 100 possible values (100ths of a second as Perry suggested), then
> you've only got 200 possible outcomes.  Obviously the more you loop it,
> the more possible outcomes, but it should be possible to predict
> approximatly how long each loop takes to run.  If the loop runs too
> quickly to get an accurate prediction, then it's faster than the system
> clock anyway and you'll end up with a predictable (same) value for
> tv_usec.  Can random be back-traced? I mean, can a value returned by
> random be used to find the initial seed?  If so, then I guess crypt would
> be a much better idea.  What do you think of something like this:
> seed = timer
> do
> 	seed = seed * timer
> while !(seed % 100)
> I'm just wondering if the gettimeofday call inside the loop will introduce
> enough randomness or not?  I'm also not sure about the probabilities
> surrouding multiplication.  I.E., if seed is initially even, then it will
> be even regardless of what timer is.  You mentioned xoring though, thats a
> great idea, that should help a lot because any bit of the output of xor
> can't be determined without knowing BOTH input bits.
> I also can have the program wait for the user to press enter.  That's the
> concept pgp uses to generate it's random number, you have to type 100 keys
> or so and it measures the timing between your keystrokes for the seed.  I
> just don't want someone to have to press a key 100 times before it will
> output the result (since we will be using it a lot).
> I'll go change my * to s - Thanks,
> 				Rick
>  On Wed, 30 Apr 1997, Graham, James wrote:
> > You _could_ do a random number generator triggered by cycling stuff
> > through
> > the crypt() call once, converting from the base-64 string into binary,
> > then
> > using that number to seed your generator.
> > 
> > There's an AWFUL lot of possibility there, especially if you grab
> > tv_usec,
> > even if there are a limited number of possible values.
> > 
> > Picture this one:
> > 
> > grab tv_usec;
> > translate to ascii;
> > run thru crypt();
> > translate result from base-64 to binary;
> > grab tv_usec again;
> > even-result:	run thru compression
> > odd-result:	run thru ebcdic encoding
> > convert result to a binary number;
> > seed your generator.
> > 
> > Convoluted, but if you throw several layers of uncertainty in there
> > (maybe repeat several times of grabbing the tv_usec, filtering it
> > thru crypt(), xoring the value and running it thru crypt() again),
> > especially ones which  have more than one possible return value,
> > you have a pretty-close-to-perfect implementation.
> > 
> > It would be really cool, but not strictly necessary, to have a
> > random number generator in the kernel.
> > 
> > /* note for crypt():  I mean the DES crypt or other routine
> >    which does a ratio of input:output better than 1:1024 */
> > 
> > Reply-To:
> > 
> > This message made possible by
> > Microsoft
> > 
> =========================================================================
> Rick Byers                                      Internet Access Worldwide
>                                      System Administrator
> Welland, Ontario, Canada                                    (905)714-1400