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 randomness. Its probably very much worth looking at what they've done, possibly even integrating it into netbsd... David/abs abs@anim.dreamworks.com - 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: greywolf@starwolf.com > > > > This message made possible by > > Microsoft > > "I'VE GOT A BAD FEELING ABOUT THIS" > > > > ========================================================================= > Rick Byers Internet Access Worldwide > rickb@iaw.on.ca System Administrator > Welland, Ontario, Canada (905)714-1400 > http://www.iaw.on.ca/rickb/ http://www.iaw.on.ca/ > >