6

As I was thinking about storing password hashes in a database, it dawned on me that there might be hash collisions if there is no set maximum length for the password being hashed.

My understanding is that any password will generate a fixed-length hash (say 128bit). So, as soon as 2128 + 1 unique passwords are used, then we have a collision (due to the pigeonhole principle), while it is technically possible a collision occurs much sooner depending on the on the hash algorithm.

Granted no collisions exist until the pingeonhole principle is satisfied, it seems rather absurd to have approximately 3.403e+38 unique passwords stored, so I can understand perhaps it is negligible to impose a password maximum.

Is there a legitimate concern to not having a set maximum of characters for passwords (with regards to hash collisions)?

This is related to this question. As mentioned by curiousguy, is it true that the "impact of hash collisions is non existent"?

Improve this question
3
  • 2
    Why is a collision a problem for you? If you don't use a unique salt, you'll far more collisions from users entering the same password
    – Beat
    Dec 15, 2015 at 21:57
  • @Beat: i agree. Use HMAC and a good random salt. Chances for collisions are very small. End even if... how would an attacker know the afftected account without dumping your DB? In practice, weak passwords and security-unaware users are far mor risky than hash collisions.
    – marstato
    Dec 15, 2015 at 22:26
  • @Beat I'm concerned of two unique passwords producing the same hash. And I want to be sure there isn't something that I have not considered yet.
    – Nicholas Miller
    Dec 15, 2015 at 22:28

2 Answers 2

Reset to default
7

For starters, hash functions are supposed to be basically random, so the length of the input string doesn't matter. The probability that two random 3-character strings hash to the same thing is the same as the probability that two random 100-character strings hash the same.

For modern hash functions (SHA1,SHA2, not MD5) their structure is mathematically complex enough that we can't say very much about it algebraically. Also, the space of possible input strings, even of length 32, is so huge that we can't experimentally check all of them. So, we don't actually know how many collisions there are within the first 2128 strings (strings whose binary representation are 1, 10, 11... 2128). In theory there should be some, but as far as I know, we haven't uncovered any yet for SHA1 or SHA2. So your intuition that capping the length of the input strings to less than 2128 bits will eliminate the risk of collisions isn't quite right.

In any case, let's assume there are pairs of passwords within the first 2128 strings that have the same hash, the probability that you will hit one in your database is roughly <number of entries in db> / 2128.

The reason that

the "impact of hash collisions is non existent"?

is that 1/ 2128 is such an unimaginably small number that even if you wrote a program to generate random passwords until the sun ran out of energy, you still wouldn't expect to see a single collision by random chance. (If someone's actively trying to do a collision attack, then that's a different story).

Consider also how the risk of a collision (~ 1/2128) compares to the risk of a standard dictionary attack. According to the 2013 Adobe password leak, 1 out of 68 accounts on the internet use the password 123456. 1/68 is a MUCH bigger number than 1/2128, so the fact that a single guess of 123456 has a 1/68 chance of being right is a MUCH more important thing to worry about than theoretically-possible-collisions. Solution: allow (or enforce) long non-dictionary passwords, use a unique salt for each password hash, and don't worry about collisions.

Improve this answer
2
  • If 2^128 unique strings are shown to not have any colliding hashes under some hashing algorithm, would it then be safe to assume that the password limit should be imposed to whatever length is required to hold any of 2^128 unique strings (and perhaps minus one if all 2^128 are used before the maximum string value occurs)?
    – Nicholas Miller
    Dec 15, 2015 at 22:35
  • 1
    @NickMiller Sure, then we would be mathematically sure that collision attacks are impossible. However, it's almost a statistical certainty that any hash function with a 128-bit output (MD5, SHA1) will have collisions within the shortest 2^128 strings, there will be collisions, we just don't know what they are. (128-bit = 16 ASCII characters btw).
    – Mike Ounsworth
    Dec 15, 2015 at 22:41
4

There is little to worry about here but let's talk through some of this:

Granted no collisions exist until the pingeonhole principle is satisfied

This is not the case. Standard hashing algorithm are deterministic (otherwise they wouldn't work.) The passwords that will collide (and there are a infinite number with no limit on password length). The collisions are not related to the size of your database. For example consider my new integer hashing algorithm mod100. The implementation is that you mod an integer by 100 and the resulting remainder is your hash. If I have hashed the numbers 101, 201, and 301 I have 100% collision rate even though my set is only 3% of the hash space.

So sure there is an astronomically small chance that someone could guess at one of the other passwords that has the same hash as an actual real password. If the hashing algorithm is a good one, It's more likely, however that they will guess the actual password. Don't lose sleep over it.

Improve this answer
2
  • Yes this makes sense. To clarify, I was assuming the use of a hash function that is so collision resistant that 2^128 + 1 unique passwords were required to produce a duplicate hash. Of course, a weaker algorithms will be more susceptible to collision attacks.
    – Nicholas Miller
    Dec 15, 2015 at 22:23
  • @NickMiller Extra credit for thinking it through but I think it might help to bring things into the realm of human comprehension. No one can conceive of 2^128. Show me someone who claims to and I'll show you a liar (or a fool.) Try this problem: let's say I have a 100-sided die. How many times do I need to roll it before I expect to see the same number come up twice? Solve for that and then substitute larger numbers. I think this kind of exercise will help you gain intuition with regard to this kind of thing.
    – JimmyJames
    Dec 16, 2015 at 2:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .