8 ms·
The long tail of MD5
- yuhong 12y agoEverybody knows that MD5 is as terribly useless as ROT13 Huh?
- jmartinpetersen 12y agoCollision attacks are trivial. It's been almost ten years since Ron Rivest declared MD5 broken.
- yuhong 12y agoI know, but this does not make MD5 as broken as ROT13.
- JoachimS 12y agoDepends on what you place in the expression broken. Md5 is useless in anything remotely related to security. An as a non secure function it is slow.
- TillE 12y ago> Md5 is useless in anything remotely related to security There are serious flaws with MD5, and I would never recommend its use today. But there is no known attack that can generate a malicious binary with an arbitrary hash. The attacker needs to control both files to generate collisions, which is a huge limitation. Maybe those attacks will exist some day. But I wouldn't be setting fire to all your legacy software without first understanding exactly how they use MD5, and if that is vulnerable to any known attack.
- yuhong 12y agoI think with practical chosen prefix attacks this may have changed.
- astrodust 12y agoGiven there are SHA256 engines that produce terahashes per second, you could probably do tens to hundreds of terahashes depending on sophistication. At that point even a sloppy brute-force approach would have a high probability of a collision on at least one key of a sufficiently large key-set. Against a specific target it may or may not be viable.
- VLM 12y agoAs a non secure function its "killer app" is being everywhere on every platform and being massive overkill for many applications.
- jmartinpetersen 12y agoConsidering that the sentence continues with something that is clearly a joke (the SHA-3 standardisation isn't finalized yet, let alone wasn't thought of 20 years ago), some hyperbole is to be expected. And the point is fair, there's not really anything today where MD5 is an obvious choice.
- NoMoreNicksLeft 12y agoRot13 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 the perl scripts, and have access to my passwords (supposing they have root). If I rot13 the form field name, and then have the name be rot13('cnffjbeq') in the script, this makes is unsearchable.
- kemayo 12y agoNote to self: add "cnffjbeq" to my password-finder scripts.
- NoMoreNicksLeft 12y agoMight as well add rot-1 through rot-25 to it as well... not like there's a storage constraint, is there?
- kedean 12y agoThat'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.
- NoMoreNicksLeft 12y agoYes. A master key. Which would have to be included in the perl script... so that when they find the script, they have all my passwords instead of just a few. You've solved it. Why didn't I think of that? > You can make the script prompt you for the master key when you start it up, Why the fuck would I want to sit around being a meat robot inputting 9 passwords at the beginning of each month just so I can have a copy of my bank statements and electric bill? The whole point was that this was in a crontab.
- FroshKiller 12y agoWell, ROT13 is at least immune to collision attacks.
- astrodust 12y agoGenerating a collision for the "encrypted" phrase "unpx" is not hard.
- FroshKiller 12y agoIt's not hard--it's impossible. The only value that ROT13 returns "unpx" for is "hack." There is no possible collision.
- astrodust 12y agoCongratulations, you found a collision. What's meant by that is if you can find a source string that hashes to the same thing. Using ROT13 is pointless since it's trivial to generate those. MD5 is only slightly harder.
- FroshKiller 12y agoReproducing the message is not a collision. In a collision attack, you find a message that produces the same hash as another message. You can't take the exact same message and call it a collision. ROT13 is immune to collision attacks by its nature, and the humor is in the fact that its "immunity" comes from not being a one-way hash. It's immune...but it's also practically useless for obfuscating the message, thus it doesn't protect your message at all. Thanks for taking great pains to make sure the joke got ruined.
- IvyMike 12y agohttps://en.wikipedia.org/wiki/Comedic_device#Hyperbole.2C_or_Overstatement https://en.wikipedia.org/wiki/Comedic_device#Hyperbole.2C_or...
- deleted 12y ago[deleted]
- yuhong 12y agoContent-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.
- bodyfour 12y agoYeah 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 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 anybody uses that either.
- donavanm 12y agoId 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.
- JoachimS 12y agoGood article that really shows why design decisions can have impact 20, 30 years or more. This is why I get fairly upset when people design something new I n 2014 that uses md5. Yes even if your application does not use md5 for anything security related, the mere fact that you use a bad, slow algorithm should be considered wrong. And adding new dependencies will make it harder for us to migrate away and extend that tail even further. If you need a good hash function that is fast, use SipHas. If you need a really secure one, use SHA-512, SHA-3, BLAKE or just SHA-256.
- pbsd 12y agoDo NOT use SipHash as a cryptographic hash function. It is designed to be a PRF, and its output length is way too small to make it collision-resistant when used as a hash. SHA-3, SHA-512/256 or BLAKE(2) (in increasing order of performance) are suitable cryptographic hash functions.
- lisper 12y agoI think you meant: it [SipHash] is NOT designed to be a PRF.
- pbsd 12y agoNo, I meant what I wrote. SipHash is fine as a keyed primitive -- 128-bit security against key recovery, (64 - t)-bit security against 2^t forgery attempts. However, as a hash function (e.g., with a fixed key), it is entirely too weak: 2^32 work for a collision, and 2^64 work for arbitrary (second-)preimages.
- jonstewart 12y agoMD5 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.
- smackfu 12y agoDo the security problems with MD5 make it bad as a hashing algorithm?
- tkmcc 12y agoNot necessarily, but if that's your use case (and the hashing speed isn't extremely critical), why not use a better algorithm with a larger output?
- derobert 12y agoDepends. Can an attacker introduce files? If so, he can probably introduce collisions. In most uses of a hash, that's an issue—a performance (DoS) issue if nothing else. If the application was just looking for a longer CRC/Adler32/etc. and not depending on the hash to be strong against attack, then MD5 wasn't an appropriate choice in the first place, as its much slower than need be. But the security problems are irrelevant.
- ChuckMcM 12y agoGenerally the tuple (<length>,<hash>) 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.
- heinrich5991 12y agoI 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 https://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities
- IvyMike 12y agoWant 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?
- awalton 12y agoHonestly, 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.
- nathan7 12y agoThese 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 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.
- w8rbt 12y agoHMAC MD5 is a perfectly reasonable choice for some situations.
- astrodust 12y agoA situation like not caring.