The long tail of MD5 • Hacker News Board

Re: The long tail of MD5

#41

Post by ekimekim » Fri, Dec 05, 2014, 5:40 AM UTC

MagicWishMonkey wrote: post #33

jonstewart wrote: post #16

MD5 also remains quite popular for file hashing/hash set analysis. I.e., is this file a member of a known set? For example, NIST's NSRL still includes MD5 hashes. * This is not an endorsement of MD5 for such use cases.

Are collisions really that much of a concern (other than for security reasons)? IIRC they are still incredibly rare even with older hashing algorithms like MD5.

Yes, if you don't care about collisions* or being able to reverse the hash (a pre-image attack) then there's nothing wrong with MD5 per se. However, MD5 was designed as a secure algorithm, and makes tradeoffs, mainly in speed, to that effect. If you don't need security, you should use something designed for that, like CRC.

* note that even if it isn't immediately obvious, in most situations you really don't want collisions to be an easy thing to cause. For example, many algorithms and structures involving hashes (even a simple in-memory hash map) suffer massively degraded performance when there's a large number of collisions. If your user can craft an input that causes operations to take orders of magnitude longer, that's a denial of service attack.

Re: The long tail of MD5

#42

Post by donavanm » Fri, Dec 05, 2014, 7:46 AM UTC

bodyfour wrote: post #15

yuhong wrote: post #5

Content-MD5 has been removed from HTTPbis. Don't forget VBA digital signatures BTW, for which MD5 is the only choice. I wonder how feasible a collision attack would be.

Yeah a couple years ago I was trying to determine whether to support Content-MD5 in some HTTP software I was writing I could find nobody actually using it. There was an attempt a decade ago to make Firefox validate with it, but that died: https://bugzilla.mozilla.org/show_bug.cgi?id=232030 Also the author is wrong that there isn't a proposed replacement -- it's the "Digest:" header (RFC 3230) although I don't think a…

Id hazard the most prolific use case of md5 as http checksum is AWS S3. You can, IIRC, send content-md5 on PUT and POST and theyll reject with a 400 if the body hash doesnt match. Conversely the default etag is the body md5.

Re: The long tail of MD5

#43

Post by nathan7 » Fri, Dec 05, 2014, 9:34 AM UTC

These days, I find using MD5 absolutely inexcusable. SHA-1 is available pretty much everywhere, SHA-2 algorithms are quite readily available too. BLAKE2 (https://blake2.net) is slightly faster than MD5, and significantly more secure. It's based on the SHA-3 finalist BLAKE. Additionally, there are versions of the algorithm that parallelise using SIMD, and there are both 32-bit and 64-bit optimised versions too. It also gives you the possibility of customising your hash, using it as an HMAC at no extra cost, salting it, or adding a personalisation key to effectively have different hash functions for different purposes. As a nice extra, it also uses a third less RAM than SHA-2 or SHA-3. If output length is a concern, truncating the output (with a corresponding increase in the likeliness of collisions) is perfectly fine with any good hash function.

Re: The long tail of MD5

#44

Post by pbsd » Fri, Dec 05, 2014, 10:40 AM UTC

wbl wrote: post #36

lisper wrote: post #22

Earlier quoted context omitted.

OK... so if it's suitable as a PRF, then you should be able to widen the output by using two different keys and concatenating the results, no?

Unfortunately not: it's only 64 times slower to generate 2^64 collisions for hash function by generic attacks than just one, and those 2^64 messages will contain a collision for another hash function of length 128. The total time is only the sum of the times for each one.

The attack you describe---Joux's multicollisions, as far as I can tell---applies to Merkle-Damgard functions. SipHash is a spongy, wide-pipe, design where that sort of thing doesn't work. The generic bound is (k!)^(1/k) ⋅ 2^(n(k-1)/k)) work to find a k-collision, or approximately k ⋅ 2^n for large k.

Re: The long tail of MD5

#45

Post by awalton » Fri, Dec 05, 2014, 12:18 PM UTC

IvyMike wrote: post #38

Want to kill MD5? Provide public-domain easy-to-compile/use versions for all languages, and furthermore, get their google page ranks high. Do not underestimate laziness. If Joe Random can find a suitable MD5 algorithm in 10 seconds but it takes 30 seconds to find a suitable SHA algorithm, guess which one gets used?

Honestly, this is not so much a problem. Cryptographers like to write simple C public domain implementations of their algorithms and then people go to work for months and years squeezing performance out of them, cryptanalyzing them, recoding them in various languages and releasing their own implementations under new licenses. You can see this happening with pretty much every newly designed crypto component from hashes to ciphers to entire crypto systems.

The problem is exactly the one elucidated in the blog post above: the long tail of baked in brokenness. These systems were never designed to be extensible, they are cooked into code that hasn't been serviced in years, perhaps even decades in some cases. They're bolted into specifications in ways that either obsolete the technology completely, or make it so incredibly complicated to update the technology that doing so outweighs the apparent cost. And that's without considering problems like deployment and phase-out.

These types of problems make it very likely we will be stuck with the stupidity of DES and MD5 in strange places until it becomes a fire drill and then all the sudden people will be baking in SHA-1/SHA-2 or BLAKE2 and we'll be going through these very same motions again in 5-15 years, wondering why we didn't learn from the mistakes we made last time.

Re: The long tail of MD5

#46

Post by heinrich5991 » Fri, Dec 05, 2014, 12:59 PM UTC

ChuckMcM wrote: post #30

smackfu wrote: post #27

Earlier quoted context omitted.

Do the security problems with MD5 make it bad as a hashing algorithm?

Generally the tuple ( , ) is unique since the attacks on MD5 all involve changing the number of octets in the hashed source. That said, it isn't secure if you can change the length independently of changing the hash. Hence the challenge of using it cryptographically. If you're confident you know the correct 'length' value (acts as a sort of openly shared secret in this case) then you trust the hash.

I believe this is wrong, and in this case it's very dangerous information. See for example the Wikipedia article for two chunks of data that only differ in a few bits (not length!) and hash the to same MD5 hash: https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities

Re: The long tail of MD5

#47

Post by w8rbt » Fri, Dec 05, 2014, 2:32 PM UTC

HMAC MD5 is a perfectly reasonable choice for some situations.

Re: The long tail of MD5

#48

Post by stubborndude » Fri, Dec 05, 2014, 4:57 PM UTC

jonstewart wrote: post #16

MD5 also remains quite popular for file hashing/hash set analysis. I.e., is this file a member of a known set? For example, NIST's NSRL still includes MD5 hashes. * This is not an endorsement of MD5 for such use cases.

Was going to make this point. But lets instead talk about the endorsement aspect, because lots of people in the forensic community take the "its popular so i use them, but i neither endorse nor oopose" position.

There is certainly risk of hash collisions in files, but most attacks require you to generate two different files with the same hash? Do people think a pre-image attack is feasible? If feasible, at what scale? What type of actor can give me a file that has different content, but the same hash as winword.exe. If they can, what is the likelihood that said file will also be executable or contain a linkable library

*similarly, and hypocritically, not an endorsement of md5

Re: The long tail of MD5

#49

Post by astrodust » Fri, Dec 05, 2014, 7:05 PM UTC

FroshKiller wrote: post #12

jmartinpetersen wrote: post #3

Earlier quoted context omitted.

Collision attacks are trivial. It's been almost ten years since Ron Rivest declared MD5 broken.

Well, ROT13 is at least immune to collision attacks.

Generating a collision for the "encrypted" phrase "unpx" is not hard.

Re: The long tail of MD5

#50

Post by kedean » Fri, Dec 05, 2014, 7:05 PM UTC

NoMoreNicksLeft wrote: post #18

yuhong wrote: post #4

Earlier quoted context omitted.

I know, but this does not make MD5 as broken as ROT13.

Rot13 is actually useful. I have perl scripts which download my bank statements, running from cron. Gets the latest every month. These perl scripts use passwords, but without knowing that they are there, who would find them? The trouble is, they have to pass the name of the form field to the server on the other side, which is some variation of "password". So anyone doing a simple string search will eventually find th…

That's pretty heavy security through obscurity. A more robust solution would be to have all of those passwords encrypted with a master key. You can make the script prompt you for the master key when you start it up, then it runs without needed any more input, but you aren't storing sensitive information.