How to analyze the off-by-one error's impact on the entropy of the result? 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 &lt; 16) { 
        x = state.getBytes(1); 
        if (x[0] &lt;= 250) {
            o += x[0] % 10;
        }
    } return parseFloat('0.' + o)
}


The off-by-one error is found in the IF condition clause which uses &lt;= rather than &lt;. 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 &lt;, 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/
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 $&lt;250$ with 16 digits;

\begin{align}
H_1(X) &amp;= 16 \cdot - \sum_{i=1}^{10}{\frac{1}{10} \log_2\left(\frac{1}{10}\right)}\\
H_1(X) &amp;= 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%.

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

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