# SHA1 collision event probability after n iterations

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

• 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.
– D.W.
Commented Jun 18, 2014 at 0:56
• Did you look at crypto.stackexchange.com/q/15068/351 ? (Did you remember to use search before asking?)
– D.W.
Commented Jun 18, 2014 at 0:58
• 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. Commented Jun 18, 2014 at 9:47

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.

• @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$ Commented Jun 17, 2014 at 15:36
• @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 Commented Jun 18, 2014 at 0:22
• 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. Commented Jun 18, 2014 at 7:38
• @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.
– otus
Commented Jun 18, 2014 at 14:19
• @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. Commented Jun 18, 2014 at 15:04