What are the “costs” to find a pre-image, weak collision, or strong collision?

Question

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

Answer 1

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)

  

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