Re: Fortuna

Re: Fortuna

[linux]

>> First, a reminder that the design goal of /dev/random proper is
>> information-theoretic security.  That is, it should be secure against
>> an attacker with infinite computational power.

> I am skeptical.
> I have never seen any convincing evidence for this claim,
> and I suspect that there are cases in which /dev/random fails
> to achieve this standard.

I'm not sure which claim you're skeptical of.  The claim that it's
a design goal, or the claim that it achieves it?


I'm pretty sure that's been the *goal* since the beginning, and it says
so in the comments:
 * Even if it is possible to
 * analyze SHA in some clever way, as long as the amount of data
 * returned from the generator is less than the inherent entropy in
 * the pool, the output data is totally unpredictable. 

That's basically the information-theoretic definition, or at least
alluding to it.  "We're never going to give an attacker the unicity
distance needed to *start* breaking the crypto."

The whole division into two pools was because the original single-pool
design allowed (information-theoretically) deriving previous
/dev/random output from subsequent /dev/urandom output.  That's
discussed in section 5.3 of the paper you cited, and has been fixed.

There's probably more discussion of the subject in linux-kernel around
the time that change went in.


Whether the goal is *achieved* is a different issue.  random.c tries
pretty hard, but makes some concessions to practicality, relying on
computational security as a backup.  (But suggestions as to how to get
closer to the goal are still very much appreciated!)

In particular, it is theoretically possible for an attacker to exploit
knowledge of the state of the pool and the input mixing transform to
feed in data that permutes the pool state to cluster in SHA1 collisions
(thereby reducing output entropy), or to use the SHA1 feedback to induce
state collisions (therby reducing pool entropy).  But that seems to bring
whole new meaning to the word "computationally infeasible", requiring
first preimage solutions over probability distributions.

Also, the entropy estimation may be flawed, and is pretty crude, just
heavily derated for safety.  And given recent developments in keyboard
skiffing, and wireless keyboard deployment, I'm starting to think that
the idea (taken from PGP) of using the keyboard and mouse as an entropy
source is one whose time is past.

Given current processor clock rates and the widespread availability of
high-resolution timers, interrupt synchronization jitter seems like
a much more fruitful source.  I think there are many bits of entropy
in the lsbits of the RDTSC time of interrupts, even from the periodic
timer interrupt!  Even derating that to 0.1 bit per sample, that's still
a veritable flood of seed material.


/dev/random has an even more important design goal of being universally
available; it should never cost enough to make disabling it attractive.
If this conflicts with information-theoretic security, the latter will
be compromised.  But if a practical information-theoretic /dev/random is
(say) just too bulky for embedded systems, perhaps making a scaled-back
version available for such hosts (as a config option) could satisfy
both goals.

Ted, you wrote the thing in the first place; is my summary of the goals
correct?  Would you like comment patches to clarify any of this?


Thank you for pointing out the paper; Appendix A is particularly
interesting.  And the [BST03] reference looks *really* nice!  I haven't
finished it yet, but based on what I've read so far, I'd like to
*strongly* recommnd that any would-be /dev/random hackers read it
carefully.  It can be found at
http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdf

Happily, it *appears* to confirm the value of the LFSR-based input
mixing function.  Although the suggested construction in section 4.1 is
different, and I haven't seen if the proof can be extended.

Re: Fortuna

[Jean-Luc Cooke]

On Sat, Apr 16, 2005 at 11:10:33AM -0000, linux@horizon.com wrote:
> Thank you for pointing out the paper; Appendix A is particularly
> interesting.  And the [BST03] reference looks *really* nice!  I haven't
> finished it yet, but based on what I've read so far, I'd like to
> *strongly* recommnd that any would-be /dev/random hackers read it
> carefully.  It can be found at
> http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdf
> 
> Happily, it *appears* to confirm the value of the LFSR-based input
> mixing function.  Although the suggested construction in section 4.1 is
> different, and I haven't seen if the proof can be extended.

Correct me if I'm wrong here, but uniformity of the linear function isn't
sufficant even if we implemented like this (right now it's more a+X than
a <dot> X).

The part which suggests choosing an irreducible poly and a value "a" in the
preprocessing stage ... last I checked the value for a and the poly need to
be secret.  How do you generate poly and a, Catch-22?  Perhaps I'm missing
something and someone can point it out.

JLC

Re: Fortuna

[linux]

> Correct me if I'm wrong here, but uniformity of the linear function isn't
> sufficent even if we implemented like this (right now it's more a+X than
> a <dot> X).
>
> The part which suggests choosing an irreducible poly and a value "a" in the
> preprocessing stage ... last I checked the value for a and the poly need to
> be secret.  How do you generate poly and a, Catch-22?  Perhaps I'm missing
> something and someone can point it out.

No, the value (the parameter pi) are specifically described as "the public
parameter".  See the "Preprocessing" paragraph at the end of section 1.2
on page 3.  "This string is then hardwired into the implementation and 
need not be kept secret."

All that's required is that the adversary can't tailor his limited
control over the input based on knowing pi.

There's a simple proof in all the papers that if an adversary knows
*everything* about the randomness extraction function, and has total
control over the input distribution, you're screwed.

Basically, suppose you have a 1024-bit input block, the attacker
is required to choose a distribution with at least 1023 bits of entropy,
and you only want 1 bit out.  Should be easy, right?
Well, with any *fixed* function, the possible inputs are divided into
those that hash to 0, and those that hash to 1.  One of those sets
must have at least 2^1023 members.  Suppose it's 0.  The attacker can
choose the input distribution to be "uniformly at random from the
>= 2^1023 inputs that hash to 0" and keep the promise while totally
breaking your extraction function.

But this paper says that if the attacker has to choose 2^t possible
input distributions (based on t bits of control over the input)
*before* the random parameter pi is chosen, then they're locked out.
*After* learning pi, they can choose *which* of the 2^t input
distributions to use.


The thing is, you need a parameterized family of hash functions.
They choose a random multiplier mod GF(2^n).  Their construction
is based on the well-known 2-universal family of hash functions
hash(x) = (a*x+b) mod p.

The /dev/random input mix is based on choosing a "random" polynomial
(since there was a lot of efficiency pressure, it isn't actually very
random; the question is, is it non-random enough to help an attacker).
Remiander modulo a uniformly chosen random irreducible polynomial is a
well-known ("division hash") family of universal hash functions, but
it's a little bit weaker than the above, and I have to figure out of
the proof extends.

Re: Fortuna

[David Wagner]

Jean-Luc Cooke  wrote:
>The part which suggests choosing an irreducible poly and a value "a" in the
>preprocessing stage ... last I checked the value for a and the poly need to
>be secret.  How do you generate poly and a, Catch-22?  Perhaps I'm missing
>something and someone can point it out.

I don't think you're missing anything.  What you say matches my
understanding as well.

Re: Fortuna

[David Wagner]

linux wrote:
>David Wagner wrote:
>>linux wrote:
>>> First, a reminder that the design goal of /dev/random proper is
>>> information-theoretic security.  That is, it should be secure against
>>> an attacker with infinite computational power.
>
>> I am skeptical.
>> I have never seen any convincing evidence for this claim, [..]
>
>I'm not sure which claim you're skeptical of.  The claim that it's
>a design goal, or the claim that it achieves it?

Oops!  Gosh, I was unclear, wasn't it?  Sorry about that.
I meant the latter claim.

I certainly agree that information-theoretic security is a stated goal
of /dev/random.  I'm just not certain that it achieves this goal.
(Caveat: I don't think that failing to achieve this goal is problematic.)

>Whether the goal is *achieved* is a different issue.  random.c tries
>pretty hard, but makes some concessions to practicality, relying on
>computational security as a backup.  (But suggestions as to how to get
>closer to the goal are still very much appreciated!)

Ok.

>In particular, it is theoretically possible for an attacker to exploit
>knowledge of the state of the pool and the input mixing transform to
>feed in data that permutes the pool state to cluster in SHA1 collisions
>(thereby reducing output entropy), or to use the SHA1 feedback to induce
>state collisions (therby reducing pool entropy).  But that seems to bring
>whole new meaning to the word "computationally infeasible", requiring
>first preimage solutions over probability distributions.

Well, wait a second.  You have to make up your mind about whether you
are claiming information-theoretic security, or claiming computational
security.  If the former, then this is absolutely an admissible attack.
There is nothing whatsoever wrong with this attack, from an
information-theoretic point of view.  On the other hand, if we are talking
about computational security, then I totally agree that this is a
(computationally) infeasible attack.

>Also, the entropy estimation may be flawed, and is pretty crude, just
>heavily derated for safety.  And given recent developments in keyboard
>skiffing, and wireless keyboard deployment, I'm starting to think that
>the idea (taken from PGP) of using the keyboard and mouse as an entropy
>source is one whose time is past.
>
>Given current processor clock rates and the widespread availability of
>high-resolution timers, interrupt synchronization jitter seems like
>a much more fruitful source.  I think there are many bits of entropy
>in the lsbits of the RDTSC time of interrupts, even from the periodic
>timer interrupt!  Even derating that to 0.1 bit per sample, that's still
>a veritable flood of seed material.

Makes sense.


As for your question about what one could do to achieve
information-theoretic security, there is a bunch of theoretical work
in the CS theory world on this subject (look up, e.g., "extractors").
Here is my summary about what is possible:

1) If you don't know anything about your source, and you don't
start with any entropy, then information-theoretically secure randomness
extraction is impossible -- at least in principle.  You pick any
deterministic algorithm for randomness extraction, and I will show you
a source for which that algorithm fails.

2) If you start with a short seed of uniformly distributed perfect
randomness, and you have a lower bound on the amount of entropy provided
by your source, then you can extract random bits in a way that is
provably information-theoretically secure.  Note that you don't have
to know anything about the distribution of the source, other than that
its (min-)entropy is not too small.  The simplest construction uses a
2-universal hash function keyed by the seed (its security is established
by the Leftover Hashing Lemma), but there are other constructions,
including a class of schemes known as "extractors".  This approach
does require a short seed of perfect true randomness for every chunk
of output you want to generate, though.

3) If you make certain assumptions about the source, you can extract
entropy in a way that is provably information-theoretically secure,
without needing the short seed.  However, the assumptions required are
typically fairly strong: e.g., that your source is completely memoryless;
that you have multiple sources that are totally independent (i.e.,
uncorrelated in any way); or that your source has a certain structure
(e.g., k of the n bits are uniformly random and independent, and the
other n-k bits are fixed in advance).  People are actively working to
push the boundaries in this category.

I'm not sure whether any of the above will be practically relevant.
They may be too theoretical for real-world use.  But if you're interested,
I could try to give you more information about any of these categories.

Re: Fortuna

[David Wagner]

linux wrote:
>Thank you for pointing out the paper; Appendix A is particularly
>interesting.  And the [BST03] reference looks *really* nice!  I haven't
>finished it yet, but based on what I've read so far, I'd like to
>*strongly* recommnd that any would-be /dev/random hackers read it
>carefully.  It can be found at
>http://www.wisdom.weizmann.ac.il/~tromer/papers/rng.pdf

Yeah, [BST03] seems worth reading.  It has a reasonable survey of some
previous work, and is well-written.

However, I'm pretty skeptical about [BST03] as a basis for a real-world
randomness generator.  It assumes that there are only 2^t possible
distributions for the source, and the set of possible distributions has
been fixed in advance (before the design of your randomness generator
is revealed).  Consequently, it fails to defend against adaptive attacks.

If the attacker can feed in maliciously chosen inputs (chosen after the
attacker learns which randomness extraction algorithm you are using),
then the BST03 scheme promises nothing.  For instance, if you feed in
timings of network packets, then even if you don't count them as providing
any entropy, the mere act of feeding them into your randomness generator
causes their theorems to be clearly inapplicable (since no matter what
value of t you pick, the adversary can arrange to get more than t bits
of freedom in the network packets he sends you).

So I'm not sure [BST03]'s theorems actually promise what you'd want.

On the other hand, if you want to take their constructions as providing
some intuition or ideas about how one might build a randomness generator,
while realizing that their theorems don't apply and there may be no
useful guarantees that can be proven about such an approach, I don't
have any objections to that view.

By the way, another example of work along these lines is
http://theory.lcs.mit.edu/~yevgen/ps/2-ext.ps
That paper is more technical and theoretically-oriented, so it might
be harder to read and less immediately useful.  It makes a strong
assumption (that you have two sources that are independent -- i.e.,
totally uncorrelated), but the construction at the heart of their paper
is pretty simple, which might be of interest.

>Happily, it *appears* to confirm the value of the LFSR-based input
>mixing function.  Although the suggested construction in section 4.1 is
>different, and I haven't seen if the proof can be extended.

Well, I don't know.  I don't think I agree with that interpretation.

Let me give a little background about 2-universal hashing.  There is a
basic result about use of 2-universal hash functions, which says that
if you choose the seed K truly at random, then you can use h_K(X) to
extract uniform random bits from a non-uniform source X.  (Indeed, you
can even reveal K without harming the randomness of h_K(X).)  The proof
of this fact is usually known as the Leftover Hashing Lemma.

One of the standard constructions of a 2-universal hash function is
as a LFSR-like scheme, where the seed K is used to select the feedback
polynomial.  But notice that it is critical that the feedback polynomial
be chosen uniformly at random, in a way that is unpredictable to the
attacker, and kept secret until you receive data from the source.

What /dev/random does is quite different from the idea of 2-universal
hashing developed in the theory literature and recounted in [BST03].
/dev/random fixes a single feedback polynomial in advance, and publishes
it for the world to see.  The theorems about 2-universal hashing promise
nothing about use of a LFSR with a fixed feedback polynomial.

Re: Fortuna

[linux]

Okay, I've merged several e-mails here for compactness...

>> I'm not sure which claim you're skeptical of.  The claim that it's
>> a design goal, or the claim that it achieves it?
>
> Oops!  Gosh, I was unclear, wasn't it?  Sorry about that.
> I meant the latter claim.
>
> I certainly agree that information-theoretic security is a stated goal
> of /dev/random.  I'm just not certain that it achieves this goal.
> (Caveat: I don't think that failing to achieve this goal is problematic.)

Great, there's one point of contention disposed of.  As I said, a
*more* important goal is universal availability.  Theoretical perfection
can be sacrificed to achieve practicality.  In particular, we want
to limit code size, data size, and particularly execution time for
entropy gathering.  Execution time for entropy output is not a major
concern.

>> [Description of attack requiring truly preposterous amount of computaton.]

> Well, wait a second.  You have to make up your mind about whether you
> are claiming information-theoretic security, or claiming computational
> security.  If the former, then this is absolutely an admissible attack.
> There is nothing whatsoever wrong with this attack, from an
> information-theoretic point of view.  On the other hand, if we are talking
> about computational security, then I totally agree that this is a
> (computationally) infeasible attack.

I don't diasgree with anything you're saying, but I'd like to point out
a large grey area between information-theoretic and computation security,
which is "robustness in the face of failure of the crypto primitives".

Computational security would be plenty, and everyone would be happy to
scale back /dev/random's ambitions to that, if we could strictly bound
the amount of effort required for a break.  But until someone comes
up with an explicit hard function (and proves that P != NP), that's
not available.  So all computational security statements are based on
the somewhat unsatisfactory assumption that our cryptographic primtive
is a hard function when we don't actually have a proof that there are any.

And I'm really not up on quantum computing, but there's a whole 'nother
pile of risk that NP-hard might not be hard enough.

Given all that, there is a continual danger that any particular crypto
primitive will be broken.  The recent developments in hash functions
are an excellent example.

So /dev/random, where it relies on computational assumptions, wants to
be very robust in the face of compromise of the primitives.  Like the
example I gave: finding collisions in a hash function is one thing;
the attack I described makes finding a first preimage look easy.

No, it's not information-theoretic secure, but I'm not losing a lot
of sleep worrying about it, either.


But anyway, does that make sense?  The goal is "rely as little as possible
on the unproven hardness of cryptographic functions", which reaches
information-theoretic security in the limit.  So that's the *goal*, but
not reaching it isn't quite *failure*, either.

> As for your question about what one could do to achieve
> information-theoretic security, there is a bunch of theoretical work
> in the CS theory world on this subject (look up, e.g., "extractors").
> Here is my summary about what is possible:

Thank you very much.  I've been reading on the subject and learned this,
but it's nice to have it confirmed that I didn't miss anything.

> [Descrptions snipped for conciseness]

Given that we *do* have multiple mostly-independent sources,
perhaps the two-source construction could be adapted.  What would be
really nice is if it could be extended to n sources such that if any
pair were independent, it would be secure.

Oh, duh, that's trivial... run the two-source construction over every
pair of sources, and XOR all the outputs together.  Of course,
I still need to take care of that nasty word "mostly".

Even if that's horribly inefficient, it could be used to bootstrap a short
seed to start an efficient seed-using extractor.

> 3) If you make certain assumptions about the source, you can extract
> entropy in a way that is provably information-theoretically secure,
> without needing the short seed.  However, the assumptions required are
> typically fairly strong: e.g., that your source is completely memoryless;
> that you have multiple sources that are totally independent (i.e.,
> uncorrelated in any way); or that your source has a certain structure
> (e.g., k of the n bits are uniformly random and independent, and the
> other n-k bits are fixed in advance).  People are actively working to
> push the boundaries in this category.

[BST03] added a nice one to this: if your source can't adapt to
your seed, you can use a fixed seed.

Also, unless I'm misunderstanding the definition very badly, any "strong
extractor" can use a fixed secret seed.

> I'm not sure whether any of the above will be practically relevant.
> They may be too theoretical for real-world use.  But if you're interested,
> I could try to give you more information about any of these categories.

I'm doing some reading to see if something practical can be dug out of the
pile.  I'm also looking at "compressors", which are a lot like our random
pools; they reduce the size of an input while preserving its entropy,
just not necesarily to 100% density like an extractor.

This is attractive because our entropy measurement is known to be
heavily derated for safety.  An extractor, in producing an output that
is as large as our guaranteed entropy, will throw away any additional
entropy that might be remaining.

Th other thing that I absolutely need is some guarantee that things will
still mostly work if our entropy estimate is wrong.  If /dev/random
produces 128 bits of output that only have 120 bits of entropy in them,
then your encryption is still secure.  But these extractor constructions
are very simple and linear.  If everything falls apart if I overestimate
the source entropy by 1 bit, it's probably a bad idea.  Maybe it can be
salvaged with some cryptographic techniques as backup.

>> 3) Fortuna's design doesn't actually *work*.  The authors' analysis
>>    only works in the case that the entropy seeds are independent, but
>>    forgot to state the assumption.  Some people reviewing the design
>>    don't notice the omission.

> Ok, now I understand your objection.  Yup, this is a real objection.
> You are right to ask questions about whether this is a reasonable assumption.
>
> I don't know whether /dev/random makes the same assumption.  I suspect that
> its entropy estimator is making a similar assumption (not exactly the same
> one), but I don't know for sure.

Well, the entropy *accumulator* doesn't use any such assumption.
Fortuna uses the independence assumption when it divides up the seed
material round-robin among the various subpools.  The current /dev/random
doesn't do anything like that.  (Of course, non-independence affects
us by limiting us to the conditional entropy of any given piece of
seed material.)

> I also don't know whether this is a realistic assumption to make about
> the physical sources we currently feed into /dev/random.  That would require
> some analysis of the physics of those sources, and I don't have the skills
> it would take to do that kind of analysis.

And given the variety of platforms that Linux runs on, it gets insane.
Yes, it can be proved based on fluid flow computations that hard drive
rotation rates are chaotic and thus disk access timing is a usable
entropy source, but then someone installs a solid-state disk.

That's why I like clock jitter.  That just requires studying oscillators
and PLLs, which are universal across all platforms.

> Actually, this example scenario is not a problem.  I'll finish the
> analysis for you.

Er... thank you, but I already knew that; I omitted the completion
because it seemed obvious.  And yes, there are many other distributions
which are worse.

But your 200-round assumption is flawed; I'm assuming the Fortuna
schedule, which is that subpool i is dumped into the main pool (and
thus inforation-theoretically available at the output) every 2^i
rounds.  So the second pool is dumped in every 2 rounds, not every 200.
And with 1/3 the entropy rate, if the first pool is brute-forceable
(which is our basic assumption), then the second one certainly is.

Now, this simple construction doesn't extend to more pools, but it's
trying to point out the lack of a *disproof* of a source distribution
where higher-order pools get exponentially less entropy per seed
due to the exposure of lower-order pools.

Which would turn Fortuna into an elaborate exercise in bit-shuffling
for no security benefit at all.

This can all be dimly seen through the papers on extractors, where
low-k sources are really hard to work with; all the designs want you
to accumulate enough input to get a large k.

> If you want a better example of where the two-pool scheme completely
> falls apart, consider this: our source picks a random bit, uses this
> same bit the next two times it is queried, and then picks a new bit.
> Its sequence of outputs will look like (b0,b0,b1,b1,b2,b2,..,).  If
> we alternate pools, then the first pool sees the sequence b0,b1,b2,..
> and the second pool sees exactly the same sequence.  Consequently, an
> adversary who can observe the entire evolution of the first pool can
> deduce everything there is to know about the second pool.  This just
> illustrates that these multiple-pool solutions make some assumptions
> about the time-independence of their sources, or at least that the bits
> going into one pool don't have too much correlation with the bits going
> into the other pool.

Yes, exactly.  I had a more elaborate construction (based on a shift
register as long as the number of pools) that actually delivered one
fresh shiny bit of conditional entropy per source sample and yet still
totally broke Fortuna.

What I'd like to figure out is a way of expressing what the correlation
requirements *are* for Fortuna to be secure.  Then we could have a
meaningful discussion as to whether real-world sources meet those
conditions.


> Yeah, [BST03] seems worth reading.  It has a reasonable survey of some
> previous work, and is well-written.
>
> However, I'm pretty skeptical about [BST03] as a basis for a real-world
> randomness generator.  It assumes that there are only 2^t possible
> distributions for the source, and the set of possible distributions has
> been fixed in advance (before the design of your randomness generator
> is revealed).  Consequently, it fails to defend against adaptive attacks.

Yes, but as the authors claim, if you can use physics/hardware arguments
to *bound* the extent of the adaptability (which is what their parameter
t is all about), then you can used a fixed-parameter extractor.

Just for future reference, the usual extractor parameters are:
n = Input size (bits)
k = Input entropy (min-entropy measure, not Shanon!)
m = Output size (<= k)
eps (epsilon, really) = Statistical distance from perfect uniformity,
   a very small number that measures the quality of the output.
   Technically, it's 1/2 the sum, over all 2^m possible outputs x,
   of abs(probability(output = x) - 1/(2^m)).  The worst possible
   value, for a constant function, approaches 1 (actually 1 - 1/(2^m)).

> If the attacker can feed in maliciously chosen inputs (chosen after the
> attacker learns which randomness extraction algorithm you are using),
> then the BST03 scheme promises nothing.  For instance, if you feed in
> timings of network packets, then even if you don't count them as providing
> any entropy, the mere act of feeding them into your randomness generator
> causes their theorems to be clearly inapplicable (since no matter what
> value of t you pick, the adversary can arrange to get more than t bits
> of freedom in the network packets he sends you).

That wouldn't be a problem if we could extract the k bits of entropy
from the m-t uncontrolled degrees of freedom; just make m proportional
to the non-malicious source rate.

However, their proof only works for m =  k - 2*t - 4*log(1/eps) - 2.
Malicious bits count twice as bad as known bits, so a source that's more
than half malicious bits is useless.

It may turn out that trying to use this for information-theoretic security
requires throwing out bits we can't prove aren't malicious, which would
require giving up so many possibly good bits that we don't want to do it.

But the seeded extractors still look promising.  They don't care how
the n-k non-random input bits are chosen.

> One of the standard constructions of a 2-universal hash function is
> as a LFSR-like scheme, where the seed K is used to select the feedback
> polynomial.  But notice that it is critical that the feedback polynomial
> be chosen uniformly at random, in a way that is unpredictable to the
> attacker, and kept secret until you receive data from the source.

Ah, it *is* a 2-universal hash, good.  I was getting confused between
2-universal hash and epsilon-almost universal hash, and wasn't quite
sure if the definitions were compatible.

> What /dev/random does is quite different from the idea of 2-universal
> hashing developed in the theory literature and recounted in [BST03].
> /dev/random fixes a single feedback polynomial in advance, and publishes
> it for the world to see.  The theorems about 2-universal hashing promise
> nothing about use of a LFSR with a fixed feedback polynomial.

I know it doesn't, but what it *does* say mirrors what the /dev/random
soruce says... *if* the source is *not* adaptive to the polynomial,
*then* it's a good extractor.

The tolerance of malicious inputs is a separate argument based on the
reversibility of the LFSR input mix and the computational infeasibility
of creating collisions in the output mixing function.  This is the
the attack I pointed out a couple of messages ago, but it's such
a hard problem that I'm not worried about it.

Briefly, suppose an attacker has partial information about the state
of the input pool.  This can be expressed as a list of probabilities
for each of the 2^4096 possible states.  The attacker can feed whatever
data he likes into the input hash, and the effect will only be to
permute those states, which won't change the Shannon- or min-entropy
measures of the pool in any way.

The only thing the attacker can do is try to cluster those states in
places that cause hash collisions.  By feeding data to the input
mix, he can:
- Multiply the state of the pool by any desired power of x (mod the
  polynomial), and
- XOR the pool with any desired number.
If the attacker can use this freedom, combined with *partial* knowledge
of the pool, to cause excess collisions in the output mixing function,
he can (partially) control the RNG output.   (The fact that the attacker
is limited to 2^8192 of the (2^4096)! possible state permutations
definitely limits him somewhat.  As does the fact that he can't actually
multiply by *any* power of x, since the time taken is proportional to
the power, and not all 2^4096-1 possibilities can be reached before
the sun goes nova.)


But what I am figuring out is that *if* we can consider the input stream
to be a sort of bit-fixing source (some bits of the input are *not*
observable or controllable by the attacker), then the current LFSR is
a decent concentrator.  That seems like a pretty plausible assumption,
and applies no matter how large a fraction of the input is under enemy
control, as long as we account for the entropy properly.

In particular, this gets our input entropy k up to a reasonable fraction
of our input block size n, which makes the information-theoretic extractors
work better.  (The downside is that it's no longer a bit-fixing source.)

If we can then add an information-theoretic extractor as an output hash,
things are looking very promising.  First of all, this is not a performance-
critical step, so I have a lot of run-time to play with.  And second, the
first-stage concentrator has got k up to a reasonable fraction of the
input block size n, which helps all of the extractor constructions.

(Further, I can limit my extractor function to a fixed output size m,
chosen to be a suitable catastrophic-reseed value for subsequent stages.)

I'm sure the Leftover Hash Lemma applies here, and I've found a couple of
statements of it, but I don't *quite* understand it yet.  That is, I
understand one statement ("If H is a universal hash family from n bits
to l bits, where l = k - 2 * log(1/eps), then Ext(x,h) = (h, h(x)) is
a (k,eps)-extractor."), but I don't see how it's the same as the
other, which indicates that my understanding is incomplete.  But I'm
still working on it.


Anyway, thanks a lot for all the pointers!

Re: Fortuna

[linux]

>> /dev/urandom depends on the strength of the crypto primitives.
>> /dev/random does not.  All it needs is a good uniform hash.
> 
> That's not at all clear.  I'll go farther: I think it is unlikely
> to be true.
> 
> If you want to think about cryptographic primitives being arbitrarily
> broken, I think there will be scenarios where /dev/random is insecure.
> 
> As for what you mean by "good uniform hash", I think you'll need to
> be a bit more precise.

Well, you just pointed me to a very nice paper that *makes* it precise:

Boaz Barak, Ronen Shaltiel, and Eran Tromer. True random number generators
secure in a changing environment. In Workshop on Cryptographic Hardware
and Embedded Systems (CHES), pages 166-180, 2003. LNCS no. 2779.

I haven't worked through all the proofs yet, but it looks to be highly
applicable.

>> Do a bit of reading on the subject of "unicity distance".
> 
> Yes, I've read Shannon's original paper on the subject, as well
> as many other treatments.

I hope it's obvious that I didn't mean to patronize *you* with such
a suggestion!  Clearly, you're intimately familiar with the concept,
and any discussion can go straight on to more detailed issues.

I just hope you'll grant me that understanding the concept is pretty
fundamental to any meaningful discussion of information-theoretic
security.

> I stand by my comments above.

Cool!  So there's a problem to be solved!

Re: Fortuna

[linux]

Just to refersh everyone's memory as to the strengths and weaknesses
of Fortuna...

First, a reminder that the design goal of /dev/random proper is
information-theoretic security.  That is, it should be secure against
an attacker with infinite computational power.  If you want a weaker
guarantee, use /dev/urandom.

I've heard a suggestion that something like /dev/urandom, but which blocks
until it has received a minimum amount of seed material at least once,
would be a nice thing.  So boot-time crypto initialization can stall
until it has achieved a minimum level of security.

The minimum could be measured two ways:
- Some reasonable default, like 256 bits, or
- (clever) the size of the read() request, which is presumably the
  key size that the user needs.  This might be too subtle to explain
  to programmers, though.


Anyway, there are two main parts to Fortuna.  The central "random pool",
and the round-robin sub-pool system for reseeding the main pool.

Fortuna uses a "small pool, trust the crypto" central pool.
/dev/random uses a large pool that is deliberately designed to be
robust against failure of the crypto primitives.  Indeed, the basic
design just uses it as a uniform hash.  Cryptographic strength is
irrelevant to the information-theoretic guarantees.

This portion of Fortuna is at odds with /dev/random's design goals,
but it could be replaced easily enough.  It's not the clever part.


The "neat idea" in Fortuna is the round-robin sub-pool seeding technique,
which attempts to avoid the entire issue of entropy estimation.

Now, for information-theoretic guarantees, entropy measurement is
*required*.  You cannot be information-theoretic secure unless you
have received more seed entropy than you have produced output.

However, Fortuna has a different philosophy.  This difference is why
Fortuna will NEVER be an "exact drop-in replacement" for /dev/random,
although it can do the job for /dev/urandom.  There are important
user-visible differences in the guarantees it makes.  Someone may
argue that the difference is immaterial in practice, but existence of
a difference is indisputable.


It tries to divide up the seed entropy into sub-pools and hold off
re-seeding the main pool until the sub-pool has accumulated enough entropy
to cause "catastrophic reseeding" of the main pool, adding enough entropy
at once that someone who had captured the prior state of the main pool
would not be able (due to computational limits and the one-way nature
of the pool output function) to reverse-engineer the post-state.

The way it schedules the additions, it doesn't know *which* re-seed of
the main pool will be catastrophic, but it knows that it will be within
a factor of 64 of the shortest time that's possible.


However, it possible to come up with some pathological entropy sources
for which the standard Fortuna design completely fails to achieve that
goal.

So Fortuna would be helped by some better understanding of what exactly
makes it fail, so the discussion could move to whether real-world
seed sources have those properties.

But until that understanding is gained, Fortuna is questionable.


Appendix: how to "break" Fortuna.

First, the standard assumptions: the "attacker" can collect arbitrary
amounts of RNG output at any time, and can see all operations on the
pool except for the value of the seed material.

In particular, if the attacker's uncertainty about the pool's state
is small, she can collect enough output to distinguish all the
possibilities and attempt a brute-force computation to recover the
unknown state information.

Finally, assume the attacker knows the full initial state of the
generator.

For a classic 32-subpool Fortuna, let the seed be a 32-bit integer.
Every time a new seed is produced, shift the previous value and insert
a fresh random bit.  Thus, the seed does deliver 1 bit of entropy
per sample, which should make for a secure source.

If you want to be cruel, encrypt that seed with a strong cipher known
only to the attacker before producing output.  That keeps the nature
of the seed from the Fortuna implementation.

Anyway, every 32 cycles, a seed word is added to subpool 0, which is then
immediately added to the main pool.  An attacker who knows the prior
state of the main pool can attempt a brute-force search for the 32 bits
of the seed word in a reasonable period of time.

Because of the shifting property, an attacker who knows the seeds added
to pool 0 at times t and t+32 can also deduce, with perfect accuracy,
the seeds added to the other 31 pools at times t+1 through t+31.

The result being that the other subpools, which are supposed to be hoarding
secret information unknown to the attacker, are actually being seeded with
bits known to the attacker.

The ultimate result is that catastrohpic reseeding never takes place.
If we could somehow separate the "fresh" entropy in the input samples
from the "holdover" material, the problem would go away, but that's
an entropy measurement problem!

Until this cloud is dissipated by further analysis, it's not possible to
say "this is shiny and new and better; they's use it!" in good conscience.

Re: Fortuna

[Theodore Ts'o]

On Thu, Apr 14, 2005 at 02:15:38PM -0000, linux@horizon.com wrote:
> I've heard a suggestion that something like /dev/urandom, but which blocks
> until it has received a minimum amount of seed material at least once,
> would be a nice thing.  So boot-time crypto initialization can stall
> until it has achieved a minimum level of security.

With a properly set up set of init scripts, /dev/random is initialized
with seed material for all but the initial boot (and even that problem
can be solved by having the distribution's install scripts set up
/var/lib/urandom/random-seed after installing the system).

If the init scripts aren't set up correctly, then you're screwed, yes,
but (a) all distributions that I know do the init scripts correctly,
and the right of doing this is documented in random.c, and (b) if user
space is screwed up in other ways, you can even worse off.

What if someone accesses the seed file directly before the machine
boots?  Well, either (a) they have broken root already, or (b) have
direct access to the disk.  In either case, the attacker with such
powers can just has easily trojan an executable or a kernel, and
you've got far worse problems to worry about that the piddling worries
of (cue Gilbert and Sullivan overly dramatic music, <Oh, horror!>) the
dreaded state-extension attack.

> It tries to divide up the seed entropy into sub-pools and hold off
> re-seeding the main pool until the sub-pool has accumulated enough entropy
> to cause "catastrophic reseeding" of the main pool, adding enough entropy
> at once that someone who had captured the prior state of the main pool
> would not be able (due to computational limits and the one-way nature
> of the pool output function) to reverse-engineer the post-state.

Actually, if you check the current random.c code, you'll see that it
has catastrophic reseeding in its design already.

> So Fortuna would be helped by some better understanding of what exactly
> makes it fail, so the discussion could move to whether real-world
> seed sources have those properties.
> 
> But until that understanding is gained, Fortuna is questionable.
>...
> Until this cloud is dissipated by further analysis, it's not possible to
> say "this is shiny and new and better; they's use it!" in good conscience.

My big concern with Fortuna is that it really is the result of
cryptographic masturbation.  It fundamentally assumes that crypto
primitives are secure (when the recent break of MD4, MD5, and now SHA1
should have been a warning that this is a Bad Idea (tm)), and makes
assumptions that have no real world significance (assume the attacker
has enough privileges that he might as well be superuser and can
trojan your system to a fare-thee-well ---- now, if you can't recover
from a state extension attack, your random number generator is fatally
flawed.)

In addition, Frotuna is profligate with entropy, and wastes it in
order to be able make certain claims of being able to recover from a
state-extension attack.  Hopefully everyone agrees that entropy
collected from the hardware is precious (especially if you don't have
special-purpose a hardware RNG), and shouldn't be wasted.  Wasting
collected entropy for no benefit, only to protect against a largely
theoretical attack --- where if a bad guy has enough privileges to
compromise your RNG state, there are far easier ways to compromise
your entire system, not just the RNG --- is Just Stupid(tm).

						- Ted

Re: Fortuna

[linux]

> What if someone accesses the seed file directly before the machine
> boots?  Well, either (a) they have broken root already, or (b) have
> direct access to the disk.  In either case, the attacker with such
> powers can just has easily trojan an executable or a kernel, and
> you've got far worse problems to worry about that the piddling worries
> of (cue Gilbert and Sullivan overly dramatic music, <Oh, horror!>) the
> dreaded state-extension attack.

So the only remaining case is where an attacker can read the random
seed file before boot but can't install any trojans.  Which seems
like an awfully small case.  (Although in some scenarios, passive
attacks are much easier to mount than active ones.)

> Actually, if you check the current random.c code, you'll see that it
> has catastrophic reseeding in its design already.

Yes, I know.  Fortuna's claim to fame is that it tries to achieve that
without explicitly measuring entropy.

> My big concern with Fortuna is that it really is the result of
> cryptographic masturbation.  It fundamentally assumes that crypto
> primitives are secure (when the recent break of MD4, MD5, and now SHA1
> should have been a warning that this is a Bad Idea (tm)), and makes
> assumptions that have no real world significance (assume the attacker
> has enough privileges that he might as well be superuser and can
> trojan your system to a fare-thee-well ---- now, if you can't recover
> from a state extension attack, your random number generator is fatally
> flawed.)

I'm not a big fan of Fortuna either, but the issues are separate.
I agree that trusting crypto prmitives that you don't have to is a bad
idea.  If my application depends on SHA1 being secure, then I might as
well go ahead and use SHA1 in my PRNG.  But a kernel service doesn't
know what applications are relying on.

(Speaking of which, perhaps it's time, in light of the breaking of MD5,
to revisit the cut-down MD4 routine used in the TCP ISN selection?
I haven't read the MD5 & SHA1 papers in enough detail to understand the
flaw, but perhaps some defenses could be erected?)

But still, all else being equal, an RNG resistant to a state extension
attack *is* preferable to one that's not.  And the catastrophic
reseeding support in /dev/random provides exactly that feature.

What Fortuna tries to do is sidestep the hard problem of entropy
measurement.  And that's very admirable.  It's a very hard thing to do in
general, and the current technique of heuristics plus a lot of derating
is merely adequate.

If a technique could be developed that didn't need an accurate entropy
measurement, then things would be much better.


> In addition, Frotuna is profligate with entropy, and wastes it in
> order to be able make certain claims of being able to recover from a
> state-extension attack.  Hopefully everyone agrees that entropy
> collected from the hardware is precious (especially if you don't have
> special-purpose a hardware RNG), and shouldn't be wasted.  Wasting
> collected entropy for no benefit, only to protect against a largely
> theoretical attack --- where if a bad guy has enough privileges to
> compromise your RNG state, there are far easier ways to compromise
> your entire system, not just the RNG --- is Just Stupid(tm).

Just to be clear, I don't remember it ever throwing entropy away, but
it hoards some for years, thereby making it effectively unavailable.
Any catastrophic reseeding solution has to hold back entropy for some
time.

And I think that, even in the absence of special-purpose RNG hardware,
synchronization jitter on modern GHz+ CPUs is a fruitful source of
entropy.

Re: Fortuna

[Theodore Ts'o]

On Fri, Apr 15, 2005 at 01:34:17AM -0000, linux@horizon.com wrote:
> (Speaking of which, perhaps it's time, in light of the breaking of MD5,
> to revisit the cut-down MD4 routine used in the TCP ISN selection?
> I haven't read the MD5 & SHA1 papers in enough detail to understand the
> flaw, but perhaps some defenses could be erected?)

The ISN selection is there only to make it harder to accomplish TCP
hijacking attacks from people who are on networking path between the
source and destination.  And you have to guess the ISI before the
3-way TCP handshake has been negotiated (or if you can stop the SYN
packet in flight, before the other side times out the attempted TCP
connection); and we also rekey every few minutes, so even if you do
figure out the seed that we are using to generate the ISI (which is
harder than just merely finding a hash collision; find the preimage
that we are using as a seed given the only a portion of the crypto
hash output), it becomes useless and you have to start all over again
within a few minutes.

Furthermore, if you really cared about preventing TCP hijacks, the
only real way to do this is to use Real Crypto.  And these days, Cisco
boxes support Kerberized telnets and ssh connections, which is the
real Right Answer.

It might be possible to use a more expensive crypto primitive here,
since CPU's have gotten so much faster, but the reason why we moved to
MD4, and then cut it down, was because otherwise it was causing a
noticeable difference in the speed we could establish TCP connections,
and hence for certain network-based benchmarks.

> Just to be clear, I don't remember it ever throwing entropy away, but
> it hoards some for years, thereby making it effectively unavailable.
> Any catastrophic reseeding solution has to hold back entropy for some
> time.

It depends on how often you reseed, but my recollection was that it
was far more than years; it was *centuries*.  And as far as I'm
concerned, that's equivalent to throwing it away, especially given the
pathetically small size of the Fortuna pools.

							- Ted

Re: Fortuna

[linux]

> The ISN selection is there only to make it harder to accomplish TCP
> hijacking attacks from people who are on networking path between the
> source and destination.  And you have to guess the ISI before the
> 3-way TCP handshake has been negotiated (or if you can stop the SYN
> packet in flight, before the other side times out the attempted TCP
> connection); and we also rekey every few minutes, so even if you do
> figure out the seed that we are using to generate the ISI (which is
> harder than just merely finding a hash collision; find the preimage
> that we are using as a seed given the only a portion of the crypto
> hash output), it becomes useless and you have to start all over again
> within a few minutes.

Er... are you sure that's right?  I think there are several mistakes
there.

First of all, people *on* the netowrk path can just *see* the packets.
Or modify them.  Or whatever.
The point is to prevent hijacking by people *not* on the path.
Such people can only blindly inject forged packets, and try to send
"passwd\nhax0r\nhax0r\n" into an open telnet connection.  Or sending
FINs to DoS.

Such injection requires guessing the TCP sequence number.  That depends
on the ISN plus the number of bytes sent.  Fortunately, some of the most
interesting protocols to attack are interactive ones like telnet where
the number of bytes sent is small and the uncertainty can be exhausted
with a flood of packets.

The problem was to prevent someone from connecting to endpoints A and B
and using the ISN they received to guess the ISNs that A and B would use
to talk to each other.  The classic TCP ISN algorithm just uses a global
timestamp, so it's pretty easy.

Further, if I capture ISNs from A and B in the same rekey interval as
the initiation of the connection I'm trying to hijack, and that
connection proceeds slowly, then I have the lifetime of the connection
to solve the crypto problem.


All that said, you are quite right (I had just figured it out myself,
actually) that the required attack is a (first) preimage attack (albeit
with partially known plaintext), not a collision, so the published
collision attacks are not directly relevant.  And the fact that the
amount of hash output is not enough to determine the input key material
so you have to make multiple probes with dirrecnt port numbers, and
it's all masked by a high-speed clock that you can only come close to
guessing the value of, makes it all even nastier for a would-be
cryptanalyst.

> Furthermore, if you really cared about preventing TCP hijacks, the
> only real way to do this is to use Real Crypto.  And these days, Cisco
> boxes support Kerberized telnets and ssh connections, which is the
> real Right Answer.

It's just so high-level.  While ipsec is the most general solution,
setting it up is a PITA.  I've often thought about trying to add a TCP
option for stream encryption what could provide opportunistic encryption
for everyone.


> It might be possible to use a more expensive crypto primitive here,
> since CPU's have gotten so much faster, but the reason why we moved to
> MD4, and then cut it down, was because otherwise it was causing a
> noticeable difference in the speed we could establish TCP connections,
> and hence for certain network-based benchmarks.

Yes, I recall.  I was more thinking that the MD5 and SHA0 problems were
insufficient mixing between columns of bits, and even SHA1 still has
the problem.  Notice how much more aggressive the shifting is in the
SHA256 key schedule.

As long as it's homebrew ad-hoc crypto, perhaps some study of the
attacks could suggest a better key schedule than just using the key
words in different orders and with different constants added.

>> Just to be clear, I don't remember it ever throwing entropy away, but
>> it hoards some for years, thereby making it effectively unavailable.
>> Any catastrophic reseeding solution has to hold back entropy for some
>> time.

> It depends on how often you reseed, but my recollection was that it
> was far more than years; it was *centuries*.  And as far as I'm
> concerned, that's equivalent to throwing it away, especially given the
> pathetically small size of the Fortuna pools.

Well, subpool n is added to the main pool every 1/2^n additions of
subpool 0.  So with pool 0 added every 0.1 second (say), then
subpool 31 is added every 6.8 years.

But the whole things depends on a minimum assumed entropy feed rate.
The idea is to be sure that *some* subpool will hoard entropy long
enough to cause catastrophic reseeding.  You can reduce the number
of subpools to fit any arbitrary bound.

E.g. if you think that 24 hours is long enough, and you have the same
0.1 second maximum reseed rate, then 21 pools will have pool 20 added
every 29:07:37.6.

As I keep saying, the small size of the Fortuna pools is a separate
matter, and can be changed without affecting the subpool structure that
is Fortuna's real novel contribution.  That was just what Niels and
Bruce came up with to make the whole thing concrete.

Re: Fortuna

[Theodore Ts'o]

On Fri, Apr 15, 2005 at 03:38:01PM -0000, linux@horizon.com wrote:
> 
> First of all, people *on* the netowrk path can just *see* the packets.
> Or modify them.  Or whatever.
> The point is to prevent hijacking by people *not* on the path.

Yes, you're correct of course.  Of course, I'll note that people who
*not* on the path have to not only guess the ISN, but they also have
to somehow know that there is a TCP connection between hosts A and B,
and what ports they are using.  Someone not on the path isn't
necessarily going to know this, unless there are publically accessible
SNMP-enabled routers that are overly free with this sort of
information.  (Loose lips sink ships!)

> Further, if I capture ISNs from A and B in the same rekey interval as
> the initiation of the connection I'm trying to hijack, and that
> connection proceeds slowly, then I have the lifetime of the connection
> to solve the crypto problem.

True, although the longer it takes to break the crypto, the greater
the uncertainty of how much data has gone across the connection, which
makes the problem harder in other ways.

> > Furthermore, if you really cared about preventing TCP hijacks, the
> > only real way to do this is to use Real Crypto.  And these days, Cisco
> > boxes support Kerberized telnets and ssh connections, which is the
> > real Right Answer.
> 
> It's just so high-level.  While ipsec is the most general solution,
> setting it up is a PITA.  I've often thought about trying to add a TCP
> option for stream encryption what could provide opportunistic encryption
> for everyone.

But ssh is pretty easy, and even if you completely ignore the host key
issue (to protect you against man-in-the-middle attacks), a simple
diffie-helman type approach is plenty to protect you against the class
of attacks which the randomized ISN buys you.  

						- Ted

Re: Fortuna

[Jean-Luc Cooke]

On Fri, Apr 15, 2005 at 10:42:16AM -0400, Theodore Ts'o wrote:
> > Just to be clear, I don't remember it ever throwing entropy away, but
> > it hoards some for years, thereby making it effectively unavailable.
> > Any catastrophic reseeding solution has to hold back entropy for some
> > time.
> 
> It depends on how often you reseed, but my recollection was that it
> was far more than years; it was *centuries*.  And as far as I'm
> concerned, that's equivalent to throwing it away, especially given the
> pathetically small size of the Fortuna pools.

"pathetically" is an interesting term to call it.  256 bits is the most any
one of the 32 pools can hold, true.  And the n-th pool is used only once
every 2^n times (where the first pool is the 0-th pool, hence it's used
everytime).

2^31 * 0.1s reseeds, mean the 31st (aka. last) pool will be drawn from once
every 6.8 years.

And the argument that "random.c doesn't rely on the strength of crypto
primitives" is kinda lame, though I see where you're coming from.  random.c's
entropy mixing and output depends on the (endian incorrect) SHA-1
implementation hard coded in that file to be pre-image resistant.  If that
fails (and a few other things) then it's broken.

Fortuna depends on known cipher-text attacks on the cipher in use (in this
case AES-256) and the digest algo in use (in this case SHA-256) to be
pre-image resistant.  Cryptographers like reducing things to known
quantities, it may be flaw.

Once I set some personal things sorted out I'll take another crack at making
/dev/fortuna with it's claws in random.c to feed it some of that entropy as 
linux@horizon.com suggested.

JLC

Re: Fortuna

[linux]

> And the argument that "random.c doesn't rely on the strength of crypto
> primitives" is kinda lame, though I see where you're coming from.
> random.c's entropy mixing and output depends on the (endian incorrect)
> SHA-1 implementation hard coded in that file to be pre-image resistant.
> If that fails (and a few other things) then it's broken.

/dev/urandom depends on the strength of the crypto primitives.
/dev/random does not.  All it needs is a good uniform hash.

Do a bit of reading on the subject of "unicity distance".

(And as for the endianness of the SHA-1, are you trying to imply
something?  Because it makes zero difference, and reduces the code
size and execution time.  Which is obviously a Good Thing.)


As for hacking Fortuna in, could you give a clear statement of what
you're trying to achieve?

Do you like:
- The neat name,
- The strong ciphers used in the pools, or
- The multi-pool reseeding strategy, or
- Something else?

If you're doing it just for hack value, or to learn how to write a
device driver or whatever, then fine.  But if you're proposing it as
a mainline patch, then could we discuss the technical goals?

I don't think anyone wants to draw and quarter *you*, but your
code is going to get some extremely critical examination.

Re: Fortuna

[Jean-Luc Cooke]

On Fri, Apr 15, 2005 at 04:50:36PM -0000, linux@horizon.com wrote:
> (And as for the endianness of the SHA-1, are you trying to imply
> something?  Because it makes zero difference, and reduces the code
> size and execution time.  Which is obviously a Good Thing.)

It just bugged me when I was reading random.c for the first time.  First
impressions and all.

> As for hacking Fortuna in, could you give a clear statement of what
> you're trying to achieve?
> 
> Do you like:
> - The neat name,
> - The strong ciphers used in the pools, or
> - The multi-pool reseeding strategy, or
> - Something else?
> 
> If you're doing it just for hack value, or to learn how to write a
> device driver or whatever, then fine.  But if you're proposing it as
> a mainline patch, then could we discuss the technical goals?
> 
> I don't think anyone wants to draw and quarter *you*, but your
> code is going to get some extremely critical examination.

The multi-pool reseeding strategy is what I find particular interesting.
It's design that can fit neatly into my little head and I hope into the heads
of others in the future.  You can call it Bob or whatever you want, names
doesn't matter to me.  As for the ciphers/digest algos used, they are
not if great concern to me, replace them with what you want.  It's the design
of the RNG itself that has my attention for the time being.

Ted and yourself are in the nest position to say "we understand random.c
currently, and should be need arise, we can feel strong enough that we can
find someone to take it over and go up the learning curve" and with a
statement "we like the current RNG design now for mixing entropy and don't
see the need to confuse people with alternatives to /dev/{u}random" and
that'll be that.

I'll take my patch and not bother you anymore.  I'm sure I've taken a lot of
your time as it is.

Not to sound like a "I'm taking my ball and going home" - just explaining
that I like the Fortuna design, I think it's elegant, I want it for my
systems.  GPL requires I submit changes back, so I did with the unpleasant
side-dish of my opinion on random.c.

JLC

Re: Fortuna

[linux]

MErging e-mails, first from mpm@selenic.com:
> You really ought to look at the _current_ implementation. There is no
> SHA1 code in random.c. 

So I'm imagining the call to sha_transform() in 2.6.12-rc2's
extract_buf()?  The SHA1 code has been moved to lib/sha1.c, so there's
no SHA1 code *lexically* in random.c, but that's a facile response;
it's a cryptologically meaningless change.

The way it's done, the length ends up being byte-swapped twice.  Here's an
alternative sha1_final, moving the byte-swapping into sha1_update and
saving a few cycles and a few bytes (234 -> 214 bytes with gcc-4.0 -O
-fomit-frame-pointer on x86).  I assume that moving the byte-swapping
from sha_transform to sha1_update has no code size impact.



extern void sha_transform(u32 state[5], u32 temp[80]);

void sha1_final(void* ctx, u8 *out)
{
	struct sha1_ctx *sctx = ctx;
	u32 temp[SHA_WORKSPACE_WORDS];
	u64 count = sctx->count;
	u32 i, j, index;
	static const u8 padding[64] = { 0x80, };
	
	/* Pad out to 56 mod 64 */
	index = (((unsigned)sctx->count >> 3) + 8) & 0x3f;
	sha1_update(sctx, padding, 64-index); 
	
	/* Byte-swap the first 14 words of the buffer */
	for (i = 0; i < 14; i++)
		temp[i] = be32_to_cpu(((u32 const *)sctx->buffer)[i]);
		
	/* Append length, two native words, in big-endian word order. */
	((u32 *)sctx->buffer)[14] = (u32)(count >> 32);
	((u32 *)sctx->buffer)[15] = (u32)count; 
	
	/* And the final transformation */
	sha_transform(sctx->state, temp);
	
	/* Store state in digest */
	for (i = j = 0; i < 5; i++, j += 4) {
		u32 t2 = sctx->state[i]; 
		out[j+3] = t2 & 0xff; t2>>=8;
		out[j+2] = t2 & 0xff; t2>>=8;
		out[j+1] = t2 & 0xff; t2>>=8;
		out[j  ] = t2 & 0xff;
	}

	/* Wipe context */
	memset(temp, 0, sizeof temp);
	memset(sctx, 0, sizeof *sctx);
}



Anyway, back to the long-suffering jlcooke@certainkey.com:

>> something?  Because it makes zero difference, and reduces the code
>> size and execution time.  Which is obviously a Good Thing.)

> It just bugged me when I was reading random.c for the first time.  First
> impressions and all.

Interesting.  Hopefully, further reflecton has shown you that the change
has zero security implications.  (For the same reason, cryptanalysts
studying DES ignore the initial permutation.)

>> Do you like:
>> - The neat name,
>> - The strong ciphers used in the pools, or
>> - The multi-pool reseeding strategy, or
>> - Something else?

> The multi-pool reseeding strategy is what I find particular interesting.
> It's design that can fit neatly into my little head and I hope into the heads
> of others in the future.  You can call it Bob or whatever you want, names
> doesn't matter to me.  As for the ciphers/digest algos used, they are
> not if great concern to me, replace them with what you want.  It's the design
> of the RNG itself that has my attention for the time being.

Great, we agree!  (Okay, almost.)  My point about "the neat name" was a
facetious straw-man.  That's a metaphor for "some stupid non-technical
reason".  Newer is not neceaarily better.  But your reason for liking
Fortuna is not quite that shallow.  Good.

Ted doesn't like Fortuna's pool design, I don't care for it much, but
you agree it's not important.  Great, no real point of contention there.
With lots of subpools, they need to be smaller, but the details of the
structure can be settled later.

But as I think I've said often enough, the sub-pool structure is what
makes Fortuna interesting.  *That* is Fortuna's contribution to the
state of the art, and the neat idea worth stealing.  We still agree!

However, there are a few issues, and if you'd like to address them, we
can actually get closer to agreeing, or at least clearly stating what
we disagree about.

1) Fortuna is trying to sidestep the hard problem of entropy measurement,
   to make it unnecessary.  This is a laudable goal, but /dev/random's
   information-theoretic design goal precludes this simplification.
   It *has* to measure entropy.  Are Fortuna's benefits sufficient to
   motivate a public interface change like that?  If you can argue that
   the current entropy measurement is such crap that it's not actually
   delivering its promise anyway, that would be a good reason.

   But as long as you *have* entropy measurement, you don't *need*
   Fortuna's elaborate scheme for avoiding it.  You only need *one*
   sub-pool.

2) Fortuna tries to support such a wide range of entropy source rates,
   down to very low rates, that it sequesters some entropy for literally
   years.  Ted thinks that's inexcusable, and I can't really disagree.
   This can be fixed to a significant degree by tweaking the number
   of subpools.

3) Fortuna's design doesn't actually *work*.  The authors' analysis
   only works in the case that the entropy seeds are independent, but
   forgot to state the assumption.  Some people reviewing the design
   don't notice the omission.

   It's that assumption which lets to "divide up" the seed material
   among various sub-pools.  Without it, seed information leaks from
   the sequestered sub-pools to the more exposed ones, decreasing the
   "value" of the sequestered pools.

   I've shown a contrived pathological example, but I haven't managed
   to figure out how to characterize the leakage in a more general way.
   But let me give a realistic example.

   Again, suppose we have an entropy source that delivers one fresh
   random bit each time it is sampled.

   But suppose that rather than delivering a bare bit, it delivers the
   running sum of the bits.  So adjacent samples are either the same or
   differ by +1.  This seems to me an extremely plausible example.

   Consider a Fortuna-like thing with two pools.  The first pool is seeded
   with n, then the second with n+b0, then the first again with n+b0+b1.
   n is the arbitrary starting count, while b0 and b1 are independent
   random bits.

   Assuming that an attacker can see the first pool, they can find n.
   After the second step, their uncertainty about the second pool is 1
   bit, the value of b0.

   But the third step is interesting.  The attacker can see the value of
   b0+b1.  If the sum is 0 or 2, the value of b0 is determined uniquely.
   Only in the case that b0+b1 = 1 is there uncertainty.  So we have
   only *half* a bit of uncertainty (one bit, half of the time) in the
   second pool.

   Where did the missing entropy go?  Well, remember the Shannon formula
   for entropy, H(p_1,...,p_n) = - Sum(p_i * log(p_i)).  If the log is
   to the base 2, the result is in bits.

   Well, p_0 = 1/4, p_1 = 1/2, and p_2 = 1/4.  The logs of those are
   -2, -1, and -2, respectively.  So the sum works out to
   2 * 1/4 + 1 * 1/2 + 2 * 1/4 = 1.5.

   Half a bit of entropy has leaked from the second pool back into the first!

   I probably just don't have enough mathematical background, but I don't
   currently know how to bound this leakage.  In pathological cases,
   *all* of the entropy leaks into the lowest-order pool, at which point
   the whole elaborate structure of Fortuna is completely useless.

   *That* is my big problem with Fortuna.  If someone can finish the
   analysis and actually bound the leakage, then we can construct something
   that works.  But I've pushed the idea around for a while and not figured
   it out.

> I'll take my patch and not bother you anymore.  I'm sure I've taken a
> lot of your time as it is.

And you've spent a lot of time preparing that patch.  It's not a bad idea
to revisit the ideas occasionally, but let's talk about the real *meat*
of the issue.

If you think my analysis of Fortuna's issues above is flawed, please
say so!  If you disagree about the importance of the issues, that's
worth discussing too, although I can't promise that such a difference
of opinions will ever be totally resolved.  But arguing about the
relative importance  of good and bad points is meaningful.

Ideally, we manage to come up with a solution that has all the good points.

The only thing that's frustrating is discussing it with someone who doesn't
even seem to *see* the issues.

> Not to sound like a "I'm taking my ball and going home" - just explaining
> that I like the Fortuna design, I think it's elegant, I want it for my
> systems.  GPL requires I submit changes back, so I did with the unpleasant
> side-dish of my opinion on random.c.

Actually, the GNU GPL doesn't.  It only requires that you give out the
source if and when you give out the binary.  You can make as many
private changes as you like.  (Search debian-legal for "desert island
test".)

Re: Fortuna

[Jean-Luc Cooke]

On Sat, Apr 16, 2005 at 10:05:55AM -0000, linux@horizon.com wrote:
> Anyway, back to the long-suffering jlcooke@certainkey.com:

;)

> >> something?  Because it makes zero difference, and reduces the code
> >> size and execution time.  Which is obviously a Good Thing.)
> 
> > It just bugged me when I was reading random.c for the first time.  First
> > impressions and all.

> Interesting.  Hopefully, further reflecton has shown you that the change
> has zero security implications.  (For the same reason, cryptanalysts
> studying DES ignore the initial permutation.)

Yes I saw that the first time, just struck me as "why?  why did I have to sit
here and add a that to the litany of things to remember when it's so easy to
just do it right?"

Guess I just see a different approach to software engineering, making it
easier to analyse makes it easier to improve.  You're 100% correct - security
wise it doesn't matter.

> 1) Fortuna is trying to sidestep the hard problem of entropy measurement,
>    to make it unnecessary.  This is a laudable goal, but /dev/random's
>    information-theoretic design goal precludes this simplification.
>    It *has* to measure entropy.  Are Fortuna's benefits sufficient to
>    motivate a public interface change like that?  If you can argue that
>    the current entropy measurement is such crap that it's not actually
>    delivering its promise anyway, that would be a good reason.
> 
>    But as long as you *have* entropy measurement, you don't *need*
>    Fortuna's elaborate scheme for avoiding it.  You only need *one*
>    sub-pool.

I agree with the statement:
 "If the current entropy estimation does not over estimate and crypto
  primitives don't fail to leak information, then we're OK"

What I've seen in my study of an older kernel (2.6.x) (the estimation scheme
hasn't changed afaik) is it's very conservative from what I understand of my
devices (keyboard,mouse not included, which is good.  But they don't contribute
as much randomness as disks and interrupts.)

> 2) Fortuna tries to support such a wide range of entropy source rates,
>    down to very low rates, that it sequesters some entropy for literally
>    years.  Ted thinks that's inexcusable, and I can't really disagree.
>    This can be fixed to a significant degree by tweaking the number
>    of subpools.

Well, I'd take hording entropy for 7 years over trusting a general entropy
accounting heuristic that is impossible to determine proper functioning.
Assuming again that the problems of malicious entropy event injection is
overcome.  Havn't come up with anything yet on how to do this nicely.

> 3) Fortuna's design doesn't actually *work*.  The authors' analysis
>    only works in the case that the entropy seeds are independent, but
>    forgot to state the assumption.  Some people reviewing the design
>    don't notice the omission.
...
>    Assuming that an attacker can see the first pool, they can find n.
>    After the second step, their uncertainty about the second pool is 1
>    bit, the value of b0.
...
>    Half a bit of entropy has leaked from the second pool back into the first!
...
>    *That* is my big problem with Fortuna.  If someone can finish the
>    analysis and actually bound the leakage, then we can construct something
>    that works.  But I've pushed the idea around for a while and not figured
>    it out.

I feel this goes back to the round-robin event input system.  Your argument
of n, n+b0, n+b0+b1, ... makes sense, in the state compromise / state
initialisation scenarios if the attacker can know for certain that they will
see 1 out of every 32 inputs.  If each of the pools has a 1:32 probability of
landing into any of the pools, then the things get a lot harder.

Does this make sense?  Ignoring the "where are you going to get a secure 1-in-32
RNG" issue.

If we look at this "slow-incremental entropy event input" situation with current
random.c, do we get a similar result?

Assuming an attacker can see the secondary-pool (/dev/random output) and
events {n, n+b0, b+b0+b1} enter primary-pool at times {t, t+t1, t+t1+t2}.
If the rate is slow enough, then an accurate entropy estimation will stop
anything from getting out, great.

"How does the entropy estimator measure entropy of the event?" becomes a
crucial concern here.  What if, by your leading example, there is 1/2 bit of
entropy in each event?  Will the estimator even account for 1/2 bits?  Or
will it see each event as 3 bits of entropy?  How much of a margin of error
can we tolerate?

/dev/random will output once it has at least 160 bits of entropy (iirc), 1/2
bit turning into 3 bits would mean that 160bits of output it effectively only
27 bits worth of true entropy (again, assuming the catastrophic reseeder and
output function don't waste entropy).

It's a lot of "ifs" for my taste.
waste any entropy

> > I'll take my patch and not bother you anymore.  I'm sure I've taken a
> > lot of your time as it is.
> 
> And you've spent a lot of time preparing that patch.  It's not a bad idea
> to revisit the ideas occasionally, but let's talk about the real *meat*
> of the issue.
> 
> If you think my analysis of Fortuna's issues above is flawed, please
> say so!  If you disagree about the importance of the issues, that's
> worth discussing too, although I can't promise that such a difference
> of opinions will ever be totally resolved.  But arguing about the
> relative importance  of good and bad points is meaningful.
> 
> Ideally, we manage to come up with a solution that has all the good points.
> 
> The only thing that's frustrating is discussing it with someone who doesn't
> even seem to *see* the issues.

Well, I'll do what I can then.  I understand your position and do my best to
explain in the thread in LKML.

> Actually, the GNU GPL doesn't.  It only requires that you give out the
> source if and when you give out the binary.  You can make as many
> private changes as you like.  (Search debian-legal for "desert island
> test".)

Humm, must be confused with another license then.  One that effects my
company required we submit back to the authors, so we just assumed that to be
the case for all of them and save the legal fees.

JLC

Re: Fortuna

[linux]

> Yes I saw that the first time, just struck me as "why?  why did I have to sit
> here and add a that to the litany of things to remember when it's so easy to
> just do it right?"

Huh?  Why?  Because it's faster and less code, that's why.
In what conceivable way is it NOT right?

On little-endian machines, we define the mixing function to the
the bit-reversed hash of the bit-reversed pool.  We could just as
easily store the entire pool bit-reversed and bit-reverse the inputs
before mising them in, and use stock SHA1.

Since we don't need to interoperate with anybody, details like
bit-ordering conventions are at the implementor's convenience.

The entire transformation has zero cryptological impact, so do it with
less code.  You don't *have* to remember it, any more than you have to
remember whether I incremented the loop counter with i++, ++i, i += 1,
or i = i+1.  It's SHA-1, and all the security properties still apply.

> Guess I just see a different approach to software engineering, making it
> easier to analyse makes it easier to improve.  You're 100% correct - security
> wise it doesn't matter.

I don't even see how it's any harder to analyze.  Any more than it
matters for most algorithm analysis whether the numbers are stored in
binary or decimal, or whether the loop counter is called i or j.

> I agree with the statement:
>  "If the current entropy estimation does not over estimate and crypto
>   primitives don't fail to leak information, then we're OK"

Er.. "if the crypto primitives don't fail TO leak information"?
I'm not quite sure I follow...

>> 2) Fortuna tries to support such a wide range of entropy source rates,
>>    down to very low rates, that it sequesters some entropy for literally
>>    years.  Ted thinks that's inexcusable, and I can't really disagree.
>>    This can be fixed to a significant degree by tweaking the number
>>    of subpools.

> Well, I'd take hording entropy for 7 years over trusting a general entropy
> accounting heuristic that is impossible to determine proper functioning.
> Assuming again that the problems of malicious entropy event injection is
> overcome.  Havn't come up with anything yet on how to do this nicely.

The problem is that it's spectacularly unlikely that the computer
will still be running in 7 years.  Any entropy put into that pool is
effectively lost *permanently*.

But maybe we can come to a compromise like 24 hours.

Plus, even a crude entropy estimate can do better.
Suppose we want do to 128-bit catastrophic reseeding.  But we don't
trust our entropy estimator.  Still, we think it's within a factor of
100 of being correct.  So we keep 8 subpools.  The first is dumped into
the main pool when we estimate it holds 128 bits.  The second, when the
extimate reaches 256.  Etc, until the eighth, which we wait for 16K bits -
the 128 bits we want plus a factor-of-128 safety margin.

And that only requires 8 pools, not 32.

(Still, unless our 8th pool can actually hold 16 kbits = 2048 bytes,
we're still wasting lots of entropy in the case that our entropy
estimator is correct.  And it's already pretty damn conservative
by design.)

> I feel this goes back to the round-robin event input system.  Your
> argument of n, n+b0, n+b0+b1, ... makes sense, in the state compromise
> / state initialisation scenarios if the attacker can know for certain
> that they will see 1 out of every 32 inputs.  If each of the pools has
> a 1:32 probability of landing into any of the pools, then the things
> get a lot harder.

Yes, but if you had a way to get 5 uniform random bits the attacker
didn't know, the entire issue would be trivial; just keep getting
5 random bits until you have as much as you need.

> Does this make sense?  Ignoring the "where are you going to get a secure
> 1-in-32 RNG" issue.

I have a really hard time letting go of the latter, but let me think...

No, I don't see how it helps more than the 5 random bits you're
giving yourself for free.  After any given subpool-0-to-main-pool
transfer, the attacker can easily see if subpool 0 was reseeded or not.
If it was, we can brute-force the seed.  With enough seeds at known
sequence positions, and high enough serial correlations, we can deduce
all the intermediate seeds.  Now the only uncertainty is which other pools
they got added to.

Which is the 5 bits of uncertainty you're giving yourself for free.

> Assuming an attacker can see the secondary-pool (/dev/random output) and
> events {n, n+b0, b+b0+b1} enter primary-pool at times {t, t+t1, t+t1+t2}.
> If the rate is slow enough, then an accurate entropy estimation will stop
> anything from getting out, great.

That's the hope.

> "How does the entropy estimator measure entropy of the event?" becomes a
> crucial concern here.  What if, by your leading example, there is 1/2 bit
> of entropy in each event?  Will the estimator even account for 1/2 bits?
> Or will it see each event as 3 bits of entropy?  How much of a margin
> of error can we tolerate?

H'm... the old code *used* to handle fractional bits, but the new code
seems to round down to the nearest bit.  May have to get fixed to
handle low-rate inputs.

As for margin of error, any persistent entropy overestimate is Bad.
a 6-fold overestimate is disastrous.

What we can do is refuse to drain the main pool below, say, 128 bits of
entropy.  Then we're safe against any *occasional* overestimates
as long as they don't add up to 128 bits.

> /dev/random will output once it has at least 160 bits of entropy
> (iirc), 1/2 bit turning into 3 bits would mean that 160bits of output
> it effectively only 27 bits worth of true entropy (again, assuming the
> catastrophic reseeder and output function don't waste entropy).
> 
> It's a lot of "ifs" for my taste.

/dev/random will output once it has as many bits of entropy as you're
asking for.  If you do a 20-byte read, it'll output once it has 160
bits.  If you do a 1-byte read, it'll output once it has 8 bits.

Re: Fortuna

[Matt Mackall]

On Sat, Apr 16, 2005 at 05:16:22PM -0000, linux@horizon.com wrote:
> > "How does the entropy estimator measure entropy of the event?" becomes a
> > crucial concern here.  What if, by your leading example, there is 1/2 bit
> > of entropy in each event?  Will the estimator even account for 1/2 bits?
> > Or will it see each event as 3 bits of entropy?  How much of a margin
> > of error can we tolerate?
> 
> H'm... the old code *used* to handle fractional bits, but the new code
> seems to round down to the nearest bit.  May have to get fixed to
> handle low-rate inputs.

I don't believe that was ever true, though it can fairly trivially be added.
JLC, please note that entropy estimation is much more conservative now
than it was a month ago.

> As for margin of error, any persistent entropy overestimate is Bad.
> a 6-fold overestimate is disastrous.
> 
> What we can do is refuse to drain the main pool below, say, 128 bits of
> entropy.  Then we're safe against any *occasional* overestimates
> as long as they don't add up to 128 bits.

I've been moving in that direction already, most of the infrastructure
is already in place.

> > /dev/random will output once it has at least 160 bits of entropy
> > (iirc), 1/2 bit turning into 3 bits would mean that 160bits of output
> > it effectively only 27 bits worth of true entropy (again, assuming the
> > catastrophic reseeder and output function don't waste entropy).
> > 
> > It's a lot of "ifs" for my taste.
> 
> /dev/random will output once it has as many bits of entropy as you're
> asking for.  If you do a 20-byte read, it'll output once it has 160
> bits.  If you do a 1-byte read, it'll output once it has 8 bits.

That's not quite right. It needs 8 bits in the relevant output pool.
Failing that, it needs 64 bits in the input pool to reseed the output
pool. In the case of /dev/urandom, it needs 128 bits in the input
pool, it always leaves enough for /dev/random to reseed.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[Matt Mackall]

On Sat, Apr 16, 2005 at 10:05:55AM -0000, linux@horizon.com wrote:
> MErging e-mails, first from mpm@selenic.com:
> > You really ought to look at the _current_ implementation. There is no
> > SHA1 code in random.c. 
> 
> So I'm imagining the call to sha_transform() in 2.6.12-rc2's
> extract_buf()?  The SHA1 code has been moved to lib/sha1.c, so there's
> no SHA1 code *lexically* in random.c, but that's a facile response;
> it's a cryptologically meaningless change.

No, it's exactly to the point: he's forked random.c before a large set
of changes that he needs to be aware of. The SHA1 code is now shared
by cryptolib and obviously no longer suffers from the (non-existent)
weakness he referenced.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[David Wagner]

linux wrote:
>3) Fortuna's design doesn't actually *work*.  The authors' analysis
>   only works in the case that the entropy seeds are independent, but
>   forgot to state the assumption.  Some people reviewing the design
>   don't notice the omission.

Ok, now I understand your objection.  Yup, this is a real objection.
You are right to ask questions about whether this is a reasonable assumption.

I don't know whether /dev/random makes the same assumption.  I suspect that
its entropy estimator is making a similar assumption (not exactly the same
one), but I don't know for sure.

I also don't know whether this is a realistic assumption to make about
the physical sources we currently feed into /dev/random.  That would require
some analysis of the physics of those sources, and I don't have the skills
it would take to do that kind of analysis.

>   Again, suppose we have an entropy source that delivers one fresh
>   random bit each time it is sampled.
>
>   But suppose that rather than delivering a bare bit, it delivers the
>   running sum of the bits.  So adjacent samples are either the same or
>   differ by +1.  This seems to me an extremely plausible example.
>
>   Consider a Fortuna-like thing with two pools.  The first pool is seeded
>   with n, then the second with n+b0, then the first again with n+b0+b1.
>   n is the arbitrary starting count, while b0 and b1 are independent
>   random bits.
>
>   Assuming that an attacker can see the first pool, they can find n.
>   After the second step, their uncertainty about the second pool is 1
>   bit, the value of b0.
>
>   But the third step is interesting.  The attacker can see the value of
>   b0+b1.  If the sum is 0 or 2, the value of b0 is determined uniquely.
>   Only in the case that b0+b1 = 1 is there uncertainty.  So we have
>   only *half* a bit of uncertainty (one bit, half of the time) in the
>   second pool.
[..]
>   I probably just don't have enough mathematical background, but I don't
>   currently know how to bound this leakage.

Actually, this example scenario is not a problem.  I'll finish the
analysis for you.  Suppose that the adversary can observe the entire
evolution of the first pool (its initial value, and all updates to it).
Assume the adversary knows n.  In one round (i.e., a pair of updates),
the adversary learns the value of b0 + b1 (and nothing more!).  In the
next round, the adversary learns b0' + b1' -- and so on.

How many bits of uncertainty have been added to the second pool in
each round?  With probability 1/2, the uncertainty of the second pool
remains unchanged.  With probability 1/2, the uncertainty increases by
exactly 1 bit.  This means there are two classes of updates, and both
classes are equally likely.

Suppose we perform 200 rounds of updates.  Then we can expect about
100 of these updates to be of the second class.  If the updates were
split evently (50/50) between these two classes, the adversary would
have 100 bits of uncertainty about the second pool.  In general, we
expect somewhere near 100 bits of uncertainty -- sometimes a bit more,
sometimes a bit less, but the chances that it is a lot less than 100
bits of uncertainty are exponentially small.

Therefore, except for an event that occurs with exponentially small
probability, the adversary will be left with many bits of uncertainty
about the second pool.  So this kind of source should not pose a serious
problem for Fortuna, or for any two-pool solution.


If you want a better example of where the two-pool scheme completely
falls apart, consider this: our source picks a random bit, uses this
same bit the next two times it is queried, and then picks a new bit.
Its sequence of outputs will look like (b0,b0,b1,b1,b2,b2,..,).  If
we alternate pools, then the first pool sees the sequence b0,b1,b2,..
and the second pool sees exactly the same sequence.  Consequently, an
adversary who can observe the entire evolution of the first pool can
deduce everything there is to know about the second pool.  This just
illustrates that these multiple-pool solutions make some assumptions
about the time-independence of their sources, or at least that the bits
going into one pool don't have too much correlation with the bits going
into the other pool.

Re: Fortuna

[David Wagner]

linux wrote:
>/dev/urandom depends on the strength of the crypto primitives.
>/dev/random does not.  All it needs is a good uniform hash.

That's not at all clear.  I'll go farther: I think it is unlikely
to be true.

If you want to think about cryptographic primitives being arbitrarily
broken, I think there will be scenarios where /dev/random is insecure.

As for what you mean by "good uniform hash", I think you'll need to
be a bit more precise.

>Do a bit of reading on the subject of "unicity distance".

Yes, I've read Shannon's original paper on the subject, as well
as many other treatments.

I stand by my comments above.

Re: Fortuna

[Matt Mackall]

On Fri, Apr 15, 2005 at 12:22:25PM -0400, Jean-Luc Cooke wrote:
> And the argument that "random.c doesn't rely on the strength of crypto
> primitives" is kinda lame, though I see where you're coming from.  random.c's
> entropy mixing and output depends on the (endian incorrect) SHA-1
> implementation hard coded in that file to be pre-image resistant.  If that
> fails (and a few other things) then it's broken.

You really ought to look at the _current_ implementation. There is no
SHA1 code in random.c. 

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[David Wagner]

Theodore Ts'o  wrote:
>With a properly set up set of init scripts, /dev/random is initialized
>with seed material for all but the initial boot [...]

I'm not so sure.  Someone posted on this mailing list several months
ago examples of code in the kernel that looks like it could run before
those init scripts are run, and that looks like it might well be using
/dev/*random before it has been seeded.

I never saw any response.

>It fundamentally assumes that crypto
>primitives are secure (when the recent break of MD4, MD5, and now SHA1
>should have been a warning that this is a Bad Idea (tm)),

It looks to me like the recent attacks on MD4, MD5, and SHA1 do not
endanger /dev/random.  Those attacks affect collision-resistance, but
it looks to me like the security of /dev/random relies on other properties
of the hash function (e.g., pseudorandomness, onewayness) which do not
seem to be threatened by these attacks.  But of course this is a complicated
business, and maybe I overlooked something about the way /dev/random uses
those hash functions.  Did I miss something?

As for which threat models are realistic, I consider it more likely
that my box will be hacked in a way that affects /dev/random than that
SHA1 will be broken in a way that affects /dev/random.

>In addition, Fortuna is profligate with entropy, [...]

Yup.

Re: Fortuna

[Patrick J. LoPresti]

Theodore Ts'o <tytso@mit.edu> writes:

> With a properly set up set of init scripts, /dev/random is
> initialized with seed material for all but the initial boot

What about CD-ROM based distros (e.g., Knoppix), where every boot is
the initial boot?

> (and even that problem can be solved by having the distribution's
> install scripts set up /var/lib/urandom/random-seed after installing
> the system).

Could you elaborate?  How should Knoppix seed its /dev/urandom?

Would reading 256 bits from /dev/random and writing them to
/dev/urandom do the job?

 - Pat

Re: Fortuna

[Jean-Luc Cooke]

Thanks for the post.

Waiting for 256bits of entropy before outputting data is a good goal.  Problem
becomes how do you measure entropy in a reliable way?  This had me lynched
last time I asked it so I'll stop right there.

Info-theoretic randomness is a strong desire of some/many users, and they think
the current entropy estimation technique does the trick, so I left it there
with the option to #define it out.

I'll not make any claim that random-fortuna.c should be mv'd to random.c, the
patch given allows people to kernel config it in under the Cryptographic
Options menu.  Perhaps a disclaimer in the help menu would be in order to
inform users that Fortuna has profound consequences for those expecting
Info-theoretic /dev/random?

The case where an attacker has some small amount of unknown in the pool is a
problem that effects BOTH random-fortuna.c and random.c (and any other
replacement for that matter).  Just an FYI.

As for the "shifting property" problem of an attacker controlling some input
to the pooling system, I've tried to get around this:

r->pools_bytes[r->pool_index] += nwords * sizeof(__u32);
crypto_digest_update(r->pools[r->pool_index], sg, 1);
if (r->pool_index == 0) {
    r->pool0_len += nwords*sizeof(__u32);
}
/* idx = (idx + r) mod ( (2^N)-1 ) */
r->pool_index = (r->pool_index + r->key[keyidx])
                      & ((1<<random_state->pool_number)-1);
/* first 8 bytes of the key are used, 8 * 8 = 64 bits */
keyidx = (keyidx + 1) & 7;

The add_entropy_words() function uses the first 8 bytes of the central
pool to aggravate the predictability of where entropy goes.  It's still a
linear progression untill the central pool is re-keyed, then you don't know
where it went.  The central pool is reseeded every 0.1ms.

This causes problems of course, the hard upper bound of "we recover from
state compromise in at most a factor of 64 times the rate of entropy inflow"
is no longer non-deterministic.  That is, it changes to "we expect to recover
from state compromise in a factor of 64 times the rate of entropy inflow."

Not sure if this was caught or not, but <linux@>Anyway, every 32 cycles, a seed word
is added to subpool 0, which is then immediately added to the main pool</linux@>.
Entirely true however, every time other than the first seeding other pools
will be adding words to the main pool as well.

Cheers,

JLC

On Thu, Apr 14, 2005 at 02:15:38PM -0000, linux@horizon.com wrote:
> Just to refersh everyone's memory as to the strengths and weaknesses
> of Fortuna...
> 
> First, a reminder that the design goal of /dev/random proper is
> information-theoretic security.  That is, it should be secure against
> an attacker with infinite computational power.  If you want a weaker
> guarantee, use /dev/urandom.
> 
> I've heard a suggestion that something like /dev/urandom, but which blocks
> until it has received a minimum amount of seed material at least once,
> would be a nice thing.  So boot-time crypto initialization can stall
> until it has achieved a minimum level of security.
> 
> The minimum could be measured two ways:
> - Some reasonable default, like 256 bits, or
> - (clever) the size of the read() request, which is presumably the
>   key size that the user needs.  This might be too subtle to explain
>   to programmers, though.
> 
> 
> Anyway, there are two main parts to Fortuna.  The central "random pool",
> and the round-robin sub-pool system for reseeding the main pool.
> 
> Fortuna uses a "small pool, trust the crypto" central pool.
> /dev/random uses a large pool that is deliberately designed to be
> robust against failure of the crypto primitives.  Indeed, the basic
> design just uses it as a uniform hash.  Cryptographic strength is
> irrelevant to the information-theoretic guarantees.
> 
> This portion of Fortuna is at odds with /dev/random's design goals,
> but it could be replaced easily enough.  It's not the clever part.
> 
> 
> The "neat idea" in Fortuna is the round-robin sub-pool seeding technique,
> which attempts to avoid the entire issue of entropy estimation.
> 
> Now, for information-theoretic guarantees, entropy measurement is
> *required*.  You cannot be information-theoretic secure unless you
> have received more seed entropy than you have produced output.
> 
> However, Fortuna has a different philosophy.  This difference is why
> Fortuna will NEVER be an "exact drop-in replacement" for /dev/random,
> although it can do the job for /dev/urandom.  There are important
> user-visible differences in the guarantees it makes.  Someone may
> argue that the difference is immaterial in practice, but existence of
> a difference is indisputable.
> 
> 
> It tries to divide up the seed entropy into sub-pools and hold off
> re-seeding the main pool until the sub-pool has accumulated enough entropy
> to cause "catastrophic reseeding" of the main pool, adding enough entropy
> at once that someone who had captured the prior state of the main pool
> would not be able (due to computational limits and the one-way nature
> of the pool output function) to reverse-engineer the post-state.
> 
> The way it schedules the additions, it doesn't know *which* re-seed of
> the main pool will be catastrophic, but it knows that it will be within
> a factor of 64 of the shortest time that's possible.
> 
> 
> However, it possible to come up with some pathological entropy sources
> for which the standard Fortuna design completely fails to achieve that
> goal.
> 
> So Fortuna would be helped by some better understanding of what exactly
> makes it fail, so the discussion could move to whether real-world
> seed sources have those properties.
> 
> But until that understanding is gained, Fortuna is questionable.
> 
> 
> Appendix: how to "break" Fortuna.
> 
> First, the standard assumptions: the "attacker" can collect arbitrary
> amounts of RNG output at any time, and can see all operations on the
> pool except for the value of the seed material.
> 
> In particular, if the attacker's uncertainty about the pool's state
> is small, she can collect enough output to distinguish all the
> possibilities and attempt a brute-force computation to recover the
> unknown state information.
> 
> Finally, assume the attacker knows the full initial state of the
> generator.
> 
> For a classic 32-subpool Fortuna, let the seed be a 32-bit integer.
> Every time a new seed is produced, shift the previous value and insert
> a fresh random bit.  Thus, the seed does deliver 1 bit of entropy
> per sample, which should make for a secure source.
> 
> If you want to be cruel, encrypt that seed with a strong cipher known
> only to the attacker before producing output.  That keeps the nature
> of the seed from the Fortuna implementation.
> 
> Anyway, every 32 cycles, a seed word is added to subpool 0, which is then
> immediately added to the main pool.  An attacker who knows the prior
> state of the main pool can attempt a brute-force search for the 32 bits
> of the seed word in a reasonable period of time.
> 
> Because of the shifting property, an attacker who knows the seeds added
> to pool 0 at times t and t+32 can also deduce, with perfect accuracy,
> the seeds added to the other 31 pools at times t+1 through t+31.
> 
> The result being that the other subpools, which are supposed to be hoarding
> secret information unknown to the attacker, are actually being seeded with
> bits known to the attacker.
> 
> The ultimate result is that catastrohpic reseeding never takes place.
> If we could somehow separate the "fresh" entropy in the input samples
> from the "holdover" material, the problem would go away, but that's
> an entropy measurement problem!
> 
> Until this cloud is dissipated by further analysis, it's not possible to
> say "this is shiny and new and better; they's use it!" in good conscience.

Re: Fortuna

[linux]

> Waiting for 256bits of entropy before outputting data is a good goal.
> Problem becomes how do you measure entropy in a reliable way?  This had
> me lynched last time I asked it so I'll stop right there.

It's a problem.  Also, with the current increase in wireless keyboards
and mice, that source should possibly not be considered secure any more.

On the other hand, clock jitter in GHz clocks is a *very* rich source
of seed material.  One rdtsc per timer tick, even accounted for at
0.1 bit per rdtsc (I think reality is more like 3-5 bits) would keep
you in clover.

> I'll not make any claim that random-fortuna.c should be mv'd to random.c, the
> patch given allows people to kernel config it in under the Cryptographic
> Options menu.  Perhaps a disclaimer in the help menu would be in order to
> inform users that Fortuna has profound consequences for those expecting
> Info-theoretic /dev/random?

I don't mean to disparage you efforts, but then what's the upside to
the resultant code maintenance hassles?  Other than hack value, what's the
advantage of even offering the choice?  An option like that is justified
when the two options have value for different people and it's not
possible to build a single merged solutions that satisfies both markets.

Also, Ted very deliberately made /dev/random non-optional so it could
be relied on without a lot of annoying run-time testing.  Would
a separate /dev/fortuna be better?



> The case where an attacker has some small amount of unknown in the pool is a
> problem that effects BOTH random-fortuna.c and random.c (and any other
> replacement for that matter).  Just an FYI.

Yes, but entropy estimation is supposed to deal with that.  If the
attacker is never allowed enough information out of the pool to
distinguish various input states, the output is secure.

> As for the "shifting property" problem of an attacker controlling some input
> to the pooling system, I've tried to get around this:

(Code that varies the pool things get added to based on r->key[i++ & 7])

> The add_entropy_words() function uses the first 8 bytes of the central
> pool to aggravate the predictability of where entropy goes.  It's still a
> linear progression untill the central pool is re-keyed, then you don't know
> where it went.  The central pool is reseeded every 0.1ms.

You need to think more carefully.  You're just elaborating it without
adding security.  Yes, the attacker *does* know!  The entire underlying
assumption is that the attacker knows the entire initial state of the
pool, owing to some compromise or another.

The assumption is that the only thing the attacker doesn't know is the
exact value of the incoming seed material.  (But the attacker does have
an excellent model of its distribution.)

Given that, the attacker knows the initial value of the key[] array,
and thus knows the order in which the pools are fed.  The question
then arises, come next reseed, can the attacker (with a small mountain
of computers, able to brute-force 40-bit problems in the blink of an
eye) infer the *complete* state of the pool from the output.

The confusion is over the word "random".  In programming jargon, the
word is most often used to mean "arbitrary" or "the choice doesn't
matter".  But that doesn't capture the idea of "unpredictable to
a skilled and determined opponent" that is needed in /dev/random.

So while the contents of key[] may be "random-looking", they're not
*unpredictable*, any more than the digits of pi are.

The attacker just has to, after each reseeding, brute-force the seed
bits fed to the (predictable) pools chosen to mix in, and then
use that information to infer the seeds added to the not-selected
pools.

If the attacker's uncertainty about the state of some of the subpools
increases to the catastrophic reseeding level, then the Fortuna design
goal is achieved.

If the seed samples are independent, then it's easy to see that the
schedule works.

But if the seed samples are correlated, it gets a lot trickier.

Re: Fortuna

[David Wagner]

Jean-Luc Cooke  wrote:
>Info-theoretic randomness is a strong desire of some/many users, [..]

I don't know.  Most of the time that I've seen users say they want
information-theoretic randomness, I've gotten the impression that those
users didn't really understand what information-theoretic randomness means,
and their applications usually didn't need information-theoretic randomness
in the first place.

As for those who reject computational security because of its
unproven nature, they should perhaps be warned that any conjectured
information-theoretic security of /dev/random is also unproven.

Personally, I feel the issue of information-theoretic security
is a distraction.  Given the widespread confusion about what
information-theoretic security means, I certainly sympathize with why
Jean-Luc Cooke left in the existing entropy estimation technique as a
way of side-stepping the whole argument.

Anyway, the bottom line is I don't consider "information-theoretic
arguments" as a very convincing reason to reject Cooke's proposal.

Re: Fortuna

[David Wagner]

>First, a reminder that the design goal of /dev/random proper is
>information-theoretic security.  That is, it should be secure against
>an attacker with infinite computational power.

I am skeptical.
I have never seen any convincing evidence for this claim,
and I suspect that there are cases in which /dev/random fails
to achieve this standard.

And it seems I am not the only one.  See, e.g., Section 5.3 of:
http://eprint.iacr.org/2005/029

Fortunately, it doesn't matter whether /dev/random provides
information-theoretic security.  I have reasonable confidence that
it provides computational security, and that is all that applications
need.

Re: Fortuna

[Matt Mackall]

[please reply to all when posting to lkml]

On Sat, Apr 16, 2005 at 01:08:47AM +0000, David Wagner wrote:
> >First, a reminder that the design goal of /dev/random proper is
> >information-theoretic security.  That is, it should be secure against
> >an attacker with infinite computational power.
> 
> I am skeptical.
> I have never seen any convincing evidence for this claim,
> and I suspect that there are cases in which /dev/random fails
> to achieve this standard.
> 
> And it seems I am not the only one.  See, e.g., Section 5.3 of:
> http://eprint.iacr.org/2005/029

Unfortunately, this paper's analysis of /dev/random is so shallow that
they don't even know what hash it's using. Almost all of section 5.3
is wrong (and was when I read it initially).

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[David Wagner]

Matt Mackall  wrote:
>On Sat, Apr 16, 2005 at 01:08:47AM +0000, David Wagner wrote:
>> http://eprint.iacr.org/2005/029
>
>Unfortunately, this paper's analysis of /dev/random is so shallow that
>they don't even know what hash it's using. Almost all of section 5.3
>is wrong (and was when I read it initially).

Yes, that is a minor glitch, but I believe all their points remain
valid nonetheless.  My advice is to apply the appropriate s/MD5/SHA1/g
substitution, and re-read the paper to see what you can get out of it.

The problem is not that the paper is shallow; it is not.  The source
of the error is likely that this paper was written by theorists, not
implementors.  There are important things we can learn from them, and I
think it is worth reading their paper carefully to understand what they
have to offer.

I believe they raise substantial and deep questions in their Section 5.3.
I don't see why you say Section 5.3 is all wrong.  Can you elaborate?
Can you explain one or two of the substantial errors you see?

Re: Fortuna

[Theodore Ts'o]

On Mon, Apr 18, 2005 at 09:40:37PM +0000, David Wagner wrote:
> Yes, that is a minor glitch, but I believe all their points remain
> valid nonetheless.  My advice is to apply the appropriate s/MD5/SHA1/g
> substitution, and re-read the paper to see what you can get out of it.
> 
> The problem is not that the paper is shallow; it is not.  The source
> of the error is likely that this paper was written by theorists, not
> implementors.  There are important things we can learn from them, and I
> think it is worth reading their paper carefully to understand what they
> have to offer.

Since the paper was written by theorists, it appears that they didn't
bother to read the implementation, but instead made assumptions from
the man pages, as well as making the assumption that the man page
(which was not written as a specification from which the code was
implemented, and indeed was not even written by the code authors) was
in fact an accurate representation of drivers/char/random.c.

So section 5.3 is essense a criticism of a straw man implementation
based on a flawed reading of a flawed man page.  Other than that, it's
fine.  :-)

> I believe they raise substantial and deep questions in their Section 5.3.
> I don't see why you say Section 5.3 is all wrong.  Can you elaborate?
> Can you explain one or two of the substantial errors you see?

For one, /dev/urandom and /dev/random don't use the same pool
(anymore).  They used to, a long time ago, but certainly as of the
writing of the paper this was no longer true.  This invalidates the
entire last paragraph of Section 5.3.

The criticisms of the /dev/random man page do have some point, but the
man page != the implementation.  Also, the paper does not so much make
an attack on the entropy estimator, so much as it casts asperions on
it, while at the same time making the unspoken assumption that
cryptographic primitives are iron-clad and unbreakable.

So I don't see any particular substantial deep questions, unless you
count, "It is not at all clear that /dev/random ... provides
information-theoretic security.  Indeed, we suspect it sometimes
doesn't" as a deep question.  I don't.

						- Ted

Re: Fortuna

[David Wagner]

Theodore Ts'o  wrote:
>For one, /dev/urandom and /dev/random don't use the same pool
>(anymore).  They used to, a long time ago, but certainly as of the
>writing of the paper this was no longer true.  This invalidates the
>entire last paragraph of Section 5.3.

Ok, you're right, this is a serious flaw, and one that I overlooked.
Thanks for elaborating.  (By the way, has anyone contacted to let them
know about these two errors?  Should I?)

I see three remaining criticisms from their Section 5.3:
1) Due to the way the documentation describes /dev/random, many
   programmers will choose /dev/random by default.  This default
   seems inappropriate and unfortunate.
2) There is a widespread perception that /dev/urandom's security is
   unproven and /dev/random's is proven.  This perception is wrong.
   On a related topic, it is "not at all clear" that /dev/random provides
   information-theoretic security.
3) Other designs place less stress on the entropy estimator, and
   thus are more tolerant to failures of entropy estimation.  A failure
   in the entropy estimator seems more likely than a failure in the
   cryptographic algorithms.
These three criticisms look right to me.

Apart from the merits or demerits of Section 5.3, the rest of the paper
seemed to have some interesting ideas for how to simplify and possibly
improve the /dev/random generator, which might be worth considering at
some point.

Re: Fortuna

[Theodore Ts'o]

On Tue, Apr 19, 2005 at 04:31:47AM +0000, David Wagner wrote:
> Theodore Ts'o  wrote:
> >For one, /dev/urandom and /dev/random don't use the same pool
> >(anymore).  They used to, a long time ago, but certainly as of the
> >writing of the paper this was no longer true.  This invalidates the
> >entire last paragraph of Section 5.3.
> 
> Ok, you're right, this is a serious flaw, and one that I overlooked.
> Thanks for elaborating.  (By the way, has anyone contacted to let them
> know about these two errors?  Should I?)

I don't know of anyone who has contacted the authors yet.  I haven't
had the time, since I'm currently travelling at the moment.

> I see three remaining criticisms from their Section 5.3:
> 1) Due to the way the documentation describes /dev/random, many
>    programmers will choose /dev/random by default.  This default
>    seems inappropriate and unfortunate.
> 2) There is a widespread perception that /dev/urandom's security is
>    unproven and /dev/random's is proven.  This perception is wrong.
>    On a related topic, it is "not at all clear" that /dev/random provides
>    information-theoretic security.
> 3) Other designs place less stress on the entropy estimator, and
>    thus are more tolerant to failures of entropy estimation.  A failure
>    in the entropy estimator seems more likely than a failure in the
>    cryptographic algorithms.
> These three criticisms look right to me.

/dev/urandom is a cryptographic RNG, which is seeded from RNG.
/dev/random uses a very similar cryptographic RNG, but it uses large
pool to collect entropy, and uses an entropy estimator to limit the
amount of data that can be extracted from the rng.  

If the entropy estimator fails, /dev/random degrades to a
cryptographic RNG.  So it is not a disaster, whereas the approach
described in this paper (which uses a non-cryptographic extractor)
would seem to me to be *more* prone to catastrophically failure if the
entropy estimator fails than /dev/random.

As to whether or not applications should be using /dev/random or
/dev/urandom, /dev/random is no worse than /dev/urandom, as long as
the application doesn't mind blocking when the entropy levels are too
low.  In practice, most of the time this situation doesn't arise since
the appropriate way of using /dev/random is only to extract a small
amount of entropy when needed to generate long-term keys, or when
seeding a userspace cryptographic RNG for session keys.

						- Ted

Fortuna

[Jean-Luc Cooke]

[-- Attachment #1: Type: text/plain, Size: 1074 bytes --]

Ahh.  Thanks Herbert.

Matt,

Any insight on how to test syn cookies and the other network stuff in
random.c?  My patch is attached, but I havn't tested that part yet.

JLC

----- Forwarded message from Herbert Xu <herbert@gondor.apana.org.au> -----

Envelope-to: jlcooke@certainkey.com
Delivery-date: Wed, 13 Apr 2005 17:39:54 -0400
To: Jean-Luc Cooke <jlcooke@certainkey.com>
Subject: Re: [PATCH] API for TRNG (2.6.11) [Fortuna]
From: Herbert Xu <herbert@gondor.apana.org.au>
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on certainkey.com
X-Spam-Level: 
X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=unavailable 
	version=3.0.2

On Wed, Apr 13, 2005 at 11:36:40AM -0400, Jean-Luc Cooke wrote:
> Patch attached.

You might want to CC the current /dev/random maintainer Matt Mackall
<mpm@selenic.com>.
-- 
Visit Openswan at http://www.openswan.org/
Email: Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

----- End forwarded message -----

[-- Attachment #2: fortuna-random-2.6.11.4.patch --]
[-- Type: text/plain, Size: 65305 bytes --]

--- linux-2.6.11.6/crypto/Kconfig	2005-03-25 22:28:37.000000000 -0500
+++ linux-2.6.11.6-fort/crypto/Kconfig	2005-03-30 09:11:12.000000000 -0500
@@ -9,6 +9,20 @@
 	help
 	  This option provides the core Cryptographic API.
 
+config CRYPTO_RANDOM_FORTUNA
+	bool "The Fortuna CSRNG"
+	depends on CRYPTO && EXPERIMENTAL
+	select CRYPTO_SHA256
+	select CRYPTO_AES if !(CRYPTO && (X86 && !X86_64))
+	select CRYPTO_AES_586 if CRYPTO && (X86 && !X86_64)
+	help
+	  Replaces the legacy Linux RNG with one using the CryptoAPI
+	  and Fortuna designed by Ferguson and Schneier.  Entropy estimation,
+	  and a throttled /dev/random remain.  Improvements include faster
+	  /dev/urandom output and event input mixing.  Entropy estimation
+	  can be removed by changing source code.
+	  Note: Requires AES and SHA256 to be built-in.
+
 config CRYPTO_HMAC
 	bool "HMAC support"
 	depends on CRYPTO
--- linux-2.6.11.6/drivers/char/random-fortuna.c	1969-12-31 19:00:00.000000000 -0500
+++ linux-2.6.11.6-fort/drivers/char/random-fortuna.c	2005-03-31 08:54:37.321371752 -0500
@@ -0,0 +1,2121 @@
+/*
+ * random-fortuna.c -- A cryptographically strong random number generator
+ *			using Fortuna.
+ *
+ * Version 2.1.7, last modified 29-Mar-2005
+ * Change log:
+ *  v2.1.7:
+ * 	- Ported to 2.6.11.4
+ *  v2.1.6:
+ *	- Sami Farin pointed out RANDOM_MAX_BLOCK_SIZE was used for __u32[]'s
+ *	  and u8[]'s, fixed.
+ *	- Sami also found TCP sequence numbers wern't very secure.  Typo
+ *	  in code fixed.
+ *	- Sami found crypto_cipher_encrypt() uses nbytes and not
+ *	  numscatterlists.  Fixed.
+ *  v2.1.5:
+ *	- random-fortuna.c is no longer #include'd from random.c, the
+ *	  drivers/char/Makefile takes care of this now thanks to Chris Han
+ *  v2.1.4:
+ *	- Fixed flaw where some situations, /dev/random would not block.
+ *  v2.1.3:
+ *	- Added a seperate round-robin index for use inputs.  Avoids a
+ *	  super-cleaver user from forcing all system (unknown) random
+ *	  events from being fed into, say, pool-31.
+ *	- Added a "can only extract RANDOM_MAX_EXTRACT_SIZE bytes at a time"
+ *	  to extract_entropy()
+ *  v2.1.2:
+ *	- Ts'o's (I love writting that!) recomendation to force reseeds
+ * 	  to be at least 0.1 ms apart (complies with Ferguson/Schnier's
+ *	  design).
+ *  v2.1.1:
+ * 	- Re-worked to keep the blocking /dev/random.  Yes I finally gave
+ *	  in to what everyone's been telling me.
+ *	- Entropy accounting is *only* done on events going into pool-0
+ *	  since it's used for every reseed.  Those who expect /dev/random
+ *	  to only output data when the system is confident it has
+ *	  info-theoretic entropy to justify this output, this is the only
+ *	  sensible method to count entropy.
+ *  v2.0:
+ *	- Inital version
+ * 
+ * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
+ * rights reserved.
+ * Copyright Jean-Luc Cooke, 2004.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, and the entire permission notice in its entirety,
+ *    including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ *    products derived from this software without specific prior
+ *    written permission.
+ * 
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL are
+ * required INSTEAD OF the above restrictions.  (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ * 
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+/*
+ * Taken from random.c, updated by Jean-Luc Cooke <jlcooke@certainkey.com>
+ * (now, with legal B.S. out of the way.....) 
+ * 
+ * This routine gathers environmental noise from device drivers, etc.,
+ * and returns good random numbers, suitable for cryptographic use.
+ * Besides the obvious cryptographic uses, these numbers are also good
+ * for seeding TCP sequence numbers, and other places where it is
+ * desirable to have numbers which are not only random, but hard to
+ * predict by an attacker.
+ *
+ * Theory of operation
+ * ===================
+ * 
+ * Computers are very predictable devices.  Hence it is extremely hard
+ * to produce truly random numbers on a computer --- as opposed to
+ * pseudo-random numbers, which can easily generated by using a
+ * algorithm.  Unfortunately, it is very easy for attackers to guess
+ * the sequence of pseudo-random number generators, and for some
+ * applications this is not acceptable.  So instead, we must try to
+ * gather "environmental noise" from the computer's environment, which
+ * must be hard for outside attackers to observe, and use that to
+ * generate random numbers.  In a Unix environment, this is best done
+ * from inside the kernel.
+ * 
+ * Sources of randomness from the environment include inter-keyboard
+ * timings, inter-interrupt timings from some interrupts, and other
+ * events which are both (a) non-deterministic and (b) hard for an
+ * outside observer to measure.  Randomness from these sources are
+ * added to an "entropy pool", which is mixed.
+ * As random bytes are mixed into the entropy pool, the routines keep
+ * an *estimate* of how many bits of randomness have been stored into
+ * the random number generator's internal state.
+ * 
+ * Even if it is possible to analyze Fortuna in some clever way, as
+ * long as the amount of data returned from the generator is less than
+ * the inherent entropy we've estimated in the pool, the output data
+ * is totally unpredictable.  For this reason, the routine decreases
+ * its internal estimate of how many bits of "true randomness" are
+ * contained in the entropy pool as it outputs random numbers.
+ * 
+ * If this estimate goes to zero, the routine can still generate
+ * random numbers; however, an attacker may (at least in theory) be
+ * able to infer the future output of the generator from prior
+ * outputs.  This requires successful cryptanalysis of Fortuna, which is
+ * not believed to be feasible, but there is a remote possibility.
+ * Nonetheless, these numbers should be useful for the vast majority
+ * of purposes.
+ * 
+ * Exported interfaces ---- output
+ * ===============================
+ * 
+ * There are three exported interfaces; the first is one designed to
+ * be used from within the kernel:
+ *
+ * 	void get_random_bytes(void *buf, int nbytes);
+ *
+ * This interface will return the requested number of random bytes,
+ * and place it in the requested buffer.
+ * 
+ * The two other interfaces are two character devices /dev/random and
+ * /dev/urandom.  /dev/random is suitable for use when very high
+ * quality randomness is desired (for example, for key generation or
+ * one-time pads), as it will only return a maximum of the number of
+ * bits of randomness (as estimated by the random number generator)
+ * contained in the entropy pool.
+ * 
+ * The /dev/urandom device does not have this limit, and will return
+ * as many bytes as are requested.  As more and more random bytes are
+ * requested without giving time for the entropy pool to recharge,
+ * this will result in random numbers that are merely cryptographically
+ * strong.  For many applications, however, this is acceptable.
+ *
+ * Exported interfaces ---- input
+ * ==============================
+ * 
+ * The current exported interfaces for gathering environmental noise
+ * from the devices are:
+ * 
+ * 	void add_keyboard_randomness(unsigned char scancode);
+ * 	void add_mouse_randomness(__u32 mouse_data);
+ * 	void add_interrupt_randomness(int irq);
+ * 
+ * add_keyboard_randomness() uses the inter-keypress timing, as well as the
+ * scancode as random inputs into the "entropy pool".
+ * 
+ * add_mouse_randomness() uses the mouse interrupt timing, as well as
+ * the reported position of the mouse from the hardware.
+ *
+ * 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.
+ *
+ * Ensuring unpredictability at system startup
+ * ============================================
+ * 
+ * When any operating system starts up, it will go through a sequence
+ * of actions that are fairly predictable by an adversary, especially
+ * if the start-up does not involve interaction with a human operator.
+ * This reduces the actual number of bits of unpredictability in the
+ * entropy pool below the value in entropy_count.  In order to
+ * counteract this effect, it helps to carry information in the
+ * entropy pool across shut-downs and start-ups.  To do this, put the
+ * following lines an appropriate script which is run during the boot
+ * sequence: 
+ *
+ *	echo "Initializing random number generator..."
+ *	random_seed=/var/run/random-seed
+ *	# Carry a random seed from start-up to start-up
+ *	# Load and then save the whole entropy pool
+ *	if [ -f $random_seed ]; then
+ *		cat $random_seed >/dev/urandom
+ *	else
+ *		touch $random_seed
+ *	fi
+ *	chmod 600 $random_seed
+ *	dd if=/dev/urandom of=$random_seed count=8 bs=256
+ *
+ * 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 the whole entropy pool
+ * 	# Fortuna resists using all of its pool matirial, so we need to
+ *      # draw 8 seperate times (count=8) to ensure we get the entropy
+ *	# from pool[0,1,2,3]'s entropy.  count=2048 pool[0 .. 10], etc.
+ *	echo "Saving random seed..."
+ *	random_seed=/var/run/random-seed
+ *	touch $random_seed
+ *	chmod 600 $random_seed
+ *	dd if=/dev/urandom of=$random_seed count=8 bs=256
+ *
+ * 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
+ * location might be in /etc/rcb.d/rc.local or /etc/rc.d/rc.0.
+ * 
+ * Effectively, these commands cause the contents of the entropy pool
+ * to be saved at shut-down time and reloaded into the entropy pool at
+ * start-up.  (The 'dd' in the addition to the bootup script is to
+ * make sure that /etc/random-seed is different for every start-up,
+ * even if the system crashes without executing rc.0.)  Even with
+ * complete knowledge of the start-up activities, predicting the state
+ * of the entropy pool requires knowledge of the previous history of
+ * the system.
+ *
+ * Configuring the /dev/random driver under Linux
+ * ==============================================
+ *
+ * The /dev/random driver under Linux uses minor numbers 8 and 9 of
+ * the /dev/mem major number (#1).  So if your system does not have
+ * /dev/random and /dev/urandom created already, they can be created
+ * by using the commands:
+ *
+ * 	mknod /dev/random c 1 8
+ * 	mknod /dev/urandom c 1 9
+ * 
+ * Acknowledgements:
+ * =================
+ *
+ * Ideas for constructing this random number generator were derived
+ * from Pretty Good Privacy's random number generator, and from private
+ * discussions with Phil Karn.  Colin Plumb provided a faster random
+ * number generator, which speed up the mixing function of the entropy
+ * pool, taken from PGPfone.  Dale Worley has also contributed many
+ * useful ideas and suggestions to improve this driver.
+ * 
+ * Any flaws in the design are solely my (jlcooke) responsibility, and
+ * should not be attributed to the Phil, Colin, or any of authors of PGP
+ * or the legacy random.c (Ted Ts'o).
+ * 
+ * Further background information on this topic may be obtained from
+ * RFC 1750, "Randomness Recommendations for Security", by Donald
+ * Eastlake, Steve Crocker, and Jeff Schiller.  And Chapter 10 of
+ * Practical Cryptography by Ferguson and Schneier.
+ */
+
+#include <linux/utsname.h>
+#include <linux/config.h>
+#include <linux/module.h>
+#include <linux/kernel.h>
+#include <linux/major.h>
+#include <linux/string.h>
+#include <linux/fcntl.h>
+#include <linux/slab.h>
+#include <linux/random.h>
+#include <linux/poll.h>
+#include <linux/init.h>
+#include <linux/fs.h>
+#include <linux/workqueue.h>
+#include <linux/genhd.h>
+#include <linux/interrupt.h>
+#include <linux/spinlock.h>
+#include <linux/percpu.h>
+#include <linux/crypto.h>
+
+#include <asm/scatterlist.h>
+#include <asm/processor.h>
+#include <asm/uaccess.h>
+#include <asm/irq.h>
+#include <asm/io.h>
+
+
+/*
+ * Configuration information
+ */
+
+/* Set to 1 to disable entropy estimation (once it reaches its max) and
+ * blocking of /dev/random */
+#define RANDOM_NO_ENTROPY_COUNT 0
+/* Queue of input events to queue for input into our pools */
+#define BATCH_ENTROPY_SIZE 256
+/* micro-seconds between random_reseeds for non-blocking reads */
+#define RANDOM_RESEED_INTERVAL 100
+/*
+ * Number of bytes you can extract at a time, 1MB is recomended in
+ * Practical Cryptography rev-0
+ */
+#define RANDOM_MAX_EXTRACT_SIZE  (1<<20)
+#define RANDOM_DEFAULT_DIGEST_ALGO "sha256"
+#define RANDOM_DEFAULT_CIPHER_ALGO "aes"
+/* Alternatives */
+//#define RANDOM_DEFAULT_DIGEST_ALGO "whirlpool"
+//#define RANDOM_DEFAULT_CIPHER_ALGO "twofish"
+
+#define DEFAULT_POOL_NUMBER 5 /* 2^{5} = 32 pools */
+#define DEFAULT_POOL_SIZE ( (1<<DEFAULT_POOL_NUMBER) * 256)
+/* largest block of random data to extract at a time when in blocking-mode */
+#define TMP_BUF_SIZE		512
+/* SHA512/WHIRLPOOL have 64bytes == 512 bits */
+#define RANDOM_MAX_DIGEST_SIZE	64
+/* AES256 has 16byte blocks == 128 bits */
+#define RANDOM_MAX_BLOCK_SIZE	16
+/* AES256 has 32byte keys == 256 bits */
+#define RANDOM_MAX_KEY_SIZE	32
+
+/*
+ * The minimum number of bits of entropy before we wake up a read on
+ * /dev/random.  We also wait for reseed_count>0 and we do a 
+ * random_reseed() once we do wake up.
+ */
+static int random_read_wakeup_thresh = 64;
+
+/*
+ * If the entropy count falls under this number of bits, then we
+ * should wake up processes which are selecting or polling on write
+ * access to /dev/random.
+ */
+static int random_write_wakeup_thresh = 128;
+
+/*
+ * When the input pool goes over trickle_thresh, start dropping most
+ * samples to avoid wasting CPU time and reduce lock contention.
+ */
+
+static int trickle_thresh = DEFAULT_POOL_SIZE * 7;
+
+static DEFINE_PER_CPU(int, trickle_count) = 0;
+
+#define POOLBYTES\
+	( (1<<random_state->pool_number) * random_state->digestsize )
+#define POOLBITS	( POOLBYTES * 8 )
+
+/*
+ * Linux 2.2 compatibility
+ */
+#ifndef DECLARE_WAITQUEUE
+#define DECLARE_WAITQUEUE(WAIT, PTR)	struct wait_queue WAIT = { PTR, NULL }
+#endif
+#ifndef DECLARE_WAIT_QUEUE_HEAD
+#define DECLARE_WAIT_QUEUE_HEAD(WAIT) struct wait_queue *WAIT
+#endif
+
+/*
+ * Static global variables
+ */
+static struct entropy_store *random_state; /* The default global store */
+static DECLARE_WAIT_QUEUE_HEAD(random_read_wait);
+static DECLARE_WAIT_QUEUE_HEAD(random_write_wait);
+
+/*
+ * Forward procedure declarations
+ */
+#ifdef CONFIG_SYSCTL
+static void sysctl_init_random(struct entropy_store *random_state);
+#endif
+
+/*****************************************************************
+ *
+ * Utility functions, with some ASM defined functions for speed
+ * purposes
+ * 
+ *****************************************************************/
+
+/*
+ * More asm magic....
+ * 
+ * For entropy estimation, we need to do an integral base 2
+ * logarithm.  
+ *
+ * Note the "12bits" suffix - this is used for numbers between
+ * 0 and 4095 only.  This allows a few shortcuts.
+ */
+#if 0	/* Slow but clear version */
+static inline __u32 int_ln_12bits(__u32 word)
+{
+	__u32 nbits = 0;
+	
+	while (word >>= 1)
+		nbits++;
+	return nbits;
+}
+#else	/* Faster (more clever) version, courtesy Colin Plumb */
+static inline __u32 int_ln_12bits(__u32 word)
+{
+	/* Smear msbit right to make an n-bit mask */
+	word |= word >> 8;
+	word |= word >> 4;
+	word |= word >> 2;
+	word |= word >> 1;
+	/* Remove one bit to make this a logarithm */
+	word >>= 1;
+	/* Count the bits set in the word */
+	word -= (word >> 1) & 0x555;
+	word = (word & 0x333) + ((word >> 2) & 0x333);
+	word += (word >> 4);
+	word += (word >> 8);
+	return word & 15;
+}
+#endif
+
+#if 0
+	#define DEBUG_ENT(fmt, arg...) printk("random: " fmt, ## arg)
+#else
+	#define DEBUG_ENT(fmt, arg...) do {} while (0)
+#endif
+#if 0
+	#define STATS_ENT(fmt, arg...) printk("random-stats: " fmt, ## arg)
+#else
+	#define STATS_ENT(fmt, arg...) do {} while (0)
+#endif
+
+
+/**********************************************************************
+ *
+ * OS independent entropy store.   Here are the functions which handle
+ * storing entropy in an entropy pool.
+ * 
+ **********************************************************************/
+
+struct entropy_store {
+	const char *digestAlgo;
+	unsigned int  digestsize;
+	struct crypto_tfm *pools[1<<DEFAULT_POOL_NUMBER];
+	/* optional, handy for statistics */
+	unsigned int pools_bytes[1<<DEFAULT_POOL_NUMBER];
+
+	const char *cipherAlgo;
+	/* the key */
+	unsigned char key[RANDOM_MAX_DIGEST_SIZE];
+	unsigned int  keysize;
+	/* the CTR value */
+	unsigned char iv[16];
+	unsigned int  blocksize;
+	struct crypto_tfm *cipher;
+
+	/* 2^pool_number # of pools */
+	unsigned int  pool_number;
+	/* current pool to add into */
+	unsigned int  pool_index;
+	/* size of the first pool */
+	unsigned int  pool0_len;
+	/* number of time we have reset */
+	unsigned int  reseed_count;
+	/* time in msec of the last reseed */
+	time_t reseed_time;
+	/* digest used during random_reseed() */
+	struct crypto_tfm *reseedHash;
+	/* cipher used for network randomness */
+	struct crypto_tfm *networkCipher;
+	/* flag indicating if networkCipher has been seeded */
+	char networkCipher_ready;
+
+	/* read-write data: */
+	spinlock_t lock ____cacheline_aligned_in_smp;
+	int		entropy_count;
+#if RANDOM_NO_ENTROPY_COUNT
+	int		entropy_count_bogus;
+#endif
+};
+
+/*
+ * 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 poolnum, struct entropy_store **ret_bucket)
+{
+	struct  entropy_store   *r;
+	unsigned long pool_number;
+	int     keysize, i, j;
+
+	pool_number = poolnum;
+
+	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
+	if (!r) {
+		return -ENOMEM;
+	}
+
+	memset (r, 0, sizeof(struct entropy_store));
+	r->pool_number = pool_number;
+	r->digestAlgo = RANDOM_DEFAULT_DIGEST_ALGO;
+
+	DEBUG_ENT("create_entropy_store() pools=%u index=%u\n",
+			1<<pool_number, r->pool_index);
+	for (i=0; i<(1<<pool_number); i++) {
+		DEBUG_ENT("create_entropy_store() i=%i index=%u\n",
+				i, r->pool_index);
+		r->pools[i] = crypto_alloc_tfm(r->digestAlgo, 0);
+		if (r->pools[i] == NULL) {
+			for (j=0; j<i; j++) {
+				if (r->pools[j] != NULL) {
+					kfree(r->pools[j]);
+				}
+			}
+			kfree(r);
+			return -ENOMEM;
+		}
+		crypto_digest_init( r->pools[i] );
+	}
+	r->lock = SPIN_LOCK_UNLOCKED;
+	*ret_bucket = r;
+
+	r->cipherAlgo = RANDOM_DEFAULT_CIPHER_ALGO;
+	if ((r->cipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+
+	/* If the HASH's output is greater then the cipher's keysize, truncate
+	 * to the cipher's keysize */
+	keysize = crypto_tfm_alg_max_keysize(r->cipher);
+	r->digestsize = crypto_tfm_alg_digestsize(r->pools[0]);
+	r->blocksize = crypto_tfm_alg_blocksize(r->cipher);
+
+	r->keysize = (keysize < r->digestsize) ? keysize : r->digestsize;
+DEBUG_ENT("create_RANDOM %u %u %u\n", keysize, r->digestsize, r->keysize);
+
+	if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+		return -EINVAL;
+	}
+
+	/* digest used during random-reseed() */
+	if ((r->reseedHash=crypto_alloc_tfm(r->digestAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+	/* cipher used for network randomness */
+	if ((r->networkCipher=crypto_alloc_tfm(r->cipherAlgo, 0)) == NULL) {
+		return -ENOMEM;
+	}
+
+	return 0;
+}
+
+/*
+ * This function adds a byte into the entropy "pool".  It does not
+ * update the entropy estimate.  The caller should call
+ * credit_entropy_store if this is appropriate.
+ */
+static void add_entropy_words(struct entropy_store *r, const __u32 *in,
+			      int nwords, int dst_pool)
+{
+	unsigned long flags;
+	struct scatterlist sg[1];
+	static unsigned int totalBytes=0;
+	static unsigned int keyidx = 0;
+
+	if (r == NULL)
+		return;
+
+	spin_lock_irqsave(&r->lock, flags);
+
+	totalBytes += nwords * sizeof(__u32);
+
+	sg[0].page = virt_to_page(in);
+	sg[0].offset = offset_in_page(in);
+	sg[0].length = nwords*sizeof(__u32);
+
+	if (dst_pool == -1) {
+		r->pools_bytes[r->pool_index] += nwords * sizeof(__u32);
+		crypto_digest_update(r->pools[r->pool_index], sg, 1);
+		if (r->pool_index == 0) {
+			r->pool0_len += nwords*sizeof(__u32);
+		}
+		/* idx = (idx + r) mod ( (2^N)-1 ) */
+		r->pool_index = (r->pool_index + r->key[keyidx])
+					& ((1<<random_state->pool_number)-1);
+		/* first 8 bytes of the key are used, 8 * 8 = 64 bits */
+		keyidx = (keyidx + 1) & 7;
+	} else {
+		/* Let's make sure nothing mean is happening... */
+		dst_pool &= (1<<random_state->pool_number) - 1;
+		r->pools_bytes[dst_pool] += nwords * sizeof(__u32);
+		crypto_digest_update(r->pools[dst_pool], sg, 1);
+	}
+DEBUG_ENT("r->pool0_len = %u\n", r->pool0_len);
+
+
+	spin_unlock_irqrestore(&r->lock, flags);
+DEBUG_ENT("0 add_entropy_words() nwords=%u pool[i].bytes=%u total=%u\n",
+	nwords, r->pools_bytes[r->pool_index], totalBytes);
+}
+
+/*
+ * Credit (or debit) the entropy store with n bits of entropy
+ */
+static void credit_entropy_store(struct entropy_store *r, int nbits)
+{
+	unsigned long flags;
+
+	spin_lock_irqsave(&r->lock, flags);
+
+	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 + nbits > POOLBITS) {
+		r->entropy_count = POOLBITS;
+	} else {
+		r->entropy_count += nbits;
+		if (nbits)
+			DEBUG_ENT("%04d : added %d bits\n",
+				  r->entropy_count,
+				  nbits);
+	}
+
+	spin_unlock_irqrestore(&r->lock, flags);
+}
+
+/**********************************************************************
+ *
+ * Entropy batch input management
+ *
+ * We batch entropy to be added to avoid increasing interrupt latency
+ *
+ **********************************************************************/
+
+struct sample {
+	__u32 data[2];
+	int credit;
+};
+
+static struct sample *batch_entropy_pool, *batch_entropy_copy;
+static int	batch_head, batch_tail;
+static spinlock_t batch_lock = SPIN_LOCK_UNLOCKED;
+
+static int	batch_max;
+static void batch_entropy_process(void *private_);
+static DECLARE_WORK(batch_work, batch_entropy_process, NULL);
+
+/* note: the size must be a power of 2 */
+static int __init batch_entropy_init(int size, struct entropy_store *r)
+{
+	batch_entropy_pool = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
+	if (!batch_entropy_pool)
+		return -1;
+	batch_entropy_copy = kmalloc(size*sizeof(struct sample), GFP_KERNEL);
+	if (!batch_entropy_copy) {
+		kfree(batch_entropy_pool);
+		return -1;
+	}
+	batch_head = batch_tail = 0;
+	batch_work.data = r;
+	batch_max = size;
+	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 by keventd.
+ */
+void batch_entropy_store(u32 a, u32 b, int num)
+{
+	int new;
+	unsigned long flags;
+
+	if (!batch_max)
+		return;
+
+	spin_lock_irqsave(&batch_lock, flags);
+
+	batch_entropy_pool[batch_head].data[0] = a;
+	batch_entropy_pool[batch_head].data[1] = b;
+	batch_entropy_pool[batch_head].credit = num;
+
+	if (((batch_head - batch_tail) & (batch_max-1)) >= (batch_max / 2)) {
+		/*
+		 * Schedule it for the next timer tick:
+		 */
+		schedule_delayed_work(&batch_work, 1);
+	}
+
+	new = (batch_head+1) & (batch_max-1);
+	if (new == batch_tail) {
+		DEBUG_ENT("batch entropy buffer full\n");
+	} else {
+		batch_head = new;
+	}
+
+	spin_unlock_irqrestore(&batch_lock, flags);
+}
+
+EXPORT_SYMBOL(batch_entropy_store);
+
+/*
+ * 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 max_entropy = POOLBITS;
+	unsigned head, tail;
+
+	/* Mixing into the pool is expensive, so copy over the batch
+	 * data and release the batch lock. The pool is at least half
+	 * full, so don't worry too much about copying only the used
+	 * part.
+	 */
+	spin_lock_irq(&batch_lock);
+
+	memcpy(batch_entropy_copy, batch_entropy_pool,
+	       batch_max*sizeof(struct sample));
+
+	head = batch_head;
+	tail = batch_tail;
+	batch_tail = batch_head;
+
+	spin_unlock_irq(&batch_lock);
+
+	while (head != tail) {
+		if (random_state->entropy_count >= max_entropy) {
+			max_entropy = POOLBITS;
+		}
+		/*
+		 * Only credit if we're feeding into pool[0]
+		 * Otherwise we'd be assuming entropy in pool[31] would be
+		 * usable when we read.  This is conservative, but it'll
+		 * not over-credit our entropy estimate for users of
+		 * /dev/random, /dev/urandom will not be effected.
+		 */
+		if (random_state->pool_index == 0) {
+			credit_entropy_store(random_state,
+				batch_entropy_copy[tail].credit);
+		}
+		add_entropy_words(random_state,
+			batch_entropy_copy[tail].data, 2, -1);
+;
+
+		tail = (tail+1) & (batch_max-1);
+	}
+	if (random_state->entropy_count >= random_read_wakeup_thresh
+		&& random_state->reseed_count != 0)
+		wake_up_interruptible(&random_read_wait);
+}
+
+/*********************************************************************
+ *
+ * Entropy input management
+ *
+ *********************************************************************/
+
+/* There is one of these per entropy source */
+struct timer_rand_state {
+	__u32		last_time;
+	__s32		last_delta,last_delta2;
+	int		dont_count_entropy:1;
+};
+
+static struct timer_rand_state input_timer_state;
+static struct timer_rand_state extract_timer_state;
+static struct timer_rand_state *irq_timer_state[NR_IRQS];
+
+/*
+ * This function adds entropy to the entropy "pool" by using timing
+ * delays.  It uses the timer_rand_state structure to make an estimate
+ * of how many bits of entropy this call has added to the pool.
+ *
+ * The number "num" is also added to the pool - it should somehow describe
+ * the type of event which just happened.  This is currently 0-255 for
+ * keyboard scan codes, and 256 upwards for interrupts.
+ * On the i386, this is assumed to be at most 16 bits, and the high bits
+ * are used for a high-resolution timer.
+ *
+ */
+static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
+{
+	__u32		time;
+	__s32		delta, delta2, delta3;
+	int		entropy = 0;
+
+	/* if over the trickle threshold, use only 1 in 4096 samples */
+	if ( random_state->entropy_count > trickle_thresh &&
+	     (__get_cpu_var(trickle_count)++ & 0xfff))
+		return;
+
+#if defined (__i386__) || defined (__x86_64__)
+	if (cpu_has_tsc) {
+		__u32 high;
+		rdtsc(time, high);
+		num ^= high;
+	} else {
+		time = jiffies;
+	}
+#elif defined (__sparc_v9__)
+	unsigned long tick = tick_ops->get_tick();
+
+	time = (unsigned int) tick;
+	num ^= (tick >> 32UL);
+#else
+	time = jiffies;
+#endif
+
+	/*
+	 * Calculate number of bits of randomness we probably added.
+	 * We take into account the first, second and third-order deltas
+	 * in order to make our estimate.
+	 */
+	if (!state->dont_count_entropy) {
+		delta = time - state->last_time;
+		state->last_time = time;
+
+		delta2 = delta - state->last_delta;
+		state->last_delta = delta;
+
+		delta3 = delta2 - state->last_delta2;
+		state->last_delta2 = delta2;
+
+		if (delta < 0)
+			delta = -delta;
+		if (delta2 < 0)
+			delta2 = -delta2;
+		if (delta3 < 0)
+			delta3 = -delta3;
+		if (delta > delta2)
+			delta = delta2;
+		if (delta > delta3)
+			delta = delta3;
+
+		/*
+		 * delta is now minimum absolute delta.
+		 * Round down by 1 bit on general principles,
+		 * and limit entropy entimate to 12 bits.
+		 */
+		delta >>= 1;
+		delta &= (1 << 12) - 1;
+
+		entropy = int_ln_12bits(delta);
+	}
+	batch_entropy_store(num, time, entropy);
+}
+
+extern void add_input_randomness(unsigned int type, unsigned int code,
+			 unsigned int value)
+{
+	static unsigned int last_value;
+
+	/* ignore autorepeat (multiple key down w/o key up) */
+	if (value != last_value)
+		return;
+
+	DEBUG_ENT("input event\n");
+	last_value = value;
+	add_timer_randomness(&input_timer_state,
+			(type << 4) ^ code ^ (code >> 4) ^ value);
+}
+
+void add_interrupt_randomness(int irq)
+{
+	if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
+		return;
+
+	add_timer_randomness(irq_timer_state[irq], 0x100+irq);
+}
+
+EXPORT_SYMBOL(add_interrupt_randomness);
+
+void add_disk_randomness(struct gendisk *disk)
+{
+	if (!disk || !disk->random)
+		return;
+	/* first major is 1, so we get >= 0x200 here */
+	add_timer_randomness(disk->random,
+				0x100+MKDEV(disk->major, disk->first_minor));
+}
+
+EXPORT_SYMBOL(add_disk_randomness);
+
+/*********************************************************************
+ *
+ * Entropy extraction routines
+ *
+ *********************************************************************/
+
+#define EXTRACT_ENTROPY_USER		1
+#define EXTRACT_ENTROPY_LIMIT		4
+
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+			       size_t nbytes, int flags);
+
+static inline void increment_iv(unsigned char *iv, const unsigned int IVsize) {
+	switch (IVsize) {
+	case 8:
+		if (++((u32*)iv)[0])
+			++((u32*)iv)[1];
+	break;
+
+	case 16:
+		if (++((u32*)iv)[0])
+			if (++((u32*)iv)[1])
+				if (++((u32*)iv)[2])
+					++((u32*)iv)[3];
+	break;
+
+	default:
+		{
+		int i;
+		for (i=0; i<IVsize; i++)
+			if (++iv[i])
+				break;
+		}
+	break;
+	}
+}
+
+/*
+ * Fortuna's Reseed
+ * 
+ * Key' = hash(Key || hash(pool[a0]) || hash(pool[a1]) || ...)
+ * where {a0,a1,...} are facators of r->reseed_count+1 which are of the form
+ * 2^j, 0<=j.
+ * Prevents backtracking attacks and with event inputs, supports forward
+ * secrecy
+ */
+static void random_reseed(struct entropy_store *r, size_t nbytes, int flags) {
+	struct scatterlist sg[1];
+	unsigned int i, deduct;
+	unsigned char tmp[RANDOM_MAX_DIGEST_SIZE];
+	unsigned long cpuflags;
+ 
+	deduct = (r->keysize < r->digestsize) ? r->keysize : r->digestsize;
+
+	/* Hold lock while accounting */
+	spin_lock_irqsave(&r->lock, cpuflags);
+
+	DEBUG_ENT("%04d : trying to extract %d bits\n",
+		  random_state->entropy_count,
+		  deduct * 8);
+
+	/*
+	 * Don't extract more data than in the entropy in the pooling system
+	 */
+	if (flags & EXTRACT_ENTROPY_LIMIT && nbytes >= r->entropy_count / 8) {
+		nbytes = r->entropy_count / 8;
+	}
+
+	if (deduct*8 <= r->entropy_count) {
+		r->entropy_count -= deduct*8;
+	} else {
+		r->entropy_count = 0;
+	}
+
+	if (r->entropy_count < random_write_wakeup_thresh)
+		wake_up_interruptible(&random_write_wait);
+
+	DEBUG_ENT("%04d : debiting %d bits%s\n",
+		  random_state->entropy_count,
+		  deduct * 8,
+		  flags & EXTRACT_ENTROPY_LIMIT ? "" : " (unlimited)");
+
+	r->reseed_count++;
+	r->pool0_len = 0;
+
+	/* Entropy accounting done, release lock. */
+	spin_unlock_irqrestore(&r->lock, cpuflags);
+
+	DEBUG_ENT("random_reseed count=%u\n", r->reseed_count);
+
+	crypto_digest_init(r->reseedHash);
+
+	sg[0].page = virt_to_page(r->key);
+	sg[0].offset = offset_in_page(r->key);
+	sg[0].length = r->keysize;
+	crypto_digest_update(r->reseedHash, sg, 1);
+
+#define TESTBIT(VAL, N)\
+  ( ((VAL) >> (N)) & 1 )
+	for (i=0; i<(1<<r->pool_number); i++) {
+		/* using pool[i] if r->reseed_count is divisible by 2^i
+		 * since 2^0 == 1, we always use pool[0]
+		 */
+		if ( (i==0)  ||  TESTBIT(r->reseed_count,i)==0 ) {
+			crypto_digest_final(r->pools[i], tmp);
+
+			sg[0].page = virt_to_page(tmp);
+			sg[0].offset = offset_in_page(tmp);
+			sg[0].length = r->keysize;
+			crypto_digest_update(r->reseedHash, sg, 1);
+
+			crypto_digest_init(r->pools[i]);
+			/* Each pool carries its past state forward */
+			crypto_digest_update(r->pools[i], sg, 1);
+		} else {
+			/* pool j is only used once every 2^j times */
+			break;
+		}
+	}
+#undef TESTBIT
+
+	crypto_digest_final(r->reseedHash, r->key);
+	crypto_cipher_setkey(r->cipher, r->key, r->keysize);
+	increment_iv(r->iv, r->blocksize);
+}
+
+static inline time_t get_msectime(void) {
+	struct timeval tv;
+	do_gettimeofday(&tv);
+	return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
+}
+
+/*
+ * This function extracts randomness from the "entropy pool", and
+ * returns it in a buffer.  This function computes how many remaining
+ * 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.
+ */
+static ssize_t extract_entropy(struct entropy_store *r, void * buf,
+			       size_t nbytes, int flags)
+{
+	ssize_t ret, i;
+	__u32 tmp[RANDOM_MAX_BLOCK_SIZE/sizeof(__u32)];
+	struct scatterlist sgiv[1], sgtmp[1];
+	time_t nowtime;
+
+	/* Redundant, but just in case... */
+	if (r->entropy_count > POOLBITS)
+		r->entropy_count = POOLBITS;
+
+	/*
+	 * To keep the possibility of collisions down, limit the number of
+	 * output bytes per block cipher key.
+	 */
+	if (RANDOM_MAX_EXTRACT_SIZE < nbytes)
+		nbytes = RANDOM_MAX_EXTRACT_SIZE;
+
+	if (flags & EXTRACT_ENTROPY_LIMIT) {
+		/* if in blocking, only output upto the entropy estimate */
+		if (r->entropy_count/8 < nbytes)
+			nbytes = r->entropy_count/8;
+		/*
+		 * if blocking and there is no entropy by our estimate,
+		 * break out now.
+		 */
+		if (nbytes == 0)
+			return 0;
+	}
+
+	/*
+	 * If reading in non-blocking mode, pace ourselves in using up the pool
+	 * system's entropy.  reseed every .1 sec (Ferguson/Schnier)
+	 */
+	if (! (flags & EXTRACT_ENTROPY_LIMIT) ) {
+		nowtime = get_msectime();
+		if (r->pool0_len > 64
+		&& (nowtime - r->reseed_time) > RANDOM_RESEED_INTERVAL) {
+			random_reseed(r, nbytes, flags);
+			r->reseed_time = nowtime;
+		}
+	}
+
+	sgiv[0].page = virt_to_page(r->iv);
+	sgiv[0].offset = offset_in_page(r->iv);
+	sgiv[0].length = r->blocksize;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = r->blocksize;
+
+	ret = 0;
+	while (nbytes) {
+		/*
+		 * Check if we need to break out or reschedule....
+		 */
+		if ((flags & EXTRACT_ENTROPY_USER) && need_resched()) {
+			if (signal_pending(current)) {
+				if (ret == 0)
+					ret = -ERESTARTSYS;
+				break;
+			}
+
+			DEBUG_ENT("%04d : extract sleeping (%d bytes left)\n",
+				  random_state->entropy_count,
+				  nbytes);
+
+			schedule();
+
+			/*
+			 * when we wakeup, there will be more data in our
+			 * pooling system so we may reseed
+			 */
+			nowtime = get_msectime();
+			if (r->pool0_len > 64
+			&& (nowtime-r->reseed_time) > RANDOM_RESEED_INTERVAL) {
+				random_reseed(r, nbytes, flags);
+				r->reseed_time = nowtime;
+			}
+
+			DEBUG_ENT("%04d : extract woke up\n",
+				  random_state->entropy_count);
+		}
+
+		/*
+		 * Reading from /dev/random, we limit this to the amount
+		 * of entropy to deduct from our estimate.  This estimate is
+		 * most naturally updated from inside Fortuna-reseed, so we
+		 * limit our block size here.
+		 *
+		 * At most, Fortuna will use e=min(r->digestsize, r->keysize) of
+		 * entropy to reseed.
+		 */
+		if (flags & EXTRACT_ENTROPY_LIMIT) {
+			r->reseed_time = get_msectime();
+			random_reseed(r, nbytes, flags);
+		}
+
+		crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+		increment_iv(r->iv, r->blocksize);
+		
+		/* Copy data to destination buffer */
+		i = (nbytes < r->blocksize) ? nbytes : r->blocksize;
+		if (flags & EXTRACT_ENTROPY_USER) {
+			i -= copy_to_user(buf, (__u8 const *)tmp, i);
+			if (!i) {
+				ret = -EFAULT;
+				break;
+			}
+		} else
+			memcpy(buf, (__u8 const *)tmp, i);
+		nbytes -= i;
+		buf += i;
+		ret += i;
+	}
+
+	/* generate a new key */
+	/* take into account the possibility that keysize >= blocksize */
+	for (i=0; i+r->blocksize<=r->keysize; i+=r->blocksize) {
+		memcpy(tmp, r->key+i, r->blocksize);
+		crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+		increment_iv(r->iv, r->blocksize);
+	}
+	memcpy(tmp, r->key+i, r->keysize-i);
+	memset(tmp+r->keysize-i, 0, r->blocksize-(r->keysize-i));
+	crypto_cipher_encrypt(r->cipher, sgtmp, sgiv, r->blocksize);
+	increment_iv(r->iv, r->blocksize);
+
+	if (crypto_cipher_setkey(r->cipher, r->key, r->keysize)) {
+		return -EINVAL;
+	}
+
+	/* Wipe data just returned from memory */
+	memset(tmp, 0, sizeof(tmp));
+	
+	return ret;
+}
+
+/*
+ * This function is the exported kernel interface.  It returns some
+ * number of good random numbers, suitable for seeding TCP sequence
+ * numbers, etc.
+ */
+void get_random_bytes(void *buf, int nbytes)
+{
+	if (random_state)
+		extract_entropy(random_state, (char *) buf, nbytes, 0);
+	else
+		printk(KERN_NOTICE "get_random_bytes called before "
+				   "random driver initialization\n");
+}
+
+EXPORT_SYMBOL(get_random_bytes);
+
+/*********************************************************************
+ *
+ * Functions to interface with Linux
+ *
+ *********************************************************************/
+
+/*
+ * Initialize the random pool with standard stuff.
+ * This is not secure random data, but it can't hurt us and people scream
+ * when you try to remove it.
+ *
+ * NOTE: This is an OS-dependent function.
+ */
+static void init_std_data(struct entropy_store *r)
+{
+	struct timeval 	tv;
+	__u32		words[2];
+	char 		*p;
+	int		i;
+
+	do_gettimeofday(&tv);
+	words[0] = tv.tv_sec;
+	words[1] = tv.tv_usec;
+	batch_entropy_store(words[0], words[1], -1);
+
+	/*
+	 *	This doesn't lock system.utsname. However, we are generating
+	 *	entropy so a race with a name set here is fine.
+	 */
+	p = (char *) &system_utsname;
+	for (i = sizeof(system_utsname) / sizeof(words); i; i--) {
+		memcpy(words, p, sizeof(words));
+		batch_entropy_store(words[0], words[1], -1);
+		p += sizeof(words);
+	}
+}
+
+static int __init rand_initialize(void)
+{
+	int i;
+
+	if (create_entropy_store(DEFAULT_POOL_NUMBER, &random_state))
+		goto err;
+	if (batch_entropy_init(BATCH_ENTROPY_SIZE, random_state))
+		goto err;
+	init_std_data(random_state);
+#ifdef CONFIG_SYSCTL
+	sysctl_init_random(random_state);
+#endif
+	for (i = 0; i < NR_IRQS; i++)
+		irq_timer_state[i] = NULL;
+	memset(&input_timer_state, 0, sizeof(struct timer_rand_state));
+	memset(&extract_timer_state, 0, sizeof(struct timer_rand_state));
+	extract_timer_state.dont_count_entropy = 1;
+	return 0;
+err:
+	return -1;
+}
+module_init(rand_initialize);
+
+void rand_initialize_irq(int irq)
+{
+	struct timer_rand_state *state;
+	
+	if (irq >= NR_IRQS || irq_timer_state[irq])
+		return;
+
+	/*
+	 * If kmalloc returns null, we just won't use that entropy
+	 * source.
+	 */
+	state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
+	if (state) {
+		memset(state, 0, sizeof(struct timer_rand_state));
+		irq_timer_state[irq] = state;
+	}
+}
+ 
+void rand_initialize_disk(struct gendisk *disk)
+{
+	struct timer_rand_state *state;
+	
+	/*
+	 * If kmalloc returns null, we just won't use that entropy
+	 * source.
+	 */
+	state = kmalloc(sizeof(struct timer_rand_state), GFP_KERNEL);
+	if (state) {
+		memset(state, 0, sizeof(struct timer_rand_state));
+		disk->random = state;
+	}
+}
+
+static ssize_t
+random_read(struct file * file, char __user * buf, size_t nbytes, loff_t *ppos)
+{
+	DECLARE_WAITQUEUE(wait, current);
+	ssize_t	n, retval = 0, count = 0;
+	
+	if (nbytes == 0)
+		return 0;
+
+	while (nbytes > 0) {
+		n = nbytes;
+
+		DEBUG_ENT("%04d : reading %d bits, p: %d s: %d\n",
+			  random_state->entropy_count,
+			  n*8, random_state->entropy_count,
+			  random_state->entropy_count);
+
+		n = extract_entropy(random_state, buf, n,
+				    EXTRACT_ENTROPY_USER |
+				    EXTRACT_ENTROPY_LIMIT);
+
+		DEBUG_ENT("%04d : read got %d bits (%d needed, reseeds=%d)\n",
+			  random_state->entropy_count,
+			  random_state->reseed_count,
+			  n*8, (nbytes-n)*8);
+
+		if (n == 0) {
+			if (file->f_flags & O_NONBLOCK) {
+				retval = -EAGAIN;
+				break;
+			}
+			if (signal_pending(current)) {
+				retval = -ERESTARTSYS;
+				break;
+			}
+
+			DEBUG_ENT("%04d : sleeping?\n",
+				  random_state->entropy_count);
+
+			set_current_state(TASK_INTERRUPTIBLE);
+			add_wait_queue(&random_read_wait, &wait);
+
+			if (random_state->entropy_count / 8 == 0
+				||  random_state->reseed_count == 0)
+				schedule();
+
+			set_current_state(TASK_RUNNING);
+			remove_wait_queue(&random_read_wait, &wait);
+
+			DEBUG_ENT("%04d : waking up\n",
+				  random_state->entropy_count);
+
+			continue;
+		}
+
+		if (n < 0) {
+			retval = n;
+			break;
+		}
+		count += n;
+		buf += n;
+		nbytes -= n;
+		break;		/* This break makes the device work */
+				/* like a named pipe */
+	}
+
+	/*
+	 * If we gave the user some bytes, update the access time.
+	 */
+	if (count)
+		file_accessed(file);
+	
+	return (count ? count : retval);
+}
+
+static ssize_t
+urandom_read(struct file * file, char __user * buf,
+		      size_t nbytes, loff_t *ppos)
+{
+	/* Don't return anything untill we've reseeded at least once */
+	if (random_state->reseed_count == 0)
+		return 0;
+
+	return extract_entropy(random_state, buf, nbytes,
+			       EXTRACT_ENTROPY_USER);
+}
+
+static unsigned int
+random_poll(struct file *file, poll_table * wait)
+{
+	unsigned int mask;
+
+	poll_wait(file, &random_read_wait, wait);
+	poll_wait(file, &random_write_wait, wait);
+	mask = 0;
+	if (random_state->entropy_count >= random_read_wakeup_thresh)
+		mask |= POLLIN | POLLRDNORM;
+	if (random_state->entropy_count < random_write_wakeup_thresh)
+		mask |= POLLOUT | POLLWRNORM;
+	return mask;
+}
+
+static ssize_t
+random_write(struct file * file, const char __user * buffer,
+	     size_t count, loff_t *ppos)
+{
+	static int	idx = 0;
+	int		ret = 0;
+	size_t		bytes;
+	__u32 		buf[16];
+	const char 	__user *p = buffer;
+	size_t		c = count;
+
+	while (c > 0) {
+		bytes = min(c, sizeof(buf));
+
+		bytes -= copy_from_user(&buf, p, bytes);
+		if (!bytes) {
+			ret = -EFAULT;
+			break;
+		}
+		c -= bytes;
+		p += bytes;
+
+		/*
+		 * Use input data rotates though the pools independantly of
+		 * system-events.
+		 *
+		 * idx = (idx + 1) mod ( (2^N)-1 )
+		 */
+		idx = (idx + 1) & ((1<<random_state->pool_number)-1);
+		add_entropy_words(random_state, buf, bytes, idx);
+	}
+	if (p == buffer) {
+		return (ssize_t)ret;
+	} else {
+		file->f_dentry->d_inode->i_mtime = CURRENT_TIME;
+		mark_inode_dirty(file->f_dentry->d_inode);
+		return (ssize_t)(p - buffer);
+	}
+}
+
+static int
+random_ioctl(struct inode * inode, struct file * file,
+	     unsigned int cmd, unsigned long arg)
+{
+	int size, ent_count;
+	int __user *p = (int __user *)arg;
+	int retval;
+	
+	switch (cmd) {
+	case RNDGETENTCNT:
+		ent_count = random_state->entropy_count;
+		if (put_user(ent_count, p))
+			return -EFAULT;
+		return 0;
+	case RNDADDTOENTCNT:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
+		if (get_user(ent_count, p))
+			return -EFAULT;
+		credit_entropy_store(random_state, ent_count);
+		/*
+		 * Wake up waiting processes if we have enough
+		 * entropy.
+		 */
+		if (random_state->entropy_count >= random_read_wakeup_thresh
+			&&  random_state->reseed_count != 0)
+			wake_up_interruptible(&random_read_wait);
+		return 0;
+	case RNDGETPOOL:
+		/* can't do this anymore */
+		return 0;
+	case RNDADDENTROPY:
+		if (!capable(CAP_SYS_ADMIN))
+			return -EPERM;
+		if (get_user(ent_count, p++))
+			return -EFAULT;
+		if (ent_count < 0)
+			return -EINVAL;
+		if (get_user(size, p++))
+			return -EFAULT;
+		retval = random_write(file, (const char __user *) p,
+				      size, &file->f_pos);
+		if (retval < 0)
+			return retval;
+		credit_entropy_store(random_state, ent_count);
+		/*
+		 * Wake up waiting processes if we have enough
+		 * entropy.
+		 */
+		if (random_state->entropy_count >= random_read_wakeup_thresh
+			&&  random_state->reseed_count != 0)
+			wake_up_interruptible(&random_read_wait);
+		return 0;
+	case RNDZAPENTCNT:
+		/* Can't do this anymore */
+		return 0;
+	case RNDCLEARPOOL:
+		/* Can't to this anymore */
+		return 0;
+	default:
+		return -EINVAL;
+	}
+}
+
+struct file_operations random_fops = {
+	.read		= random_read,
+	.write		= random_write,
+	.poll		= random_poll,
+	.ioctl		= random_ioctl,
+};
+
+struct file_operations urandom_fops = {
+	.read		= urandom_read,
+	.write		= random_write,
+	.ioctl		= random_ioctl,
+};
+
+/***************************************************************
+ * Random UUID interface
+ * 
+ * Used here for a Boot ID, but can be useful for other kernel 
+ * drivers.
+ ***************************************************************/
+
+/*
+ * Generate random UUID
+ */
+void generate_random_uuid(unsigned char uuid_out[16])
+{
+	get_random_bytes(uuid_out, 16);
+	/* Set UUID version to 4 --- truely random generation */
+	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
+	/* Set the UUID variant to DCE */
+	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+}
+
+EXPORT_SYMBOL(generate_random_uuid);
+
+/********************************************************************
+ *
+ * Sysctl interface
+ *
+ ********************************************************************/
+
+#ifdef CONFIG_SYSCTL
+
+#include <linux/sysctl.h>
+
+static int sysctl_poolsize;
+static int min_read_thresh, max_read_thresh;
+static int min_write_thresh, max_write_thresh;
+static char sysctl_bootid[16];
+
+static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
+			    void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	int	ret;
+
+	sysctl_poolsize = POOLBITS;
+
+	ret = proc_dointvec(table, write, filp, buffer, lenp, ppos);
+	if (ret || !write ||
+	    (sysctl_poolsize == POOLBITS))
+		return ret;
+
+	return ret; /* can't change the pool size in fortuna */
+}
+
+static int poolsize_strategy(ctl_table *table, int __user *name, int nlen,
+			     void __user *oldval, size_t __user *oldlenp,
+			     void __user *newval, size_t newlen, void **context)
+{
+	int	len;
+	
+	sysctl_poolsize = POOLBITS;
+
+	/*
+	 * We only handle the write case, since the read case gets
+	 * handled by the default handler (and we don't care if the
+	 * write case happens twice; it's harmless).
+	 */
+	if (newval && newlen) {
+		len = newlen;
+		if (len > table->maxlen)
+			len = table->maxlen;
+		if (copy_from_user(table->data, newval, len))
+			return -EFAULT;
+	}
+
+	return 0;
+}
+
+/*
+ * These functions is used to return both the bootid UUID, and random
+ * UUID.  The difference is in whether table->data is NULL; if it is,
+ * then a new UUID is generated and returned to the user.
+ * 
+ * If the user accesses this via the proc interface, it will be returned
+ * as an ASCII string in the standard UUID format.  If accesses via the 
+ * sysctl system call, it is returned as 16 bytes of binary data.
+ */
+static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
+			void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	ctl_table	fake_table;
+	unsigned char	buf[64], tmp_uuid[16], *uuid;
+
+	uuid = table->data;
+	if (!uuid) {
+		uuid = tmp_uuid;
+		uuid[8] = 0;
+	}
+	if (uuid[8] == 0)
+		generate_random_uuid(uuid);
+
+	sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
+		"%02x%02x%02x%02x%02x%02x",
+		uuid[0],  uuid[1],  uuid[2],  uuid[3],
+		uuid[4],  uuid[5],  uuid[6],  uuid[7],
+		uuid[8],  uuid[9],  uuid[10], uuid[11],
+		uuid[12], uuid[13], uuid[14], uuid[15]);
+	fake_table.data = buf;
+	fake_table.maxlen = sizeof(buf);
+
+	return proc_dostring(&fake_table, write, filp, buffer, lenp, ppos);
+}
+
+static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
+			 void __user *oldval, size_t __user *oldlenp,
+			 void __user *newval, size_t newlen, void **context)
+{
+	unsigned char	tmp_uuid[16], *uuid;
+	unsigned int	len;
+
+	if (!oldval || !oldlenp)
+		return 1;
+
+	uuid = table->data;
+	if (!uuid) {
+		uuid = tmp_uuid;
+		uuid[8] = 0;
+	}
+	if (uuid[8] == 0)
+		generate_random_uuid(uuid);
+
+	if (get_user(len, oldlenp))
+		return -EFAULT;
+	if (len) {
+		if (len > 16)
+			len = 16;
+		if (copy_to_user(oldval, uuid, len) ||
+		    put_user(len, oldlenp))
+			return -EFAULT;
+	}
+	return 1;
+}
+
+ctl_table random_table[] = {
+	{
+		.ctl_name	= RANDOM_POOLSIZE,
+		.procname	= "poolsize",
+		.data		= &sysctl_poolsize,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_do_poolsize,
+		.strategy	= &poolsize_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_ENTROPY_COUNT,
+		.procname	= "entropy_avail",
+		.maxlen		= sizeof(int),
+		.mode		= 0444,
+		.proc_handler	= &proc_dointvec,
+	},
+	{
+		.ctl_name	= RANDOM_READ_THRESH,
+		.procname	= "read_wakeup_threshold",
+		.data		= &random_read_wakeup_thresh,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &min_read_thresh,
+		.extra2		= &max_read_thresh,
+	},
+	{
+		.ctl_name	= RANDOM_WRITE_THRESH,
+		.procname	= "write_wakeup_threshold",
+		.data		= &random_write_wakeup_thresh,
+		.maxlen		= sizeof(int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_minmax,
+		.strategy	= &sysctl_intvec,
+		.extra1		= &min_write_thresh,
+		.extra2		= &max_write_thresh,
+	},
+	{
+		.ctl_name	= RANDOM_BOOT_ID,
+		.procname	= "boot_id",
+		.data		= &sysctl_bootid,
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.strategy	= &uuid_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_UUID,
+		.procname	= "uuid",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.strategy	= &uuid_strategy,
+	},
+	{
+		.ctl_name	= RANDOM_DIGEST_ALGO,
+		.procname	= "digest_algo",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_dostring,
+	},
+	{
+		.ctl_name	= RANDOM_CIPHER_ALGO,
+		.procname	= "cipher_algo",
+		.maxlen		= 16,
+		.mode		= 0444,
+		.proc_handler	= &proc_dostring,
+	},
+	{ .ctl_name = 0 }
+};
+
+static void sysctl_init_random(struct entropy_store *random_state)
+{
+	int i;
+
+	/* If the sys-admin doesn't want people to know how fast
+	 * random events are happening, he can set the read-threshhold
+	 * down to zero so /dev/random never blocks.  Default is to block.
+	 * This is for the paranoid loonies who think frequency analysis
+	 * would lead to something.
+	 */
+	min_read_thresh = 0;
+	min_write_thresh = 0;
+	max_read_thresh = max_write_thresh = POOLBITS;
+	for (i=0; random_table[i].ctl_name!=0; i++) {
+		switch (random_table[i].ctl_name) {
+		case RANDOM_ENTROPY_COUNT:
+			// If we don't want 
+#if RANDOM_NO_ENTROPY_COUNT
+			random_table[i].data = &random_state->entropy_count_bogus;
+			random_state->entropy_count_bogus = POOLBITS;
+#else
+			random_table[i].data = &random_state->entropy_count;
+#endif
+		break;
+
+		case RANDOM_DIGEST_ALGO:
+			random_table[i].data = (void*)random_state->digestAlgo;
+		break;
+
+		case RANDOM_CIPHER_ALGO:
+			random_table[i].data = (void*)random_state->cipherAlgo;
+		break;
+
+		default:
+		break;
+		}
+	}
+}
+#endif 	/* CONFIG_SYSCTL */
+
+/********************************************************************
+ *
+ * Random funtions for networking
+ *
+ ********************************************************************/
+
+/*
+ * TCP initial sequence number picking.  This uses the random number
+ * generator to pick an initial secret value.  This value is encrypted
+ * with the TCP endpoint information to provide a unique starting point
+ * for each pair of TCP endpoints.  This defeats attacks which rely on
+ * guessing the initial TCP sequence number.  This algorithm was
+ * suggested by Steve Bellovin, modified by Jean-Luc Cooke.
+ *
+ * Using a very strong hash was taking an appreciable amount of the total
+ * TCP connection establishment time, so this is a weaker hash,
+ * compensated for by changing the secret periodically.  This was changed
+ * again by Jean-Luc Cooke to use AES256-CBC encryption which is faster
+ * still (see `/usr/bin/openssl speed md4 sha1 aes`)
+ */
+
+/* This should not be decreased so low that ISNs wrap too fast. */
+#define REKEY_INTERVAL	(300*HZ)
+/*
+ * Bit layout of the tcp sequence numbers (before adding current time):
+ * bit 24-31: increased after every key exchange
+ * bit 0-23: hash(source,dest)
+ *
+ * The implementation is similar to the algorithm described
+ * in the Appendix of RFC 1185, except that
+ * - it uses a 1 MHz clock instead of a 250 kHz clock
+ * - it performs a rekey every 5 minutes, which is equivalent
+ * 	to a (source,dest) tulple dependent forward jump of the
+ * 	clock by 0..2^(HASH_BITS+1)
+ *
+ * Thus the average ISN wraparound time is 68 minutes instead of
+ * 4.55 hours.
+ *
+ * SMP cleanup and lock avoidance with poor man's RCU.
+ * 			Manfred Spraul <manfred@colorfullife.com>
+ * 		
+ */
+#define COUNT_BITS	8
+#define COUNT_MASK	( (1<<COUNT_BITS)-1)
+#define HASH_BITS	24
+#define HASH_MASK	( (1<<HASH_BITS)-1 )
+
+static spinlock_t ip_lock = SPIN_LOCK_UNLOCKED;
+static unsigned int ip_cnt, network_count;
+
+static void __check_and_rekey(time_t time)
+{
+	u8 tmp[RANDOM_MAX_KEY_SIZE];
+	spin_lock_bh(&ip_lock);
+
+	get_random_bytes(tmp, random_state->keysize);
+	crypto_cipher_setkey(random_state->networkCipher,
+					(const u8*)tmp,
+					random_state->keysize);
+	random_state->networkCipher_ready = 1;
+	network_count = (ip_cnt & COUNT_MASK) << HASH_BITS;
+	mb();
+	ip_cnt++;
+
+	spin_unlock_bh(&ip_lock);
+	return;
+}
+
+static inline void check_and_rekey(time_t time)
+{
+	static time_t rekey_time=0;
+
+	rmb();
+	if (!rekey_time || (time - rekey_time) > REKEY_INTERVAL) {
+		__check_and_rekey(time);
+		rekey_time = time;
+	}
+
+	return;
+}
+
+#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
+__u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr,
+				   __u16 sport, __u16 dport)
+{
+	struct timeval 	tv;
+	__u32		seq;
+	__u32		tmp[4];
+	struct scatterlist sgtmp[1];
+
+	/*
+	 * The procedure is the same as for IPv4, but addresses are longer.
+	 * Thus we must use two AES operations.
+	 */
+
+	do_gettimeofday(&tv);	/* We need the usecs below... */
+	check_and_rekey(tv.tv_sec);
+
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	/*
+	 * AES256 is 2.5 times faster then MD4 by openssl tests.
+	 * We can afford to encrypt 2 block in CBC with
+	 * and IV={(sport)<<16 | dport, 0, 0, 0}
+	 *
+	 * seq = ct[0], ct = Enc-CBC(Key, {ports}, {daddr, saddr});
+	 *                 = Enc(Key, saddr xor Enc(Key, daddr))
+	 */ 
+	
+	/* PT0 = daddr */
+	memcpy(tmp, daddr, random_state->blocksize);
+	/* IV = {ports,0,0,0} */
+	tmp[0] ^= (sport<<16) | dport;
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+	/* PT1 = saddr */
+	random_state->networkCipher->crt_cipher.cit_xor_block((u8*)tmp,
+		(const u8*)saddr);
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	seq = tmp[0];
+	seq += network_count;
+	seq += tv.tv_usec + tv.tv_sec*1000000;
+
+	return seq;
+}
+EXPORT_SYMBOL(secure_tcpv6_sequence_number);
+
+__u32 secure_ipv6_id(__u32 *daddr)
+{
+	__u32 tmp[4];
+	struct scatterlist sgtmp[1];
+
+	check_and_rekey(get_seconds());
+
+	memcpy(tmp, daddr, random_state->blocksize);
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	/* id = tmp[0], tmp = Enc(Key, daddr); */
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+EXPORT_SYMBOL(secure_ipv6_id);
+#endif
+
+
+__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
+				 __u16 sport, __u16 dport)
+{
+	struct timeval 	tv;
+	__u32		seq;
+	__u32 tmp[4];
+	struct scatterlist sgtmp[1];
+
+	/*
+	 * Pick a random secret every REKEY_INTERVAL seconds.
+	 */
+	do_gettimeofday(&tv);	/* We need the usecs below... */
+	check_and_rekey(tv.tv_sec);
+
+	/*
+	 *  Pick a unique starting offset for each TCP connection endpoints
+	 *  (saddr, daddr, sport, dport).
+	 *  Note that the words are placed into the starting vector, which is 
+	 *  then mixed with a partial MD4 over random data.
+	 */
+	/*
+	 * AES256 is 2.5 times faster then MD4 by openssl tests.
+	 * We can afford to encrypt 1 block
+	 *
+	 * seq = ct[0], ct = Enc(Key, {(sport<<16)|dport, daddr, saddr, 0})
+	 */ 
+	
+	tmp[0] = (sport<<16) | dport;
+	tmp[1] = daddr;
+	tmp[2] = saddr;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	seq = tmp[0];
+	seq += network_count;
+	/*
+	 *	As close as possible to RFC 793, which
+	 *	suggests using a 250 kHz clock.
+	 *	Further reading shows this assumes 2 Mb/s networks.
+	 *	For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
+	 *	That's funny, Linux has one built in!  Use it!
+	 *	(Networks are faster now - should this be increased?)
+	 */
+	seq += tv.tv_usec + tv.tv_sec*1000000;
+
+#if 0
+	printk("init_seq(%lx, %lx, %d, %d) = %d\n",
+	       saddr, daddr, sport, dport, seq);
+#endif
+	return seq;
+}
+
+EXPORT_SYMBOL(secure_tcp_sequence_number);
+
+/*  The code below is shamelessly stolen from secure_tcp_sequence_number().
+ *  All blames to Andrey V. Savochkin <saw@msu.ru>.
+ *  Changed by Jean-Luc Cooke <jlcooke@certainkey.com> to use AES & C.A.P.I.
+ */
+__u32 secure_ip_id(__u32 daddr)
+{
+	struct scatterlist sgtmp[1];
+	__u32 tmp[4];
+
+	check_and_rekey(get_seconds());
+
+	/*
+	 *  Pick a unique starting offset for each IP destination.
+	 *  id = ct[0], ct = Enc(Key, {daddr,0,0,0});
+	 */
+	tmp[0] = daddr;
+	tmp[1] = 0;
+	tmp[2] = 0;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+u32 secure_tcp_port_ephemeral(__u32 saddr, __u32 daddr, __u16 dport)
+{
+	struct scatterlist sgtmp[1];
+	__u32 tmp[4];
+
+	check_and_rekey(get_seconds());
+
+	/*
+	 *  Pick a unique starting offset for each ephemeral port search
+	 *  id = ct[0], ct = Enc(Key, {saddr,daddr,dport,0});
+	 */
+	memset(tmp, 0, sizeof(tmp));
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = dport;
+	tmp[3] = 0;
+	sgtmp[0].page = virt_to_page(tmp);
+	sgtmp[0].offset = offset_in_page(tmp);
+	sgtmp[0].length = random_state->blocksize;
+
+	crypto_cipher_encrypt(random_state->networkCipher, sgtmp, sgtmp,
+		random_state->blocksize);
+
+	return tmp[0];
+}
+
+#ifdef CONFIG_SYN_COOKIES
+/*
+ * Secure SYN cookie computation. This is the algorithm worked out by
+ * Dan Bernstein and Eric Schenk.
+ *
+ * For linux I implement the 1 minute counter by looking at the jiffies clock.
+ * The count is passed in as a parameter, so this code doesn't much care.
+ * 
+ * SYN cookie (and seq# & id#) Changed in 2004 by Jean-Luc Cooke
+ * <jlcooke@certainkey.com> to use the C.A.P.I. and AES256.
+ */
+
+#define COOKIEBITS 24	/* Upper bits store count */
+#define COOKIEMASK (((__u32)1 << COOKIEBITS) - 1)
+
+__u32 secure_tcp_syn_cookie(__u32 saddr, __u32 daddr, __u16 sport,
+		__u16 dport, __u32 sseq, __u32 count, __u32 data)
+{
+	struct scatterlist sg[1];
+	__u32   tmp[4];
+
+	/*
+	 * Compute the secure sequence number.
+	 *
+	 * Output is the 32bit tag of a CBC-MAC of
+	 * PT={count,0,0,0} with IV={addr,daddr,sport|dport,sseq}
+	 *   cookie = {<8bit count>,
+	 *             truncate_24bit(
+	 *               Encrypt(Sec, {saddr,daddr,sport|dport,sseq})
+	 *             )
+	 *            }
+	 *
+	 * DJB wrote (http://cr.yp.to/syncookies/archive) about how to do this
+	 * with hash algorithms.
+	 * - we can replace two SHA1s used in the previous kernel with 1 AES
+	 *   and make things 5x faster
+	 * - I'd like to propose we remove the use of two whittenings with a
+	 *   single operation since we were only using addition modulo 2^32 of
+	 *   all these values anyways.  Not to mention the hashs differ only in
+	 *   that the second processes more data... why drop the first hash?
+	 *   We did learn that addition is commutative and associative long ago.
+	 * - by replacing two SHA1s and addition modulo 2^32 with encryption of
+	 *   a 32bit value using CAPI we've made it 1,000,000,000 times easier
+	 *   to understand what is going on.
+	 */
+
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = (sport << 16) + dport;
+	tmp[3] = sseq;
+
+	sg[0].page = virt_to_page(tmp);
+	sg[0].offset = offset_in_page(tmp);
+	sg[0].length = random_state->blocksize;
+	if (!random_state->networkCipher_ready) {
+		check_and_rekey(get_seconds());
+	}
+	/* tmp[]/sg[0] = Enc(Sec, {saddr,daddr,sport|dport,sseq}) */
+	crypto_cipher_encrypt(random_state->networkCipher, sg, sg,
+		random_state->blocksize);
+
+	/* cookie = CTR encrypt of 8-bit-count and 24-bit-data */
+printk("random: secure_tcp_syn_cookie cook=%x", tmp[0] ^ ( (count << COOKIEBITS) | (data & COOKIEMASK) ) );
+	return tmp[0] ^ ( (count << COOKIEBITS) | (data & COOKIEMASK) );
+}
+
+/*
+ * This retrieves the small "data" value from the syncookie.
+ * If the syncookie is bad, the data returned will be out of
+ * range.  This must be checked by the caller.
+ *
+ * The count value used to generate the cookie must be within
+ * "maxdiff" if the current (passed-in) "count".  The return value
+ * is (__u32)-1 if this test fails.
+ */
+__u32 check_tcp_syn_cookie(__u32 cookie, __u32 saddr, __u32 daddr, __u16 sport,
+		__u16 dport, __u32 sseq, __u32 count, __u32 maxdiff)
+{
+	struct scatterlist sg[1];
+	__u32 tmp[4], thiscount, diff;
+
+printk("random: check_tcp_syn_cookie state=%p", random_state);
+	if (random_state == NULL  ||  !random_state->networkCipher_ready)
+		return (__u32)-1;       /* Well, duh! */
+
+	tmp[0] = saddr;
+	tmp[1] = daddr;
+	tmp[2] = (sport << 16) + dport;
+	tmp[3] = sseq;
+	sg[0].page = virt_to_page(tmp);
+	sg[0].offset = offset_in_page(tmp);
+	sg[0].length = random_state->blocksize;
+	crypto_cipher_encrypt(random_state->networkCipher, sg, sg,
+		random_state->blocksize);
+
+	/* CTR decrypt the cookie */
+	cookie ^= tmp[0];
+
+	/* top 8 bits are 'count' */
+	thiscount = cookie >> COOKIEBITS;
+
+	diff = count - thiscount;
+printk("random: check_tcp_syn_cookie diff=%x maxdiff=%x", diff, maxdiff);
+	if (diff >= maxdiff)
+		return (__u32)-1;
+
+	/* bottom 24 bits are 'data' */
+	return cookie & COOKIEMASK;
+}
+#endif
--- linux-2.6.11.6/drivers/char/Makefile	2005-03-25 22:28:37.000000000 -0500
+++ linux-2.6.11.6-fort/drivers/char/Makefile	2005-03-30 09:04:49.000000000 -0500
@@ -7,7 +7,13 @@
 #
 FONTMAPFILE = cp437.uni
 
-obj-y	 += mem.o random.o tty_io.o n_tty.o tty_ioctl.o
+obj-y	 += mem.o
+ifeq ($(CONFIG_CRYPTO_RANDOM_FORTUNA),y)
+  obj-y	 += random-fortuna.o
+else
+  obj-y	 += random.o
+endif
+obj-y	 += tty_io.o n_tty.o tty_ioctl.o
 
 obj-$(CONFIG_LEGACY_PTYS)	+= pty.o
 obj-$(CONFIG_UNIX98_PTYS)	+= pty.o
--- linux-2.6.11.6/include/linux/sysctl.h	2005-03-25 22:28:22.000000000 -0500
+++ linux-2.6.11.6-fort/include/linux/sysctl.h	2005-03-30 09:04:49.000000000 -0500
@@ -202,7 +202,9 @@
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
 	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_UUID=6,
+	RANDOM_DIGEST_ALGO=7,
+	RANDOM_CIPHER_ALGO=8
 };
 
 /* /proc/sys/kernel/pty */

Re: Fortuna

[Matt Mackall]

On Wed, Apr 13, 2005 at 07:43:37PM -0400, Jean-Luc Cooke wrote:
> Ahh.  Thanks Herbert.
> 
> Matt,
> 
> Any insight on how to test syn cookies and the other network stuff in
> random.c?  My patch is attached, but I havn't tested that part yet.

For starters, this is not against anything like a current random.c. A
great number of cleanups have been done.

Syncookies are perhaps best tested with printk of the cookie
ingredients in the generation and check steps.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[Jean-Luc Cooke]

On Wed, Apr 13, 2005 at 05:09:39PM -0700, Matt Mackall wrote:
> On Wed, Apr 13, 2005 at 07:43:37PM -0400, Jean-Luc Cooke wrote:
> > Ahh.  Thanks Herbert.
> > 
> > Matt,
> > 
> > Any insight on how to test syn cookies and the other network stuff in
> > random.c?  My patch is attached, but I havn't tested that part yet.
> 
> For starters, this is not against anything like a current random.c. A
> great number of cleanups have been done.

You caught me.  :)

Last I proposed Fortuna for /dev/random it nearly got me drawn and quarterd.
So I've left it as a kenrel config option, leaving the current random.c
alone.  I thought this was a way to make everyone happy.

JLC

Re: Fortuna

[Matt Mackall]

On Wed, Apr 13, 2005 at 08:26:47PM -0400, Jean-Luc Cooke wrote:
> On Wed, Apr 13, 2005 at 05:09:39PM -0700, Matt Mackall wrote:
> > On Wed, Apr 13, 2005 at 07:43:37PM -0400, Jean-Luc Cooke wrote:
> > > Ahh.  Thanks Herbert.
> > > 
> > > Matt,
> > > 
> > > Any insight on how to test syn cookies and the other network stuff in
> > > random.c?  My patch is attached, but I havn't tested that part yet.
> > 
> > For starters, this is not against anything like a current random.c. A
> > great number of cleanups have been done.
> 
> You caught me.  :)
> 
> Last I proposed Fortuna for /dev/random it nearly got me drawn and quarterd.

It still might. Ted and I are as yet unconvince that the Fortuna
approach is superior. While it may have some good properties, it lacks
some that random.c has, particularly robustness in the face of failure
of crypto primitives.

> So I've left it as a kenrel config option, leaving the current random.c
> alone.  I thought this was a way to make everyone happy.

Duplicated code rarely does that.

At any rate, you ought to review the changes (there've been 40+
patches recently). There are a number of bug fixes in there and quite
a bit of cleanup. Syncookies in particular no longer live in random.c.

-- 
Mathematics is the supreme nostalgia of our time.

Re: Fortuna

[David Wagner]

Matt Mackall  wrote:
>While it may have some good properties, it lacks
>some that random.c has, particularly robustness in the face of failure
>of crypto primitives.

It's probably not a big deal, because I'm not worried about the
failure of standard crypto primitives, but--

Do you know of any analysis to back up the claim that /dev/random
will be robust in the failure of crypto primitives?  I have never
seen anyone try to do such an analysis, but maybe you know of something
that I don't.