Is it possible to make a more secure random number generator algorithm by XORing two or more less secure random number algorithms?

Question

Is it possible to make a more secure random number generator (e.g. for cryptologic purposes) by combining two or more less secure random number generator algorithms using XOR? Here is an example of what I am talking about:

// Create random numbers using weak algorithms
weak_random1 = WeakRandomAlgorithm1(seed1);
weak_random2 = WeakRandomAlgorithm2(seed2);
...

// Combine the random numbers into something stronger with XOR
stronger_random = weak_random1 XOR weak_random2 ...;

Answer 1

Since this doesn't seem to have been done yet, I am going to suggest an answer from a purely information theoretical point of view:

Let X, Y be two random variables in {0,1}^n. Let f(x,y) = x XOR y

Now, H(X,Y) = H(X)+H(Y|X) = H(Y)+H(X|Y), and since the information entropy is always nonnegative, we have H(X,Y)>=H(X) and H(X,Y)>=H(Y). So the join random variable (X,Y) has at least as much entropy as each individual random variable alone (equality occurs when one random variable perfectly depends on the other).

However, when you apply a function to a random variable, you reduce its entropy (no reduction if f is bijective, but this is certainly not true for our case), so we have H(f(X,Y)) < H(X,Y). A proof is here (question two).

Now, the question of OP is whether it is possible to make H(f(X,Y)) bigger than both H(X) and H(Y)? The answer is yes.

We write X as (X_1, ..., X_n) and Y as (Y_1, ..., Y_n). Now consider an extreme case where X_1 is constant and the rest of the bits are iid Bernoulli with p=0.5, and Y_1 is Bernoulli with p=0.5 and independent of X, while the other bits of Y are constant, then H(X) = n-1, H(Y) = 1, and H(f(X,Y)) = n, greater than both H(X) and H(Y).

This may not be a very interesting answer, but I think it does answer exactly what the OP asks.

EDIT:

I think a question the OP also has in mind is: is it possible to get a random number worse than both inputs when we do this? The answer is also yes. Consider X Bernoulli with p=0.5. And Y = NOT X. Before combining X and Y, we get H(X) = H(Y) = 1. But, X XOR Y == 1, so H(f(X,Y)) = 0 ! Oops ... So definitely don't just arbitrarily XOR two random numbers and expect to get a better one out of it.

EDIT 2:

An interesting discussion below brought up an important question: if X and Y are independent, is X XOR Y at least as random as both X and Y? Mark is absolutely right: the answer is yes.

Here is why:

First note that for any two random variables U and V, we have H(U)>=H(U|V). Equality holds when U and V are independent. Intuitively, this means that knowing something about V never hurts if we are trying to find out where U is. A formal proof reduces H(U)-H(U|V) to a KL divergence, which is always nonnegative.

Now, using the same notation as above, we have:

H(f(X,Y),X) = H(f(X,Y)|X)+H(X) = H(X|f(X,Y))+H(f(X,Y))

Since for any fixed x, we have H(f(x,Y)) = H(Y) (warning: not true for arbitrary f, but we have this since we defined f(x,y) to be x XOR y), we have H(f(X,Y)|X) = H(Y), and this gives us:

H(X)+H(Y) = H(X|f(X,Y))+H(f(X,Y))

But since H(X)>=H(X|f(X,Y)), we have:

H(Y)<=H(f(X,Y))

and by symmetry:

H(X)<=H(f(X,Y))

So that's the good news. The bad news is: testing for independence is probably not any easier than testing for randomness, if not more difficult. So it doesn't help us as much as it seems.

btw, how does everyone feel about asking SE to enable MathJax here so that we can do some serious math when needed?

Answer 2

I would not recommend combining random number generators in this way without having some underlying theory to support your case.

A simple way to illustrate the issues is to consider the behavior of low-end LCG algorithms, the popular "one-liner" schemes for generating random numbers.

These can be made to produce sequences that will pass certain statistical tests, but are not suitable for cryptographic applications. One known flaw in such generators is that the low-order bits are not random. For example, I have observed the low bit to oscillate between 0/1, and if you have two generators like this, and you XOR that low bit, and the generators are either in phase or out of phase, in either case the result of the XOR is rather predictable. It's not clear that you've improved the situation, but may have made it worse.

In Knuth's discussion of random number generation, he presents a humorous example of his attempts to construct a "super deluxe" generator.

Answer 3

This probably sounds like snark, but your solution only improves the situation if the two PRNGs are themselves chosen with sufficient randomness. Think of the reason that we consider a weak PRNG to be insecure: the result is statistically easy to guess some/all of, resulting in crypto and other operations that can be attacked by knowing part of the input data. If you go from one PRNG to two PRNGs, the attacker simply needs to know both PRNGs (or guess at them a few times) before they can reduce the potential strength of either (providing more random input data) into the weakness of the other (providing guessable input data). You can probably statistically improve the strength if you develop a PRNG-fed algorithm to choose which two (or, better yet, more) PRNGs at random, but it's only one factor away from the same weakness you started with. Better, probably, to look into a single more secure PRNG.

Answer 4

It is quite possible to create a stronger RNG using the suggested method, however it is also possible to create a weaker RNG, or one that does not improve. The end result depends on the properties of the weaker RNGs. Bit distribution and bias has just as much effect as the entropy level. Only careful analysis and knowledge of the entire scheme can tell if the strength improves, and if there are any potential issues can could compromise security.

Consider the following 2 weak RNGs, A and B.
A produces a bit stream where every odd bit is 0, and every even bit is cryptographically pseudorandom.
B produces a bit stream where every even bit is 0, and every odd bit is cryptographically pseudorandom.
The resultant XOR stream C has full cryptographic pseudorandomness, and is obviously stronger than the others, assuming independent seeds.

Now consider the following.
A is the bitstream output from Dual_EC_DRBG with NSA backdoored constants. The future outputs are predictable to an attacker who can observe the raw output of the bitstream.
B is the bitstream output from a cyclical MD5 hash on a random number, where the future output is the hash of the current output. The future outputs are predictable to an attacker who can observe the raw output of the bitstream.
The resultant XOR stream C is no longer predictable in the same way its components are. If an attacker is able to view the output of A or B on their own, C is no longer secure. Recovery of the seed for MD5 renders all future outputs immediately predictable, it must be large enough to prevent a brute force attack. The security of the stream is not better than the work effort to recover and verify the MD5 seed, or one the iterated hash values.

And finally.
A is the bitstream output from AES-CTR where the key is known to the NSA.
B is the bitstream output from AES-CTR where the key is known to the KGB.
The resultant XOR stream C is secure and unpredictable to either agency in the absence of collusion, which would make the output completely predictable.

These examples show that bitstreams with either weak entropy or predictable output can be made more secure by XORing them together, given the right properties and conditions. That does not necessarily make them completely secure.

Answer 5

Unless one is perfectly random, the end results is unclear. But if one were perfectly random, it would not be weak any more.

Edit: Unless you're sure the two are completely independent of each other, the benefits may be unclear.

Answer 6

The quick but overly vague answer to your original question is: Yes.

However, as most people have indicated: more secure != secure.

The purpose behind RNGs/PRNGs is to produce sufficient entropy to make it infeasible for an attacker to guess enough information to recover sufficient protected data.

Most sources of entropy are tested to determine whether they contain a sufficiently-mixed sequence of binary 0's and 1's such that simply "guessing" the next binary digit would be wrong approximately 50% of the time.

There are a couple of underlying elements that determine what "sufficiently-mixed" means.

First, it's the actual ratio of 1's to 0's in the output:

For instance, if the PRNG produced 110110101011101 then of the 15 bits we generated there were 10 of them set to 1, which is 66% of the entropy space. An attacker anticipating this kind of PRNG would be "better off" guessing that there are overall more 1's than 0's so for each bit they would favor setting it to 1 and 2/3 of the time they would be correct.

Conversely, a PRNG that produced 011011000100110 has eight 0's and 7 1's, which favors a 0-bit against a 1-bit at 53%:47%. Therefore, the attacker trying to defeat this system basically has little benefit to guessing a 0 over a 1 (...about 6% better odds).

Ideally, the close to 50:50 you get then the more protection for this first protection characteristic.

Seconds, is the randomness of the entropy such that a pattern cannot be discerned. For instance, if the PRNG output a perfect bit ratio for 0's to 1's of 50:50, but a pattern was observable, then there is reduced benefit of the system.

Consider the following 16-bit entropy: 1010101010101010 Well we sure pass the first requirement of having perfect bit-wise distribution of 50% 0's and 50% 1's; however, as you can trivially observe this is not secure. The same can be said for: 0011001100110011 or 0000000011111111.

There is a discernible pattern to the entropy output. Patterns are the bane of cryptographic operations because they leak information that reduces the overall effectiveness of the algorithm.

Now as a better example, lets look at the following 16-digit PRNG sequence: 0001011011000111 That output is much more "random looking" than the previous several examples in this section. Sure there are 2 sequences where there are three 0's in a row, but given these first 16 digits can you trivially guess when the 3rd sequence of three 0's would appear? It's not so easy.

So to bring this back to your original question: if you combined two weak entropy sources and afterwards ensured that their resultant XOR produced near-equal ratio of 0's to 1's AND there were no obvious patterns to the output then you COULD produce a stronger pseudo random number generator than either of the two would have been on their own.

Note: to work around some of the issues that others' have cited (such as predictable lower-bit state) you can shift one or both of weak_random1 and weak_random2 by a some number of bits before conducting the XOR. For instance, shift work_random1 by 3 bit positions and shift weak_random2 by 5 bit positions. Except for the fact that I disclosed the shift values (3 and 5, respectively), this would have "scrambled" the values that were more traditionally guessed/predictable to different locations in their respectively PRNG strings before the XOR operation making the predictability much more difficult.

All this said, I suggest using a better random source to begin with! While possible to achieve what you're asking, I know of few mathematicians that would say it is easy to accomplish and fewer that would consider it a secure solution.

Good luck :)

Answer 7

One potential problem I see is if the first random number generator generates the same or similar random numbers as the second one. If the numbers produced by the algorithms exactly match, the resulting number would be 0, which is not very secure. As long as the algorithms are sufficiently different, this pitfall probably should not happen. I welcome further discussion on this.