# Birthday attack on hash functions derived from a collision-resistant hash function

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

## bumped to the homepage by Community♦6 mins ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

• Perhaps you mean $O(2^L)$ and $O(2^{L/2})$ for your final answer... – poncho May 21 at 13:18
• 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 – 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$$?