2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suggest that you read about the design of the Linux CSPRNG named "/dev/random". The source code is well explained in English: github.com/torvalds/linux/blob/master/drivers/char/random.c $\endgroup$ – A. Hersean May 3 at 12:07
  • $\begingroup$ In your example, 'a', 'b' and 'c' do not increase the overall entropy, however you mix the contents (addition, concatenation, XORing). The size of the output is not equal to the entropy of its content. $\endgroup$ – A. Hersean May 3 at 12:09
  • 1
    $\begingroup$ @A.Hersean: Something like Fortuna might be a better starting point. $\endgroup$ – Ilmari Karonen May 3 at 15:06
  • $\begingroup$ @IlmariKaronen Indeed! Thanks for the tip. The paper describing Fortuna is far more detailed than the Linux source code: schneier.com/academic/paperfiles/fortuna.pdf $\endgroup$ – A. Hersean May 3 at 15:20
  • $\begingroup$ What is bad entropy exactly? You can think of entropy as the element gold (Au). Therefore all entropy/gold is good. It's just that sometimes it is found like gold ore, of varying purity or concentration Or in low quantities. So do you really mean a low amount of entropy, rather than "bad"? $\endgroup$ – Paul Uszak May 3 at 20:41
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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:-

dice

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.

$\endgroup$
  • 2
    $\begingroup$ No. Entropy is not dependent on variance or vice versa. Entropy depends only on the individual probability of each possible outcome. Variance depends on the value of each outcome and its likelihood in relation to other outcomes. A random variable which is 1 20% of the time, 2 30%, 3 50% has the same entropy as one that is 1, 10, or 1000 with the respective probabilities 0.5, 0.2, and 0.3, but each variable has a different variance. Variance will not tell you what the entropy is. Entropy will not tell you the variance. $\endgroup$ – Future Security May 5 at 1:32
  • $\begingroup$ Min-entropy is not dropping with more dice. The maximum probability of any given sum decreases with more dice. Min-entropy goes up as max probability goes down. For fair two dice, the most like outcome (sum 7) has $0.1\overline{6}$ chance of occurring. $-\log_2(1/6) \approx 2.58$. For three dice, sums 10 and 11 tie for 12.5%. Therefore the min-entropy of this 3-dice-sum distribution is $-\log_2(0.125) = 3$ bits. $\endgroup$ – Future Security May 5 at 1:50
  • $\begingroup$ Entropy is unaffected by ignoring fixed bits. It is the system that has entropy, not individual bits. In fact, if you were to concatenate the four variables and could ensure that it's always possible to extract the original four values from the combined string, then the result would have as much entropy as you could possibly get from the result of any function of those four variables. Even adding a constant prefix wouldn't lower entropy. Entropy depends only on the probability of each outcome. Not how you represent the outcome. $\endgroup$ – Future Security May 5 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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