How to analyze the off-by-one error's impact on the entropy of the result?

Question

I'm reading Jean-Philippe Aumasson's book Serious Cryptography to learn more about cryptography. On page 37, the author gives an example of Cryptocat's off-by-one error in its PRNG implementation in 2013, as shown below:

Cryptocat.random = function() { 
    var x, o = ''; 
    while (o.length < 16) { 
        x = state.getBytes(1); 
        if (x[0] <= 250) {
            o += x[0] % 10;
        }
    } return parseFloat('0.' + o)
}

The off-by-one error is found in the IF condition clause which uses <= rather than <. The author states that the values generated had an entropy of 45 instead of approximately 53 bits.

I'm wondering how the entropy of 45 bits is calculated.

In fact, if the code uses <, then everything is all right: the probability of a decimal digit is equally 1/10. Thus the entropy of 16 decimal digits would be 16*10*1/10*log(10, 2) = 53.1508.

However, in the case of the above-flawed code, the probability of decimal 0 is 26/251, and the probability of each other value is 25/251. Thus, the entropy of 16 decimal digits would be 16*(26/251*log(251/26, 2) + 9*25/251*log(251/25, 2)) = 53.149.

I don't any clues on how to get the 45 bits entropy. Can anyone help me, please?

References:

• https://tobtu.com/decryptocat.php

• https://nakedsecurity.sophos.com/2013/07/09/anatomy-of-a-pseudorandom-number-generator-visualising-cryptocats-buggy-prng/

Answer 1

First of all the first Entropy calculation is not correct. Recall the definition of (Shannon) entropy:

$$H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_{\,b} \mathrm{P}(x_i)}$$

If uniformly chosen a digits entropy is

$$H(X) = -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 3.3219280...$$

• Case $<250$ with 16 digits;

  \begin{align} H_1(X) &= 16 \cdot - \sum_{i=1}^{10}{\frac{1}{10} \log_2\left(\frac{1}{10}\right)}\\ H_1(X) &= 16 \cdot 10 \cdot -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 53.15084951...\\ \end{align}

  See the calculation at Wolfram Alpha

• Case $\leq250$ with 16 digits;

  $$H_2(X) = 16 \cdot - \left( \frac{26}{251} \cdot \log_2\left(\frac{26}{251}\right)+9 \cdot \frac{25}{251} \cdot \log_2\left(\frac{25}{251}\right) \right) = 53.14921795...$$

  See the calculation at Wolfram Alpha

It seems this is a mistake in the book. The current errata doesn't include this.

The difference is tiny but can make a difference since 0 will occur more and that is distinguishable. For example, take a 1.000.000 sample occurrence of 0 is around 103,500 – approximately 10.36%.

      

For the visualization of the difference read this nice blog Anatomy of a pseudorandom number generator – visualizing Cryptocat’s buggy PRNG

Answer 2

In cryptography you usually want to use min-entropy (which is a lower bound on security) instead of shannon-entropy (which can be higher than the security if the attacker is content with breaking only a fraction of the targets).

Min-entropy is simply $-\log p$ where p is the probability of the most likely value. In this case this works out to:

$$-16 \cdot \log_2\left(\frac{26}{251}\right) \approx 52.34$$

which is still pretty close to 53.15, so the loss of security is small even in this model.