Wednesday, August 22, 2012

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.


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.

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)


Anonymous said...

Actually there is rainbow-tables for 9 letters passwords

rainbow-tables won't stop password attack however they will slow it down. In the example you mentioned if linkedin passwords where salted cracking them will take much longer than cracking the passwords with no salt.

Anonymous said...

I meant salting will slow down password cracking it won't stop it.

Anonymous said...

A very interesting and pertinent overview of passwords cracking. Generating rainbow tables for longer passwords is just a matter of (cpu) time. As said previously for salting, it just slows down the problem of their building. I think the Figure you display would be better with a logarithmic y axis.

George said...

When Adobe "upgraded" Acrobat to SHA-1 from MD4 (I guess to achieve NSA Suite B status), they severely downgraded the password security of PDF documents. Instead of running 100 rounds of MD5, they switched it to a single round of SHA-1 making it trivially easy and fast to crack the password protecting the PDF file.

JPGoldberg said...

I am one of the people who talked about using salt to defeat rainbow tables.

Once I understand what I did wrong, I will be happy to issue a correction.

Anonymous said...

Um. Rainbow tables DO make finding that 7/8/9 char password a lot faster - because they've already been found. That's what a rainbow table is.

Salting, especially with multiple rounds, invalidates any standard SHA-1 rainbow table - hence a cracker is starting from scratch. And with no knowledge of the salt, he cannot generate one either. Hence, salting is an excellent countermeasure.

Steven Alexander said...

Anonymous: salting prevents rainbow tables. Even a 16-bit salt would make rainbow tables impractical. A large salt (i.e. 128-bits) makes rainbow tables impossible.

ba san said...

These bags will always remain in style because of their simple beauty, materials used and brilliant detailing that makes this bag worth every penny spent. Another reason why women prefer these designer Lanvin handbag is because it suits every woman right from teenagers to women in their late 40’s and even beyond! They never look garish or out of style even for the youngest or the oldest woman who carries these Lanvin bag.Link :

Ryan Lackey said...

The reasonable way of using AWS to attack hashes is to use the nvidia-enabled nodes, and to have them burstable as needed, with the ability to use a stolen credit card and tor to access them potentially. $2.10/hr for these is pretty appealing.

Ladadadada said...

Robert said: "rainbow-tables don’t exist for 9 letter passwords (using upper/lower/digit/symbol)"

Anonymous said: "Actually there is rainbow-tables for 9 letters passwords"

None of the 9-letter rainbow tables on that site include upper and lower case, numbers and symbols. Ones that do would be orders of magnitude larger.

"rainbow-tables won't stop password attack however they will slow it down"

How much? It matters. Salts have a use, but increasing attack time on a single password is not it. Even if they do achieve that, it isn't their purpose. Choosing the correct hashing algorithm is what you should do for that purpose.

"Generating rainbow tables for longer passwords is just a matter of (cpu) time."

No it's not. It's storage too. Rainbow tables are a way of trading off CPU for storage. The download times are significant. The storage costs are prohibitive. (This is a simplification but you can't cheat the maths.)

mbethke said...

As for helping the attacker by reducing the search space: suppose people use passwords up to 12 characters with uppercase, lowercase and digits. Now forbid anything in a big dictionary (say 10 million words if we include a bunch of languages) and anything up to 6 characters. That's 62^6+10*10^6=56,810,235,584 combinations the attacker doesn't have to search, or 0.000000002% of the remaining search space. That's like "making your work easy" by shaving 50 ┬Ás off your 8 hour working day :)
On the other hand it effectively prevents people from using "password", "secret", "12345" and such that are susceptible to online bruteforcing even if your password DB is perfectly secured.