[mikeash]

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

[dperfect]

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!

[mikeash]

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, then your only hope is brute force, so you look at the size of the hash. If you're breaking SHA-256, for example, that's 256 "random" bits.

If you have a specific hash that you want to generate, it will take you on average 2^255 attempts. (On average you have to try half the possibilities before you find a match.) If your computer can do a billion hashes per nanosecond then that means you'll spend on average 2^255 / (10^9 * 10^9) seconds, or about 10^41 times the current age of the universe.

If you just want to find any collision, then the birthday paradox comes into play, and on average you'll need to try roughly the square root of the number of possibilities before you find a collision. At a billion per nanosecond that's 2^128 / (10^9 * 10^9) second, or a mere 780 times the current age of the universe. Plus you have to figure out how to store all those intermediate results.

If MD5 fit this property it would still be good. Not as good as SHA-256, because it's only 128 bits, but plenty sufficient. 128 bits with the hypothetical billion hashes per nanosecond gives you 390 times the current age of the universe to find a specific hash. A collision is easier, at 18 seconds, but a billion hashes per nanosecond is also orders of magnitude faster than you'll realistically be able to do, and you'll need 2^64 * 128 bits = 300 exabytes of storage.

The problem with MD5 is that it does not fit this "random number" property. You can manipulate the input with somewhat predictable results in the output if you're clever, and that means you can generate a collision much easier than it would require for brute force.

My understanding is that more modern hashes are believed/hoped to have this property, but it's unknown. And not only that, but it's unknown whether any hash could exist with that property, or whether it's a theoretically impossible goal.

[granos]

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.

[mikeash]

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.

[__z]

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

[dperfect]

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.

[__z]

No arguments from me that cyptography is often explained confusingly which leads to misunderstandings.

[syncsynchalt]

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

[rictic]

MD5 is also supposed to require a tremendous amount of computation, it's just that there are weaknesses in the algorithm that were eventually discovered, such that an attacker can short circuit much of that work. The reason that SHA-1 is being sunset is that some preliminary results by researchers suggest that it also has weaknesses that can enable it to be short circuited, and that researchers appear to be on a path to discovering those weaknesses.

[dperfect]

Hmmm... so the takeaway for me is that when designing critical systems that rely on hashes/fingerprints as identifiers, we should probably treat those as transient identifiers with a reasonable expectation of migrating them as newer algorithms replace older broken ones. Does that sound right?

[Diederich]

That's correct.

[dperfect]

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 easily accommodate changes to the algorithm."

[xorcist]

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 better practices not only in algorithms but also in how they are used (mac-before-encryption being the canonical example of this which took far too long to change).

[bluefox]

Correct. http://valerieaurora.org/hash.html

[userbinator]

The story of how the MD5 collision pathways were discovered is an interesting one - the first colliding pair is said to have been calculated by Xiaoyun Wang by hand, with little computer use. She has also figured out similar methods for SHA-1 and a few other hashes.

http://en.wikipedia.org/wiki/Wang_Xiaoyun

[gkoz]

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

[mikeash]

It was thought to, which is why it became so popular. It turned out to be wrong.

[astrodust]

Not really. It was cracked by a distributed network of ordinary computers were people volunteered CPU time.

[pbsd]

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