1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ If you are talking about a password that is chosen uniformly at random from say {a..z}^20 then, the choice of hash function is not important (even md5 should do the work). However, it's not the case for standard human users, they tend to choose passwords with low entropy and reuse in multiple sites. So if your weak password is included in some attacker's dictionary, the slower the hash function is the slower the attacker scan through his dictionary. $\endgroup$ – DiamondDuck Mar 7 '18 at 22:03
  • $\begingroup$ SHA256 can be used for password if used many times over. The output of the 1st hash (of the password+salt) is the input of the 2nd sha256 hash calculation. And so on. Do this a hundred or a thousand times for each password, and a brute force attack is much less feasible. And if it so happens in the future that a weakness is found in the sha256 algorithm (as md5), you could always just update your users password hashes with the hashes of those of a new better hashing algorithm. Just don't overdo it and hash so many times that many users logins at the same time brings down your server. $\endgroup$ – Kjetil S. Jul 31 at 19:10
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Ok, a password is the same predictable, regardless of the hashing method used, but, if somebody has an algorithm to judge the likelihood of a guess to be a password, then an attacker can build a dictionary attack faster for SHA than PBKDF2. $\endgroup$ – ribamar Mar 8 '18 at 9:36
  • 1
    $\begingroup$ @ribamar: I've expanded my answer to give a bit of an idea of the difference in scale between a password cracking attack and a generic collision-finding attack. $\endgroup$ – Luis Casillas Mar 8 '18 at 21:24
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nit: $2^{42}$ hashes at 1 millisecond each is 140 years, not 278. In any case, once we add GPU farms (which can compute a huge number of hashes in parallel), this total of 140 CPU years can actually be feasible (as we have lots of CPUs in parallel). Your point that $2^{128}$ hashes being too much to compute still stands (even with a GPU farm, or even ASICs) $\endgroup$ – poncho Mar 7 '18 at 22:57
  • $\begingroup$ Ok, basically you're confirm that it's related to the size of passwords. I can brute force 2^^42 but a general text 2^^128. Where between 2^^42 and 2^^128 is OK to use SHA? Surely I can do the maths myself, I only want to know if is that simple, or somebody to criticize me for missing a point. $\endgroup$ – ribamar Mar 8 '18 at 9:07
  • $\begingroup$ @poncho: thanks for the note, I've changed the 1 ms to the intended 2 ms. The amount of GPUs is already inside the 2 ms. Adding more to the farm would reduce this number, which would have to be counteracted by slowing down the hash function (something which should be pretty easy with a password hashing scheme like PBKDF2 , bcrypt, ...) $\endgroup$ – Nova Mar 9 '18 at 13:07
  • $\begingroup$ @ribamar: depends on the amount of money and time the attacker has. 1000 GPUs with 600 million hashes per second can calculate $\approx 2^{60}$ hashes per month, so 64 Bit should work against nearly everything except NSA, Google, ... take note that this only works for things like hashed passwords, but not creating secure hashes for certificates and such. You need to double the amount of bits for that because of the birthday paradox. $\endgroup$ – Nova Mar 9 '18 at 13:19
  • $\begingroup$ @Nova: ", I only want to know if is that simple," => i guess your answer is "yes". there is another answer which answers "no, the strength of password-hashing algorithms aren't not simply a matter of input size". Do you agree? $\endgroup$ – ribamar Mar 9 '18 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.