Why SHA-256 (or any other) is too fast for passwords but "slow" for collisions to be found? 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)?
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 &lt;Cj{Vm7&amp;Jr5y9&lt; (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:


Prioritize guesses that are very likely to be passwords over guesses that are less likely to be so.
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}$).