5. Mixing

What is the best overall strategy for obtaining unguessable random numbers in the absence of a strong, reliable hardware entropy source? It is to obtain input from a number of uncorrelated sources and to mix them with a strong mixing function. Such a function will preserve the entropy present in any of the sources, even if other quantities being combined happen to be fixed or easily guessable (low entropy). This approach may be advisable even with a good hardware source, as hardware can also fail. However, this should be weighed against a possible increase in the chance of overall failure due to added software complexity.

Once one has used good sources, such as some of those listed in Section 3, and mixed them as described in this section, one has a strong seed. This can then be used to produce large quantities of cryptographically strong material as described in Sections 6 and 7.

A strong mixing function is one that combines inputs and produces an output in which each output bit is a different complex non-linear function of all the input bits. On average, changing any input bit will change about half the output bits. But because the relationship is complex and non-linear, no particular output bit is guaranteed to change when any particular input bit is changed.

Consider the problem of converting a stream of bits that is skewed towards 0 or 1 or which has a somewhat predictable pattern to a shorter stream which is more random, as discussed in Section 4. This is simply another case where a strong mixing function is desired, to mix the input bits and produce a smaller number of output bits. The technique given in Section 4.1, using the parity of a number of bits, is simply the result of successively XORing them. This is examined as a trivial mixing function, immediately below. Use of stronger mixing functions to extract more of the randomness in a stream of skewed bits is examined in Section 5.2. See also [NASLUND].