LastPass One Time Recovery Passwords--How?

Question

The LastPass password manager stores One Time Recovery Passwords locally in each browser you use the plugin with:

http://helpdesk.lastpass.com/account-recovery/

My question is, how can you have more than one password?

I thought LastPass derived the encryption key from your master password using a variant of PBKDF2 and then encrypted your data with this encryption key locally with AES. There's no room in this scenario for multiple passwords, unless the data is encrypted multiple times. And, how can they enable or disable the OTPs unless they're stored somehow server-side? It just all smells really fishy. If the encryption key for my data never leaves my computer, I cannot understand how any password besides my master password could allow access to my password vault unless there's something LastPass isn't telling us and the local Javascript encryption is all smoke and mirrors...

Update

I contacted LastPass and they pointed me to an explanation here: http://forums.lastpass.com/viewtopic.php?f=12&t=22959&p=87289

Answer 1

LastPass stores, on the server, a "vault" which is a collection of data, encrypted with a key derived from the "master password". Let's call K that key. Normally, K is rebuild on the local computer by recomputing it from the master password. However, the same key K could also be stored on the server, this time encrypted with a recovery key K_r, allowing reconstruction of K by whoever knows K_r. The "one-time recovery password stored in the browser" would be that K_r (they call it "password" but the user does not type it, so it can be a fat sequence of random bytes, something usually known as a "key").

With such a system, the vault can expanded with a "recovery blob" which is E_Kr(K). Generating a recovery blob requires knowledge of K, so it must have happened on the client system, since LastPass does not know the K or the master password. This matches the idea that the one-time recovery password is browser-specific.

If one "recovery blob" can be stored, several recovery blobs can be stored as well. When the user wants to prepare his browser for a potential subsequent recovery, he makes his browser generate a new random K_r, store it in the browser entrails, and compute the recovery blob (the user types his master password, the browser recomputes K and does the encryption with K_r). The recovery blob is then sent to LastPass's servers for storage. At no point does LastPass learn K or the master password or any of the "one-time recovery passwords".

---

What I describe above is a plausible implementation. I cannot vouch for what LastPass actually does.

A point to make, however, is about "one-time". That one is pure marketing. There is nothing intrinsically "one-time" in what I described. What they mean is that the server will refuse to send back a given recovery blob to the user more than once. Presumably, when a user connects and requests download of a recovery blob, the LastPass server sends it back and then destroys it on its side. This is all relative to how well LastPass complies to this data destruction routine.

(There cannot be anything one-time in a system unless parts of the system enforce some state change which the attacker cannot revert. This is generic.)

Answer 2

They could use a system similar to the Linux Unified Key Setup (LUKS), commonly used to encrypt HDD partitions under Linux. LUKS is also usually deployed with PBKDF2 and AES, as in your question.

With LUKS, the data is encrypted under a Master Key, which is then encrypted once for each User Key. User keys are generated from one or more User Passwords, and each stored individually. That way, you can use any of the passwords to yield the master key and decrypt the data.

This is all explained in detail in the 'Overview' section of the pdf linked above.

You can also give different keys to different people and revoke access to individuals without having to change any keys/passwords.

Answer 3

I've attempted to collate the various pieces of information about this feature.

What is the difference between "Login OTPs" and "Recovery OTPs"?

Login OTPs:

Login OTPs or One Time Passwords can be generated on this page: https://lastpass.com/otp.php You can print off these passwords and carry them with you. Each one time password in that list can then be used to log in to LastPass via https://lastpass.com/otp.php - the idea is that if you are on an untrusted computer, and do not want to enter your Master Password because of a keylogger threat, you can use the OTP. It expires after you use it, but allows you to log in without entering your Master Password. These are portable, and are not local to the device where they are generated. The list can be accessed anywhere when you log in at https://lastpass.com/otp.php where you can generate and print more. They are not to be used for account recovery.

Recovery OTPs:

Users do not have direct access to recovery OTPs. These are bits of data that are stored automatically by the browser add-on. When you use the LastPass browser add-on, the add-on generates an OTP that is derived from the Master Password and stores it in the browser's LastPass files. It will stay there until you go through account recovery in that specific browser where the OTP was generated and stored. If you do the recovery process (https://lastpass.com/recover.php) it will try to "call up" that OTP, and allow you to immediately reset your password if it detects that the OTP was stored in the browser.

OTPs are local to specific browsers and one OTP should be generated for each browser, on each computer, where you use LastPass. Recovery OTPs are not portable, they are stored in the specific browser's file, so recovery can only be done on a browser where you have used your LastPass account before. When you next log in to your account after you've reset your Master Password, new OTPs are generated for the browser the next time you login.

*** Note: All OTPs are derived from the master password that is current to the account when they are created. Changing the master password in any way, even through a revert, will cause the OTPs to not function.

From https://lastpass.com/support.php?cmd=showfaq&id=4616

Then some more technical details were posted in this LastPass forum thread:

...

What we actually do is far more complicated:

• Create a completely random 128-bit number
• Make the random key out of the username and the random password as a hash
• Make a random hash from your username and random password, send this to the server, this will be how we can tell you entered the right 32 digits of hex to allow you to download your encrypted data later
• Encrypt your actual key with the new random_key, so we can retrieve it when random password is entered later, send this to the server

Basically we recursed our entire process using a 128-bit key that's randomly created.

The safety of this is very high, especially if you turn over your OTPs -- a full 128-bit key to encrypted data which gets wiped once you use it.

There is one minor regret here, but it came about because we needed to implement it on a time-line: we're using the same 128-bit OTP process for the stored password recovery hash -- there's no reason that couldn't be 256 bit (or even longer) since you're not typing it in. We'll hopefully get around to fixing this at some point, but 128-bit AES is still exceptionally strong and it would be the end of the universe before it's brute forced .... time is on our side here.

---

I hope I understand it now. I'll just repeat for clarity:

In simplified words (in terms of what data is sent and what is used locally), when I ask for an OTP,

• Random OTP is created locally
• temp_key = hash(username + OTP)
• Username + hash(OTP) is sent to the server
• encrypt(master_password, temp_key) is sent to the server

Thus, neither my master password nor OTP nor temp_key is ever sent to the server.

When I am using the OTP,

• I enter my username and OTP
• Username + hash(OTP) is sent to the server for authorization
• You then send me the encrypted database and the temp_key-encrypted master_password
• temp_key is recreated locally from username and OTP
• Master password is locally decrypted
• Database is locally decrypted
• You delete the used Username + hash(OTP) value so that this OTP cannot be used for authorization any more.

So basically we are dealing with OTP-encrypted master password.

Is this correct? Then I don't understand how an OTP can be revoked. If you have sent me the OTP-encrypted master_password, and I have entered the OTP locally, someone key-logging on the local machine can save both values and decrypt the master_password later? You will not allow second authorization with the same OTP, but the person has already obtained the master password! Where am I wrong?

---

Not entirely -- to try to put it in a simple way the OTP creates a hash, which that hash then verifies if the OTP is still valid on the server and if so allows download of random data that can then be combined with the OTP locally (remember the OTP wasn't sent to the server just the hash) to create your key.

Yes if your OTP is valid on the server and is used it's too late -- your key is now local too -- but if you say lose your OTP list you can run to the server and invalidate them all before the person has a chance to use them.

From https://forums.lastpass.com/viewtopic.php?f=12&t=22959&p=87289

This helps, but LastPass don't seem to have provided clear implementation details or confirmation after this post.