Re: [RFC] frandom - fast random generator module

[Jeff Garzik]

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).

If you care at all about it being easy to guess, then why bother with 
the crappy PRNG?  :)

If you _don't_ care about the numbers being easy to guess -- i.e. you 
simply want unique values -- then it doesn't seem like a PRNG is needed 
at all.  With a random number you have to deal with collisions between 
nodes choosing the same number coincidentally _anyway_, so why not just 
use sequence numbers?


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

Let's see what pans out...  It sounds like the random driver has 
untapped performance potential, and could be made more SMP-friendly...

FWIW, for h/w RNGs, I prefer the model where a userspace daemon feeds 
the kernel entropy pool.  On most days, you will have full entropy 
buffers because 'xstore' generates random data much faster than most 
apps consume it.  But the userspace daemon can also throttle (nice to 
PM), validate the h/w RNG (ugly and costly to do in-kernel), and utilize 
a few processor-dependent features that increase xstore's throughput in 
userspace.

Then the problem simply becomes one of making sure you can copy entropy 
out of kernel memory buffers efficiently.

	Jeff



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