Aug. 27, 2011, 6:48 p.m.

Password strength misconceptions

I have read countless articles where people tell you how bad it is to:

Their reasonings are:

  1. There are roughly 250 000 english words. That is what many people cite as the reason a dictionary word based password is easily hackable. It does not matter how long the word is, one only has to search the 250 000 possible passwords words and some combinations thereof.
  2. Same as above for phrases - a phrase with 4 words - regardless of length - is the same as 250 0004. Which is way less than the length of the password would led to believe you.
  3. Scanners can easily substitute symbols and numbers in dictionary words hence making it easy to crack said passwords. It is believed that personal details in you password makes it trivial to crack it because anyone can find out said details.
  4. Since using rainbow tables allows one to easily crack passwords with reduced complexity, not mixing in all possible symbols makes it easy to crack.
  5. Repeated constructs are easy to test for and reduces the entropy in your password.

But I applied some straight forward deductive logic, and here is what I realised. This assumes you are not Bin Laden or Hitler or someone that has all the 3 lettered acronym departments after you, and that you are english speaking...

The most important thing to realise is that once a cracker has your password hash, or attempts to break into your account, he has NO IDEA what your password is like. Assuming he is reverting to brute force or educated guess attacks, that implies he does not know the structure of your password. So…

  1. He puts his gloves on, and get his cracking programs, his multi core GPU's or Amazon EC2 cloud farm ready….
  2. Ummm… What now? If I were him I'd try to run a dictionary attack first. This should finish in under a second or two. This will catch 12345, password, iloveyou etc. So it fails…
  3. Next I try dictionary based with simple combinations with digits, like password123 etc. This takes longer… Say 8 hours. So it fails…
  4. Next I try to brute force it with lower, upper, digits and special characters. But since this can take forever, I limit it to 6 characters. This will take about 2-18 hours to search, depending on the computing power available. So it fails…
  5. Next I try with special knowledge of my victim, I use their name / friends names / birth dates etc. This should complete quickly. But it fails…
  6. By now I have wasted almost a day…
  7. So I try combinations of dictionary words and symbols and digits, such as IL0veYou!. This will take longer, even assuming you have access to a huge database of these words, it will still take several days at least. Remember, I can chose to only substitute one letter like Beaut1ful, B3autiful, B3aut1ful, B3aut!ful. Then, you can play with case - Beaut1ful, beAUt1ful, bEAut1ful etc. Then I can prepend / append symbols, like Beaut1ful!, $Beaut1ful#, etc. The combinations are endless. I do not believe any modern computer has the hard disk space for storing this dictionary, and brute forcing it will take too long. So it fails…
  8. Now all that is left is to let the brute force program run at 8 character length say, and a basic set of characters, say upper/lower. This will take about a year on modern hardware. So this fails...
  9. By now I decide to take a hammer and go get her password using pure coercion.
  10. So she (Jennifer) tells me under torture that her password is: brullende

    Which is a simple password, no uppercase, digits and no symbols except for one space, and no words out of the english dictionary yet it is uncrackable by the procedures I followed above. Why? She decided not to use English words. Sure you could have extended the dictionary search to other languages too but would a cracker? There are approximately 6900 languages in the world. Assume only 10% of those have truly unique words. English has about 250 000 words. Assume then very roughly that each language has half the amount of words of English, then the total amount of words to be found in some dictionary or another to be approximately (10%)6900(50%)*250000 = 86 million words. Considering that you can alter each word by using mixed upper/lower case, and to simplify things I am going to assume an average word length of 5 characters and ignore the fact that exponential values cannot be averaged using linear techniques, that means roughly that each word can have 25 combinations, thus 86 000 000 * 25 = 2.7 billion combinations. That is a 13GB word list right there…. Lets presume that a wordlist exists with all these words in it. Let me change that password to: brull3ndE

    To crack that, brute force is out too since the length exceeds 8 characters. I have merely added an uppercase letter and a simple substitution for one of the letters. To crack that, lets assume the cracker has extended his word list with all combinations of words including common number and symbol substitution. Lets assume the following letters are commonly substituted: abeilos by 4831!05 respectively. Now I know I am simplifying but it is Sunday and trying to illustrate a point. Assume a letter frequency of a = 8%, b = 1.5%, e = 12.7% , i = 7%, l = 4%, o = 7.5% and s = 6.3%. That means each word consists of 8% a's, 1.5% b's etc. Each letter can be substituted for another letter, a can be substituted with 4. The math is escaping me now, but it is clear from this that the 2.7 billion words suddenly explodes into the trillions. That is a 50TB word list… Not going to happen. I have not even considered combinations such as prefixing/affixing special symbols. Sure you can calculate these substitutions on the fly, but you would still need to test trillions of passwords. Assuming a very fast cracking rate of 1 000 000 passwords per second, it would still take 115 days… If I start combining words… Like: brull3ndE p4ddas

    the attacker needs to consider combinations of this list. Lets assume no more than 4 words that are being combined. That expands the list to say 10 trillion4 = 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000. That cannot be cracked. Even if you just stick to normal words with no substitution - all lowercase, with 4 words that still allows for 86 000 0004 = 54 700 816 000 000 000 000 000 000 000 000 combinations… Uncrackable. Heck, even sticking with all lowercase english only words, for a 4 word phrase, there are still 250 0004 = 3 906 250 000 000 000 000 000 combinations, and at 25 million passwords a second that will take 5 million years.

I do agree with the following though:

  1. Never chose a password of length less than 8 characters. Assuming you mix lower/upper/digits and symbols, cracking a password of length 8 on a very fast machine will take many years (for AES, or several days for MD4), however rainbow tables can make that moot. Combined with other strategies as mentioned above, it is best to stick to at least 8 characters.
  2. Do combine different character classes - use upper/lower/digits and at least one symbol, preferably not ! as it is very common.
  3. Do not use dictionary words unless you use them in an uncommon phrase.
  4. Do not use personal identifiable information, and if you do, make sure the password's still adheres to above recommendations.
  5. Do not use common phrases / well known numbers.
  6. Do not make the password too long or complex, otherwise you will forget it.
  7. Pick something that makes sense to only you. Like oneDIESwith0ut air could work… That password cannot be cracked with wordlists, rainbow tables or by brute force.

If you really want a strong password that cannot be brute forced, and that is easily remembered, simply use a nonsense phrase. A good example is:

dogs cannot eat green