[PATCH][RFC] Allow net devices to contribute to /dev/random

[PATCH][RFC] Allow net devices to contribute to /dev/random

[Robert Love]

Updated versions of my netdev-random patch are out.  The patchset is two
piece: one containing the core code and two containing the updated
drivers.

2.4.9-ac15:
http://tech9.net/rml/linux/patch-rml-2.4.9-ac15-netdev-random-1
http://tech9.net/rml/linux/patch-rml-2.4.9-ac15-netdev-random-2

2.4.10:
http://tech9.net/rml/linux/patch-rml-2.4.10-netdev-random-1
http://tech9.net/rml/linux/patch-rml-2.4.10-netdev-random-2

ChangeLog and more information:
http://tech9.net/rml/linux/

Quick summary:  This patch enables a new configure option that allows
users to allow whether network devices can contribute to /dev/random. 
Normally block devices and the keyboard contribute, although very few
network devices do.  This patch makes a user-configurable policy out of
the issue: either allow them all or disallow them all.  Some users, such
as those on a headless or diskless system, have little or no entropy. 
This patch will give them that entropy.  Summarizing the discussion on
the issue, as long as SHA-1 is secure or your network traffic is secure,
this is safe.  For those who don't want the option, leave the setting
disabled and no NIC will contribute.

How it works:  defines a new flag for each architecture,
SA_SAMPLE_NET_RANDOM which defines to 0 or SA_SAMPLE_RANDOM depending on
the value of the configure statement.

All architectures and all network devices are supported.  The lastest
patch fixes a few typos and the like.

[You can ignore further if you just wanted the newest patch]

Now, why this I ask for comments.  An alternative approach to this is to
not have a configure setting but instead have a /proc interface.  When
disabled, interrupts will not contribute, and when enabled, they will.

The code is something like this:

define SA_SAMPLE_NET_RANDOM to be our new SA_SAMPLE_RANDOM for NICs
(like with the normal patch).

let random_netdev_contribute be 0 or 1 set from the /proc interface.

in setup_irq and handle_IRQ_event() we change:

if (status & SA_SAMPLE_RANDOM)

to

if ((status & SA_SAMPLE_RANDOM) ||
	   ((status & SA_SAMPLE_NET_RANDOM) && random_netdev_contrib))

That's about it.  Most of the code I have is for the proc interface.

One problem, and one concern.

The problem: setup_irq is called on device setup.  this means that
in-kernel drivers and modules loaded before the /proc interface is set
will have the wrong value registered in setup_irq.  I am not too sure
what this entails

Ie, if random_netdev_contrib=0 when we call setup_irq, we won't call
rand_initialize_irq() but then if random_netdev_contrib is set to 1, we
will all of a sudden start calling add_interrupt_randomness()!  You can
see the reverse of this, too, where we will initialize it but not call
add.

Changing the proc entry on the fly and/or loading/unloading modules just
adds to this mess.

I just don't think this will work cleanly.

Finally, my concern is that the if statement is not the cleanest.  We
have to check for the normal SA_SAMPLE_RANDOM flag, and then we need to
check for the other possibility of the NET version of the flag. If it
exists, we need to see if random_netdev_contrib is set.  Not very
clean.  A cleaner design, anyone?

I am happy to just leave the patch as is, and right now I am thinking I
will do just that.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[David Wagner]

I'm worried about the language in the configuration documentation:
  +  Some people, however, feel that network devices should not contribute to
  +  /dev/random because an external attacker could observe incoming packets
  +  in an attempt to learn the entropy pool's state. Note this is completely
  +  theoretical. 
Incrementing the entropy counter based on externally observable
values is dangerous.  Calling this risk 'completely theoretical'
is, I believe, a misrepresentation, unless I've missed something.

A failed RNG is one of the most likely -- and most devastating
-- failure modes possible for modern cryptosystems, and as such
it pays to be careful here.  Are you proposing this for inclusion
in the mainline Linux kernel?  If so, I'm concerned that this patch
could put security at risk.  What am I missing?

Here is my reasoning.  I'd like to quote drivers/char/random.c:
  * add_interrupt_randomness() uses the inter-interrupt timing as random
  * inputs to the entropy pool.  Note that not all interrupts are good
  * sources of randomness!  For example, the timer interrupts is not a
  * good choice, because the periodicity of the interrupts is too
  * regular, and hence predictable to an attacker.  Disk interrupts are
  * a better measure, since the timing of the disk interrupts are more
  * unpredictable.
  * 
  * All of these routines try to estimate how many bits of randomness a
  * particular randomness source.  They do this by keeping track of the
  * first and second order deltas of the event timings.
This suggests that add_interrupt_randomness() should not be called
on all interrupts without discrimination.  Would it be fair to say
that your patch enables randomness collection on almost all interrupts?
If so, why is this safe to do?

I hope you agree that making this configurable does not obviate our
responsibility to make sure that the default configuration is reasonable.
This stuff is subtle, and changing it is not something I'd recommend
without a careful analysis of the impact on security.  Moreover, the
comments about 'completely theoretical' leave me concerned that any
analysis that has been done on this patch may be based on misconceptions
about cryptographic security.  Can you tell us anything about what
security analysis you've done so far?

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Robert Love]

On Tue, 2001-09-25 at 20:20, David Wagner wrote:
> I'm worried about the language in the configuration documentation:
>   +  Some people, however, feel that network devices should not contribute to
>   +  /dev/random because an external attacker could observe incoming packets
>   +  in an attempt to learn the entropy pool's state. Note this is completely
>   +  theoretical. 
> Incrementing the entropy counter based on externally observable
> values is dangerous.  Calling this risk 'completely theoretical'
> is, I believe, a misrepresentation, unless I've missed something.

First, I agree the wording is too `kind' and I will change it.

However, the actual end result -- that the output of /dev/random can be
predicted -- is theoretical, because of the fact the output is one-way
hashed.  I do not want to get into another full discussion of this, but
a thread exists about a month back that discussed it.

To summarize: the patch is a risk if and only if: SHA-1 is cracked, an
attacker can observe the state of network packets, and it contributes
enough to the pool that enough of its state is learned.

Some diskless machines really have _zero_ entropy.  This patch does them
good.  If you don't want net devices to contribute, don't enable them.

Hell, without this patch, some network devices do contribute!  It
actually standardizes the whole thing.

> A failed RNG is one of the most likely -- and most devastating
> -- failure modes possible for modern cryptosystems, and as such
> it pays to be careful here.  Are you proposing this for inclusion
> in the mainline Linux kernel?  If so, I'm concerned that this patch
> could put security at risk.  What am I missing?

I would like to see it in the kernel, for 2.5.

I agree a poor RNG is a risk.  I also put forth that this patch is
configurable and that WITHOUT it you actually have a few NIC drivers
that contribute to /dev/random!

If you are on a diskless system and need some seed for whatever, say SSH
or just something dinky, this patch may be a requirement.  Even on my
workstation, sometimes SSH blocks for some seconds waiting for
/dev/random to fill up.

> Here is my reasoning.  I'd like to quote drivers/char/random.c:
>   * add_interrupt_randomness() uses the inter-interrupt timing as random
>   * inputs to the entropy pool.  Note that not all interrupts are good
>   * sources of randomness!  For example, the timer interrupts is not a
>   * good choice, because the periodicity of the interrupts is too
>   * regular, and hence predictable to an attacker.  Disk interrupts are
>   * a better measure, since the timing of the disk interrupts are more
>   * unpredictable.
>   * 
>   * All of these routines try to estimate how many bits of randomness a
>   * particular randomness source.  They do this by keeping track of the
>   * first and second order deltas of the event timings.

Obviously the timer interrupt would be the worst idea ever.  Its the
same value (HZ) on almost all versions of Linux (Alpha being on example
where it is not the same).

> This suggests that add_interrupt_randomness() should not be called
> on all interrupts without discrimination.  Would it be fair to say
> that your patch enables randomness collection on almost all interrupts?
> If so, why is this safe to do?

No, it enables them on the interrupt for your NIC, if you enable the
config setting.  If you don't enable the config, then your NIC won't
contribute.

If you don't use the patch, then it is unknown what your NIC will do
without looking at the source.  A few drivers currently do set
SA_SAMPLE_RANDOM.

> I hope you agree that making this configurable does not obviate our
> responsibility to make sure that the default configuration is reasonable.

The default is off.

> This stuff is subtle, and changing it is not something I'd recommend
> without a careful analysis of the impact on security.  Moreover, the
> comments about 'completely theoretical' leave me concerned that any
> analysis that has been done on this patch may be based on misconceptions
> about cryptographic security.  Can you tell us anything about what
> security analysis you've done so far?

This patch has been around, and a consensus has been reached.  I also
understand the mathematics here.

Again:
Yes, network traffic can be observed (or even influenced) and this could
allow an attacker to learn something of the state of your entropy pool. 
Note this would be hard due to clock skews and the such, but yes it is
entirely possible.

Yes, if your pool has little other entropy, the attacker now knows of a
good deal of the state of the pool.

Yes, assuming SHA-1 is at risk, the attacker can know for SURE the
output of /dev/random.

Yes, this is completely theoretical.  Is this a risk? Sure. But it
defaults to off.  Sitting on my home network and knowing the strength of
SHA-1, I don't fear any of this.  Or maybe I am desperate for entropy
since I have no disks or user interaction on this system.  The patch was
written out of a discussion for it, even.

Thus, the patch defaults to off.  By all means, keep it off.  I agree
the wording should be made more intimidating.  However, without this
patch, your NIC could be contributing -- the patch actually institutes a
policy.

That is all this is.  Having a clearly defined policy, and letting it be
configurable.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[David Wagner]

Ok.  Since the default is 'off', I agree that this patch is unlikely
to lead to cryptographic failures in the 'off' setting.  At worst,
/dev/random will block forever, or more likely, block longer than it
otherwise would.  There is still a question in my mind about whether, by
turning off all network collection (and thus doing less entropy collection
than today's kernels do), this patch might be making the situation worse
for the average user.  However, I agree that at least this is fail-safe,
not fail-open, which is a useful property.

I certainly agree that insufficient entropy is indeed an important
problem for some installations.  However, I must admit that am not yet
convinced that this patch is the right solution for those installations:
it seems that the cure might well be worse than the disease in some cases.
I'll give some further discussion about my concerns below.  But before
I do, let me be clear about the worst case: With this patch set to
'on', the system might silently fail open and become insecure, but with
this patch in the default 'off' setting, at worst it just freezes, if
I understand correctly.  In other words, the reservations about being
too generous with the entropy counter only apply to the non-default 'on'
setting, so the rest of my comments only apply to this limited setting
where the user has already been warned.


Robert Love  wrote:
>On Tue, 2001-09-25 at 20:20, David Wagner wrote:
>> Incrementing the entropy counter based on externally observable
>> values is dangerous.
>
>However, the actual end result -- that the output of /dev/random can be
>predicted -- is theoretical, because of the fact the output is one-way
>hashed.

I didn't follow this part.  One concern is that, if we are too
generous with the entropy count, _all_ of the inputs to the randomness
pool might be known or predictable.  In this situation, the SHA
hash doesn't help at all.  I don't know how likely it is that this
situation will arise -- once we get 160 bits of good randomness
into the pool, we're safe as long as SHA is secure -- but the
whole reason that /dev/random exists is to be extremely conservative
about security.  Being overly generous with the entropy count invalidates
the warranty on /dev/random.  And for those who don't need an extremely
conservative solution, there's no reason to use /dev/random in the
first place: just grab 160 good bits and use /dev/urandom from then on.

>I do not want to get into another full discussion of this, but
>a thread exists about a month back that discussed it.

Yes, I followed that thread, and would not have posted my note about
this revision of the patch if I did not still have some questions.

>To summarize: the patch is a risk if and only if: SHA-1 is cracked, an
>attacker can observe the state of network packets, and it contributes
>enough to the pool that enough of its state is learned.

Well, maybe I could suggest that this statement should be extended
a bit.  Your statement is absolutely correct if we have gotten 160
good bits of true randomness into the pool at some point since booting,
but it is not quite correct if all of the inputs to /dev/random since
booting were predictable.

Thus, it might be more accurate to say that /dev/random is at risk
if SHA-1 is cracked, OR if the attacker can observe or predict all
the inputs to the randomness pool, OR if (SHA is cracked and the
attacker can observe or control the state of network packets and
these packets contribute enough to the pool).  Any of these three
cases are sufficient to invalidate security.

One concern might be that the patch could increase the risk of the
second failure mode by being overly generous with the entropy count
when in the 'on' setting.  /dev/random wasn't designed to be secure
when we feed it predictable values to add_interrupt_randomness(), and
it seems unreasonable to expect it to be reliably safe in this scenario.

>Some diskless machines really have _zero_ entropy.  This patch does them
>good.  If you don't want net devices to contribute, don't enable them.

Again, one concern is that for some devices, this patch might be
making the problem worse by turning off entropy collection for a
number of network devices.

>Hell, without this patch, some network devices do contribute!  It
>actually standardizes the whole thing.

Yes, but my understanding is that the devices that do contribute in
the current kernel were chosen according to some security analysis,
to ensure that they actually provide at least as much entropy as the
/dev/random entropy estimator expects.  My impression was that Ted
Ts'o had looked at this pretty carefully.  Was this impression incorrect?
Has anyone done a similar security analysis for the devices this
patch enables?

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Gordon Oliver]

Hi,
  I would actually suggest breaking out a longer discussion of the
risks associated with the patch into Documentation, and _strongly_
suggesting that the person configuring the kernel read it before
enabling the option. Then a statement that this may put the security
of /dev/random at risk would probably be enough.

  So let's start with the possible conditions are.
What I can see are the following:
   1) network card on visible net:
	- BadGuy can monitor the network traffic, extracting
	  timing information. Given enough knowledge about the
	  latency of the network card, all network entropy might
	  be known (making it non-secure). If the network is
	  the only, or primary, source of entropy this leads
	  to compromise
   2) network card on private net:
	- BadGuy must plug into private net to monitor the traffic,
	  any external monitoring is very likely to fail to get
	  much useful information.
   3) TSC not used to add randomness:
	- Prediction of time between interrupts becomes much easier
	  (jiffies are a big target).
   4) Systems that are largely quiescent could lead to easier prediction
      of latencies, and thus easier compromise.

In any case the following must be true for this to cause problems:
   a) The network must be the primary source of entropy (this
      will be common in the case where the patch is useful)
   b) BadGuy must monitor from time 0 (boot of system) to get
      useful information
   c) BadGuy must have information about what network card the system
      has, or _very_ good statistical information about delay to
      interrupt & timing in general.
   d) BadGuy must have information about how long the processing for
      the interrupt handler takes, as the randomness addition is done
      _after_ all processing. This also causes interesting problems
      for prediction if more than one event is handled at once.
   e) BadGuy must have access to information of network traffic on
      all the networks that are attached to the computer.

Now none of this guarantees security (but then again, very little will
_guarantee_ security.

I may have missed some stuff here... (caveat emptor)

Just as a comment, I actually like the patch, and would certainly be
willing to use it for a computer on a private network...
	-gordo

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Andreas Steinmetz]

> In any case the following must be true for this to cause problems:
>    a) The network must be the primary source of entropy (this
>       will be common in the case where the patch is useful)
>    b) BadGuy must monitor from time 0 (boot of system) to get
>       useful information
>    c) BadGuy must have information about what network card the system
>       has, or _very_ good statistical information about delay to
>       interrupt & timing in general.
>    d) BadGuy must have information about how long the processing for
>       the interrupt handler takes, as the randomness addition is done
>       _after_ all processing. This also causes interesting problems
>       for prediction if more than one event is handled at once.
>    e) BadGuy must have access to information of network traffic on
>       all the networks that are attached to the computer.
> 
> Now none of this guarantees security (but then again, very little will
> _guarantee_ security.
> 
> I may have missed some stuff here... (caveat emptor)
> 

To be constructive: why not make this HMAC-SHA1? The key for HMAC can be fed
through a sysctl interface. This would mean that BadGuy would need knowledge of
the key and thus the key generation method, too, especially if the key is
replaced at varying times and independent of network traffic.


Andreas Steinmetz
D.O.M. Datenverarbeitung GmbH

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[dean gaudet]

On 25 Sep 2001, Robert Love wrote:

> Some diskless machines really have _zero_ entropy.

have you considered the Network Randomization Protocol?

http://www.usenix.org/publications/library/proceedings/security95/full_papers/chow.txt

-dean

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Oliver Xymoron]

On 25 Sep 2001, Robert Love wrote:

> On Tue, 2001-09-25 at 20:20, David Wagner wrote:
> > I'm worried about the language in the configuration documentation:
> >   +  Some people, however, feel that network devices should not contribute to
> >   +  /dev/random because an external attacker could observe incoming packets
> >   +  in an attempt to learn the entropy pool's state. Note this is completely
> >   +  theoretical.
> > Incrementing the entropy counter based on externally observable
> > values is dangerous.  Calling this risk 'completely theoretical'
> > is, I believe, a misrepresentation, unless I've missed something.
>
> First, I agree the wording is too `kind' and I will change it.
>
> However, the actual end result -- that the output of /dev/random can be
> predicted -- is theoretical, because of the fact the output is one-way
> hashed.

Explain to me how you can simultaneously prefer /dev/random for its purely
theoretical advantages and yet want to throw exactly that advantage out
the window?

What is really called for is the addition of potential network randomness
without crediting it with entropy. And using /dev/urandom, now exactly as
strong as the /dev/random you propose[1]. And acceptable to everyone.

> Some diskless machines really have _zero_ entropy.

Then we shouldn't be pretending that they can generate secure random
numbers.


[1] Assume an SSL webserver with only network interrupts as a source of
entropy. If entropy is a bottleneck, you're in a catch-22: you must wait
for more traffic to generate keys, but getting more traffic depends on
generating said keys. Blocking = dropping connections = not handling n% of
load at all load levels. Thus, the application demands entropy produced is
greater than entropy consumed.

Assuming that's the case and you'd be able to run a system with
/dev/random+network "entropy", it will work just as well with
/dev/urandom+network "entropy". Blocking buys us nothing if entropy is
proportional to load and capacity is proportional to entropy.

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Pavel Machek]

Hi!

> > Here is my reasoning.  I'd like to quote drivers/char/random.c:
> >   * add_interrupt_randomness() uses the inter-interrupt timing as random
> >   * inputs to the entropy pool.  Note that not all interrupts are good
> >   * sources of randomness!  For example, the timer interrupts is not a
> >   * good choice, because the periodicity of the interrupts is too
> >   * regular, and hence predictable to an attacker.  Disk interrupts are
> >   * a better measure, since the timing of the disk interrupts are more
> >   * unpredictable.
> >   * 
> >   * All of these routines try to estimate how many bits of randomness a
> >   * particular randomness source.  They do this by keeping track of the
> >   * first and second order deltas of the event timings.
> 
> Obviously the timer interrupt would be the worst idea ever.  Its the
> same value (HZ) on almost all versions of Linux (Alpha being on example
> where it is not the same).

Actually, not quite. On 2.4.9 system, console kept interrupts disabled
for so long that timer interrupt was pretty good source of randomness.

								Pavel
-- 
I'm pavel@ucw.cz. "In my country we have almost anarchy and I don't care."
Panos Katsaloulis describing me w.r.t. patents at discuss@linmodems.org

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Robert Love]

On Mon, 2001-10-01 at 10:43, Pavel Machek wrote:
> > Obviously the timer interrupt would be the worst idea ever.  Its the
> > same value (HZ) on almost all versions of Linux (Alpha being on example
> > where it is not the same).
> 
> Actually, not quite. On 2.4.9 system, console kept interrupts disabled
> for so long that timer interrupt was pretty good source of randomness.

That is pretty sad, to be honest :)

Besides, on some systems interrupts may rarely be disabled -- its too
hard to tell.  We don't want another config option, do we? :)

Also, 2.4.10 merged Andrew Morton's console-locking patch, so one can
hope the console's latency is improved.

-- 
Robert M. Love
rml at ufl.edu
rml at tech9.net

Re: [PATCH][RFC] Allow net devices to contribute to /dev/random

[Florian Weimer]

daw@mozart.cs.berkeley.edu (David Wagner) writes:

> Incrementing the entropy counter based on externally observable
> values is dangerous.

How do you want to collect any entropy with such a requirement in
place?  Computers tend to send out a lot of information on the air.

BTW, I still think that the entropy estimate for mouse movements is
much too high.  And the compression function used probably doesn't
have the intended property.

-- 
Florian Weimer 	                  Florian.Weimer@RUS.Uni-Stuttgart.DE
University of Stuttgart           http://cert.uni-stuttgart.de/
RUS-CERT                          +49-711-685-5973/fax +49-711-685-5898

/dev/random entropy calculations broken?

[Andreas Dilger]

On Oct 01, 2001  11:52 +0200, Florian Weimer wrote:
> daw@mozart.cs.berkeley.edu (David Wagner) writes:
> > Incrementing the entropy counter based on externally observable
> > values is dangerous.
> 
> How do you want to collect any entropy with such a requirement in
> place?  Computers tend to send out a lot of information on the air.
>
> BTW, I still think that the entropy estimate for mouse movements is
> much too high.  And the compression function used probably doesn't
> have the intended property.

Has anyone even checked whether the current entropy estimates even work
properly?  I was testing this, and it appears something is terribly wrong.
Check /proc/sys/kernel/random/entropy_avail.  On a system that has been
running any length of time, it should be 4096 (512 bytes * 8 bits of
entropy for a full pool).

Now, "dd if=/dev/random bs=16 count=1 | wc -c" and check entropy_avail
again.  It "loses" thousands of bits of entropy for generating 16 bytes
(128 bits) of random data.  Same thing happens with /dev/urandom consuming
the available entropy.

Now if you do the above test on /dev/random several times in a row, you see
that you really HAVE used up the entropy, because it will return a number
of bytes less than what you requested.  At this point, however, it is at
least consistent, returning a number of bytes = entropy_avail/8.

Ted, any ideas about this?  I'm just looking through the code to see where
the entropy is counted, and where it goes.  It _may_ be a bug with the
entropy_avail value itself, but then why the short reads?  The output values
are at least consistent in that they grow slowly only when kb/mouse/disk
activity happens, and are constant otherwise.

This may be a major source of problems for entropy-poor environments, since
you will basically only be able to read a single random value from /dev/random
before the pool "dries up", regardless of the pool size (I tried with a
4096-byte pool, and the same problem happens).  Hence, in such systems there
would be more of a desire to use the "less secure" network interrupts for
entropy.

Cheers, Andreas

PS - For systems which have _some_ entropy, but just not very much, it is
     possible to increase the size of the pool (if it actually worked ;-)
     so that you can save entropy for periods of high demand.  You can do
     this by "echo 4096 > /proc/sys/kernel/random/poolsize" (or some other
     larger power-of-two size).
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: /dev/random entropy calculations broken?

[Alex Bligh - linux-kernel]

--On Monday, 01 October, 2001 10:59 AM -0600 Andreas Dilger 
<adilger@turbolabs.com> wrote:

> Has anyone even checked whether the current entropy estimates even work
> properly?

And while we're at it, many things which add to entropy are
observable by non-root users (interupt timings always, mouse
movements, keypresses if a non-root user is logged in at
the console). And entropy is overestimate on some non-x86
platforms due to lack of fine-grained timer implementations.
And without Robert Love's patch the choice of whether to source
it from network events is completely arbitrary (NIC dependent)

However, unless one is worried about someone having broken
SHA-1 OR one is worried about annoying blocking behavour
on read(), I'm not convinced the entropy calculation is
doing anything useful anyway.

People do, however, seem particularly reluctant to accept
any change in this area.

--
Alex Bligh

Re: /dev/random entropy calculations broken?

[antirez]

On Mon, Oct 01, 2001 at 10:55:26PM +0100, Alex Bligh - linux-kernel wrote:
> However, unless one is worried about someone having broken
> SHA-1 OR one is worried about annoying blocking behavour
> on read(), I'm not convinced the entropy calculation is
> doing anything useful anyway.

I think the /dev/random /dev/urandom solution is perfect
from this point of view. Using /dev/random you can get
random number that are secure _even_ if tomorrow SHA1 will
be broken at the cost of a very slow generation.
Or you may trust SHA1 (or some other crypto primitive) to
avoid to collect too much entropy to generate the output.
Probably real world applications should use
/dev/urandom, assuming it's properly designed, i.e. the
internal state is changed once there is enough entropy
to create a new unguessable key, the entropy isn't
overstimated, and so on.

BTW I agree, instead to create a key being paranoid about
the SHA1 security it's better to double check if the
entropy source is ok. For example the linux PRNG used
to collect a lot of entropy bits from the keyboard
auto-repeat aaaaaaaaaaaaaa ...
It's useless to try to collect enough entropy (and maybe
overstimating it) to produce an output secure against
SHA1 possible weakness (i.e. totally generated with
entropy bits). It's probably better a more conservative
approach in the entropy collection and to use a belived secure
crypto primitive to produce the PRNG output.

After all, unless you are using a one-time pad probably
the key generated with /dev/random will be used with
the crypto algorithms you refused to trust.

-- 
Salvatore Sanfilippo <antirez@invece.org>
http://www.kyuzz.org/antirez
finger antirez@tella.alicom.com for PGP key
28 52 F5 4A 49 65 34 29 - 1D 1B F6 DA 24 C7 12 BF

Re: /dev/random entropy calculations broken?

[Andreas Dilger]

On Oct 01, 2001  10:59 -0600, adilger wrote:
> Has anyone even checked whether the current entropy estimates even work
> properly?  I was testing this, and it appears something is terribly wrong.
> Check /proc/sys/kernel/random/entropy_avail.  On a system that has been
> running any length of time, it should be 4096 (512 bytes * 8 bits of
> entropy for a full pool).
> 
> Now, "dd if=/dev/random bs=16 count=1 | wc -c" and check entropy_avail
> again.  It "loses" thousands of bits of entropy for generating 16 bytes
> (128 bits) of random data.
> 
> Now if you do the above test on /dev/random several times in a row, you see
> that you really HAVE used up the entropy, because it will return a number
> of bytes less than what you requested.  At this point, however, it is at
> least consistent, returning a number of bytes = entropy_avail/8.

OK, after going through the code carefully, it appears that there are
several big problems in entropy accounting in drivers/char/random.c
which essentially mean that any time we read /dev/random or /dev/urandom
or /proc/sys/kernel/random/uuid we would entirely deplete the entropy pool.

While this in itself is not a security problem (i.e. we discard huge
amounts of entropy on each operation) it could be a problem for systems
that need entropy and don't want it wasted.  Similarly, it _may_ be a
factor in "inflating" entropy counts from sources, because we were
throwing so much away it wouldn't be usable without such high entropy
counts.  In my testing, be basically ALWAYS get 9-12 bits of entropy
from each keystroke, disk I/O, and (many, many) mouse interrupts, rather
than dribble in entropy in small bits at a time.


The below patch fixes these problems, at least to be sane in regards
to accounting of entropy in the system.  There are still some issues
to be discussed however.

First fix (minor): in batch_entropy_process() if the store had the maximum
  amount of entropy, the remaining entropy _appeared_ that it should go
  into the secondary store.  However, the test "entropy_count > max_entropy"
  could never be true (entropy_count is clamped in credit_entropy_store()).
  Fixed so we add entropy to secondary store until it is also full, and
  then alternate stirring in values into both stores (accumulates more
  entropy, and adds more randomness even if we don't account for entropy).

Second fix (minor): in batch_entropy_process() IF we switched to adding
  entropy to the secondary store, we credited this store with entropy
  that was actually added to the first store.  Also in this case we only
  woke up a reader if the _secondary_ store had enough entropy, and not
  it the _primary_ store had enough entropy (which is much more likely).

Third fix (minor): in xfer_secondary_pool() we extract entropy from the
  primary pool, even if the secondary pool is already full, if we request
  more entropy than can fit into the secondary pool.  The pool will be
  refilled anyways because it will be depleted after this action.  We now
  only refill the secondary pool if it is not already full (saving entropy).
  We could save even more entropy by only adding as much entropy as we need.

Fourth fix (minor): in xfer_secondary_pool() we credit the secondary pool
  with the correct number of BITS taken from the primary pool(*).  We were
  adding 1/4 of the number of bits taken from the primary to the secondary,
  and losing the other 3/4 of the entropy (byte/word mismatch?)(**).

Fifth fix: in extract_entropy() the "redundant but just in case" check was
  wrong, comparing entropy bit count and pool words.  This had the effect
  of losing 31/32 of the random pool on each access.  BAD, BAD program!


(*) It is my assumption that if you extract N bits of entropy from one
    pool, you add N bits into the other pool.  If this isn't true, then
    something needs to be fixed elsewhere.  I believe the problem is
    that extract_entropy() returns "nbytes" of data regardless of how
    much real entropy is in the pool, hence "creating" entropy where
    there was none in xfer_secondary_pool().  Either we should return
    the REAL amount of entropy backed data (and fix the urandom return
    values), or figure out some way to credit the secondary pool with
    only as much entropy as is really available.

(**) When using the SHA hash, we extract 5+80 words = 2720 bits from the
    primary pool and "add" it to the secondary pool.  However, the
    secondary pool is only 1024 bits in size, so we throw half of this
    entropy away each time (including extra CPU overhead).  Should we
    fix the secondary pool to be at least TMP_BUF_SIZE to hold this data?


The second patch is purely cosmetic fixes (added comments and such),
and also exports "generate_random_uuid()" for use in modules (I was
playing around with this in reiserfs as a module, and it needs to
be exported anyways, according to the comments above it).

Cheers, Andreas
===========================================================================
--- linux.orig/drivers/char/random.c	Tue Jul 10 17:05:24 2001
+++ linux/drivers/char/random.c	Tue Oct  2 00:17:40 2001
@@ -403,6 +403,12 @@
 #define MIN(a,b) (((a) < (b)) ? (a) : (b))
 #endif
 
+#if 0
+#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
+#else
+#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+
 /*
  * Unfortunately, while the GCC optimizer for the i386 understands how
  * to optimize a static rotate left of x bits, it doesn't know how to
@@ -651,24 +670,23 @@
 
 static void batch_entropy_process(void *private_)
 {
-	int	num = 0;
-	int	max_entropy;
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	
+	int	max_entropy = r->poolinfo.poolwords*32;
+
 	if (!batch_max)
 		return;
 
-	max_entropy = r->poolinfo.poolwords*32;
+	p = r;
 	while (batch_head != batch_tail) {
+		if (r->entropy_count >= max_entropy) {
+			r = (r == sec_random_state) ?	random_state :
+							sec_random_state;
+		}
 		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
-		p = r;
-		if (r->entropy_count > max_entropy && (num & 1))
-			r = sec_random_state;
 		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
 		batch_tail = (batch_tail+1) & (batch_max-1);
-		num++;
 	}
-	if (r->entropy_count >= random_read_wakeup_thresh)
+	if (p->entropy_count >= random_read_wakeup_thresh)
 		wake_up_interruptible(&random_read_wait);
 }
 
@@ -1210,12 +1233,19 @@
 {
 	__u32	tmp[TMP_BUF_SIZE];
 
-	if (r->entropy_count < nbytes*8) {
+	if (r->entropy_count < nbytes*8 && r->entropy_count < r->poolsize*32) {
+		DEBUG_ENT("xfer %d from primary to %s (have %d need %d)\n",
+			  sizeof(tmp) * 8,
+			  r == sec_random_state ? "secondary" : "unknown",
+			  r->entropy_count, nbytes * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
 		add_entropy_words(r, tmp, TMP_BUF_SIZE);
-		credit_entropy_store(r, TMP_BUF_SIZE*8);
+		credit_entropy_store(r, TMP_BUF_SIZE*32);
 	}
 	if (r->extract_count > 1024) {
+		DEBUG_ENT("reseeding %s with %d from primary\n",
+			  r == sec_random_state ? "secondary" : "unknown",
+			  sizeof(tmp) * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
 		add_entropy_words(r, tmp, TMP_BUF_SIZE);
 		r->extract_count = 0;
@@ -1240,10 +1270,10 @@
 	__u32 x;
 
 	add_timer_randomness(&extract_timer_state, nbytes);
-	
+
 	/* Redundant, but just in case... */
-	if (r->entropy_count > r->poolinfo.poolwords) 
-		r->entropy_count = r->poolinfo.poolwords;
+	if (r->entropy_count > r->poolinfo.poolwords * 32)
+		r->entropy_count = r->poolinfo.poolwords * 32;
 
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);



===========================================================================
--- linux.orig/drivers/char/random.c	Tue Jul 10 17:05:24 2001
+++ linux/drivers/char/random.c	Tue Oct  2 00:17:40 2001
@@ -272,8 +272,8 @@
 static int random_write_wakeup_thresh = 128;
 
 /*
- * A pool of size POOLWORDS is stirred with a primitive polynomial
- * of degree POOLWORDS over GF(2).  The taps for various sizes are
+ * A pool of size .poolwords is stirred with a primitive polynomial
+ * of degree .poolwords over GF(2).  The taps for various sizes are
  * defined below.  They are chosen to be evenly spaced (minimum RMS
  * distance from evenly spaced; the numbers in the comments are a
  * scaled squared error sum) except for the last tap, which is 1 to
@@ -552,11 +558,12 @@
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
 	int new_rotate;
+	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w;
 
 	while (num--) {
 		w = rotate_left(r->input_rotate, *in);
-		i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
+		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
 		 * At the beginning of the pool, add an extra 7 bits
@@ -569,11 +576,11 @@
 		r->input_rotate = new_rotate & 31;
 
 		/* XOR in the various taps */
-		w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
+		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
@@ -586,12 +593,20 @@
 {
 	int	max_entropy = r->poolinfo.poolwords*32;
 
-	if (r->entropy_count + num < 0)
+	if (r->entropy_count + num < 0) {
+		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
+			  r->entropy_count, num);
 		r->entropy_count = 0;
-	else if (r->entropy_count + num > max_entropy)
+	} else if (r->entropy_count + num > max_entropy) {
 		r->entropy_count = max_entropy;
-	else
-		r->entropy_count = r->entropy_count + num;
+	} else {
+		r->entropy_count += num;
+		if (num)
+			DEBUG_ENT("%s added %d bits, now %d\n",
+				  r == sec_random_state ? "secondary" :
+				  r == random_state ? "primary" : "unknown",
+				  num, r->entropy_count);
+	}
 }
 
 /**********************************************************************
@@ -627,6 +642,12 @@
 	return 0;
 }
 
+/*
+ * Changes to the entropy data are put into a queue rather than being added
+ * to the entropy counts directly.  This is presumably to avoid doing heavy
+ * hashing calculations during an interrupt in add_timer_randomness().
+ * Instead, the entropy is only added to the pool once per timer tick.
+ */
 void batch_entropy_store(u32 a, u32 b, int num)
 {
 	int	new;
@@ -643,12 +664,15 @@
 		queue_task(&batch_tqueue, &tq_timer);
 		batch_head = new;
 	} else {
-#if 0
-		printk(KERN_NOTICE "random: batch entropy buffer full\n");
-#endif
+		DEBUG_ENT("batch entropy buffer full\n");
 	}
 }
 
+/*
+ * Flush out the accumulated entropy operations, adding entropy to the passed
+ * store (normally random_state).  If that store has enough entropy, alternate
+ * between randomizing the data of the primary and secondary stores.
+ */
 static void batch_entropy_process(void *private_)
 {
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
@@ -1228,9 +1258,12 @@
  * bits of entropy are left in the pool, but it does not restrict the
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
- * If the EXTRACT_ENTROPY_SECONDARY flag is given, then this function will 
  *
- * Note: extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
+ * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually
+ * extracting entropy from the secondary pool, and can refill from the
+ * primary pool if needed.
+ *
+ * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
 			       size_t nbytes, int flags)
@@ -1248,6 +1278,11 @@
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);
 
+	DEBUG_ENT("%s has %d bits, want %d bits\n",
+		  r == sec_random_state ? "secondary" :
+		  r == random_state ? "primary" : "unknown",
+		  r->entropy_count, nbytes * 8);
+
 	if (r->entropy_count / 8 >= nbytes)
 		r->entropy_count -= nbytes*8;
 	else
@@ -2238,4 +2276,5 @@
 EXPORT_SYMBOL(add_interrupt_randomness);
 EXPORT_SYMBOL(add_blkdev_randomness);
 EXPORT_SYMBOL(batch_entropy_store);
+EXPORT_SYMBOL(generate_random_uuid);
 
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: /dev/random entropy calculations broken?

[Andreas Dilger]

On Oct 02, 2001  01:51 -0600, Andreas Dilger wrote:
> -	if (r->entropy_count < nbytes*8) {
> +	if (r->entropy_count < nbytes*8 && r->entropy_count < r->poolsize*32) {
                                                                 ^^^^^^^^
Doh!  I hate it when I do that (compile, test, think, edit, send patch
without the compile, test steps).   Should be "poolinfo.poolwords".

Cheers, Andreas
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: /dev/random entropy calculations broken?

[Oliver Xymoron]

On Tue, 2 Oct 2001, Andreas Dilger wrote:

> Fifth fix: in extract_entropy() the "redundant but just in case" check was
>   wrong, comparing entropy bit count and pool words.  This had the effect
>   of losing 31/32 of the random pool on each access.  BAD, BAD program!

> +	if (r->entropy_count > r->poolinfo.poolwords * 32)
> +		r->entropy_count = r->poolinfo.poolwords * 32;

Damnit, I read that line 30 times yesterday!

While we're on words/bytes/bits confusion, add_entropy_words() seems to
get called with number of bytes rather than words.

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: /dev/random entropy calculations broken?

[Andreas Dilger]

On Oct 02, 2001  10:37 -0500, Oliver Xymoron wrote:
> On Tue, 2 Oct 2001, Andreas Dilger wrote:
> > Fifth fix: in extract_entropy() the "redundant but just in case" check was
> >   wrong, comparing entropy bit count and pool words.  This had the effect
> >   of losing 31/32 of the random pool on each access.  BAD, BAD program!
> 
> > +	if (r->entropy_count > r->poolinfo.poolwords * 32)
> > +		r->entropy_count = r->poolinfo.poolwords * 32;
> 
> Damnit, I read that line 30 times yesterday!

So did I.  It wasn't till my system was spewing debugging output that I
saw where it was going.

> While we're on words/bytes/bits confusion, add_entropy_words() seems to
> get called with number of bytes rather than words.

Makes it that much more random, doesn't it ;-).  OK, here is a new version
of the patch.  It clears up the parameters to the functions, and makes sure
that we pass the right values to each.

Cheers, Andreas
===========================================================================
--- linux.orig/drivers/char/random.c	Tue Jul 10 17:05:24 2001
+++ linux/drivers/char/random.c	Tue Oct  2 14:50:19 2001
@@ -272,8 +272,8 @@
 static int random_write_wakeup_thresh = 128;
 
 /*
- * A pool of size POOLWORDS is stirred with a primitive polynomial
- * of degree POOLWORDS over GF(2).  The taps for various sizes are
+ * A pool of size .poolwords is stirred with a primitive polynomial
+ * of degree .poolwords over GF(2).  The taps for various sizes are
  * defined below.  They are chosen to be evenly spaced (minimum RMS
  * distance from evenly spaced; the numbers in the comments are a
  * scaled squared error sum) except for the last tap, which is 1 to
@@ -281,49 +281,47 @@
  */
 static struct poolinfo {
 	int	poolwords;
+	int	poolbits;	/* poolwords * 32 */
 	int	tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
-	{ 2048,	1638,	1231,	819, 	411,	1 },
+	{ 2048,	65536,	1638,	1231,	819,	411,	1 },
 
 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
-	{ 1024,	817, 	615,	412,	204,	1 },
-
+	{ 1024,	32768,	817,	615,	412,	204,	1 },
 #if 0				/* Alternate polynomial */
 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
-	{ 1024,	819,	616,	410,	207,	2 },
+	{ 1024,	32768,	819,	616,	410,	207,	2 },
 #endif
-	
-	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
-	{ 512,	411,	308,	208,	104,	1 },
 
+	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
+	{ 512,	16384,	411,	308,	208,	104,	1 },
 #if 0				/* Alternates */
 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
-	{ 512,	409,	307,	206,	102,	2 },
+	{ 512,	16384,	409,	307,	206,	102,	2 },
 	/* x^512 + x^409 + x^309 + x^205 + x^103 + x^2 + 1 -- 95 */
-	{ 512,	409,	309,	205,	103,	2 },
+	{ 512,	16384,	409,	309,	205,	103,	2 },
 #endif
 
 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
-	{ 256,	205,	155,	101,	52,	1 },
-	
-	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
-	{ 128,	103,	76,	51,	25,	1 },
+	{ 256,	8192,	205,	155,	101,	52,	1 },
 
+	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
+	{ 128,	4096,	103,	76,	51,	25,	1 },
 #if 0	/* Alternate polynomial */
 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
-	{ 128,	103,	78,	51,	27,	2 },
+	{ 128,	4096,	103,	78,	51,	27,	2 },
 #endif
 
 	/* x^64 + x^52 + x^39 + x^26 + x^14 + x + 1 -- 15 */
-	{ 64,	52,	39,	26,	14,	1 },
+	{ 64,	2048,	52,	39,	26,	14,	1 },
 
 	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
-	{ 32,	26,	20,	14,	7,	1 },
+	{ 32,	1024,	26,	20,	14,	7,	1 },
+
+	{ 0,	0,	0,	0,	0,	0,	0 },
+};
 
-	{ 0, 	0,	0,	0,	0,	0 },
-};		
-	
 /*
  * For the purposes of better mixing, we use the CRC-32 polynomial as
  * well to make a twisted Generalized Feedback Shift Reigster
@@ -461,6 +459,12 @@
 }
 #endif
 
+#if 0
+#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
+#else
+#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+
 /**********************************************************************
  *
  * OS independent entropy store.   Here are the functions which handle
@@ -545,18 +549,19 @@
  * the entropy is concentrated in the low-order bits.
  */
 static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			     int num)
+			      int nwords)
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
 	int new_rotate;
+	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w;
 
-	while (num--) {
+	while (nwords--) {
 		w = rotate_left(r->input_rotate, *in);
-		i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
+		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
 		 * At the beginning of the pool, add an extra 7 bits
@@ -569,11 +574,11 @@
 		r->input_rotate = new_rotate & 31;
 
 		/* XOR in the various taps */
-		w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
+		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
@@ -582,16 +587,22 @@
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
-static void credit_entropy_store(struct entropy_store *r, int num)
+static void credit_entropy_store(struct entropy_store *r, int nbits)
 {
-	int	max_entropy = r->poolinfo.poolwords*32;
-
-	if (r->entropy_count + num < 0)
+	if (r->entropy_count + nbits < 0) {
+		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
+			  r->entropy_count, nbits);
 		r->entropy_count = 0;
-	else if (r->entropy_count + num > max_entropy)
-		r->entropy_count = max_entropy;
-	else
-		r->entropy_count = r->entropy_count + num;
+	} else if (r->entropy_count + nbits > r->poolinfo.poolbits) {
+		r->entropy_count = r->poolinfo.poolbits;
+	} else {
+		r->entropy_count += nbits;
+		if (nbits)
+			DEBUG_ENT("%s added %d bits, now %d\n",
+				  r == sec_random_state ? "secondary" :
+				  r == random_state ? "primary" : "unknown",
+				  nbits, r->entropy_count);
+	}
 }
 
 /**********************************************************************
@@ -627,6 +638,12 @@
 	return 0;
 }
 
+/*
+ * Changes to the entropy data is put into a queue rather than being added to
+ * the entropy counts directly.  This is presumably to avoid doing heavy
+ * hashing calculations during an interrupt in add_timer_randomness().
+ * Instead, the entropy is only added to the pool once per timer tick.
+ */
 void batch_entropy_store(u32 a, u32 b, int num)
 {
 	int	new;
@@ -643,32 +660,33 @@
 		queue_task(&batch_tqueue, &tq_timer);
 		batch_head = new;
 	} else {
-#if 0
-		printk(KERN_NOTICE "random: batch entropy buffer full\n");
-#endif
+		DEBUG_ENT("batch entropy buffer full\n");
 	}
 }
 
+/*
+ * Flush out the accumulated entropy operations, adding entropy to the passed
+ * store (normally random_state).  If that store has enough entropy, alternate
+ * between randomizing the data of the primary and secondary stores.
+ */
 static void batch_entropy_process(void *private_)
 {
-	int	num = 0;
-	int	max_entropy;
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	
+
 	if (!batch_max)
 		return;
 
-	max_entropy = r->poolinfo.poolwords*32;
+	p = r;
 	while (batch_head != batch_tail) {
+		if (r->entropy_count >= r->poolinfo.poolbits) {
+			r = (r == sec_random_state) ?	random_state :
+							sec_random_state;
+		}
 		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
-		p = r;
-		if (r->entropy_count > max_entropy && (num & 1))
-			r = sec_random_state;
 		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
 		batch_tail = (batch_tail+1) & (batch_max-1);
-		num++;
 	}
-	if (r->entropy_count >= random_read_wakeup_thresh)
+	if (p->entropy_count >= random_read_wakeup_thresh)
 		wake_up_interruptible(&random_read_wait);
 }
 
@@ -1210,14 +1228,26 @@
 {
 	__u32	tmp[TMP_BUF_SIZE];
 
-	if (r->entropy_count < nbytes*8) {
-		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
-		credit_entropy_store(r, TMP_BUF_SIZE*8);
+	if (r->entropy_count < nbytes * 8 &&
+	    r->entropy_count < r->poolinfo.poolbits) {
+		int nwords = MIN(r->poolinfo.poolwords - r->entropy_count/32,
+				 sizeof(tmp) / 4);
+
+		DEBUG_ENT("xfer %d from primary to %s (have %d need %d)\n",
+			  nwords * 32,
+			  r == sec_random_state ? "secondary" : "unknown",
+			  r->entropy_count, nbytes * 8);
+
+		extract_entropy(random_state, tmp, nwords, 0);
+		add_entropy_words(r, tmp, nwords);
+		credit_entropy_store(r, nwords * 32);
 	}
 	if (r->extract_count > 1024) {
+		DEBUG_ENT("reseeding %s with %d from primary\n",
+			  r == sec_random_state ? "secondary" : "unknown",
+			  sizeof(tmp) * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
+		add_entropy_words(r, tmp, sizeof(tmp) / 4);
 		r->extract_count = 0;
 	}
 }
@@ -1228,9 +1258,12 @@
  * bits of entropy are left in the pool, but it does not restrict the
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
- * If the EXTRACT_ENTROPY_SECONDARY flag is given, then this function will 
  *
- * Note: extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
+ * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually
+ * extracting entropy from the secondary pool, and can refill from the
+ * primary pool if needed.
+ *
+ * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
 			       size_t nbytes, int flags)
@@ -1240,14 +1273,19 @@
 	__u32 x;
 
 	add_timer_randomness(&extract_timer_state, nbytes);
-	
+
 	/* Redundant, but just in case... */
-	if (r->entropy_count > r->poolinfo.poolwords) 
-		r->entropy_count = r->poolinfo.poolwords;
+	if (r->entropy_count > r->poolinfo.poolbits)
+		r->entropy_count = r->poolinfo.poolbits;
 
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);
 
+	DEBUG_ENT("%s has %d bits, want %d bits\n",
+		  r == sec_random_state ? "secondary" :
+		  r == random_state ? "primary" : "unknown",
+		  r->entropy_count, nbytes * 8);
+
 	if (r->entropy_count / 8 >= nbytes)
 		r->entropy_count -= nbytes*8;
 	else
@@ -1543,9 +1581,7 @@
 		c -= bytes;
 		p += bytes;
 
-		/* Convert bytes to words */
-		bytes = (bytes + 3) / sizeof(__u32);
-		add_entropy_words(random_state, buf, bytes);
+		add_entropy_words(random_state, buf, (bytes + 3) / 4);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;
@@ -1589,7 +1625,7 @@
 		ent_count = random_state->entropy_count;
 		if (put_user(ent_count, p++))
 			return -EFAULT;
-			
+
 		if (get_user(size, p))
 			return -EFAULT;
 		if (put_user(random_state->poolinfo.poolwords, p++))
@@ -1598,7 +1634,7 @@
 			return -EINVAL;
 		if (size > random_state->poolinfo.poolwords)
 			size = random_state->poolinfo.poolwords;
-		if (copy_to_user(p, random_state->pool, size*sizeof(__u32)))
+		if (copy_to_user(p, random_state->pool, size * 4))
 			return -EFAULT;
 		return 0;
 	case RNDADDENTROPY:
@@ -1845,8 +1881,7 @@
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;
-	max_read_thresh = max_write_thresh =
-		random_state->poolinfo.poolwords * 32;
+	max_read_thresh = max_write_thresh = random_state->poolinfo.poolbits;
 	random_table[1].data = &random_state->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */
@@ -2238,4 +2273,5 @@
 EXPORT_SYMBOL(add_interrupt_randomness);
 EXPORT_SYMBOL(add_blkdev_randomness);
 EXPORT_SYMBOL(batch_entropy_store);
+EXPORT_SYMBOL(generate_random_uuid);
 
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: /dev/random entropy calculations broken?

[Oliver Xymoron]

On Tue, 2 Oct 2001, Andreas Dilger wrote:

> > While we're on words/bytes/bits confusion, add_entropy_words() seems to
> > get called with number of bytes rather than words.
>
> Makes it that much more random, doesn't it ;-).  OK, here is a new version
> of the patch.  It clears up the parameters to the functions, and makes sure
> that we pass the right values to each.

Cool. Not sure if I like the introduction of poolbits. My personal
preference would be to s/poolwords/words/ and just use ->words*32, since
foo->foomember is a throwback to pre-ANSI compilers with a flat namespace
for structure members. Note that we don't bother prefixing tap*.

If not, at least put poolbits in the structure first...

>  static struct poolinfo {
>  	int	poolwords;
> +	int	poolbits;	/* poolwords * 32 */
>  	int	tap1, tap2, tap3, tap4, tap5;
>  } poolinfo_table[] = {
>  	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
> -	{ 2048,	1638,	1231,	819, 	411,	1 },
> +	{ 2048,	65536,	1638,	1231,	819,	411,	1 },
                ^^^^^
...because it's not as confusing comparing the polynomial in the comment
to the initializer.

--
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.."

Re: /dev/random entropy calculations broken?

[Andreas Dilger]

On Oct 02, 2001  16:29 -0500, Oliver Xymoron wrote:
> Cool. Not sure if I like the introduction of poolbits. My personal
> preference would be to s/poolwords/words/ and just use ->words*32, since
> foo->foomember is a throwback to pre-ANSI compilers with a flat namespace
> for structure members. Note that we don't bother prefixing tap*.

I added poolbits because we were doing poolwords * 32 all the time in the
commonly called functions credit_entropy_store() and batch_entropy_process()).
I don't really care either way, except that it makes the code easier to read.

We could always do the following (hackish, but makes code more readable):

#define POOLBITS	poolwords*32
#define POOLBYTES 	poolwords*4

> If not, at least put poolbits in the structure first...
> 
> >  static struct poolinfo {
> >  	int	poolwords;
> > +	int	poolbits;	/* poolwords * 32 */
> >  	int	tap1, tap2, tap3, tap4, tap5;
> >  } poolinfo_table[] = {
> >  	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
> > -	{ 2048,	1638,	1231,	819, 	411,	1 },
> > +	{ 2048,	65536,	1638,	1231,	819,	411,	1 },
>                 ^^^^^
> ...because it's not as confusing comparing the polynomial in the comment
> to the initializer.

Sorry, I didn't notice that the poolwords was also part of the polynomial.
I'll wait a while before reposting in case of more comments (Ted has been
silent thus far).

Cheers, Andreas
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

[PATCH] Re: /dev/random entropy calculations broken?

[Andreas Dilger]

I never heard back from Ted on this issue, but it is plain to see that
entropy accounting for /dev/random is broken.  Linus, Alan, please apply
the new patch.

Testing for broken entropy accounting (in kernel debugging verifies this):

$cat /proc/sys/kernel/random/entropy_count	# current entropy count in bits
4096
$dd if=/dev/random bs=64 count=1 | wc -c	# should get 64 bytes back, and
1+0 records in					# reduce entropy count by 512
1+0 records out
     64
$cat /proc/sys/kernel/random/entropy_count	# the entropy is all gone!
81
$dd if=/dev/random bs=64 count=1 | wc -c	# we don't get 64 bytes back
0+1 records in
0+1 records out
     24


In my testing, the second "dd" returns a short read because the entropy has
disappeared because of bad accounting.

Attached are two patches - the first corrects the real bugs in the accounting,
and the second updates comments, cleans up the code a bit (no functional
changes just debugging and clarifying where we are using bits/bytes/ words
as quantities, which was the source of the original bug), removes some
extraneous whitespace, etc.

Note that I have NOT changed anything in the way that random data values are
calculated in either patch, only making the "accounting" of the entropy sane.

Cheers, Andreas

On Oct 02, 2001  01:51 -0600, adilger wrote:
> OK, after going through the code carefully, it appears that there are
> several big problems in entropy accounting in drivers/char/random.c
> which essentially mean that any time we read /dev/random or /dev/urandom
> or /proc/sys/kernel/random/uuid we would entirely deplete the entropy pool.
> 
> While this in itself is not a security problem (i.e. we discard huge
> amounts of entropy on each operation) it could be a problem for systems
> that are entropy poor and don't want it wasted.
> 
> 
> The below patch fixes these problems, at least to be sane in regards
> to accounting of entropy in the system.  There are still some issues
> to be discussed however.  Patch hunk descriptions with severity of bug:
> 
> First fix (small): in batch_entropy_process() if the store had the maximum
>   amount of entropy, the remaining entropy _appeared_ that it should go
>   into the secondary store.  However, the test "entropy_count > max_entropy"
>   could never be true (entropy_count is clamped in credit_entropy_store()).
>   Fixed so we add entropy to secondary store until it is also full, and
>   then alternate stirring in values into both stores (accumulates more
>   entropy, and adds more randomness even if we don't account for entropy).
> 
> Second fix (small): in batch_entropy_process() IF we switched to adding
>   entropy to the secondary store, we credited this store with entropy
>   that was actually added to the first store.  Also in this case we only
>   woke up a reader if the _secondary_ store had enough entropy, and not
>   it the _primary_ store had enough entropy (which is much more likely,
>   since we are adding entropy to the primary store first).
> 
> Third fix (small): in xfer_secondary_pool() we extract entropy from the
>   primary pool to add to the secondary pool, even if the secondary pool
>   is already full, if we make a large request.  The pool will be refilled
>   anyways because it will be depleted after this action.  We now only
>   refill the secondary pool if it is not already full (saving entropy).
> 
> Fourth fix (medium): in xfer_secondary_pool() we credit the secondary pool
>   with the correct number of BITS taken from the primary pool(*).  We were
>   adding 1/4 of the number of bits taken from the primary to the secondary,
>   and losing the other 3/4 of the entropy (byte/word mismatch?)(**).
> 
> Fifth fix (LARGE): in extract_entropy() the "redundant but just in case"
>   check was wrong, comparing entropy BITS and pool WORDS.  This had
>   the effect of losing 31/32 of the random pool each access.  BAD program!
> 
> 
> (*) It is my assumption that if you extract N bits of entropy from one
>     pool, you add N bits into the other pool.  If this isn't true, then
>     something needs to be fixed elsewhere.  I believe the problem is
>     that extract_entropy() returns "nbytes" of data regardless of how
>     much real entropy is in the pool, hence "creating" entropy where
>     there was none in xfer_secondary_pool().  Either we should return
>     the REAL amount of entropy backed data (and fix the urandom return
>     values), or figure out some way to credit the secondary pool with
>     only as much entropy as is really available.
> 
> (**) When using the SHA hash, we extract 5+80 words = 2720 bits from the
>     primary pool and "add" it to the secondary pool.  However, the
>     secondary pool is only 1024 bits in size, so we throw half of this
>     entropy away each time (including extra CPU overhead).  Should we
>     fix the secondary pool to be at least TMP_BUF_SIZE to hold this data?

===========================================================================
--- linux.orig/drivers/char/random.c	Tue Jul 10 17:05:24 2001
+++ linux/drivers/char/random.c	Fri Oct 19 14:41:07 2001
@@ -321,9 +325,12 @@
 	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
 	{ 32,	26,	20,	14,	7,	1 },
 
-	{ 0, 	0,	0,	0,	0,	0 },
-};		
-	
+	{ 0,	0,	0,	0,	0,	0 },
+};
+
+#define POOLBITS	poolwords*32
+#define POOLBYTES	poolwords*4
+
 /*
  * For the purposes of better mixing, we use the CRC-32 polynomial as
  * well to make a twisted Generalized Feedback Shift Reigster
@@ -461,6 +468,12 @@
 }
 #endif
 
+#if 0
+#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
+#else
+#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+
 /**********************************************************************
  *
  * OS independent entropy store.   Here are the functions which handle
@@ -649,26 +673,31 @@
 	}
 }
 
+/*
+ * Flush out the accumulated entropy operations, adding entropy to the passed
+ * store (normally random_state).  If that store has enough entropy, alternate
+ * between randomizing the data of the primary and secondary stores.
+ */
 static void batch_entropy_process(void *private_)
 {
-	int	num = 0;
-	int	max_entropy;
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	
+	int max_entropy = r->poolinfo.POOLBITS;
+
 	if (!batch_max)
 		return;
 
-	max_entropy = r->poolinfo.poolwords*32;
+	p = r;
 	while (batch_head != batch_tail) {
+		if (r->entropy_count >= max_entropy) {
+			r = (r == sec_random_state) ?	random_state :
+							sec_random_state;
+			max_entropy = r->poolinfo.POOLBITS;
+		}
 		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
-		p = r;
-		if (r->entropy_count > max_entropy && (num & 1))
-			r = sec_random_state;
 		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
 		batch_tail = (batch_tail+1) & (batch_max-1);
-		num++;
 	}
-	if (r->entropy_count >= random_read_wakeup_thresh)
+	if (p->entropy_count >= random_read_wakeup_thresh)
 		wake_up_interruptible(&random_read_wait);
 }
 
@@ -1210,14 +1239,26 @@
 {
 	__u32	tmp[TMP_BUF_SIZE];
 
-	if (r->entropy_count < nbytes*8) {
-		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
-		credit_entropy_store(r, TMP_BUF_SIZE*8);
+	if (r->entropy_count < nbytes * 8 &&
+	    r->entropy_count < r->poolinfo.POOLBITS) {
+		int nwords = min(r->poolinfo.poolwords - r->entropy_count/32,
+				 sizeof(tmp) / 4);
+
+		DEBUG_ENT("xfer %d from primary to %s (have %d, need %d)\n",
+			  nwords * 32,
+			  r == sec_random_state ? "secondary" : "unknown",
+			  r->entropy_count, nbytes * 8);
+
+		extract_entropy(random_state, tmp, nwords, 0);
+		add_entropy_words(r, tmp, nwords);
+		credit_entropy_store(r, nwords * 32);
 	}
 	if (r->extract_count > 1024) {
+		DEBUG_ENT("reseeding %s with %d from primary\n",
+			  r == sec_random_state ? "secondary" : "unknown",
+			  sizeof(tmp) * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
+		add_entropy_words(r, tmp, sizeof(tmp) / 4);
 		r->extract_count = 0;
 	}
 }
@@ -1240,10 +1284,10 @@
 	__u32 x;
 
 	add_timer_randomness(&extract_timer_state, nbytes);
-	
+
 	/* Redundant, but just in case... */
-	if (r->entropy_count > r->poolinfo.poolwords) 
-		r->entropy_count = r->poolinfo.poolwords;
+	if (r->entropy_count > r->poolinfo.POOLBITS)
+		r->entropy_count = r->poolinfo.POOLBITS;
 
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);
@@ -2238,4 +2284,5 @@
 EXPORT_SYMBOL(add_interrupt_randomness);
 EXPORT_SYMBOL(add_blkdev_randomness);
 EXPORT_SYMBOL(batch_entropy_store);
+EXPORT_SYMBOL(generate_random_uuid);
 
===========================================================================
--- linux.orig/drivers/char/random.c	Tue Jul 10 17:05:24 2001
+++ linux/drivers/char/random.c	Fri Oct 19 14:41:07 2001
@@ -164,25 +164,32 @@
  * sequence: 
  *
  *	echo "Initializing random number generator..."
- * 	random_seed=/var/run/random-seed
+ *	random_seed=/var/run/random-seed
  *	# Carry a random seed from start-up to start-up
- *	# Load and then save 512 bytes, which is the size of the entropy pool
- * 	if [ -f $random_seed ]; then
+ *	# Load and then save the whole entropy pool
+ *	if [ -f $random_seed ]; then
  *		cat $random_seed >/dev/urandom
- * 	fi
- *	dd if=/dev/urandom of=$random_seed count=1
- * 	chmod 600 $random_seed
+ *	else
+ *		touch $random_seed
+ *	fi
+ *	chmod 600 $random_seed
+ *	poolfile=/proc/sys/kernel/random/poolsize
+ *	[ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=bytes
  *
  * and the following lines in an appropriate script which is run as
  * the system is shutdown:
- * 
+ *
  *	# Carry a random seed from shut-down to start-up
- *	# Save 512 bytes, which is the size of the entropy pool
+ *	# Save the whole entropy pool
  *	echo "Saving random seed..."
- * 	random_seed=/var/run/random-seed
- *	dd if=/dev/urandom of=$random_seed count=1
- * 	chmod 600 $random_seed
- * 
+ *	random_seed=/var/run/random-seed
+ *	touch $random_seed
+ *	chmod 600 $random_seed
+ *	poolfile=/proc/sys/kernel/random/poolsize
+ *	[ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=bytes
+ *
  * For example, on most modern systems using the System V init
  * scripts, such code fragments would be found in
  * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
@@ -272,8 +279,8 @@
 static int random_write_wakeup_thresh = 128;
 
 /*
- * A pool of size POOLWORDS is stirred with a primitive polynomial
- * of degree POOLWORDS over GF(2).  The taps for various sizes are
+ * A pool of size .poolwords is stirred with a primitive polynomial
+ * of degree .poolwords over GF(2).  The taps for various sizes are
  * defined below.  They are chosen to be evenly spaced (minimum RMS
  * distance from evenly spaced; the numbers in the comments are a
  * scaled squared error sum) except for the last tap, which is 1 to
@@ -284,19 +291,17 @@
 	int	tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
-	{ 2048,	1638,	1231,	819, 	411,	1 },
+	{ 2048,	1638,	1231,	819,	411,	1 },
 
 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
-	{ 1024,	817, 	615,	412,	204,	1 },
-
+	{ 1024,	817,	615,	412,	204,	1 },
 #if 0				/* Alternate polynomial */
 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
 	{ 1024,	819,	616,	410,	207,	2 },
 #endif
-	
+
 	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
 	{ 512,	411,	308,	208,	104,	1 },
-
 #if 0				/* Alternates */
 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
 	{ 512,	409,	307,	206,	102,	2 },
@@ -306,10 +311,9 @@
 
 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
 	{ 256,	205,	155,	101,	52,	1 },
-	
+
 	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
 	{ 128,	103,	76,	51,	25,	1 },
-
 #if 0	/* Alternate polynomial */
 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
 	{ 128,	103,	78,	51,	27,	2 },
@@ -480,7 +493,7 @@
 /*
  * Initialize the entropy store.  The input argument is the size of
  * the random pool.
- * 
+ *
  * Returns an negative error if there is a problem.
  */
 static int create_entropy_store(int size, struct entropy_store **ret_bucket)
@@ -507,12 +520,12 @@
 	memset (r, 0, sizeof(struct entropy_store));
 	r->poolinfo = *p;
 
-	r->pool = kmalloc(poolwords*4, GFP_KERNEL);
+	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
 	if (!r->pool) {
 		kfree(r);
 		return -ENOMEM;
 	}
-	memset(r->pool, 0, poolwords*4);
+	memset(r->pool, 0, POOLBYTES);
 	*ret_bucket = r;
 	return 0;
 }
@@ -524,7 +537,7 @@
 	r->entropy_count = 0;
 	r->input_rotate = 0;
 	r->extract_count = 0;
-	memset(r->pool, 0, r->poolinfo.poolwords*4);
+	memset(r->pool, 0, r->poolinfo.POOLBYTES);
 }
 
 static void free_entropy_store(struct entropy_store *r)
@@ -545,18 +558,19 @@
  * the entropy is concentrated in the low-order bits.
  */
 static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			     int num)
+			      int nwords)
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
 	int new_rotate;
+	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w;
 
-	while (num--) {
+	while (nwords--) {
 		w = rotate_left(r->input_rotate, *in);
-		i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
+		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
 		 * At the beginning of the pool, add an extra 7 bits
@@ -569,11 +583,11 @@
 		r->input_rotate = new_rotate & 31;
 
 		/* XOR in the various taps */
-		w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
+		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
@@ -582,16 +596,22 @@
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
-static void credit_entropy_store(struct entropy_store *r, int num)
+static void credit_entropy_store(struct entropy_store *r, int nbits)
 {
-	int	max_entropy = r->poolinfo.poolwords*32;
-
-	if (r->entropy_count + num < 0)
+	if (r->entropy_count + nbits < 0) {
+		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
+			  r->entropy_count, nbits);
 		r->entropy_count = 0;
-	else if (r->entropy_count + num > max_entropy)
-		r->entropy_count = max_entropy;
-	else
-		r->entropy_count = r->entropy_count + num;
+	} else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) {
+		r->entropy_count = r->poolinfo.POOLBITS;
+	} else {
+		r->entropy_count += nbits;
+		if (nbits)
+			DEBUG_ENT("%s added %d bits, now %d\n",
+				  r == sec_random_state ? "secondary" :
+				  r == random_state ? "primary" : "unknown",
+				  nbits, r->entropy_count);
+	}
 }
 
 /**********************************************************************
@@ -627,6 +647,12 @@
 	return 0;
 }
 
+/*
+ * Changes to the entropy data is put into a queue rather than being added to
+ * the entropy counts directly.  This is presumably to avoid doing heavy
+ * hashing calculations during an interrupt in add_timer_randomness().
+ * Instead, the entropy is only added to the pool once per timer tick.
+ */
 void batch_entropy_store(u32 a, u32 b, int num)
 {
 	int	new;
@@ -643,9 +669,7 @@
 		queue_task(&batch_tqueue, &tq_timer);
 		batch_head = new;
 	} else {
-#if 0
-		printk(KERN_NOTICE "random: batch entropy buffer full\n");
-#endif
+		DEBUG_ENT("batch entropy buffer full\n");
 	}
 }
 
@@ -1200,9 +1229,9 @@
 
 /*
  * This utility inline function is responsible for transfering entropy
- * from the primary pool to the secondary extraction pool.  We pull 
- * randomness under two conditions; one is if there isn't enough entropy 
- * in the secondary pool.  The other is after we have extract 1024 bytes,
+ * from the primary pool to the secondary extraction pool.  We pull
+ * randomness under two conditions; one is if there isn't enough entropy
+ * in the secondary pool.  The other is after we have extracted 1024 bytes,
  * at which point we do a "catastrophic reseeding".
  */
 static inline void xfer_secondary_pool(struct entropy_store *r,
@@ -1228,9 +1269,12 @@
  * bits of entropy are left in the pool, but it does not restrict the
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
- * If the EXTRACT_ENTROPY_SECONDARY flag is given, then this function will 
  *
- * Note: extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
+ * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually
+ * extracting entropy from the secondary pool, and can refill from the
+ * primary pool if needed.
+ *
+ * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
 			       size_t nbytes, int flags)
@@ -1248,6 +1292,11 @@
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);
 
+	DEBUG_ENT("%s has %d bits, want %d bits\n",
+		  r == sec_random_state ? "secondary" :
+		  r == random_state ? "primary" : "unknown",
+		  r->entropy_count, nbytes * 8);
+
 	if (r->entropy_count / 8 >= nbytes)
 		r->entropy_count -= nbytes*8;
 	else
@@ -1543,9 +1592,7 @@
 		c -= bytes;
 		p += bytes;
 
-		/* Convert bytes to words */
-		bytes = (bytes + 3) / sizeof(__u32);
-		add_entropy_words(random_state, buf, bytes);
+		add_entropy_words(random_state, buf, (bytes + 3) / 4);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;
@@ -1589,7 +1636,7 @@
 		ent_count = random_state->entropy_count;
 		if (put_user(ent_count, p++))
 			return -EFAULT;
-			
+
 		if (get_user(size, p))
 			return -EFAULT;
 		if (put_user(random_state->poolinfo.poolwords, p++))
@@ -1598,7 +1645,7 @@
 			return -EINVAL;
 		if (size > random_state->poolinfo.poolwords)
 			size = random_state->poolinfo.poolwords;
-		if (copy_to_user(p, random_state->pool, size*sizeof(__u32)))
+		if (copy_to_user(p, random_state->pool, size * 4))
 			return -EFAULT;
 		return 0;
 	case RNDADDENTROPY:
@@ -1715,11 +1762,11 @@
 {
 	int	ret;
 
-	sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
 
 	ret = proc_dointvec(table, write, filp, buffer, lenp);
 	if (ret || !write ||
-	    (sysctl_poolsize == random_state->poolinfo.poolwords * 4))
+	    (sysctl_poolsize == random_state->poolinfo.POOLBYTES))
 		return ret;
 
 	return change_poolsize(sysctl_poolsize);
@@ -1731,7 +1778,7 @@
 {
 	int	len;
 	
-	sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
 
 	/*
 	 * We only handle the write case, since the read case gets
@@ -1746,7 +1793,7 @@
 			return -EFAULT;
 	}
 
-	if (sysctl_poolsize != random_state->poolinfo.poolwords * 4)
+	if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)
 		return change_poolsize(sysctl_poolsize);
 
 	return 0;
@@ -1845,8 +1892,7 @@
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;
-	max_read_thresh = max_write_thresh =
-		random_state->poolinfo.poolwords * 32;
+	max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS;
 	random_table[1].data = &random_state->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */

Cheers, Andreas
--
Andreas Dilger  \ "If a man ate a pound of pasta and a pound of antipasto,
                 \  would they cancel out, leaving him still hungry?"
http://www-mddsp.enel.ucalgary.ca/People/adilger/               -- Dogbert

Re: [PATCH] Re: /dev/random entropy calculations broken?

[Robert Love]

On Fri, 2001-10-19 at 18:59, Andreas Dilger wrote:
> I never heard back from Ted on this issue, but it is plain to see that
> entropy accounting for /dev/random is broken.  Linus, Alan, please apply
> the new patch.

I show the same problem on my machines here.  Upon applying the patch:

[00:57:14]rml@phantasy:~$ cat /proc/sys/kernel/random/entropy_avail
4096
[00:57:18]rml@phantasy:~$ dd if=/dev/random bs=64 count=2 | wc -c
2+0 records in
2+0 records out
    128
[00:57:19]rml@phantasy:~$ cat /proc/sys/kernel/random/entropy_avail
3977

(initial - final < 128 because entropy is being added, I assume)

IANADRE, but the patch design looks good to me.  I tried to figure out
where things should be bytes and where things should be words and
everything matched up.

Also, I couldn't get the patch to apply but Andreas kindly sent me a
copy.  It did not diff perfectly against the latest trees, so I rediffed
it.  The attached patches fine against 2.4.12-ac3 and 2.4.13-pre5.  Alan
and Linus, it looks right to me.


diff -u linux-2.4.12-ac3/drivers/char/random.c linux/drivers/char/random.c
--- linux-2.4.12-ac3/drivers/char/random.c	Sun Oct 21 00:32:39 2001
+++ linux/drivers/char/random.c	Sun Oct 21 00:37:18 2001
@@ -164,25 +164,32 @@
  * sequence: 
  *
  *	echo "Initializing random number generator..."
- * 	random_seed=/var/run/random-seed
+ *	random_seed=/var/run/random-seed
  *	# Carry a random seed from start-up to start-up
- *	# Load and then save 512 bytes, which is the size of the entropy pool
- * 	if [ -f $random_seed ]; then
+ *	# Load and then save the whole entropy pool
+ *	if [ -f $random_seed ]; then
  *		cat $random_seed >/dev/urandom
- * 	fi
- *	dd if=/dev/urandom of=$random_seed count=1
- * 	chmod 600 $random_seed
+ *	else
+ *		touch $random_seed
+ *	fi
+ *	chmod 600 $random_seed
+ *	poolfile=/proc/sys/kernel/random/poolsize
+ *	[ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=bytes
  *
  * and the following lines in an appropriate script which is run as
  * the system is shutdown:
- * 
+ *
  *	# Carry a random seed from shut-down to start-up
- *	# Save 512 bytes, which is the size of the entropy pool
+ *	# Save the whole entropy pool
  *	echo "Saving random seed..."
- * 	random_seed=/var/run/random-seed
- *	dd if=/dev/urandom of=$random_seed count=1
- * 	chmod 600 $random_seed
- * 
+ *	random_seed=/var/run/random-seed
+ *	touch $random_seed
+ *	chmod 600 $random_seed
+ *	poolfile=/proc/sys/kernel/random/poolsize
+ *	[ -r $poolfile ] && bytes=`cat $poolfile` || bytes=512
+ *	dd if=/dev/urandom of=$random_seed count=1 bs=bytes
+ *
  * For example, on most modern systems using the System V init
  * scripts, such code fragments would be found in
  * /etc/rc.d/init.d/random.  On older Linux systems, the correct script
@@ -272,8 +279,8 @@
 static int random_write_wakeup_thresh = 128;
 
 /*
- * A pool of size POOLWORDS is stirred with a primitive polynomial
- * of degree POOLWORDS over GF(2).  The taps for various sizes are
+ * A pool of size .poolwords is stirred with a primitive polynomial
+ * of degree .poolwords over GF(2).  The taps for various sizes are
  * defined below.  They are chosen to be evenly spaced (minimum RMS
  * distance from evenly spaced; the numbers in the comments are a
  * scaled squared error sum) except for the last tap, which is 1 to
@@ -284,19 +291,17 @@
 	int	tap1, tap2, tap3, tap4, tap5;
 } poolinfo_table[] = {
 	/* x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1  -- 115 */
-	{ 2048,	1638,	1231,	819, 	411,	1 },
+	{ 2048,	1638,	1231,	819,	411,	1 },
 
 	/* x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1 -- 290 */
-	{ 1024,	817, 	615,	412,	204,	1 },
-
+	{ 1024,	817,	615,	412,	204,	1 },
 #if 0				/* Alternate polynomial */
 	/* x^1024 + x^819 + x^616 + x^410 + x^207 + x^2 + 1 -- 115 */
 	{ 1024,	819,	616,	410,	207,	2 },
 #endif
-	
+
 	/* x^512 + x^411 + x^308 + x^208 + x^104 + x + 1 -- 225 */
 	{ 512,	411,	308,	208,	104,	1 },
-
 #if 0				/* Alternates */
 	/* x^512 + x^409 + x^307 + x^206 + x^102 + x^2 + 1 -- 95 */
 	{ 512,	409,	307,	206,	102,	2 },
@@ -306,10 +311,9 @@
 
 	/* x^256 + x^205 + x^155 + x^101 + x^52 + x + 1 -- 125 */
 	{ 256,	205,	155,	101,	52,	1 },
-	
+
 	/* x^128 + x^103 + x^76 + x^51 +x^25 + x + 1 -- 105 */
 	{ 128,	103,	76,	51,	25,	1 },
-
 #if 0	/* Alternate polynomial */
 	/* x^128 + x^103 + x^78 + x^51 + x^27 + x^2 + 1 -- 70 */
 	{ 128,	103,	78,	51,	27,	2 },
@@ -321,9 +325,12 @@
 	/* x^32 + x^26 + x^20 + x^14 + x^7 + x + 1 -- 15 */
 	{ 32,	26,	20,	14,	7,	1 },
 
-	{ 0, 	0,	0,	0,	0,	0 },
-};		
-	
+	{ 0,	0,	0,	0,	0,	0 },
+};
+
+#define POOLBITS	poolwords*32
+#define POOLBYTES	poolwords*4
+
 /*
  * For the purposes of better mixing, we use the CRC-32 polynomial as
  * well to make a twisted Generalized Feedback Shift Reigster
@@ -461,6 +468,12 @@
 }
 #endif
 
+#if 0
+#define DEBUG_ENT(fmt, arg...) printk(KERN_DEBUG "random: " fmt, ## arg)
+#else
+#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+
 /**********************************************************************
  *
  * OS independent entropy store.   Here are the functions which handle
@@ -480,7 +493,7 @@
 /*
  * Initialize the entropy store.  The input argument is the size of
  * the random pool.
- * 
+ *
  * Returns an negative error if there is a problem.
  */
 static int create_entropy_store(int size, struct entropy_store **ret_bucket)
@@ -507,12 +520,12 @@
 	memset (r, 0, sizeof(struct entropy_store));
 	r->poolinfo = *p;
 
-	r->pool = kmalloc(poolwords*4, GFP_KERNEL);
+	r->pool = kmalloc(POOLBYTES, GFP_KERNEL);
 	if (!r->pool) {
 		kfree(r);
 		return -ENOMEM;
 	}
-	memset(r->pool, 0, poolwords*4);
+	memset(r->pool, 0, POOLBYTES);
 	*ret_bucket = r;
 	return 0;
 }
@@ -524,7 +537,7 @@
 	r->entropy_count = 0;
 	r->input_rotate = 0;
 	r->extract_count = 0;
-	memset(r->pool, 0, r->poolinfo.poolwords*4);
+	memset(r->pool, 0, r->poolinfo.POOLBYTES);
 }
 
 static void free_entropy_store(struct entropy_store *r)
@@ -545,18 +558,19 @@
  * the entropy is concentrated in the low-order bits.
  */
 static void add_entropy_words(struct entropy_store *r, const __u32 *in,
-			     int num)
+			      int nwords)
 {
 	static __u32 const twist_table[8] = {
 		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
 		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
 	unsigned i;
 	int new_rotate;
+	int wordmask = r->poolinfo.poolwords - 1;
 	__u32 w;
 
-	while (num--) {
+	while (nwords--) {
 		w = rotate_left(r->input_rotate, *in);
-		i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
+		i = r->add_ptr = (r->add_ptr - 1) & wordmask;
 		/*
 		 * Normally, we add 7 bits of rotation to the pool.
 		 * At the beginning of the pool, add an extra 7 bits
@@ -569,11 +583,11 @@
 		r->input_rotate = new_rotate & 31;
 
 		/* XOR in the various taps */
-		w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
-		w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
+		w ^= r->pool[(i + r->poolinfo.tap1) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap2) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap3) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap4) & wordmask];
+		w ^= r->pool[(i + r->poolinfo.tap5) & wordmask];
 		w ^= r->pool[i];
 		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
 	}
@@ -582,16 +596,22 @@
 /*
  * Credit (or debit) the entropy store with n bits of entropy
  */
-static void credit_entropy_store(struct entropy_store *r, int num)
+static void credit_entropy_store(struct entropy_store *r, int nbits)
 {
-	int	max_entropy = r->poolinfo.poolwords*32;
-
-	if (r->entropy_count + num < 0)
+	if (r->entropy_count + nbits < 0) {
+		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
+			  r->entropy_count, nbits);
 		r->entropy_count = 0;
-	else if (r->entropy_count + num > max_entropy)
-		r->entropy_count = max_entropy;
-	else
-		r->entropy_count = r->entropy_count + num;
+	} else if (r->entropy_count + nbits > r->poolinfo.POOLBITS) {
+		r->entropy_count = r->poolinfo.POOLBITS;
+	} else {
+		r->entropy_count += nbits;
+		if (nbits)
+			DEBUG_ENT("%s added %d bits, now %d\n",
+				  r == sec_random_state ? "secondary" :
+				  r == random_state ? "primary" : "unknown",
+				  nbits, r->entropy_count);
+	}
 }
 
 /**********************************************************************
@@ -627,6 +647,12 @@
 	return 0;
 }
 
+/*
+ * Changes to the entropy data is put into a queue rather than being added to
+ * the entropy counts directly.  This is presumably to avoid doing heavy
+ * hashing calculations during an interrupt in add_timer_randomness().
+ * Instead, the entropy is only added to the pool once per timer tick.
+ */
 void batch_entropy_store(u32 a, u32 b, int num)
 {
 	int	new;
@@ -643,32 +669,35 @@
 		queue_task(&batch_tqueue, &tq_timer);
 		batch_head = new;
 	} else {
-#if 0
-		printk(KERN_NOTICE "random: batch entropy buffer full\n");
-#endif
+		DEBUG_ENT("batch entropy buffer full\n");
 	}
 }
 
+/*
+ * Flush out the accumulated entropy operations, adding entropy to the passed
+ * store (normally random_state).  If that store has enough entropy, alternate
+ * between randomizing the data of the primary and secondary stores.
+ */
 static void batch_entropy_process(void *private_)
 {
-	int	num = 0;
-	int	max_entropy;
 	struct entropy_store *r	= (struct entropy_store *) private_, *p;
-	
+	int max_entropy = r->poolinfo.POOLBITS;
+
 	if (!batch_max)
 		return;
 
-	max_entropy = r->poolinfo.poolwords*32;
+	p = r;
 	while (batch_head != batch_tail) {
+		if (r->entropy_count >= max_entropy) {
+			r = (r == sec_random_state) ?	random_state :
+							sec_random_state;
+			max_entropy = r->poolinfo.POOLBITS;
+		}
 		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
-		p = r;
-		if (r->entropy_count > max_entropy && (num & 1))
-			r = sec_random_state;
 		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
 		batch_tail = (batch_tail+1) & (batch_max-1);
-		num++;
 	}
-	if (r->entropy_count >= random_read_wakeup_thresh)
+	if (p->entropy_count >= random_read_wakeup_thresh)
 		wake_up_interruptible(&random_read_wait);
 }
 
@@ -1204,9 +1233,9 @@
 
 /*
  * This utility inline function is responsible for transfering entropy
- * from the primary pool to the secondary extraction pool.  We pull 
- * randomness under two conditions; one is if there isn't enough entropy 
- * in the secondary pool.  The other is after we have extract 1024 bytes,
+ * from the primary pool to the secondary extraction pool.  We pull
+ * randomness under two conditions; one is if there isn't enough entropy
+ * in the secondary pool.  The other is after we have extracted 1024 bytes,
  * at which point we do a "catastrophic reseeding".
  */
 static inline void xfer_secondary_pool(struct entropy_store *r,
@@ -1214,14 +1243,26 @@
 {
 	__u32	tmp[TMP_BUF_SIZE];
 
-	if (r->entropy_count < nbytes*8) {
-		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
-		credit_entropy_store(r, TMP_BUF_SIZE*8);
+	if (r->entropy_count < nbytes * 8 &&
+	    r->entropy_count < r->poolinfo.POOLBITS) {
+		int nwords = min(r->poolinfo.poolwords - r->entropy_count/32,
+				 sizeof(tmp) / 4);
+
+		DEBUG_ENT("xfer %d from primary to %s (have %d, need %d)\n",
+			  nwords * 32,
+			  r == sec_random_state ? "secondary" : "unknown",
+			  r->entropy_count, nbytes * 8);
+
+		extract_entropy(random_state, tmp, nwords, 0);
+		add_entropy_words(r, tmp, nwords);
+		credit_entropy_store(r, nwords * 32);
 	}
 	if (r->extract_count > 1024) {
+		DEBUG_ENT("reseeding %s with %d from primary\n",
+			  r == sec_random_state ? "secondary" : "unknown",
+			  sizeof(tmp) * 8);
 		extract_entropy(random_state, tmp, sizeof(tmp), 0);
-		add_entropy_words(r, tmp, TMP_BUF_SIZE);
+		add_entropy_words(r, tmp, sizeof(tmp) / 4);
 		r->extract_count = 0;
 	}
 }
@@ -1232,9 +1273,12 @@
  * bits of entropy are left in the pool, but it does not restrict the
  * number of bytes that are actually obtained.  If the EXTRACT_ENTROPY_USER
  * flag is given, then the buf pointer is assumed to be in user space.
- * If the EXTRACT_ENTROPY_SECONDARY flag is given, then this function will 
  *
- * Note: extract_entropy() assumes that POOLWORDS is a multiple of 16 words.
+ * If the EXTRACT_ENTROPY_SECONDARY flag is given, then we are actually
+ * extracting entropy from the secondary pool, and can refill from the
+ * primary pool if needed.
+ *
+ * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
  */
 static ssize_t extract_entropy(struct entropy_store *r, void * buf,
 			       size_t nbytes, int flags)
@@ -1244,14 +1288,19 @@
 	__u32 x;
 
 	add_timer_randomness(&extract_timer_state, nbytes);
-	
+
 	/* Redundant, but just in case... */
-	if (r->entropy_count > r->poolinfo.poolwords) 
-		r->entropy_count = r->poolinfo.poolwords;
+	if (r->entropy_count > r->poolinfo.POOLBITS)
+		r->entropy_count = r->poolinfo.POOLBITS;
 
 	if (flags & EXTRACT_ENTROPY_SECONDARY)
 		xfer_secondary_pool(r, nbytes);
 
+	DEBUG_ENT("%s has %d bits, want %d bits\n",
+		  r == sec_random_state ? "secondary" :
+		  r == random_state ? "primary" : "unknown",
+		  r->entropy_count, nbytes * 8);
+
 	if (r->entropy_count / 8 >= nbytes)
 		r->entropy_count -= nbytes*8;
 	else
@@ -1547,9 +1596,7 @@
 		c -= bytes;
 		p += bytes;
 
-		/* Convert bytes to words */
-		bytes = (bytes + 3) / sizeof(__u32);
-		add_entropy_words(random_state, buf, bytes);
+		add_entropy_words(random_state, buf, (bytes + 3) / 4);
 	}
 	if (p == buffer) {
 		return (ssize_t)ret;
@@ -1599,7 +1646,7 @@
 			return -EINVAL;
 		if (size > random_state->poolinfo.poolwords)
 			size = random_state->poolinfo.poolwords;
-		if (copy_to_user(p, random_state->pool, size*sizeof(__u32)))
+		if (copy_to_user(p, random_state->pool, size * 4))
 			return -EFAULT;
 		return 0;
 	case RNDADDENTROPY:
@@ -1716,11 +1763,11 @@
 {
 	int	ret;
 
-	sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
 
 	ret = proc_dointvec(table, write, filp, buffer, lenp);
 	if (ret || !write ||
-	    (sysctl_poolsize == random_state->poolinfo.poolwords * 4))
+	    (sysctl_poolsize == random_state->poolinfo.POOLBYTES))
 		return ret;
 
 	return change_poolsize(sysctl_poolsize);
@@ -1732,7 +1779,7 @@
 {
 	int	len;
 	
-	sysctl_poolsize = random_state->poolinfo.poolwords * 4;
+	sysctl_poolsize = random_state->poolinfo.POOLBYTES;
 
 	/*
 	 * We only handle the write case, since the read case gets
@@ -1747,7 +1794,7 @@
 			return -EFAULT;
 	}
 
-	if (sysctl_poolsize != random_state->poolinfo.poolwords * 4)
+	if (sysctl_poolsize != random_state->poolinfo.POOLBYTES)
 		return change_poolsize(sysctl_poolsize);
 
 	return 0;
@@ -1846,8 +1893,7 @@
 {
 	min_read_thresh = 8;
 	min_write_thresh = 0;
-	max_read_thresh = max_write_thresh =
-		random_state->poolinfo.poolwords * 32;
+	max_read_thresh = max_write_thresh = random_state->poolinfo.POOLBITS;
 	random_table[1].data = &random_state->entropy_count;
 }
 #endif 	/* CONFIG_SYSCTL */
@@ -2239,4 +2285,5 @@
 EXPORT_SYMBOL(add_interrupt_randomness);
 EXPORT_SYMBOL(add_blkdev_randomness);
 EXPORT_SYMBOL(batch_entropy_store);
+EXPORT_SYMBOL(generate_random_uuid);
 

	Robert Love