0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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}$ $\endgroup$ – Neal Page Apr 1 at 3:56

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.