Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Assume that I have two sources of entropy (say, a hardware RNG and a CSPRNG) and that the two sources are independent (do not know anything about the internal state of the other RNG). Can I mix them by XORing blocks safely? If one of the two has been compromised/subverted, is there any way it can reduce the total entropy of the other source?

The answer here seems to imply this is possible, but does not specifically address the case of one of the two being subverted.

I'm aware of entropy mixing via hashes, but I'm wondering about something with less overhead.

(In case anyone's wondering, I'm not actually implementing an entropy pool, just settling a debate at work.)

share|improve this question
    
If one had been subverted to be a copy of the other, then xor would be a poor choice, whilst hashing would remain ok. Although that is quite contrived (if attacker can route one RNG, they are likely to be able to view it too) –  Neil Slater Jun 11 at 5:32
    
That's what I meant by independent.. That they might be able to have predictable output, but not output that depends on the other source. –  David Jun 11 at 5:38
    
Should be fine. Think of one-time-pad. For an attacker that doesn't know the key, it is still perfectly secure no matter what the plaintext was. –  mikeazo Jun 11 at 13:57
add comment

1 Answer 1

up vote 8 down vote accepted

If one source remains uncompromised plus statistically random on all bits, and both sources remain independent, then a xor of both sources together can also be considered uncompromised plus statistically random for all bits.


Basic proof:

Label the the results two RNGs $X$ and $Y$, consider bits $X_n$, $Y_n$ and $Z_n = X_n \oplus Y_n$

Assume each value of $X$ remains uncompromised, such that $p(X_n=1) = 0.5$, and that each value of $Y$ is compromised so that $p(Y_n=1) = w$, the following holds assuming $X$ and $Y$ are independent:

$p(Z_n=1) = p(X_n=1) * p(Y_n=0) + p(X_n=0) * p(Y_n=1)$

$ = 0.5 * (1.0-w) + 0.5 * w$

$ = 0.5$

In other words, each bit of $Z$ retains the same probabilities and qualities of $X$, if $X$ is from a good RNG, then $Y$ can then be anything at all (provided it is independent of X). This holds even if $p(Y_n=1)$ is not independent of $p(Y_m=1)$, because whatever distribution you provide for $Y$, it just cancels out as above.

Knowing the exact value of $Y$ is just a special case of the above where $p(Y_n=1)$ is either 0 or 1 for each $n$. It doesn't grant any knowledge about $Z$, because each bit of $Z$ remains independent from each other bit of $Z$ and an attacker still only knows $p(Z_n=1) = 0.5$


Using a secure hash-based mixing method might allow you to relax the requirement for independence between the RNGs.

Entropy mixing with secure hashes can also be used to flatten distributions from sources which are not flat e.g. event timing data. You generally don't have that problem when the sources you are considering are well-written RNGs in the first place.

share|improve this answer
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.