Password Entropy

Passwords, ugh.  The very word causes pain.  It invokes feelings of aggravation and despair, memories of fighting computers and IT admins.  And still, despite their flaws, we have yet to universally assign any other means of simple authentication, so we’re stuck with them.

And, we constantly argue over what makes a good password.  In the midst of this debate, one man and his famous comic surged through the internet:

XKCDIf you don’t know of XKCD, shame on you.  Go there now and revel in its wonderfully sophisticated humor.

In summary, the argument’s premise is that words, being easier to remember, are better suited for passwords as their method of authentication relies upon human memory.  And indeed they would be, but it would take significantly more words than could feasibly fit into a password field.  Why?  Because of dictionary attacks.

A dictionary attack works by guessing known words.  Even if the words are obscure, they are known.  I will elaborate:

For this example, I will use the word hello.  Hello is 5 letters.  The logic behind using words for passwords is their per character entropy.  5 letters, all lowercase, represents 26^5 possible combinations, or 11,881,376.  With dictionary attacks, however, the word in itself becomes a single “character”.  According to the Oxford English Dictionary, there are 171,476 in-use words in the English language.  This translates a password, consisting of one word, to having one of 171,476 possibilities–significantly less than the 11,881,376 previously mentioned.

So why not stack random words?  Well, in the comic’s given example of correcthorsebatterystaple, there are 4 words.  171476^4=864,596,308,417,753,000,000 (approximately, since Excel is truncating numbers to 15 significant figures).  So we’ll say 8.65E+20 (using Excel notation).  How secure is this?  I honestly have no idea.  This is where the argument turns ugly.  So I will pass on forcing an opinion upon you and instead stick to providing information.

Looking at the ASCII chart, there are 95 usable characters.  Taking 95^X then, the tipping point is 11 characters.  This, compared to the above example, has 5.69E+21 possible combinations, significantly more entropy, yet significantly fewer characters (11 vs. 25).

The argument then would be to add more words to the password.  And I would agree, except all too often we encounter password field limits.  And besides, how many random words for how many websites could you remember anyway?  Once you fail to remember one, you completely lose the benefit of the word method, in which case why not make a higher-entropy password instead?

Searching the Internet for consensus on password size, I find the general rule is to use 12 characters.  This equates to 5.40E+23 combinations for ASCII, which means we need five words to achieve at least that number of combinations with the word method.  That’s a lot of words to remember for every website.

Another point that bears mentioning is that we need to consider the lowest possible entropy denomination, so word length does come into play, although not significantly.  Specifically, a word has to be at least 4 letters long, otherwise its number of combinations falls below 171,476 (26^3=17,576).  Therefore, if you think you can get away with stringing together 5 short words, you’re only getting the combined strength of the letters themselves, meaning you’d need 17 letters to at least meet the entropy of a 12-character ASCII password.  And remember, you don’t get more entropy by using longer words, so correcthorsebatterystaple is 8.65E+20, not 2.37E+35.

We’re gonna need a bigger column

And no, mixing lowercase and capitalized letters, or even number substitutions, does not impact a word’s entropy in a meaningful way, as dictionary attacks are aware of this trick.

Finally, the word method is assuming any word in the OED might be used, when in practice there are estimated to be only 100,000 common English words.  I was erring in favor of the word method, but in practice it’s much weaker than this math suggests.

Conclusion: in order to supply enough random words to a password chain to achieve the minimum industry-recommended level of entropy, you would need to supply 5 uncommon words, which will likely defeat its own purpose of being memorable, not to mention it will likely exceed the password length limit of many servers.

Whatever method you choose to use, I think it’s safe to say that we can all agree that passwords just plain suck, and with the exponentially increasing computational power of Moore’s Law, it’s only going to get worse.