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

• I asked the author: "yes it's an error, was reported, thought it was in the errata" Mar 17 '20 at 21:58

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

• Thanks for your response! I forgot to type a '16' in my first entropy calculation when writing, edited. So your calculation is same as mine, which is not 45 bits entropy stated by the book author. I guess the book author probably made a mistake about that.
– c4mx
Mar 17 '20 at 14:55
• Well, Still not using the standard $16*10*1/10*log(10, 2)$, it should be $16*1/10*log(1/10, 2)$, assuming the second parameter is the base of the logarithm. Yes, there seems an error in the book that you catch it. Mar 17 '20 at 15:10
• I think in your H1(x) calculation, it misses a factor of 10, tho your link to wolfram alpha's calculation is correct.
– c4mx
Mar 18 '20 at 9:16
• @c4mx Thanks. Corrected. Mar 18 '20 at 9:27

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.