What are the memory requirements for this type of search if the hash function has an output length n bits?

Question

Let us suppose that we perform a collision search to find a pair $x_1$, $x_2$ with $x_1 \neq x_2$ such that $h(x_1)=h(x_2)$ for a given hash function, and we would like to specify the memory requirements for this type of search.

What does memory requirements means in this question ?

Answer 1

The naive approach

A naive algorithm for a research of collision is the following:

1. choose $x_1$
2. compute $h(x_1)$
3. Choose $x_2 \gets x_1 + 1$ ($x_2$ takes the value $x_1 + 1$)
4. compute $h(x_2)$ and verify if it matches $h(x_1)$
5. if it does not, do $x_2 \gets x_2 + 1$
6. go back to step 4, repeat and rinse.

How much memory do we need for this algorithm to work?
Well we need to store only $x_1$ and $x_2$. You can also store $h(x_1)$ in order to not compute it each time.

So if $h$ has a $b$ bits inputs, you need... $2 \times b$ memory to find your collision ($b$ for $x_1$ and $b$ for $x_2$). This is the memory requirement for THIS search algorithm.

However this algorithm is clearly inefficient. Assuming the output of your hash function is $n$ bits. You have $2^n$ hash possibles. This will lead to an average of $\frac{2^n}{2}$ tentative... Clearly not feasible with a complexity of $O(2^{n-1})$.

The multi-target attack

In the previous attack we targeted a specific or fixed value ($x_1$). A more advanced attack consist of storing all the previous attempts and each time you try a new value of $x_2$, thus the multi-target.

The algorithm is the following:

1. consider an empty list $lst$.
2. choose $x$
3. add $x$ to $lst$
4. Choose $x' \gets x + 1$
5. Check if there is $x \in lst$ such that $h(x') = h(x)$
6. Add $x'$ to $lst$
7. Compute $x' \gets x' + 1$
8. go back to step 5, repeat and rinse.

I will let you guess the memory requirement for this algorithm.

In term of complexity, if you consider a list of $2^m$ elements, the complexity of this attack is $O(2^{n-m})$.