2
$\begingroup$

One thing I see a lot on InfoSec Exchange is this phrase -

MD5 is weak against collisions

but what I am failing to understand is why.

Why specifically is MD5 weak to collisions? I understand the concept of a collision attack (at least I think I do) so perhaps this question appears stupid in that case, but what is it specifically which makes MD5 so prone to collisions? Are there any other "common" hashing functions which suffer from the same issue? And to what extent do they suffer this issue?

Would I be correct in assuming speed has something to do with this?


TL;DR: On an overview / high-level, how do the collision attacks against MD5 work and why don't they apply to other algorithms?

$\endgroup$
2
  • $\begingroup$ While not an answer, I'd hope that this paper (PDF) can serve as the basis for an answer, found via fgrieu's answer. $\endgroup$
    – SEJPM
    Commented May 24, 2018 at 13:55
  • $\begingroup$ @SEJPM Thank you, I will definitely take the time to give all this a read. $\endgroup$
    – user58434
    Commented May 24, 2018 at 13:56

1 Answer 1

4
$\begingroup$

We know techniques for cheaply computing collisions in MD2, MD4, SHA-0, and, of course, MD5.

The first cheaper-than-generic technique for computing MD5 collisions was published by Hans Dobbertin in 1996; then a collision in MD5, computed in a few hours on an IBM p690, was published by Xiaoyun Wang, Dengguo Feng, Xuejia Lai and Hongbo Yu in 2004, and the technique explained in a followup paper in 2005 (some details on the history); an independently developed technique was used in an international incident of industrial sabotage by the United States and Israel against Iran; and the techniques for computing MD5 collisions have since improved nearly to the point of being a parlor trick.

We also know a technique for computing collisions in SHA-1 much more cheaply than a generic collision search on a 160-bit hash function. It is nowhere near as cheap as MD5—it cost about $2^{64}$ evaluations of SHA-1, whereas a generic collision search costs $2^{80}$ evaluations of the hash function, and the current best known MD5 collision search by Tao Xie, Fanbao Liu, and Dengguo Feng costs only $2^{18}$ MD5 evaluations. But it has been executed to find SHA-1 collisions, and for Merkle–Dåmgard hash functions like MD5 and SHA-1, one collision of equal-length messages can be trivially extended into many, so knowing one SHA-1 collision is enough to get you in trouble!

We don't know any techniques for finding collisions with reasonable cost in SHA-2, SHA-3, any of the SHA-3 finalists, BLAKE2, or various hash functions of lesser import.

Many crypanalysts have tried, and failed, to figure out techniques for finding collisions in these. Any hash function widely used by many applications, especially financial or political applications, will be subjected to scrutiny because of its high value. It's possible that a spook or crook who found an attack might choose not to publish it, of course! The SHA-3 competition subjected a number of candidates to years of scrutiny by the world's top public academic cryptanalysts, compiled at the SHA-3 zoo, so that we have some confidence in them to resist collisions.

We also don't consider any hash functions with small outputs, e.g. less than (say) 192-bit, to be collision-resistant because the cost of generic collision searches, counted in number of evaluations of the hash function, is small enough to be within the realm of feasibility for humanity to execute.

To put the number in perspective, the Bitcoin network today performs about $30 \times 10^{18}$ SHA-256 computations every second, about $2^{64}$ per second or $2^{90}$ per year. A generic collision search on a 192-bit hash function would cost an expected $2^{96}$ evaluations. That's not cheap, but it's imaginable.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer - sorry to be a "pain" but I assume you when you say "cheap" you're referring to computation? Does that mean that my assumption of speed is correct or at least in part a factor? $\endgroup$
    – user58434
    Commented May 24, 2018 at 17:25
  • 1
    $\begingroup$ @JoshJones It is a factor, but in many attacks you have a wide latitude to trade off time and space. Say you could compute MD5 in one nanosecond (which would be amazing, but let's suspend our disbelief for a moment). A single CPU core could find a collision by generic search in half a millennium, but you don't have to wait that long: buy five hundred CPU cores and you'll have an answer in a year. However, the energy or euro cost of the two is comparable (ignoring the inevitable long-term extinction of sentient life on earth by humanity's imminent roasting of the planet). $\endgroup$ Commented May 24, 2018 at 17:31
  • $\begingroup$ Damn, $2^{64}$ per second? $\endgroup$
    – forest
    Commented May 28, 2018 at 1:33

Your Answer

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