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:

• Make PRNG implementations responsible for gathering OS entropy when desired using a helper function.
• 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 TRUSTED). 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 TRUSTED entropy input.
• Eliminate the Yarrow PRNG implementation.
• Add a PRNG implementation which uses only OS entropy.
• Eliminate current calls to add external 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 a pool system 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 pool logic is only useful for long-running callers such as the KDC which can generate a stream of unreliable entropy events.

The generator and pool system 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 pools, 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 by someone without access to Schneier's description of Fortuna. As a result, it implements something completely different from the Fortuna algorithm which is unlikely to be of benefit.

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.