Subject: Re: Kernel random number generator
To: None <>
From: Rick Byers <>
List: current-users
Date: 04/30/1997 19:09:40

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
	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,

 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