3
$\begingroup$

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 ?

$\endgroup$
3
$\begingroup$

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})$.

$\endgroup$
  • 1
    $\begingroup$ thanks a lot I guess the memory requirement for this algorithm is number of elements in lst. $\endgroup$ – han Oct 17 '16 at 3:25
  • $\begingroup$ @han the best way of thanking Biv is to accept the answer if he helped you along enough. Yeah, number of elements times $b$ of course. $\endgroup$ – Maarten Bodewes Jan 13 '17 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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