password security

In choosing a strong password, length is more important than the size of the character space.

Consider the following example. Suppose you choose a password with 2 lower case letters, 2 uppercase, 2 numbers, and 2 special characters, for a total of 8 characters. (Assume that there are 15 special characters available.)

The number of such passwords is given by

 C(8,2)C(6,2)C(4,2)*262*262*102*152 ≈ 2.6E13

Suppose on the other hand that we limit our choice of characters to the lower case letters, but increase the length of the password from 8 characters to 10. We then have

 269 ≈ 1.4E14

or more than 5 times as many possibilities as before.

Notes: In the language of computational complexity, the number p of possible passwords of length L in a character space of size c is given by p(c, L) = cL. If we fix L, then p is a polynomial function in c, and if we fix c, then p is exponential in L.

Therefore, it's more important to choose a longer password or phrase than it is to use a larger character set, other things being equal. As a practical matter, however, it's wise to do both.

Increasing the length of your password or passphrase by even one character can greatly increase its security. In any fixed character space, there are many more passwords of length n+1 than there are passwords of lengths n or fewer.

For example, suppose a password of length 10 is chosen from the upper and lower characters and the digits. The character space is 62 and the total number of possible passwords is 6210 or about 1.45E17. Increasing the length of the password to 11 characters yields about 7.52E18 possibilities. One would need to increase the number of characters in the character space from 62 to 73 to achieve a comparable increase in possible passwords of length 10.

Taking another example, suppose you've chosen a password with 8 characters, all of them lowercase. If you double the number of possible characters by including upper as well as lowercase characters, then you've increased the total number of possible passwords from 268 to 528 = (28)(268) = 256*268, or by a factor of 256.

That is, there are 256 possible passwords in the larger character space than there were in the smaller space. Think of it as follows: the first character in the password can be upper or lower, so there are 2 choices in that place. The second character can also be upper or lower, again 2 choices, and so on eight times, for a product of 256 different passwords using both upper and lower for each password using all lowercase.

If, however, you double the length of your password from 8 characters to 16 characters, while sticking with lowercase letters only, then the total number of possible passwords increases from 268 to 2616 = (268)(268), or by a factor of about 200 million. That is, there are 200 million different passwords of length 16 for each password of length 8.

One way to understand this larger number is that each 16-character passphrase can be thought of as two 8-character passwords stuck together. For each of the 200 million or so 8-character passwords in the first 8 places, there are another 200 million possible 8-character passwords in the last 8 places. Given that the last 8 characters are chosen independently of the first 8 characters, the resulting number of passwords is the product of 268 and 268.

The fancy understanding of this is that the total number of possible passwords increases in polynomial time (c2) with a doubling of the number of characters in the available character space, but it increases in exponential time (in this case 26L) with an increase in the length of the passphrase.

cactuspear home
comments to comments at cactuspear dot org