Continuing /dev/random problems with 2.4

Continuing /dev/random problems with 2.4

[Ken Brownfield]

Since I've switched to using 2.4 in situations where /dev/random is
heavily used, I've been seeing more and more of the running issue with
/dev/random.

After a few days of occasional use from sshd and our own cryptographic
purposes, we're seeing entropy_avail go to 0 and requests to /dev/random
block.  The processes that block remain killable, but entropy no longer
appears until a reboot is performed.

Robert Love did some /dev/random maintenance a while back, and his
netdev patches are essential for low disk-activity systems.  While his
patches have helped the situation greatly, it appears that there is
something in the random code that can cause extraction of entropy to
permanently exhaust the pool.  Some kind of issue when entropy is near
zero at the time of a read?

In any case, this is becoming a major pain throughout the many systems
and distibution mechanisms that we're running and at this point I think
it really should be looked at.

I will try to take a look at the code at some point, but I'd really
appreciate it if someone with some previous knowledge of this area of
the kernel could take a look.

This problem has occurred on many many different SMP configurations
(varying procs, motherboards, SCSI, IDE, RAM, etc) for all of the 2.4
series, although Robert's much appreciated fixes a few revs ago helped
quite a bit.  Haven't been able to test on UP, since we're exclusively
SMP.

/dev/urandom is indeed an option for _some_ situations, but I'd rather
fix the problem for the good of everyone else, and I'd like to reap the
benefits of /dev/random vs. /dev/urandom.

Thanks much,
-- 
Ken.
brownfld@irridia.com

Re: Continuing /dev/random problems with 2.4

[Andreas Dilger]

On Feb 01, 2002  03:17 -0600, Ken Brownfield wrote:
> Since I've switched to using 2.4 in situations where /dev/random is
> heavily used, I've been seeing more and more of the running issue with
> /dev/random.
> 
> After a few days of occasional use from sshd and our own cryptographic
> purposes, we're seeing entropy_avail go to 0 and requests to /dev/random
> block.  The processes that block remain killable, but entropy no longer
> appears until a reboot is performed.

What specific kernel version are you using?  There were some bugs where
the entropy was /32 on each usage that I fixed.

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

Re: Continuing /dev/random problems with 2.4

[Robert Love]

On Fri, 2002-02-01 at 04:17, Ken Brownfield wrote:

> Robert Love did some /dev/random maintenance a while back, and his
> netdev patches are essential for low disk-activity systems.  While his
> patches have helped the situation greatly, it appears that there is
> something in the random code that can cause extraction of entropy to
> permanently exhaust the pool.  Some kind of issue when entropy is near
> zero at the time of a read?

Most of the useful fixes actually came in a large update from Andreas
Dilger.  Perhaps he would have some insight, too.

Exhausting entropy to zero under high use is not uncommon (that is a
motivation for my netdev-random patch).  What boggles me is why it does
not regenerate?

	Robert

Re: Continuing /dev/random problems with 2.4

[Ken Brownfield]

On Fri, Feb 01, 2002 at 09:36:57AM -0700, Andreas Dilger wrote:
| On Feb 01, 2002  03:17 -0600, Ken Brownfield wrote:
| > Since I've switched to using 2.4 in situations where /dev/random is
| > heavily used, I've been seeing more and more of the running issue with
| > /dev/random.
| > 
| > After a few days of occasional use from sshd and our own cryptographic
| > purposes, we're seeing entropy_avail go to 0 and requests to /dev/random
| > block.  The processes that block remain killable, but entropy no longer
| > appears until a reboot is performed.
| 
| What specific kernel version are you using?  There were some bugs where
| the entropy was /32 on each usage that I fixed.

Yes, which was at least partially Robert's contribution.

I'm seeing this on 2.4.16 and 2.4.18-preN.  It's been there since the
beginning AFAIK.
-- 
Ken.
brownfld@irridia.com


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

Re: Continuing /dev/random problems with 2.4

[Ken Brownfield]

On Fri, Feb 01, 2002 at 11:53:20AM -0500, Robert Love wrote:
| On Fri, 2002-02-01 at 04:17, Ken Brownfield wrote:
| Most of the useful fixes actually came in a large update from Andreas
| Dilger.  Perhaps he would have some insight, too.

Ah, my apoligies then.

| Exhausting entropy to zero under high use is not uncommon (that is a
| motivation for my netdev-random patch).  What boggles me is why it does
| not regenerate?

Yeah -- slow entropy is "acceptable", but blocking until a reboot is rather unacceptable. ;)

Thx much,
-- 
Ken.
brownfld@irridia.com

| 
| 	Robert
| 
| -
| To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
| the body of a message to majordomo@vger.kernel.org
| More majordomo info at  http://vger.kernel.org/majordomo-info.html
| Please read the FAQ at  http://www.tux.org/lkml/

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Followup to:  <1012582401.813.1.camel@phantasy>
By author:    Robert Love <rml@tech9.net>
In newsgroup: linux.dev.kernel
>
> On Fri, 2002-02-01 at 04:17, Ken Brownfield wrote:
> 
> > Robert Love did some /dev/random maintenance a while back, and his
> > netdev patches are essential for low disk-activity systems.  While his
> > patches have helped the situation greatly, it appears that there is
> > something in the random code that can cause extraction of entropy to
> > permanently exhaust the pool.  Some kind of issue when entropy is near
> > zero at the time of a read?
> 
> Most of the useful fixes actually came in a large update from Andreas
> Dilger.  Perhaps he would have some insight, too.
> 
> Exhausting entropy to zero under high use is not uncommon (that is a
> motivation for my netdev-random patch).  What boggles me is why it does
> not regenerate?
> 

The kernel itself sometimes need randomness, and probably manages to
keep the enthropy pool completely drained.  Remember, /dev/random
means "don't give me anything unless you can promise it's fresh
entrophy."

Anything that is meant to be a server really pretty much needs an
enthropy generator these days.  We really should push vendors to
provide it (together with serial console firmware and other "well,
duh" things rackmount servers should have as a matter of course.)

Once you have software to assist you, meaning that you don't require
that every bit stepping off the wire is truly random, just a
predictable minimum, then building an RNG is a trivial number of
components -- although some care has to be taken in their assembly.
This means, IMO, that we should push on server motherboard
manufacturers more so than, for example, chipsets: although
integration tend to improve pervasiveness, ICs are awfully noisy
beasts.

	-hpa
-- 
<hpa@transmeta.com> at work, <hpa@zytor.com> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>

Re: Continuing /dev/random problems with 2.4

[Ken Brownfield]

On Fri, Feb 01, 2002 at 10:40:35AM -0800, H. Peter Anvin wrote:
[...]
| > Exhausting entropy to zero under high use is not uncommon (that is a
| > motivation for my netdev-random patch).  What boggles me is why it does
| > not regenerate?
[...]
| Anything that is meant to be a server really pretty much needs an
| enthropy generator these days.  We really should push vendors to
| provide it (together with serial console firmware and other "well,
| duh" things rackmount servers should have as a matter of course.)

Yes, in fact we do have entropy generators in some cases, especially on
Solaris.  I think this is a very good idea -- it would be extremely nice
to see this especially since SO much more is dependent upon entropy
these days.  More than about 7 years ago I would have thought entropy
was a nethack clone.

Of course, in my case deleting the /dev/random character node still
doesn't allow entropy to drain in (after at least a month) so I suspect
the kernel's entropy generation would be sufficient if it didn't
artificially stall or drain from within the kernel.

Thanks much,
-- 
Ken.
brownfld@irridia.com


| 
| 	-hpa
| -- 
| <hpa@transmeta.com> at work, <hpa@zytor.com> in private!
| "Unix gives you enough rope to shoot yourself in the foot."
| http://www.zytor.com/~hpa/puzzle.txt	<amsp@zytor.com>
| -
| To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
| the body of a message to majordomo@vger.kernel.org
| More majordomo info at  http://vger.kernel.org/majordomo-info.html
| Please read the FAQ at  http://www.tux.org/lkml/

Re: Continuing /dev/random problems with 2.4

[Andreas Dilger]

On Feb 01, 2002  10:40 -0800, H. Peter Anvin wrote:
> Anything that is meant to be a server really pretty much needs an
> enthropy generator these days.  We really should push vendors to
> provide it (together with serial console firmware and other "well,
> duh" things rackmount servers should have as a matter of course.)

Well, all of the Intel i8XX chipsets have a harware RNG I believe.
There are even tools available to use them (gkernel.sf.net), but
it is not fed into the /dev/random entropy pool by default, and I
doubt that these tools are available with any distro.  At the
time, this decision was made because it is hard to determine what
the actual entropy of this device is.

Maybe, i8XX hardware RNG should feed the /dev/random entropy pool
directly if you enable the chipset support (with an option to turn
it off if you want to use the user-space tools or a separate RNG),
so that people get the benefits of the h/w RNG without having to
install another tool (which they won't know about)?

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

Re: Continuing /dev/random problems with 2.4

[Robert Love]

On Fri, 2002-02-01 at 14:38, Ken Brownfield wrote:

> Of course, in my case deleting the /dev/random character node still
> doesn't allow entropy to drain in (after at least a month) so I suspect
> the kernel's entropy generation would be sufficient if it didn't
> artificially stall or drain from within the kernel.

Agreed, I suspect you do indeed have a problem.

What is the output of `/proc/sys/kernel/random/entropy_avail' when
programs are stalled?  Is it actually 0?

Can you see if any programs are perhaps draining entropy in the
background?  See what has /dev/[u]random open ... note even /dev/urandom
uses entropy, its the same as /dev/random, except it doesn't care when
the entropy estimate is 0.

	Robert Love

Re: Continuing /dev/random problems with 2.4

[Ken Brownfield]

On Fri, Feb 01, 2002 at 02:50:31PM -0500, Robert Love wrote:
| What is the output of `/proc/sys/kernel/random/entropy_avail' when
| programs are stalled?  Is it actually 0?

Yep, and it never raises above that -- it doesn't jump around even after
a month.

| Can you see if any programs are perhaps draining entropy in the
| background?  See what has /dev/[u]random open ... note even /dev/urandom
| uses entropy, its the same as /dev/random, except it doesn't care when
| the entropy estimate is 0.

I've scanned /proc to verify that all PIDs do not have an FD open to
/dev/random.  This was my first guess when this started -- some
developer was draining entropy in a while(1) loop.  I believe I went so
far as to go to runlevel 1 with nothing but sh and kernel threads.

That may not be comprehensive, so I'm open to other diagnostic tips.
And yes, /dev/urandom does continue to work, as expected.

Thanks!
-- 
Ken.
brownfld@irridia.com

| 	Robert Love

Re: Continuing /dev/random problems with 2.4

[Andreas Dilger]

On Feb 01, 2002  13:38 -0600, Ken Brownfield wrote:
> Of course, in my case deleting the /dev/random character node still
> doesn't allow entropy to drain in (after at least a month) so I suspect
> the kernel's entropy generation would be sufficient if it didn't
> artificially stall or drain from within the kernel.

Hmm, you may also need to delete /dev/urandom too.  Reading from
/dev/urandom will also deplete the entropy pool just as much as
reading from /dev/random.  The only difference is that /dev/random
will block if there aren't enough bits as requested, while reads
from /dev/urandom will happily continue to return data which isn't
"backed" by any entropy.

You could also enable debugging in drivers/char/random.c to see what
is going on (it may be very verbose).  You could even change the one
message in extract_entropy() to include the command name, like:

	DEBUG_ENT("%s has %d bits, %s wants %d bits\n",
		  r == sec_random_state ? "secondary" :
		  r == random_state ? "primary" : "unknown",
		  current->comm, r->entropy_bits, nbytes * 8);

(not sure of exact usage for current->comm, but you could use ->pid
instead).


Note that even traffic over the network will deplete your entropy
pool, because it is using secure_tcp_sequence_number() and secure_ip_id().
Also, using SYN cookies appears to increase the amount of entropy used.

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

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Andreas Dilger wrote:

> 
> Maybe, i8XX hardware RNG should feed the /dev/random entropy pool
> directly if you enable the chipset support (with an option to turn
> it off if you want to use the user-space tools or a separate RNG),
> so that people get the benefits of the h/w RNG without having to
> install another tool (which they won't know about)?
> 


"Let's put it in the kernel because people are too stupid to install it
otherwise"?

No thank you.

	-hpa

Re: Continuing /dev/random problems with 2.4

[Ken Brownfield]

On Fri, Feb 01, 2002 at 12:57:03PM -0700, Andreas Dilger wrote:
| Hmm, you may also need to delete /dev/urandom too.  Reading from
| /dev/urandom will also deplete the entropy pool just as much as
| reading from /dev/random.  The only difference is that /dev/random
| will block if there aren't enough bits as requested, while reads
| from /dev/urandom will happily continue to return data which isn't
| "backed" by any entropy.

*forehead smack*  Very good point.

| You could also enable debugging in drivers/char/random.c to see what
| is going on (it may be very verbose).  You could even change the one
| message in extract_entropy() to include the command name, like:
| 
| 	DEBUG_ENT("%s has %d bits, %s wants %d bits\n",
| 		  r == sec_random_state ? "secondary" :
| 		  r == random_state ? "primary" : "unknown",
| 		  current->comm, r->entropy_bits, nbytes * 8);
|
| (not sure of exact usage for current->comm, but you could use ->pid
| instead).

I'll add this and see what pops up, thanks!

| Note that even traffic over the network will deplete your entropy
| pool, because it is using secure_tcp_sequence_number() and secure_ip_id().
| Also, using SYN cookies appears to increase the amount of entropy used.

Very good to know.  The machines that this has happened on don't all
have tcp_syncookies enabled, and some have very little network traffic,
so at first glance those don't seem to be involved.

Thanks,
-- 
Ken.
brownfld@irridia.com

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

Re: Continuing /dev/random problems with 2.4

[Peter Monta]

> Anything that is meant to be a server really pretty much needs an
> enthropy generator these days.

Many motherboards have on-board sound.  Why not turn the mic
gain all the way up and use the noise---surely there will be
a few bits' worth?

Perhaps there ought to be a way to give bits to the kernel's
/dev/random input hopper from user space.

Cheers,
Peter Monta

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Peter Monta wrote:

>>Anything that is meant to be a server really pretty much needs an
>>enthropy generator these days.
>>
> 
> Many motherboards have on-board sound.  Why not turn the mic
> gain all the way up and use the noise---surely there will be
> a few bits' worth?
> 
> Perhaps there ought to be a way to give bits to the kernel's
> /dev/random input hopper from user space.
> 


There already is.  If I'm not completely mistaken, just write the raw data
to /dev/random, then there is an ioctl() saying "add N bits to the
entrophy counter."

	-hpa

Re: Continuing /dev/random problems with 2.4

[Jeff Garzik]

On Fri, Feb 01, 2002 at 12:12:37PM -0800, H. Peter Anvin wrote:
> Andreas Dilger wrote:
> > Maybe, i8XX hardware RNG should feed the /dev/random entropy pool
> > directly if you enable the chipset support (with an option to turn
> > it off if you want to use the user-space tools or a separate RNG),
> > so that people get the benefits of the h/w RNG without having to
> > install another tool (which they won't know about)?

> "Let's put it in the kernel because people are too stupid to install it
> otherwise"?

There actually used to be a timer function in i810_rng driver which
directly added entropy to the pool.  batch_entropy_store was exported in
order to do this.

However, that was just the quick and dirty way.  You DO NOT want to do
this in the kernel, because one must perform fitness tests on the random
data before adding it to the kernel's /dev/[u]random entropy pool.
Putting proper fitness tests into the kernel is just plain code bloat.

Therefore, RNG drivers -must- deal with a userspace agent in order to be
properly used, and properly secure.

The userspace tools for i810 RNG specifically are available at the
website URL mentioned in the source code.  So if somebody cannot find
them, feel free to laugh.

	Jeff

Re: Continuing /dev/random problems with 2.4

[Jeff Garzik]

On Fri, Feb 01, 2002 at 12:23:34PM -0800, Peter Monta wrote:
> > Anything that is meant to be a server really pretty much needs an
> > enthropy generator these days.
> 
> Many motherboards have on-board sound.  Why not turn the mic
> gain all the way up and use the noise---surely there will be
> a few bits' worth?

Even if you think you have a good true source of random noise, you need
to run good fitness tests on the data to ensure it's truly random.

	Jeff

Re: Continuing /dev/random problems with 2.4

[Jeff Garzik]

On Fri, Feb 01, 2002 at 12:27:14PM -0800, H. Peter Anvin wrote:
> Peter Monta wrote:
> 
> >>Anything that is meant to be a server really pretty much needs an
> >>enthropy generator these days.
> >>
> > 
> > Many motherboards have on-board sound.  Why not turn the mic
> > gain all the way up and use the noise---surely there will be
> > a few bits' worth?
> > 
> > Perhaps there ought to be a way to give bits to the kernel's
> > /dev/random input hopper from user space.
> > 
> 
> 
> There already is.  If I'm not completely mistaken, just write the raw data
> to /dev/random, then there is an ioctl() saying "add N bits to the
> entrophy counter."

Yep.  The i810 RNG userspace daemon, rngd, does this.  It reads from
i810 RNG data from /dev/intel_rng, tests the data, and injects it back
into /dev/random with the specified entropy bits.  (zero bits by default,
because we default to paranoia mode of not trusting, but that can and is
usually increased)

	Jeff

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Jeff Garzik wrote:

> 
> Even if you think you have a good true source of random noise, you need
> to run good fitness tests on the data to ensure it's truly random.
> 


The i810 user-space code already should do this, though, right?  Could one
simply point the existing rngd at /dev/dsp instead?

	-hpa

Re: Continuing /dev/random problems with 2.4

[Jeff Garzik]

On Fri, Feb 01, 2002 at 12:40:43PM -0800, H. Peter Anvin wrote:
> Jeff Garzik wrote:
> > Even if you think you have a good true source of random noise, you need
> > to run good fitness tests on the data to ensure it's truly random.

> The i810 user-space code already should do this, though, right?  Could one
> simply point the existing rngd at /dev/dsp instead?

Theoretically yes.  rngd is tuned right now for i810's byte-at-a-time
device, but it would be simple to make the code more generic, or simply
use a faster device in a slower byte-at-a-time mode.

	Jeff

Re: Continuing /dev/random problems with 2.4

[Peter Monta]

> > > Anything that is meant to be a server really pretty much needs an
> > > enthropy generator these days.
> > 
> > Many motherboards have on-board sound.  Why not turn the mic
> > gain all the way up and use the noise---surely there will be
> > a few bits' worth?
>
> Even if you think you have a good true source of random noise, you need
> to run good fitness tests on the data to ensure it's truly random.

Well, yes and no.  What you really need is a conservative estimate
of how much entropy is contained in n bits of input; a cryptographic
hash, such as MD5, will distill out the "truly random".  The comments
in drivers/char/random.c claim that the input hash is cryptographically
noncritical, but to be pedantic, maybe MD5 the audio noise before
writing to /dev/random.

Assuming the sound-card output looks like reasonable noise of
a few LSBs amplitude, a conservative estimate might be 0.1 bit
of entropy per sample.  This is 9600 bits of entropy per second
from a stereo card, more than enough.

A small daemon would wake up every so often, check if /dev/random
needs topped up, read some audio samples, MD5(), write(),
ioctl(# of claimed entropy bits).  I haven't seen the i810 RNG tools,
but I guess they do something similar.

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Peter Monta wrote:

> 
> Well, yes and no.  What you really need is a conservative estimate
> of how much entropy is contained in n bits of input; a cryptographic
> hash, such as MD5, will distill out the "truly random".  The comments
> in drivers/char/random.c claim that the input hash is cryptographically
> noncritical, but to be pedantic, maybe MD5 the audio noise before
> writing to /dev/random.
> 


/dev/random rather does that itself (that's what the output hash does.)


> Assuming the sound-card output looks like reasonable noise of
> a few LSBs amplitude, a conservative estimate might be 0.1 bit
> of entropy per sample.  This is 9600 bits of entropy per second
> from a stereo card, more than enough.
> 
> A small daemon would wake up every so often, check if /dev/random
> needs topped up, read some audio samples, MD5(), write(),
> ioctl(# of claimed entropy bits).  I haven't seen the i810 RNG tools,
> but I guess they do something similar.


The point with the tests that have been mentioned is to derive such a
conservative estimate, and to raise a red flag if the output suddenly
becomes predictable.

	-hpa

 

Re: Continuing /dev/random problems with 2.4

[Peter Monta]

> The point with the tests that have been mentioned is to derive such a
> conservative estimate, and to raise a red flag if the output suddenly
> becomes predictable.

Ah, I see; I was misled by the "truly random" remark, sorry.  So a reasonable
sanity test for a block of audio samples might be a standard deviation
greater than a few LSB; this will catch constant or close-to-constant
output.

Re: Continuing /dev/random problems with 2.4

[David Wagner]

Jeff Garzik  wrote:
>There actually used to be a timer function in i810_rng driver which
>directly added entropy to the pool.  batch_entropy_store was exported in
>order to do this.
>
>However, that was just the quick and dirty way.  You DO NOT want to do
>this in the kernel, because one must perform fitness tests on the random
>data before adding it to the kernel's /dev/[u]random entropy pool.
>Putting proper fitness tests into the kernel is just plain code bloat.

Hmm.  I don't quite follow your reasoning.  Does the kernel already
perform fitness tests on random data from other drivers?  I don't
think so.

The i810 rng seems much less prone to entropy failure than the data
currently collected from I/O events.  Why are fitness tests for it more
important than for the existing entropy sources that are currently in
the kernel?

What am I missing?

Re: Continuing /dev/random problems with 2.4

[H. Peter Anvin]

Peter Monta wrote:

>>The point with the tests that have been mentioned is to derive such a
>>conservative estimate, and to raise a red flag if the output suddenly
>>becomes predictable.
>>
> 
> Ah, I see; I was misled by the "truly random" remark, sorry.  So a reasonable
> sanity test for a block of audio samples might be a standard deviation
> greater than a few LSB; this will catch constant or close-to-constant
> output.
> 


However, those aren't the main failure modes you need to be concerned 
with.  Antenna effects may actually be your biggest problem -- picking 
up deterministic signals from other parts of the system.

However, I believe this is a solved problem.  It would definitely be 
interesting taking rngd and figuring out a way to drive it from /dev/dsp 
-- probably not too difficult a modification.

	-hpa

Re: Continuing /dev/random problems with 2.4

[David Wagner]

Peter Monta  wrote:
>Many motherboards have on-board sound.  Why not turn the mic
>gain all the way up and use the noise---surely there will be
>a few bits' worth?

That may be reasonable, but beware: there are some potential pitfalls.
For instance, is there a risk that the audio data you read is strongly
correlated to 60Hz mains noise in some scenarios?  Also, my understanding
is that the quality of randomness you get can depend on which sound card
you have, and moreover that the left and right channels can be strongly
correlated (audio-entropyd takes the difference between the two).
I think there are some things you can do, but it seems that one might
want to be a bit careful here.

In general, I am warmly supportive of using as diverse a set of entropy
sources as possible to provide robustness in case one source unexpectedly
fails, but I also recommend care in analyzing how much entropy each
source really gives you (it seems prudent to be a bit conservative in
one's entropy estimates, due to the variety of subtle effects that can
compromise the quality of your randomness sources).

Also, you may be interested in audio-entropyd, rexx, and Nautilus,
all of which use something like this as part of their entropy collection.

Re: Continuing /dev/random problems with 2.4

[Peter Monta]

H. Peter Anvin wrote:

> However, those aren't the main failure modes you need to be concerned 
> with.  Antenna effects may actually be your biggest problem -- picking 
> up deterministic signals from other parts of the system.

David Wagner wrote:

> For instance, is there a risk that the audio data you read is strongly
> correlated to 60Hz mains noise in some scenarios?  ...

I don't think predictable elements in the audio hurt anything.
So long as there is a noise component, things are fine.

Take the case of a half-full-scale 60 Hz sine wave plus a tiny
bit of noise.  No problem---each sample would still be worth
0.1 bit because the attacker can only guess the 60 Hz part:
subtract this out and you've still got unpredictable noise.
Same deal with crosstalk between channels, so long as it's
reasonably small, say -20 dB or better (as it will be with any
sane sound chip).

> [ audio-entropyd ]

Aha, nothing new under the sun.

Cheers,
Peter Monta

Re: Continuing /dev/random problems with 2.4

[Jeff Garzik]

On Sat, Feb 02, 2002 at 01:33:48AM +0000, David Wagner wrote:
> Hmm.  I don't quite follow your reasoning.  Does the kernel already
> perform fitness tests on random data from other drivers?  I don't
> think so.
> 
> The i810 rng seems much less prone to entropy failure than the data
> currently collected from I/O events.  Why are fitness tests for it more
> important than for the existing entropy sources that are currently in
> the kernel?
> 
> What am I missing?

The "random" data from the RNG might suddenly become non-random.  If you
are telling the system you are trusting this source, you better make
sure it truly is random.

RNGs are different than other entropy sources in the kernel because it's
a black box.

	Jeff

Re: Continuing /dev/random problems with 2.4

[Kai Henningsen]

garzik@havoc.gtf.org (Jeff Garzik)  wrote on 01.02.02 in <20020201152829.A2497@havoc.gtf.org>:

> The userspace tools for i810 RNG specifically are available at the
> website URL mentioned in the source code.  So if somebody cannot find
> them, feel free to laugh.

I'm sure you didn't mean the URL to the tools is in the source of the  
tools, right?

So then, which other sources do you mean? "The Linux kernel", for example,  
is an awful lot of source. And in any case, why would you expect anyone  
(who probably hasn't heard that the i810 *has* a RNG) to look at it just  
to find out if possibly there was a tool that could be helpful for  
something?

What am I missing here? I hope I *am* missing something here ...

MfG Kai

Re: Continuing /dev/random problems with 2.4

[Andreas Dilger]

On Feb 02, 2002  10:54 +0200, Kai Henningsen wrote:
> garzik@havoc.gtf.org (Jeff Garzik)  wrote on 01.02.02 in <20020201152829.A2497@havoc.gtf.org>:
> > The userspace tools for i810 RNG specifically are available at the
> > website URL mentioned in the source code.  So if somebody cannot find
> > them, feel free to laugh.
> 
> I'm sure you didn't mean the URL to the tools is in the source of the  
> tools, right?

I think he meant that the i810 RNG user-space tools were mentioned in
the i810 kernel code.

In any case, check out gkernel.sf.net.

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

Re: Continuing /dev/random problems with 2.4

[Martin Dalecki]

David Wagner wrote:

>Peter Monta  wrote:
>
>>Many motherboards have on-board sound.  Why not turn the mic
>>gain all the way up and use the noise---surely there will be
>>a few bits' worth?
>>
>
>That may be reasonable, but beware: there are some potential pitfalls.
>For instance, is there a risk that the audio data you read is strongly
>correlated to 60Hz mains noise in some scenarios?  Also, my understanding
>is that the quality of randomness you get can depend on which sound card
>you have, and moreover that the left and right channels can be strongly
>correlated (audio-entropyd takes the difference between the two).
>I think there are some things you can do, but it seems that one might
>want to be a bit careful here.
>
There is no need to speculate here - just please do aan autocorrelation 
of the signal with grace for example and
laugh at the idea ;-).

Re: Continuing /dev/random problems with 2.4

[Henning P. Schmiedehausen]

Andreas Dilger <adilger@turbolabs.com> writes:

>Well, all of the Intel i8XX chipsets have a harware RNG I believe.

No, only those using the Firmware hub.

I have an (Original Intel (sic!)) i810 board without Firmware Hub (and
without RNG).

	Regards
		Henning


-- 
Dipl.-Inf. (Univ.) Henning P. Schmiedehausen       -- Geschaeftsfuehrer
INTERMETA - Gesellschaft fuer Mehrwertdienste mbH     hps@intermeta.de

Am Schwabachgrund 22  Fon.: 09131 / 50654-0   info@intermeta.de
D-91054 Buckenhof     Fax.: 09131 / 50654-20   

Re: Continuing /dev/random problems with 2.4

[Sean Hunter]

One thing I have found useful is to install an old soundcard, and use the
"audio entropy daemon".  This essentially samples static noise in the input
channels of the card, and feeds the result into the kernel entropy pool.

I don't know that anyone maintains this thing any more, so I have begun
rewriting it, in the hope that a maintained version would be more widely
useful.


Sean

On Fri, Feb 01, 2002 at 11:01:37AM -0600, Ken Brownfield wrote:
> On Fri, Feb 01, 2002 at 11:53:20AM -0500, Robert Love wrote:
> | On Fri, 2002-02-01 at 04:17, Ken Brownfield wrote:
> | Most of the useful fixes actually came in a large update from Andreas
> | Dilger.  Perhaps he would have some insight, too.
> 
> Ah, my apoligies then.
> 
> | Exhausting entropy to zero under high use is not uncommon (that is a
> | motivation for my netdev-random patch).  What boggles me is why it does
> | not regenerate?
> 
> Yeah -- slow entropy is "acceptable", but blocking until a reboot is rather unacceptable. ;)
> 
> Thx much,
> -- 
> Ken.
> brownfld@irridia.com
> 
> | 
> | 	Robert
> | 
> | -
> | To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> | the body of a message to majordomo@vger.kernel.org
> | More majordomo info at  http://vger.kernel.org/majordomo-info.html
> | Please read the FAQ at  http://www.tux.org/lkml/
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 

Re: Continuing /dev/random problems with 2.4

[Ishan O. Jayawardena]

Wouldn't it be trivial to use a zener diode with a rock-solid (i.e. as
ripple-free as possible) power supply? We'd have the randomness of the
electrons at our disposal. It's very easy to shield effectively. Of
course, this is a hardware issue...

I've been using zener diodes as white-noise generators for years for
meditation (I kid you not.) Had I used a RNG, I'd be totally insane by
now.

Cheerio!

	alvin
.

Re: Continuing /dev/random problems with 2.4

[Bill Davidsen]

On Fri, 1 Feb 2002, H. Peter Anvin wrote:

> Andreas Dilger wrote:
> 
> > 
> > Maybe, i8XX hardware RNG should feed the /dev/random entropy pool
> > directly if you enable the chipset support (with an option to turn
> > it off if you want to use the user-space tools or a separate RNG),
> > so that people get the benefits of the h/w RNG without having to
> > install another tool (which they won't know about)?
> 
> "Let's put it in the kernel because people are too stupid to install it
> otherwise"?
> 
> No thank you.

Why would the kernel NOT use available source of entropy? If the kernel is
gathering entropy, in what way is user mode better? Are you going to make
users install disk, keystroke, packet, etc daemons to do the work of the
kernel?

The only reason I can see for not doing this is if there is reason to
believe that it is not producing useful information.

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

Re: Continuing /dev/random problems with 2.4

[Roland Dreier]

>>>>> "Bill" == Bill Davidsen <davidsen@tmr.com> writes:

    Bill> Why would the kernel NOT use available source of entropy? If
    Bill> the kernel is gathering entropy, in what way is user mode
    Bill> better? Are you going to make users install disk, keystroke,
    Bill> packet, etc daemons to do the work of the kernel?

Entropy is gathered from interrupt timing in the kernel because
interrupts are handled in the kernel.  It would be quite difficult for
a user space process to get accurate information about interrupt
timing.

However, the i8xx RNG and audio entropy daemons work perfectly well
from user space.  What is gained by moving that code into the kernel?

Best,
  Roland

Re: Continuing /dev/random problems with 2.4

[Robert Love]

On Mon, 2002-02-04 at 17:37, Roland Dreier wrote:

> Entropy is gathered from interrupt timing in the kernel because
> interrupts are handled in the kernel.  It would be quite difficult for
> a user space process to get accurate information about interrupt
> timing.
> 
> However, the i8xx RNG and audio entropy daemons work perfectly well
> from user space.  What is gained by moving that code into the kernel?

Exactly.  Nothing is gained.

A misconception in this thread seems to be on how this works. 
Generating entropy from interrupts and block I/O uses timing values. 
Differences in successive operations of whatever.  The infrastructure
for carrying out those operations already exists, we just need to note
their timing. 

The i8xx and other RNGs are different.  They actually _give_ us the
random data.  In other words, they generate entropy to just push
directly into the pool.  The concern is that this data may not be safe,
and thus we need to run a fitness test on it (i.e. FIPS 190, I
believe).  All this muck is new code and can exist in userspace --
therefore it will.

	Robert Love

Re: Continuing /dev/random problems with 2.4

[Bill Davidsen]

On 4 Feb 2002, Robert Love wrote:

> The i8xx and other RNGs are different.  They actually _give_ us the
> random data.  In other words, they generate entropy to just push
> directly into the pool.  The concern is that this data may not be safe,
> and thus we need to run a fitness test on it (i.e. FIPS 190, I
> believe).  All this muck is new code and can exist in userspace --
> therefore it will.

You seem to equate root space with user space, which is a kernel way of
looking at things, particularly if you haven't been noting all the various
hacker attacks lately. Just because it is possible to run in user space
doesn't mean it's desirable to do so, and many sites don't really want
things running as root so they can feed other things to the kernel.

The assumption that power users will know how to fix it and other users
won't notice they have no entropy isn't all that appealing to me, I want
Linux to be as easy to do right as the competition.

Just my read on it.

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

Re: Continuing /dev/random problems with 2.4

[Robert Love]

On Tue, 2002-02-05 at 18:02, Bill Davidsen wrote:

> You seem to equate root space with user space, which is a kernel way of
> looking at things, particularly if you haven't been noting all the various
> hacker attacks lately. Just because it is possible to run in user space
> doesn't mean it's desirable to do so, and many sites don't really want
> things running as root so they can feed other things to the kernel.
> 
> The assumption that power users will know how to fix it and other users
> won't notice they have no entropy isn't all that appealing to me, I want
> Linux to be as easy to do right as the competition.

It is certainly desirable to run as much as feasibly possible in
userspace.  The only exception of things that could be handled in
userspace but are allowed to live in kernel space would be performance
critical and stable items (say, TCP/IP).

No one said the rngd has to run as root.  For example, run it as nobody
in a random group and give /dev/random write privileges to the random
group.

If userspace equates to insecure, and we stick things in the kernel for
that reason, we are beyond help ...

	Robert Love

Re: Continuing /dev/random problems with 2.4

[Bill Davidsen]

On 5 Feb 2002, Robert Love wrote:

> On Tue, 2002-02-05 at 18:02, Bill Davidsen wrote:
> 
> > You seem to equate root space with user space, which is a kernel way of
> > looking at things, particularly if you haven't been noting all the various
> > hacker attacks lately. Just because it is possible to run in user space
> > doesn't mean it's desirable to do so, and many sites don't really want
> > things running as root so they can feed other things to the kernel.
> > 
> > The assumption that power users will know how to fix it and other users
> > won't notice they have no entropy isn't all that appealing to me, I want
> > Linux to be as easy to do right as the competition.
> 
> It is certainly desirable to run as much as feasibly possible in
> userspace.  The only exception of things that could be handled in
> userspace but are allowed to live in kernel space would be performance
> critical and stable items (say, TCP/IP).

  Given that there is graphics stuff in there, and web server stuff, I
would say that having the system hang waiting for entropy is a performance
issue. And lack of it is a security issue.
 
> No one said the rngd has to run as root.  For example, run it as nobody
> in a random group and give /dev/random write privileges to the random
> group.

  So a functional /dev/random would be a feature of power users installing
fixes, as opposed to the kernel using the available hardware? And having
one or more extra user space daemons crapping up the system doesn't seem
an issue?
 
> If userspace equates to insecure, and we stick things in the kernel for
> that reason, we are beyond help ...

  Not all Linux users are hackers, and depending on users to know their
hardware, find, build, install, and configure something, change ownership
of a device without messing it up, and understand that not doing so is
both a performance and security issue... seems either optimistic or just
unconcerned with the users. 

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

Need a clew WRT fig2dev

[Kirk Reiser]

Hi Folks: I have been trying to make the docbook documentation in the
2.5.3 tree but have run into a problem not having fig2dev.  I do not
seem to be able to find this utility or any reference to it.  It does
not appear to be in my docbook utilities at any rate.  Any suggestions
would certainly be appreciated.

  Kirk

-- 

Kirk Reiser				The Computer Braille Facility
e-mail: kirk@braille.uwo.ca		University of Western Ontario
phone: (519) 661-3061

Re: Need a clew WRT fig2dev

[Adrian Bunk]

On 6 Feb 2002, Kirk Reiser wrote:

> Hi Folks: I have been trying to make the docbook documentation in the
> 2.5.3 tree but have run into a problem not having fig2dev.  I do not
> seem to be able to find this utility or any reference to it.  It does
> not appear to be in my docbook utilities at any rate.  Any suggestions
> would certainly be appreciated.

fig2dev is part of transfig. You can get it e.g. from [1].

>   Kirk

HTH
Adrian

[1] ftp://ftp.dante.de/pub/tex/graphics/transfig/

Re: Need a clew WRT fig2dev

[Jeff Garzik]

Kirk Reiser wrote:
> Hi Folks: I have been trying to make the docbook documentation in the
> 2.5.3 tree but have run into a problem not having fig2dev.  I do not
> seem to be able to find this utility or any reference to it.  It does
> not appear to be in my docbook utilities at any rate.  Any suggestions
> would certainly be appreciated.

[jgarzik@cum rpm]$ rpm -qf `which fig2dev`
transfig-3.2.3d-7mdk

-- 
Jeff Garzik      | "I went through my candy like hot oatmeal
Building 1024    |  through an internally-buttered weasel."
MandrakeSoft     |             - goats.com

Re: Continuing /dev/random problems with 2.4

[Nix N. Nix]

On Wed, 2002-02-06 at 11:16, Bill Davidsen wrote:
> On 5 Feb 2002, Robert Love wrote:
> 
> > On Tue, 2002-02-05 at 18:02, Bill Davidsen wrote:
> > 
> > > You seem to equate root space with user space, which is a kernel way of
> > > looking at things, particularly if you haven't been noting all the various
> > > hacker attacks lately. Just because it is possible to run in user space
> > > doesn't mean it's desirable to do so, and many sites don't really want
> > > things running as root so they can feed other things to the kernel.
> > > 
> > > The assumption that power users will know how to fix it and other users
> > > won't notice they have no entropy isn't all that appealing to me, I want
> > > Linux to be as easy to do right as the competition.
> > 
> > It is certainly desirable to run as much as feasibly possible in
> > userspace.  The only exception of things that could be handled in
> > userspace but are allowed to live in kernel space would be performance
> > critical and stable items (say, TCP/IP).
> 
>   Given that there is graphics stuff in there, and web server stuff, I
> would say that having the system hang waiting for entropy is a performance
> issue. And lack of it is a security issue.
>  
> > No one said the rngd has to run as root.  For example, run it as nobody
> > in a random group and give /dev/random write privileges to the random
> > group.
> 
>   So a functional /dev/random would be a feature of power users installing
> fixes, as opposed to the kernel using the available hardware? And having
> one or more extra user space daemons crapping up the system doesn't seem
> an issue?
>  
> > If userspace equates to insecure, and we stick things in the kernel for
> > that reason, we are beyond help ...
> 
>   Not all Linux users are hackers, and depending on users to know their
> hardware, find, build, install, and configure something, change ownership
> of a device without messing it up, and understand that not doing so is
> both a performance and security issue... seems either optimistic or just
> unconcerned with the users. 

What about distributors ?  These user space daemons and device ownership
changes can be done by the installation process of any given distro.  I
know Mandrake allows users to choose their "security level" from
install.  The options range from "Welcome to crackers" to "Paranoid". 
I'm certain that distros could perform the proper steps upon detection
of, say, a RNG.

> 
> -- 
> bill davidsen <davidsen@tmr.com>
>   CTO, TMR Associates, Inc
> Doing interesting things with little computers since 1979.
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>