4 ms·

Presumably the salt is stored separately in the database.

by gizmo 14y ago

thaumaturgy 14y ago
That would be fair, but I didn't assume so since that wasn't mentioned in the original post.
- RyanZAG 14y ago
  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?
  - thaumaturgy 14y ago
    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.

Presumably the salt is stored separately in the database.

by gizmo 14y ago

Presumably the salt is stored separately in the database.

thaumaturgy 14y ago

That would be fair, but I didn't assume so since that wasn't mentioned in the original post.

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