How difficult is it to modify an ISO image and still have the old md5 check sum?

Question

If I want to download the ubuntu11.04.iso then:

UBUNTUMIRRORSRV -> ISP -> ISP -> etc. -> MYPC

I just want to ask that how difficult is to spoof the original MD5 sum (e.g.: the md5sum would be reachable through HTTPS!).

So we have:
- on the ubuntumirrorsrv: XY md5hash, and XZ ubuntu iso
- on mypc (the downloaded iso from ubuntumirrorsrv): XY md5hash, and XY! ubuntu iso.

so could the md5hash be the same (as the original one on the ubuntumirrorsrv) if there were a "mitm" attack, that modified (put a trojan) in the ubuntu iso (e.g.: one of my ISP)? (+- a few MBytes) - how difficult could that be?

Answer 1

It would be difficult to the point where to seriously suggest it even remotely possible is verging on lunacy.

There have been some demonstrations of theoretical attacks against MD5 wherein the "attacker" could create message data intended to yield a predetermined MD5 hash. But this is miles and miles away from adding a non-jibberish file to an ISO and having it give the same hash.

A much more likely attack scenario would be the MitM altering the page that lists the MD5sums before it gets to you so that you see the attacker's hash rather than the real one. However unlikely this may be, here are the hashes for your comparison:

ubuntu-11.04-desktop-amd64.iso 7de611b50c283c1755b4007a4feb0379

ubuntu-11.04-desktop-i386.iso 8b1085bed498b82ef1485ef19074c281

Answer 2

The would be called a second preimage. For a hash function h with an output of n bits, there are three kind of attacks that we consider; for each, there exists a generic algorithm with a high cost, and the function is deemed secure if we cannot find any method which is faster than the generic algorithm. The attacks are:

• Preimage: given x (a n-bit string), find m such that h(m) = x. Generic attack has average cost 2ⁿ (expressed in evaluations of the function h over small inputs): the generic attack works by trying random messages m until hitting x (the "luck and pray" attack).

• Second preimage: given m (a given string), find m' distinct from m and such that h(m) = h(m'). This is the case you envision here. Generic attack is again of cost 2ⁿ and is similar to the preimage attack.

• Collisions: find m and m', distinct from each other, such that h(m) = h(m'). Generic attack has cost 2^n/2 (known as the birthday attack).

MD5 has a 128-bit output. 2¹²⁸ evaluations is a very high and should provide adequate security (it is one billion billions times higher than is technologically doable right now, even with a google/facebook-like budget). On the other hand, 2⁶⁴, while still very expensive (months of computation with thousands of computers), has already been demonstrated once (see distributed.net).

Moreover, a number of weaknesses have been found in MD5, allowing for a very efficient algorithm for generating collisions (with my PC I can generate one MD5 collision in 14 seconds on average -- using a single core). For that reason, MD5 is not considered secure anymore. But no shortcut for second preimages is currently known. The existence of weaknesses leading to easy collisions shows that the internal structure of MD5 is not "garbled enough" so we have reason to worry about preimage attacks which might be found in the near future. But, right now (July 2011), no such attack is publicly known.

So the answer to your question is that it would be overwhelmingly difficult to send you an altered ISO which would end up with the same MD5 hash than the original one. But the Ubuntu distributors would be well inspired to begin publishing SHA-256 hashes too. Just in case.