Can adding bad entropy to good entropy, make a system insecure?

Question

For example,

If I needed to generate a random number. I use a good source of entropy to generate r.

Then I add values a, b and c whom are generated from bad entropy such that new entropy = r + a + b + c

How would the overall entropy look like?

The plus sign means to add and not concatenate. I believe that if we concatenated, then this would lead to an overall bad entropy because if we assume that each a,b,c,r each contribute 64 bits to 256 bits of entropy. We would in reality only have 64 bits of good entropy from r. This is my intuition with concatenation.

Answer 1

If you have a variable with maximal entropy, and you combine it with an independent variable with less entropy using Xor or modular addition you will still have maximal entropy.

If you have two independent variables with low entropy and you combine them in the above fashion the result will be a variable with more entropy than either the original ones

If however the variables are correlated all bets are off. Even combining two maximal entropy variables may result in 0 entropy (constant variable ) when adding/xoring them.

Answer 2

I assume that addition is mod 2^64.In this case the variable new entropy = r + a+ b+c would have the same entropy as as r (we are assuming that r has already maximum entropy).

If instead the addition is over the integer and a,b,c, are bounded to be 64bits, you would get a random variable with at most 67 bits that it is not uniformly distributed, and without any assumption on a,b,c, it could have just 64 bits of entropy. (a,b,c could be correlated, so that the sum is always equal to 452441, for example.)

A better approach would be to use a flexible two source extractor where the two sources are a|b|c (the concatenation) and r, or for practical reason just hash the concatenation (a|b|c|r) with a SHA256.

Answer 3

How would the overall entropy look like?

If you sum algebraically, entropy $H$ is related to the variance of any variable $X$, and so for $N$ independent variables:-

$$ H \sim \operatorname{Var}\left( \sum^N X_i \right) = \sum^N \operatorname{Var}\left( X_i \right) $$

Which means the total entropy is approximately related to the sum of the individual variances, as $ \sim \operatorname{Var}(a) + \operatorname{Var}(b) + \operatorname{Var}(c) + \operatorname{Var}(r) $. If you're assuming that $a,b,c$ have low entropy (say couple/three bits), it won't make much of a difference compared to the 64 bits of $r$.

Whilst not using the same sample spaces as your example, the following is what happens to the entropy distribution when several dice are summed:-

Your input distributions will be uniform as the dice, just with three small and one much larger. The resultant convolution will be a slightly non uniform distribution. But it won't distort as far as the normal approximation in the diagram of four dice.

It makes it difficult to calculate the resultant summed entropy this way as there is no simple closed form probability equation. Consequently we tend not to do it this way.

It's also very inefficient way to convolve entropy inputs, and not done as we aim for a maximal entropy uniform distribution. Crucially you can see that the per die increase in min. entropy $(-\log_2{(p_{\text{max}})})$ is dropping logarithmically in relation to the number of dice, and $H_{min}$ is the conservative estimate of $H$ we use for system security. So you'd face diminishing returns in $H_{min}(r)$ as you add more variables to $r$.

We actually would instead concatenate the variables as $ a||b||c||r $, ignore fixed bits and preserve their entropies. The final entropy would be the summation of the individual entropies. Just remember that this is entropy, not a uniform distribution or any sort of cryptographic key. Those require further work such as randomness extraction with hash functions or perhaps a key derivation function.