Sign in with
Sign up | Sign in

LinkedIn's Password Breach and Official Response Dissected

By - Source: Tom's Hardware US | B 23 comments
Tags :

We dive into the LinkedIn password breach and how the information may be cracked.

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/

Discuss
Ask a Category Expert

Create a new thread in the News comments forum about this subject

Example: Notebook, Android, SSD hard drive

This thread is closed for comments
  • 1 Hide
    A Bad Day , June 10, 2012 4:00 AM
    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?).
  • 6 Hide
    oafed , June 10, 2012 6:17 AM
    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?
  • 1 Hide
    freggo , June 10, 2012 6:25 AM
    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.


  • Display all 23 comments.
  • 0 Hide
    Anonymous , June 10, 2012 8:08 AM
    "such as finding 050 starting from 000 and 999"
    O really? Wasn't it 500 maybe?
  • 2 Hide
    Chipi , June 10, 2012 8:33 AM
    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.
  • 2 Hide
    unksol , June 10, 2012 8:53 AM
    Quote:
    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.
  • -3 Hide
    randomizer , June 10, 2012 9:30 AM
    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.
  • 0 Hide
    A Bad Day , June 10, 2012 12:51 PM
    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.
  • 1 Hide
    Chipi , June 10, 2012 1:00 PM
    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 :) )
  • 0 Hide
    Jerky_san , June 10, 2012 1:36 PM
    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..
  • 0 Hide
    acku , June 10, 2012 2:51 PM
    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.

    There are partial hashes in the list: linkedin, LinkedIn, L1nked1n, l1nked1n, L1nk3d1n, l1nk3d1n, linkedinsecret, linkedinpassword

    substitution is easy to code and compensate for.

    Cheers,
    Andrew Ku
    TomsHardware.com
  • 0 Hide
    ojas , June 10, 2012 3:05 PM
    @Andrew:

    What about leetspeak?

    For example, "Serendipity&" could be "$3r3nD1p1ty&"
  • 0 Hide
    acku , June 10, 2012 3:08 PM
    Quote:
    @Andrew:

    What about leetspeak?

    For example, "Serendipity&" could be "$3r3nD1p1ty&"


    That would be harder, but not impossible. Strong passwords should look completely random. Word-based passwords are weak.

    Check out what this guy did with only a CPU. (cracked 900k passwords in 4 hours)
    https://community.qualys.com/blogs/securitylabs/2012/06/08/lessons-learned-from-cracking-2-million-linkedin-passwords


    Quote:

    If I tried to match the word linkedin slightly modified (reversed or with '1' or '!' instead of 'i' like in l1nked1n):



    In the first iteration, 558 passwords found in the 554,404 (0.1%) are related to the ‘Linkedin’ string;
    In the second iteration, 3248 out of 22,688 (14%) are related to the ‘Linkedin’ string;
    Third iteration: 1,733 out of 3,682 (47%);
    Fourth iteration: 539 out of 917 (59%);
    Fifth iteration: 217 out of 330 (66%);
    Sixth iteration: 119 out of 152 (78%);
    Seventh iteration: 40 out of 51 (78%);
    And so on through the tenth iteration.



    An example of what I found on the 7th pass is: m0c.nideknil



    Another example is: lsw4linkedin, which was found on the tenth pass. To illustrate how the rules work for modifying words in the dictionary, below is the actual set of modifications used to get from the dictionary entry 'pwlink' to the successfully cracked password 'lsw4linkedin' over the ten iterations:



    pwdlink from pwlink with the rule "insert d in 3rd position"
    pwd4link from pwdlink with the rule "insert 4 in 4th position"
    pwd4linked from pwd4link with the rule "append ed"
    pw4linked from pwd4linked with the rule "remove 3rd char"
    pw4linkedin from pw4linked with the rule "append in"
    mpw4linkedin from pw4linkedin with the rule "prepend m"
    mw4linkedin from mpw4linkedin with the rule "remove second character"
    smw4linkedin from mw4linkedin with the rule "prepend s"
    sw4linkedin from smw4linkedin with the rule "remove second character"
    lsw4linkedin from sw4linkedin with the rule "prepend l"
  • 0 Hide
    jryan388 , June 10, 2012 4:23 PM
    That's why I have around 6 random passwords of 10 to 12 character random strings of mixed caps, numbers, and symbols that I have memorized.
  • 0 Hide
    STravis , June 10, 2012 8:53 PM
    A Bad DayWonder 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.


    Gmail provides for two factor authentication - there is NO reason NOT to use said feature.
  • 0 Hide
    acku , June 10, 2012 10:42 PM
    STravisGmail provides for two factor authentication - there is NO reason NOT to use said feature.


    Agreed.

    Cheers,
    Andrew Ku
    TomsHardware.com
  • 0 Hide
    PreferLinux , June 10, 2012 11:48 PM
    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.

    Ever heard of a dictionary attack? It is easy to include those modifications in the dictionary (which will make it several times longer, but nowhere near as much as a completely random password that is several characters shorter).

    By the way, one thing that was missed in the article is rainbow tables – using them would drop the cracking time massively, even for long random passwords.
  • 0 Hide
    bebangs , June 11, 2012 1:08 AM
    wow. i have linkedin account 5years ago. i've never used it. so now i have to change password for all other accounts and email!? YOU SUCK!
  • 0 Hide
    tntom , June 11, 2012 1:39 AM
    I am always getting on my wife for using the same password for everything. I have to go in and change them for her. I know it is not as secure as memorization but I keep them in a password protected file. I only use similar passwords for things like webforums where I want something easy to remember but could careless if someone hacked it.
  • 0 Hide
    acku , June 11, 2012 5:14 AM
    PreferLinuxEver heard of a dictionary attack? It is easy to include those modifications in the dictionary (which will make it several times longer, but nowhere near as much as a completely random password that is several characters shorter).By the way, one thing that was missed in the article is rainbow tables – using them would drop the cracking time massively, even for long random passwords.


    The existing rainbow tables appear to have already been used. That's built into the ~3.5 million hashes that start with 00000. Now it's dictionary and brute-force cracking with iteration/variation strings.

    It's my impression that hackers used RTs first (working backwards from the text file). They would be the easiest to check against, because they are pregenerated hashes. You don't need a fast computer to do that. Plus, if your password can be looked up using a RT, it's definately not a secure password. RTs are for common stuff. Anyone with "passwordpassword" is just looking for trouble.

    Cheers,
    Andrew Ku
    TomsHardware.com
Display more comments