Could a very long password theoretically eliminate the need for a slow hash?

Question

Before I provide details, I want to clarify that I am not looking to implement this practically, but I'm only asking to get a better understanding.

The way I currently understand it, we use slow hashes for passwords because there are too few possibilities in passwords. This means people could calculate all the potential passwords (or a whole lot of them) fairly quickly when using a performance hash, and find what made the digest. E.g. if in an imaginary world where digests are 3 bytes and slow hashes last a decade my password is "abb" and it results in digest "x3x", someone who got this hash could start retrieving my password by hashing "aaa", then "aab", then "abb" and see that the result is "x3x", and so my password must be "abb". With a slow hash, he wouldn't have time to calculate all three results.

This makes sense for short passwords, but I thought the strength in modern block ciphers lied in the key space. For Two-fish for example, it can have a key from any of 2^256 different variations. Trying all those variations would just be insane, and so it can't be done (for now).

Given these two things, wouldn't the strength of a performance hash as a password storage tool increase with each letter? Alphanumeric letters cover 32 to 127 in ASCII, so that's 6 bits entropy per character (I think). If that's true, would a password of 43 characters be secure when hashed with say, SHA 256?

Answer 1

Despite the impracticalities of using a 43-char password, I would say yes, such a long password would be secure when hashed with just SHA256. Assuming 127 possible ascii characters, a password of 8 characters would require an attacker to search about 2^56 possibilites (viable), whereas a password of 43 characters would require searching about 2^300 possibilities (infeasible, considering that 2^128 for encryption using a 128-bit key is infeasible). Having such a long password would make a slow-hash redundant. With the case of a 43-character password, I doubt that rainbow tables would be issue either.

Answer 2

It's not a very long password which matters, but a very random password -- length is just needed in order to make enough room for randomness.

We need slow hashing because passwords have relatively low entropy: it is possible to enumerate potential passwords with a good chance of hitting the password chosen by an average user. Slow hashing tries to make such an exhaustive search more expensive. If you use passwords with high enough entropy (ideally 128 bits, in practice 80 bits or so are enough), then exhaustive search in the password ceases to be a viable strategy for the attacker, and hashing no longer needs to be slow.

You don't have to make passwords very long to get a lot of entropy; if you use 64 possible signs (uppercase and lowercase letters, digits, and a couple of other signs), then 15 characters are enough to achieve a very comfortable 90-bit entropy, provided that you generate 15 totally random characters. If you generate your password as a concatenation of meaningful words, then you will need a much longer password to reach such an entropy level (but maybe a long sequence of words would be easier to remember).

When passwords have very high entropy, we tend not to call then "passwords", but keys. A "password" is something which fits in a normal human brain.

Answer 3

The answer is generally yes because hash functions are collision-resistant. But an attacker doesn't really need to find the exact password a user has entered, you only need to find a preimage that will give you the same output as the password. This of course prohibits him from using that password to get access to another website the victim is using (assuming a healthy password managment practice is in place).

Finding a collision basically means that "abc" may well have the same output as "supercalifragilisticexpialidocious" in which case the point of having a long password is moot. Good news however, the chances of finding a collision in most of the algorithms used (or should be used) in the real word are negligible. But a hash algorithm with a long password, especially when used with salting (whose whole purpose is to increase the attacker's search space) should definitely be more secure for practical applications.

Answer 4

The "slowness" of a hash is general measured by it's work factor. The underlying cryptographic hash function itself is rarely very slow, so the password hash function built on top of it artificially slows the crypto function down via iteration. For each hash derivation, there are a certain number of iterations that have to be performed. For example, a typical bcrypt hash may use a work factor of 12 (aka, $2^{12}$ iterations), meaning the attacker does $2^{12}$ times as much work as they would have if there were no iterations used.

To eliminate the need for the slow password function, account for the desired work factor of attacking the password in the password itself. If you want to match $2^{12}$ iterations worth of "slowness", add $2^{12}$ = 12 bits of work to the password itself. (12 bits, this rounds to the equivalent of 2 random alphanumeric ASCII characters.) The result is the same amount of brute-force work for the attacker.