Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Suppose I'm suspicious that one or more (pseudo)-random number generators is cryptographically flawed, perhaps even deliberately backdoored. The RNGs in this case might be either PRNG algorithms, hardware random number generators, or some OS-provided primitive whose source might be either of these.

Can it ever be a bad thing to "salt" the RNG by using the xor of its output and some other RNG's output? The latter RNG might be of much lower quality but be unlikely to have been compromised by the same attacker -- for example, your hardware manufacturer might have compromised your hardware RNG but it's unlikely they've also steered a standards committee towards something like DUAL_EC_DRBG or bribed your OS provider into sneaking a bug into the cryptographic primitives.

Given the ongoing revalations about tampering with cryptographic standards committees, it seems like it would be prudent to start using the xor of multiple sources of randomness where at least one is "high quality" and at least one of the others has a very low "attack correlation" with it.

share|improve this question
    
If they are the same, there may be a slight bias in the output... –  Thomas Dec 21 '13 at 5:36
    
Right, I guess I should have said "two different RNG outputs". Obviously all-zeroes is not a very random bit-sequence :) –  eldentyrell Dec 21 '13 at 5:42
    
I am not a cryptography expert, but I want to say "no". XOR'ing two different same-length RNG outputs in the way you describe should be an effective way to hedge against one of the RNGs being biased or backdoored. –  Anorov Dec 21 '13 at 8:20
    
@Anorov: The key word in your comment is the word different. Judging whether one RNG is different enough from another one is harder than you might think, and XORing one RNG against another RNG that "look and feel" different might eliminate key entropy in the function and leave stuff that looks like entropy (like a sequence of primes mod some small number) but which is easy for an attacker to filter out. As a general rule, the answer is NO. Don't mess with cryptographic primitives unless you know what you're doing. –  Matt Dec 21 '13 at 18:35
    
@Matt Thanks! That does make sense. –  Anorov Dec 21 '13 at 22:02
show 1 more comment

1 Answer

There are details.

It rather hinges on the notion of how different, or, more adequately said, unrelated, your two RNG are. Let's see it with cryptographic eyes.

"Breaking" a RNG means observing n bits of output and then predicting the n+1 bit with a success probability substantially better than 1/2. A cryptographically secure RNG will in practice be a cryptographically secure PRNG which deterministically extends an internal state into as many bits as requested. We assume that the attacker knows the code (if only through reverse-engineering, or through paying beers to the guy who did the development); so a RNG output is exactly as unknown as the internal state of the RNG. The generic attack is exhaustive force on the state value, and this will be way too expensive if the space of possible state values is huge (e.g. more than 128 bits). The PRNG is cryptographically secure if the best known attack is the generic attack and that attack is indeed infeasible.

The formal setup is that the attacker is given the n bits of RNG output (let's call it r1), and challenged with predicting the n+1 bit. Suppose now that the "XOR of two RNG" turns out to be weak, meaning that given r1 XOR r2 (an n-bit sequence), the attacker can compute the n+1 bit of that sequence with probability higher than 1/2. Then the attacker just has... to produce r2 himself ! He builds the second RNG and runs it, with an output r2 that he perfectly knows, and XORs r2 with the given r1. He then applies the "attack on XOR" on the XOR result, and this yields the n+1 bit of r1 XOR r2. But the attacker knows the n+1 bit of r2 with 100% reliability (he generated it himself), so he can compute the n+1 bit of r1.

This argument shows that the XOR of two RNG cannot be weaker than either RNG alone... provided that the formal setup above is a correct description of the reality.

Indeed, the implicit assumption here is that the two RNG are sufficiently unrelated to each other that a formal attacker can, from the outside, build a proper emulation of the second RNG without knowing anything about the first. This is not a given. In practice, on a given machine, each good RNG will compute the initial value of its internal state from measures on "hardware events" (e.g. times of occurrences of hardware interrupts, with clock cycle accuracy); and both RNG run on the same hardware at the same time, so they see the same events... This implies that the formal description above does not match practical situations, and this invalidates the mathematical argument.

A contrived example will highlight my point. Suppose that RNG1 takes an initial seed S and uses it as key for AES in CTR mode (encryption with AES of successive values of a counter, starting with 0). This is a good, strong RNG, that cryptographers would not shun. Now define RNG2 also as AES in CTR mode, but such that each output bit is reversed (a bit of value 0 becomes a 1, and vice versa). Seed RNG2 with the same S. Taken alone, RNG2 is easily shown to be as cryptographically strong as RNG1. Cryptographers would readily bet a pint of Guinness on its strength. However, suppose that you XOR the outputs of RNG1 and RNG2 together; you then get... a long sequence of 1's, not a single 0. And that's very weak, because the n+1 bit can then be predicted to be a 1 with 100% reliability.

Yet RNG1 and RNG2 are, without any doubt, "different". They don't produce the same sequence of bits. This shows that "different output" is not the good notion here. What we want is unrelated RNG which is formalized as: an attacker can build an emulation of the second RNG without knowing anything about the internal state of the first. If both RNG are seeded from the same hardware, then the two RNG cannot be blindly assumed to be "unrelated".


Conclusion: the XOR of two RNG which run on the same hardware may, in practice, be weaker than either RNG alone. Whether the XOR is strong hinges on "how well" the cryptographic entrails of the PRNG can hide a common seeding. On the other hand, if you can arrange for unrelated seeding (you seed RNG1 with a seed S1, and then RNG2 with another seed S2, and you have good reasons to believe that S2 is unrelated to S1), then, in that case, the XOR of the two RNG cannot be weaker than either RNG alone.

I suggest that you do not indulge in such games. XORing two RNG together will give you some guarantee of security only if you know enough on how they are seeded that you could ascertain whether either is strong alone. If you know that one RNG is strong, then just use it. And if both RNG are weak, it is quite possible that the XOR of the two will be just as weak. The only sure thing about XORing two RNG together is that it increases computational cost and, more importantly, complexity. Complexity is bad for security.

share|improve this answer
    
Although two RNGs may both "run on the same hardware at the same time" that doesn't necessarily mean "they see the same events" and so set up correlated internal state. The entropy sources for the the RNGs may be entirely separate, as with a hardware RNG and a software entropy collection pool driving a PRNG. –  mgkrebbs Dec 22 '13 at 4:39
    
"and both RNG run on the same hardware at the same time, so they see the same events" -- of course not. The seed is absolutely never the entire machine state (an enormous space, including everything down to thermal noise, random dopant fluctuations, time-of-day, and electromigration of on-chip interconnect) -- it is a tiny subset of it, and different sources of randomness (for example software PRNG vs hardware thermal noise sampling) use wildly different tiny subsets. –  eldentyrell Dec 22 '13 at 9:43
    
"I suggest that you do not indulge in such games. XORing two RNG together will give you some guarantee of security only if you know enough on how they are seeded that you could ascertain whether either is strong alone." -- that's silly. If you don't know how an RNG is seeded you don't know if it is secure at all. –  eldentyrell Dec 22 '13 at 9:46
    
"Complexity is bad for security." -- sigh, the discussion has devolved to slogans. It's been fun, thanks, goodbye. –  eldentyrell Dec 22 '13 at 9:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.