frandom - fast random generator module

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; [email protected]

Allow me to supply a couple facts about frandom:

* It's not a "crappy" RNG. Its RC4 origins and the fact, that it has passed tests indicate the opposite. A fast RNG doesn't necessarily mean a bad one. I doubt if any test will tell the difference between frandom and any other good RNG. You're most welcome to try.

* Frandom is written completely in C. On an i686, gcc compiles the critical part to 26 assembly instructions per byte, and I doubt if any hand assembly would help significantly. The algorithms is clean and simple, and the compiler performs well with it.

Eli

The "crappy RNG" being referred to is just some code we implemented to give us somewhat unique numbers instead of sucking CPU.

This is still more expensive than a hw RNG (which will be about 1 ins per 4 bytes), so it would be nice to make this arch-specific if possible (runtime and compile time).

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

In article <[email protected]>, Andreas Dilger <[email protected]> wrote:

| On Oct 16, 2003  21:28 +0200, Eli Billauer wrote:
| > Allow me to supply a couple facts about frandom:
| > 
| > * It's not a "crappy" RNG. Its RC4 origins and the fact, that it has 
| > passed tests indicate the opposite. A fast RNG doesn't necessarily mean 
| > a bad one. I doubt if any test will tell the difference between frandom 
| > and any other good RNG. You're most welcome to try.
| 
| The "crappy RNG" being referred to is just some code we implemented to
| give us somewhat unique numbers instead of sucking CPU.
| 
| > * Frandom is written completely in C. On an i686, gcc compiles the 
| > critical part to 26 assembly instructions per byte, and I doubt if any 
| > hand assembly would help significantly. The algorithms is clean and 
| > simple, and the compiler performs well with it.
| 
| This is still more expensive than a hw RNG (which will be about 1 ins
| per 4 bytes), so it would be nice to make this arch-specific if possible
| (runtime and compile time).

Clearly that's true inside the kernel. Although the speed will be somewhat less because you may not always need four bytes, no?

The benefit of a random number source user programs can use, which is going to avoid giving the same number to multiple processes or threads is significant for simulations and sampling. It doesn't matter if this is done with frandom or speeding urandom to similar speed, other than that some people will protest a change in urandom, even a change for the better.

bill davidsen <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

The output hash for /dev/random would use RC4 or the like except for historical political reasons. I'm hoping to move it in that direction, but adding yet another cryptographic algorithm outside cryptoapi is a step in the wrong direction right now.

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