Article: Security Words

Ever since I've been a kid, I've been fascinated with codes and cryptography. Of course, this topic has some great overlap with security, such as solving problems with storing, retrieving, and comparing passwords. So I was the obvious choice to implement the security engines for the software at the small start-up company that I work for.

Now this article is NOT about implementing security in Rails. This is a big and complicated topic that I do plan on writing about because implementing enterprise level security in Rails is not easy at all.

No, this is about another common topic. We often have to reset passwords for users. (We, of course, only store the hashed form of the password with salt so that no one get them!)

Now most of the time, assigned passwords are generated out of random sets of characters. This is great. A randomly generated password is very secure. But it is really hard to remember.

So I got to thinking. What if instead of passwords, we used a passphrase? That is to say, instead of joining together a series of individual characters, what if we joined together a fewer number of words? For me, at least, it is easier to remember a series of words than random characters, as I can come up with some visual or some rhyme to help me remember it.

For example, most sys-admins might give you a random password that looks something like 2qLzj94k. But what if, instead, they gave you a password like GreenRunDallasOrchard? I'd be willing to bet that you'd be much more likely to remember the 4 words better than the 8 random letters.

But this gives rise to the question: How many words would I need to string together, and from a dictionary how large, in order to match the security of a random string of characters?

Now For The Math

If you hate math, you may want to skim this section. Though I am pretty sure that if you are still actually reading this, then either you are a technical individual and like math, or you are a manager who was forced to read this by your IT staff because you just don't get it.

Normal passwords can be generated using all the letters (uppercase, and lower), digits, and a plethora of symbols. Looking at an ASCII table, it looks like there are, 94 eligible characters that one could use in a password.

Strangely enough, though, most random passwords are generated just with a subset of all letters and numbers, giving only 62 possible symbols. This reduction of 32 symbols leads to a drop of 5,877,349,279,825,920 passwords from all the possible 8 character passwords, which is a reduction in passwords of about 1/28th the fully possible 6,095,689,385,410,816!

Now to calculate the number of random passwords possible with just letters and numbers given password of a given length, we just raise 62 to the power of that length. Thus the following table hilights the number of possible passwords that exist with lengths of 4, 6, 8, and 16.

Possible Passwords Composed of Letters and Numbers

Password Length	Possible Passwords
4	624	14776336
6	626	56800235584
8	628	218340105584896
16	6216	47672401706823533450263330816

So the real question then becomes: If we had a pass-phrase of 4 words, how many words would have to be in our dictionary of random words to match the security of a random string of letters and numbers of a given length?

To calculate this, it is just a matter of the reverse problem from above. We know how many passwords we want there to be, and we know the length needs to be 4, so we use some n-th roots to produce the following table:

Dictionary Size Needed For 4 Word Passphrases to Match Passwords of a Given Length

Password Length	Dictionary Size
4	624/4	62
6	626/4	489
8	628/4	3844
16	6216/4	14776336

The Answer For The Math Weenies

So what do all those numbers mean? They mean that to reach the security of a randomly generated 8-character password generated just of letters and numbers, we only need to pull four random words from a dictionary of 3844 words, which is a completely reasonable feat.

Indeed, doing a quick
grep -Ec "^[a-z]{3,6}$" /usr/share/dict/words
on my OS X box seems to indicate that there are 29,041 words, none of which are proper nouns, that are from 3 to 6 letters long that could be used. And expanding the list to contain proper nouns results in a dictionary of 33,925 possible words.

Thus with a dictionary of 30,000 words, it would be possible to match the security of a random 10 letter password made of letters and numbers, with only a four word passphrase! And if we increased the number of words in the passphrase to five, it would add 24,299,190,000,000,000,000,000 passphrases, which is the same security level as a 15 character alphanumeric password!