5.9 pisces.yarrow - Yarrow random number generator

5.9 `pisces.yarrow` - Yarrow random number generator

This module implements a Yarrow-160 cryptographic pseudorandom number generator for Unix. It is based on a design described in the following paper: John Kelsey, Bruce Schneier, and Niels Ferguson: ``Yarrow-160: Notes on the Design and Analysis of the Yarrow Cryptographic Pseudorandom Number Generator,'' http://www.counterpane.com/yarrow.html. The documentation here assumes you are familiar with the design described there.

Counterpane also provides an implementation, Yarrow 0.8.71, for Windows developed by Ari Benbasat. The implementation appears to diverge from the design document in numerous respects, e.g. entropy estimation and generating pseudorandom ouputs from the pool values.

A note on the implementation: The Yarrow design paper uses 3DES in counter mode. Counter mode is fairly unusual. It is not implemented in the Python Crypto Toolkit or OpenSSL; it only merits a one-paragraph mention in Schneier's book Applied Cryptography. The implementation here uses 3DES in ECB mode with a counter. The counter is encrypted with the key, then XORed with the plaintext.

EntroypSource ()

EntropySource instances track the amount of entropy available from a single source. It is used internally by EntropyPool.

The design document proposes three different methods for Entropy Estimation: It estimates the entropy using three different methods and returns the lowest result.

This implementation, following Benbasat, uses two estimates: one provided by the programming who supplies the input and another generator from zlib.

addInput (buf, estbits): Update the estimate to account for the entropy in buf with estbits bits of entropy. Both the actual data and the user-supplied estimare are necessary to update the internal entropy estimate.

getEntropy (): Return the minimum estimated entropy currently available.

reset (): Reset the estimates to zero.

EntroypPool (threshold, count)

The EntropyPool collects samples from entropy sources. The design document described an Entropy Accumulator, which collects samples from entropy sources and puts them into two pools. This class implements the pools.

A pool contains the running hash of all inputs fed into it since the accumulate method was called. The accumulate method is called by the Yarrow class during reseed operations.

The pool keeps estimates about the entropy of each individual source, although the digest is over all sources. Each souce must be initialized by calling addSouce and passing the source's name. The instance variable sources maps from names to EntropySource instances.

The constructor takes two arguments, the threshold and a count. A pool is ready to be used when at least count of its sources have an entropy greater than or equal to threshold. The isReady method returns true when this condition is met.

EntropyPool instances are thread safe, because a typical use is to have multiple threads adding entropy to the pool.

addSource (name): Prepare pool for accepting input from source named source.

addInput (source, buf, estbits): Update hash of pool source with buf containing estbits estimated entropy.
If the source was not initialized via addSource, this method will raise a KeyError.

isReady (): Returns true if there is enough entropy in the pool. Enough is defined by the threshold and count arguments to the constructor.

accumulate (): Return the current pool digest and reset the pool.

Yarrow ()

The Yarrow class generates random data and managed the fast and slow entropy pools for seeding the PRNG. These functions are described as three seperate entities in the design document: ``generating pseudorandom outputs,'' ``reseed mechanism,'' and ``reseed control.''

The main API for this class is three methods: getOutput, addSource, and addInput.

A client may also call forceReseed and allowReseed to cause a reseed to occur. However, reseed control is implemented internally and should occur regularly even if the client does not call these methods.

The reseed methods take an optional ticks argument that affects how long the reseed will take. The class implements a default number, which should be sufficient, but the user can override it.

The Yarrow class is not threadsafe.

getOuput (num): Return num bytes of random data.

addSource (sourceName): Intialize a new entropy source named sourceName.

addInput (source, input, estbits): Add input string to source pool, estimating estbits of entropy.

forceReseed ([ticks]): Force a reseed.

allowReseed ([ticks]): Perform a reseed in enough entropy is available.

reseed ([ticks]): Use current entropy to generate new seed.

ThreadedYarrow (): This subclass of Yarrow adds locking on addInput, getOutput and allowReseed calls. This locking is sufficient to make the class thread-safe.

EntropyGatherer (jobs, yarrow)

An EntropyGatherer runs a collection of system utilities periodically. Each instance is a threading.Thread designed to be run via a start method. One instance should be created for each collection of utilities that are run at the same period.

The arguments are: jobs, a description of the system utilities to run, and yarrow, a Yarrow instance to feed the data to.

pad64 (s): Returns a copy s padded to 64 bits.

hash (x): Returns the SHA digest of x.

hash_ex (m, k): Extend input m to k bytes using SHA digests.