23
$\begingroup$

I read an article about password schemes that makes two seemingly conflicting claims:

MD5 is broken; it’s too slow to use as a general purpose hash; etc

The problem is that MD5 is fast

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.

However, I was under the impression that MD5 still can be used as a non-cryptgraphic hash function:

  1. Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.
  2. Finding duplicate files. By MD5-summing all files in a directory structure it's easy to find identical hashes. The seemingly identical files can then be compared in full to check if they are really identical. Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5. (In a way, this would be creating a rainbow table where all the files are the dictionary)

There are checksums of course, but from my experience, the likelihood of finding two different files with the same MD5 hash is very low as long as we can rule out foul play.

When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash. But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"? Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

$\endgroup$
  • 5
    $\begingroup$ The collision attack is the problem, however, MD5 still has pre-image resistance. $\endgroup$ – kelalaka Apr 25 at 8:39
  • 3
    $\begingroup$ "Using SHA512 would make the process slower ..." - On my system, openssl speed reports 747MB/s for MD5, and 738MB/s for SHA-512, so that's barely a difference ;) $\endgroup$ – marcelm Apr 25 at 21:25
  • 2
    $\begingroup$ I believe MD5 can still be used as a PRF. $\endgroup$ – jww Apr 26 at 3:24
  • 1
    $\begingroup$ For longer files on amd64 processors with optimized implementations, I think SHA-512 is one of the faster hashing algorithms (faster than SHA-256 as the type sizes are easier to manipulate). $\endgroup$ – Nick T Apr 26 at 18:07
  • 1
    $\begingroup$ Fun fact: There's still a use for MD4 on millions of devices. The popular ext4 filesystem in Linux uses half-MD4 internally to generate a hash tree. I'm sure there are plenty of other uses too, even for MD5. $\endgroup$ – forest Apr 27 at 3:58
26
$\begingroup$

I know that MD5 should not be used for password hashing, and that it also should not be used for integrity checking of documents. There are way too many sources citing MD5 preimaging attacks and MD5s low computation time.

There is no published preimage attack on MD5 that is cheaper than a generic attack on any 128-bit hash function. But you shouldn't rely on that alone when making security decisions, because cryptography is tricky and adversaries are clever and resourceful and can find ways around it!

  1. Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.

The question of whether to publish known-good vs. known-bad hashes after a compromise is addressed elsewhere—in brief, there's not much that publishing known-bad hashes accomplishes, and according to the citation, Linux Mint published known-good, not known-bad, hashes. So what security do you get from known-good MD5 hashes?

There are two issues here:

  1. If you got the MD5 hash from the same source as the ISO image, there's nothing that would prevent an adversary from replacing both the MD5 hash and the ISO image.

    To prevent this, you and the Linux Mint curators need two channels: one for the hashes which can't be compromised (but need only have very low bandwidth), and another for the ISO image (which needs high bandwidth) on which you can then use the MD5 hash in an attempt to detect compromise.

    There's another way to prevent this: Instead of using the uncompromised channel for the hash of every ISO image over and over again as time goes on—which means more and more opportunities for an attacker to subvert it—use it once initially for a public key, which is then used to sign the ISO images; then there's only one opportunity for an attacker to subvert the public key channel.

  2. Collision attacks may still be a vector in cases like this. Consider the following scenario:

    • I am an evil developer. I write two software packages, whose distributions collide under MD5. One of the packages is benign and will survive review and audit. The other one will surreptitiously replace your family photo album by erotic photographs of sushi.
    • The Linux Mint curators carefully scrutinize and audit everything they publish in their package repository and publish the MD5 hashes of what they have audited in a public place that I can't compromise.
    • The Linux Mint curators cavalierly administer the package distributions in their package repository, under the false impression that the published MD5 hashes will protect users.

    In this scenario, I can replace the benign package by the erotic sushi package, pass the MD5 verification with flying colors, and give you a nasty—and luscious—surprise when you try to look up photos of that old hiking trip you took your kids on.

  1. Finding duplicate files. By MD5-summing all files in a directory structure it's easy to find identical hashes. The seemingly identical files can then be compared in full to check if they are really identical. Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5.

When I put my benign software package and my erotic sushi package, which collide under MD5, in your directory, your duplicate-detection script will initially think they are duplicates. In this case, you absolutely must compare the files in full. But there are much better ways to do this!

  • If you use SHA-512, you can safely skip the comparison step. Same if you use BLAKE2b, which can be even faster than MD5.

  • You could even use MD5 safely for this if you use it as HMAC-MD5 under a uniform random key, and safely skip the comparison step. HMAC-MD5 does not seem to be broken, as a pseudorandom function family—so it's probably fine for security, up to the birthday bound, but there are better faster PRFs like keyed BLAKE2 that won't raise any auditors' eyebrows.

  • Even better, you can choose a random key and hash the files with a universal hash under the key, like Poly1305. This is many times faster than MD5 or BLAKE2b, and the probability of a collision between any two files is less than $1/2^{100}$, so the probability of collision among $n$ files is less than $\binom n 2 2^{-100}$ and thus you can still safely skip the comparison step until you have quadrillions of files.

  • You could also just use a cheap checksum like a CRC with a fixed polynomial. This will be the fastest of the options—far and away faster than MD5—but unlike the previous options you still absolutely must compare the files in full.

So, is MD5 safe for finding candidate duplicates to verify, if you subsequently compare the files bit by bit in full? Yes. So is the constant zero function.

(In a way, this would be creating a rainbow table where all the files are the dictionary)

This is not a rainbow table. A rainbow table is a specific technique for precomputing a random walk over a space of, say, passwords, via, say, MD5 hashes, in a way that saves effort trying to find MD5 preimages for hashes that aren't necessarily in your table in the first place, or doing it in parallel to speed up a multi-target search. It is not simply a list of precomputed hashes on a dictionary of inputs.

(The blog post by tptacek that you cited, and the blog post by Jeff Atwood that it was a response to, are both confused about what rainbow tables are.)

When the password scheme article states that "MD5 is fast", it clearly refers to the problem that hashing MD5 is too cheap when it comes to hashing a large amount of passwords to find the reverse of a hash. But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"? Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

I don't know what tptacek meant—you could email and ask—but if I had to guess, I would guess this meant it's awfully slow for things like hash tables, where you would truncate MD5 to a few bits to determine an index into an array of buckets or an open-addressing array.

$\endgroup$
  • $\begingroup$ Why does selecting a different hash algorithm eliminate the risk of collisions (sushi bullet)? $\endgroup$ – chrylis Apr 25 at 18:09
  • $\begingroup$ @chrylis Nobody has ever published any way to find SHA-512 or BLAKE2b collisions, nor even, say, SHA-256 collisions. $\endgroup$ – Squeamish Ossifrage Apr 25 at 19:19
  • 1
    $\begingroup$ @Alexander ‘Hash function’ means many things, and is usually some approximation to a uniform random choice of function in some context (random oracle model, pseudorandom function family, pseudorandom permutation family, etc.). A ‘checksum’ is used for some error-detecting capability; e.g., a well-designed 32-bit CRC is guaranteed to detect any 1-bit errors and usually guarantees detecting some larger number of bit errors in certain data word sizes, while a 32-bit truncation of SHA-256 might fail to detect some 1-bit errors. The terms are generally used quite loosely, however. $\endgroup$ – Squeamish Ossifrage Apr 25 at 19:28
  • 1
    $\begingroup$ @SqueamishOssifrage "CRC is guaranteed to detect any 1-bit errors and usually guarantees detecting some larger number of bit errors in certain data word sizes, while a 32-bit truncation of SHA-256 might fail to detect some 1-bit errors. " woah. That's really powerful, and really cool. I didn't know that. I'll read more into it! $\endgroup$ – Alexander Apr 25 at 19:36
  • 2
    $\begingroup$ I think you misunderstood the Linux Mint case. They published the MD5 hash of the infected ISO after they recovered from the hack, so that people can check whether the ISO they installed from was infected. Your sushi story seems to imply that you thought MD5 was used to prove the integrity of the original uninfected ISO file. This was not the case. $\endgroup$ – jornane Apr 25 at 21:14
9
$\begingroup$

But what does it mean when it says that "[MD5 is] too slow to use as a general purpose hash"? Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

BLAKE2 is faster than MD5 and currently known to provide 64-bit collision resistence when truncated to the same size as MD5 (compare ~30 of that of MD5).

$\endgroup$
6
$\begingroup$

There's not a compelling reason to use MD5; however, there are some embedded systems with a MD5 core that was used as a stream verifier. In those systems, MD5 is still used. They are moving to BLAKE2 because it's smaller in silicon, and it has the benefit of being faster than MD5 in general.

The reason that MD5 started fall out of favor with hardware people was that the word reordering of the MD5 message expansions seems to be simple, but actually they require a lot of circuits for demultiplexing and interconnect, and the hardware efficiencies are greatly degraded compared to BLAKE. In contrast, the message expansion blocks for BLAKE algorithms can be efficiently implemented as simple feedback shift registers.

The BLAKE team did a nice job of making it work well on silicon and in instructions.

edit: SHA-1, SHA-2, etc also look pretty nice in circuits.

$\endgroup$
  • $\begingroup$ I did not know about BLAKE, this seems interesting. I assumed from the post that there would be some hashing system that would not be cryptographically secure to be faster that MD5, but it seems BLAKE has managed to be the best of both worlds. I’m considering this answer as the accepted one, but I’ll wait a few days while there is activity around this question. $\endgroup$ – jornane Apr 25 at 21:28
  • $\begingroup$ @jornane Squeamish Ossifrage has a better answer. I just wanted to mention the hardware side of things. $\endgroup$ – b degnan Apr 26 at 0:23
2
$\begingroup$

I know that MD5 should not be used for password hashing

Indeed. However, that's about the direct applicability of MD5 to a password or to use it with just a password and salt. In that case MD5 is less secure than a dedicated password hash with a work factor, at least for common passwords and pass phrases.

However, the use of MD5 within a PRF (HMAC) and within a password hash is still OK as it relies on pre-image resistance for security, rather than collision resistance.

I'd rather not bet that MD5 stays secure for pre-image resistance though. Attacks only get better and although I don't see any progress on breaking MD5's pre-image resistance, I would not rule it out either.

Identifying malicious files, such as when Linux Mint's download servers were compromised and an ISO file was replaced by a malicious one; in this case you want to be sure that your file doesn't match; collision attacks aren't a vector here.

MD5 is still secure to check hashes from another server as long as hackers cannot alter the input of the MD5 hash. However, for something like a full ISO, I'd say that they would have plenty of opportunity bringing in binary files that seem innocent with regard to contents, while they alter the intermediate state of MD5 vulnerable to collision attacks.

That was not the attack that you referred to; in that case the MD5 hash on the official server was different from the one calculated over the ISO image.

But attack on file distribution do rely on collision resistance, and this kind of use case can definitely be attacked. It would probably not be all that easy (correctly lining up the binary data required for the attack at the start of the ISO and such), but it is a vector of attack none-the-less.

The same goes for SHA-1 in Git by the way. Not easy to breach, but far from impossible, whatever Linus says.

Finding duplicate files. By MD5-summing all files in a directory structure it's easy to find identical hashes. The seemingly identical files can then be compared in full to check if they are really identical. Using SHA512 would make the process slower, and since we compare files in full anyway there is no risk in a potential false positive from MD5. (In a way, this would be creating a rainbow table where all the files are the dictionary)

Sure, if there is no possibility of attack or if you compare the files fully anyway then MD5 is fine.

However, if there is a vector of attack then you need to perform a full binary compare even after the hash has matched. Otherwise an attacker could make you retrieve the wrong deduplicated file. If you'd use a cryptographically strong hash then you would not have to perform the full file comparison at all. As others have noticed, a 256-512 bit hash is a lot easier to handle than performing a full file compare when storing. Passing over the file twice is not very fast either; all the speed advantages of MD5 are very likely nullified by the I/O required.

Besides that, if you would reference it using the hash then there is no comparison to be made; you would only have a single file (this is about deduplication after all).

"[MD5 is] too slow to use as a general purpose hash"? Are there faster standardized hashes to compare files, that still have a reasonably low chance of collision?

Others have already mentioned keyed hashes (Message Authentication Codes) and non-crypto hashes, and one or two really fast crypto hashes that are more secure and usually as fast as MD5. But yes, as cryptographic hashes go, MD5 is certainly rather fast. That's mainly because it is uncomplicated and because it has a small state / output size.

As we found out, MD5 is so uncomplicated that it could be broken. Other algorithms such as SHA-256 and -512 largely rely on the same principles but are still deemed secure. Note that newer Intel and AMD processors have SHA-256 acceleration, so it is likely that they would perform similarly to MD5 if the hardware acceleration is indeed used.


As you can see, MD5 is almost never is a good idea, and many (smart) people still believe MD5 or SHA-1 to be secure under "their specific circumstances". They can often be proven wrong and leave the door open for (future) attacks on the system. I'd try to avoid it under any circumstances, especially if it is not used within HMAC.

What I also see is that it is defended because a system cannot be upgraded. MD5 has been under attack for years and years. If you still cannot migrate away from MD5 then there is something seriously wrong with the security of your system that transcends the use of MD5. If you're designing / programming or keeping systems without upgrade path then you're the main security hazard, not the hash algorithm.

$\endgroup$
  • $\begingroup$ There's no modern password hash that uses MD5. One could instantiate PBKDF2 with HMAC-MD5, but I'm not sure I've ever seen anyone do that, and if one is making a custom choice to begin with, one might as well choose a modern password hash! $\endgroup$ – Squeamish Ossifrage Apr 26 at 23:28
  • 2
    $\begingroup$ I'm very prolific on SO, I've seen it plenty of times. People know MD5 and for some reason like to use it. $\endgroup$ – Maarten Bodewes Apr 26 at 23:42
  • 1
    $\begingroup$ > MD5 is still secure to check hashes from another server as long as hackers cannot alter the input of the MD5 hash. $$$$ This requires very careful qualification. The issue about how much control an attacker might have over the input is extremely subtle and not obvious if you're not very familiar with cryptography. See the story at crypto.stackexchange.com/a/70057 where the attacker doesn't change anything at the time the initial compromise is detected but still compromises everyone in the end even if they verify the good MD5 hashes. $\endgroup$ – Squeamish Ossifrage Apr 26 at 23:43
  • $\begingroup$ Well, that was kind of the point of my answer, you think you're secure, but you're not. What you posted is an interesting attack vector, but it still relies on the adversary (or one of his companions, same thing in a theoretic sense) to control the input of the hash. $\endgroup$ – Maarten Bodewes Apr 26 at 23:47
2
$\begingroup$

MD5 is currently used throughout the world both at home and in the enterprise. It's the file change mechanism within *nix's rsync if you opt for something other than changed timestamp detection. It's used for backup, archiving and file transfer between in-house systems. Even between enterprises over VPNs.

Your comment that it "should not be used for integrity checking of documents" is interesting, as that's kinda what is done when transferring files (aka documents). A hacked file/document is philosophically a changed file/document. If on a source system an attacker changes a document in a smart way to produce the same MD5 hash, it will not propagate onward to the target system as the document has not changed in rsync's eyes. As colliding hashes can be found quickly now, a carefully made change can go unnoticed by rsync, and (niche) attacks can occur.

So if you ask "Is there really no use for MD5 anymore?", an answer is that it's in current and widespread use at home and in the enterprise.

In rsync's case, swapping out MD5 to something faster would only produce marginal overall speed improvement given storage and networking overheads. It would certainly be less than the simple ratio of hash rates suggests.

$\endgroup$
  • 1
    $\begingroup$ I think librsync actually uses BLAKE2 now. $\endgroup$ – forest Apr 26 at 1:30
  • $\begingroup$ BLAKE2b is 512, BLAKE2s is 256. It can be truncated though, of course. $\endgroup$ – forest Apr 26 at 2:20
  • $\begingroup$ @forest Well you sound convincing, though man pages say MD5 and the hash is 32 hex characters. What would be the reason for truncation? $\endgroup$ – Paul Uszak Apr 26 at 2:39
  • 1
    $\begingroup$ @forest All that codey stuff sounds hard, but I think that if (protocol_version >= 30) return CSUM_MD5; in download.samba.org/pub/unpacked/rsync/checksum.c calls download.samba.org/pub/unpacked/rsync/lib/md5.c. It seems to be self contained. Perhaps you have a different version of rsync? Even if not, any changes must be pretty recent so there'll still be a lot of MD5 out there... $\endgroup$ – Paul Uszak Apr 26 at 2:48
  • 1
    $\begingroup$ I was linking to librsync, which provides the backend. $\endgroup$ – forest Apr 26 at 2:50
1
$\begingroup$

A case where the use of the MD5-hash would still make sense (and low risk of deleting duplicated files):

If you want to find duplicate files you can just use CRC32.

As soon as two files return the same CRC32-hash you recompute the files with MD5 hash. If the MD5 hash is again identical for both files then you know that the files are duplicates.


In a case of high risk by deleting files:

You want the process to be fast: Instead use a hash function that's not vulnerable for a second hash of the files, i.e. SHA2 or SHA3. It's extremely unlikely that these hashes would return an identical hash.

Speed is no concern: Compare the files byte per byte.

$\endgroup$
1
$\begingroup$

If you don't care about intentional attacks on the hash, then you don't need a cryptographic hash at all. There are some algorithms that are very, very fast and provide excellent collision resistance for most, data, but not for intentional attacks. Take a look at xxhash.

$\endgroup$
-1
$\begingroup$

One of the things not mentioned here, is that the attraction of hashing algorithms, (like programming languages etc) is ubiquity. The 'reason' for using MD5 is:

  • everyone knows about it
  • it's implemented for pretty much every combination of architectures, OSs, programming languages etc
  • it's limitations are well understood.

This is important both from a practicality and security point of view. It reasonable to expect someone to be able to handle it (practicality) and it helps devs audit the process and not skip steps because they are 'tricky' (security).

All that said, SHA is catching up and I think in time MD5 will die out, and when it does so, it will be quite quickly. Because its only a self-fulfilling-prophecy that it is popular in the first place, as there are normally better choices.

However, in the intervening time, that its widely adopted may well be a good reason in it own right to use MD5 (within it's limits).

$\endgroup$
  • $\begingroup$ Welcome to crypto.stackexchange - I think there are some additions that would improve this answer: It seems like the bullet points are equally applicable to SHA1/SHA2 (considering that they're standardized algorithms). It is clear why those points would promote the use of an algorithm, but it's not clear to me why they would promote the use of MD5 over SHA1/SHA2. The last point seems to say that "everyone else is doing it" is a good enough reason to use MD5 (which is seldom a good reason to do anything). It also mentions limits, but does not elaborate on what those limits should be. $\endgroup$ – Ella Rose Apr 26 at 14:51
  • 4
    $\begingroup$ Use of MD5 has been questionable for a quarter of a century since Hans Dobbertin published collisions in the compression function in 1996, and MD5 has been completely broken for a decade and a half since Xiaoyun Wang's team demonstrated collisions in 2004. Collisions in MD5 were exploited in practice by the United States and Israel to sabotage Iran's nuclear program. SHA-2 has been available since 2002, seventeen years. Note SHA-0 and SHA-1 are broken too; timeline. $$$$ The Caesar cipher meets all your criteria too. $\endgroup$ – Squeamish Ossifrage Apr 26 at 15:19
  • 1
    $\begingroup$ Just too be clear: I don't think MD5 is better than SHA-2 (or good). The question was not 'which is better' but is there any reason to use MD5. Sure, the 17 years that SHA-2 has had to take over and is widely enough used that it's a good choice. Especially if you're the internet connected windows/linux space. If that's where you are and there's no special cases then don't use MD5 there are better alternatives. But that wan not the question. It take a while to become trusted and some tech stacks move a lot less rapidly. Sometimes 17 years isn't that long. $\endgroup$ – ANone Apr 26 at 15:43
  • 1
    $\begingroup$ If someone is (a) actually designing a protocol (b) constrained to a specific, real environment that is (c) limited to MD5 in that environment for specific technical reasons that can be articulated, then they can ask a question in which we give useful guidance for security. That's not the case here: the original poster is asking about convenience, about an ad hoc vulnerability disclosure on highly capable computers that can easily use SHA-2, about cheap ways to keep collision probabilities low, etc. $\endgroup$ – Squeamish Ossifrage Apr 26 at 15:49
  • 1
    $\begingroup$ @SqueamishOssifrage Sure but that wasn't the question. Also if your looking for hashing advice and your research is: Read one crypto.stackexchange Q/A titled: "Is there really no use for MD5 anymore?", scroll past most of the answers that say 'dont do it' and get to the one that says "well for completeness's sake: maybe", and take that to mean MD5 for the win... On that note, there'd be fewer of those hackernews posts if there wasn't a legit argument to say people had been overly negative. I think honesty about its weakness is better than scaring people away. $\endgroup$ – ANone Apr 26 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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