Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

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);
}

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/