4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $\operatorname{mod} \hspace{.04 in} 2^{80} \:$ will just give you the left or right 80 bits, depending on whether you use big or little endianness. $\;\;\;$ $\endgroup$ – user991 Dec 9 '14 at 23:28
  • $\begingroup$ Yes, so my question could be: are the right 80 bits of the hash equally random to the left 80 bits? Or, more general, are all bits equally random? $\endgroup$ – Chris Dec 10 '14 at 12:01
  • $\begingroup$ Yes. ${}{}{}\;$ $\endgroup$ – user991 Dec 10 '14 at 12:25
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you very much. If in fact the result is not uniformly random, do you have any advice on how to create a uniformly randomized result between ${0...n-1}$ using $\operatorname{SHA-1}$? $\endgroup$ – Chris Dec 10 '14 at 12:46
  • 1
    $\begingroup$ it could be useful to insist on something that is hinted at in this answer: bare modulo may break indistinguishability from random but in a lot of cases we don't care that much because we just expect collision or pre-image resistance from a hash function. Be sure of what you need from SHA in your case. $\endgroup$ – Cédric Van Rompay Dec 11 '14 at 13:33
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I agree. Though, I do not really care about the increased collision probability. Rather, I just need the same pseuo-randomness in the result. $\endgroup$ – Chris Dec 10 '14 at 11:58
  • $\begingroup$ @Chris : $\:$ Will a secret key be involved? $\;\;\;\;$ $\endgroup$ – user991 Dec 10 '14 at 12:44
  • $\begingroup$ @Ricky: No, just a string-based identifier that is consistently mapped to a key space $\endgroup$ – Chris Dec 10 '14 at 12:59
  • $\begingroup$ There will be pseudo-randomness. The only real difference is that the results are just distributed over 2^80 values instead of the initial 2^160. If you randomly generate a number between 0 and 99 and then mod 10 that number, you've effectively generated a random number between 0 and 9.Then the probability of each value in the modified space will be equal to the sum of the probability of the values in the original space that map to the new value. $\endgroup$ – Charles B. Dec 10 '14 at 18:04

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.