# Exactly how bad is using 'mod' to clamp reduce numbers to a given range?

Let's say I'm naive and want to generate a random integer in the range [0, m), so I do the following:

k = cryptographically_secure_rng() % m


where cryptographically_secure_rng returns a random integer in the range [0,n).
Obviously, assume m <= n. Now in general k isn't distributed uniformly anymore.

It seems to me that for any reasonably nontrivial value of m and n, this can't possibly cut the attacker's time by more than half -- and in general, it would seem to cut it by a much smaller fraction.
Yet my impression from security/crypto is that such a naive RNG would be catastrophic for the security of the system.

So my question is:
How bad is this from the standpoint of an attacker trying to attack a system by exploiting this function?

Could such a bias be abused and amplified (e.g. exponentially) to attack a system?
If so, in what kind of a system might this occur, and how?
If not, then is the problem worth worrying about, and why?

• @those who migrated this question: I wasn't just talking about crypto though... imagine an attacker trying to DDoS a service by making it execute worst-case behavior on a hashtable. Or whatever. Jan 30 '16 at 21:34
• I don't think it is a serious problem. The distribution of k will not be uniform (unless n%m=0), but it will be close to uniform. As an attacker I will start from zero and work up, rather than m-1 and work down. Jan 30 '16 at 21:41
• I would like to understand how the modulo operation influences the uniformity of k. Can someone link or summarize the information for me? Jan 30 '16 at 21:43
• @E.Rose take for instance $n = 10$ and $m=7$. So, the value 1 has double of the chance to appear, because 1 % 7 = 8 % 7 = 1 ... Jan 30 '16 at 21:47
• @squeamishossifrage : ​ The distinguishing advantage increases by less than m/(2$\hspace{-0.02 in}\cdot$n), so it'll also be secure when that is negligible. ​ ​ ​ ​
– user991
Jan 31 '16 at 0:26

The answer is that it depends on how much larger $n$ is than $m$, and also depends on the application. If $n$ is much larger than $m$ (say 64-128 bits longer) then you are fine, as pointed out by @Ricky Demer. However, otherwise, you will have bits that have a bias.
If you are using this key in HMAC, then it doesn't matter. However, in general, it can matter and can matter a lot. Thus, I strongly recommend against doing this without making $n$ at least 64-128 bits longer than $m$. If you want to see a work where small biases are used to recover plaintext, then Analysing and Exploiting the Mantin Biases in RC4 is a good place to start.