Subject: Re: Kernel random number generator
To: Rick Byers <email@example.com>
From: David Brownlee <firstname.lastname@example.org>
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:
> 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: email@example.com
> > This message made possible by
> > Microsoft
> > "I'VE GOT A BAD FEELING ABOUT THIS"
> Rick Byers Internet Access Worldwide
> firstname.lastname@example.org System Administrator
> Welland, Ontario, Canada (905)714-1400
> http://www.iaw.on.ca/rickb/ http://www.iaw.on.ca/