Is variable length password generation more secure?

Recently I was posed an interesting question: When generating passwords for many systems, is it better to set all the passwords to the same length (the max), or to allow the passwords length to vary a couple characters? The argument was that the number of possible passwords is increased if you allow variable length passwords, which makes it harder to bruteforce.

This took a lot of research, so I brought it here to the blog rather than let it languish in a sent email forever. Note this is from a situation where you control the password generation. This is not applicable to user-provided passwords.

I am also assuming that the passwords are random characters and the attacker knows this because that was the original concern of the customer. So I will assume a classic brute force, Markov optimization would not benefit here for example.

Allowing shorter passwords does increase entropy, but it makes a bruteforce search easier. You would think intuitively that adding more options is better, but not in this case.

First, we can approach this logically. Let's assume these are passwords for Domain Admin accounts. Say the range is 12 to 16 characters. If truly random, then 1/4 of the passwords should be 12 characters long, and another 1/4 of the passwords should be 16 characters long.

Here is the first problem, and the original customer concern leaks through: for most privileged accounts, each account is only as strong as the weakest account. A 12-character password is weaker than a 16-character password. If you crack the 12-character password of a Domain Admin account, you can reset the password of the 16-character account that you weren't able to crack. Each password is only as strong as the weakest password.

Perhaps in your case, it doesn't matter if one account gets compromised, but you want to limit the total accounts that can be cracked in a fixed amount of time. Adding variable length passwords should increase entropy, right? Wouldn't that make it harder?

Still, the answer is almost certaintly no. To understand why will take a little bit of math, bear with me. We’ll assume 12 to 16 characters, alphanumeric, mixed case. This gives 62 possible chars for each position.

n=26+26+10=62

All the passwords shorter than the maximum length make up approximately 1/n percent of the total passwords. Assuming the length is k, we can figure out the fraction of all passwords in the keyspace that have a length less than k:

(t(k-1))/(t(k))=(n^k-1)/(n^(k+1)-1)≈1/n

For our 62 possible chars, that gives 1/62≈1.6%. For a 16-length character password, that means allowing 0-16 characters instead of just 16 characters adds 1.6% more passwords to brute force. This is where the entropy increase comes from.

What if we limit this to 12-16 characters? To calculate the percentage difference between 0-16 characters and 12-16 characters I just used WolframAlpha as a cheat:

(62^16*0.016-62^12*0.016)/62^16≈1.5999998

Allowing 12-16 characters reduces this to 1.59% percent, which is basically a rounding error so I’ll just use 1.6%. You may think that seems small, which it is! This is because it's not exponential to allow variable length, it only adds 1.6% more passwords to crack in this case. The number of possible passwords added by allowing a variable length of 0-12 is dwarfed by 1.6% of the 13 character passwords. We're used to exponential gains when dealing with password keyspaces, but we don't get that here.

What is exponential here is the increase in password length, which we are giving up by using variable length. It doesn’t even matter if the attacker knows the length range, because limiting the brute force only give a minuscule difference (<0.01%)! Why even bother? If they don't know the right length, the cracker will try 1 char length, then 2 char length, and so on, so it doesn’t matter if they know the max length either. After they’ve finally gotten to 17 chars, all your 12-16 hashes are cracked anyways. If we allow a Markov or other brute forcer it may try a few more passwords, but again that only adds 1.6%.

To further illustrate this, each time you add another character of length you are multiplying the current password keyspace (number of passwords) by n, which in our case is 62. So that’s 6200% more passwords to crack each time you add another character.

When you add variable length passwords, you get 1.6% more passwords to crack. Hooray! But if you go from having 16 characters to between 12 and 16 characters, on your weakest 12-character password you now have lost 99.99% of the keyspace of your strongest 16-character password. Boo.

That's not a typo, it really loses that much. You can calculate the percantage loss in password strength between 16 to 12 with:

1-1/n^j =1-1/62^4≈0.9999

Where j is the amount of characters you are losing.

The only time this strategy would work is if you have to crack ALL passwords to win anything and at least one password has 16 characters. One in every four passwords will be cracked after 12 characters. Only when they pass 75% of passwords cracked do you start to see any gains from adding variable length, because by the point they've reached 75% of passwords they have had to crack an extra 1.6% passwords.

If you had just used 16-character passwords, you would have no passwords cracked at that point. In other words, always use the max length you possibly can.

Because when they've finally gotten to 16-character passwords, we will all already be dead.

Some extra useful math if you want to check the 1/n calculation manually:

Calculating the total keyspace for a fixed length password is easy enough:

t(k)=n^k

Where k is the length, and n is the possible chars in each position (62).

We can calculate the total keyspace for variable length passwords with the following series:

t(k)=n+n^2+n^3+⋯+n^k=∑(j=1)^k,n^j=(n^(k+1)-1)/(n-1)

I found some of these formulas from this great StackExchange Crypto answer.

Shout out to my home-boy Euler.