# Could we break MD5 entirely in the future?

Even of today MD5 is (sadly) still heavyly used in some applications. Even big tools like ApacheMD5. But even today there are more then enough MD5 hashes which are still not cracked.

According to Wikipedia, the strongest attack at time of writing this seems to be a preimage attack against MD5 wich was published in April 2009, was published that breaks MD5's preimage resistance. This attack is only theoretical, with a computational complexity of $2^{123.4}$ for full preimage.

But in the future with Quantum computers, could we get all known plaintext for MD5 (or make them collide)? And would anyone who has a quantum computer even take the effort ot do so ?

• They're not cracked because nobody's bothered to crack them. Having a complete lookup table of all hashes isn't going to affect people using apache-md5 passwords: they're already screwed for different reasons. – OrangeDog Jul 26 '17 at 16:21
• Even of today MD5 is (sadly) still heavyly used in some applications, I wouldn't say that. MD5 is perfectly fine when used in non security related things, like i.e. rsync protocol. Not the best solution thought. – Hauleth Jul 26 '17 at 21:19
• MD5 is fine for rsync only if you can guarantee that nobody else has control of the chunks of the files you're synchronizing. Do they contain emails someone sent you? Bzzzt: Not fine. Do they contain a browser cache from web sites you have visited? Bzzzt: Not fine. Do they contain Git repositories you've cloned from someone? Bzzzt: Not fine. For general-purpose tools like rsync one stands on very shaky ground when one asserts it's OK—it's not security-related. – Squeamish Ossifrage Jul 26 '17 at 22:14
• However, a situation where making someone's rsync intentionally fail is to anyone's benefit is in the end security related - defeating a backup system set up for traceability, plain vandalism, hiding changes when someone checks for changes/tampering via a "dry" rsync... all sound like security breaches. – rackandboneman Jul 27 '17 at 2:13
• @Navin: [citation needed] With the notable exception of Snefru, to my knowledge, no serious cryptographic primitive advertised as preimage-resistant has ever had its preimage resistance broken. – Squeamish Ossifrage Jul 27 '17 at 4:02

If you follow the reference for the alleged preimage attack on MD5, you will see that although the time cost is $2^{123.4}$ steps, the memory cost is $2^{45} \times 11$ words of memory, which has a far higher area*time cost than a smart attacker would use—a smart attacker would fit 32 CPU cores or MD5 circuits in parallel into much less die area and get an answer faster, in $2^{123}$ time. So that attack gives no reason to treat MD5's preimage resistance as below its advertised level.

But the advertised level—the best preimage resistance that can be provided by a 128-bit hash—is not very high. A smart attacker will do even better: a smart attacker will attack many targets at once with a parallel brute force machine using rainbow tables, and find one preimage among $n$ target hashes on a machine parallelized $n^2$ ways with probability $p$ at the area*time cost of about $2^{128}p/n$ evaluations of MD5—much cheaper than the cost of about $2^{128}p$ for an attack on a single target, and in the time for $2^{128}p/n^3$ sequential evaluations of the MD5. This is not an attack on MD5 in particular; this is a generic attack on any 128-bit hash. Could this happen in practice? It's within the realm of human feasibility, even for a preimage that is not an easily guessable passphrase.

With an array of $k$ quantum computers large enough to run Grover's algorithm, you could find a single MD5 preimage with probability $p$ in about $2^{64}\sqrt{p/k}$ time. Whether this will ever be cheaper than the standard generic classical parallel brute force attack depends on how cheaply quantum computers capable of running Grover can be built and powered—at the moment, they do not exist at all. (Studying the quantum multi-target story is left as an exercise for the reader.)

That doesn't necessarily mean you would find the original input strings—unless you know something about the distribution of the original input strings and restrict your search to that, you might find gibberish that happens to have the same hash as the original input strings. (In fact, merely knowing an MD5 hash—a 128-bit string—doesn't mean there ever was an ‘original input string’. Here's an example: 914c24484128dfe05c3060632ee16e3f. Maybe you can find a preimage for that, but I just pulled it out of /dev/urandom.) So it would mostly be useful mainly for either (a) filling in very short unknown high-entropy details of large documents the rest of which you know, or (b) inventing substitute strings that will have the same hash and that are useful only in active attacks on systems still using MD5 as a proxy for identity.

As for computing collisions—finding pairs of messages $m_0 \ne m_1$ with $\operatorname{MD5}(m_0) = \operatorname{MD5}(m_1)$, with no control over what the common hash value might come out to be—you don't need a quantum computer to do that. It's practically a parlor trick at this point, costing under a million MD5 computations to make fresh ones, to say nothing of extending existing collisions into longer ones which costs no computation at all.

• With an array of $k$ quantum computers... you could find a single MD5 preimage in about $2^{64}/k$ time; is that true? I've looked for parallel versions of Grover's, and the best I could find is $2^{64}/\sqrt{k}$ time. Do you have a reference for an efficient parallelized version? – poncho Jul 26 '17 at 15:08
• Nope! I misquoted the paper I cited. Fixed now. – Squeamish Ossifrage Jul 26 '17 at 15:12
• Thanks for the reference; I had thought that was the case, now I have proof... – poncho Jul 26 '17 at 15:16
• When it comes to breaking a hash algorithm, I wouldn't think that finding the original input is the goal. If, for example, a site is distributing an executable binary and publishes the size and an MD5 hash of the file, the attacker's goal wouldn't be to find the original input, but would rather be to create a malicious file of the same size that produces the same hash that they could trick users into downloading and executing. – martin Jul 27 '17 at 7:00
• @martin: That is certainly one application! The OP's question seemed to be about recovering what the original plaintexts were, so I focused on that goal. What you describe is similar to (a), except instead of learning what the original input was, we don't care and just fill it with garbage to match a target hash, like a Bitcoin block. – Squeamish Ossifrage Jul 27 '17 at 7:11