2
$\begingroup$

For a secure, n-bit hash function, what are the “costs” to find a pre-image, weak collision, or strong collision?

$\endgroup$

1 Answer 1

2
$\begingroup$

Definitions:

  • In the pre-image attack, given a hash function $H$ and a hash value $h$, we try to find $x$ such that $h = H(x)$. The $x$ need not be the original input value used to calculate the hash $h$.

  • In the second preimage attack ( weak collison); we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.

  • Collision attack (strong collision); we are looking for two different inputs $a$ and $b$ such that such that $H(a)=H(b)$.

Costs:

  • The cost of pre-image and secondary pre-image is $\mathcal{O}(2^n)$

    The usual search for preimage and secondary pre-image is either iterating from 0 to $c\cdot2^n$ or randomly testing $c\cdot2^n$ values from a larger space then $2^n$.

  • The cost of the collision is $\mathcal{O}(2^{n/2})$ with 50% probability and this is due to the birthday attack.

    The naive way is generating $2^{n/2}$ input hash pairs and sort them according to hash values. This costs around $\mathcal{O}(2^{n/2})$ space.

    A better way is using Pollard's Rho *;

    1. Pick a random hash value $h_1$ and set $h_1' = h_1$
    2. Compute $h_2 = H(h_1)$ and $h_2' = H(H(h_1'))$. That is one is slow one is fast.
    3. continue the process $h_{i+1} = H(h_i)$ and $h_{i+1}' = H(H(h_i'))$ until we reach an index $j$ such that $h_{j+1} = h_{j+1}'$

    We can visualize this algorithm as below; The algorithm eventually enter a cycle (the Rho-Shape)

    enter image description here

    The path to $h_5$ is a collision. The cycle length and the collision points can be found by Floyds algorithm.

    This requires $\mathcal{O}(2^{n/2})$ operations to find the collision.

    If we ask, what is the average cycle length is? If we model the hash function as uniform random then this is shown by Harris in 1960. For a hash function with $\ell$ bit output, the average cycle length is $\frac{1}{ 2} \sqrt{2 \pi \ell}$ for SHA256 that makes $2^{127} \sqrt{\pi}$. That makes it quite unreachable for a hash function with 256-bit output to run the cycle to find a collision


*In other context this is also known as Floyd Cycle detection algorith (Floyd's Tortoise and Hare). Knuth attributing it to Floyd, without a citation. The origin is not known.

$\endgroup$
1
  • $\begingroup$ I've looked for dupe but couldn't. If you see let close this question. $\endgroup$
    – kelalaka
    Dec 13, 2020 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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