# Is there a length beyond which increasing password length provides no additional security?

Assuming that the password is stored hashed and salted, and that it is a string of random characters, is there a point where adding to password length doesn't add security?

Since the hash will have a constant length, there are a finite number of possible hashes. So I would assume that at some very long length, the probability that a password's hash collides with the hash of a shorter password starts to climb, until we get to a length where all passwords have collisions with shorter passwords.

-

## 3 Answers

The strength of a password is a measure of what it could have been. That's how passwords work: they are something which a given user remembers, but is unknown to outsiders. How much unknown ? That's the tricky point.

If you consider a password consisting of 7 random letters (uppercase and lowercase) and digits, where each sign is chosen randomly, uniformly, and independently of each other, then there are 627 = 3521614606208 possible passwords and they all have the same probability of being chosen; so, for attackers, the best possible strategy is to try them all (no order is better than any other) until a match is found. On average, attackers will try half the space of possible password (hence 1760807303104, in this case) before hitting the right one.

So the strength of a password does not come from what it is, and in particular does not come from its length. The password length has no direct relation to password security. What makes a password strong is its randomness; and that's, strictly speaking, a property of the password generation method, not of the password itself. The indirect relation of length with security is that you need some room to exercise randomness: while a very long password is not necessarily secure, a very short password is necessarily insecure.

Moreover, if you create your password by accumulating randomly chosen elements (random letters, random words...) then randomness is increased by accumulating more of them, as long as they are chosen independently of each other (you don't get more randomness if you repeat four times the same word). In that sense, you may have the impression that length makes strength; but that's an illusion. Randomness makes strength -- and just happens to need space.

How much randomness do you need ? Enough to deter attackers. How many passwords an attacker can try per second depends a lot of the context. If the password is the PIN code for a smart card, then the attacker can try 3 codes, and no more (after 3 wrong PIN, the card locks itself permanently). If the attacker must talk to a Web server for each password try, then he will be able to try as many passwords per second as the server is willing to accept, based on the server CPU power and configuration. If the attacker knows a hash of the password, then he can try as many as he can based on his budget (for a simple hash function, this can range in the billions per second).

For each context, there is a limit to the number of passwords the attacker may try. If his chances of hitting the right password within his budget are too low, the attacker will deem it "not worth the effort", and then you win. You do not need to get more randomness than this point.

Since hash functions have a finite length, there is also another limit beyond which it is useless to increase password randomness, but it is much farther. It is not about collisions, but about preimages. Let's put figures under it. A realistic attacker, with a lot of budget, and faced with a simple hash function, may try up to about 270 potential passwords. We are talking about a budget of some millions of dollars here, and also a rather patient attacker (he will accept to spend a few weeks on that password). There are good reasons why this figure won't raise indefinitely with technological advances. Let's consider that the hash function has an output of n bits (e.g. n = 128 for MD5). The attacker's goal is to find a password which, when hashed, yields a given hash value; he does not need the password which was initially used, just a matching password. He has two attacking strategies:

1. He can try "potential passwords" that the human user may have come up with.
2. He can try random passwords until a match is found.

Strategy 1 will have cost P/2 where P is (more or less) the number of potential passwords that the user may have chosen. If P is beyond 271 then that's too expensive for the attacker.

Strategy 2 will have cost 2n-1. If n is greater than 71 then that's too expensive for the attacker.

Even the oldest, most basic hash functions like MD5 have an output size which is more than enough to make strategy 2 unworkable (MD2, MD4, MD5 have output size 128 bits; SHA-1 and RIPEMD-160 offer 160 bits; SHA-256 has 256 bits). In other words, the fixed hash output size could limit security only if it was below 70 bits or so.

For more on the subject of password randomness (often called "entropy"), see this answer. For more on correct ways to do password hashing (in particular, to do slow hashing, with salts to prevent parallel attacks), see that answer.

-

To expand a tiny bit on Tom's excellent answer, the hard limit for useful length, assuming random characters, is the size of the resulting hash (eg: 128bits is about 21 random characters, assuming you use upper, lower, numbers, and basic symbols, and just English characters).

Real passwords, though, are much more bounded by construction mnemonics, and the ability of people to remember them. As Tom said, what you really want is 128 bits of random entropy (assuming 128bit hash), which can take far more than 21 characters to generate in a password with that much entropy which someone can also actually remember. In practice, few user-memorized passwords will have this much entropy.

-

Absolutely, I've given a thought to that too. Specially after reading this paper:

It's a study made by security researchers Wang and Yu, who developed a technique to force collissions between md5 hashes (And according to them HAVAL, MD4, RIPEMD and SHA0)... And it is a widely studied topic when it comes to colliding certificate hashes

Although, I believe, hash collissions are an issue primarly for certificates and files rather than passwords, since they are so short (comparing it to a file) their collissions are far less likely.

If we are talking strictly about passwords, this is the reason why authentication is slowly migrating to two factor auth. Passwords and their human keepers are simply unreliable for proper authentication. Not because of their weakness and hash-collission risks, but because of a much simpler factor: the humans behind them.

-
Collisions on hash functions have nothing whatsoever to do with password security. When passwords are hashed, they rely on preimage resistance, which is something completely different. – Tom Leek Mar 26 at 0:13