22

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.

4
  • 6
    ... you brute force the hash, so the reasons are not different than live login brute force. And just because something is not 100% perfect does not mean it is useless... "mitigates" yes, but that does not mean "eliminates all risk in every conceivable form".
    – schroeder
    May 25, 2021 at 14:29
  • "Password length/complexity only mitigates a brute force attack, correct?" no, dictionary attacks are also mitigated.
    – northerner
    May 27, 2021 at 10:54
  • I'm not clear what point the question is trying to make. I think it is that since it would be equally hard to reverse a short password as a long password from a given hashing function, what point is having a length requirement. Though I think some answers interpret it differently.
    – northerner
    May 27, 2021 at 10:57
  • @northerner rainbow tables typically have full coverage of short and medium passwords, but not so much for long passwords. (Of course, "medium" has been getting longer as disk capacity and CPU power have increased and time passed.
    – RonJohn
    May 27, 2021 at 13:40

4 Answers 4

48

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.

11
  • @thegr33k this is actually a better answer than mine. I will not be offended if you move the Accepted Answer checkmark to this answer :) May 25, 2021 at 17:29
  • "half of the key space" is not quite correct, although I imagine you meant the right thing. Not sure how to rephrase it nicely, but that should be something with half the entropy of the key space May 26, 2021 at 1:25
  • @DreamConspiracy Actually, as kelalaka explained, in cryptographic terms, we are looking for a preimage, not a collision. For a preimage, you would (on average) have to search half the keyspace (2^(n-1) for an n bit hash).
    – nobody
    May 26, 2021 at 8:28
  • @DreamConspiracy square root of the size of key space is accurate (which would be half the bit entropy of the key). People may not get it exactly what it means well at a glance. But it is still better than the misleading one in the answer May 26, 2021 at 8:53
  • Besides for weaker hash functions like MD5 and SHA1 there are ways to create collisions far more efficiently than hashing a lot of strings and relying on "birthday bound" expected number of collisions. But it requires putting some random looking collision blocks which may not work with passwords. Still, if an attack is possible by creating collisions (remember that the attacker needs to control both the passwords in this case), and first step is H(password||salt) with non-collision resistant hash H, they can use the random looking collision blocks as the salt. May 26, 2021 at 9:00
26

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.

2
  • How are collisions relevant to this question? The probability of a collision is fixed. A collision is a certainty given a large enough population and a simple enough hash. A password that works is a good as the actual password.
    – mckenzm
    May 28, 2021 at 5:14
  • @mckenzm Yeah, "collision with a much shorter string" is probably better described as a second-preimage. I prefer to mirror the language that the OP used in the question when it's clear from context, which I think is the case here. May 28, 2021 at 14:11
12

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(2n/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(2n) 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.

1
  • Of course "slowing the attack time" is relative. Resources will scale to make this time tolerable, given the means to pay. Using fields we can delay attempts in increasing intervals. But having the hashes in hand is another matter.
    – mckenzm
    Jun 16, 2021 at 4:15
0

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.

1
  • The Birthday paradox is a vast overestimate. Take a 256 bit hash. According to the birthday paradox, there are likely two 128 bit keys with same hash. But if you take 2^40 actually used keys, you can only expect some 216 bit key with a hash matching any of them.
    – gnasher729
    May 27, 2021 at 22:07

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.