51–59 of 59 posts
NO! This is a bad idea: "When a user logs in, you retrieve the salt for the given user, re-compute the hash as you normally would, and simply check if the resulting value EXISTS in the Hashes table. If it does, you consider the login as successful." This will cause false positives. Let's say that of the trillions of hashes, one is the one we want... But what if one brute forces the system? What if one of the brute at…
NO! This is a bad idea: "When a user logs in, you retrieve the salt for the given user, re-compute the hash as you normally would, and simply check if the resulting value EXISTS in the Hashes table. If it does, you consider the login as successful." This will cause false positives. Let's say that of the trillions of hashes, one is the one we want... But what if one brute forces the system? What if one of the brute at…
Do you really know what you're talking about, huh? Your pigeon-hole example is pretty wrong because you can't use intuition (with completely wrong numbers!) to judge, you use math. Let's say there's a trillion pigeons and the hash we're using is 256 bits. That 2^256 ~ 10^77. Divide that by a trillion and you still have 10^65. Vastly more than enough to be secure all the while solving two problems. First that with a specific user's password one can often access other services. Two, and most importantly, that the password database blows up and isn't feasible to steal any more, either over internet or in real life.
The only effective difference would be that the entire database would become a single unit instead of a collection of separate hashes. Both an attacker and your webapp need to carry this extra weight of a monolithic blob of un-dividable data. It probably won't really slow down an attacker trying to brute force it if he has the data, but it may be more difficult to get the data in the first place.
But if an attacker has access to, say 10% of the hashes, he'll still be able to brute force 10% of the user accounts with weak passwords.
A different way to get a similar result of requiring a huge amount of data to be able to start cracking, would be to treat the database like a huge bloom filter: treat the database as a huge bit array of (say) a petabyte, hash the user's password with a hundred different hash functions (but with scrypt-like slowness), and use those 100 hashes as 100 indexes into the array to set the corresponding 100 bits. To verify a password, create those same 100 hashes and check if all 100 bits are set. Now, if an attacker has access to a part of the database, he won't be able to determine with certainty of any of his guesses at the user's passwords are correct.
Yet a third way to accomplish the same goal: pre-generate a petabyte of random data. To hash a user's password, apply a standard scrypt, then based on the resulting hash, generate a 100 pseudorandom offsets into the petabyte of data. At each of those 100 offsets, read a few (say, 16) bytes from our petabyte of random data, and finally store a hash of (scrypt_result + huge_data[offset1] + huge_data[offset2] + ... + huge_data[offset100]). You'd still have one hash per user, but to check a hash you also need access to a huge block of random data. The block of data functions in a way as an additional system-wide salt.
Anyway, there are more ways to get to a similar result as the OP's proposal. I'm not sure if it buys any additional security or if it's just more of a hassle for the webapp implementing this, but at least it's fun to think about.
Doesn't this add a new vulnerability? If I can see the salt for a user, I can easily add a new password for that user _without anyone possibly being aware of it until it is used_ by just adding the hash of the desired password with the existing salt to the database.
Earlier quoted context omitted.
With this scheme random isn't quite enough though, it needs to be unique as well doesn't it?
Chances of generating two random 32-byte strings that collide are so tiny that you can as well say that they are unique.
Earlier quoted context omitted.
Chances of generating two random 32-byte strings that collide are so tiny that you can as well say that they are unique.
Remember that assumption is the mother of all fuck-ups, although in this case the risk as you say is minimal.
Earlier quoted context omitted.
This should be used with scrypt or bcrypt set to the highest difficulty your application can support. The point is to increase difficulty of targeting an individual user, and increase difficulty of stealing the data in the first place. This is separate and distinct protection from what scrypt/bcrypt gives you. [Edit] In a typical GPU accelerated brute force attack, the target hash and salt are both known as fixed 20…
Actually, I was wrong about O(log(N)), the lookup time is O(1), you just have to put all known hashes in a map structure, or even better, a rainbow hash. So your technique only adds some constant lookup time. Instead of if (hash == target_hash) ... you will do if (map[hash]) .... Sorry, I think you are wrong.
don't confuse true O(1) with amortized ;)