The Curious Case of MD5 (opens in new tab)

The unsatisfying answer to this is probably that it just doesn't matter. It's not as if evidence chain of custody is assured cryptographically; it's assured by rules and regulations and an adversarial system. If you tried to submit as evidence a forged document vouchsafed with a colliding MD5 hash, you'd be putting your own freedom at risk, because the forgery will be straightforwardly detectable (the real document won't have hash colliding artifacts in it).

None of this is to say that the legal profession shouldn't move to SHA2; it should.

If you could just throw anyone who forged a digital signature in prison, you'd keep using MD5, too.

The reason why people like us keep changing everything for security is specifically because we have no access to justice. Computer crimes are international and difficult to prosecute, so you might as well drop an algorithm like a hot potato if anyone - even just nation state actors - could break it. We build our rules out of code because we do not have access to the material they make laws out of.

That being said, continuing to use MD5 is utterly inexcusable.

The article mentions the key detail: MD5 is broken for cryptography (collisions) but not for second preimage attacks. I was hoping there would be some discussion of just how much more difficult the latter is. It is extremely difficult.

Let’s ignore that no second preimage attack is currently known for MD5. The software the author links to has a FAQ that links to a paper that lays out the second preimage complexity for MD4:

https://who.paris.inria.fr/Gaetan.Leurent/files/MD4_FSE08.pd...

It takes 2^102 hashes to brute force this for MD4, which is weaker than MD5. A bitcoin Antminer K7 will set you back $2,000, and it gets 58 TH/s for sha256, which is slower than MD5 or MD4. Let’s ignore that MD5 is more complex than MD4, and let’s say conservatively that similar hardware might be twice as fast for MD5 (SHA256 is really only 20-30% slower on a cpu). It’ll take 2^102/58e12/2/60/60/24/365, or about 1.4 billion years to do a second preimage attack with current hardware. So you could do that 3 times before the sun dies.

If you want to reduce that to 1.4 years, you could maybe buy a billion K7’s for $2 trillion. And each requires 2.8kW so you’ll need to find 2.8 terawatts somewhere. That’s 34 trillion kWh for 1.4 years. US yearly energy consumption is 4 trillion kWh.

It will be a while, probably decades or more, before there’s a tractable second preimage attack here.

Yes, there are stronger hashes out there than MD5, but for file verification (which is what it’s being used for) it’s fine. Safe, even. The legal folks should probably switch someday, and it’ll probably be convenient to do so since many crypto libraries won’t even let you use MD5 unless you pass a “not for security” argument.

But there’s no crisis. They can take their time.

Another unfortunately place where MD5 is widely used: pirate libraries such as Library Genesis and Anna's Archive. While content is distributed at large in torrents with SHA1-summed shards, and Anna's Archive at least offers some structured metadata which would allow to slowly migrate away from MD5, files are still indexed using MD5 as primary key, and any other kind of file hash is nowhere to be found.

Pirate libraries are particularly important to preserve our cultural heritage in a transparent and trustworthy way. A role that traditional libraries sadly cannot fulfill due to draconian copyright laws, especially around digital books. With archive.org as notable exception.

I actually picked SHA256 for the path-prefix feature in https://jacob.jkrall.net/benfords-law for “NIST compliance.” That is, I didn’t ever want to answer “yes” to a potential customer’s CISO security surveys question like “does your application use any non-NIST-approved hashing functions?”

It’s frankly broken that evidence-handling doesn’t have to follow the government's advice about hash function selection!

I still use MD5 as a 128-bit checksum algorithm that is fast and universally supported and compatible everywhere. In this role it's still useful, just don't expect it to be a cryptographic hash anymore.

There's a difference between finding a collision and finding a second pre-image. While I agree you shouldn't use MD5, and absolutely don't use a signature algorithm which uses it, finding a second pre-image is harder than finding an arbitrary collision with MD5.

An "arbitrary collision" here means you can find two inputs (pre-images) which hash to the same thing. Like you ran some code and discovered that "SDFKLHKLJxchjasdfgklhjaskdhjlf9" hashed to the same thing as "klhkasdfhjkl899078790". Finding a second pre-image means you start with one message, like "ALL QUIET. REMAIN CALM." and figured out that "ATTACK AT DAWN 051928" hashes to the same MIC.

I can't believe I'm defending using MD5. But... finding second pre-images is still hard. Sasaki & Aoki say it's got a complexity of around 2^116.9 and requires 11 * 2^45 words of memory (thought 1400Tb isn't THAT outlandish these days.)

Still... statements like "finding a second pre-image is hard" don't age well and will guarantee a tractable second pre-image attack will be published tomorrow.

But... if you have a bunch of docs and you're not signing them or asking people to trust the hash of each doc, you can (reasonably) quickly de-dup by sorting by MD5 hash and then looking for dups. Which is how many people use MD5. And they continue using MD5 because multiple organizations have similar lists and if you wanted to change it, you would need to get everyone to move to a different algorithm.

But yeah... at this point we should assume someone will publish a tractable second pre-image attack "any day now" and get to work migrating from MD5 to MD5 : Next Generation. But good luck getting more than 2 people to agree to what the next preferred hash algorithm should be.

We still see heavy use of MD5 in genomics as well. It's effectively used to generate a single identifier that can be used to reference a specific genome assembly. There have been discussions and attempts to move to other, more secure algorithms, but the community and its tooling is too deeply entrenched in using the MD5 for the reference that it would take a herculean effort to change.

I'm personally of the opinion that it doesn't matter. MD5 is fine for genomics. The chances of valid genome files colliding is still extremely low, and there's not really any relevant attack space. Replacing one assembly file with another will just break someone's analysis pipeline, and most likely in a very clear obvious way.

Sigh, been having this conversation in a related codebase. Md5 is just as fine as any other generic hash function if its being used as a non-unique key, which for many cases replacing it with one of the more "secure" alternatives does nothing except for the fact that the resulting hashes are frequently longer, thereby further reducing the statistical chance of an accidental collision. For something like a document store, duplication system, etc, simply taking the extra step of doing a binary comparison against the text associated with the hash assures that accidental (or intentional) collisions are handled. With the bonus that you probably get to either publish a paper or detect someone trying to attack the system should the text comparison fail.

And given the history of cryptographic hashes, i'm even more convinced that anyone depending on sha3/whatever being better than md5/etc over the next 10-20 years is fooling themselves.

Now would I use it in a secure boot chain/etc as a stamp of uniqueness? Probably not.

> MD5 should be considered broken and unsuitable for further use.

Ya know... It's 2024 and Azure's blob storage ONLY supports MD5 for integrity checks when writing blobs. There are no other hash functions supported there. The default cloud storage solution implemented by one of the largest cloud providers out there ONLY uses MD5.

I really want to use something else, but whenever I have to interact with them I must fall back to MD5. It's not up to me as a dev to use something better if I need to interact with Azure. Yes, I can use other hashes alongside MD5, but if I want integrity checks with the storage provider I can't completely abandon MD5.

The history of this makes it hard to convince people to supersede hashes based on the fact that they can be collided. If the legal community had switched to SHA-1 at the point that MD5 was found to be weak for collisions they would have had to consider switching over to SHA-2 10 years later. From their perspective they dodged a bullet.

There ends up being a usability issue here. An MD5 hash is only 128 bits long. So 32 hex digits. A SHA-2 hash is going to be 256 bits. Or 64 hex digits. Manually comparing 64 hex digits is in practice much harder than twice as hard as comparing 32 hex digits. People get lost in the middle. If you chop down your 256 bit hash to 128 bits then due to birthday collisions you can probably brute force a collision anyway (you end up only having to do something like 2^64 operations). So there ends up being a usability argument for specifying that your system has to be able to be secure in the face of collisions. At that point you could then further argue that you will just stick with MD5.

This is the same legal system that still uses polygraphs as “lie defectors” and known-junk DNA matching tests as fact, so this isn’t exactly shocking.

I can see the lawyers’ point. Any old checksum is good enough for spotting random data corruption. If you do happen to have a crooked lawyer who is submitting tampered evidence then you would hope that there are better systems in place to weed out this ethical corruption.

For instance: law school training to strengthen ethics, well known punishments to act as a deterrent, hiring processes to filter out unscrupulous actors, and whistleblower protections to encourage and reward vigilance.

It’s not an opinion that adheres to the cynical zeitgeist, but in my experience most members of this profession are extremely trustworthy. I’m sure they dislike the stereotype of lawyer=rotter just as much as hackers are tired of being typecast as Newman… sorry, Dennis from Jurassic Park!

“A cryptographic hash should uniquely identify a file.”

This is not true. It’s not possible to guarantee this. One can be certain that two files DON’T match if they have different hashes, but one cannot be certain that two files DO match based ONLY on the fact that they have the same hash.

MD5 is incredibly broken. The PDF file PoC||GTFO 0x14 (https://dl.packetstormsecurity.net/mag/pocgtfo/pocorgtfo14.p..., 42MB large) is a PDF file that can be also run in a NES emulator, and will display its own MD5 hash. The MD5 hash is also shown in the pdf document itself. (Don't download it from archive.org, their copy is altered)

The fact that any document can contain its own MD5 hash embedded in there should be hugely concerning enough.

The hash also happens to start with 5EAF00D.

> Yes, they say, MD5 is broken for encryption, but since they’re not doing encryption, it’s fine for them to use it.

Unless I missed it, this article seems to not refute the most fundamental point: MD5 was never broken for encryption. Hashing is not encryption.

> only broken for encryption

It's broken in an adversarial situation: given the hash of evidence-file A, it's possible to construct a file B that gives the same hash.

But it would be a different matter entirely to construct a file B that actually looked like a file of evidence relevant to the case. I don't know how lawyers use these hashes, but unless they're being used to detect malicious tampering, I don't see what's wrong with MD5. And since the files to be hashed are evidence, they're in the custody of a court; things have got quite bad if court officials might be tampering with evidence.

I've been wondering, is there a term for a type of attack like this:

Given a message M, length function L(), and MD5 hash function H(); is there an attack which can generate message M', such that H(M)==H(M') _and_ L(M)==L(M')?

In other words: Two different messages, both of the same length, with the same hash?

It's almost like a chosen prefix collision attack, but with no prefix (so P is empty) and a given message (M is known, M' is up to the attacker).

I ask because I frequently use GridFTP for data transfer, and it uses both the file length and the MD5 has to verify that files were transferred correctly.

Despite official statements about MD5, the leading e-discovery software provider uses sha256: https://help.relativity.com/9.0/Content/Relativity/Processin....

And it is unclear if that is in any way unusual.

MD5 hashes are half the length of the recommended hashing algorithms. This convenience (and the switching cost) is worth more than the theoretical security considerations.

In other industries, MD5 collision is the most minor problem, it just works, and God know when/how they encounter collision, so just use it.

I've always wondered what would happen if some black hat made all their payloads have the same hash in the hopes that if it ever went to court the confusion would hinder the proceedings.

Like i get that md5 is essentially a unique identifier and not meant to protect against malicious interference but if all the exhibits had the same identifier surely that would confuse people.

I worked for years as the tech guy for a document imaging company. We worked a few gigs for the Serious Fraud Office in the UK. So, while I'm not a lawyer, I bumped into this stuff a fair bit.

The point is that evidence is an agreement between the two sides in a case, and it's not an absolute thing.

If you have the original document that was signed by both parties, great. If you have a scan (using a lossless compression format) of the document and proof that the original was destroyed, great. If you have a scan but no proof of destruction, still great. If you have a photograph of the document and no proof, still great. If you have a vague recollection of what was in the document, still great. All of these are "great" if the other side accepts that they are accurate depictions of the original. If they don't accept that, then there's an argument about what the original document contained and the provenance of the evidence, and only then does the actual quality matter. Original document with wet signature is hard to argue with (but not impossible - wet signatures can be forged). The further away from that, the easier it is to argue that the document presented is not accurate and should not be accepted as evidence.

Knowing that it's possible to use collisions to create false evidence doesn't matter if no-one contests that the evidence is false. It only becomes significant if one side says that the document has been tampered with, and that's not that common. The side claiming it was tampered with would have to present their version of the document, and their version of events that allowed the document to be tampered with, and so on. The judge would make a ruling about which version of the document was considered the "real" one and the case would continue. Obviously there are edge cases where the whole trial verdict hinges on which version of the document is the correct one, but they're edge cases. And in those cases you could-re-hash the documents involved and double-check with one was right, etc.

In the OP's example, where a letter of recommendation has the same hash as a authorisation letter, this is only going to matter if one side says the accused was authorised and the other says they weren't. The authorisation letter will be produced by one side, and the recommendation letter produced by the other, and there'll be an argument about which was the original document. The fact that they have the same hash isn't really relevant. It's a minor point of interest given that these are two clearly different documents saying different things.

In the specific cases for the SFO that I worked on, the SFO descended on the accused's offices like locusts, sweeping every single document into carefully numbered bags. We scanned the documents in secure facilities, stored the originals in secure facilities, stored the resulting images in secure storage, and deleted any cache or copies. My professional opinion is that it would be impossible for anyone to create two documents prior to the SFO's investigation that would create an intentional MD5 collision in the evidence used in court. And, even if they somehow did, it wouldn't matter because both documents would be in evidence bags in storage and could be recovered to be examined by the court.

Obviously, from a black/white technical point of view, using a better hash algorithm would be better. But I can see why the legal profession is reluctant to adopt the new thing; it's a hassle and it will only affect a tiny amount of cases, if any.

Interestingly, use of MD5 has been been found in court to make evidence less convincing. https://www.schneier.com/blog/archives/2005/08/the_md5_defen...

To the article, what tptacek said.

This is actually something I discussed with my legal team and was prepared to bring up at trial with our own forensic expert. My team was (correctly, IMO) not expecting much to happen because the amount of precedent that exists with MD5 being used as a way to say these documents haven't been swapped or tampered.

It's worth noting that there are no known attacks against MD5 HMACs, which look identical to MD5 hashes.

Interestingly, DBT is still using MD5 as the default algorithm for generating row identifiers.

I read through this hoping to have a reasonable discussion of the difference between preimage attacks (see https://en.m.wikipedia.org/wiki/Preimage_attack) and was disappointed when I did not see the topic mentioned once. :(

It is much more computationally feasible to create two inputs from scratch that hash to the same value than to forge an existing documents hash (the threat model I’m assuming they’re discussing in relation to the law).

As far as I know I am not aware of a demonstrated second preimage attack on md5. Not saying to keep using it, just trying to not spread fud.

Edit: I do see second preimage is mentioned about 3/4 of the way through the article. I confess that I did stop reading and started skimming before then.