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, 2019 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, 2019 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, 2019 at 16:29
  • 2
    $\begingroup$ You seem to think that md5 is collision resistant. I have bad news for you. $\endgroup$
    – Maeher
    Dec 11, 2019 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, 2019 at 18:03


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.