Are Rainbow Tables Attacks even a threat?

Question

let's just assume a simple non salted hash function, just a plain old $hash = md5($pass).

Premises:

1. the password hashing all takes place server side, and the hashes are stored in the database. The client has no way to see these.
2. a rainbow table attack must have knowledge of the hashes in order to retrieve passwords.

Given premise 2., that would mean that the hacker already has control of the database, in which point you have a much bigger problem on your hand.

So, is the point of trying to foil a rainbow table attack simply to protect the retrieval of passwords from an already compromised database/system. Is it that simple or is there something else that I am missing.

I'm already familiar with password hashing techniques, but am just wondering why there is so much hype about rainbow tables. Thanks!

Marlenmarlena

Think of your users. Would you like to explain to them that all of their passwords got compromised? Just ask Gizmodo... – Overspend

Answer 1

Yes.

Many people use the same password for everything. Compromising the original password (as opposed to simply changing it to something you know) can often give an attacker access to someone's accounts on other services.

Rainbow tables are also much less computationally intensive (simple lookup) than a dictionary attack (which requires hashing) or brute force (which requires a lot more hashing).

Use strong, unique passwords!

Roccoroch

+1, decided I'm not massively adding anything to what you've said. – Drivein

Answer 2

1. Password compromise doesn't require control of the database. What if I break into your car and steal a stack of DVDs with database dumps? You do back up your database, right?
2. As mentioned, people use the same password for multiple sites. HBGary fell victim to this when they were hacked by Anonymous recently. One server with an SQL injection vulnerability turned into a much larger compromise.
3. If I have access to your database for five minutes and get the hash, I now have access to your account until you change the password.
4. Salt is cheap.
5. You should use a key derivation function anyway, not a salt.

Martyrize

You should use a salt along with the key derivation function. In fact, PBKDF2 requires one (a standard derivation function for password based keys)... – Overspend

Thanks for point 1. I hadn't taken that into account. and yes I back up my Database :) I also agree with your points 4 and 5. – Marlenmarlena

@ircmaxwell -- Yes, I wasn't clear about that. I meant "not just a salt." – Martyrize

Answer 3

Most of the time, data-theft from databases succeed through injection; sometimes even blind injection.

An attacker who has found a database injection exploit in one of your scripts doesn't gather any control over the rest of the system until he is able to retrieve some kind of higher credential - which could be the admin's password.

If you (being the admin) have your password stored as a simple md5() hash together with the rest of the users, and the attacker manages to retrieve it - he could eventually overtake your system by using a rainbow table to look it up.

Anthiathia

Answer 4

If I understand them correctly, rainbow tables remove the computational burden of calculating the hashes (which is deliberately high), so attacking is faster.

Kaiserism

Actually, computing hashes is supposed to be very low burden (in fact, it's one of the criteria in selecting a good cryptographic strength hash function, that it's fast). The burden you speak of is because there are so many possibilities to try, not that each possibility is expensive (in fact some crackers can hash upwards of 15 million passwords per second). That's why you should stretch your keys to make them slower to brute force... – Overspend