frandom - fast random generator module

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

Hi

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

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.

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, a userspace solution that makes use of the existing kernel random number source if needed.

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.

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

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.

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

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

[...]

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

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/

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

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

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.

Indeed you are.

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

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

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/

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/

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.

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

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

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

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

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/

Correct.

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

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/

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?

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

rngd tests for this :)

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.

In fact there are silly bugs yet to be fixed.

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

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?

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

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

________________________________________________________________
	J.W. Schultz            Pegasystems Technologies
	email address:		[email protected]

		Remember Cernan and Schmitt

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/

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.

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.

In article <[email protected]>,
Nick Piggin <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

In article <[email protected]>, Jeff Garzik <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

In article <[email protected]>, Ingo Oeser <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

In article <[email protected]>, Jeff Garzik <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Followup to:  <[email protected]>
By author:    [email protected] (bill davidsen)
In newsgroup: linux.dev.kernel

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

/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

<[email protected]> at work, <[email protected]> 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

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

In article <[email protected]>,
H. Peter Anvin <[email protected]> wrote:

| Followup to:  <[email protected]>
| By author:    [email protected] (bill davidsen)
| In newsgroup: linux.dev.kernel
| >
| > In article <[email protected]>,
| > Nick Piggin  <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

In article <[email protected]>, Helge Hafting <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

Followup to:  <[email protected]>
By author:    [email protected] (bill davidsen)
In newsgroup: linux.dev.kernel

You can also put your stuff in Thread Local Storage.

-hpa

<[email protected]> at work, <[email protected]> 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

Followup to:  <[email protected]>
By author:    [email protected] (bill davidsen)
In newsgroup: linux.dev.kernel

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

<[email protected]> at work, <[email protected]> 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

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

		Remember Cernan and Schmitt

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?

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?

Hey Kent,

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

-Dale Farnsworth

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.

Neat utility, and one I didn't know about. Thanks.

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

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?

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?

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

I'm with you there.

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.

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

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

In article <[email protected]>, Sandy Harris <[email protected]> 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 <[email protected]>
  CTO, TMR Associates, Inc
Doing interesting things with little computers since 1979.

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

- Ted

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

		Remember Cernan and Schmitt