Does password length / complexity make any difference if hashes are leaked?

Question

Password length/complexity only mitigates a brute force attack, correct? In the event of a hash leak, since any algorithm is a fixed length, there could potentially be a pre-image* with a very short / not complex string? Salting notwithstanding.

Answer 1

Say you have a dozen people on a beach. You get each person in turn to pick a grain of sand at random, and without looking at it, write their name on it and throw it back randomly onto the beach.

What are the chances two people write their name on the same grain of sand?

The size of the key-space for human-generated passwords is around 40 bits according to Wikipedia. The key-space for most modern cryptographic hashes is 128 or 256 bits.

This is such an astronomical difference in the sizes of the two sets, the overwhelming majority of possible hash values are not reachable from a typical password. The chances of a collision are like two people picking the same grain of sand on a beach.

To reach a collision, you would typically have to iterate through half of the hash key-space. In doing so you would have to generate a password that is likely to be far longer, and far less like a human-chosen word, that the actual original password would have been much easier to guess.

Answer 2

there could potentially be a collision with a very short / not complex string

That's true.

It's possible that your password happens to have a collision with a much shorter string under the specific hash function and salt that was used. But "possible" is different than "likely"; crypto security proofs rely on a very strict definition of "likely".

(update) As @lynks points out in their answer, a brute-forcer guessing the password correctly on the first try is astronomically more likely than stumbling on a hash collision, let alone a collision where the other value is super short.

On average (ie not counting luck, godly intervention, etc), the attacker will need to iterate through some sort of extremely large password dictionary.

Answer 3

In the event of a hash leak, since any algorithm is a fixed length, there could potentially be a collision with a very short / not complex string?

Collision is not the correct term in terms of cryptography. In the hash term, the collision term is used for finding two different inputs x and y such that hash(x) = hash(y). In this case, the attackers are free two choose both of the inputs. Therefore this is not your case. The cost of the collision attack is O(2^n/2) with 50% probability for hash functions of n bit output size due to the birthday attack.

The correct term is finding a pre-image x for a given hash value h such that hash(x) == h. One should be careful with the usage of a pre-image, due to the pigeonhole principle, as you noted, we expect more than one input value for any hash value. Finding any of them enough since they all have the same hash value. The generic cost of finding pre-images is O(2ⁿ) for a hash function with output size n. The usual pre-image search is executed with random n inputs.

In your case, the password is very short then you fall into the short input space problem for hash functions. In this case, a direct search on the input space will found the exact pre-image.

The pre-image can be easily parallelized. If salt is not used a short password was an easy target of the Rainbow tables. Even the salt is used, the very short password is an easy target for the big agencies.

Password length/complexity only mitigates a brute force attack, correct?

Not exactly. The deployed password hashing algorithm is also important. For example, if you use PBKDF2 with iteration 100K then you slow the attack time. If you use Argon2, then you have more parameters to slow the attack time like high memory demand (memory-hard), parallelism, and iterations.

The memory hardness is to prevent the massive ASIC/GPU search, and the parallelism is about multiple threads. With these, you can reduce the attacker's powers and you even can estimate their timing.

If we assume the collective power of the bitcoin miners as the largest computing entity, we can start to quantify. In a year they can calculate around 2^93 SHA256 hashes. If you use 100K iteration then they can reach most 2^76 in a year. If you start to consider that most of them use ASIC and GPU, then they almost will be useless again the Argon2. The GPU/CPU timing can be found in the hashcat site or just search like hashcat PBKDF2 GTX 3080, (an example).

Does password length / complexity make any difference if hashes are leaked?

So the exact answer can be given by the password length and complexity and the deployed password hashing mechanism.

If the password is really short and not complex it is probably in the pwned password list that currently contains around 613M pwned password. It is a little matter of time to be tested with a good database. If not in the list, it is just another search. A single GTX 3080 GPU can reach 2^48 SHA-512 in 18 hours. The real metric needs the password hashing algorithm and password length / complexity.

---

Forget about old password methods, use word-based methods like dicewire or Bip39. And the better alternative is to use a password manager like keepass or 1password, or... In this case, you will need only one password with good strength for locking and unlocking the password manager, and the rest is handled by the managers.

Answer 4

Password length/complexity only mitigates a brute force attack, correct?

yeah pretty much (it also helps against mutating dictionary attacks, like if it tries "horse1"-"horse999" but your password is "horse0999", the extra password complexity would defeat that specific mutation)

In the event of a hash leak, since any algorithm is a fixed length, there could potentially be a collision with a very short / not complex string?

not beyond the Birthday Paradox, which is really not a problem with password-hashing-grade hashes.