The "Tiny" random number infrastructure

Introduction

Tiny is divided into two parts, the Entropy Gateway (EG) and the Pseudo-Random Number Generator (PRNG). The PRNG is a slight modification of the PRNG used in Yarrow-160 (we use a MAC instead of a block cipher in counter mode, and make other minor changes). The entropy gateway is totally different than anything specified in the Yarrow paper, and is also completely different from the Yarrow-AES algorithm John and Pravir worked on while at Cigital (potential IP issues was one reason for this new algorithm; efficiency was the other).

The Tiny Entropy Gateway

Parameters

• N: maximum number of sources (1..)
• POOLSZ: Size of an entropy pool in bytes (128, 256, 512, 1024, 2048)
• UOL: Output length of UMAC algorithm in bytes (1-32)
• KEYSZ: Size of UMAC Key in bytes (16 or 32)
• BUFSZ: Size of output buffer in UMAC-output blocks. (1..)
• P/Q: Fraction of outputs that get mixed in with the UMAC key. (any)
• R: Number of sources we assume can be compromised by an attacker. (1..N-1)
• S: Paranoia constant (as a percent). (any)

Recommended values

• N: 10
• POOLSZ: 512
• UOL: 8
• KEYSZ: 16
• BUFSZ: 32
• P: 1
• Q: 10
• R: 1
• S: 10

Computed values

• THRESH is computed by taking FLOOR((UOL * S)/100) + UOL

Components of the Entropy Gateway

1. The "entropy pool". The entropy pool is a collection unit for raw data coming in from entropy sources. The pool consists of a buffer (the entropy buffer), a 128-bit counter, and an array of N entropy estimates. The entropy buffer is implemented as a set of parallel LSFRs (linear shift feedback registers).
2. The "slow pool". The slow pool is a set of data structures intended to provide cryptographic security as a fallback mechanism, in case entropy sources are compromised. The slow pool consists of a UMAC context, and a buffer of size KEYSZ (we call this the pre-key, as it will ultimately replace the internal UMAC key).
3. An output buffer. This is a buffer that contains "processed" entropy. External requests for entropy get serviced from this buffer.

The Entropy Pool

The counter and entropy estimates initialize to zeros. The entropy buffer initializes to all bits set (each byte is 0xff). When the entropy pool is flushed (see below), all elements of the entropy pool get set to the original state, except for the counter.

The entropy buffer is really 8 parallel LSFRs. Entropy sources mix their data into this pool. Bytes get mixed in using a primitive polynomial of the appropriate size over GF(2). We use polynomials taken from /dev/random, though the mixing code is different.

Here are primitive polynomials taken from /dev/random. Hopefully they are not too sparse:

• 2048 bytes: x^2048 + x^1638 + x^1231 + x^819 + x^411 + x + 1
• 1024 bytes: x^1024 + x^817 + x^615 + x^412 + x^204 + x + 1
• 512 bytes: x^512 + x^411 + x^308 + x^208 + x^104 + x + 1

Special note: The buffer size must be at least eight times (default is 16) the size of the output size (UOL), to avoid entropy loss when sources only provide entropy in lower order bits. (Optionally, we can do some sort of shifting, but it seems like more effort than it is worth). This is sufficient for Tiny, because we never expect the entire buffer to contain more than UOL bits of entropy.

The 2nd-6th terms of the polynomial are "taps", numbered 1 through 5. To mix in a byte of entropy, we take the byte, xor it with the 5 taps, then we rotate the pool left one byte, and replace the first byte of the pool with the result.

When entropy comes in from a source, the entropy counter for that source is incremented by the "hint" provided by the source (note that there is no need to count past THRESH for any one source, and doing so might result in overflow errors).

After entropy is added, the EG checks to see if the LSFR has enough entropy to output. The output rule is as follows:

Total the entropy collected from all sources, after subtracting out the top R contributors. If the number of bits is > THRESH, then an output occurs.

Outputs can go to the output buffer or to the slow pool. The rules for where to output are as follows:

1. If the slow pool has not reseeded (ie, the internal UMAC context has not been initialized), outputs go to the slow pool.
2. If the output buffer is full, outputs go to the slow pool.
3. The first (Q-P) out of every Q outputs go to the output buffer. The remaining P go to the slow pool. If any outputs went to the slow pool because the output buffer was filled, then any counters get reset. That is, the next Q-P outputs should go to the output buffer, if possible.

1. Increment the UMAC nonce by one.
2. UMAC the contents of the entropy buffer.

1. Place the results in the output buffer.
2. Re-initialize the entropy buffer (to 0xff) and the entropy estimates.

1. XOR the output into the first UOL bytes of the slow buffer.
2. Rotate the slow buffer left UOL bytes.
3. Re-initialize the entropy buffer (to 0xff) and the entropy estimates.
4. Re-seed the slow pool, if necessary.

The Slow Pool

At startup, the slow pool counter is set to zero. The step is set to zero. The UMAC is initialized with a key of all zeros, and a nonce of the current time as reported by gettimeofday(), truncating off the most significant bits if necessary. The buffer is initialized to all zeros.

Slow Pool Reseeds

When the entropy pool has output to every byte of the pre-key once and only once, that is called a "pass" on the pre-key.

If the slow pool has never reseeded before, it reseeds after a single pass on the pre-key.

Otherwise, the slow pool takes twice as many passes on the pre-key to reseed as it did the last time it reseeded, with a maximum of 32.

When the slow pool reseeds, output KEYLEN blocks of output as follows:

1. Increment the nonce by one.
2. UMAC UOL bytes of the pre-key.

Then, take the resulting bytes, and overwrite the UMAC key. Finally, zero out the pre-key.

The Output Buffer

Outputs are serviced from the output buffer. Outputs should be given in byte-quantities. Pending requests that cannot be fufilled should be queued until output is available. If multiple requests are pending, they should be served in round-robin style.

Saving and restoring state

The Tiny EG should be able to save and restore its state. The UMAC context only should be stored. On restore, the requirement for entropy pool outputs to go to the slow pool is ignored. The slow pool reseeds after a single pass on the pre-key.

EG Rationalle

The EG tries to output pure entropy. We try to collect at least as many bits of entropy as we wish to output, and usually collect more, because of a conservative assumption that an attacker might be able to compromise one or more entropy sources. If sufficient entropy exists, the EG should produce "good" outputs. We mearly compress (lossily) and whiten the entropy pool using UMAC.

When sufficient entropy is not available due to compromise, UMAC provides cryptographic security as a fallback, assuming that the system has ever mixed sufficient entropy into the slow pool.

We clear the entropy pool every time to ensure that there are no correlations between successive outputs.

We use UMAC because it is fast and has good provable properties. The only assumption we need to make (assuming our design doesn't suck) is the cryptographic strength of AES.

The Tiny PRNG

Tiny uses the original Yarrow-160 PRNG, except that:

1. We use UMAC instead of a block cipher. The nonce is the counter.
2. We need data to mac... that is a 128-bit value, passed in as part of the seed.

The generator gate frequency is a system parameter (for self-rekeying). The default frequency is every 10 outputs, as in Yarrow-160. The self-rekey operation is about the same as in Yarrow. The key is overwritten with blocks of generator output, along with the counter and the counter step. The step parameter is always modified to be odd after a rekey.

The seed should be raw entropy, and big enough to set the counter, the UMAC key and the step parameter. If the step parameter is not odd, it is modified to be so.

"Real" reseeds (ones where we add new entropy to the PRNG) can happen by periodic polling, or by push. In both cases, there should be a parameter, minimum time between reseeds. We recommend 60 seconds as the default parameter.