I’ve seen several people recently discussing how LastPass protects your LastPass master password and your encrypted site password data (a.k.a., your vault). If what some of those people were saying were true, then LastPass wouldn’t be as secure as I thought it was. This gave me pause, since I use LastPass to store all my passwords, so I decided to do some research to try to understand for myself exactly how it works. Now that I’ve done that, it seems to me that others might benefit from my research, and in any case writing it down will clarify it in my own mind, so here it is.
The client-server protocol
I’m going to first describe tersely how the process of logging into LastPass, downloading your vault, and decrypting it works, and then talk about what makes this process secure, what its vulnerabilities are, and how difficult it would be to take advantage of those vulnerabilities. Then at the end I’ll talk specifically about how the Heartbleed bug relates to those vulnerabilities.
To log you in, the LastPass extension or app (hereafter just “app”) on your client device needs to know three things: your email address, your master password, and the number of password hashing iterations you’ve configured in your LastPass account (more iterations == more secure but slower login), which is referred to below as “pw_iterations”. The first time you log in, the app doesn’t know the number of iterations to use, so it asks the server for it before processing your username and master password. If you change the number of iterations in your settings, then the server tells the app that the next time it tries to log in, and it switches to the new number of iterations automatically.
In the notation below, PBKDF2 refers to a password-base key derivation function which uses SHA-256 as its hashing algorithm. The first argument shown in each PBKDF2 call is the number of iterations, and the second is the data being turned into a password.
Here’s what happens when you create a new LastPass account:
app: Set encryption_key = PBKDF2(password=master_password, salt=email_address, pw_iterations).
app: Set login_key = PBKDF2(password=encryption_key, salt=master_password, iterations=1).
app: Send login_key to server.
server: Create and store random 256-bit uid for this account.
server: stored_login_hash = PBKDF2(password=login_key, salt=uid, iterations=lots-not-sure-exactly-how-many).
server: Store stored_login_hash for future authentication.
Then, during login, the first five steps above are repeated, and if the resulting login hash matches the stored login hash, the user is logged in, his/her encrypted vault is sent down to the app, and the app uses the encryption key to decrypt it.
It’s important to note the following:
- Your master password is never transmitted over the network.
- Your encryption key is never transmitted over the network.
- The LastPass server doesn’t know your master password, and your master password cannot be reconstructed from the data that the server knows.
- The LastPass server doesn’t know your encryption key, and your encryption key cannot be reconstructed from the data that the server knows.
- Without knowing your master password or your encryption key, it is essentially impossible to decrypt the data in your vault.
However, all is not quite as rosy as it seems. In particular, if your master password isn’t strong enough, then if either your login key (i.e., the blob of data that gets sent from the app to the server when you log in) or the uid and login hash stored on the server, could be used to determine your master password through a brute-force attack. This is discussed in more detail below.
How an attacker could get the data
Now, let’s look at what how each of the secret data in this process could theoretically be compromised by an attacker. Then we’ll look at how those data could be used or leveraged to give an attacker access to your decrypted vault.
|master_password||malware on device or on LastPass server (if logging in at lastpass.com)|
|encryption_key||malware on device or on LastPass server (if logging in at lastpass.com)|
|login_key||malware on device; MITM; compromised LastPass server|
|uid||compromised LastPass server|
|stored_login_hash||compromised LastPass server|
|encrypted vault||malware on device; using stolen login_key; MITM; compromised LastPass server|
|decrypted vault||malware on device or on LastPass server (if logging in at lastpass.com)|
How an attacker could use the data
Now, let’s talk about what an attacker can do with this stuff.
If an attacker manages to get malware onto your device, then there’s no point in talking about the specifics of what data he can obtain; he can get all of it if his malware is sufficiently clever. This, of course, is not unique to LastPass… if somebody gets malware onto your computer, he can eavesdrop on which web sites you log into, what passwords you use on them, etc. But it is important to recognize that since LastPass stores all of your passwords in your vaule, if your device is compromised then the attacker could steal all of them at once, not just the ones you actually use while your device is compromised.
Similarly, if an attacker manages to hack LastPass.com and install malware there, and you go to lastpass.com to log into your LastPass account, then the attacker could cause LastPass.com to serve malware to your device and steal your master_password when you type it to log in, so it’s the same as any other malware on your device.
An attacker could steal your login_key by using a man-in-the-middle (MITM) or eavesdropping attack to redirect your traffic through the attacker’s servers on the way to/from LastPass. This would require stealing LastPass’s SSL certificate and private key file or getting a forged SSL certificate that your browser accepts and then using a DNS attack to redirect your device to go through the attacker’s server instead of directly to LastPass.com; or compromising the web proxy your device is configured to use, e.g., in a corporate environment. A MITM attack could also be done using malware on your device, but if the attacker already has malware on your device, then it’s easier to just steal your data directly than to set up a complicated MITM.
If you have a good, strong master password, then the attacker can use your login_key to gain access to your encrypted vault, but he can’t decrypt it and access its contents. He might be able to leverage your login_key to change the email address or master password associated with your account, but I suspect there are additional protocol steps involved in those changes that would prevent this (I haven’t explored carefully what those are). Even if not, the worst-case scenario is that he would deny you access to the data in your vault; he wouldn’t be able to gain access to it himself; because without your master_password or encryption_key, he can’t decrypt it. (Personally, to protect myself from an attacker somehow locking me out of my account, LastPass somehow screwing up and locking me out of my account, or my doing something stupid and screwing up the data in my vault, I back up my LastPass vault monthly by exporting it into a CSV file and encrypting the CSV file with GPG.)
However, if you have a weak master password, the situation is much more bleak. If you have a user’s email address and a login key and their master password is weak, it is easy to derive it using a brute-force attack. And once that’s done, of course, you’re back in “all bets are off” land.
uid and stored_login_hash
If an attacker managed to steal your uid and stored_login_hash from the LastPass server, he could use them to do an offline brute-force attack to derive your master_password. He would do this by playing the role of both the app and the server: create login_key from master_password guess; create try_login_hash from login_key and uid; compare try_login_hash to stored_login_hash and stop if they match or repeat the whole process with another master_password guess otherwise.
If you use a master_password that LastPass rates as strong, then this brute-force attack is unlikely to succeed because it will take too long for the attacker to find your password. However, if you do something stupid like use one of the 10,000 most common passwords that represent more than 99% of all user passwords, the attacker will obtain your password in well under an hour.
I can’t say for certain, but I’m assuming that a user’s encrypted vault by itself is useless to an attacker. Assuming that LastPass uses a decent block-chaining encryption algorithm and puts random data at the beginning of the plaintext, it’s not computationally feasible for an attacker to brute-force the decryption key.
What about Heartbleed?
UPDATE 2: Here is what LastPass, or at least one of its employees, has to say about this. While I find his explanation reassuring, I do not find it 100% convincing. I think the folks at LastPass are downplaying, at least a little bit, the risk that weak master passwords could have been compromised, and I wish they were being a bit more upfront about it.
UPDATE: When I first wrote this section (original text below), I was convinced that the likelihood of Heartbleed significantly impacting LastPass’s security was minimal. However, I have come to believe that if, in fact, the Heartbleed vulnerability was known by attackers before it went public, and if those attackers used Heartbleed to access the memory on the LastPass servers, there’s a good chance that many users’ login keys and corresponding email addresses could have been stolen, and the login keys corresponding to accounts with weak passwords could easily have been cracked.
To test this theory, I set up an nginx server as an SSL reverse proxy to my local web server, submitted a bunch of web requests with known strings in them through nginx, and at the same time used heartbleed-poc.py to attempt to scrape data from nginx’s memory space. I was able to easily capture much of the content being submitted to the server. It seems like there’s a pretty good chance that the same thing would have been possible with LastPass’s servers, in which case attackers could have been stealing people’s email addresses and login keys for an indeterminate amount of time without LastPass or anyone else realizing it.
The problem, of course, is that as far as we know, there’s no way of knowing whether this was going on, because one of the hallmarks of the Heartbleed attack is that it’s essentially invisible. It’s possible that LastPass had some clever network monitoring going on that would have tipped them off that something was awry and allowed them to put a stop to it, but so far they’re not saying.
The best-case scenario is that this vulnerability wasn’t known to anyone except the researchers who discovered it until it was publicized. The worst-case scenario is that many LastPass users’ master passwords and vaults have been compromised. Yikes!
Having said all that, if your master password is one that LastPass says is strong, you’re almost certainly safe even if your login key was compromised, because it will simply take too long for an attacker to brute-force your password.
Original text follows:
Through the Heartbleed bug, an attacker could have gotten his hands on LastPass’s SSL certificate and private key. Armed with that information, the attacker could have set up a man-in-the-middle or eavesdropping attack as described above to capture user login keys. However, as noted above, this isn’t enough for the attacker to actually gain access to the data in your vault, so it’s probably not worth the effort.
The other potential attack people are discussing is an attacker using the Heartbleed bug to gain access to the uid and stored_login_hash associated with specific user email addresses, and then to do a brute-force attack on them to derive those users’ master passwords. I’ve thought a lot about this, and I don’t think it’s feasible, for one simple reason: I don’t think the LastPass servers store these persistently in memory where Heartbleed could read them. They’re only kept in memory for long enough to validate users during login. At the very least, they are overwritten after that by other data; but if LastPass is smart (and they do seem pretty smart), they are probably actively erased from memory immediately after they are used (note that PHP, which LastPass uses, doesn’t intern strings, so wiping strings from memory is relatively easy).
I suppose it is remotely possible that someone could Heartbleed a LastPass.com server just as you happen to be logging into it, and just happen to grab the correct 64kb chunk of memory to obtain your email address, uid, and stored_login_hash before it gets wiped from memory, but that frankly seems rather implausible. And if LastPass was smart enough to put the login_key checking in a separate process, such that the web server makes a remote procedure call with the email_address and login_key and gets back success or failure, then even this remote possibility isn’t, because the uid and stored_login_hash will never be in the web servers memory space where the Heartbleed bug can read them.
If in fact many (email_address, uid, stored_login_has) tuples are stored in memory where an attacker could have accessed them using the Heartbleed bug, then yeah, there was a vulnerability there. But LastPass says there wasn’t. It’s unlikely that they’re lying, because they’ve got a track record of openness and transparency, and because if they lie it’ll eventually come out and they’ll be in deep trouble.
If you think they’re lying, then you obviously shouldn’t trust them to store your passwords.
Please comment below if you think I’ve made any mistakes here.