Why SHA-256 (or any other) is too fast for passwords but "slow" for collisions to be found?

Question

Normally, the standard answers of why passwords shouldn't be stored using a groups of hash algorithms, including SHA-256 or higher, even if salted, are "because they are 'fast' hashes", "the attacker has access to specific hardware", and so on.

Why SHA-256 (or some other hashes) is too fast for passwords but "slow" for collisions to be found? Other ways of asking the same question are: When SHA is "slow" enough for being useful? Why can't that special hardware that the attacker used to crack passwords can't be used to find SHA collisions too?

I suspect the answer is related to the fact that passwords are, in general, small. If so, the question gets more accurate: What's the size of the message where it starts being worthy using SHA-256 (for example)?

Answer 1

I suspect the answer is related to the fact that passwords are, in general, small.

No, actually, the answer is related to the fact that passwords are, in general, predictable. Meaning that out of the set of all possible inputs to the hash function, a relative few of them are vastly more likely to be somebody's password than others. For example, Password1 is vastly more likely to be somebody's password than act chance past language (generated using the XKCD comic method), which is in turn vastly more likely than <Cj{Vm7&Jr5y9< (generated with this page). And that last one in turn is significantly more likely to be somebody's password than any randomly-selected 14-byte sequence (which is unlikely to even be printable ASCII).

What makes passwords weak is that the fact that some candidate passwords are vastly more likely than others means that the attacker can effectively avail themselves of this strategy:

1. Prioritize guesses that are very likely to be passwords over guesses that are less likely to be so.
2. Do this guessing process at very high speed using specialized hardware.

You've probably heard the term "dictionary attack," which is a very simple and effective technique for #1. Just make a list of likely passwords and try them all. Or download one from the Internet; this one, which collects "every wordlist, dictionary, and password database leak that [the author] could find on the internet" has 1,493,677,782 entries, which is about $2^{30}$.

---

The equivalent of this in the collision resistance scenario would be if we had some procedure that was able, for the hash function that we are attacking, to prioritize pairs of inputs that were more likely to collide than others. There's some knowledge about how to do that sort of thing for broken hash functions like MD5 or SHA-1, but not for SHA-256. Given the state of our knowledge, there isn't any way we know of prioritizing the search so that we try pairs likelier to collide ahead of unlikelier ones.

Since we don't know of a clever way to prioritize the search, then, generic math (the Birthday Problem) tells us that it should take us about $2^{128}$ guesses to find a SHA-256 colliding pair. That's a number vastly bigger than the $2^{30}$-entry password dictionary I cited above. Since SHA-256 is much faster than dedicated password hashing functions, you can test guesses for colliding pairs much faster than you could test password guesses, but definitely nothing even close to $2^{98}$ times faster (about $3 \times 10^{29}$).

Answer 2

If one hash takes 2 nanoseconds, $2^{42}$ hashes are fast to compute - you can do that in under 3 hours. But what if you want to try $2^{128}$ hashes? Even with one billion times the computational power you would still need more time than our universe is old to solve that. But what if you need 2 millisecond to calculate a hash instead of 2 nanoseconds? $2^{42}$ hashes would now take you over 278 years. That's too slow for any practical attacker.

To find any general collision in SHA-256 you need to brute force these $2^{128}$ hash calculations, as long as you don't know any break for the algorithm itself. Calculating SHA-256 is relative fast, but you still will most likely never find such collisions. Another thing is it if you just need to find the correct password for a given hash. If you know that the password was 9 letters long, a to z, that are $26^9 \approx 2^{42}$ possibilities. As I said with SHA-256 that's pretty fast to reverse with brute force. Let's say you take a special password hashing scheme like PBKDF2 or bcrypt which raises the compute time of a hash try from 2 nanoseconds up to (for example) 1 millisecond. Calculating $2^{42}$ hashes is now infeasible. These algorithms are slow for passwords and collisions.