Security concern about reducing hash value using modulo operation

Question

As stated in the title, what I am looking for is information about a "technique" that I would like to use in some of my algorithms.

Sometimes I need to map a hash function's result into a range of numbers that is not as large as the hash function's codomain; to do so I use the modulo operator. I take the hash function's output and treat it as an integer; then to this integer I apply the modulo operation $$h(x)\bmod n\text,$$ where $n$ is the excluded upper bound of the allowed numeric range $\{0,\dots,n-1\}$.

Now what I would like to understand is if this leads to some security risk, other than the fact that the obtained "hash" size is smaller (so a brute-force attack is easier), for instance that a modulus operator could break randomness of the hash function in some way.

Thanks in advance for clarification.

Answer 1

Let's assume that $h(x)$ returns a value between 0 and $k$ (exclusive). If $h$ is a good hash, this distribution will be uniform.

Computing $h(x) \mod n$ will introduce a bias if $k$ is not a multiple of $n$. This bias is significant if $k$ is only slightly smaller than $n$ and decreases as $k/n$ grows. How large $k/n$ needs to be depends on what level of bias is acceptable to you.

The DSA algorithm needs to generate an unbiased number. NIST recommends (FIPS 186-4 in appendix B.2.1) that you should use at least 64 extra bits, i.e. that $k/n > 2^{64}$. This is a reasonable since it means that the bias only becomes detectable if the attacker sees around $2^{64}$ samples. I doubt that you'll generate that much data.

So if you take a cryptographic hash of at least 128 bits, interpret it as a big integer and take it modulo a number smaller than $2^{64}$ the resulting bias will be negligible.

If your application is less sensitive to bias, it might be acceptable to reduce a 64 bit number modulo $n$. This avoids the need for a big integer library and is the approach I took for my random string generator.

---

Another approach to avoiding bias is rejecting values between $\geq k - k \mod n$. But this means that you need to consume a potentially unlimited amount of random values, so it's probably not the best fit for your application.

Answer 2

You will have more collisions. Also the collision space could be smaller than expected and predictable but if the hash function is random enough and uniformly distributed, the collision space should not be predictable.

What you are doing might be equivalent to using a hash that has a smaller output. Although there might be things I don't see... but if it's something that doesn't depend on your life, or doesn't have to be overly secure, don't sweat it because it seems secure enough.