Date: 15 Apr 2005 01:34:17 -0000
Message-ID: <20050415013417.3536.qmail@science.horizon.com>
From: linux@horizon.com
To: tytso@mit.edu
Subject: Re: Fortuna
Cc: jlcooke@certainkey.com, linux-kernel@vger.kernel.org, mpm@selenic.com
In-Reply-To: <20050414133336.GA16977@thunk.org>
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3872
Lines: 76

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