1
$\begingroup$

There are String1 and String2 - some variables-strings. The probability of collision for different String1 and String2 is 

P{SHA1(`String1`) == SHA1(`String2`)} = p

What's the probability of

P{SHA1(SHA1(`String1`))} == P{SHA1(SHA1(`String2`))} //two times
P{SHA1(...(SHA1(`String1`)))} == P{SHA1(...(SHA1(`String2`)))} //10^9 times
Improve this question
$\endgroup$
3
  • $\begingroup$ What do you think? What have you tried? Where did you get stuck? Where did you run into this question? What is the context/motivation for your question? This is not a site where you copy-paste your exercise and we do your exercise for you. $\endgroup$
    – D.W.
    Commented Jun 18, 2014 at 0:56
  • $\begingroup$ Did you look at crypto.stackexchange.com/q/15068/351 ? (Did you remember to use search before asking?) $\endgroup$
    – D.W.
    Commented Jun 18, 2014 at 0:58
  • $\begingroup$ The question came into play after using many iterations for generating hash for the password (with or without using salt). I was curious if it gets less secure after using 10^9 iterations and was curious if it gets not secure at all, if we don't use salt and the push number of iterations to infinity (neither asked nor answered this question yet). Many iterations with salt was used to exclude using of rainbow tables by hackers so the server counts the hash for some (mili-)seconds. $\endgroup$
    – Haradzieniec
    Commented Jun 18, 2014 at 9:47

1 Answer 1

Reset to default
2
$\begingroup$

Assuming the inputs and outputs are random, you would expect:

$$\begin{align} P[\operatorname{SHA1}(s_1) \not= \operatorname{SHA1}(s_2)] &= 1 - 2^{-160} \\ P[\operatorname{SHA1}^2(s_1) \not= \operatorname{SHA1}^2(s_2)] &= (1 - 2^{-160})^2 \\ ... \\ P[\operatorname{SHA1}^n(s_1) \not= \operatorname{SHA1}^n(s_2)] &= (1 - 2^{-160})^n \approx 1 - n/2^{160}, \\ \end{align}$$

where $\operatorname{SHA1}^2 = \operatorname{SHA1} \circ \operatorname{SHA1}$, etc.

Thus, $P[\operatorname{SHA1}^{10^9}(s_1) = \operatorname{SHA1}^{10^9}(s_2)] \approx 10^9 / 2^{160} \approx 2^{-130}$.

That's for a single pair $s_1 \not= s_2$. If you are looking for collisions, you would expect a collision with $\operatorname{SHA1}^{10^9}$ after something like $2^{130/2} = 2^{65}$ strings.

This approximation only holds while $n$ is small enough, and breaks down when it gets close to $2^{80}$ and cycles start to become an issue. However, for $10^9$ it should do all right.

However, there are (theoretical) attacks to find collisions in SHA1 faster, so for non-random inputs the probabilities could be higher.

Improve this answer
$\endgroup$
8
  • 4
    $\begingroup$ @DmitryKhovratovich: actually, it's not quite correct, however it's in the other direction. It's fairly close for small $n$ (and in this context, $10^9$ is small), however for huge $n$, the cycle structure of iterated SHA1 becomes important. Iterated SHA1 will fall into a cycle eventually, that means that two different inputs have a good probability of falling two different cycles, or two different offsets in the same cycle -- this means that there is a good probability that two different inputs will never collide for any $n$ $\endgroup$
    – poncho
    Commented Jun 17, 2014 at 15:36
  • 3
    $\begingroup$ @poncho: the cycle effect comes into play when the number of iterations approaches $2^{n/2}$. Before that, the image size of $SHA1^i$ is about $\frac{2^n}{i}$, so for $i=10^9$ you'd have $(1-2^{-130})$ instead of $(1-2^{-160})$. See eprint.iacr.org/2014/223.pdf for the details $\endgroup$
    – Dmitry Khovratovich
    Commented Jun 18, 2014 at 0:22
  • 2
    $\begingroup$ I think there is danger in extending analysis of SHA1 treating it as "true random" through so many iterations. My feeling is that its pseudo-randomness comes into play quite early on, and probabilities of collisions for large n are much lower than estimated. I'd perhaps run an experiment with a truncated SHA1 (e.g. 16 bits) to see what properties that has. $\endgroup$
    – Neil Slater
    Commented Jun 18, 2014 at 7:38
  • 2
    $\begingroup$ @NeilSlater: I ran a quick test with 16-bit SHA1 and the results match the formula from the answer like this (inverse probability that two random strings are equal, plotted against the expected $2^{16}/n$). Python code. $\endgroup$
    – otus
    Commented Jun 18, 2014 at 14:19
  • 1
    $\begingroup$ @otus: I must have made a mistake in my experiment (and I have deleted comment with spurious claims that probability seems limited to $2^{-15}$ irrespective of number of iterations). I've played with a few variations of your code to make it more like my originally-intended test (longer, random strings, iterating digest, not hex digest). I get same results as you. Looking for my bug now . . . found it, I had a hard-coded value for N (or what you call N in your code) over-riding the param that I set for later tests, so most of my tests only looked at two iterations. $\endgroup$
    – Neil Slater
    Commented Jun 18, 2014 at 15:04

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.