I'm trying a Birthday Attack to randomly generated strings and its $\mathop{SHA-1}$ hashes using a Mapped table of values in order to find a collision on only the first 8 bytes. With the first 4 or 5 bytes it was easy, but the problem now with 8 bytes is I'm running out of RAM memory as I'm storing the values, and I don't think generating all the possible hashes and storing them in a file is a solution. Any ideas to make it memory-efficient/faster?


About the memory requirement

Your target is 8 bytes long i.e. $2^{64}$ possibilities.

The probability to have a collision is given by the formula: $$P(n,N) \approx 1 - e^{-n^2/2N}$$ Where $N$ is the size of the output space and $n$ the number of values you try. By inverting the equation you get: $$n \approx \sqrt{-2N\ln (1 - p)}$$ For $p = 0.5$, you get : $$n \approx 1.2\sqrt{N}$$ Thus with $N = 2^{64}$, $$n = 1.2\times 2^{32}$$ Therefore you will need to generate about $5\ 000\ 000\ 000$ values of 8 bytes. The memory requirement is therefore of $40 GB$.

If you target $p = 10\%$ in order to reduce the memory requirement (you will just need to do the experiment a bunch of times), you will need $0.46\times 2^{32} \approx 2\ 000\ 000\ 000$ values and about $16 GB$ (which is a bit less constraining.

What you are doing is actually called a multi-target attack. I would also suggest you to have a look at this question : What are the memory requirements for this type of search if the hash function has an output length n bits?

Some optimisations:

You might want to avoid the random generation part. You could just take a seed $s$ and iterate from it using an array of values such that $$\forall i, h[i] = \mathop{SHA}(s + i)$$ This will divide the memory space required by 2 (as you don't need to store the value because it is the array index of the hash).

You might also want to consider the time complexity of your search (for each value you need to check that there are no previous collision). From my point of view, this really looks like in $O(n^2)$...

Another possibility would require you to look at differential cryptanalysis of $\mathop{SHA1}$ and look for differential trails where the 8 first bytes of the last difference are being composed only of $0$.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.