LinkedIn's Password Breach and Official Response Dissected

Following the leak of 6.5 million LinkedIn passwords, many made a mad dash to change their passwords, and now that things have finally started to settle, the company has posted an official response on the matter.

The second paragraph by Vicente Silveira, Director of LinkedIn, states, "First, it's important to know that compromised passwords were not published with corresponding e-mail logins. At the time they were initially published, the vast majority of those passwords remained hashed, i.e., encoded, but unfortunately a subset of the passwords was decoded. Again, we are not aware of any member information being published at any time in connection with the list of stolen passwords. The only information published was the passwords themselves." So maybe things aren't that bad? The answer depends and requires more dissection.

The last portion of the email talks about how LinkedIn is in the process of transitioning "from a password database system that hashed passwords, i.e. provided one layer of encoding, to a system that both hashed and salted the passwords." Say what?

In other words, these passwords were merely protected with a single SHA-1 hash, which amounts to a part time mall cop as opposed to an armed escort. For those not in the know, hashing in its purest form is simply a way to a convert several data sets of varying length into a smaller set of fixed length. Think of it kind of like a one-way decoder ring. That's the extent of what LinkedIn did to secure passwords. As we explored with WPA, salting (which is part of LinkedIn's new protocol) is the more serious stuff that requires serious hardware to crack.


I played with the leaked password file about two days ago, and I think the forum post by John Graham-Cumming largely sums up my own observations. In the password file, there are roughly 3.5 million passwords that begin with 00000. These entries appear to be hashes that are already comprised and broken. The others not denoted by zeros at the beginning number another 3 million or so, and these appear to be unbroken.

These unbroken passwords aren't necessarily safe. In fact, I've cracked many of them on my own. The problem is LinkedIn only used a single SHA-1 conversion. This makes it child's play for anyone with a fast graphics card and some GPGPU-optimized software.

On these matters, Ivan Golubev's my favorite guy to talk to. His cryptography work with GPGPU is amazing. Using his ihashgpu app, a single 6990 is capable of processing ~2.6 billion single SHA-1 hashes per second.

Now consider the following:

  1. English language has ~300k words
  2. Conversation English has somewhere between 15k and 20k words.
  3. The search space with brute-force cracking is n^(length of password), where n is the number of elements to choose from.

If the password only contains words and numbers, I can search through all two and three word/number combos in matter of minutes, and I can process the entire 3 million chuck of unbroken passwords on my coffee break.

If the password is sufficiently random, it's much harder to break. Assuming we're dealing with alphanumeric and say 50 percent search time (passwords are usually discovered in the middle of a random search, such as finding 500 starting from 000 and 999), it would take me about half a day to break a single hashed password using a 6990. The caveat is that we've capped password length to 8 characters. With ~3 million entries, this speed isn't practical. Bring it down to 7 characters max, and now we can process each entry in around 15 minutes. The total search time for all ~3 million entries is now 85 years. Give a team of hackers some Crossfire 6990 configs, and that time drops down to 5 years.

At the end of the day, the LinkedIn's breach is serious, but the significance to your personal security is hard to estimate. LinkedIn's blog post is careful to point out email logins weren't published by hackers, but this doesn't exclude them from having this information. LinkedIn hasn't explicitly stated whether email logins were part of the original breach. Hackers could have just chosen to publish the password hashes only.

If email logins were part of the breach, I'd consider every word-based password to be toast. Though, not everyone may be at risk. LinkedIn claims a user base of ~160 million. The published file contains no duplicates, which means we're dealing with ~6.5 million unique passwords. Given the amount of password reuse and poor password choices (i.e. passwordpassword or LinkedIn), it's not improbable every single password was leaked. However, several people converted their password to an SHA-1 hash and told me their password was not on the list.

For those who use random passwords, if it happens to be under 7 characters in length, I'd say you're at risk and need to change your password. Other sites were also reportedly breached (i.e. eHarmony) in what might be related attacks, which is why those profiles too should be updated. If you fall into this camp, we have a recommendation.

While more secure, there's no question that long random passwords are hard to remember. Words-based passwords, though easy to recall, are also very easy to break. There is a way to bridge the gap and get the best of both words. Use a mnemonic. Flip open a book, take an uncommon sentence, and use the first character (or second...) of each word. Then, add a number at the end. Thus, "To grunt and sweat under a weary life" from Shakespeare's To Be Or Not To Be, becomes "tgasuawl9." This strategy has long been used by security experts for their own passwords, as it's easy to remember and confounds brute-force cracking. Make sure the phrase is longer than 8 words, and you should be good to go.

Update: Check To See If Your Password Has Been Compromised

Users at risk have been notified, but it's very likely the hackers have more passwords. If you don't want the websites contacting you for notification of a breach, you can check if your LinkedIn or eHarmony passwords have been compromised via LastPass:

LinkedIn: https://lastpass.com/linkedin/

eHarmony: https://lastpass.com/eharmony/

  • A Bad Day
    I never understood what the IT departments or the higher ups that had full control over what the ITs did were thinking. Did they really think they would get away with weak encryption, or even without encryption?

    Then again, maybe they were completely blind to the news for the past year or were lazy, like an unnamed company that still uses Windows NT 4.0 because the OS still works (so why replace it?).
    Reply
  • oafed
    I think other personal information has gotten in the hands of spammers. I think this for 3 reasons.

    1) An email account I rarely use (but have had for 10 years) was hacked this morning and locked out for sending spam. It had the same password as my LinkedIn account.

    2) My friends gmail informed him that it had blocked someone in Peru who was accessing his account. He said his gmail was the only other account he had with the same password as LinkedIn.

    3) I am hearing of a lot more spam coming from friends email addresses in the last couple days.

    Coincidence?
    Reply
  • freggo
    A Bad DayI never understood what the IT departments or the higher ups that had full control over what the ITs did were thinking. Did they really think they would get away with weak encryption, or even without encryption?Then again, maybe they were completely blind to the news for the past year or were lazy, like an unnamed company that still uses Windows NT 4.0 because the OS still works (so why replace it?).

    There is only so much security you can implement.
    The problem is not 'weak' security.
    The problem is that there are not serious enough consequences for hacking.

    Put a 20 year minimum sentence on major attacks; put serious law enforsment resources behind finding theose guilty; and make the -short- trials VERY public. Than the rest if these idiots will get the message. You get caught... your life as you know it is over.
    Think about this from the perspective of the 6+Million accounts (not just people) affected. The amount of time lost, money lost, their worries. You are not just screwing with a 'big company'; you are screwing with the lives of Millions of people.

    This is not kiddy stuff, this is a Major Financial crime all told.
    Lock 'em up with Bubba and the gang, and loose the key.


    Reply
  • "such as finding 050 starting from 000 and 999"
    O really? Wasn't it 500 maybe?
    Reply
  • Chipi
    Holy cow! I just found my password has in the list, unbroken.

    Good thing it's 12 characters long, with "random" letters and numbers, and I don;t use it for any email accounts.
    Reply
  • unksol
    9373872 said:
    There is only so much security you can implement.
    The problem is not 'weak' security.
    The problem is that there are not serious enough consequences for hacking.

    Put a 20 year minimum sentence on major attacks; put serious law enforsment resources behind finding theose guilty; and make the -short- trials VERY public. Than the rest if these idiots will get the message. You get caught... your life as you know it is over.
    Think about this from the perspective of the 6+Million accounts (not just people) affected. The amount of time lost, money lost, their worries. You are not just screwing with a 'big company'; you are screwing with the lives of Millions of people.

    This is not kiddy stuff, this is a Major Financial crime all told.
    Lock 'em up with Bubba and the gang, and loose the key.

    You do realize the internet is global, you can hop on open wifi, and this person was (probably) in Russia right?

    you can't even figure out who a hacker is unless they are an idiot let alone chase them down. nevermind that consequences don't do anything to prevent normal crime. the problem IS weak security because crime will never. ever. stop.
    Reply
  • randomizer
    You don't need to use mnemonics and you don't need to use a password made up of entirely random characters. You just need a long password that uses a large character space (ie. at least one lowercase and uppercase letter, one number and preferably one special character). "pAssw0rd1112!" is a much stronger password than ")1!#Bjt1{.#" by orders of magnitude.
    Reply
  • A Bad Day
    freggoThere is only so much security you can implement.The problem is not 'weak' security.
    Wonder why I use long complex passwords for Gmail and Yahoo Mail? Because I prefer forcing the hackers to break through those companies' security measures rather than giving them a weak password to play with.
    Reply
  • Chipi
    randoMIZERYou don't need to use mnemonics and you don't need to use a password made up of entirely random characters. You just need a long password that uses a large character space (ie. at least one lowercase and uppercase letter, one number and preferably one special character). "pAssw0rd1112!" is a much stronger password than ")1!#Bjt1{.#" by orders of magnitude.
    Notice how the word random is in in quotation marks in my sentence. That means I'm not using it literally ;)
    What I meant was that my password looks like a bunch of random letters and numbers, but it's actually a sentance in my head.

    And I never said random symbols, I said letters and numbers. Maybe you should drink your coffee first, huh...

    I'm not even gonna comment on your statement regarding the strength of those 2 passwords, it's just ridiculous :))
    Reply
  • Jerky_san
    it would seem hotmail does the same thing if you look at their login screen as its logging in... I tried to post it but it wouldn't let me.. but it appears they only use SHA1 on their stuff as well..
    Reply