4
$\begingroup$

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?

$\endgroup$

migrated from security.stackexchange.com Jan 30 '16 at 21:32

This question came from our site for information security professionals.

  • $\begingroup$ @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. $\endgroup$ – Mehrdad Jan 30 '16 at 21:34
  • $\begingroup$ 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. $\endgroup$ – emory Jan 30 '16 at 21:41
  • $\begingroup$ I would like to understand how the modulo operation influences the uniformity of k. Can someone link or summarize the information for me? $\endgroup$ – Ella Rose Jan 30 '16 at 21:43
  • 1
    $\begingroup$ @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 ... $\endgroup$ – Hilder Vítor Lima Pereira Jan 30 '16 at 21:47
  • 1
    $\begingroup$ @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. ​ ​ ​ ​ $\endgroup$ – user991 Jan 31 '16 at 0:26
5
$\begingroup$

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.

$\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.