14 ms·

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

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.

RyanZAG 14y ago
>> 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?
- thaumaturgy 14y ago
  > ...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

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

thaumaturgy 14y ago
> ...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.