The Math of Passwords
[Home] [Writing samples] [LinkedIn]

By Robert Delwood

Introduction

System administrators have been telling us for years to improve our passwords. Many of us recall requirements of four to six characters changing to six to eight, eight to 12, and now 12 to 15 characters, and the reset time is also changing from 90 days to often monthly or less. While we agree longer passwords are better, let's take a moment to understand why.

First, there are a few assumptions. Cracking passwords is not real time on someone's account. That's because most companies have a minimum password entry limit, usually one second per attempt, and as we'll see, that's more than plenty to stop anyone. Another reason is that sites usually lock accounts after about five failed attempts. No, if it's hacked, it's been done ahead of time. Thieves steal blocks of passwords at time, a fact publicized in the national media. And the thefts are staggering: Yahoo, 500 million 2016; another 500 million from Yahoo 2012, AdultFriendFinder 412 million in 2016, and even security minded Google, 1 million 2016, to name only a few.

Afterwards, they batch process these accounts to see how many how many passwords get hacked. The ones they can, they either sell or use. However, decrypting takes computers with considerable processing speeds, and that's our defense. Ridiculously simplifying a complex process, there are two approaches to hacking encryption: Brute force, and dictionary.

Brute Force

Brute force attack is the less elegant but more thorough. Here, the try literally try every permutation1 possible. For example, with a four letter lowercase password the attempts would be aaaa, aaab, aaac...aaaz, aaba, aabb...zzzz, for 456,976 permutations. With today's home computers being able to process 4 billion calculations a second, that would take a maximum of 0.00005 seconds. With still four characters but allow all upper, lower case, number and special characters (for 94 possible characters), it would form 78,074,896 permutations but still take a maximum of 0.009 seconds to crack. That makes your four character debit card PIN seem vulnerable all of the sudden. But using more characters makes the task harder.

Eight characters: Upper and lower case text characters (52 total).
Permutations: 53,459,728,531,456 or 5.3x1013.
Maximum hacking time: 13,365 seconds or about 3.7 hours.

Eight characters: Upper and lower case keyboard characters (a-Z, 0-9, ~ - ?) (94 total).
Permutations: 6,095,689,385,410,816 or 6x1015.
Maximum hacking time: 761,961 seconds or about 17 days.

16 characters: Upper and lower case keyboard characters (a-Z, 0-9, ~ - ?) (94 total).
Permutations: 37,157,429,083,410,091,685,945,089,785,856 or 3.7x1031.
Maximum hacking time: 2,986,547,476,483 centuries or 2.9x1012 centuries.

Clearly, your system administrator is on to something.

Using this to our advantage, it gets harder to crack with the longer passwords. 32 characters has 1.3x1064 permutations, and 128 characters has 3.6 x10252 permutations, or a maximum cracking time of 2.9x10231 millennia. At this point, more practical matters come into play. Clearly, we're neither going to remember a password of 128 random characters nor be patient enough to enter all that. For this, you'll need a password keychain that creates and enters passwords for you. Regardless how it's done, you get the point.

Dictionary

The dictionary attack uses a list of words. The namesake comes from the early days where a computer tried a list of words found literally in a English dictionary for passwords, with the premise that users would tend to use real words. Today, those lists go far beyond just the dictionary and include common misspellings, previously hacked passwords, variations, and word combinations. Don't think that using at signs (@) for o's (l@@k) or 3's for e's (3xampl3) fool hackers. Therefore a seemingly obscure word such as jubate, or slight variations like jubate01, would be as easily found as apple since they both appear in the dictionary.

There is also a brute force aspect as hackers combine multiple words. Straight text matching will make password1, an embarrassing password if you actually used it, a certain hack. MyBelovedJennifer wouldn't be much harder. It's three common words. That and it's already been found as a previously hacked password. It's on the list. Assuming an English dictionary of 175,000 words, with another 100,000 slang, and possibly several million previous passwords, the math of combining words becomes similar to brute force.

The trick, then, is to create words that neither appear in the dictionary nor have been used by anyone else. A 36 character random alphanumeric would do it. A randomly generated password like hHKirehd!DDj$3?7mmS8=l1.UedFiO_SWj9= is seemingly unbreakable. Even if they did find that exact sequence, how would they know it's the right one? But as people, we like our words. So use three almost random words, perhaps pyrophorusseriocomiclendrumbilate, may be an equally impossible hack. Remember, the canonical lists are based on previous usage, and it seems unlikely that pyrophorusseriocomiclendrumbilate has ever been used together before. Finally, add in special characters, not at word breaks (pyrophorus_seriocomic_lendrumbilate), but where special characters have no purpose being. With pyrop#horusserioc7omiclen^^drumbilate you likely have an as unbreakable password as you can get. In this case, the brute force method would have to hack a 37 character full keyboard word (expected brute force hacking time 8.1x1053 centuries), and a dictionary would need to have included that word in the list. Either case seems unlikely.

Summary

The tradeoff comes in remembering and entering these passwords. Good practice requires changing passwords often and not reusing passwords - ever. That's a point hackers take advantage of. People tend to reuse their favorite passwords, often for years, and sometimes exclusively. Therefore, if a hacker has your e-mail, usually a public piece of information identified as a user name, they can associate it to previously hacked passwords. Many professionals recommend using a password manager. One application creates and remembers each of your passwords, and you just have to remember one master password. The obvious risk is if that one password gets hack, but current technology favors this approach. Just keep in mind that this is an ever changing battleground and you may have to change practices from time to time.

While in theory any password can be hacked, if you typed the password using a keyboard and so could someone else, knowing how they get hacked helps you to create good passwords. At least it's possible to create very difficult passwords, and that may be enough - for the moment.

------------------

1 There is always confusion here. In a combination, order or sequence doesn't matter. ABC is the same combination as BCA. For permutations order does matter. ABC is different than BCA. Passwords always use permutations. Because of this distinction, we shouldn't call it a combination lock but a permutation lock.