Projects/PRNG Cleanup

This is an early stage project for MIT Kerberos. It is being fleshed out by its proponents. Feel free to help flesh out the details of this project. After the project is ready, it will be presented for review and approval.

Overview

This project is intended to clean up some of the conceptual errors in the PRNG framework and make it interface more cleanly to the rest of the code. The specific proposed changes are:

• Correct (probably rewrite) the Fortuna PRNG implementation and make it the default.
• Make the Fortuna implementation immediately reseed the generator on inputs likely to contain an interesting amount of entropy (OSRAND and TRUSTEDPARTY). Use the pool logic for other entropy inputs.
• Make the Fortuna implementation fail out if it cannot gather OS entropy and does not receive an OSRAND or TRUSTEDPARTY entropy input.
• Eliminate the Yarrow PRNG implementation.
• Add a PRNG implementation which just gathers OS entropy.
• Eliminate current calls to contribute entropy except for:
  • krb5_generate_subkey_extended: parent key
  • krb5_generate_seq_number: parent key
  • KDC: master key
  • KDC: interval between packets
  • KDC: OS entropy once per hour
  • kdb5_util, kdb5_ldap_util: master key

Background

Kerberos uses entropy from the operating system when possible. However, it also contains logic to attempt to produce random results in the cases where:

• The operating system has no PRNG.
• The operating system's PRNG produces guessable values.
• The operating system's PRNG produces a sequence of values which can be used to determine its internal state.

The countermeasures we currently implement are:

1. When generating subkeys, we contribute the parent key as PRNG entropy. Similarly, when operating on a KDC database, we supply the master key as PRNG entropy.
2. We produce values using a cryptographic generator. A cryptographic generator, once seeded with input not known to the attacker, produces an indefinite sequence of random values which, without an infeasible amount of computational power, cannot be used to determine the internal state of the generator.
3. We implement an accumulator which allows a stream of unreliable entropy events to be pooled together and used to reseed the generator. The goal is that even if the internal state of the PRNG is known to an attacker at some point in time, the attacker will eventually be unable to recover the state after one of the reseed operations.

These countermeasures are not completely reliable at resolving the problem cases. If the operating system cannot produce non-guessable initial entropy and we have no parent key to contribute, we cannot generate non-guessable values. The accumulator is only helpful for long-running callers such as the KDC which can generate a stream of unreliable entropy events.

The generator and accumulator we use are from Yarrow, a creation of Schneier and others. As of krb5 1.9, we also offer a compile-time choice of a "Fortuna-like" implementation of the generator and accumulator, based loosely on more recent work of Schneier and others.

Problem Analysis

The Yarrow PRNG implementation requires callers to estimate the entropy of unreliable-entropy events. This requirement has been recognized by the creators of Yarrow as unrealistic and a flaw in the Yarrow architecture.

The Fortuna-like PRNG implementation was written without direct access to Schneier's description of Fortuna. As a result, it implements something completely different from the Fortuna accumulator. Its generator logic also has subtle differences from the Fortuna generator. These differences carry significant risk of compromising the PRNG's design goals.

When entropy from a parent key or master key is contributed to the PRNG, it is not guaranteed to trigger a reseed. If the PRNG was previously in a guessable state, we will generate a guessable subkey unnecessarily.

The Yarrow implementation is complicated and delicately integrated with the rest of the crypto library, making it an obstacle to simplifying the organization of the library.

Implementation Details

The corrected Fortuna PRNG will attempt gather entropy from the OS at initialization time. If this fails, and no TRUSTEDPARTY or OSRAND entropy is contributed, subsequent calls to obtain random values will fail.

The OS-only PRNG implementation will always use /dev/urandom. Currently we make some effort to seed the PRNG with values from /dev/random when creating a Kerberos database or starting kadmind; a note will be made to only select the OS-only PRNG when /dev/urandom is not manifestly stronger than /dev/random.

Relevant Mailing List Threads

http://mailman.mit.edu/pipermail/krbdev/2010-September/009561.html