[RFC] frandom - fast random generator module

[RFC] frandom - fast random generator module

[Eli Billauer]

  Hello,

Frandom is the faster version of the well-known /dev/urandom random 
number generator. Not instead of, but rather as a supplement, when 
pseudorandom data is needed at high rate. Few tests so far show that 
frandom is 10-50 times faster than urandom.

The project's home page: http://frandom.sourceforge.net.

The module works on 2.2, 2.4 and 2.6 kernels. A few straightforward 
#ifdef's handle compatability (easy to remove to match common coding style).

Purpose
=======

(1) Frandom is a handy source of bulk random data.
(2) It is *not* intended for encryption and security-related applications.
(3) frandom is intended for (scientific) simulations, wiping the disk, 
stress tests on algorithms and so on.
(4) It is more of an /dev/zero than /dev/random

Quality of random numbers
=========================

(1) The module has been tested for random number quality with the 
"diehard" set of tests, and passed them all. This indicates that the 
bytes are random enough for most scientific purposes.
(2) Additional tests results are welcomed.
(3) The core of frandom is based upon RC4. frandom is exactly RC4, minus 
the XOR operation with the data. So if frandom doesn't generate good 
random numbers, I would wonder why RC4 is considered safe.
(4) The random generator is seeded with 256 bytes of the kernel's 
get_random_bytes() for every file opened on /dev/frandom. This is 
equivalent to a 2048-bit random key on RC4.
(5) I don't see frandom fit for crypto purposes, mainly because the 
module was naively written. I won't fall off my chair if it turns out to 
be crypto-safe, but I wouldn't trust it either. Not yet, anyhow.
(6) Those who read the source and feel that such a simple algorithm 
can't create good random: That's exactly the beauty of RC4: It's simple 
and it works.

frandom and the linux kernel tree
=================================

(1) Occasionally, people complain that /dev/urandom is too slow, wishing 
for something faster.
(2) Other argue that a random generator can be written in user space.
(3) I agree with both. And I use /dev/zero a lot. I know how to write a 
zero-generating application in user space.
(4) The module is small: 6kB of source code as a standalone module, and 
2.3 kB of kernel memory.

Test results and comments will be appreciated.

    Eli

Re: [RFC] frandom - fast random generator module

[Nick Piggin]

Eli Billauer wrote:

>  Hello,
>
> Frandom is the faster version of the well-known /dev/urandom random 
> number generator. Not instead of, but rather as a supplement, when 
> pseudorandom data is needed at high rate. Few tests so far show that 
> frandom is 10-50 times faster than urandom.
>

Hi

>
> Test results and comments will be appreciated.
>

Without looking at the code, why should this be done in the kernel?

Re: [RFC] frandom - fast random generator module

[Eli Billauer]

>
>
>> Frandom is the faster version of the well-known /dev/urandom random 
>> number generator. Not instead of, but rather as a supplement, when 
>> pseudorandom data is needed at high rate. Few tests so far show that 
>> frandom is 10-50 times faster than urandom.
>>
>
> Without looking at the code, why should this be done in the kernel?

I suppose you're asking why having a /dev/frandom device at all. Why not 
let everyone write their own little random generator (based upon 
well-known C functions) whenever random data is needed.

There are plenty of handy things in the kernel, that could be done in 
userspace. /dev/zero is my favourite example, but I'm sure there are 
other cases where things were put in the kernel simply because people 
found them handy. Which is a good reason, if you ask me.

Besides, it's quite easy to do something wrong with random numbers. By 
having a good source of random data, I suppose we can spare a lot of 
people the headache of getting their own user-space application right 
for the one-off thing they want to do.

But it's really a matter of taste. That's why I bring up the subject here.

   Eli

Re: [RFC] frandom - fast random generator module

[Nick Piggin]

Eli Billauer wrote:

>>
>>
>>> Frandom is the faster version of the well-known /dev/urandom random 
>>> number generator. Not instead of, but rather as a supplement, when 
>>> pseudorandom data is needed at high rate. Few tests so far show that 
>>> frandom is 10-50 times faster than urandom.
>>>
>>
>> Without looking at the code, why should this be done in the kernel?
>
>
> I suppose you're asking why having a /dev/frandom device at all. Why 
> not let everyone write their own little random generator (based upon 
> well-known C functions) whenever random data is needed.


Yes, a userspace solution that makes use of the existing kernel random
number source if needed.

>
> There are plenty of handy things in the kernel, that could be done in 
> userspace. /dev/zero is my favourite example, but I'm sure there are 
> other cases where things were put in the kernel simply because people 
> found them handy. Which is a good reason, if you ask me.


There is probably a lot in the kernel that can (and a lot that should) be
done in userspace (although I'm not sure /dev/zero is one of them).

This doesn't mean having them in the kernel is a good idea because they are
handy. I'm not passing judgement on your module though - I was just 
wondering
why it is in kernel.

>
> Besides, it's quite easy to do something wrong with random numbers. By 
> having a good source of random data, I suppose we can spare a lot of 
> people the headache of getting their own user-space application right 
> for the one-off thing they want to do.


Although we do have 2 types of random number sources in the kernel. I'm not
sure we'd want to keep adding them as the need arises. Maybe if it were 
a very
general and configurable one, but AFAIKS frandom is not.

Cheers,
Nick

Re: [RFC] frandom - fast random generator module

[Jeff Garzik]

Eli Billauer wrote:
> I suppose you're asking why having a /dev/frandom device at all. Why not 
> let everyone write their own little random generator (based upon 
> well-known C functions) whenever random data is needed.
> 
> There are plenty of handy things in the kernel, that could be done in 
> userspace. /dev/zero is my favourite example, but I'm sure there are 
> other cases where things were put in the kernel simply because people 
> found them handy. Which is a good reason, if you ask me.
> 
> Besides, it's quite easy to do something wrong with random numbers. By 
> having a good source of random data, I suppose we can spare a lot of 
> people the headache of getting their own user-space application right 
> for the one-off thing they want to do.

This is completely bogus logic.  I can use this (incorrect) argument to 
similar push for applications doing bsearch(3) or qsort(3) via a system 
call.

When the _implementation_ requires that a piece of code be in-kernel 
(for performance or security, usually), it is.

In this case, there is no such requirement.  More below.


> But it's really a matter of taste. That's why I bring up the subject here.


Processors are trending towards putting RNG on the CPU.  VIA won't be 
the last, I predict.  When generating random bits is a single 
instruction, "xstore", userspace applications _should_ be directly using 
this.  It should not be in-kernel.  And similarly, if there is no 
requirement that the kernel's entropy pool is used, the userspace 
application _should_ be where the implementation lives.

So, given that trend and also given the existing /dev/[u]random, I 
disagree completely:  /dev/frandom is the perfect example of something 
that should _not_ be in the kernel.  If you want /dev/urandom faster, 
then solve _that_ problem.  Don't try to solve a /dev/urandom problem by 
creating something totally new.

	Jeff

Re: [RFC] frandom - fast random generator module

[Eli Billauer]

Jeff Garzik wrote:

>> Besides, it's quite easy to do something wrong with random numbers. 
>> By having a good source of random data, I suppose we can spare a lot 
>> of people the headache of getting their own user-space application 
>> right for the one-off thing they want to do.
>
>
> This is completely bogus logic.  I can use this (incorrect) argument 
> to similar push for applications doing bsearch(3) or qsort(3) via a 
> system call.
>
My argument, possibly better formulated, asks the following questions:

(1) How much good will the existence of an standard /dev/frandom device 
do? Is it going to be used?
(2) How much space will it take up in the kernel tarball?
(3) How much disk space will it take after compilation?
(4) How much compilation time will it take up?
(5) How much effort is it going to be to maintain it?

(If we use it as a kernel module, we don't even have to consider the 
little kernel memory it takes up)

If I've missed some other pragmatic consideration, by all means tell me.

Now, I think that (1) wins (2)-(5). I can comment on maintaining the 
module after making it compatible with 2.2 and 2.6: It's a simple 
character device, with the most basic adaptions to it.

I actually agree that the kernel isn't "the right place" for a random 
generator. I simply think that having it there is useful, with a very 
low cost.

   Eli

Re: [RFC] frandom - fast random generator module

[Jeff Garzik]

Eli Billauer wrote:
> My argument, possibly better formulated, asks the following questions:
> 
> (1) How much good will the existence of an standard /dev/frandom device 
> do? Is it going to be used?
> (2) How much space will it take up in the kernel tarball?
> (3) How much disk space will it take after compilation?
> (4) How much compilation time will it take up?
> (5) How much effort is it going to be to maintain it?
[...]
> I actually agree that the kernel isn't "the right place" for a random 
> generator. I simply think that having it there is useful, with a very 
> low cost.


Add up 1000 low-cost items, and you can run a catalog store...  but not 
a kernel.

None of those questions 1-5 make much bit of difference:  The key 
question is "right place", and you just agreed w/ me the kernel isn't :)

	Jeff

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

On Oct 16, 2003  07:29 -0400, Jeff Garzik wrote:
> Eli Billauer wrote:
> > I suppose you're asking why having a /dev/frandom device at all. Why not 
> > let everyone write their own little random generator (based upon 
> > well-known C functions) whenever random data is needed.
> > 
> > There are plenty of handy things in the kernel, that could be done in 
> > userspace. /dev/zero is my favourite example, but I'm sure there are 
> > other cases where things were put in the kernel simply because people 
> > found them handy. Which is a good reason, if you ask me.
> 
> This is completely bogus logic.  I can use this (incorrect) argument to 
> similar push for applications doing bsearch(3) or qsort(3) via a system 
> call.
> 
> When the _implementation_ requires that a piece of code be in-kernel 
> (for performance or security, usually), it is.

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.

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

Re: [RFC] frandom - fast random generator module

[Jeff Garzik]

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.

For VIA CPUs, life is easy.  Use xstore insn and "You've got bytes!"  :)

	Jeff

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/

Re: [RFC] frandom - fast random generator module

[Richard B. Johnson]

On Thu, 16 Oct 2003, 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);
> }
>
> Cheers, Andreas
> --
> Andreas Dilger
> http://sourceforge.net/projects/ext2resize/
> http://www-mddsp.enel.ucalgary.ca/People/adilger/


Simple FAST (possibly good-enough) random number generator
that is fast enough to not screw up performance. Of course,
purests will claim that no random number generator is good
enough, but.........

This is for Intel. Other code could be generated for other
platforms. 'C' doesn't do a 'rotate' which makes 'C' methods
slow.

Various 'magic numbers' give the following periods, all better
than the rand() method:

Period = fff67290 Magic = cffd5880
Period = fffe3278 Magic = 62040ffd


#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#
#   File rnd.S            Created 04-FEB-1999        Richard B. Johnson
#
#   Simple random number generator. Based upon Alan R. Miller's
#   algorithm. Professor of Metallurgy, University of New Mexico
#   Institute of Mining and Technology, circa 1980. Published
#   In the 8080/Z-80 Assembly Language manual he wrote.
#
#   unsigned size_t rnd((size_t *) seed);
#
#   The seed can be initialized with time(&seed); on each boot.
#

MAGIC  = 0x62040ffd
INTPTR = 0x08
DIVISR = 0x0c
.section	.text
.global		rnd
.type		rnd,@function
.align	0x04
rnd:	pushl	%ebx
	movl	INTPTR(%esp), %ebx
	movl	(%ebx), %eax
	rorl	$3, %eax
	addl	$MAGIC, %eax
	movl	%eax, (%ebx)
	popl	%ebx
        ret

#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#
#	This returns a random number between 0 and one less than the
#	input divisor, i.e. n mod rand(x).
#
#	size_t modrnd((size_t *) seed, size_t divisor);
#
.type	modrnd,@function
.global	modrnd
.align	0x04

modrnd:	pushl	%ebx
	movl	INTPTR(%esp), %ebx
	movl	(%ebx), %eax
	rorl	$3, %eax
	addl	$MAGIC, %eax
	movl	%eax, (%ebx)
	xorl	%edx, %edx
	divl	DIVISR(%esp)
	movl	%edx, %eax
	popl	%ebx
        ret
.end
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
#-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-


Cheers,
Dick Johnson
Penguin : Linux version 2.4.22 on an i686 machine (797.90 BogoMips).
            Note 96.31% of all statistics are fiction.

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

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

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

On Oct 16, 2003  14:31 -0500, Matt Mackall wrote:
> On Thu, Oct 16, 2003 at 12:18:25PM -0600, Andreas Dilger wrote:
> > 	while (nbytes >= sizeof(*data)) {
> > 		*(long *)buf = *data;
> > 		buf += sizeof(*data);
> > 		*data = *data * 1812433253L + 12345L; /* or whatever... */
> > 	}
> 
> 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.

Oh, by all means the above isn't sufficient, just an example.  We have
already had 2 arch-specific assembly PRNGs that are much better than
the above that can be used if there is no HW RNG.  My point was that it
would be nice to hide the details of which PRNG and all the CPU selection
and config detection from callers in the kernel.

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

Re: [RFC] frandom - fast random generator module

[David Wagner]

Andreas Dilger  wrote:
>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).

I guess I don't understand this objection.

I'm having a hard time understanding the requirements for your PRNG.
In one place you say you just want uniqueness, but then in another
place you talk about it being easy to guess.  If all we care about is
uniqueness, why should ease of guessing matter?  I'm confused.

If all we need is uniqueness, then I don't see what's wrong with grabbing
8 bytes from get_random_bytes() and incrementing.  In particular, you
don't need frandom in this case.

If we need both uniqueness and unpredictability, then grab 8 bytes
from get_random_bytes() each time you need a new value.  This will
satisfy both your requirements.  If you truly do need something hard
to guess, nothing less than a full-strength crypto PRNG will suffice.
In particular, frandom won't help you in this case.

What am I missing?

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

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

On Oct 16, 2003  19:17 -0400, Jeff Garzik wrote:
> Andreas Dilger wrote:
> > 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 the current version of Lustre security is not a primary concern (our
customers run Lustre in very secure network environments).  We started
with get_random_bytes() but had to remove it because of the overhead.
Note that the random numbers are produced and consumed local to a single
node but are passed over the network to clients as an opaque handle,
so cross-node collisions are not a concern.

At some point in the future we may need to increase the security of such
handles, but it would be nice to not increase the CPU usage as much as
get_random_bytes() did.  Direct HW RNG would suit this perfectly.

Note that the security of these handles isn't really that critical to
the overall security model when implemented (which will be kerberos based
like AFS and DCE), but it would be nice from a warm-n-fuzzy point of view
to have something better than "last handle + N" which is what we have now.

In any case, this is getting off topic for l-k now so we should probably
end the discussion here.

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

Re: [RFC] frandom - fast random generator module

[David Wagner]

Andreas Dilger  wrote:
>For the current version of Lustre security is not a primary concern (our
>customers run Lustre in very secure network environments).  We started
>with get_random_bytes() but had to remove it because of the overhead.
>Note that the random numbers are produced and consumed local to a single
>node but are passed over the network to clients as an opaque handle,
>so cross-node collisions are not a concern.
>
>At some point in the future we may need to increase the security of such
>handles, but it would be nice to not increase the CPU usage as much as
>get_random_bytes() did.  Direct HW RNG would suit this perfectly.

I don't get it.  What do you mean by "increase the security"?
If your security relies on unpredictability, then with a non-cryptographic
PRNG, you have no security.  What am I missing?

I'm just not seeing how frandom is going to make your life any better
here.  In almost every security system I've ever looked at, either you
need a full-strength crypto PRNG, or else a simple counter is enough.

>Note that the security of these handles isn't really that critical to
>the overall security model when implemented (which will be kerberos based
>like AFS and DCE), but it would be nice from a warm-n-fuzzy point of view
>to have something better than "last handle + N" which is what we have now.

I am always suspicious of warm-n-fuzzy arguments, when it comes to
security.  Either it is security-critical, or it isn't.  And, if you
don't know whether or not it is security-critical, look out!

If the most compelling argument we can come up with for putting
frandom in the kernel is warm-n-fuzzies...  well, I think we can all
draw some conclusions from that.

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Thu, Oct 16, 2003 at 10:20:20AM -0600, Andreas Dilger wrote:
> On Oct 16, 2003  07:29 -0400, Jeff Garzik wrote:
> > Eli Billauer wrote:
> > > I suppose you're asking why having a /dev/frandom device at all. Why not 
> > > let everyone write their own little random generator (based upon 
> > > well-known C functions) whenever random data is needed.
> > > 
> > > There are plenty of handy things in the kernel, that could be done in 
> > > userspace. /dev/zero is my favourite example, but I'm sure there are 
> > > other cases where things were put in the kernel simply because people 
> > > found them handy. Which is a good reason, if you ask me.
> > 
> > This is completely bogus logic.  I can use this (incorrect) argument to 
> > similar push for applications doing bsearch(3) or qsort(3) via a system 
> > call.
> > 
> > When the _implementation_ requires that a piece of code be in-kernel 
> > (for performance or security, usually), it is.
> 
> 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).

Is this SMP? If so, how many processors? I wonder if you might be
running into some lock contention in the pool entropy transfer -
there's a lock held while mixing new samples into a given pool that
could potentially be a hit.

Beyond that, there are a couple small multiples that can be squeezed
out of the extraction path for a total of 5-10x.
 
> The tcp sequence numbers probably do not need to be crypto-secure (I could
> of course be wrong on that ;-)

Indeed you are.

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

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

On Oct 16, 2003  12:45 -0500, Matt Mackall wrote:
> On Thu, Oct 16, 2003 at 10:20:20AM -0600, Andreas Dilger wrote:
> > 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).
> 
> Is this SMP? If so, how many processors? I wonder if you might be
> running into some lock contention in the pool entropy transfer -
> there's a lock held while mixing new samples into a given pool that
> could potentially be a hit.

It was a 2-way SMP system.  We use the RNG a fair amount (enough to know
that 2 CPUs can race and return the same value from get_random_bytes() ;-)
so we had to put a spinlock around our calls to that.  Even so, oprofile
showed extract_entropy() and SHATransform() near the top of CPU users.

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

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Thu, Oct 16, 2003 at 12:38:28PM -0600, Andreas Dilger wrote:
> On Oct 16, 2003  12:45 -0500, Matt Mackall wrote:
> > On Thu, Oct 16, 2003 at 10:20:20AM -0600, Andreas Dilger wrote:
> > > 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).
> > 
> > Is this SMP? If so, how many processors? I wonder if you might be
> > running into some lock contention in the pool entropy transfer -
> > there's a lock held while mixing new samples into a given pool that
> > could potentially be a hit.
> 
> It was a 2-way SMP system.  We use the RNG a fair amount (enough to know
> that 2 CPUs can race and return the same value from get_random_bytes() ;-)

Sure this is a race and not a birthday paradox? How recent is this?
Possibly before locking was added to random.c?

> so we had to put a spinlock around our calls to that.  Even so, oprofile
> showed extract_entropy() and SHATransform() near the top of CPU users.

Ok, the lock contention would be with add_entropy_words. I've got code
that reduces calls to SHATransform for /dev/urandom, but it require
addressing the starvation issues between /dev/random and /dev/urandom first.

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

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

On Oct 16, 2003  14:08 -0500, Matt Mackall wrote:
> On Thu, Oct 16, 2003 at 12:38:28PM -0600, Andreas Dilger wrote:
> > It was a 2-way SMP system.  We use the RNG a fair amount (enough to know
> > that 2 CPUs can race and return the same value from get_random_bytes() ;-)
> 
> Sure this is a race and not a birthday paradox? How recent is this?
> Possibly before locking was added to random.c?

This is with a 2.4 kernel, which AFAIK doesn't have any locking.

> > so we had to put a spinlock around our calls to that.  Even so, oprofile
> > showed extract_entropy() and SHATransform() near the top of CPU users.
> 
> Ok, the lock contention would be with add_entropy_words. I've got code
> that reduces calls to SHATransform for /dev/urandom, but it require
> addressing the starvation issues between /dev/random and /dev/urandom first.

But there isn't an in-kernel interface to "/dev/urandom" so that doesn't
help us.

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

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Thu, Oct 16, 2003 at 02:27:06PM -0600, Andreas Dilger wrote:
> On Oct 16, 2003  14:08 -0500, Matt Mackall wrote:
> > On Thu, Oct 16, 2003 at 12:38:28PM -0600, Andreas Dilger wrote:
> > > It was a 2-way SMP system.  We use the RNG a fair amount (enough to know
> > > that 2 CPUs can race and return the same value from get_random_bytes() ;-)
> > 
> > Sure this is a race and not a birthday paradox? How recent is this?
> > Possibly before locking was added to random.c?
> 
> This is with a 2.4 kernel, which AFAIK doesn't have any locking.

Correct.
 
> > > so we had to put a spinlock around our calls to that.  Even so, oprofile
> > > showed extract_entropy() and SHATransform() near the top of CPU users.
> > 
> > Ok, the lock contention would be with add_entropy_words. I've got code
> > that reduces calls to SHATransform for /dev/urandom, but it require
> > addressing the starvation issues between /dev/random and /dev/urandom first.
> 
> But there isn't an in-kernel interface to "/dev/urandom" so that doesn't
> help us.

There is, it's called get_random_bytes. There's no interface to the
blocking version though.

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

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Thu, Oct 16, 2003 at 07:29:05AM -0400, Jeff Garzik wrote:
> 
> So, given that trend and also given the existing /dev/[u]random, I 
> disagree completely:  /dev/frandom is the perfect example of something 
> that should _not_ be in the kernel.  If you want /dev/urandom faster, 
> then solve _that_ problem.  Don't try to solve a /dev/urandom problem by 
> creating something totally new.

I have some performance fixes for /dev/urandom, but there's a fair
amount of other cleanup that has to go in first.

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

Re: [RFC] frandom - fast random generator module

[Eli Billauer]

Matt Mackall wrote:

>On Thu, Oct 16, 2003 at 07:29:05AM -0400, Jeff Garzik wrote:
>  
>
>>So, given that trend and also given the existing /dev/[u]random, I 
>>disagree completely:  /dev/frandom is the perfect example of something 
>>that should _not_ be in the kernel.  If you want /dev/urandom faster, 
>>then solve _that_ problem.  Don't try to solve a /dev/urandom problem by 
>>creating something totally new.
>>    
>>
>
>I have some performance fixes for /dev/urandom, but there's a fair
>amount of other cleanup that has to go in first.
>
... and this reminded me that I originally wanted to patch random.c, and 
change the algorithm to the faster one. To my best understanding, there 
would be no degradation in random quality, assuming I would do it 
correctly (and not being hung for the nerve to do it). But that's the 
problem: What if I got something wrong?

If a hardware device driver is buggy, you usually know about it sooner 
or later. If an RNG has a rare bug, or an architecture-dependent flaw, 
it's much harder to notice. If the RNG starts to repeat itself, you 
won't know about it, unless you happened to test exactly that data. The 
algorithm may be perfect, but a silly bug can blow it all.

So personally, I wouldn't touch the urandom code, not even the smallest 
fix. Instead, I decided to write another RNG, which doesn't interfere 
with the existing one. The only way to be confident about it, is to give 
it mileage. And that means making it available for broad use.

Which is why I originally offered frandom as a supplement, not an 
alternative.

   Eli

Re: [RFC] frandom - fast random generator module

[Jeff Garzik]

Eli Billauer wrote:
> If a hardware device driver is buggy, you usually know about it sooner 
> or later. If an RNG has a rare bug, or an architecture-dependent flaw, 
> it's much harder to notice. If the RNG starts to repeat itself, you 
> won't know about it, unless you happened to test exactly that data. The 
> algorithm may be perfect, but a silly bug can blow it all.


rngd tests for this :)

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Fri, Oct 17, 2003 at 01:03:26AM +0200, Eli Billauer wrote:
> Matt Mackall wrote:
> 
> >On Thu, Oct 16, 2003 at 07:29:05AM -0400, Jeff Garzik wrote:
> > 
> >
> >>So, given that trend and also given the existing /dev/[u]random, I 
> >>disagree completely:  /dev/frandom is the perfect example of something 
> >>that should _not_ be in the kernel.  If you want /dev/urandom faster, 
> >>then solve _that_ problem.  Don't try to solve a /dev/urandom problem by 
> >>creating something totally new.
> >>   
> >>
> >
> >I have some performance fixes for /dev/urandom, but there's a fair
> >amount of other cleanup that has to go in first.
> >
> ... and this reminded me that I originally wanted to patch random.c, and 
> change the algorithm to the faster one. To my best understanding, there 
> would be no degradation in random quality, assuming I would do it 
> correctly (and not being hung for the nerve to do it). But that's the 
> problem: What if I got something wrong?

Well you can't just drop SHA, that's needed for mixing purposes. The
designs in the literature use both a secure hash and a cipher.
 
> If a hardware device driver is buggy, you usually know about it sooner 
> or later. If an RNG has a rare bug, or an architecture-dependent flaw, 
> it's much harder to notice. If the RNG starts to repeat itself, you 
> won't know about it, unless you happened to test exactly that data. The 
> algorithm may be perfect, but a silly bug can blow it all.

In fact there are silly bugs yet to be fixed.

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

Re: [RFC] frandom - fast random generator module

[jw schultz]

On Fri, Oct 17, 2003 at 01:03:26AM +0200, Eli Billauer wrote:
> Matt Mackall wrote:
> 
> >On Thu, Oct 16, 2003 at 07:29:05AM -0400, Jeff Garzik wrote:
> > 
> >
> >>So, given that trend and also given the existing /dev/[u]random, I 
> >>disagree completely:  /dev/frandom is the perfect example of something 
> >>that should _not_ be in the kernel.  If you want /dev/urandom faster, 
> >>then solve _that_ problem.  Don't try to solve a /dev/urandom problem by 
> >>creating something totally new.
> >>   
> >>
> >
> >I have some performance fixes for /dev/urandom, but there's a fair
> >amount of other cleanup that has to go in first.
> >
> ... and this reminded me that I originally wanted to patch random.c, and 
> change the algorithm to the faster one. To my best understanding, there 
> would be no degradation in random quality, assuming I would do it 
> correctly (and not being hung for the nerve to do it). But that's the 
> problem: What if I got something wrong?
> 
> If a hardware device driver is buggy, you usually know about it sooner 
> or later. If an RNG has a rare bug, or an architecture-dependent flaw, 
> it's much harder to notice. If the RNG starts to repeat itself, you 
> won't know about it, unless you happened to test exactly that data. The 
> algorithm may be perfect, but a silly bug can blow it all.
> 
> So personally, I wouldn't touch the urandom code, not even the smallest 
> fix. Instead, I decided to write another RNG, which doesn't interfere 
> with the existing one. The only way to be confident about it, is to give 
> it mileage. And that means making it available for broad use.
> 
> Which is why I originally offered frandom as a supplement, not an 
> alternative.

Sounds like a case for having a config choice for which
urandom code to build in.

-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <3F8E8101.70009@pobox.com>, Jeff Garzik  <jgarzik@pobox.com> wrote:

| In this case, there is no such requirement.  More below.

If the result is used for crypto that is a requirement, as noted in the
original post. See below. And if it's in a shared library it's subject
to various other attempts at control or duplication of results.
| 
| 
| > But it's really a matter of taste. That's why I bring up the subject here.
| 
| 
| Processors are trending towards putting RNG on the CPU.  VIA won't be 
| the last, I predict.  When generating random bits is a single 
| instruction, "xstore", userspace applications _should_ be directly using 
| this.  It should not be in-kernel.  And similarly, if there is no 
| requirement that the kernel's entropy pool is used, the userspace 
| application _should_ be where the implementation lives.

If you are running multiple threads you may really want some independent
random numbers. Looking at this, I believe that if I open the device and
then various threads read blocks from the device, each will get
independent random numbers.

Take this as "there are benefits to having this in the kernel" and not
"this really should be in the kernel." A contribution to the discussion.

What I don't hear is results from testing, from doing this as a
procedure, etc.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <3F8E8101.70009@pobox.com>, Jeff Garzik  <jgarzik@pobox.com> wrote:
| Eli Billauer wrote:

| > Besides, it's quite easy to do something wrong with random numbers. By 
| > having a good source of random data, I suppose we can spare a lot of 
| > people the headache of getting their own user-space application right 
| > for the one-off thing they want to do.
| 
| This is completely bogus logic.  I can use this (incorrect) argument to 
| similar push for applications doing bsearch(3) or qsort(3) via a system 
| call.

Your argument is correct, but this is data generation rather than
analysis. In doing simulation it's desirable to ensure that multiple
instances of a program don't use the same numbers.

For instance, simulating user load against a server; I want the
simulation of human thinking time to be a number in the range n..m and
not to be the same for all threads. Sure I can get around that, and do,
but I wouldn't mind having a simple source of random bytes which was
quality PRNG and unique.

Again, this is not a case that this is a "must have" feature, just an
opinion that there are benefits to having such a feature which don't
apply to the cases you cited above.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[Helge Hafting]

On Tue, Oct 21, 2003 at 07:55:32PM +0000, bill davidsen wrote:

> Your argument is correct, but this is data generation rather than
> analysis. In doing simulation it's desirable to ensure that multiple
> instances of a program don't use the same numbers.
> 
> For instance, simulating user load against a server; I want the
> simulation of human thinking time to be a number in the range n..m and
> not to be the same for all threads. Sure I can get around that, and do,
> but I wouldn't mind having a simple source of random bytes which was
> quality PRNG and unique.

Each thread use the same userspace pseudo-random generator (faster
than any kernel implementation as you avoid the syscalls) and
each initialize by a single read from urandom, so they get
different series of numbers.

Helge Hafting

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <20031021212136.GA15043@hh.idb.hist.no>,
Helge Hafting  <helgehaf@aitel.hist.no> wrote:
| On Tue, Oct 21, 2003 at 07:55:32PM +0000, bill davidsen wrote:
| 
| > Your argument is correct, but this is data generation rather than
| > analysis. In doing simulation it's desirable to ensure that multiple
| > instances of a program don't use the same numbers.
| > 
| > For instance, simulating user load against a server; I want the
| > simulation of human thinking time to be a number in the range n..m and
| > not to be the same for all threads. Sure I can get around that, and do,
| > but I wouldn't mind having a simple source of random bytes which was
| > quality PRNG and unique.
| 
| Each thread use the same userspace pseudo-random generator (faster
| than any kernel implementation as you avoid the syscalls) and
| each initialize by a single read from urandom, so they get
| different series of numbers.

As noted, I do get around that... some care needs to be taken calling
random number generators from threads, since some have internal storage
in addition to the seed which can be provided by the caller.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[H. Peter Anvin]

Followup to:  <bn4bav$ji4$1@gatekeeper.tmr.com>
By author:    davidsen@tmr.com (bill davidsen)
In newsgroup: linux.dev.kernel
> 
> As noted, I do get around that... some care needs to be taken calling
> random number generators from threads, since some have internal storage
> in addition to the seed which can be provided by the caller.
> 

You can also put your stuff in Thread Local Storage.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <3F8E58A9.20005@cyberone.com.au>,
Nick Piggin  <piggin@cyberone.com.au> wrote:

| Without looking at the code, why should this be done in the kernel?

Because it's a generally useful function, /dev/random and /dev/urandom
are in the kernel, /dev/urandom is SLOW. And doing a userspace solution
is a bitch in shell scripts ;-)

Since bloat is being discussed in several threads, you may want to
propose that /dev/*random be config options in the "delete features for
size" section.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[H. Peter Anvin]

Followup to:  <bn40oa$i4q$1@gatekeeper.tmr.com>
By author:    davidsen@tmr.com (bill davidsen)
In newsgroup: linux.dev.kernel
>
> In article <3F8E58A9.20005@cyberone.com.au>,
> Nick Piggin  <piggin@cyberone.com.au> wrote:
> 
> | Without looking at the code, why should this be done in the kernel?
> 
> Because it's a generally useful function, /dev/random and /dev/urandom
> are in the kernel, /dev/urandom is SLOW. And doing a userspace solution
> is a bitch in shell scripts ;-)
> 

Bullshit.  "myrng 36 | foo" works just fine.

> Since bloat is being discussed in several threads, you may want to
> propose that /dev/*random be config options in the "delete features for
> size" section.

/dev/random and /dev/urandom are in the kernel because they are
clients of the kernel's entropy collection system, period.  There is
no other justification for their inclusion in the kernel, and using
them as motivation for sticking a pure PRNG in the kernel is daft at
best.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <bn46q9$1rv$1@cesium.transmeta.com>,
H. Peter Anvin <hpa@zytor.com> wrote:
| Followup to:  <bn40oa$i4q$1@gatekeeper.tmr.com>
| By author:    davidsen@tmr.com (bill davidsen)
| In newsgroup: linux.dev.kernel
| >
| > In article <3F8E58A9.20005@cyberone.com.au>,
| > Nick Piggin  <piggin@cyberone.com.au> wrote:
| > 
| > | Without looking at the code, why should this be done in the kernel?
| > 
| > Because it's a generally useful function, /dev/random and /dev/urandom
| > are in the kernel, /dev/urandom is SLOW. And doing a userspace solution
| > is a bitch in shell scripts ;-)
| > 
| 
| Bullshit.  "myrng 36 | foo" works just fine.

myrng?? That doesn't seem to be part of the bash I have, or any
distribution I could check, and google shows a bunch of visual basic
results rather than anything useful.

If you're suggesting that every user write their own program to
generate random numbers, then write a script to call it, that kind of
defeats the purpose of doing shell instead of writing a program, doesn't
it? Not to mention that to get entropy the user program will have to
call the devices anyway.

I think this could also fail the objective of returning unique results
in an SMP system, but that's clearly imprementation dependent.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[H. Peter Anvin]

Followup to:  <bn4aov$jf7$1@gatekeeper.tmr.com>
By author:    davidsen@tmr.com (bill davidsen)
In newsgroup: linux.dev.kernel
> | 
> | Bullshit.  "myrng 36 | foo" works just fine.
> 
> myrng?? That doesn't seem to be part of the bash I have, or any
> distribution I could check, and google shows a bunch of visual basic
> results rather than anything useful.
> 
> If you're suggesting that every user write their own program to
> generate random numbers, then write a script to call it, that kind of
> defeats the purpose of doing shell instead of writing a program, doesn't
> it? Not to mention that to get entropy the user program will have to
> call the devices anyway.
> 
> I think this could also fail the objective of returning unique results
> in an SMP system, but that's clearly imprementation dependent.
> 

No, I mean that putting a piece of code in the kernel "so it can be
accessed from shell scripts" is idiotic.  Make a binary of it and put
it in the filesystem.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
If you send me mail in HTML format I will assume it's spam.
"Unix gives you enough rope to shoot yourself in the foot."
Architectures needed: ia64 m68k mips64 ppc ppc64 s390 s390x sh v850 x86-64

Re: [RFC] frandom - fast random generator module

[jw schultz]

On Tue, Oct 21, 2003 at 06:06:02PM -0700, H. Peter Anvin wrote:
> Followup to:  <bn4aov$jf7$1@gatekeeper.tmr.com>
> By author:    davidsen@tmr.com (bill davidsen)
> In newsgroup: linux.dev.kernel
> > | 
> > | Bullshit.  "myrng 36 | foo" works just fine.
> > 
> > myrng?? That doesn't seem to be part of the bash I have, or any
> > distribution I could check, and google shows a bunch of visual basic
> > results rather than anything useful.
> > 
> > If you're suggesting that every user write their own program to
> > generate random numbers, then write a script to call it, that kind of
> > defeats the purpose of doing shell instead of writing a program, doesn't
> > it? Not to mention that to get entropy the user program will have to
> > call the devices anyway.
> > 
> > I think this could also fail the objective of returning unique results
> > in an SMP system, but that's clearly imprementation dependent.
> > 
> 
> No, I mean that putting a piece of code in the kernel "so it can be
> accessed from shell scripts" is idiotic.  Make a binary of it and put
> it in the filesystem.

Not to mention that some (bash the most common) shells have
a PRNG built-in.  As does perl and i'm sure python and any
other higher-than-shell scripting language.

I'm convinced we don't need another device.  This might
still be an alternative (build time selected) for the PRNG
in the existing /dev/urandom if someone is that concerned
with PRNG overhead.

I am curious how someone is going to use random data from a
device in a shell with the possible exception of "dd
if=/dev/urandom of=/some/file" given that they emit a binary
stream not numerals.

-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [RFC] frandom - fast random generator module

[Kent Borg]

On Tue, Oct 21, 2003 at 07:56:02PM -0700, jw schultz wrote:
> I am curious how someone is going to use random data from a device
> in a shell

I regularly use:

  $ head -c 4 /dev/random | ./mnencode

I do it when I need to generate yet another password (I finally had
the brains to realize I can't reuse passwords).  I pipe 4 (rarely
more) bytes into mnencode, a cute little program that maps any data
into pronounceable/spellable words.  (And mndecode will reverse to
process.)  So I have a lot of passwords that look like
corona-million-binary or horizon-july-egypt or single-august-pump
or...

For more information on mnencode see
<http://www.tothink.com/mnemonic/>.


-kb, the Kent who would like to see the kernel's random number
generator improved (better entropy estimation, better entropy
management, ability to supply some initial entropy early in the
boot--for embedded devices--and even speed), but the Kent who doesn't
want the kernel to be exploded into a catalogue of competing random
number generators.


P.S.  When is there going to be a good open source password safe for
Palm OS?

Re: [RFC] frandom - fast random generator module

[Dale Farnsworth]

On Wed, Oct 22, 2003 at 04:22:51PM +0000, Kent Borg wrote:
> P.S.  When is there going to be a good open source password safe for
> Palm OS?

Hey Kent,

I've been very satisfied with GNU keyring on my palm.

-Dale Farnsworth

Re: [RFC] frandom - fast random generator module

[Sandy Harris]

Kent Borg wrote:

> I regularly use:
> 
>   $ head -c 4 /dev/random | ./mnencode
> 
> ... I pipe 4 (rarely more) bytes into mnencode, ...
> ... So I have a lot of passwords that look like
> corona-million-binary or ...

That's not secure; four bytes give only 2^32 = 4 billion odd
possibilities. An enemy can easily enumerate them all as the
start of an attack.

> For more information on mnencode see
> <http://www.tothink.com/mnemonic/>.
> 
Neat utility, and one I didn't know about. Thanks.
> 
> -kb, the Kent who would like to see the kernel's random number
> generator improved

I think we'd all like to see it improved if possible. The question
is how, and why?

>(better entropy estimation, better entropy management,

I see no problems there.

The estimation is of course imperfect, but seems conservative
and reasonable.

There are only two ways I can see to manage entropy -- use a pool
as /dev/random does or just use a couple of hash contexts as
Yarrow does. Methinks the pool approach is better because it
gives a higher upper bound on entropy used. The implementation
in /dev/random looks fine to me, too.

Do you have anything specific? What do you think is wrong in
these areas, and can you suggest a fix?

> ability to supply some initial entropy early in the
> boot--for embedded devices

Once you have a file system, that's easy. Just cat or dd a
saved entropy file into /dev/random. You can play with pool
size #defines in the /dev/random code and constants in the
shellscript to adjust the details.

Do you think you need this before there's a file system? Why?
Or are you thinking of boxes that don't have a file system?
Or not writable? Not local?

> --and even speed),

I suspect that's the real issue. People report using other
things because /dev/urandom is too slow.

Can we speed up /dev/urandom? Or perhaps write a PRNG daemon?

If all we need is a library, there's an RC4-based one named
prng.c in the FreeS/WAN libraries.
http://www.freeswan.org/freeswan_snaps/CURRENT-SNAP/doc/manpage.d/ipsec_prng.3.html

Two threads discussing the desin start at:
http://lists.freeswan.org/pipermail/design/2002-March/002166.html
http://lists.freeswan.org/pipermail/design/2002-March/002207.html

> but the Kent who doesn't
> want the kernel to be exploded into a catalogue of competing random
> number generators.

I'm with you there.

Re: [RFC] frandom - fast random generator module

[Kent Borg]

On Thu, Oct 23, 2003 at 11:22:53AM +0800, Sandy Harris wrote:
> That's not secure; four bytes give only 2^32 = 4 billion odd
> possibilities. An enemy can easily enumerate them all as the
> start of an attack.

It depends upon whether the foe can get access to the encrypted/hashed
copy, and it depends upon the importance of the password.  For
example, what properties do you think my amazon.com password should
have?  Is a sufficiently motivated foe really likely to get access?
And what is the cost of that happening?  I think 32-bits of entropy is
quite reasonable for such uses.  Certainly for some uses, such as
encrypted communications, 32-bits is not enough, but have you tried
remembering a passphrase with, say, 128-bits of entropy?  It can be
done, but it is not easy.  And entering such a passphrase blind (with
no echo) is not easy either.  

I want normal people with normal notivations to be able to keep their
computers secure, and expecting a normal person to use such a long
passphrase not reasonable.  Let's keep the shadow file not world
readable, and then 32-bit passwords are secure.

> > -kb, the Kent who would like to see the kernel's random number
> > generator improved
> 
> I think we'd all like to see it improved if possible. The question
> is how, and why?

Actually, I think much of what I was thinking of has been done for
2.6.

> > ability to supply some initial entropy early in the
> > boot--for embedded devices
> 
> [...]
> 
> Do you think you need this before there's a file system? Why?
> Or are you thinking of boxes that don't have a file system?
> Or not writable? Not local?

I am thinking of little embedded boxes which can cobble up some
trickle of entropy once running (frequently from the network), and
probably find a place to store some, but at the very beginning of
their first boot, before opening networking or before it has been up
for long, at the point when they might want to generate ssh keys, it
would be nice to have ~some~ entropy.  One source would be to hash the
power-on contents of some of the DRAM.  Yes, I know DRAM does not come
up in a random state, but it does not come up in a predictable state
either; there *is* some entropy there.  Make a digest of a megabyte.
How many bits need vary from one boot to another (or even easier, from
one physical chip to another) to produce a useful lump of entropy?
Yes, I know that a warm boot might have no entropy in RAM contents,
but in the case of a warm boot there can be some saved entropy, and
mixing in known data does the entropy pool no harm.  And hashing a
megabyte of RAM is not that expensive, even on a slow CPU.

Maybe I am wrong about needing entropy so early, but if it is
collected before Linux boots, it needs to be stored somewhere, and it
would be nice to be able to free that space when Linux frees other
boot memory.


-kb

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <3F97498D.9050704@storm.ca>, Sandy Harris  <sandy@storm.ca> wrote:

| Do you think you need this before there's a file system? Why?
| Or are you thinking of boxes that don't have a file system?
| Or not writable? Not local?
| 
| > --and even speed),
| 
| I suspect that's the real issue. People report using other
| things because /dev/urandom is too slow.
| 
| Can we speed up /dev/urandom? Or perhaps write a PRNG daemon?

I know someone noted that frandom couldn't just replace urandom, but I
don't recall why. The values appear to be at least a good, the speed is
much higher, and since it's already in use, there would be no opposition
to having it, since we need to have something.

Could someone clarify why this isn't a drop-in replacement?

| If all we need is a library, there's an RC4-based one named
| prng.c in the FreeS/WAN libraries.
| http://www.freeswan.org/freeswan_snaps/CURRENT-SNAP/doc/manpage.d/ipsec_prng.3.html
| 
| Two threads discussing the desin start at:
| http://lists.freeswan.org/pipermail/design/2002-March/002166.html
| http://lists.freeswan.org/pipermail/design/2002-March/002207.html
| 
| > but the Kent who doesn't
| > want the kernel to be exploded into a catalogue of competing random
| > number generators.
| 
| I'm with you there.

No argument, but the performance of urandom is quite poor in terms of
speed and having every application generate their own number using
their own possibly badly flawed algorithm certainly qualifies as
undesirable.

-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[Theodore Ts'o]

On Fri, Oct 24, 2003 at 05:37:44PM +0000, bill davidsen wrote:
> 
> No argument, but the performance of urandom is quite poor in terms of
> speed and having every application generate their own number using
> their own possibly badly flawed algorithm certainly qualifies as
> undesirable.

That's what shared libraries are for....


						- Ted

Re: [RFC] frandom - fast random generator module

[David Wagner]

bill davidsen wrote:
>I know someone noted that frandom couldn't just replace urandom, but I
>don't recall why.

Because we don't have enough confidence in the cryptographic
security of frandom.

Re: [RFC] frandom - fast random generator module

[jw schultz]

On Fri, Oct 24, 2003 at 08:59:42PM +0000, David Wagner wrote:
> bill davidsen wrote:
> >I know someone noted that frandom couldn't just replace urandom, but I
> >don't recall why.
> 
> Because we don't have enough confidence in the cryptographic
> security of frandom.

If that is the only reason there is no need for further
discussion on this thread.  The idea of adding /dev/frandom
is i think clearly rejected.  Frandom as replacement for
urandom is a future possibility.

The frandom author or someone else who cares enough can code
a patch that provides does do a drop-in replacement for
urandom.  Preferably that patch could have a build option to
chose which PRNG to use.  People that care can try the
patch.  Everyone else can ignore it.

In the mean time the cryptogeeks can analise it, bang on it,
sprinkle it with pixie dust, or whatever until there is
enough confidence or its weaknesses are known.

If after these things are done, months from now, it can be
considered a candidate, or not, for inclusion in some of the
speciality, distribution or development trees.


-- 
________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		jw@pegasys.ws

		Remember Cernan and Schmitt

Re: [RFC] frandom - fast random generator module

[Sandy Harris]

H. Peter Anvin wrote:

> No, I mean that putting a piece of code in the kernel "so it can be
> accessed from shell scripts" is idiotic.  Make a binary of it and put
> it in the filesystem.

I posted one of those here during a previous discussion.
http://www.geocrawler.com/archives/3/35/2000/8/0/4192943/
The version I posted was first draft code, quite likely buggy,
but the general idea  was sound.

This was a while back, before the /dev/random code was
rewritten into a two-stage generator. Since my code
was to add a second stage to old /dev/random, I doubt it
is now a good idea.

If the problem is that /dev/urandom is too slow, then
we need to look at speeding it up, not adding a PRNG,
let alone one in the kernel.

Would a block cipher second stage as in Yarrow or my
example be faster than the hashing 2nd stage Ted used?
Can we use a block cipher without legal hassles? Is
there some third choice? A faster hash?

Re: [RFC] frandom - fast random generator module

[Ingo Oeser]

On Thursday 16 October 2003 10:22, Eli Billauer wrote:
> (3) I agree with both. And I use /dev/zero a lot. I know how to write a
> zero-generating application in user space.

There is a good reason for this: You can implement pages containing only
zeroes very efficiently in the kernel. You can map pages containing only
zeroes to a single physical page in the kernel (the ZERO_PAGE). You can
ignore the refcounting on this page and save precious cache flushes and
much more by doing this in the kernel.

Compare an application with memset() and mmaping of /dev/zero in
multiple processes, writing to only some of these pages later.

> (4) The module is small: 6kB of source code as a standalone module, and
> 2.3 kB of kernel memory.

That's a price worth as an "default to off" option. We have much more
seldom used stuff in the kernel and maintain it, which is a bigger mess
than this.

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <200310161245.59939.ioe-lkml@rameria.de>,
Ingo Oeser  <ioe-lkml@rameria.de> wrote:
| On Thursday 16 October 2003 10:22, Eli Billauer wrote:

| > (4) The module is small: 6kB of source code as a standalone module, and
| > 2.3 kB of kernel memory.
| 
| That's a price worth as an "default to off" option. We have much more
| seldom used stuff in the kernel and maintain it, which is a bigger mess
| than this.

Yes, and it could be disabled to take no resources, unlike the Athlon
pagefault bugfix, which is forced in all kernels instead of just those
destined for those which need the fix.
-- 
bill davidsen <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[David Mosberger-Tang]

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

Re: [RFC] frandom - fast random generator module

[Eli Billauer]

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

Re: [RFC] frandom - fast random generator module

[Andreas Dilger]

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

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

Re: [RFC] frandom - fast random generator module

[bill davidsen]

In article <20031016144205.I7000@schatzie.adilger.int>,
Andreas Dilger  <adilger@clusterfs.com> 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 <davidsen@tmr.com>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Re: [RFC] frandom - fast random generator module

[Matt Mackall]

On Thu, Oct 16, 2003 at 09:28:58PM +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.
> 
> * 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.

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