Even of today MD5 is (sadly) still heavily 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 which 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 to do so ?

  • 6
    $\begingroup$ 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. $\endgroup$
    – OrangeDog
    Commented Jul 26, 2017 at 16:21
  • 2
    $\begingroup$ 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. $\endgroup$
    – Hauleth
    Commented Jul 26, 2017 at 21:19
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 26, 2017 at 22:14
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jul 27, 2017 at 2:13
  • 3
    $\begingroup$ @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. $\endgroup$ Commented Jul 27, 2017 at 4:02

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – poncho
    Commented Jul 26, 2017 at 15:08
  • 1
    $\begingroup$ Nope! I misquoted the paper I cited. Fixed now. $\endgroup$ Commented Jul 26, 2017 at 15:12
  • $\begingroup$ Thanks for the reference; I had thought that was the case, now I have proof... $\endgroup$
    – poncho
    Commented Jul 26, 2017 at 15:16
  • $\begingroup$ 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. $\endgroup$
    – martin
    Commented Jul 27, 2017 at 7:00
  • $\begingroup$ @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. $\endgroup$ Commented Jul 27, 2017 at 7:11

Your Answer

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

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