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

In 2004 paper, Rogaway and Shrimpton gave reference to Merkle's paper

• 1998 : One Way Hash Functions and DES

and they Merkle's definitions simply as

Contemporaneously, Merkle [10] describes notions of hash-function security: weak collision resistance and strong collision resistance, which refer to second-preimage and collision resistance, respectively.

Since we are talking about attacks, let's convert the definitions into;

Attack 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 ( breaking weak collision resistance); we are given $H,x,h$ with $h = H(x)$ and we need to find another $x'$ such that $h = H(x')$.

• Collision attack (breaking strong collision resistance); 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.}

---

Pollard Rho's with python

import hashlib
import secrets

def blake2b32(data):
    hasher = hashlib.blake2b(digest_size=6)
    hasher.update(data)
    return hasher.digest()

def pollard_rho(h):
    # Initialize both x and y with the same value
    x = y = h
    d = 1
    previous_x = x
    previous_y = y

    count = 0

    while d != 0:

        x = blake2b32(x)
        y = blake2b32(blake2b32(y))

        # Convert bytes to integers for bitwise XOR
        x_int = int.from_bytes(x, byteorder='big')
        y_int = int.from_bytes(y, byteorder='big')

        # Perform bitwise XOR
        d_int = x_int ^ y_int

        # Convert the result back to a bytes object
        d = d_int.to_bytes(6, byteorder='big')

        previous_x = x
        previous_y = blake2b32(y)

        if d == b'\x00\x00\x00\x00\x00\x00':
            print("Found collision!")
            print("x:", previous_x.hex())
            print("y:", previous_y.hex())

            print("count", count)

            return previous_x, previous_y

        count = count + 1

    print("count", count)

    return None

if __name__ == "__main__":
    # Generate a random hash value
    h = secrets.randbelow(2**32).to_bytes(6, byteorder='big')

    # Find a collision for the hash value
    result = pollard_rho(h)

    if result:
        x, y = result
        print("Input values that have the collision:")
        print("x:", x.hex())
        print("y:", y.hex())
    else:
        print("No collision found")

with an output

Found collision!
x: 63ebb4a1a3cb
y: 6858c12e10e5
count 11526583
Input values that have the collision:
x: 63ebb4a1a3cb
y: 6858c12e10e5

real    0m24,966s
user    0m24,931s
sys     0m0,012s

1. Note that for 4 bytes it was less than 1 second.
2. I've used Bard and corrected it many times, and finally I've changed the random with secrets that it again failed to replace...