krb5 and PRNGs

[Greg Hudson]

On Tue, 2010-09-21 at 19:10 -0400, Ken Raeburn wrote:
> As best I recall, when the Yarrow support was originally
> done, /dev/random and especially /dev/urandom were relatively new and
> not always available everywhere, so something would've been needed
> anyways on systems not supplying them, and it would have to use other
> sources as best it could.  We do use /dev/urandom to seed Yarrow, but
> we also include other sources.

Okay, that changes my perspective a bit, and means I need to analyze the
security of krb5 without /dev/urandom more carefully when considering
changes.  (That evaluation also covers the case where /dev/urandom
contains no useful entropy for some reason.)

We currently input the following non-trivial sources of non-OS entropy:

  * The parent key, when generating subkeys or sequence numbers
  * The master key, when performing some tasks on the KDC
  * The time between requests received by the KDC

When attacking a PRNG, your job is to keep track of its internal state
across every reseed.  If too much entropy (more than your computational
capacity) goes into the PRNG on any reseed, you're generally sunk, since
the entropy of the current key is preserved across reseeds.  On the
other hand, if reseeds happen frequently but with only small chunks of
entropy, you can brute-force the internal state across each reseed, if
you're able to see any of the output between each reseed and the next.

Therefore, the job of the defender is to reseed with enough entropy to
exceed the attacker's computational capacity.  This creates a bit of
tension in the case where we can't get OS entropy:

* If we're a client or application server program and the PRNG receives
a cryptographic key as entropy, we probably want to reseed with it
immediately, because it's the only good entropy we're going to get, and
if we don't use it right away, we're going to generate a subkey or
sequence number with only weak entropy.  (Of course, even generating a
key with the parent key as seed could have security implications, since
it means that the client isn't necessarily contributing randomness to an
exchange when it's supposed to, and is instead computing relatively
predictable derivatives of keys chosen by the KDC.  I'm not going to
analyze that issue carefully at this time.)

* On the other hand, if we're the KDC and the PRNG receives packet
timings, we want to pool those together so that at least some of our
reseeds contain enough entropy to thwart an attacker.  This is where
Fortuna's reseeding logic makes the most sense, since request times best
match Fortuna's design model of a relatively steady stream of events
with unknown (but likely non-zero) entropy.

I'm not quite sure what my conclusion is yet.  Possibilities for the
PRNG reseeding logic include:

1. Reseed the generator every time the caller provides entropy
2. Yarrow logic (using entropy estimates)
3. Fortuna logic
4. (1) if the data source is KRB5_C_RANDSOURCE_TRUSTEDPARTY, (2) or (3)
otherwise

(1) works well for the case where we have OS entropy, or in clients
without OS entropy where one of the caller-provided seeds is a secret
key which we ought to use immediately.  (3) is best for a KDC with no
available OS entropy, but fails miserably in the client case.  I'm
concerned that the current state, (2), isn't good for either case, and
is also the most complex.