$H_1$ is a collision-resistant hash function with an $L$-bit output. 2 hash functions are created based on it as follows:

$$H_2((k_1,k_2);m) = (H_1(k_1;m), \space H_1(k_2;m))$$

$$H_3((k_1,k_2);(m_1,m_2)) = (H_1(k_1;m_1), \space H_1(k_2;m_2))$$

Notation: $k1$, $k2$ are keys. $m$, $m_1$, $m_2$ messages. $(m_1,m_2)$ is simply the concatenation of $m_1$ and $m_2$. What would the smallest number of evaluations (based on $H_1$) be to successfully do a birthday attack on $H_2$ and $H_3$ with at least 1/2 probability? Could you please explain along with the attack that you build against $H_2$ and $H_3$?

This is a past practice question and I do have a solution (spoiler: see bottom of post) but do not understand how to get to it myself. I understand that to find a collision in $H_1$ I have to do $2^{L/2}$ number of evaluations where $L$ would be the output length.

Bonus help would be any variations of the given hashes to help solidify my understanding of the concept further.

The final answer is: $O(2^L)$ for $H_2$ and $O(2^{L/2})$ for $H_3$

  • $\begingroup$ Perhaps you mean $O(2^L)$ and $O(2^{L/2})$ for your final answer... $\endgroup$ – poncho May 21 at 13:18
  • $\begingroup$ If the collision doesn't require the use of the same keys on both sides, then $H_2$ can be attacked in $O(2{L/2})$ time $\endgroup$ – poncho Jun 20 at 19:29

Hint: Can you break down the problem of finding a collision in $H_2$ into two independent subproblems that you can compute separately, or do you have to find a collision for all of it together? What about $H_3$?


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.