Last time, we looked at how passwords work. To confirm your identity, companies salt your password, they hash the salted password, and they check your hash. (For brevity, I won’t mention salts anymore. Assume that salts are used.)

We left out 3 important questions.

1. Can a hacker find out our passwords from hashes?

Yes and no. We will see that a hash function that is designed well acts like a trapdoor. We can change passwords to hashes, but there is no way to change hashes back to passwords. However, the hacker can still make guesses at our passwords and check which ones result in the stolen hashes. We call this an attack. I will cover 2 ways to make an attack.

2. Can the hash function stop attacks?

Yes, a hash function that is designed well makes attacks difficult. I will explain what I mean by a good design.

3. What can we do to protect ourselves?

We can’t completely rely on the hash function to protect us. We have to be vigilant, too. I will show you how to create good passwords and keep your accounts safe.

3. Attack

Suppose that a hacker has stolen the hashes. It’s impossible to change hashes back to passwords, so the hacker has to make guesses at the passwords and check which ones result in the stolen hashes. There are 2 ways to make an attack.

a. Brute-force

The simplest way is to try every possible combination of letters, numbers, and symbols in an orderly fashion. We call this a brute-force attack. For example, the hacker can try “aaa…a,” then “aaa…b,” then “aaa…c,” until the very last one.

This attack is slow, but guarantees finding all passwords if the hacker had infinite time. That’s impossible, of course, but the hacker can still run a program to make billions of attacks each second. A brute-force attack can easily find short passwords.

b. Dictionary

A better way to attack is to exploit the human nature. We tend to use certain words and styles when we create our passwords. The hacker can look at a list of common words, called a dictionary or wordlist, and manipulate the words according to some rules. For example, “password” is often used, so the hacker can hash that word and every variation of it, such as “Password,” “password1,” “passwords,” and “p@55w0rd$.”

A dictionary attack doesn’t guarantee finding all passwords, but is much more effective than brute-force in finding long passwords. The hacker can achieve higher success by combining a dictionary attack with brute-force or other attacks.

4. Hash design

Now that we know how attacks are made, let’s look at ways to stop them. One way is to design a hash function well. The hash function has to meet 4 requirements.

a. Trapdoor

First, the hash function must act like a trapdoor. We can change passwords to hashes, but there is no way to change hashes back to passwords.

(Mathematically, there is no inverse function.)

b. Difficulty

Second, hashing can’t take too little or too much time. If it takes too little, the hacker can easily make many guesses. If it takes too much, we can get fed up with the long login. The hash function must be just difficult so that hashing takes the right time.

c. Collision resistance

Third, two different passwords should never result in the same hash. We call the event when they do, a hash collision. We talked about its danger last time. The hash function must show collision resistance.

(Hash collisions are inevitable, because hash functions allow passwords to be infinitely long, while hashes are finite in length. By designing the hash function well and limiting the password length, we make the probability of a hash collision close to 0.)

d. Avalanche effect

Lastly, even a small change in the password must create a huge change in the hash. We call this an avalanche effect. An avalanche hides any patterns that the hacker can exploit to guess our passwords.

5. Safe practice

The first way to stop attacks is to design the hash function well. The second way is for us to be diligent. Here’s how to create good passwords and keep your accounts safe.

a. Good passwords

When you create passwords, simply ask yourself two questions: Can they survive a brute-force attack? Can they survive a dictionary attack? If you have good passwords, you will answer yes to both.

To survive a brute-force attack, choose long passwords. The longer, the better. As a rule of thumb, use at least 12 characters. To survive a dictionary attack, don’t choose common words and any variations thereof. Be unpredictable by creating passwords that mix letters, numbers, and symbols really well.

b. Password manager

This comic shows the pitfall of asking you to create your passwords. What you think are hard-to-guess passwords—because you used letters, numbers, and symbols—are actually easy to a computer. It’s human nature. We are bad at remembering a random mix of letters, numbers, and symbols, so we end up using certain words and styles when we create passwords. Remember, the key to survive a dictionary attack is to be unpredictable, and we are bad at being unpredictable.

A better solution is to create long passwords by combining multiple words. We call these passwords, passphrases. Passphrases are easy to remember. They are also hard to guess, but only if you chose the words randomly. Again, we are human. We are bad at being random.

The best solution is to let a computer create your passwords. A password manager is a program that can create random passwords. It will also keep your passwords safe and even enter them for you at login. You just have to remember one good password—your master password. Always use a password manager.

c. Safety rules

Now that you can create good passwords, let’s work on keeping your accounts safe.

First, check if your accounts are safe. You can use sites like Have I Been Pwned? to see which accounts have been compromised. Change your password if necessary.

Second, make sure that each account uses a different password. This is trivial if you use a password manager. If one account is compromised, the others will be still safe.

Third, never share your passwords with anyone, especially over emails and texts. You don’t have control over who else can read them.

Lastly, use two-factor authentication if it’s offered. You provide two evidence to prove your identity so that it’s harder for a hacker to pretend to be you. One is your password and, often, the other is your cell phone, something that you use everyday.

6. Conclusion

Let’s review the three questions that we had posed in the beginning.

First, we looked at how a hacker can find out our passwords. A brute-force attack can find the short passwords by trying every possible combination, and a dictionary attack can find the long ones by trying common words and their variations.

There are two ways to stop attacks. One is to design the hash function well. The hash function must act like a trapdoor, must be just difficult, must resist hash collisions, and must create avalanche effects.

The second way is for us to be diligent. Always use a password manager. It’s the only way to create good passwords that can survive brute-force and dictionary attacks. In addition, keep your accounts safe by using a different password for each account and never sharing your passwords. Lastly, use two-factor authentication if it’s offered. You will be safe and sound for a long time.

Notes

In addition to brute-force and dictionary attacks, there are two more that are worth knowing. For brevity, I did not include them in Section 3.

c. Lookup table

Hashing takes time, but looking up pre-made hashes takes very little. The hacker can create a list of passwords and their hashes in advance, and see if the stolen hashes appear. We call this list a lookup table.

A lookup table requires little time but huge storage. The hacker can balance time and storage by creating a rainbow table, a more sophisticated lookup table. (We use a sequence of functions to create chains of hashes. We keep the beginning and the end of each chain to save storage and be able to recreate the entire chain when needed.)

Lucky for us, lookup tables (rainbows, too) are useless when salts are used. The hacker would need to create a lookup table for every salt, which is impractical.

d. Markov chain

We tend to use letters, numbers, and symbols in a manner that is neither independent nor uniform (both in the probability sense). Orwell said it best: All characters are equal, but some characters are more equal than others. The hacker can look at a probability distribution to guess passwords that are more likely to occur.

References

Ars Technica, Anatomy of a Hack.

Computerphile, Password Cracking.

Crackstation, Secure Salted Password – Doing it Right.

IT Security Community Blog, About Secure Password Hashing.

kestas.kuliukas.com, How Rainbow Tables Work.