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

Poisonous MD5 – Wolves Among the Sheep

blog.silentsignal.eu

Post reply on HN
Print view View original

31–40 of 55 posts

Re: Poisonous MD5 – Wolves Among the Sheep

#31

Post by cstejerean »

4mnt wrote: post #27
jimrandomh wrote: post #22

Earlier quoted context omitted.

No, the property you describe is called "preimage resistance". Collision resistance is stronger; it states that an attacker should not be able to create a pair of inputs with the same hash. In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. The MD5 algorithm is known to lack collision resistanc…

> In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. This is the case with all instances of seeking a collision, due to the birthday paradox [0] 0: https://en.wikipedia.org/wiki/Birthday_attack

The birthday paradox helps with the case of finding any two random inputs that have the same hash. The problem with MD5 is that it's feasible to craft two specific inputs that happen to have the same hash.

Re: Poisonous MD5 – Wolves Among the Sheep

#33

Post by garrettr_ »

jimrandomh wrote: post #22
kedean wrote: post #4

Earlier quoted context omitted.

The collision-resistance property that all good hashes should have (and md5 lacks) states that an attacker with an input and its hash cannot arbitrarily produce a second input with the same hash. The possibility of it happening in the wild will always exist with hashes by their finite nature, but the only way an attacker should be able to find collisions is by enumerating the input space (rainbow table generation).

No, the property you describe is called "preimage resistance". Collision resistance is stronger; it states that an attacker should not be able to create a pair of inputs with the same hash. In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. The MD5 algorithm is known to lack collision resistanc…

Nitpick: the property OP describes is actually second pre-image resistance, not preimage resistance (or collision resistance). See https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr...

Re: Poisonous MD5 – Wolves Among the Sheep

#34

Post by __z »

dperfect wrote: post #7
mikeash wrote: post #5

Earlier quoted context omitted.

Your parenthetical is the key, though. There's a big difference between a hash algorithm where generating a collision requires a few minutes of work on a cheap computer (MD5, now) and a hash algorithm where generating a collision requires a computer the size of the universe operating for a trillion trillion years (any good cryptographically secure hash).

Cool - didn't realize the difference was so great. I've always known that the good algorithms are better because they're more difficult to brute-force, but always wondered if it's just a matter of a few years before the "impossible" becomes possible. Your illustration helps clarify that improbability in my mind - thanks!

>always wondered if it's just a matter of a few years before the "impossible" becomes possible.

This is from 1998 but the relevant parts - https://www.schneier.com/essays/archives/1998/05/the_crypto_...

>Cryptographic algorithms have a way of degrading over time. It's a situation that most techies aren't used to: Compression algorithms don't compress less as the years go by, and sorting algorithms don't sort slower. But encryption algorithms get easier to break; something that sufficed three years ago might not today.

>Cryptographic algorithms are all vulnerable to brute force--trying every possible encryption key, systematically searching for hash-function collisions, factoring the large composite number, and so forth--and brute force gets easier with time. A 56-bit key was long enough in the mid-1970s; today that can be pitifully small. In 1977, Martin Gardner wrote that 129-digit numbers would never be factored; in 1994, one was.

>Aside from brute force, cryptographic algorithms can be attacked with more subtle (and more powerful) techniques. In the early 1990s, the academic community discovered differential and linear cryptanalysis, and many symmetric encryption algorithms were broken. Similarly, the factoring community discovered the number-field sieve, which affected the security of public-key cryptosystems.

DES was used in the 70s, now it can be brute forced in a few days (with the right hardware).

Re: Poisonous MD5 – Wolves Among the Sheep

#35

Post by pbsd »

gkoz wrote: post #10
mikeash wrote: post #5

Earlier quoted context omitted.

Your parenthetical is the key, though. There's a big difference between a hash algorithm where generating a collision requires a few minutes of work on a cheap computer (MD5, now) and a hash algorithm where generating a collision requires a computer the size of the universe operating for a trillion trillion years (any good cryptographically secure hash).

Did breaking MD5 require a computer the size of the universe 20 years ago?

MD5's compression function was already broken 20 years ago: http://cseweb.ucsd.edu/~bsy/dobbertin.ps

Re: Poisonous MD5 – Wolves Among the Sheep

#36

Post by dperfect »

__z wrote: post #34
dperfect wrote: post #7

Earlier quoted context omitted.

Cool - didn't realize the difference was so great. I've always known that the good algorithms are better because they're more difficult to brute-force, but always wondered if it's just a matter of a few years before the "impossible" becomes possible. Your illustration helps clarify that improbability in my mind - thanks!

>always wondered if it's just a matter of a few years before the "impossible" becomes possible. This is from 1998 but the relevant parts - https://www.schneier.com/essays/archives/1998/05/the_crypto_... >Cryptographic algorithms have a way of degrading over time. It's a situation that most techies aren't used to: Compression algorithms don't compress less as the years go by, and sorting algorithms don't sort slower.…

I suppose one could say this is an argument against using the "computer the size of the universe operating for a trillion trillion years"-type illustrations. Statements like that reflect the current theoretical strength of an algorithm, but unfortunately the illustrations can lead us to (wrongly) assume that flaws won't be discovered in the algorithm for that period of time, which is very much untrue and undermines the practical implications of those statements.

Re: Poisonous MD5 – Wolves Among the Sheep

#37

Post by VLM »

xorcist wrote: post #30
dperfect wrote: post #25

Earlier quoted context omitted.

I feel like this gets missed in the debate over the "best" hash algorithms. It seems like the message is always "use XYZ algorithm for everything - it's practically perfect and the only one you'll ever need". In reality, it should be more along the lines of "migrate to this one for now, but don't build things that depend on it being the best option next year since it's probably not perfect. Design your systems to eas…

That is the common wisdom. However some people, most known perhaps djb, actually argue against it. Pluggable algorithms may allow for downgrade attacks, and in a world wide complex system there will always be holdouts for some reason. They argue you would be better with hardcoding your system to known secure best practice. When the time comes to change it, you specify a new protocol version, as there will be new and…

"Pluggable algorithms may allow for downgrade attacks"

This is a uniquely severe problem for hashing. MD5 is by far the fastest of the common hashes, at least 20% faster than SHA1 for example.

The Venn diagram is you've got popular fast hashes, of which md5 is arguably the best, and in fast hashes, you've got cryptographically secure fast hashes, of which md5 most certainly is no longer a member. Its awesome for everything non-crypto non-secure non-over the internet.

Last weekend I had to burn a legacy DVD and I compared the md5sum of the image to the md5sum of the burned DVD, thankfully they matched. As much as I distrust legacy media, there probably isn't a sentient opponent in the burner, although I've occasionally sworn otherwise, and the most likely failure mode would have been simple truncation or buffer dropouts, so sheer speed was the priority. The hashes obviously matched, it was a good burn.

I've also used them as checksums for engineering data files. Everything on the planet from AS400s to MySQL databases can calculate md5, which is convenient for cross platform interchange type stuff. Heres a data blob and its md5, does your hash calculation match? Oh it does, how nice to know you have perfect data integrity, here have the next one. On the internet I wouldn't trust the opfor with md5, but I can trust my own coworkers and my own engineering machinery not to try and attack me (well, probably).

That means until the end of time you'll unfortunately have people discover md5 is available for non-crypto use, then try to use it to hash passwords or DRM executables or something, which is not so wise. Or for a downgrade attack, they misdesign their crypto system to allow any hash installed on the machine as the hash type and not blacklist md5 and sha1 and maybe more.

What will die out is hashes like SHA1. Why use something almost as dangerous as md5 for crypto, thats slower than md5, and not as widespread as md5? Bye bye sha1!

Re: Poisonous MD5 – Wolves Among the Sheep

#38

Post by mikeash »

granos wrote: post #26
mikeash wrote: post #21

Earlier quoted context omitted.

Glad to be of service. This seems to be a common misconception. To put some numbers on it, a good cryptographic hash should produce random-looking output with no way to predictably influence the output, and no visible correlation between the input and the output. Put in A, get out "random number" B, except that every time you put in the same A, you get out the same B. If you have a hash that matches that description,…

Also, even it were provably true that some hash algorithm has this property, we would have to implement it properly. That requires the algorithm itself as well as all of its dependencies to be implemented properly. It's very easy to make an implementation mistake that breaks security.

Is that typically a problem for a plain hash? There's no random data to be leaked or generated poorly, and there's typically not going to be any private information that could be leaked through a timing attack.

Re: Poisonous MD5 – Wolves Among the Sheep

#39

Post by syncsynchalt »

__z wrote: post #34
dperfect wrote: post #7

Earlier quoted context omitted.

Cool - didn't realize the difference was so great. I've always known that the good algorithms are better because they're more difficult to brute-force, but always wondered if it's just a matter of a few years before the "impossible" becomes possible. Your illustration helps clarify that improbability in my mind - thanks!

>always wondered if it's just a matter of a few years before the "impossible" becomes possible. This is from 1998 but the relevant parts - https://www.schneier.com/essays/archives/1998/05/the_crypto_... >Cryptographic algorithms have a way of degrading over time. It's a situation that most techies aren't used to: Compression algorithms don't compress less as the years go by, and sorting algorithms don't sort slower.…

To reinforce your point, DES is now crackable by the public in under a day: https://www.cloudcracker.com/blog/2012/07/29/cracking-ms-cha...

Re: Poisonous MD5 – Wolves Among the Sheep

#40

Post by taumhn »

ryan-c wrote: post #16
snorkel wrote: post #12

Earlier quoted context omitted.

The attack vector would be malware binary crafted to have the same MD5 sig as a popular already trusted app. But of course once the badware is caught virus scanners could check other properties aside from MD5 sig to flag a bad binary. I assume virus scanners use MD5 just a fast prescreen scan, then do a few deeper checks on pototentially bad binaries to make sure.

What you describe there would be a preimage attack[0], not a collision attack. There is no publicly known practical[1] preimage attack on MD5 at this time. 0. http://en.wikipedia.org/wiki/Preimage_attack 1. 2^123.4 complexity is not practical

If I understand correctly, what's described in the article indeed uses a collision attack. The "trusted app" is one the hacker manufactures himself.
Post reply on HN