It’s the worst thing–and worst irony–that could happen to a company whose business is about storing passwords securely for its users. In a corporate blog post, LastPass disclosed that it had suffered a major server breach that allowed email addresses, password-reminder hints, and encryption related to master passwords to be snarfed down by an unknown attacker. The company says files containing passwords themselves (which it calls “vaults”) were not retrieved.
This sounds terrible, and it certainly still has the potential to be a major problem for LastPass and its customers. However, the folks at LastPass aren’t dummies. It’s unlikely this breach will result in those who obtain the stolen data unlocking many vaults at all, so long as LastPass’s description of how it holds user data is accurate and well implemented.
Some password-storage firms only store information on devices themselves, like AgileBits and its multi-platform 1Password software. Although 1Password can sync through various means, data vaults remain in the possession of users, and passwords are never disclosed to or stored by AgileBits.
Like 1Password, LastPassword stores passwords on its customers’ computers. But it also offers central storage and sync, letting users access passwords via a website in addition to client apps on many platforms. That’s an Achilles’ heel that crackers exploited.
Unlike some very large password thefts in the past, such as those from LinkedIn and others, the LastPass breach won’t permit a malicious interloper to rely on a simple way to unlock many accounts at once if they share the same password. Instead, making use of the purloined data will be a tedious process.
Any sensible company that stores passwords uses an encryption algorithm called a “hash.” A hash takes an input (the “message”) and runs it through a series of operations that compresses it down to a hash. (Hashes are primarily used to ensure a message being unaltered, but are also used as a way to validate a password without retaining the original in clear text.)
A hash can’t be used to reconstitute the original message, and it’s designed so that similar messages produce wildly dissimilar results. A firm stores only the hash, and whenever you try to log in, it performs the same transformation and compares the result against what it’s stored.
Because all hashes from the same input text are the same, a cracker need only run through the most common passwords and then dictionary words to find every match in LinkedIn and similar companies’ lists. If 100,000 users picked “123456”, their accounts are instantly compromised.
But that kind of iteration requires massive amounts of computation—the kind that is now available for rental at Amazon and other cloud services and is also built into relatively affordable graphics processing units (GPUs) for PCs. Crackers must work their way through every password they want to test using the hashing algorithm employed at the site.
LinkedIn used a very simple approach, which was already considered a terrible idea in 2012 when its breach occurred. It took a password and ran it through a hashing algorithm called SHA-1 that was and remains the weakest reliable one. (Today, it’s been broken by security researchers and is moving closer to becoming a real-world risk.)
LastPass went several steps further—well, actually literally thousands of steps further—using methods that are now highly recommended and one hopes most companies employ.
First, every password has a unique “salt,” a value that’s combined with the password before it’s hashed. With a salt, two identical passwords with different salts produce dissimilar hashes. Even though the per-password salts were stolen from LastPass along with account password hashes, this slows things down: Every password a cracker tests has to be uniquely tested with each salt. With a million accounts, it takes a million more calculations to crack the same password across every account that uses it.
Second, instead of performing a single hashing operation, LastPass—like 1Password and other password-vault makers—performs thousands. Using the ungainly monikered Password-Based Key Derivation Function (PBKDF), LastPass takes a salt, a hashing algorithm, and a password, and runs thousands of iterations. Each iteration adds another round of calculations for a cracker, while still allowing your PC or mobile device to create the resultant hash in a fraction of a second.
Let’s look at how much extra work this approach takes with benchmarks from oclHashcat, software designed to run “password recovery” operations against every protocol and authentication system. Using eight $1,000 Nvidia-based GeForce GTX Titan X cards, with the basic SHA-1 encryption, the software can create over 42 billion hashes per second. (Even faster cards are now available.)
With a million accounts separately salted, that’s still 42,000 passwords checked per account per second. Switching to SHA256, which is what LastPass employs, that speeds drops by about 66%,. But 17 billion remains a large number.
Ah, but add in PBKDF and a minimum of 5,000 rounds (as LastPass configures things by default on the client side) and things start looking better. Five thousand rounds means only 3.4 million hashes can be calculated per second on the same equipment. With a million accounts, it would take an hour to check the 1,000 most popular passwords.
LastPass allows users to configure the number of rounds, though it recommends not setting the number too high, because older and mobile gear will bog down when you log in, or even fail to complete the rounds.
But, wait! There’s even more. The company’s security support documents note, “LastPass also performs a large number of rounds of PBKDF2 server-side.” According to Blair Hanley Frank of the IDG News Service, LastPass uses 100,000 rounds. Because that iteration happens on a server and only when a user logs in, LastPass can be gradually increasing the rounds over time to compensate for faster cracking gear. 100,000 rounds on top of an already-hashed password (provided by a native or web app) lowers the number a cracker can check with that same equipment to a paltry 30 passwords a second.
Further, any LastPass user who enabled two-factor security can’t have their centrally stored vaults unlocked without access to that information, either.
This is still bad news for any user whose password is “password” or “123456”. Criminal entities may rent massive amounts of on-demand computers using stolen credit cards or have rooms full of GPUs. This is why picking a long phrase or a password with at least some complexity (say, an errant punctuation mark) will help you foil brute-force efforts to reveal it–even if they were conducted by crackers who had the NSA’s supercomputers on their side.
Now, because password hints were stolen from LastPass along with email addresses, thieves do have the ability to target specific accounts based on those hints. They can also test more weakly protected passwords elsewhere—or those stolen and distributed from previous hijackings—knowing the email and password hint. (Sites should lock out someone who makes too many incorrect attempts to enter a password, but many do not.)
However, unless it comes out that LastPass was breached in other fashions or there’s an implementation flaw in their work, LastPass customers should take the firm’s advice: Change your master password. And if you use the same password elsewhere—a terrible idea that passwords vaults were born to keep us from doing—change that, too.