6
$\begingroup$

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:

$\endgroup$
  • 3
    $\begingroup$ I asked the author: "yes it's an error, was reported, thought it was in the errata" $\endgroup$ – CodesInChaos Mar 17 at 21:58
10
$\begingroup$

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%.

      Taken from the above blog

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – c4mx Mar 17 at 14:55
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Mar 17 at 15:10
  • $\begingroup$ I think in your H1(x) calculation, it misses a factor of 10, tho your link to wolfram alpha's calculation is correct. $\endgroup$ – c4mx Mar 18 at 9:16
  • $\begingroup$ @c4mx Thanks. Corrected. $\endgroup$ – kelalaka Mar 18 at 9:27
5
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.