Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Curious Case of MD5

katelynsills.com

Post reply on HN
Print view View original

51–60 of 173 posts

Re: The Curious Case of MD5

#51

Post by drisden84 »

wyldfire wrote: post #45
tneely wrote: post #43

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

> there's not really any relevant attack space. Then why use a cryptographic hash at all? much better hashes out there that only strive for distribution/avalanche. https://en.wikipedia.org/wiki/Non-cryptographic_hash_functio...

MD5 has/had a well-known "media" surface - lawyers/genomics folks had heard of it. Libraries had it as an accessible function (command line utilities, even).

Sure, there are better non-cryptographic hashes, but, again the concern of lawyers and genomics folk is neither security nor efficiency - simplicity and "works most of the time" are the two metrics at stake.

If either laywers or genomics folks cared about document forgery of this nature (spoiler, they don't), they would move to something like SHA3. If they had a need for high-scalability hash algorithms (spoiler, they don't), they would switch to another faster algorithm.

This is a concept I understand security folks struggle to understand - sometimes we _just don't care_. And we never should.

Maybe, something a struggling security enthusiast could understand - a video game.

If you implement e.g. a caesar cipher, you can have fun, accessible puzzle. Implementing AES in your game as a puzzle, while much harder, fails desperately at the "accessibility" metric. In your single player game, if you want to see some "identifying hash", if you see an md5 one, that's enough. No, you should not worry about people forging documents for your ad-hoc identification system, if you don't have people attempting to forge in-game items. Maybe its even a feature that you need to forge such a hash, as a way to solve a puzzle.

Re: The Curious Case of MD5

#52

Post by magicalhippo »

AlienRobot wrote: post #48
hoten wrote: 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…

When making a dupe detector some decades ago, I kept the filesize outside of the hash.

No need to compute the hash until there's at least two files with the same size.

Re: The Curious Case of MD5

#53

Post by OhMeadhbh »

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.

Re: The Curious Case of MD5

#54

Post by drisden84 »

ms512 wrote: post #8
kozak wrote: post #2

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.

When you don't have a need for a cryptographic digest, it's important to think of the channel's bit error distribution in selecting a checksum algorithm. Different checksum algorithms can provide better error detection for specific channel error models (potentially even with fewer bits). Non-cryptographic checksums are typically designed for various failure models like a burst of corrupt bits, trading off what they d…

"When you don't have a need for a cryptographic digest, it's important to think of the channel's bit error distribution in selecting a checksum algorithm."

Important real-life-facts.

There was no "give-me-an-appropriate-hash" function.

There was:

md5sum yourfile.txt

Nobody wants to think about "channel's bit error distribution" in a non-security critical context. In fact, its irrelevant, and possibly a usability issue.

Re: The Curious Case of MD5

#55

Post by gruez »

moyix wrote: post #39
wuiheerfoj wrote: post #37

Earlier quoted context omitted.

Running 2^64 SHA1 ops on a GPU takes 15 years, so I think finding a reasonable collision for that half using SHA2/3 is not as trivial as you suggest: https://crypto.stackexchange.com/questions/84520/how-long-wo...

Since that post was published, the 4090 came out, which can (according to this hashcat benchmark [1]) do 50,638.7 million SHA1 hashes per second, so now it would only take a single 4090 GPU 11.55 years. Or you could buy 12 of them and do it in a year, etc. So it's definitely not cheap but 15 years is definitely an overestimate (and presumably GPUs will keep getting faster...). SHA2-256 is "only" 21975.5 MH/s so you'd…

Generating 2^64 hashes isn't guaranteed to produce a collision, and even if a collision did exist in that set, you're not going to find it by getting a bunch of GPUs to compute 2^64 hashes. There's a huge difference between a haystack that maybe contains a needle, and a needle that's been pulled from the haystack and presented to you. To actually find and identify the collisions you'll need to hook those GPUs up to some sort of storage/retrieval system. Just to store 2^64 128-bit hashes would take 295.1 exabytes. That's an order of magnitude more storage than NSA's utah datacenter[1].

[1] https://en.wikipedia.org/wiki/Utah_Data_Center

Re: The Curious Case of MD5

#56

Post by bawolff »

OhMeadhbh wrote: post #53

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 "SDFKLHKLJx…

So if the document is evidence , then its probably created by the attacker. This seems like a setup where collision is more relavent than 2nd preimage.

Re: The Curious Case of MD5

#57

Post by bawolff »

throwaway89201 wrote: post #19

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

It should be noted that md5 is probably still secure for this usecase (maybe you could do a bait and switch with a specificly prepared file, but you can't force a collision with a non-evil file)

Still, they should switch. Sha1 is not good either.

Re: The Curious Case of MD5

#58

Post by saghm »

upofadown wrote: post #33

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…

> 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.

Comparing MD5 and SHA-2 for visual human diffing is like comparing a stick of dynamite to a landmine when trying to pop a pimple; any potential safety differences are trivial once you start using something in a fundamentally unsafe way.

Re: The Curious Case of MD5

#59

Post by moyix »

gruez wrote: post #55
moyix wrote: post #39

Earlier quoted context omitted.

Since that post was published, the 4090 came out, which can (according to this hashcat benchmark [1]) do 50,638.7 million SHA1 hashes per second, so now it would only take a single 4090 GPU 11.55 years. Or you could buy 12 of them and do it in a year, etc. So it's definitely not cheap but 15 years is definitely an overestimate (and presumably GPUs will keep getting faster...). SHA2-256 is "only" 21975.5 MH/s so you'd…

Generating 2^64 hashes isn't guaranteed to produce a collision, and even if a collision did exist in that set, you're not going to find it by getting a bunch of GPUs to compute 2^64 hashes. There's a huge difference between a haystack that maybe contains a needle, and a needle that's been pulled from the haystack and presented to you. To actually find and identify the collisions you'll need to hook those GPUs up to s…

You can generate pairs of hashes for random inputs and check for collision without storing all of the outputs, no?

Re: The Curious Case of MD5

#60

Post by bawolff »

notahomosapien wrote: post #44
chias wrote: post #32

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

Quantum computers will severely break MD5 and SHA-1, so they'd be broken even if they are used with HMAC. Use SHA2-256 unless you need quantum-resistant collision resistance, in which case you should use SHA2-384. Use HMAC-SHA2-* with an 256-bit key if you want to prevent length extension attacks.

Severely break is a bit of a overstatement.

It will make a speed up, but its not like shor's algorithm - you need a really powerful quantum computer before md5 comes under threat.

But to be clear. Md5 is broken do not use.

Post reply on HN