The past few weeks, I’ve been on this security kick particularly when it comes to encryption. I’m developing my own app in my spare time. So I’m trying a whole bunch of things, no doubt making plenty of mistakes in the process. Luckily, the data I am protecting is only quasi-valuable so I can afford to take a hit due to my own conscious incompetence.

Anyhow, I ran across this article on Ars Technica yesterday entitled “Why Passwords have never been weaker—and crackers have never been stronger.” It’s a long article and it will take you a while to read it, but here is my summary:

* * *

The hardware has gotten better

Because of advances in technology, passwords have become easier to crack for determined hackers. Part of the reason for this is advances in hardware. As the cost of hardware keeps dropping, hackers/attackers can push through more and more combinations of passwords in the same amount of time. This reduces the amount of time it takes to break a password.

The software has gotten better

One of the advances in breaking passwords has been the advancement of rainbow tables. Rainbow tables are basically a way of storing pre-encrypted tables of common passwords. I used to think that a rainbow table was just a super big table of pre-encrypted passwords and that the reason this was possible was because of the low cost of storage.

However, it turns out this is not what a rainbow table does. Instead, it efficiently compresses pre-computed passwords and only stores the minimal amount of information. You then use an algorithm to search for a hash that you do have, and if you hit it, work your way backwards (or rather, start at the front of the chain and go forwards) until you find the original key. I may do a future blog post to explain rainbow tables, but for now this article here does a good job: Kestas Kuliukas.

Password algorithms are frequently implemented poorly, part 1

Part of the problem with the LinkedIn breach, as well as eHarmony and Yahoo Voice is the lack of salts when hashing the password. A password salt is a unique random string that is added to the clear-text password of every user’s password. The password + salt is then hashed instead of just the password. For example, a database might store a user’s login information the following way:

username: [email protected]
salt: 7xsLOp
password: fba1d284701ccd85e1314fe51c727eb50dcf5670

When the user logs in, he types in his password. The web portal:

a) Transmits the information
b) Looks up his username
c) Gets the salt
d) Combines it with the entered text that was the password, then hashes it.

If it matches, then the user’s login has succeeded. In the above, the user knows that his password is “password”, but the string “7xsLOppassword” was hashed. Thus, even if a hacker pre-computed every SHA1 hash in the English language, his hash of the word “password” would be “5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8” which is different than the above hashed string. This doesn’t necessarily defeat a determined hacker. Instead, they might create multiple rainbow tables that consist of multiple salts.

However, this drives up their cost because instead of maintaining a single rainbow table, they have to maintain lots of rainbow tables. For example, if they knew that the salt was six characters, and if the allowable characters were letters and numbers, then they’d have to maintain (26 uppercase + 26 lowercase + 10 digits) = 62 x 62 x 62 x 62 x 62 x 62 = 56 billion rainbow tables. If they’re going to do that, what they are trying to steal had better be worth the cost of maintenance (maybe a rainbow table of rainbow tables?).

Some systems include another salt, called “peanuts” which is a common string across all passwords. In our example, a hashed SHA password for “peanuts7xsLOppassword” is “ed410e919f2b4f13f2ebd0cd22d88d0fc4d45f64”. In this way, an attacker would have to figure out the random string “peanuts” (which could be any random letter/number combination) and then maintain an absolutely huge number of rainbow tables. The lack of salts in passwords makes it a lot easier for an attacker.

Password algorithms are frequently implemented poorly, part 2

The article also talks about the password hash that LinkedIn used—SHA1. SHA1 is designed to be fast. In other words, the amount of computer time required to compute a SHA1 hash is very small. Instead, a password hash like Bcrypt or PBKDF2 is designed to be computationally more expensive. It takes longer for a computer to figure it out. For humans logging into a webpage, this doesn’t matter because we can wait a second or two and we wouldn’t notice because the amount of time it takes to transfer data online is more than a couple of seconds (enter username/password, hit send… wait for response, page loads).

However, to a computer that is trying to compute as many hashes as possible, computing a SHA1 hash is 500,000 times faster than SHA512 (also more computationally expensive). Taking so long to perform all those hashes makes it computationally infeasible unless you have a ton of resources. Only governments have that type of money to burn on breaking security, and even then, only a handful of governments invest that much into security. Thus, the infrequent use of password hashes combined with the lack of salting contributes to making password cracking easier, especially with cheap hardware and good software algorithms.

* * *

Thus, all these factors combined are what make it easier for hackers today to crack passwords. Furthermore, because they already know what many of the most common passwords are (“password”,“123456”,“12345678”), this gives them a head start.

That’s how passwords have gotten easier to crack over the past five years.