krb5 and PRNGs

[Nicolas Williams]

On Tue, Sep 21, 2010 at 04:34:42PM -0400, ghudson at MIT.EDU wrote:
> 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.

/dev/random and /dev/urandom have... suboptimal semantics.  What would
be nice is to get some guarantee as to the entropy density of output bit
strings.  Something like a /dev/random<N> which guarantees N bits of
minimum entropy for every read() of N bits or more.  /dev/random128
would be perfect for most uses.

(The file metaphor is not really well-suited for this purpose.  An
application might want an ETA for having N bits of entropy available.
An application might want N bits of output and know how many bits of
entropy are embodied in it.  Etcetera.  That can't be done with open(2)
and read(2).)

But /dev/random and /dev/urandom are what we have.  Their quality will
vary.  Solaris' /dev/random is, I believe, quite good, and supports HW
RNGs (if you have them).

> 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

No, that's not correct.  /dev/urandom should be a cryptographically
strong PRNG, preferably seeded with real entropy, and preferably used in
an entropy-pool manner (i.e., a fixed-sized state bit string has entropy
cryptographically added at various times, and entropy cryptographically
extracted at other times to re-seed the PRNG).  If this is not so on
some operating systems, well, gee, that's just too bad for users
thereof.

Given that, the issue is that an attacker might be able to discover the
internal state of /dev/urandom.  The only chance an attacker will have
to do this is to know or have knowledge about likely initial
/dev/urandom seeds used at boot time.  Overcoming that hurdle is
difficult for any would-be attacker of a reasonably well designed
system.  Their only alternative is harder: cryptanalyze /dev/urandom's
output.

IOW, this is the province of the OS developer.  The OS' should provide a
/dev/random and /dev/urandom with semantics such that they can be used
in MIT krb5 reasonably safely.  It'd be better to have a standard
interface that provides guarantees regarding entropy content, but you
can do without.

Note though that we must count on attackers obtaining some /dev/urandom
outputs.  For example, they may be able to observe IVs/confounders/
session keys, if they are authenticate peers and those items are
generated by reading from /dev/urandom.  Which is why /dev/urandom had
better be at least a PRNG seeded with some real entropy.

> way, then krb5's security in a multi-user environment is irreparably
> damaged, but we can still salvage security in single-user
> environments.

True, but I believe that would be a bug in /dev/urandom.

> Instead, we use /dev/urandom values as entropy sources for Yarrow.

If you don't trust /dev/urandom then using it to seed Yarrow isn't much
of an improvement.  Or did you mean that you use /dev/random to seed
Yarrow?

> [description of Yarrow and Fortuna elided]

Applications can only do so much to make up for limitations of the host
OS' entropy services.  I'd say: use /dev/random to seed Yarrow/Fortuna,
and be done.  Timeout reads from /dev/random, and if they timeout then
warn the user (ha! try doing that from within the krb5 GSS mech, not).

Nico
--