4

Let's say I need to generate a 32-character secret comprised of ASCII characters from the set '0'..'9'. Here's one way of doing it:

VALID_CHARS = '0123456789'

generate_secret_string() {
    random = get_crypto_random_bytes(32)
    secret = ''
    for (i = 0; i < 32; i++) {
        secret += VALID_CHARS[random[i] % 10]
    }
    return secret
}

My concern is that my character selection is biased. Because 10 doesn't divide evenly into 256, the first 6 VALID_CHARS are slightly more likely to occur.

The secret space is 1032, but my generated secrets have less entropy than that. How can I calculate precisely how much entropy I actually have?

Update: Clarifications

  • For this question, I just want to know how to compute the entropy of this technique. I'm trying to compare it against other techniques for which I know how to compute the entropy.
  • The parameter I chose here (10 valid chars) is just an example. I'd like to be able to evaluate the entropy for other character ranges as well.
2
  • This depends entirely on the kind of bias. If you have mod 256 and have 255 characters, then the first character is twice as likely to appear. If you have 170 characters mod 170, then the first 85 characters would be twice as likely. I am not really a math person, so I can't answer precisely, but I know that bias can be more and less severe.
    – user163495
    Commented May 24, 2019 at 8:55
  • At the point you're doing this, I'd probably just seed a normal random number generator with the crypto-random value, then just generate unbiased digits, eg int nextDigit = random.Next(0, 10); In most base language utilities, the problem with random generators is doing something like seeding off the system time, as opposed to a material weakness in the PRNG itself. There are also usually better libraries to help you out with this, anyways. Commented May 24, 2019 at 17:47

3 Answers 3

5

For reasons that are a bit involved, cryptographers use the min-entropy of a distribution as a measure of its strength:

The min-entropy, in information theory, is the smallest of the Rényi family of entropies, corresponding to the most conservative way of measuring the unpredictability of a set of outcomes, as the negative logarithm of the probability of the most likely outcome.

One neat things about min-entropy is that it's easier to compute than the Shannon entropy (a.k.a. the average entropy) that hft's answer has amply illustrated (which requires you to compute the entropy of all alternatives and do a weighted average by their probabilities). You just have to:

  1. Figure out the probability of the likeliest outcome. In this case, it's 26/256 ≈ 10.16%.
  2. Take the negative logarithm of that: -log2(25/256) ≈ 3.30 bits.

This means any digit chosen by your procedure will have at least 3.30 bits of entropy, and possibly more. By comparison, the entropy of a uniformly chosen decimal digit is log2(10) ≈ 3.32 bits. Since the min-entropy you're getting only marginally lower than the entropy of a uniform random digit (which is the best case you could hope for), we can conclude that the digit selection bias in your example doesn't matter in practice.

1
5

My concern is that my character selection is biased. Because 10 doesn't divide evenly into 256, the first 6 VALID_CHARS are slightly more likely to occur.

The secret space is 10^32, but my generated secrets have less entropy than that. How can I calculate precisely how much entropy I actually have?

Because not every digit is equally likely you can not set

p(i) = 1/10

for all the digits.

Rather, you have

p(0) = p(1) = ... = p(5) = 26/256

and

p(6)=...=p(9) = 25/256

So, use the usual formula for entropy:

e = -Sum[ p(i) log(p(i)) ] = -6*(26/256)*(log2(26/256))-4*(25/256)*(log2(25/256)) = 3.32166...

to get the numerical value of "entropy" e for one digit (n.b., if p(i) were 1/10 for each digit then this would be e=log(10), but it is not)

Then the entropy for the full string of 32 characters is:

32*e = 106.293...
6
  • I've forgotten how to format math on this stackexchange...
    – hft
    Commented May 24, 2019 at 2:12
  • oh no, there is actually no LaTex engine! Let me try to reformat this answer some other way I guess...
    – hft
    Commented May 24, 2019 at 2:14
  • yep, crypto stack exchange has MathJax, but infosec does not. security.meta.stackexchange.com/a/2784/70830
    – Z.T.
    Commented May 24, 2019 at 2:17
  • weeping emoji
    – hft
    Commented May 24, 2019 at 2:18
  • The average entropy formula given is right, but you don't give the answer: e = 3.3217 bits, and therefore 32 × e = 106.29 bits. Note that log2(10) = 3.3219 and thus 32 × log2(10) = 106.30 bits. If we use a min-entropy calculation instead then we get -log2(26/256) = 3.2996 bits, and 32 × -log2(26/256) = 105.59 bits. Which means that the bias in this example is nothing to worry about. Commented May 24, 2019 at 22:49
0

You need log2(10^32) entropy. By my calculation, 106.3 bits. What if you do get_crypto_random_bytes(14), throw away 6 bits, and then treat the value as a single number and convert it to decimal?

5
  • This doesn't address the fact that 0,1,2,3,4,5 are more likely than 6,7,8,9
    – hft
    Commented May 24, 2019 at 2:05
  • My proposed alternative algorithm does not have this problem.
    – Z.T.
    Commented May 24, 2019 at 2:07
  • Then this is not an answer to the question...
    – hft
    Commented May 24, 2019 at 2:08
  • I interpreted the question to be "how to do this better". If the question really only concerns "analyze this less good method", then I did not answer the question.
    – Z.T.
    Commented May 24, 2019 at 2:09
  • Yeah, in this case I actually just want to analyze this one method. (So I can compare it against other methods that I already know how to analyze.) Commented May 24, 2019 at 5:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .