Given 2 (weak) hash functions, namely MD5 and SHA1

The fact that there exists 2 different inputs that will result in the same output under both hashing functions is explained in "Can there be two hash functions without common collisions?"

I would like to quantify the probability of this type of inputs to be forged. Namely:

MD5(x) = MD5(y) whilst SHA1(x) = SHA1(y)

So if I keep the two hashes of a file, how much harder is it to forge another file that yield the same hashes rather than either of those individually ?

I expect it to be more than the added probability of each, but by how much (order of magnitude) ?

up vote 11 down vote accepted

A "simple" answer (but somewhat wrong) would be the following: define function $H$ which is the concatenation of MD5 and SHA-1; i.e. on input $x$, $H(x)$ will be the 288-bit string consisting of MD5($x$) (128 bits) followed by SHA-1($x$) (160 bits). If you have distinct two messages $x$ and $y$ such that MD5($x$) = MD5($y$) and SHA-1($x$) = SHA-1($y$), then, by definition, $x$ and $y$ are a colliding pair for $H$. Since $H$ has a 288-bit output, finding a collision for $H$ requires an average effort of, at most, $2^{144}$ invocations, since that's the best you can expect from a "perfect" hash function.

What's wrong in the paragraph above is that the $H$ function, as described above, is far from the "perfect" state. In 2004, Joux published (Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions) an attack that works on "iterated" hash functions such as MD5 and SHA-1, which shows that even if MD5 and SHA-1 were both ideally strong (given their output size), the concatenation would not be stronger than the strongest of the two. In other words, even without leveraging known attacks on MD5 and SHA-1, a collision on the concatenated hash function $H$ can be found in about $2^{80}$ invocations. This work was generalized in 2006 by Hoch and Shamir (Breaking the ICE - Finding Multicollisions in Iterated Concatenated and Expanded (ICE) Hash Functions).

Now, both MD5 and SHA-1 have known structural attacks. In an answer to a previous question on that subject, @poncho explains how to use the known attacks on SHA-1 (with cost $2^{61}$) to make a simultaneous MD5+SHA-1 collision in effort $2^{67}$. Amusingly, this does not leverage any specific weakness of MD5; it would also work for a perfect 128-bit hash function instead of MD5.

  • Thanks for the link to the very similar question. Though, is the probability not significantly higher due to the fact that both are "iterated" (or ICE) hash functions ? – Simon Oct 29 at 10:10
  • @Simon all practical hash functions we know are somehow iterated, because they have a finite internal state during computation. Not sure what the "CE" part contributes, though. – Paŭlo Ebermann Oct 29 at 10:52
  • Also, "probability" is not the right word here. Collisions exist, it's a mathematical necessity. What matters is the effort to find one. – Thomas Pornin Oct 29 at 14:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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