Why do we not combine random number generators?

Question

There are many applications where a pseudo random number generator is used. So people implement one that they think is great only to find later that it's flawed. Something like this happened with the Javascript random number generator recently. RandU much earlier too. There are also issues of inappropriate initial seeding for something like the Twister.

I cannot find examples of anyone combining two or more families of generators with the usual xor operator. If there is sufficient computer power to run things like java.SecureRandom or Twister implementations, why do people not combine them? ISAAC xor XORShift xor RandU should be a fairly good example, and where you can see the weakness of a single generator being mitigated by the others. It should also help with the distribution of numbers into higher dimensions as the intrinsic algorithms are totally different. Is there some fundamental principle that they shouldn't be combined?

If you were to build a true random number generator, people would probably advise that you combine two or more sources of entropy. Is my example different?

I'm excluding the common example of several linear feedback shift registers working together as they're from the same family.

Answer 1

IIRC (and this is from memory), the 1955 Rand bestseller A Million Random Digits did something like this. Before computers were cheap, people picked random numbers out of this book.

The authors generated random bits with electronic noise, but that turned out to be biassed (it's hard to make a flipflop spent exactly equal times on the flip and the flop). However, combining bits made the distribution much more uniform.

Answer 2

Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently. However, it will be slower and it probably won't solve the most pressing problems that people have.

In practice, if you have a requirement for a very high-quality PRNG, you use a well-vetted cryptographic-strength PRNG and you seed it with true entropy. If you do this, your most likely failure mode is not a problem with the PRNG algorithm itself; the most likely failure mode is lack of adequate entropy (or maybe implementation errors). Xor-ing multiple PRNGs doesn't help with this failure mode. So, if you want a very high-quality PRNG, there's probably little point in xor-ing them.

Alternatively, if you want a statistical PRNG that's good enough for simulation purposes, typically the #1 concern is either speed (generate pseudorandom numbers really fast) or simplicity (don't want to spend much development time on researching or implementing it). Xor-ing slows down the PRNG and makes it more complex, so it doesn't address the primary needs in that context, either.

As long as you exhibit reasonable care and competence, standard PRNGs are more than good enough, so there's really no reason why we need anything fancier (no need for xor-ing). If you don't have even minimal levels of care or competence, you're probably not going to choose something complex like xor-ing, and the best way to improve things is to focus on more care and competence in the selection of the PRNG rather than on xor-ing.

Bottom line: Basically, the xor trick doesn't solve the problems people usually actually have when using PRNGs.

Answer 3

In fact, something of a breakthrough has just been announced by doing precisely this.

University of Texas computer science professor David Zuckerman and PhD student Eshan Chattopadhyay found that a "high-quality" random number could be generated by combining two "low-quality" random sources.

Here's their paper: Explicit Two-Source Extractors and Resilient Functions

Answer 4

Suppose that $X_1,\ldots,X_n$ is a pseudorandom binary sequence. That is, each $X_i$ is a random variable supported on $\{0,1\}$, and the variables $X_1,\ldots,X_n$ are not necessarily independent. We can think of this sequence being generated in the following way: first we sample a uniformly random key $K$, and then use some function $f(K)$ to generate the pseudorandom sequence.

How do we measure how good the pseudorandom sequence $X_1,\ldots,X_n$ is? While it is possible to measure how good a particular realization is (say using Kolmogorov complexity), here I will concentrate on measures which depend on the entire distribution of the random variable $(X_1,\ldots,X_n)$. One such example is entropy, but we will only require two properties of our measure $L$: (a larger $L(\cdot)$ means a more random sequence)

• If $y_1,\ldots,y_n$ is a deterministic sequence (i.e., a fixed sequence) then $L(X_1 \oplus y_1, \ldots, X_n \oplus y_n) = L(X_1,\ldots,X_n)$.

• If $\vec{X^0},\vec{X^1}$ are two independent pseudorandom sequences, $T \in \{0,1\}$ is an independent random bit, and $\vec{Z} = \vec{X^T}$, then $L(\vec{Z}) \geq \min(\vec{X^0},\vec{X^1})$.

The first property means that the measure is invariant under flipping the $i$th bit. The second property means that if we mix two distributions $\vec{X},\vec{Y}$, then the result is at least as good as the worse one.

Any reasonable randomness measure will satisfy the first property. The second property is satisfied by most popular measures such as entropy $H$ and min-entropy $H_\infty$.

We can now state and prove a theorem showing that XORing two pseudorandom sequences is always a good idea.

Theorem. Let $\vec{X},\vec{Y}$ be two independent pseudorandom sequences of the same length, and let $L$ be an admissible randomness measure (one satisfying the two conditions above). Then $$ L(\vec{X} \oplus \vec{Y}) \geq \max(L(X),L(Y)). $$

Proof. Suppose $L(X) \geq L(Y)$. Then $X \oplus Y$ is a mixture of the distributions $X \oplus y$, mixed according to the distribution of $Y$. Since $L(X \oplus y) = L(X)$ and a mixture is at least as good as the worst distribution being mixed, we obtain $L(X \oplus Y) \geq L(X)$. $~\square$

What this theorem means is that if you XOR two pseudorandom sequences generated using two independent keys, the result is always at least as good as the better sequence being XORed, with respect to any admissible randomness measure.

In practice, in order to use two independent keys, we probably expand one key to two keys in a pseudorandom fashion. The two keys are then not independent. However, if we use an "expensive" way to expand the one key into two keys, we expect the resulting two keys to "look" independent, and so for the theorem to hold "morally". In theoretical cryptography there are ways of making this statement precise.

---

Should we, then, XOR two pseudorandom number generators? If we are not restricted by speed, then that's certainly a good idea. But in practice we have a speed limit. We can then ask the following question. Suppose that we are given two PRNGs, each with a parameter $T$ that controls the running time (and so the strength) of the generator. For example, $T$ could be the length of an LFSR, or the number of rounds. Suppose we use one PRNG with parameter $T_1$, the other with parameter $T_2$, and XOR the result. We can assume that $T_1 + T_2 = t$, so that the total running time is constant. What is the best choice of $T_1,T_2$? Here there is a tradeoff which is hard to answer in general. It may be that the setting $(t/2,t/2)$ is much worse than either $(t,0)$ or $(0,t)$.

The best advice here is to stick to a popular PRNG which is considered strong. If you can spare more time for generating your sequence, XOR several copies, using independent keys (or keys generated by expanding a single key using an expensive PRNG).

Answer 5

I'll give this a shot, since I'm sufficiently disturbed by the advice given in some of the other answers.

Let $\vec{X},\vec{Y}$ be infinite bit sequences generated by two RNGs (not necessarily PRNGs which are deterministic once initial state is known), and we're considering the possibility of using the sequence $\vec{X} \oplus \vec{Y}$ with the hope of improving behavior in some sense. There are lots of different ways in which $\vec{X} \oplus \vec{Y}$ could be considered better or worse compared to each of $\vec{X}$ and $\vec{Y}$; here are a small handful that I believe are meaningful, useful, and consistent with normal usage of the words "better" and "worse":

• (0) Probability of true randomness of the sequence increases or decreases
• (1) Probability of observable non-randomness increases or decreases (with respect to some observer applying some given amount of scrutiny, presumably)
• (2) Severity/obviousness of observable non-randomness increases or decreases.

First let's think about (0), which is the only one of the three that has any hope of being made precise. Notice that if, in fact, either of the two input RNGs really is truly random, unbiased, and independent of the other, then the XOR result will be truly random and unbiased as well. With that in mind, consider the case when you believe $\vec{X},\vec{Y}$ to be truly random unbiased isolated bit streams, but you're not completely sure. If $\varepsilon_X,\varepsilon_Y$ are the respective probabilities that you're wrong about each of them, then the probability that $\vec{X} \oplus \vec{Y}$ is not-truly-random is then $\leq \varepsilon_X \varepsilon_Y \lt min\{\varepsilon_X,\varepsilon_Y\}$, in fact much less since $\varepsilon_X,\varepsilon_Y$ are assumed very close to 0 ("you believe them to be truly random"). And in fact it's even better than that, when we also take into account the possibility of $\vec{X},\vec{Y}$ being truly independent even when neither is truly random: $$ \begin{eqnarray*} Pr(\vec{X} \oplus \vec{Y} \mathrm{\ not\ truly\ random}) \leq \min\{&Pr(\vec{X} \mathrm{\ not\ truly\ random}), \\ &Pr(\vec{Y} \mathrm{\ not\ truly\ random}), \\ &Pr(\vec{X},\vec{Y} \mathrm{\ dependent})\}. \end{eqnarray*} $$ Therefore we can conclude that in sense (0), XOR can't hurt, and could potentially help a lot.

However, (0) isn't interesting for PRNGs, since in the case of PRNGs none of the sequences in question have any chance of being truly random.

Therefore for this question, which is in fact about PRNGs, we must be talking about something like (1) or (2). Since those are in terms of properties and quantities like "observable", "severe", "obvious", "apparent", we're now talking about Kolmogorov complexity, and I'm not going to try to make that precise. But I will go so far as to make the hopefully uncontroversial assertion that, by such a measure, "01100110..." (period=4) is worse than "01010101..." (period=2) which is worse than "00000000..." (constant).

Now, one might guess that (1) and (2) will follow the same trend as (0), and that therefore the conclusion "XOR can't hurt" might still hold. However, note the significant possibility that neither $\vec{X}$ nor $\vec{Y}$ was observably non-random, but that correlations between them cause $\vec{X} \oplus \vec{Y}$ to be observably non-random. The most severe case of this, of course, is when $\vec{X} = \vec{Y}$ (or $\vec{X} = \mathrm{not}(\vec{Y})$), in which case $\vec{X} \oplus \vec{Y}$ is constant, the worst of all possible outcomes; in general, it's easy to see that, regardless of how good $\vec{X}$ and $\vec{Y}$ are, $\vec{X}$ and $\vec{Y}$ need to be "close" to independent in order for their xor to be not-observably-nonrandom. In fact, being not-observably-dependent can reasonably be defined as $\vec{X} \oplus \vec{Y}$ being not-observably-nonrandom.

Such surprise dependence turns out to be a really big problem.

---

An example of what goes wrong

The question states "I'm excluding the common example of several linear feedback shift registers working together as they're from the same family". But I'm going to exclude that exclusion for the time being, in order to give a very simple clear real-life example of the kind of thing that can go wrong with XORing.

My example will be an old implementation of rand() that was on some version of Unix circa 1983. IIRC, this implementation of the rand() function had the following properties:

• the value of each call to rand() was 15 pseudo-random bits, that is, an integer in range [0, 32767).
• successive return values alternated even-odd-even-odd; that is, the least-significant-bit alternated 0-1-0-1...
• the next-to-least-significant bit had period 4, the next after that had period 8, ... so the highest-order bit had period $2^{15}$.
• therefore the sequence of 15-bit return values of rand() was periodic with period $2^{15}$.

I've been unable to locate the original source code, but I'm guessing from piecing together a couple of posts from in https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A that it did precisely the following (C code), which agrees with my memory of the properties above:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

As one might imagine, trying to use this rand() in various ways led to an assortment of disappointments.

For example, at one point I tried simulating a sequence of random coin flips by repeatedly taking:

rand() & 1

i.e. the least significant bit. The result was simple alternation heads-tails-heads-tails. That was hard to believe at first (must be a bug in my program!), but after I convinced myself it was true, I tried using the next-least-significant bit instead. That's not much better, as noted earlier-- that bit is periodic with period 4. Continuing to explore successively higher bits revealed the pattern I noted earlier: that is, each next higher-order bit had twice the period of the previous, so in this respect the highest-order bit was the most useful of all of them. Note however that there was no black-and-white threshold "bit $i$ is useful, bit $i-1$ is not useful" here; all we can really say is the numbered bit positions had varying degrees of usefulness/uselessness.

I also tried things like scrambling the results further, or XORing together values returned from multiple calls to rand(). XORing pairs of successive rand() values was a disaster, of course-- it resulted in all odd numbers! For my purposes (namely producing an "apparently random" sequence of coin flips), the constant-parity result of the XOR was even worse than the alternating even-odd behavior of the original.

A slight variation puts this into the original framework: that is, let $\vec{X}$ be the sequence of 15-bit values returned by rand() with a given seed $s_X$, and $\vec{Y}$ the sequence from a different seed $s_Y$. Again, $\vec{X} \oplus \vec{Y}$ will be a sequence of either all-even or all-odd numbers, which is worse than the original alternating even/odd behavior.

In other words, this is an example where XOR made things worse in the sense of (1) and (2), by any reasonable interpretation. It's worse in several other ways as well:

• (3) The XORed least-significant-bit is obviously biased, i.e. has unequal frequencies of 0's and 1's, unlike any numbered bit position in either of the inputs which are all unbiased.
• (4) In fact, for every bit position, there are pairs of seeds for which that bit position is biased in the XOR result, and for every pair of seeds, there are (at least 5) bit positions that are biased in the XOR result.
• (5) The period of the entire sequence of 15-bit values in the XOR result is either 1 or $2^{14}$, compared to $2^{15}$ for the originals.

None of (3),(4),(5) is obvious, but they are all easily verifiable.

---

Finally, let's consider re-introducing the prohibition of PRNGs from the same family. The problem here, I think, is that it's never really clear whether two PRNGs are "from the same family", until/unless someone starts using the XOR and notices (or an attacker notices) things got worse in the sense of (1) and (2), i.e. until non-random patterns in the output cross the threshold from not-noticed to noticed/embarrassing/disastrous, and at that point it's too late.

I'm alarmed by other answers here which give unqualified advice "XOR can't hurt" on the basis of theoretical measures which appear to me to do a poor job of modelling what most people consider to be "good" and "bad" about PRNGs in real life. That advice is contradicted by clear and blatant examples in which XOR makes things worse, such the rand() example given above. While it's conceivable that relatively "strong" PRNGs could consistently display the opposite behavior when XORed to that of the toy PRNG that was rand(), thereby making XOR a good idea for them, I've seen no evidence in that direction, theoretical or empirical, so it seems unreasonable to me to assume that happens.

Personally, having been bitten by surprise by XORing rand()s in my youth, and by countless other assorted surprise correlations throughout my life, I have little reason to think the outcome will be different if I try similar tactics again. That is why I, personally, would be very reluctant to XOR together multiple PRNGs unless very extensive analysis and vetting has been done to give me some confidence that it might be safe to do so for the particular RNGs in question. As a potential cure for when I have low confidence in one or more of the individual PRNGs, XORing them is unlikely to increase my confidence, so I'm unlikely to use it for such a purpose. I imagine the answer to your question is that this is a widely held sentiment.

Answer 6

DISCLAIMER: This answer is strictly about "We are we not doing it" and not "here's mathematical proof why it can or can't work". I don't claim that XOR introduces (or not) any cryptographic vulnerabilities. My point is only that experience shows us that even simplest schemes almost always introduce unforeseen consequences - and this is why we avoid them.

"Randomness" is just a tip of the iceberg when it comes to RNGs and PRNGs. There are other qualities that are important, eg uniformity.

Imagine a common dice which is quite good RNG on it's own. But now let's say you need a 1-5 range instead of 1-6. First thing that comes to mind is to simply erase the 6 face and replace it with an extra 1. The "randomness" remains (results are still truly random), however uniformity suffers greatly: now 1 is twice as likely as other outcomes.

Combining results from multiple RNGs is a similarly slippery slope. Eg. simple adding 2 dice throws completely wipes out any uniformity, as "7" is now 6 times more likely than "2" or "12". I agree that XOR looks better than addition at first glance, but in PRNGs nothing turns out as it looks at first glance.

This is why we tend to stick to known implementations - because someone spent loads of time and money into researching them and all the shortcomings are well known, understood and can be worked around. When you roll out your own, you potentially create vulnerabilities and you should put in similar effort to prove it. As the dice addition example shows, combining can be not much different from creating a new one from scratch.

Security is a chain, as strong as it's weakest component. A rule of thumb in security: whenever you combine 2 things, you usually get a sum of flaws, not a sum of strengths.