3 ms·

> ...but this is exactly what rainbow tables are. Precomputed lists of passwords + salt. Rainbow tables are precomputed lists of hashes: md5('password1'), md5(

> ...but this is exactly what rainbow tables are. Precomputed lists of passwords + salt. Rainbow tables are precomputed lists of hashes: md5('password1'), md5('password2'), etc. Rainbow tables are not precomputed lists of hashes with salts: md5('password1'.salt), md5('password2'.salt). At the very least, salts will vary from database to database, so there's no reason to "precompute" anything that's salted. It doesn't gain you anything. What we're talking about here is different, the common approach to dealing with salted hashes. You have a big list of commonly-used passwords -- "abc123", "logmein", etc. -- and you have a list of hashes from your stolen database, and a list of salts from the same. You feed all that in to a program that just computes the hash using your password list + the known salt. If the salt varies by user, the attacker is in for a long day, but can still expect to break a lot of passwords if the database is using MD5 or SHA1. If the salt varies by user, and the database is using bcrypt (or better yet, scrypt), then the attacker is in for a long couple of years. bcrypt with a decent work factor should take in the neighborhood of 1 cpu-second on non-specialized hardware to compute a hash. If you have a database of 15,000 passwords, you're looking at 4 cpu-hours per hash. Compare that to GoofHash(): on my sorta-decent laptop, GoofHash() runs in 0.035s. That means that I can compare my entire password list against each user in the database in 8.75 minutes. That's a huge difference.

RyanZAG 14y ago
Pretty good calculations of the kind of expected time: http://security.stackexchange.com/questions/12994/whats-the-practical-limit-for-rainbow-table-based-bruteforce http://security.stackexchange.com/questions/12994/whats-the-... These are with MD5/SHA1 style hashes, which shows that your password is pretty safe regardless of hash method (as long as it has salt) if it has enough entropy in it. Pretty interesting.
- thaumaturgy 14y ago
  Nice link, thanks for sharing that. So, this also is a slightly different situation. If you are an end-user, yes, you can protect your individual password against stupid hashing schemes by using passwords with lots of entropy. (I use KeePassX for this.) However, if you are a service provider, you have to protect your users from the stupid passwords that around 30% of them are likely to use and re-use elsewhere, and you do that by using a smart hashing scheme (like bcrypt or scrypt) that makes brute-forcing the passwords an annoying and time-consuming endeavor.

RyanZAG 14y ago

Pretty good calculations of the kind of expected time: http://security.stackexchange.com/questions/12994/whats-the-practical-limit-for-rainbow-table-based-bruteforce http://security.stackexchange.com/questions/12994/whats-the-... These are with MD5/SHA1 style hashes, which shows that your password is pretty safe regardless of hash method (as long as it has salt) if it has enough entropy in it. Pretty interesting.

thaumaturgy 14y ago
Nice link, thanks for sharing that. So, this also is a slightly different situation. If you are an end-user, yes, you can protect your individual password against stupid hashing schemes by using passwords with lots of entropy. (I use KeePassX for this.) However, if you are a service provider, you have to protect your users from the stupid passwords that around 30% of them are likely to use and re-use elsewhere, and you do that by using a smart hashing scheme (like bcrypt or scrypt) that makes brute-forcing the passwords an annoying and time-consuming endeavor.