The technology press is talking widely about a serious data breach at LinkedIn, in which 6.5 million password hashes were apparently leaked onto file sharing sites by an unknown hacker group. If you haven’t already done so, check your password by visiting leakedin.org, a courtesy site that calculates your password hash and checks it against the leaked database.
As you should, I checked my LinkedIn password against the database, and was shocked to find it was in there. Here’s the thing: Because I’m aware of the risks posed by “rainbow tables” (Wikipedia), I use long, complex passwords for all of my logins. My LinkedIn password was 13 characters long, and contained a mixture of upper and lower case letters, numbers, and symbols (i.e. !@#$…).
By using a 13-character password with this mixture of symbols, I reduce the risk of my password being guessed through brute force attacks, by ensuring that an attacker would need to test an unreasonably large number of passwords before finding mine. For fun, I used Wolfram Alpha to determine the search space for my password. Here’s what that calculation looks like:
total symbols = (26 letters from a-z) + (26 letters from A-Z) + (10 numbers) + (10 symbols) = 72
total number of 13-character passwords = total symbols ^ 13 = 1.4 × 10^24
average number you have to guess = total number of 13-character passwords / 2 = 7 x 10^23
… that’s 7 with 23 zeroes, or one million billion billion and change; approximately 1 septillion.
Modern brute-force password hashing programs running on GPU hardware can test approximately 11 billion passwords per second. That’s a big number, but it’s not nearly large enough to conquer a septillion.
If you divide 7 × 10^23 by 11 billion, you get ~6.4 × 10^13. This is the number of seconds in 2 million years. In other words, if you wanted to brute force guess my 13-character password drawn from a 72-symbol character set, it would take a well-equipped computer 2 million years.
Let’s say you had a big cluster of computers — 10,000 of them. It would still take 200 years to guess my password.
In summary, I don’t think these passwords were brute-forced. It just doesn’t make any sense. These passwords weren’t brute-forced. They were stolen in plaintext (from LinkedIn’s servers or elsewhere), and whomever stole them published the SHA1 hashes simply to prove to buyers of the data that they had the real goods.