Re: [RFC] frandom - fast random generator module

[David Mosberger-Tang <David.Mosberger@acm.org>]

>>>>> On Thu, 16 Oct 2003 18:40:12 +0200, Jeff Garzik <jgarzik@pobox.com> said:

  Jeff> We don't need "low cost RNG" and "high cost RNG" in the same
  Jeff> kernel. That just begs a "reduce RNG cost" solution...  I
  Jeff> think security experts can easily come up with arguments as to
  Jeff> why creating your own "low-cost crappy PRNG" isn't needed --
  Jeff> you either need crypto-secure, or you don't.  If you don't,
  Jeff> then you could just as easily create an ascending 64-bit
  Jeff> number for your opaque filehandle, or use a hash value, or
  Jeff> some other solution that doesn't require an additional PRNG in
  Jeff> the kernel.

I don't think that's true.  For example, the perfmon module in ia64
needs a fast pseudo-random number generator in order to randomize
sampling intervals.  It doesn't have to be a great RNG (certainly not
crypto-secure), but it does have to have reasonable properties to
avoid statistical bias.  We have tried without in-kernel RNG and the
results were unusable (e.g., resetting the sampling intervals in
user-space was far too costly and not randomizing the sampling
intervals caused horrible bias).  The RNG we settled on for now is the
Carta's (see arch/ia64/lib/carta_random.S), which is quite fast and
compact (all of 19 machine instructions).

	--david
--
David Mosberger; 35706 Runckel Lane; Fremont, CA 94536; David.Mosberger@acm.org