Is the following 4 digits code generator secure and non-deterministic?

Question

In a C# WCF service, I need to send a 4 digits code by SMS to validate a user account/password. For security reasons, the code has to be non-deterministic (so that a malicious user/hacker should not be able predict what the next code will be).

I use the following code :

protected string Generate4DigitsCode()
{
    RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider();
    byte[] bytes = new byte[4];
    rng.GetBytes(bytes);
    return string.Format("{0:D4}", BitConverter.ToUInt32(bytes, 0) % 10000);
}

I am especially worried by the modulo operation, which probably focus on the lowest bytes. Would it be better to do a integer division ?

Answer 1

I'm assuming that RNGCryptoServiceProvider is an interface to a properly implemented CSPRNG. If so, its output should be impossible to predict (for an adversary with any practical amount of computing power, and no access to the internal RNG state) and uniformly distributed (i.e. every $n$-bit output is generated with the same probability of $1/2^n$).

Thus, assuming that your CSPRNG isn't broken, as far as the attacker is concerned you're effectively generating truly random 4 × 8 = 32 bit random numbers and then applying a known function (reduction modulo 10,000) to map them into strings of four decimal digits.

The only possibly exploitable source of bias is therefore the non-uniformity of your reduction function: if the function maps more of the 32-bit random inputs to some 4-digit codes than to others, an attacker will know that those specific 4-digit codes will be more likely on average, and can optimize their attack to try them first.

So, how biased is your modulo reduction, then? It turns out that, while it's not perfectly unbiased, it's as close to unbiased as any map from 32-bit numbers to 4-digit codes can be.

Since the number of possible outputs (10,000) does not evenly divide the number of possible inputs (2³² = 4,294,967,296), there must necessarily be some bias. A perfectly unbiased reduction would have to map 429,496.7296 inputs to each output, but that's obviously not possible — the number of inputs mapped to each output must be an integer. So at best, we can arrange for some outputs to be generated by 429,496 inputs and some by 429,497 inputs, making the latter ones about 1.0000023 times as likely to occur as the former kind.

The modulo reduction indeed achieves precisely this. Specifically, using your generation scheme, the codes 7295 and below are about 1.0000023 times as likely to occur as the codes 7296 and above.

For all practical purposes, this bias is completely negligible. Certainly, it won't be the weakest point of your authentication system, at least not compared to the obvious weakness that, regardless of how carefully you generate the codes, an attacker has a one-in-10,000 chance of getting the code right just by guessing randomly.

(If you did wish to eliminate even this tiny amount of remaining bias, you could either generate even more input bits for each code (e.g. 64 bits, for a bias of 1,844,674,407,370,956 / 1,844,674,407,370,955 ≈ 1.0000000000000004), or you could use rejection sampling and regenerate a new 32-bit number whenever the original one happens to be equal to or greater than 4,294,960,000 (= the largest multiple of 10,000 not greater than 2³²). But, as noted above, this would surely be overkill.)