by Viet Hoang
We have all been down this road: you are making a new account and you need to choose a password. You decide to use the same, easy-to-remember password that you have already used for every other account. You feel a little guilty because you know if someone gets ahold of one of your accounts, every other account will be compromised. Unfortunately, this has probably already happened. Avast, an antivirus company, has released a tool that will check a database of 30 million leaked passwords and search for yours: https://www.avast.com/hackcheck/. Over the years, many large companies have had large security breaches, such as Linkedin and Dropbox with over 117 million and 68 million passwords being leaked respectively (1,2).
Fortunately, all the passwords that were leaked were heavily encrypted. Before passwords are stored, they are processed using a hash function, which is a mapping between the input (password) and the output (hash) (3).
A hash is a string of seemingly random characters that is unique to every password. The hashed password is stored in place of the real one. When a user is trying to log in, their input is hashed, and if the resulting hash matches with the hash stored in the database, then we know they have given the correct password without actually needing to know the password.
Despite the apparent strength of storing hashed passwords, hackers can also compute the hash of any string and compare it with leaked passwords. With access to modern computing power, they are able to compare millions of possible passwords per second (3). More powerful hash functions can slow down this process, but it is of no use if the password is easy to guess.
What are bad passwords?
Any password under eight characters long is unacceptable, as it can easily be brute-force attacked (4). Suppose you have an eight-character password composed of only lowercase letters and numbers. There are 26+10=36 characters to choose from and you have to choose eight. Therefore there are 368 possible combinations, which may seem like a lot, but if the hacker is making millions of comparisons per second, then after a few days at most, your password is likely cracked.
There is still no guarantee of safety for passwords greater than eight characters. Ideally, people would use random characters as their passwords. Unfortunately, humans are lazy and predictable and use simpler passwords that are easy to remember. They use common words, such as “password”, or names. Some are more diligent and will substitute some letters with numbers like exchanging “E” for “3” or “S” for “5”. Most modern password cracking techniques take advantage of this and use dictionary attacks, which use a list of commonly used words, names, and substitutions to crack passwords.
How to construct an uncrackable password
A good password should be easy to remember and immune to both brute-force and dictionary attacks. Dr. Mike Pound from the University of Nottingham recommends that a password should be composed of four uncommonly used words (4). Any password of this structure should easily exceed eight characters, making traditional brute-force impossible. Furthermore, since there are approximately 170000 English words, the number of possible passwords is 1700004 which is far too large to use dictionary attacks. For even further complexity, words from different languages, misspelled words, and random symbol insertions can all be used as well. Putting everything together, below is an example password that is almost uncrackable:
The four words used are terracotta, portfolio, magnificent (in french) and abstract. Note that this specific password should never be used as it is now on a public website!