How Password Manager Cryptography Keeps Your Data Safe
A look behind the curtain at some very clever systems
Password managers like Lastpass, 1Password and Dashlane are becoming more and more popular as users are being forced to remember passwords for everything they use online. However, many people are sceptical of this technology.
It’s only natural to question the security of a service that you’re trusting with your entire digital life, and often I hear security as the reason people don’t use these services. They feel unsafe, after all:
How can we be 100% sure that if a malicious party gained access to all the logins and personal information stored by a password manager, they wouldn’t be able to do anything with it?
That’s what I want to answer here by stepping through the process of how you could build your very own password manager. Strap in.
Before we begin, it’s important to note that we’ll be ignoring man-in-the middle attacks (e.g. intercepting data on a dodgy public WiFi). Most browsers and servers have ways of handling encryption built in (e.g. HTTPS) meaning, for the most part, that we don’t have to worry about securing our communications. If you want to know more about how communication security works, Computerphile have some incredible videos on Diffie-Hellman, Digital Signatures, TLS Handshakes etc.
Step 1 — The World’s Worst Password Manager
Let’s begin with an incredibly naive attempt at building a password manager. Fundamentally, we have two parties involved:
- The user — who has a username and master password that that they use to log in to the password manager, and a vault which stores all the login information for different websites
- The “cloud” — which is just a location on the internet with a database storing user information
The database could look something like this:
It’s just a table with columns: username, master password and vault. Each user has one row, with their vault being a big list of their websites and passwords.
Initially, we’ll ignore the horrendous idea of the vault being stored in plain text. We’ll get to that later, I promise.
The process the system takes to log a user in and retrieve their vault is very simple. All it does is lookup the user’s row, compare passwords and returns the vault if they match.
There are a million problems with this, even assuming we have 100% secure communication (which we don’t in reality).
The main threat we want to protect against is a database breach. This could be:
- Internal (like a rogue software engineer reading the database)
- External (like a hacker leaking the database)
In both cases, we want to ensure that no-one would be able to access any information of users on the database.
Let’s say there was a leak and a hacker got access to your row. How do we prevent them from just logging in to your account with the email and password in the database?
Step 2 — Goodbye Plain-text Password!
If the idea of a cryptographic hash function is new to you, think of it as a function that scrambles a message in an highly unpredictable way. Trying to reverse a cryptographic hash function is impossible, so the only way to know what went in is to guess and check.
When we send a user’s login information, it’s first hashed.
This has an undeniably great benefit: anyone looking at the database won’t see your plain password. They won’t be able to just copy/paste from your row and log in on the website.
Because hash functions are by-definition impossible (or at least unbelievably hard) to reverse, there’s absolutely no way anyone can figure out our password from the hash.
Or is there?
Unfortunately most people don’t use big long strings of random characters as their master password. They’ll tend to use short, normal words, maybe swapping out numbers for letters if they think they’re really clever. We’re predictable. And this leaves us open to rainbow table attacks.
A rainbow table is a huuuge database (100s of GB) of hashes and their inputs. If someone has the hash of your password, they can just search the table for it! Yeah it might take a few hours to check through billions of possibilities, but that’s much much faster than the years for guessing and checking hash inputs.
RainbowCrack is a website with some of these tables available for purchase. You can see the scarily high success rates they have in the image below.
We now have a real problem, if people have the hash of our password it’s almost no better than storing it in plain text!
How can we ‘rainbow-proof’ our login?
Step 3 — Rainbow-Proofing
What if, when a user first creates their account, a random, long string of characters is generated. We call this a “salt”. Before the hash, we append the salt to the user’s password. Then we can store both the hash and the salt in the database. The hashes can be checked for verification as normal by first getting the salt.
Our database now looks like this, with the salt stored next to the hashed password.
So how does this guard against rainbow tables? Simply put, it is much less likely that a very long, random string is in the table. Because of the unpredictability of hash functions, storing the salt in plain text tells the attacker absolutely nothing about how it affects the final hash. They can’t ‘un-salt’ the hash.
Importantly though, salting alone doesn’t protect from guess-and-check (brute force) attacks. Someone will still be able to guess and check what password creates the hash, they just have to append the salt to their guesses too. And when they’re guessing hundreds of millions of passwords a second, they could get lucky.
So to be even more secure, we’ve also changed the hashing algorithm from a fast one (e.g. SHA-256) to a slow one (PBKDF2) and repeated it 100 thousand times. This does two things:
- Further prevents against rainbow tables (who’s gonna have a rainbow table for the results of 100,000+ hashes in a row?)
- Slows down anyone trying to brute force (each guess takes over 100,000 times longer)
It might be a good idea to choose a random (but still large) amount of hashes that’s kept secret. That adds another layer of security, as an attacker would need to know the exact number of hashes to perform.
After all that, are we now protected? Not in the slightest.
Hashing on the user-side might seem reasonable as we don’t send the password over the internet, but it just makes the hash a drop-in replacement for the password! Anyone who knows the hash can just give it to the server directly, and the server has no way of knowing that the hash hasn’t come from the user typing in their password!
What can we do to stop this?
Step 4 — Do It Again?
In this step, we decouple what’s in the database from what’s sent to the server. Before the server checks the password, it does some hashing of its own to come up with a new value that’s compared to the database.
This way, even if the hash in the database is known, it can’t be passed to the server to log in as it’ll hash it again and come up with the wrong value.
This process is made a bit clearer below. The hacker knows the hash stored in the database and attempts to use it to log in.
We now have protection against the database being leaked! Your passwords are safe and no-one can access your account!
…
But the vault is still being stored in plain text! Anyone looking at the database can just see your login information right there!
Let’s fix that.
For a bit more information about how Lastpass securely hash and store your password in the database, check out this article.
Step 5— Encrypting The Vault
We can’t use a hash function here, as we want to be able to get the information back after it’s scrambled (which by definition cannot be done with a hash function).
What we need here is an encryption algorithm: a function that uses a key to encrypt and decrypt information. It’s important that this encryption algorithm is cryptographically strong — i.e. it satisfies a few key points:
- A small change in the input or key should result in a completely different (seemingly random) output (similar to a cryptographic hash function)
- Knowing how the algorithm works does not help with decryption
- Brute forcing (“guess and checking”) the key is infeasible even with large amounts of compute time
AES-256 (Advanced Encryption Standard) is an encryption algorithm that satisfies all these requirements. It’s used absolutely everywhere online and is generally considered very strong. It’s what Lastpass state they use.
AES-256 takes a message of any length (split into 128 bits/ 16 bytes) and transforms it into an output of the same length, using a key of 256 bits (hence AES-256). You can get the original message back from the scrambled output using the same key.
Importantly, all of this encryption should be done on your device. No encryption keys or decrypted information is ever sent across the internet or stored anywhere other than your device.
The question now is what should our key be? It needs to be consistent across all devices, but you can never store it anywhere so we can’t generate it randomly.
We can use our master password! Or rather, we can use our email and master password combined to generate our key via a Key Derivation Function. (We don’t want to store our password in plaintext on our device, even if we think the device is secure).
A KDF is just some function for creating a key from an input. This could be a hash function like SHA-256, but PBKDF2 is pretty commonly used (used by Lastpass). As always, this algorithm needs to be cryptographically strong.
With all this in mind, let’s take a look at the final system. Follow the flow from the user inputting their password.
For something so secure, there aren’t as many steps as you’d think. Granted, I’m sure this is a major simplification of how password managers actually work. Unfortunately, these companies aren’t rushing to explain their systems to the public (although it’s probably best that way).
While we can never be sure that these tools are 100% secure, the cryptographic theory behind password managers is sound. And let’s be honest, they are almost certainly safer than the alternative of using the same, simple password for everything.
I hope you learned something and I’ve convinced you that it is possible for password managers to be secure, at least in the context of database breaches.
If you enjoyed this, feel free to give me a clap or two (I’d really appreciate it!).
If you want to see more like this, check out my profile or the article below!
