Mathematically, the definition of entropy, H(X), for a variable X is
where P(X=x) is the probability that the variable X takes on the value x.
This document describes in detail the latest deterministic random number generator (RNG) algorithm used in our CryptoSys range of products: CryptoSys API (as of version 4.0, Sept 2007), the CryptoSys PKI Toolkit (as of version 3.0, Mar 2007) and CryptoSys KeyExchange (as of version 1.0, Feb 2007).
The RNG has been implemented to conform to NIST Special Publication 800-90 Recommendation for Random Number Generation Using Deterministic Random Bit Generators [SP80090], first published June 2006, revised March 2007. Entropy is accumulated in "Fortuna" pools as described in Ferguson and Schneier, Practical Cryptography, chapter 10, "Generating Randomness" [FERG03].
This supersedes the old RNG implementation which complied with ANSI X9.31 Appendix A.2.4 [AX931] (which replaced X9.17 Appendix C). We assert that the NIST method is at least as secure as the ANSI X9.31-compliant method under any circumstances.
This document describes the implementation for the Windows® operating system. The Linux implementation is similar but does not use thread-safe techniques and the personalisation string uses fewer parameters.
This information is published for peer review and comment. Please contact us with your comments.
RNG ≡ RBGIn particular, the terms random number generator (RNG) and random bit generator (RBG) are interchangeable. The output from a RNG or RBG is a sequence of zero and one bits. In our case, the output is always in 8-bit blocks (bytes, octets).
We use two basic references for the background theory: NIST Special Publication 800-90 Recommendation for Random Number Generation Using Deterministic Random Bit Generators [SP80090] and Ferguson and Schneier, Practical Cryptography, chapter 10, "Generating Randomness" [FERG03]. Ferguson and Schneier is much easier to read and we have drawn on several sections of their book here (because they can write about the subject much better than we can).
Some typical pseudo-code for a PRNG generator might be:
INPUT: (Key, Seed) OUTPUT: random_data, (Key', Seed') random_data = F(Key, Seed) Key' = F(Key, Seed+1) Seed' = F(Key', Seed) return random_datawhere F is a cryptographic function. All the generators are essentially some variant of this.
Backtracking resistance is provided by ensuring that the DRBG generator algorithm is a one-way function. This is easy: all the DRBG mechanisms in NIST SP800-90 provide backtracking resistance.
Prediction resistance depends on the Reseed process; that is, the ability to effectively reseed after a compromise but before the next request. This is more difficult.
- The attacker attempts to reconstruct the internal state from the output. This is a classic cryptographic attack, and rather easy to counter using cryptographic techniques.
- The attacker is at some point able to acquire the internal state. If no further entropy is added, then the attacker can follow all the outputs and all the updates of the internal state. This means that if the the PRNG is ever attacked successfully, then it can never recover to a secure state.
To solve: mix in entropy from truly-random events into the internal state.
- If the entropy added is only in small amounts - as it most likely will be - the attacker makes frequent requests for random data from the PRNG. As long as the total amount of entropy added between two such requests is limited to say, 30 bits, then the attacker can simply try all possibilities for the random inputs and recover the new state after the mixing.
The best defence against this particular attack is to pool the incoming events that contain entropy. You collect entropy until you have enough to mix into the internal state without the attacker being able to guess the pooled data. How much is enough? You want to have 128 bits of entropy. But here is the real problem: making any kind of estimate of the amount of entropy is extremely difficult, if not impossible. It depends heavily on how much the attacker knows or can know, but that information is not available to the developers during the design phase.
To reseed the generator, we need to pool events in a pool large enough that the attacker can no longer enumerate the possible values for the events in the pool. Fortuna solves the problem of how many events to collect in a pool before using it to reseed the generator.
There are 32 pools: P0,P1,...,P31. Each pool conceptually contains a string of bytes of unbounded length but in practice contains the partly-computed hash of the string as it is assembled in the pool.
Each source distributes its random events over the pools in a cyclical fashion. This ensures that the entropy from each source is distributed more or less evenly over the pools. Each random event is appended to the string in the pool in question.
We reseed the generator every time pool P0 is long enough. Reseeds are numbered 1,2,3,.... Depending on the reseed number r, one or more pools are included in the reseed. Pool Pi is included if 2i is a divisor of r. Thus P0 is used in every reseed, P1 every other reseed, P2 every fourth reseed, etc. After a pool is used in a reseed, it is reset to the empty string.
Irrespective of how many fake random events the attacker generates, or how many of the events he knows, as long as there is at least one source of random events he can't predict, there will always be a pool that collects enough entropy to defeat him.
To prevent the attacker injecting so many events that even if pool P31 does not contain enough randomness between reseeds to recover from a compromise, we limit the speed of the reseeds. A reseed will only be performed if the previous reseed was more than 100 milliseconds ago, so it will take more than 13 years before P32 would have been used, had it existed.
The measure of randomness is called entropy. Entropy measures how uncertain you are about the value. You can think of entropy as the average number of bits you would need to specify the value if you could use an ideal compression algorithm. The more you know about a value, the smaller its entropy is.Mathematically, the definition of entropy, H(X), for a variable X is
where P(X=x) is the probability that the variable X takes on the value x.
For example, if you have a value consisting of a sequence of 16 bytes that are completely random; that is, each of the sequence of 128 bits (16 bytes x 8 bits/byte = 128 bits) has been chosen in an unbiased manner, then the 16-byte value has 128 bits of entropy. You would say that the security strength of the value is 128 bits, or the amount of work required to break the security is 2128 operations. This is computationally infeasable.
But if you know that each byte has been chosen from the set of, say, the two values {0x00, 0xFF}, then you only have 16 bits of entropy. Each byte in the sequence has entropy of only 1 bit, so the sequence has 16 bits. Thus the work required to break the security has been reduced to 216 operations: a mere 65,000 guesses.
At the far extreme, if an attacker knows exactly what these 16 bytes are, then you have zero bits of entropy.
So the amount of entropy can be anything between zero and the actual size of the value in bits depending on how much the attacker knows. It's relative to an observer and his knowledge prior to an observation.
From FIPS PUB 140-2 Section 4.9.2 Self-Tests - Conditional Tests [FIPS140]:ANNEX C: APPROVED RANDOM NUMBER GENERATORS
Annex C provides a list of the FIPS Approved random number generators applicable to FIPS PUB 140-2
(snip)...
6. National Institute of Standards and Technology, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, Special Publication 800-90, June 2006.
Continuous random number generator test.
If a cryptographic module employs Approved or non-Approved RNGs in an Approved mode of operation, the module shall perform the following continuous random number generator test on each RNG that tests for failure to a constant value.1. If each call to a RNG produces blocks of n bits (where n > 15), the first n-bit block generated after power-up, initialization, or reset shall not be used, but shall be saved for comparison with the next n-bit block to be generated. Each subsequent generation of an n-bit block shall be compared with the previously generated block. The test shall fail if any two compared n-bit blocks are equal.
HMAC_DRBG mechanism
as specified in Section 10.1.2 of NIST SP800-90 with SHA-1 as the underlying hash function.
Highest supported security strength = 128 Output block length (outlen) = 160 bits Maximum number of bits per request = 2^19 bits (i.e. 65536 bytes) Reseed interval = 2^30 (< 2^48 max for HMAC_DRBG) or as dictated by the Fortuna algorithm Maximum length of personalization string = 160 bits Maximum length of entropy input = 5120 bits (32 pools x 160 bits) Maximum additional input length = 2^34 bits (2^31 bytes)
Each thread has its own Generator in Thread Local Storage. Each process has one Accumulator accessed by all Generators and protected by a Critical Section when accessed. The accumulator has 32 "Fortuna" accumulation pools with the minimum pool size before a reseed set to 32 bytes.
The "personalization string" used on instantiation in each thread is derived by hashing the current time, process ID, thread ID, user name and computer name, and so is almost certain to be different each time. The instantiation nonce is a 32-bit value derived from the current time which is incremented on the instantiation of any new Generator in a different thread.
The random events polled by the accumulator include the system time, the clock count, the memory status, the position and class name of each window, the free disk space, and other system parameters. Every event is time-stamped to the accuracy of the system clock, which means that, in the worst case, we have a cumulative hash of the times of every event polled since power up.
In the absolute worst case, if no seed file is used and an attacker can call the
GenerateRandomData function before any entropy has been generated by the system,
the output is effectively a "strong" hash of the current time and
personalization string with good backtracking resistance.
This is at least equivalent to an X9.31-compliant generator.
We do not make available to the consumer either a reseed_required_flag
or a prediction_resistance_request.
This is by design to prevent a clash with the Fortuna accumulation system.
The Fortuna algorithm will reseed every time pool P0 is long enough (in our case, when its length is 32 bytes or more) AND the time-since-last-reseed is greater than 100 milliseconds. This is not directly under the consumer's control, although he can force it eventually by repeatedly calling the library functions known to trigger entropy accumulation.
The NIST DRBG mechanism reseeds on either (a) first use; or (b) at the end of the seed life. The seed life of the DRBG mechanism is deliberately set high to reduce the risk of an attacker forcing a reseed by repeatedly requesting random data.
If the DRBG mechanism requires a reseed, then it requests entropy from the Fortuna pools, which is provided unconditionally.
In pseudo-code:
INPUT: nbits, previous_block
OUTPUT: random_data, previous_block'
if (previous_block != Null)
{
random_data = GenerateRandomData(nbits)
if (nbits < 64)
tocompare = random_data || 0^(64 - nbits)
else
tocompare = LeftMostBits(random_data, 64)
if (tocompare == previous_block)
return "catastrophic error"
}
previous_block' = GenerateRandomData(64)
return random_data
A strict reading of FIPS 140-2 would seem to require a check of every successive 64-bit block generated
by the DRBG_Generate function where the requested number of bits is greater than 64.
We assert that this pointless unless the HMAC-SHA-1 function is corrupted.
Furthermore, and far more serious, storing every generated block to compare with the next would expose a huge
security hole.
We chose the HMAC_DRBG mechanism with SHA-1 because:
HMAC_DRBG is preferred to Hash_DRBG because it is more secure.
There are known problems with
Hash_DRBG when the DRBG is instantiated with insufficient entropy for the requested
security strength.
But HMAC outputs look random even given knowledge and control over the inputs when an attacker doesn't know the key used.
Ref: [SP80090] p119-120. (In other words, you won't be able to tell if we get it wrong.)
RNG_Generate but the system decides to call that function in another thread. In that case, the
generator in the new thread will be initialized again without the extra entropy from the seed file. It will only have the
basic nonce and personalisation string plus a small amount of entropy from the pools that may have been collected
in the interim. How can you tell this has happened? You can't.
rand() function. Here is the source code.
We know nobody ever reads this far :-)
#include <stdlib.h>
#include <time.h>
void rng_bytes(unsigned char *buf, int nbytes)
{
static unsigned seed;
int i;
if (seed == 0)
{
seed = (unsigned)time(NULL);
srand(seed);
}
for (i = 0; i < nbytes; i++)
buf[i] = rand() & 0xFF;
}
If you really want the full source code, please just ask nicely and provide a reason why you want it.
Comments? Disagree? Found a mistake? Please let us know.
This page last updated: 22 July 2008
