Re: [PROPOSAL/PATCH 2] Fortuna PRNG in /dev/random

[Jean-Luc Cooke]

Oops!  my bad.  Attached here along with a few other changes.  I'm running a
change log now at the top of the random-fortuna.c file.

Being 100% faithful to their designs would require such constructions as each
event source would hold its own pool index pointer, right now event collection
is separated from event mixing for API and performance reasons.
 


Trying to find solace and more articulate advise I've sat down with Practical
Crypto again reviewed the state compromise-extension attack recovery section.

If copyright laws smile on me, I'll quote section 10.5.2 starting at chapter
6 on page 170 of the soft-cover print.

 -- start quote --
The speed at which the system recovers from a compromised state depends on
the rate at which entropy (with respect to the attacker) flaws into the
pools.  If we assume that this is a fixed rate R, then after t seconds we
have in total R*t bits of entropy.  Each pool receives about R*t/32
bits in this time period.  The attacker can no longer keep track of the state
if the generator is reseeded with a pool with more then 128 bits of entropy
in it.  There are two cases.  If pool P_0 collects 128 bits of entropy before
the next reseed operation, then we have recovered from the compromise.  How
fast this happens depends on how large we let P_0 grow before we reseed.  The
second case is when P_0 is reseeding too fast, due to random events unknown to
(or generated by) the attacker.  Let t be the time between reseeds.  Then pool
P_i collects 2^i*R*t/32 bits of entropy between reseeds, and is used in a
reseed every 2^i*t seconds.  The recovery from the compromise happens the
first time we reseed with pool P_i where 128 <= 2^i*R*t < 256.  (The upper
bound derives from the fact that otherwise pool P_{i-1} would contain 128
bits of entropy between reseeds.)  This inequality gives us

  2^i * R * t
  ----------- < 256
       32

and thus

             8192
   2^i * t < ----
               R

In other words, the time between recovery points (2^i*t) is bounded by the
time it takes to collect 2^13 bits of entropy (8192 / R).  The number 2^13
seems a bit large, but it can be explained in the following way.  We need at
least 2^7 bits to recover from a compromise.  We might be unlucky if the
system reseeds just before we have collected 2^7 bits in a particular pool,
and then we have to use the next pool, which collect close to 2^8 bits before
the reseed.  Finally, we divide our data over 32 pools, which accounts for
another factor of 2^5.

This is a very good result.  The solution is within a factor of 64 of an
ideal solution (it needs at most 64 times as much randomness as an ideal
solution would need).  The is a constant factor and it ensures that we can
never do terribly badly, and will always recover eventually.  Furthermore, we
do not need to know how much entropy out events have or how much the attacker
knows.  That is the real advantage Fortuna has over Yarrow.  The
impossible-to-construct entropy estimators are gone for good.  Everything is
fully automatic; if there is a good flow of random data, the PRNG will
recover quickly.  If there is only a trickle of random data, it takes a long
time to recover.
 -- end quote --

Hopefully the above quote from the book will be interpreted as free
advertising and not theft.



On Wed, Sep 29, 2004 at 05:53:15PM -0400, Theodore Ts'o wrote:
> On Wed, Sep 29, 2004 at 04:27:07PM -0400, Jean-Luc Cooke wrote:
> > 
> > Here's patch v2.1.2 that waits at least 0.1 sec before reseeding for
> > non-blocking reads to alleviate Ted's concern wrt waiting for reseeds.
> 
> You didn't include the patch, and in any case, you'll probably want to
> probably want to do it for both blocking as well as non-blocking
> reads.  And keep in mind, it's not *my* concerns, but it's Neil
> Ferguson and Bruce Schneier's concerns.  After all, if you're going to
> call it Fortuna, you might as well be faithful to their design,
> especially since if you don't, you're leaving it to be utterly
> vulnerable to this state extension attack they are so worried about.
> 
> 						- Ted
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/