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:
- English language has ~300k words
- Conversation English has somewhere between 15k and 20k words.
- 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/
