# Computational feasible to reverse MD5SUM?

This might be out of ignorance, I apologize, but how complex of a problem might it be to generate a file of size $N$ whose MD5SUM is $X$?

For example,

ls -l wczasp.rb
-rwxrwxrwx  1 master master     7273877 2011-01-30 17:13 wczasp.rb

md5sum wczasp.rb
acf3602b5eb9a2db3e365d3043682faf  wczasp.rb


So, how computationally hard might be to generate any 7273877-byte file whose 128-bit checksum is also acf3602b5eb9a2db3e365d3043682faf? In a sense, I am asking for a hash collision. My intuition says next to trivial, and nearly as useless too, but I would like to know for sure.

-
of interest: mscs.dal.ca/~selinger/md5collision – Marcos Mar 6 '12 at 22:46
The size of the file is not the important part here - for about every file size (above some minimum slightly more than the output size) there will be preimages, and brute-forcing requires only changing the last block to find one (with high probability), though it will take too long anyways. – Paŭlo Ebermann Mar 6 '12 at 22:56
Stemming from the Chinese engineer's algorithm linked above, it wasn't hard to soon find programs like md5clone.exe and evilize for Unix. The difference seems to be that they can control both images, whereas I can't control the first image; taken purely as data input. Anyway, I am actually less interested in MD5 itself, than in another way of hashing uncontrolled data that's more easily clone-able. You pointed out CRC, good--somehow thinking of that I confused it with MD5 earlier (huge diff I know) – Marcos Mar 7 '12 at 10:26

Actually, to the best of our knowledge, it's computationally infeasible.

By the terminology what we use when we discuss cryptographical hash functions, you're not asking for a hash collision (which is "find two different messages that hash to the same value"), but instead you're asking for a hash preimage (which is "for this hash value, find a message that hashes to it").

While MD5 is known to be woefully inadequate when it comes to resistance to hash collisions, there is no known way to find hash preimages that is faster than brute force (that is, hash different message until you stumble across one that happens to hash to the target value). This brute force approach with MD5 will take $O(2^{128})$ expected operations, and so it is computationally impractical.

-
You're both right, apparently what I was asking for was a hash preimage. My question was really just a stepping stone to another exploration, which is: what other well-known hashing functions do make it easy to find preimages, yet such that I only need store that hash + some kind of seed much shorter than either m or m', to allow me to regenerate that image or preimage again? – Marcos Mar 6 '12 at 23:04
@Marcos: it sounds like you're looking for a data compression method. Well, you're pretty constrained in what you can expect. If you expect the exact same preimage, well, if you have $2^N$ possible preimages, then the lengths of the hash and the seed must total at least $N$ bits long. If you expect a similar preimage, well, how well you can do is highly dependent on your definition of "similar". – poncho Mar 6 '12 at 23:42
The bit "there is no known way to find hash preimages that is faster than brute force" is wrong, see my answer. Also, we do not know how the file was prepared. – fgrieu Mar 7 '12 at 7:16
@poncho You are perhaps alluding to the Pigeonhole principle. I am just experimenting/designing an algorithm that tries to make that irrelevant by compensating in other ways. – Marcos Mar 7 '12 at 10:38

You are not asking for a collision but for a preimage.

Collision attack: the attacker computes two messages m and m', distinct from each other, such that m and m' hash to the same value.

Preimage: the attacker is given a goal (a hash value h) and finds a message m which hashes to h.

MD5 is weak for collisions, but not for preimages: no attack method is known, which can find preimages for MD5 faster than the simple luck-based method of trying out random messages until a match is found. The luck-based method has average cost $2^{128}$ evaluations of MD5 (because MD5 offers a 128-bit output, each trial has probability $2^{-128}$ of succeeding), and $2^{128}$ is way too much for being doable in practice. The traditional, conventional limit on what is doable is $2^{80}$. A good GPU could try about $2^{30}$ MD5 evaluations per second, so $2^{128}$ with one billion GPU (i.e. many more computers than what Google, IBM and Microsoft operate) would still need an average of $2^{68}$ seconds to complete, which is about 9 trillions of years.

-
Actually, the question looks like a second preimage is wanted. – Paŭlo Ebermann Mar 6 '12 at 22:53
Excellent and informative reply. – Marcos Mar 6 '12 at 23:06
The bit "no attack method is known, which can find preimages for MD5 faster than the simple luck-based method of trying out random messages until a match is found." is wrong, see my answer. Also, we do not know how the file was prepared. – fgrieu Mar 7 '12 at 7:36

We know no practically feasible way to do what you ask for, except if the hash X=acf3602b5eb9a2db3e365d3043682faf or the content of the file wczasp.rb was prepared specially to make that possible.

Assuming that the content of file wczasp.rb is arbitrary, what is asked would be a preimage attack. This is further sub-classified as first preimage if only the hash X=acf3602b5eb9a2db3e365d3043682faf is known to the attacker, or second preimage if the content of the file wczasp.rb is known.

If MD5 was a perfect Merkle–Damgård 128-bit hash, the best attack would be brute force, with an average cost of $2^{128}$ rounds (1 round is needed to hash a file of less than 56 bytes). Put simply, that won't happen even if you harnessed all the computing power available on earth.

However, MD5 is far from perfect. Its collision resistance is broken, very badly. In particular, this makes it very easy to prepare a wczasp.rb file hashing to some value, so that it is possible to exhibit a different file, of the same length, hashing to the same value. Without a theoretical break, that would have required about $2^{64}$ rounds using Floyd's cycle-finding, which is costly, but feasible.

Because MD5 has these known weaknesses, and no strong security argument, a much better-than-brute-force preimage attack against MD5 can not be ruled out (especially a second preimage attack, which is easier than first preimage in a Merkle–Damgård construct at least). In fact, a preimage attack with complexity $2^{123.4}$ has been published. That is 24 times better than brute force (but still entirely impractical). I have not reviewed it in depth, and conjecture that it could work only as a second-preimage attack for a file of length $21\pmod{64}$, which is part of the example problem.

While there is currently a helluva of headroom in the security of MD5 against pre-image attacks, the saying attributed to the NSA comes to mind: "Attacks always get better; they never get worse".

-
Interesting, even though I'm less about MD5 now and actually looking for easy collisions. Incidentally, I can't control the file contents per se but I can decide where to begin and stop reading from the input stream, to process as segments. So something using a Rolling hash might apply. – Marcos Mar 7 '12 at 21:03