Hacker News Reader

Comment by nayuki | Hacker News Reader

There is a small inherent bias in TOTP (and HOTP) codes. The algorithm extracts 31 consecutive bits from a SHA-1 hash ( https://en.wikipedia.org/wiki/HMAC-based_one-time_password#A... ). Let's assume that SHA-1 produces uniformly random bits.

The 31-bit number is modulo'd by 10^6 to generate a 6-digit base-10 number. But 2^31 isn't a multiple of 10^6, so some remainders will be slightly more likely than others. Namely:

• 000000 to 483647: 2148/2147483648 ≈ 1.000240e-6 chance.

• 483648 to 999999: 2147/2147483648 ≈ 0.999774e-6 chance.

This kind of bias always happens when changing the range of random numbers and the number of possible outcomes is not a divisor of the number of incomes, and rejection sampling isn't used.

This is why, for example, java.util.Random.nextInt(int n) (which generates an integer in the range [0, n)) carefully uses rejection sampling in its algorithm: https://docs.oracle.com/javase/8/docs/api/java/util/Random.h...

View on HN

One I remember stumbling upon some years back was the .NET Framework equivalent of that, System.Random.Next(0, int.MaxValue), which has a much greater probability of producing odd numbers than even numbers, the probability of getting odd numbers being 50.34%, because of some rather unfortunate translations between integers and floating points. https://fuglede.dk/en/blog/bias-in-net-rng/

The most extensive comparison of rejection methods I've seen is on the PCG blog:

https://www.pcg-random.org/posts/bounded-rands.html

The effect of this on the min-entropy is basically nil.

Added: to be pedantic, the difference in min-entropy from a uniform distribution is about 0.000347 bits if my calculation is right (log2(2148*1e6/2**31)). Really, this is not of practical significance given how TOTP is used.

I love how this response corresponds to your profile description, and I mean that in a positive way, just to be clear.

The entropy ( https://en.wikipedia.org/wiki/Entropy_(information_theory) ) of the uniform distribution is −log2(0.000001) ≈ 19.9315685693 bits.

The entropy of the TOTP distribution is −log2(2148/2147483648)×483648×2148/2147483648−log2(2147/2147483648)×516352×2147/2147483648 ≈ 19.9315685303 bits.

So yes, the difference in entropy is negligible. The TOTP distribution is worse by 39 nanobits (3.906e-8) per code.

Pedantry 2: normally in cryptography we use the min-entropy <https://en.wikipedia.org/wiki/Min-entropy> rather than the Shannon entropy that you linked, though in this case they are almost equal.

Exercise: consider a weighted, million sided die. 50% of the time when you roll it, it comes up 1. The other 50% of the time, it comes up on one of the other 999999 results, with equal likelihood. What is the min-entropy of this distribution? What is the Shannon-entropy? This should tell you why the min-entropy is preferable.

Added: hmm I think I made a calculation error further up. I'll look at it tomorrow if I can.

Not being an expert, I was unaware of this and worked through it after reading the article you linked.

So you have 1 bit for the min-entropy and about 11 bits for the Shannon entropy. The Shannon-entropy pretty much hides the elephant in the room, which is the enormous bias of rolling a 1. So basically in crypto you use the min-entropy because that reflects the most vulnerable scenario in a system which is what you prioritize protecting against, rather than protecting against the average scenario.

This was very insightful, thanks for sharing.

Reply on news.ycombinator.com