# Finding multiple smaller collisions equal work as finding a bigger collision?

Problem A:

I receive two hash digests $$H(x), H(y)$$ and the corresponding preimages $$(x, y)$$.

$$H$$ is a 128-bit cryptographic hash function: $$H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$$

I need to find two second preimages $$(x', y')$$ such that $$H(x) = H(x')$$ and $$H(y) = H(y')$$, where $$x \neq x'$$ and $$y \neq y'$$.

Problem B:

I receive one hash digest $$H'(x)$$ and and the corresponding preimage $$x$$.

$$H'$$ is a 256-bit cryptographic hash function: $$H': \{0,1\}^{*} \longrightarrow \{0, 1\}^{256}$$

I need to find one second preimage $$x'$$ such that $$H(x) = H(x')$$ , where $$x \neq x'$$.

Are problem A and B equivalent? In other words, do both take $$2^{256}$$ work?

Are problem A and B equivalent? In other words, do both take $$2^{256}$$ work?
No; in the first case, you can find the first collision with $$2^{128}$$ effort and then find the second collision with $$2^{128}$$ effort, yielding a total effort of $$2^{128}+2^{128} = 2^{129}$$
Actually, you'd likely start hashing arbitrary values, and stop after both a second preimage of $$x$$ and a second preimage of $$y$$ came up; this expected effort is slightly less than $$2^{129}$$...
• Thank you! That actually makes a lot of sense, you do the work for the first and then the work for the second, so you just do $2 \times 2^{128}$ work... For whatever reason I thought that it would be $2^{128} \times 2^{128}$ Apr 1, 2021 at 3:56