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?

Improve this question
$\endgroup$
14
  • $\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$
    – user541686
    Commented Jan 30, 2016 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
    Commented Jan 30, 2016 at 21:41
  • 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 Vitor Lima Pereira
    Commented Jan 30, 2016 at 21:47
  • 1
    $\begingroup$ I think this question already has an answer. Unless $m$ is a factor of $n$, your RNG is no longer cryptographically secure. $\endgroup$
    – r3mainer
    Commented Jan 31, 2016 at 0:18
  • 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
    Commented Jan 31, 2016 at 0:26

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.