Statistical properties of hash functions when calculating modulo

Question

When using SHA-1 to hash an input, the result is a pseudo-random number in the numeric ID space $\{0\dots2^{160}-1\}$. Do I loose any statistical property in the result if I use modulo to restrict the key space? Obviously, the probability of collisions increases but is the randomness affected?

As an example, if I hash a string 'something', the result is pseudo-random:
$\operatorname{SHA-1}(\mathtt{"something"}) = \operatorname{pseudoRandom}$

So what happens when calculating modulo? Do the statistical properties still hold?
$\operatorname{SHA-1}(\mathtt{"something"})\bmod 2^{80} = \operatorname{pseudoRandom}$

Edit: What I actually want to achieve is a uniform distribution of the resulting, restricted ID space when feeding the $\operatorname{SHA-1}$ function with pseudo-random strings.

Answer 1

The question asks if $\operatorname{SHA-1}(M)\bmod n$ is random, giving the example of $n=2^{80}$.

I'll consider arbitrary $M$ (that is, determined without knowledge of SHA-1, or just of SHA-1's 160-bit initialization constant), and that it makes $\operatorname{SHA-1}(M)$ indistinguishable from $160$ random bits (which is true from a computational perspective, baring any huge theoretical progress).

When $n=2^k$ for $0\le k\le160$ (including $n=2^{80}$ in the question), $\operatorname{SHA-1}(M)\bmod n$ is simply the integer with binary representation the $k$ low-order bits of $\operatorname{SHA-1}(M)$, thus is indistinguishable from $k$ random bits (proof sketch: an hypothetical efficient distinguisher for $\operatorname{SHA-1}(M)\bmod n$ can be turned into an efficient distinguisher for $\operatorname{SHA-1}(M)$).

For other $n$ of interest, that is $n=s\cdot2^k$ with odd $s>1$ and $\log_2(s)+k<160$, the low-order $k$ bits of $\operatorname{SHA-1}(M)\bmod n$ are the low-order $k$ bits of $\operatorname{SHA-1}(M)$, and similarly indistinguishable from $k$ random bits. However $\operatorname{SHA-1}(M)\bmod n$ is not uniformly random over the set $\{0\dots(n-1)\}$: low values are more likely than high values. When $n=3\cdot2^{158}$, odds that $\big(\operatorname{SHA-1}(M)\bmod n\big)<{n\over3}$ are $1\over2$, rather than $1\over3$ for a uniform distribution. For example, the generator specified by FIPS 186-1 Appendix 3.1 has such bias (but it does not matter much in the application).

---

Update: a comment asks a simple algorithm based on SHA-1 that, given an arbitrary input $M$, outputs an integer uniformly random on the set $\{0\dots(n-1)\}$ for some parameter $n$ with $0<n\le2^{160}$.

As previously stated, when $n$ is a power of two, we can use $\operatorname{SHA-1}(M)\bmod n$. This is also the case when $n<2^{90}$ or so, because the adversary gets a negligible advantage for computationally reasonable effort.

Whatever $n$, we can use the following:

• $r\gets 0$ ($r$ is expressed as a 16-byte string)
• repeat $h\gets\operatorname{SHA-1}(r\|M)$ and $r\gets r+1$ until $h\ge(2^{160}\bmod n)$
• output $h\bmod n$.

The output is uniformly random based on the fact that in the final step, $h$ is uniformly random on the set $\{(2^{160}\bmod n)\dots(2^{160}-1)\}$, which contains a number of elements multiple of $n$.

Answer 2

The randomness still holds in your example but it is not true for any value of N.

For example, if the original key space was {0,1,2} and you wanted to restrict it to {0,1}, doing mod 2 would give the following results:

0 mod 2 = 0 1 mod 2 = 1 2 mod 2 = 0

Clearly, 0 will occur more often than 1 (not uniformly random).

I believe the more general rule is the following:

Given an original key space of 0 to M-1, and a target key space of 0 to N-1, you are not "allowed" to mod N any number that is above or equal to M - (M mod N) (otherwise, it biases your randomness).

One solution could be to use your hash as the seed to a proper PRNG?

Disclaimer: I'm not a cryptographer.

Answer 3

Well, I am not an expert in this, and this is an answer only because I can't comment yet, however I will do my best. The numeric ID space is now functionally 0 to 2^80-1, so as you noted the probability of collisions increases. The result is that being distributed across a range of 0 to 2^80-1, due to the higher collision chance, results in a higher probability of a successful collision attack.