# 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. Jun 18 '14 at 0:56
Did you look at crypto.stackexchange.com/q/15068/351 ? (Did you remember to use search before asking?) – D.W. Jun 18 '14 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. – Haradzieniec Jun 18 '14 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$ – poncho Jun 17 '14 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 – Dmitry Khovratovich Jun 18 '14 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. – Neil Slater Jun 18 '14 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 Jun 18 '14 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. – Neil Slater Jun 18 '14 at 15:04