Re: [RFC] frandom - fast random generator module

[Matt Mackall <mpm@selenic.com>]

On Thu, Oct 16, 2003 at 12:18:25PM -0600, Andreas Dilger wrote:
> On Oct 16, 2003  12:31 -0400, Jeff Garzik wrote:
> > Andreas Dilger wrote:
> > > Actually, there are several applications of low-cost RNG inside the kernel.
> > > 
> > > For Lustre we need a low-cost RNG for generating opaque 64-bit handles in
> > > the kernel.  The use of get_random_bytes() showed up near the top of
> > > our profiles and we had to invent our own low-cost crappy PRNG instead (it's
> > > good enough for the time being, but when we start working on real security
> > > it won't be enough).
> > > 
> > > The tcp sequence numbers probably do not need to be crypto-secure (I could
> > > of course be wrong on that ;-) and with GigE or 10GigE I imagine the number
> > > of packets being sent would put a strain on the current random pool.
> > 
> > 
> > We don't need "low cost RNG" and "high cost RNG" in the same kernel. 
> > That just begs a "reduce RNG cost" solution...  I think security experts 
> > can easily come up with arguments as to why creating your own "low-cost 
> > crappy PRNG" isn't needed -- you either need crypto-secure, or you 
> > don't.  If you don't, then you could just as easily create an ascending 
> > 64-bit number for your opaque filehandle, or use a hash value, or some 
> > other solution that doesn't require an additional PRNG in the kernel.
> 
> Hmm, so every part of the kernel that doesn't need crypto-secure RNG data
> (i.e. fast and relatively unique) should implement its own hash/PRNG then?
> It isn't a matter of unbreakable crypto, but the fact that we want relatively
> unique values that will not be the same on a reboot.  Currently we do just
> as you propose for our "crappy PRNG", which is "grab 8 bytes via
> get_random_bytes and increment", but that is a little _too_ easy to guess
> (although good enough for the time being).
> 
> > For VIA CPUs, life is easy.  Use xstore insn and "You've got bytes!"  :)
> 
> As you say, we could throw away even our crappy PRNG and get better data
> with a single opcode.  So you advocate we add CPU/arch-specific code into
> our filesystem?  How about we add a wrapper around all the different
> CPU-specific RNG codes and call it the "low cost RNG" which will be faster
> _and_ give better data than any explicitly-coded PRNG. ;-)  For our needs
> at least, the asm-generic code would be on the order of maybe 15 lines of C:
> 
> #define RESEED_INTERVAL 65536
> 
> int get_fast_random_bytes(char *buf, int nbytes)
> {
> 	static int data_arr[NR_CPUS], count_arr[NR_CPUS]; /* use percpu... */
> 	int *data = &data_arr[smp_processor_id()];
> 	int *count = &count_arr[smp_processor_id()];
> 
> 	*count -= nbytes;
> 	if (*count < 0) {
> 		*count = RESEED_INTERVAL;
> 		get_random_bytes(data, sizeof(*data));
> 	}
> 		
> 	while (nbytes >= sizeof(*data)) {
> 		*(long *)buf = *data;
> 		buf += sizeof(*data);
> 		*data = *data * 1812433253L + 12345L; /* or whatever... */
> 	}
> 	memcpy(buf, data, nbytes);
> }

I don't think a get_pseudorandom_bytes() is a horrible idea. But it's
still worth the trouble to pick a more robust pseudorandom generator.
The above won't satisfy common spectral requirements. I'd rather try
to make /dev/urandom suffice first though.

-- 
Matt Mackall : http://www.selenic.com : Linux development and consulting