$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 '19 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 '19 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$?

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.