krb5 and PRNGs

[ghudson@MIT.EDU]

I want to take a step back and look at what we're doing with PRNG code
in MIT krb5.  I'm particularly interested in input from people with
more history with the project than I have.

Currently, we assume that Unix-like environments have a /dev/urandom
which can be used as much as we want and a /dev/random which must be
used sparingly to avoid exhausting system entropy (we use it only when
starting kadmind or creating a new KDB).  We treat /dev/urandom as our
primary "strong" source of entropy--that is, we are not in the
business of trying to generate significant amounts of entropy from
what we can observe as a library operating within a user-space
process.  If values drawn from /dev/urandom have no significant
entropy from the attacker's point of view, then we have no security.

We don't use /dev/urandom directly to generate keys.  I assume this is
out of concern that /dev/urandom might not be cryptographically
strong--that is, an attacker might be able to look at some of its
output, recover the internal state of the kernel's PRNG, and know all
of the subsequent outputs.  If /dev/urandom can be attacked in this
way, then krb5's security in a multi-user environment is irreparably
damaged, but we can still salvage security in single-user
environments.

Instead, we use /dev/urandom values as entropy sources for Yarrow.
Yarrow appears to have been designed for operating system kernels, and
can be viewed at two layers:

  * A generator function which produces an arbitrary amount of
    pseudo-random data based on a seed.  This function is a slight
    gloss on using a block cipher in counter mode.  The generator
    function ensures that it is difficult to recover the internal
    state of the PRNG from its outputs.

  * Logic for reseeding the generator based on unpredictable entropy
    events with varying entropy estimates.

Fortuna (an update to Yarrow, which we do not yet use but are
considering) is similar in having these two layers.  It uses a
slightly different generator function, and a different reseeding logic
which does not require entropy estimates.

The thing is, we are not an operating system kernel, and we don't have
a set of drivers asynchronously producing entropy events.  The PRNG
code could reach out to /dev/urandom and generate entropy whenever it
wants, but since we have a deterministic API, it doesn't do so.
Instead, "entropy events" are caused by caller invocations of
krb5_c_random_add_entropy() or krb5_c_random_os_entropy().  The latter
is called whenever a krb5 context is initialized (although the PRNG
state is process-global) and once per hour by the KDC.

So I do not understand the value of using either Yarrow's or Fortuna's
reseeding logic.  Using the Yarrow or Fortuna generator to work around
a cryptographically weak /dev/urandom makes some sense to me, but we
could do that with much less PRNG code than we have today.