Common misconceptions of password cracking

After this great article on passwords at Ars Technica, I've seen some common misconceptions pop up. I thought I'd clarify them (even though that article adequately covers many of this, people seem to have missed them).


MD5 is broken, use SHA1 instead

MD5 isn’t broken as far as passwords are concerned. Sure, it has “collision” problems, making it unsuitable for signing things (such as certificates), but that really has nothing to do with passwords. Thus, MD4, MD5, SHA1, SHA2, SHA3 are all roughly equally secure as far as passwords are concerned.


Because SHA1 is cryptographic that means it’s secure

Hash functions are designed to be fast, which means they make password cracking fast. But for logins, there is no need to be fast. You want slow algorithms to make password cracking slower. Algorithms, like scrypt, bcrypt, or PBKDF2 will be better for passwords.

In other words, for protecting passwords, a cryptographic algorithm is necessary, but not sufficient.


Rainbow-Tables

Most mentions of Rainbow Tables are a misconception. After every major password breach, like the recent LinkedIn incident, numerous cybersec “experts” make the claim that they “should use salts to stop Rainbow Tables”. That’s nonsense.

In the LinkedIn case, a single 7 letter password can be cracked in minutes, an 8 character password in a day, and a 9 letter password in months. A rainbow-table doesn’t make finding that 7 letter password any faster, and rainbow-tables don’t exist for 9 letter passwords (using upper/lower/digit/symbol). It would only speed cracking of that 8 letter password from a day down to a few minutes. Sure, rainbow-tables help, but not as much as you’d think.

Rainbow-tables have their uses. Bitweasil, for example, is doing some cool things with them (like web-tables and much better GPU acceleration). But mostly when people mention rainbow-tables, it’s because they are repeating a misconception.


Salt is a magic pixie dust to secure passwords (from Steven Alexander)

As mentioned above, salt makes only a small difference stopping rainbow-tables. The major effect it has is stopping that "mass crack", like cracking millions of LinkedIn passwords all at once. But if the hacker is targeting a single password, salt makes little difference at all. Yes, passwords should be salted, but no, don't imagine that it's sufficient. What's far more important is whether they used scrypt, bcrypt, or PBKDF2, not whether they used salt.

Online vs. offline password guessing

When we talk about cracking passwords, we mean “offline” cracking. We mean hacking into a website, stealing their password database, and trying to decrypt the passwords (by guessing potential passwords and seeing if the hashes match).

Guessing passwords online, such as using a tool that sends passwords at the target, means we can guess maybe 100 passwords per second. Guessing offline means doing a BILLION passwords per second.

Moreover, many sites defeat online guessing by disabling access for a time after too many failed attempts. No such mechanism exists for slowing down offline cracking (other than using the scrypt/bcrypt algorithms to slow cracking).


Just as secure as they’ve always been

In the past few years, password crackers have jumped forward a huge amount. They now use GPUs and FPGAs to jump forward a few years ahead of expected Moore’s Law increases. Most importantly, all these massive password dumps like LinkedIn and RockYou have taught crackers what patterns to look for, making their guesses much better. Thus, your password has gotten a lot less secure in the past few years.


Amazon EC2 will defeat passwords

Not really, as I explain here and here.

Brute-forcing passwords is an exponential problem. That means having 100 times more compute power just means you can crack an 8 character password in the time you would’ve taken to crack a 7 character password. It doesn’t mean 100 times better password cracking.

Amazon EC2 economics are not designed for integer compute. The economics are not there. For the average hacker or pentester, a good GPU will be vastly better. Amazon EC2 really only makes sense in an emergency, when you absolutely have to crack something faster than it takes to go to the store and buy up all the GPUs.

GPUs are oodles faster than CPUs

Yes, but not as much as you’d hope. Like I explain above, brute-force cracking is an exponential problem, so doubling your cracking speed has a tiny improvement on effectiveness. Buying the latest GPU is useful, the marginal gains are large for the price, but the marginal benefits of buying even a second GPU are small.


Here’s a password hash; how long will it take you to crack it?

This isn’t how things work. We crackers sort our efforts according to effectiveness. We’ll try the most effective methods first, and if they fail, choose less and less effective methods. If your target chose a secure password, then I’m never going to be able to crack it.

Given a single cryptographic hash algorithm (MD5, SHA1, MD4), it’s a 30% chance I’ll find it in a few minutes, and 90% chance I’ll find it after a couple of days. As time goes on, the chance I’ll find the password keeps going down, so if I haven’t found it after a day, it’s unlikely I’ll discover the password even after a year. (It's a 'long tail' distribution)


Password meters (from Pers Thorsheim)

Many websites have some sort of "password meter" to show the "strength" of your password. While they certainly point out "weak" passwords, just because they claim your password is strong doesn't make it so. Don't believe them.
Links:
http://securitynirvana.blogspot.com/2010/02/never-trust-password-meters.html
http://securitynirvana.blogspot.com/2010/11/revisiting-password-meters.html


Password requirements

Many websites have password requirements, like forcing you to include numeric digits or upper/lower case. These have only limited utility, as many people choose predictable patterns, like appending '1' to the end of the password to meet the requirement.

Curiously, by reducing the search space, such requirements can sometimes help the attacker.

Password strength (from XKCD)

Uncrackable passwords (from XKCD)