Comment by RyanZAG | Hacker News Reader

Comment by RyanZAG | Hacker News Reader

Parent Full thread

He does seem to imply that Dave's solution works, and if you read the last line:

$hash = hash_it($password, $crypt);

So it is fairly clear that $hash and $crypt would be stored in the DB. $crypt is a reasonable (but not great) salt:

crypt($user.$time.$rand);

$user is obviously known, $time is the time when the password was created - or maximum ~2000 possible values for most systems. The main part of the hash is $rand, which is 31 bits of pseudo-random entropy. So about 40 bits of entropy if I'm not mistaken? That should be enough to make it infeasible to create rainbow tables in advance.

EDIT: I'm wrong on $time - it is "mdYHis", so much more than 2000 possible values and is actually pretty decent in the salt, as it's unlikely an attacker would know which user registered when. Unless you publish the registration date as some forums do...

EDIT2: While user is known for each user, it does add extra required input for a rainbow table - if there are 1000 users and you know all of their usernames, you would still need to generate 1000x more rainbow tables (1 per known username) if you wanted to crack all 1000 passwords. Also slows down brute forcing, as you can't use the result of one 'trial' on all users at once. (Correct?)

The real main issue is the speed of brute forcing MD5/SHA1 - it's probably possible to brute force these passwords very quickly if the database is stolen. Use of bcrypt is therefore obviously preferred to slow it down - but it is also very likely that FPGAs can brute force bcrypt just as fast, so I'm not sure how much I agree with the common mantra of 'sha1 is useless, use bcrypt'. bcrypt does, after all, have a speed impact on your login requests and puts more load on your servers if you are handling thousands of logins per second...

I guess large scale FPGAs are probably only in use by NSA and some syndicates, while far more hackers have access to mass GPUs?

There are a few things in your comment here that I think are wrong or irrelevant, but I know very little about this stuff, so I'm reluctant to be adamant about it.

> ...rainbow tables...

That's not really relevant anymore. Rainbow tables aren't used, and haven't been for a while; once you start using salts of any kind, there's no point to rainbow tables.

> Also slows down brute forcing, as you can't use the result of one 'trial' on all users at once. (Correct?)

Correct, but any random salt will do. I think you'd usually be better off reading from /dev/urandom though, but for the purposes here I don't think it matters.

> The real main issue is the speed of brute forcing MD5/SHA1 - it's probably possible to brute force these passwords very quickly if the database is stolen.

Exactly. Ordinarily, what happens is a database gets ripped via an SQL injection or some other thing, and then a list of the usernames & passwords gets posted to a forum somewhere where people take turns brute-forcing them in chunks.

MD5 and SHA1 both give recognizable hash values -- you can glance at either one and usually tell which it is.

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.

But, there is a challenge here in GoofHash(): if only the database was stolen, and if the methods used to generate the hashes aren't known, then the hashes would be useless. Attackers could tell at a glance that they had SHA1 values, but even assuming that the "salt" was clearly labeled as such in the stolen database, brute-forcing salt + common passwords wouldn't give them the SHA1 values they're looking for.

So I'm a little circumspect about how bad this approach is. I still wouldn't hesitate to say that it's not as good as using known approaches, but if the end goal is the protection of users' passwords, this might be sort of OK -- as long as nobody knows what they're dealing with. Still though, "security by obscurity" is generally not considered to be a smart approach by people like Schneier.

edit: Oh, I meant to respond to this,

> ...but it is also very likely that FPGAs can brute force bcrypt just as fast...

I don't think so. bcrypt (or, better yet in this regard, scrypt) depend upon stretching -- hashing the hash over and over again. Standard SHA1 doesn't do that, so you're pretty much comparing "one iteration of SHA1 versus thousands of iterations of hashF()"; assuming that hashF() isn't found to be broken in some horrible way, thousands of iterations of that will always be slower, on all hardware, than a single iteration of anything else.

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