[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Re-keying Issues Document

It's true that our key-generation algorithm must be computationally
secure, or else the forward secrecy will be compromised.  But that's
already a requirement -- if the key-generation algorithm is poor (or
poorly seeded), the entire system is at risk.  See e.g.
	http://www.ddj.com/ddj/1996/1996_01/wagner.htm
for an example of this failure mode.

And it's true that finding enough good entropy to really seed these
algorithms properly is a little tricky in kernel-mode.  But I think it's
not infeasible.  See
	http://www.cs.berkeley.edu/~daw/netscape-randomness.html
for a collection of links to help with this task.

And yes, it's also true that the use of a computationally-secure
key-generation algorithm means that we can't achieve information
theoretically secure perfect forward secrecy.  But that's ok; as long as
the key-generator is good, we should be able to achieve computationally-
secure forward secrecy; and we're not demanding information-theoretic
security in other aspects of the system -- we're not using a one-time
pad for encryption, for instance -- so computational security ought to
be good enough for key generation too.

I think a proper analysis of computationally-secure forward secrecy has
to take into account the threat model and the reason why you're seeking
forward secrecy.  As I see it, there are two goals: one, if a session
key is compromised by cryptanalysis, we want to recover; and two, if an
intruder manages to break into our IPSEC machine and steal machine
state, we want to limit the damage.

The former is pretty easy to ensure.  Just take a key-generation
algorithm which is computationally secure (they're not too hard to
build), and seed it well.

The latter is somewhat trickier to achieve when you're using a
key-generator to ``stretch'' limited amounts of true randomness, so let
me concentrate on that for the remainder of the note.

The issue is that if the intruder breaks into your machine, he can steal
the internal state of the key-generator; you don't want him to be able
to deduce the value of all your old keys from that.  So the
key-generator should periodically hash its internal state with a one-way
function (technically, with a function whose output doesn't leak any
information on the input).  That's not so hard.

Second, once the intruder loses access (for whatever reason), you don't
want him to be able to ``follow along'' and predict the value of new
keys -- that would also be catastrophic.  This issue is quite a bit
subtler.  The obvious fix is to periodically update the state of your
key-generator by hashing in some new entropy samples from whatever
source you think appropriate.  The idea is that eventually you'll
accumulate enough new entropy so that the attacker won't be able to
follow along any more.

But there's a subtle problem with this fix.  The same PRNG used to
generate keys will probably also be used to generate other quantities --
such as IVs, nonces, and so on -- which are publicly disclosed.  Now
imagine that you grab an entropy sample, generate an IV, generate a
session key, and repeat.  If each entropy sample has only 20 bits of
unpredictable entropy, which is not unlikely, then an attacker can
follow along forever: he tries all 2^{20} possible values for the first
sample, checks his guess against the first IV, recovers the first
session key, and then repeats.  The cost of recovering N session keys is
then 2^{20} * N work.  (In some cases, this can be reduced to just
2^{10} * N work, by playing some games.)  Thus, the system never
recovers, even after sampling thousands of bits of good entropy, despite
the fact that you'd think it ought to eventually recover somehow.

This attack is from some joint work on analysis of key-generators I've
done with John Kelsey, Bruce Schneier, and Chris Hall.  We called it a
``state compromise extension'' attack in our paper; I think it's pretty
general.  (See
	http://www.cs.berkeley.edu/~daw/prngs-fse98.ps
for the paper.)

Fortunately, the fix is pretty simple.  Instead of immediately mixing
every entropy sample into the internal state of the key-generator, use
some buffering.  Buffer the entropy samples until you're pretty sure
you've got at least 128 bits of good unpredictable entropy -- or wait
for a few hundred bits, just to be on the safe side, since estimating
entropy is hard -- and then stir the buffered entropy into the internal
state all at once.

I do highly recommend using this technique, or some variant of it, in
IPSEC key-generators to help reduce the risk of state compromise and to
help improve the security of IPSEC's forward secrecy guarantees.
Follow-Ups: References: