If the hash is stored independently in another table as you suggest, then an attacker attacks each account by performing the hash on each potential password and checking to see if it is in the set. If that set is small enough to fit in memory (and they could likely store billions) then a simple contains check doesn't buy you very much. It is simpler to raise the work factor of the hash.
If someone is using dedicated hardware it may make it a bit trickier to implement, but it also makes things trickier for you to manage. Better to use a hash designed to thwart such an attacker (like scrypt) up front.
In any case, one can seed the hashes table with a couple billion random hashes, making the lookup slower for both parties. It would hurt the attacker more, given the nature of brute force.
The first thing he would do is a dictionary attack from a list of common passwords: Pick one user, create the hash and search the hash table for a match. That is one step more than only having to check the hash in the same row. I'd say it is slightly, but not significantly, more difficult.
http://opine.me/a-better-way-to-store-password-hashes/
http://opine.me/all-your-hashes-arent-belong-to-us/
http://ethanheilman.tumblr.com/post/28481738192/security-thr...
Any chance you would have time to elaborate a bit? I like the idea of having a table full of hashes with no (clear) link to accounts.
Password table has one column: hash(userid+password+salt).
Login process: given userid and password, look up salt. Check if hash(userid+password+salt) appears in Password table.
Password reset process: Given a userid and new password, change salt to a new random value and save to User table. Insert hash(userid+new_password+new_salt) into Password table. The old hash remains in the Password table and could still be used to log in, but in theory is useless because the salt has been destroyed.
Implementation detail: Make sure the old salt really is destroyed.
EDIT: After thinking about this, I think the reason not to do it is that it doesn't really win you much protection over the usual approach -- a single table with userid; salt; hash(userid+password+salt).
In that scenario, if your database is stolen then the attacker will have to brute force each user password individually and compare it to the stored hash for that user. You hopefully used an expensive hash() algorithm so that will be a slow process. The only thing the separate table adds is an extra table lookup during each brute force attempt, which compared to the cost of hash() is basically free.
So yeah, I don't think this really gets you anywhere.
EDIT2: In fact, you get almost exactly the same effect by making your bcrypt()/scrypt() parameters one notch harder. Crypto primitives FTW.
Even if all of these fancy hashing algorithms are implemented, it only makes it slightly more difficult to crack weak (common, short, dictionary word) passwords.
The idea is that you have a passwords table and whenever someone sets a new password / registers, you insert something like "hash(userid + password + salt)" into the table. There is no link between the account and hash, when the user logs in, you need to check the existence of the computed hash on the table. If someone dumps the database, at best, they have some password hashes with no way to connect them to user accounts.
Password changes would require asking the old password but I guess there is no way to implement 'forgot password' functionality here? How would you invalidate old passwords?
Is this something viable? Anyone uses anything like this? I thought about adopting it on some new auth systems we are working on but losing password recovery is downer.
edit: Changing the salt on account information would take care of invalidating old hashes I guess..