Suppose I have the following hash function: $\newcommand{\md}[1]{\text{md#1}} \newcommand{\H}{\text{H}}$

$$\H(x, y) = \md{5}(x) \oplus \md{4}(y)$$

How can I prove it's collision proof?

I tried to say "lets assume we have an oracle which know how to find a collision/pre image of $\H$" and find an algorithm to find $\md5$ collision. I didn't manage to find such algorithm.

How can it be proved?

  • 3
    $\begingroup$ Actually, a standard birthday attack would take circa $2^{64}$ hash evaluations - plausible for some real-world entities... $\endgroup$ – poncho Dec 11 '19 at 15:26
  • 3
    $\begingroup$ Hint: when asked to prove something, first question if it is true or false. That'll get you a grasp on the problem. $\endgroup$ – fgrieu Dec 11 '19 at 15:34
  • $\begingroup$ I couldn't find a way to make a collision. Thus, the hint isn't usefull for me $\endgroup$ – MyNick Dec 11 '19 at 16:29
  • 2
    $\begingroup$ You seem to think that md5 is collision resistant. I have bad news for you. $\endgroup$ – Maeher Dec 11 '19 at 17:37
  • 1
    $\begingroup$ Well then fix $x$. Finding collisions in md4 is even simpler. It apparently takes less than 2 md4 invocations to find fresh md4 collisions. $\endgroup$ – Maeher Dec 11 '19 at 18:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.