Tuesday, June 16, 2015

Should I panic because Lastpass was hacked?

Maybe, maybe not. Lastpass uses 100000 iterations in its PBKDF2 algorithm. If you chose a long, non-dictionary password, nobody can crack it. Conversely, if you haven't, then yes, you need to change it.

I benchmarked this on my computer using "oclHashcat". It's not an exact match with the Lastpass algorithm, but it's close enough to show the performance.

As you can see, my machine is getting 2577 (two and a half thousand) random password guesses per second. This may sound like a lot, but it's not not, because cracking passwords is exponentially difficult.

Consider normal hashes, not the stronger ones used by Lastpass. My desktop can crack 1 billion of those per second.  Consider that a password can be built from UPPER and lower case letters, numbers, and punctuation marks -- or about 64 variations per character.

In this case, a 5 letter password has 1 billion combinations, so a fast computer can guess it in a second. Adding one letter, with it's 64 different possibilities, makes this 64 times harder, meaning it'll take a minute. Another letter (7), and it becomes an hour. Another letter (to 8), and it becomes several days. Another letter (9), and it becomes a year. Another letter (10), and it becomes 64 years. Another letter (11), and it's thousands of years, and another letter (12) and its millions of years.

Lastpass re-hashes the password 100,000 times, which slows this down dramatically. What I could've hashed in an hour now takes a decade. On the other hand, consider an adversary like the NSA or a hacker with a botnet that controls 100,000 computers, that would speed things back up to the normal rate. But even with 100,000 computers, the NSA won't be able to brute-force a 12 letter password.

Unfortunately, brute-force isn't the only option. Hackers may instead use a dictionary attack, where they use word lists and common password choices (like GoBroncos!), and then mutate them with common patterns, like adding numbers on to the end. This speeds things up dramatically, making it easy to crack even 12 letter passwords in minutes.

In between the two are Markov chains, which is sort of like brute-forcing, but which follows the logic humans use to construct passwords. If a password letter is lower-case, it's overwhelmingly likely that the next letter will also be lower case, for example.

The upshot is that your 12 character password is a lot weaker than you assume. Your passwords not only have to be long, but also fairly random and not based much on dictionary words, and random in ways that Markov chains can't easily guess.

NSA leaker Edward Snowden recent suggested that a strong password would look like "MargaretThatcheris110%SEXY". he's been criticized for this, but actually, it indeed pretty strong. Yes, there are lots dictionary and Markov weakness, but they are compensated for by length. All else being equal, longer is better. Indeed, whatever password you have now, simply adding "xxxxxxxxxxx" onto the end of it it likely to make it unbreakable, and it's extremely easy for you to remember. A password like "MaThis110%SX" is a 12 character password such that even the NSA is unlikely to be able to break it if it were your Lastpass password -- Snowden's longer form doens't make it worse. (Note, some people claim this Snowden example isn't so secure, but they are wrong).

The downside of password complexity is that you have to both remember the password and type it in frequently. There's really no getting around this -- but that's tools like Lastpass or 1Password are for. They allow you to choose one strong pasword once, then have the system use secure random passwords for all the websites you visit. I don't use such services, I just get use to typing long strings very fast (and write down passwords), but it's a solution used by many others.


Luke said...

Lasthash > Lastpass?

Quentin Minster said...

This is usually the point where I bring up Diceware. It makes even insanely long passwords much easier to remember.

David Wong said...

they say they use clientside hashing in addition as well " in addition to the rounds performed client-side" so it's more than 10,000 rounds of pbkdf2.

Also relevant xkcd: https://xkcd.com/936/

Unknown said...

Qwertycards is also useful, as a offline password manager solution, or using the card alongside a online password manager (www.qwertycards.com)