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

["Theodore Ts'o" <tytso@mit.edu>]

While addition of the entropy estimator helps protect the Fortuna
Random number generator against a state extension attack, /dev/urandom
is using the same entropy extraction routine as /dev/random, and so
Fortuna is still vulernable to state extension attacks.  This is
because a key aspect of the Fortuna design has been ignored in JLC's
implementation.  

This missing piece to assure that a rekey can only take place when
there has been sufficient entropy built up in the higher order pools
in order to assure a catastrophic rekey.  Otherwise, the attacker can
simply brute force a wide variety of entropy inputs from the hardware,
and see if any of them matches output from the /dev/urandom (from
which the attacker is continuously pulling output).  So in the
original design, the rekey from a higher order pool only takes place
after k*2^n seconds, where n is the order of the pool, and k is some
constant.  The idea is that after some period of time hopefully one of
the pools has built up at least 128 bits or so worth of entropy, and
so the catastrophic reseeding will prevent an attacker from trying all
possible inputs and determining the state of the pool.  (Neils
recommends that k be at least a tenth of a second; see pages 38-40 of
http://th.informatik.uni-mannheim.de/people/lucks/papers/Ferguson/Fortuna.pdf).

Unfortunately, Fortuna will call random_reseed() after every single
read from /dev/urandom.  This is not time-limited at all, so as long
as the attacker can call /dev/urandom fast enough, it can continue to
monitor the various higher-level pools.  This can be fixed easily by
simply changing the rekey function so that it only attempts a reseed
after some period of time has gone by.

There is of course the question of whether a state extension attack is
realistic.  After all, most attacks where the attacker as sufficient
privileges to obtain the complete state of the RNG is also one where
the attacker also has enough privileges to install a rootkit, or
compromise the kernel by loading a hostile loadable kernel module,
etc.  Also, there is the question about whether an attacker could read
sufficient amounts of to keep track of the the contents of the pool,
and whether the attacker can either do the brute-forcing on the local
machine, or send the large amounts of information read from
/dev/urandom to an outside machine, without using enough CPU time that
it would be noticed by a system administrator ---- but then again, the
Crypto academics that are worried about things like state extension
attacks aren't worried about practical niceties.  But then again, if
we decide that state extension attacks aren't practically possible, or
otherwise not worthy of concern, or if JLC's Fortuna implementation is
vulnerable to state extension attacks, there's no reason to use JLC's
implementation in the first place.

						- Ted