Comment by RyanZAG | Hacker News Reader

Comment by RyanZAG | Hacker News Reader

Parent Full thread

>> So someone with a big list of usernames and known salts and MD5s just proceeds to generate MD5s of a list of common passwords + the salt, and then compares that to the list of stolen hashes, and ends up with a pile of passwords that work.

You mentioned earlier that rainbow tables aren't used anymore - but this is exactly what rainbow tables are. Precomputed lists of passwords + salt. That's why I was talking about the entropy in the salt earlier - the more randomness in the salt, the more infeasible it is that anybody would have your rainbow table. And you're right, /dev/urandom of a fairly large size is perfect, but the crypt($user.$time.$rand) is not all that bad either as it does have $rand in there.

I think you were agreeing with me here, and if so I'm just confirming your confirmation. ;)

>> thousands of iterations of that will always be slower, on all hardware, than a single iteration of anything else.

If your FPGA array can brute force 10 characters of bcrypt in 8 seconds and 10 characters of SHA1 in 1 second - does it really matter? If you have pushed the time to crack down into feasible time, the exact number of seconds becomes irrelevant. The hacker may have to step out for a coffee if you use bcrypt instead of getting the results right away. Hardly more secure?

> ...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.

Pretty good calculations of the kind of expected time: 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.

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.

The goal of a salt is to make it so that each password must be targeted individually. The salt need not be random, only unique and sufficiently long. It is impractical to precompute the hashes for (that is, have rainbow tables for) every possible salt, since rainbow tables take up a huge amount of space and take time to generate. Instead, you have to choose a specific password you want to attack and generate the table just for that password. Somebody is not just going to "have the rainbow table" for the salt G$F#V2.

Your calculations are off by several orders of magnitude. Bcrypt can be customized to take more time, but a reasonable amount of time might be 0.1 seconds per password, or 10 passwords per second. Most users are already logged in, so logging in should not be a very common operation.

By comparison, a $500 graphics card can hash billions of SHA1 passwords per second. So what takes 1 second to brute force with SHA1 will take 100 million times as long, or over 3 years, to brute force using bcrypt.

Note that a 10 character all lowercase password has 26^10 possibilities. If we are just targeting this password it will take 19 hours at 2 billion SHA1 hashes per second (well, on average half of that, so around 10 hours), and over 447000 years at 10 bcrypt hashes per second(again, half that on average).

Reply on news.ycombinator.com