On June 15, 2015, LastPass announced that email addresses, password reminders, user salts, and master password hashes, stored on their servers, were compromised. On social media fierce discussions erupted about the question whether LastPass could be trusted and, more generally, whether it was wise to store one's passwords in the cloud. Being an LP user, I read many of these discussions and noticed that a lot of discussants did not know what they were talking about. Therefore, I decided to look into LP's security procedures. The following brief report contains my findings.
I could not find on the Internet all necessary details of the procedures, which is why the present report contains some educated guesses; it is not impossible that some of these guesses contain inaccuracies. However, I'm confident that the information in this note is correct as far as the security aspects are concerned. My most important reference is an Ars Technica discussion contribution by Jeremi Gosney, alias epixoip, a well-known security expert. Note that the definition of authentication_hash given below is taken from this paper. It differs somewhat from Gosney's definition.
h := SHA(msg).
In the present context msg is a salted password.
SHA maps the string msg to the hash h. The hash h
is a binary string that can be used as a cryptographical key. As said, SHA is non-invertible. Indeed, its algorithm
is constructed in such a way that it as difficult as possible
to go back from h to msg. Knowing h, one could obtain msg by
guessing different strings str and comparing SHA(str) with h. If a match
is found, i.e., h = SHA(str), then str = msg.
HMAC(key, msg) := H(H(msg+key)+key),
where H(msg+key) is a hash of msg+key; the symbol + stands for string
concatenation. LastPass uses for H the hashing function SHA256, which is SHA
with a 256 bit hash. The combined function, which generates a 256 bit key, is commonly written as HMAC-SHA256.
In the LP authentication procedure described in the next section, msg is the cryptographic salt.
aes_key := PBKDF2(HMAC-SHA256, master_password, email, 5000)
HMAC-SHA256 is invoked 5000 times. During the iterations master_password is used as key
and the output of the previous iteration serves as salt. In the first
iteration email, a standardized form of the user email address, is used as salt. The number 5000 is default, the user may change it.
Because the number of iterations must be accessible across multiple devices, it is stored on the server (and was
compromised in the 2015 hack). The iterations are executed on the device of the user (the
client). They produce the 256 bit AES key aes_key. The key is used for encrypting and decrypting
the content of the user's password vault. Note that
aes_key never leaves the client, because the AES encryption and decryption of the vault
occurs on the client, too. Also master_password never leaves the client. The initial salting with email
personalizes the master password so that tables of precomputed hashes of common passwords cannot be
used for retrieving master_password.
authentication_hash := PBKDF2(HMAC-SHA256, aes_key, master_password, 1)In this step aes_key is hashed in a single round with master_password as salt. This extra hashing round is performed because aes_key may not leave the client. The key authentication_hash is sent to the server; together with the user e-mail address it authenticates the LastPass user. As aes_key itself is not sent to the server, it is impossible to decrypt the user vault on the server.
server_hash := PBKDF2(HMAC-SHA256, authentication_hash, salt, 100000)
For security reasons authentication_hash is not stored, but hashed further to the key
server_hash. The latter hash is computed and stored on the server; salt is a 256 bit random
salt per user which is created and stored on the server. The number of iterations (100,000) is fixed; it cannot be
changed by the user.
When you login to LastPass, with your e-mail address and master password, a new value of server_hash is calculated by the three steps above. If the result matches the stored version of server_hash and corresponding e-mail address, LP will send you your AES encrypted vault, otherwise LP will refuse it. When a hacker steals the key server_hash and somehow entices LP to send the vault, it is of no use to the hacker without aes_key, which LP does not know. Moreover, LP does not expect to receive server_hash, but rather the hashed password authentication_hash. Even if this were intercepted somehow, it is of no use because aes_key, the key to the user vault, cannot be extracted from authentication_hash. Note that interception of the latter value requires breaking the HTTPS connection of the user with LastPass.
When a password of a new website must be included in the vault, it is AES-encrypted and added to the vault on the client, before the updated and encrypted vault is uploaded to LP.
The hackers of LP have retrieved all ingredients, except master_password, necessary for the computation of server_hash. Because all algorithms are in the public domain, the intruders can make a guess for the string master_password, compute a value of server_hash, and check it against the stolen value of server_hash. In other words, the security of LastPass after the hack depends to a large extent on the guessability of the user's master password. It is estimated that at present it will take about a tenth of a millisecond of computation on a fast graphical processing unit to go from one guess of master_password+email to the value server_hash.
When a password reminder is something like "my dog" (and the password is indeed a dog's name), the password is likely to be hacked in less than a tenth of a second, because the hackers will work through a list of, say, the thousand most common dog names. When the answer to a password reminder is not obvious, the attackers must try per account a list of, say, the 106 most common passwords. Such lists can be found on the Internet. If the password is in the list, it will be cracked within 100 seconds. This may seem fast, but note that this is per account. If there are, say, a million accounts hacked, the hackers must spend three years of processing time to check all passwords against the list. On the other hand, the process is very easily parallelizable: n processors cut the time by a factor n.
When the password is not in any list, brute force is called for. The hacker must assume that the password is a random list of length L composed of all lowercase and uppercase letters, digits, and special characters (72 in total). The number of such passwords is 72L. If L=8, there about 7×1014 possible passwords. Checking all of these takes about 2290 years, which gives a user plenty of time to adapt his/her master password.
Personally, I use a passphrase of 7 words that I can easily remember. The phrase contains one word that is used infrequently in my language. Checking all such passphrases against a wordlist of the 10,000 most frequent words costs 1024 seconds, which is 3 × 1016 year (3 million times the lifetime of the Universe). After the hack of LP I added a few special characters to my master passphrase in a way that I can remember and I blanked out my password reminder.
Dr. Paul E.S. Wormer, June 2015.