Live data from Hacker News

The Curious Case of MD5

katelynsills.com

161–170 of 173 posts

Re: The Curious Case of MD5

#161

Earlier quoted context omitted.

How so?

Second preimage attacks are relevant for the documents that you create and give to others. Keeping a hash of the document ensures that you can prove that any altered document shown by someone else is not the original. Collision attacks are relevant for the documents created by others, which you receive. If you have a hash of the document that is collision-resistant, you can trust that the creator does not have other…

Again. A "collision" means you have two pre-images which hash to the same value, but you did not pick either of the two pre-images. So if someone gives you a doc that says "SDKLFHJSDJKLGHJKLb9iyasdfkghjasdf97897asdfg798789asd" and then gives you another doc that says "klhjasdfhjklasdfhjkl97879087908789sdfga" and they have the same hash, then... what has the attacker achieved other than proving they've found a collision.

A "second pre image" means they can give you a document like '{"status":"calm","launch_missiles":false}' and then later come up with another document like '{"status":"angry","launch_missiles":true,"whatever":"a9d7s8gh283g7d7"}' and both would have the same hash.

A critical part of using a hash function is understanding how it can be used. So if I was expecting a message to parse to a JSON blob and you gave me "SDKLFHJSDJKLGHJKLb9iyasdfkghjasdf97897asdfg798789asd", it doesn't matter what the second message's hash is, because you've given me two messages which can't be used.

In the use case you've given, it turns out courts don't look at hashes of messages, they look at messages. So a collision is of limited use for forensics.

In password hashing systems, if you could force someone to use the password "SDKLFHJSDJKLGHJKLb9iyasdfkghjasdf97897asdfg798789asd", you could come in later and use "klhjasdfhjklasdfhjkl97879087908789sdfga" to log in. But you should be pilloried for not using something like a PKCS#5 PBEKDF. If you used PBEKDF2 for instance, you would now be looking for a second pre-image of the salt prepended with the password. And again, second pre-images are harder than finding a collision.

I absolutely agree that a digital signature is only meaningful if it uses a collision and second-pre image resistant hash function. But that's not what we were talking about.

I'm also very happy that the knee-jerk response to MD5 is now "STOP IT BEFORE IT GETS TO THE CHILDREN." A decade ago I had a senior architect say it was okay to use MD5 in new systems because Bruce Schneier's 1996 "Applied Cryptography" said it was okay. I spent the next year moving that app from auth using straight MD5 of the password to an SRP based system.

Re: The Curious Case of MD5

#162

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…

A truncated SHA-256 is both more secure and also faster to compute on any modern CPU than MD5, and a visual comparison would work identically. If a visual comparison is believed necessary, it should better be made easier, e.g. by overwriting the two hash values, using text of different colors. Otherwise, even a bash script, or even just one bash command line can easily compare the output of two sha256sum executions a…

If you have some sort of information processing system available to compare hashes, then you would be better off comparing the data directly. The hashes when used in this context are primarily to make things like manual comparisons possible. Usability is the point.

Re: The Curious Case of MD5

#163
post #10

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 w…

It certainly does not matter. If you wanted to present a fake document as evidence, would sha-whatever help? Nope. If you wanted to withhold key evidence and pretend it didn’t exist, would it help? Nope.

And do you think we trust md5, or do you think we have another tool that can compare documents? We do have such tools.

What prevents chicanery in discovery and disclosure is how annoying it was to go to law school and pass the bar compared to how fun it would be to work at Wendy’s for the rest of our careers.

Should we use a better hash function: probably. Is this a problem of not enough technology literacy in the profession? Well, not really; there are plenty of tech literate lawyers (hi!) we just have questionable tools just like you do in IT and we make do.

Re: The Curious Case of MD5

#164
post #79

Earlier quoted context omitted.

Second preimage attacks aren't the only threat in a forensics environment. Also, hand-wavy extrapolations from Bitcoin miners aren't a reliable estimate of how fast & energy-efficient dedicated MD5 hardware could become.

Which part was hand-wavy/unreasonable? Do you think that dedicated MD5 hardware could become billions or even millions of times more efficient within a decade? If so, why?

MD5 is already not "fine" or "safe, even" against malicious actors who might pre-prepare collisions, or pre-seed their documents with the special constructs that make MD5 manipulable to collision-attacks.

Even if your extrapolative method was sound, you've already got several factors wrong. The best SHA256 Bitcoin miners are today more than twice your estimate in hashrate, and on plain CPUs SHA256 is more like 4x slower than MD5. (Your smaller estimate of MD5's speed advantage is likely derived from benchmarks where there's special hardware support for SHA256, but not MD5, as common in modern processors.)

But it's also categorically wrong to think the CPU ratio is a good guide to how hardware optimizations would fare for MD5. The leading Bitcoin miners already use a (patented!) extra 'ASICBoost' optimization to eke out extra parallelized SHA256 tests, for that use-case, based on the internals of the algorithm. As a smaller, simpler algorithm – also with various extra weaknesses! – there's no telling how many times faster dedicated MD5 hardware, either for generically calculating hashes or with special adaptations for collision-search – might run, with similar at-the-gates, on-the-die cleverness.

Further, attacks only get better & theory breakthroughs continue. Since MD5 is already discredited amongst academics & serious-value-at-risk applications – and has been since 1994, when expert cryptographers began recommending against its use in new work – there's not much above-ground scholarly/commercial activity refining attacks further. The glory & gold has mostly moved elsewhere.

But taking solace in the illusory lack-of-attacks from that situation is foolhardy, as is pronouncing, without reasoning, that it's "probably decades or more" before second-preimage attacks are practical. Many thought that with regard to collision attacks versus SHA1 – but then the 1st collision arrived in 2017 & now they're cheap.

You can't linear-extrapolate the lifetime of a failed, long-disrecommended cryptographic hash that's already failed in numerous of its original design goals. Like a bridge built with faulty math or tainted steel, it might collapse tomorrow, or 20 years from now. Groups in secret may already have practical attacks – this sort of info has large private value! – waiting for the right time to exploit, or currently only exploiting in ways that don't reveal their private capability.

You are right that there's no present 'crisis'. But it could arrive tomorrow, causing a chaotic mad-dash to fix, putting all sorts of legal cases/convictions/judgements in doubt. Evidentiary systems should be providing robust authentication/provenance continuity across decades, as that's how long cases continue, or even centuries, for related historical/policy/law issues to play out.

Good engineers won't wait for a crisis to fix a longstanding fragility in socially-important systems, or deploy motivated-reasoning wishful-thinking napkin-estimates to rationalize indefinite inaction.

Re: The Curious Case of MD5

#165
post #7

Earlier quoted context omitted.

SHA256 is something like 30 percent slower than MD5. I'd suggest using Adler (what zlib does) for a simple and fast checksum. Then that should, one hopes, be painfully obvious to be a bad fit for anything security related.

In Python the Adler library returns a 32 bit checksum. It works pretty well when you're comparing one file to another file. It doesn't work pretty well if you want to, for example, create a quick fingerprint that (tries to) uniquely identify tens of thousands of files. On StackOverflow I saw someone say that they got hash collisions in MD5 (128 bit) after hashing around 20k files. When I tried making something simila…

Conventional analysis of non-contrived files would suggest only a 50% chance of an MD5 collision among 2^64 (18 quintillion) files.

So any SO account of "hash collisions in MD5 (128 bit) after hashing around 20k files" may be indicative of some other bug, misreporting, or having a set of files that includes pairs intentionally-contrived to include MD5 collisions. (That's now trivial as long as you're not targeting a specific MD5 value, just intending two files to match, and have some ranges in the files where you can stuff the right result-aligning binary patterns.)

Re: The Curious Case of MD5

#166

Earlier quoted context omitted.

Second preimage attacks are relevant for the documents that you create and give to others. Keeping a hash of the document ensures that you can prove that any altered document shown by someone else is not the original. Collision attacks are relevant for the documents created by others, which you receive. If you have a hash of the document that is collision-resistant, you can trust that the creator does not have other…

Again. A "collision" means you have two pre-images which hash to the same value, but you did not pick either of the two pre-images. So if someone gives you a doc that says "SDKLFHJSDJKLGHJKLb9iyasdfkghjasdf97897asdfg798789asd" and then gives you another doc that says "klhjasdfhjklasdfhjkl97879087908789sdfga" and they have the same hash, then... what has the attacker achieved other than proving they've found a collisi…

> A "collision" means you have two pre-images which hash to the same value, but you did not pick either of the two pre-images.

I think the use of the word "you" is ambiguous here (do you mean the attacker? verifier?).

In an attack scenario for a collision attack, you would have an attacker prepare two documents that have the same hash but a different message. Attacker uses the innocent message initially, and then later swaps it to the evil message pretending it was that all along (or vice versa).

The way i could see it happening in a court setting (This is super far fetched and a bunch of reasons why this wouldn't work in practice).

Attacker, knowing they might end up in court, creates two payloads, one evil, one innocent with same md5 hash.

Attacker uses the evil payload to attack some target

Attacker gets arrested

In court, the put the payload the attacker used into evidence, indexed by its md5 hash

Attacker claims in court that it is all a misunderstanding, all they sent to the server was the innocent payload that just so happens to have the same hash as the evil one.

There's a bunch of (social) reasons why this probably wouldn't work, but this seems just as viable as the 2nd pre-image attack, and unlike the 2nd pre-image attack, actually is viable with md5.

Re: The Curious Case of MD5

#167
post #10

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 w…

That's right.

Same reason why blockchain is (almost) never the answer: that's not how human systems work.

Trust is centralized. Always had been.

Re: The Curious Case of MD5

#168
post #165

Earlier quoted context omitted.

In Python the Adler library returns a 32 bit checksum. It works pretty well when you're comparing one file to another file. It doesn't work pretty well if you want to, for example, create a quick fingerprint that (tries to) uniquely identify tens of thousands of files. On StackOverflow I saw someone say that they got hash collisions in MD5 (128 bit) after hashing around 20k files. When I tried making something simila…

Conventional analysis of non-contrived files would suggest only a 50% chance of an MD5 collision among 2^64 (18 quintillion) files. So any SO account of "hash collisions in MD5 (128 bit) after hashing around 20k files" may be indicative of some other bug, misreporting, or having a set of files that includes pairs intentionally-contrived to include MD5 collisions. (That's now trivial as long as you're not targeting a…

I'm not well-versed in this, but I think you're wrong. A MD5 hash has 2^128 permutations, so it's like the birthday problem, you'll get 50% chance of any two files in a set having the same hash with far fewer than 2^64 files.

Besides, we're talking about probabilities. It's possible for 2 files, one after the other, to have the exact same hash just because of chance. In fact, I think there was a bitcoin bug due to this, something about making the wrong assumption that the hash of the entire blockchain and the hash of the entire blockchain + 1 block would never be the same hash, if I remember correctly.

Hashes are simply not a reliable method of uniquely identifying things. They are a convenient method but if you implement any hash-based system for identification you should also implement a escape hatch for when two different things have the same hash but must be treated differently.

Re: The Curious Case of MD5

#169

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 st…

> Md5 is just as fine as any other generic hash function if its being used as a non-unique key MD5 brings the feature that you'll forever be explaining why you chose a function that had already been broken for 30 years when other options were readily available.

Often, its less about picking it for a new project vs having the discussion about how to update an existing one, often with data at rest that needs converting. In the latter case often the hash needs to fit into the existing 128b field size, so one is throwing a good number of the SHA bits away anyway.

Re: The Curious Case of MD5

#170
post #129
post #16

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!

Funnily enough, I had an interesting discussion with a client's lawyer (who, to their credit, is reasonably tech-savvy) before the holidays. I had redlined "FIPS 140-2" from their contract language. I'll omit the context, because it's too nuanced to be discussed here, but the long and short of it was that she wanted to know why I did that. I informed her that since FIPS 140-2 is about physical properties of key creat…

May we all be so lucky to have such an enlightened client(‘ s lawyer)!
Post reply on HN