3

Conventional password advice encourages the use of long passwords with the rationale being hashing the entire password space (rainbow table or brute force) takes longer with each character added.

With current/secure hashing algorithms, bcrypt or similar, and dynamic salts, is it even remotely possible that "A super long passphrase, and easy to remember!" could be cracked by brute force because "Rand0m" coincidentally produces the same hash?

I'm aware this is statistically beyond having the same hash as a coworker. I am wondering if any password hashing algorithms have ever been shown to produce the same hash for different levels of entropy, therefore making a very strong password potentially breakable by brute force via a weaker one, and if the modern algorithms actively protect against this.

|improve this question
  • 2
    if a hash is well-designed it could produce the same hash from different texts, but it's "unlikely" – dandavis Dec 10 '16 at 9:32
3

MD5 has had numerous collision issues, even to the point that someone was able to create a valid code-signing certificate for Windows. But even with this, collisions are intentionally created. When examining plaintext password dumps, you'll see that passwords don't tend to have much variety: they tend to use lots of lowercase latin characters, and up to 12 or so (or include numbers in predictable places, like 1 at the end). This doesn't give very good odds of generating a collision at random, because your input set is rather small. That is, while it may be possible for a researcher to find two english phrases that map to the same md5 hash, the chances of either one of those (much less both) being used as a password are quite small.

With more modern algorithms like SHA-2, SHA-3, bcrypt, etc., we don't have any known good weaknesses that would lead to generating hash collisions. In addition, the digest sizes are much larger (MD5 produces a 128-bit hash, while SHA-256 produces, as the name suggests, a 256-bit hash), which greatly reduces the chance of collisions. You can compare this to simple checksum hash algorithms like CRC, which is generally used with a 32-bit digest. Having an extremely low probability of hash collisions is one of the important properties of a cryptographic hash function that separates it from the more general class of hash functions.

|improve this answer
3

A bcrypt hash is 184 bits, so there are 2^184 possible hashes. That is way more than the number of atoms in the earth. You picking a password with a hash that matches another hash is like me picking a random atom in the earth, and then you by accident picking that exact same atom! You are literally more likely to die from a comet hitting earth tomorrow.

|improve this answer
  • 1
    You are more likely to die from every comet in the Oort Cloud simultaneously being sent on a collision course with Earth and arriving all at the same time. – Stephen Touset Dec 10 '16 at 4:31
  • 1
    Actually, 10^80 is almost 2^270; 2^184 is a good bit less than that -- but it is roughly atoms in our solar system, which is as far as any human can realistically pick from since traveling to other stars isn't practical at present. @StephenTouset: I wanted to try the probability of your computer spontaneously decaying into unstable isotopes and blowing you up, but couldn't easily find numbers. – dave_thompson_085 Dec 10 '16 at 4:32
  • 2
    This does assume that all hashes can be generated (impossible to check) and that there are no biases in the output (difficult to check). However, even if 10% of the output space is unreachable, the chances of collision are really remote! – Matthew Dec 10 '16 at 8:55
  • @dave_thompson_085 Thanks for pointing that out - my bad! Have fixed it by changing to the more modest earth. – Anders Dec 10 '16 at 10:36
  • 1
    @Matthew Even if only 10% of the output space is reachable, the chances of collision are still really remote! 10% being reachable (and knowing exactly which 10% is reachable) means you reduce the search space by about 3.3 bits, as log2(10) ~ 3.3. – a CVn Dec 10 '16 at 12:47

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.