With my understanding of bcrypt, it's an algorithm that's designed to be slow (and the implementation providing guarantee's to resist attempts to significantly speed it up), and the slowness is tuneable through a work factor. So usually you would target something like 200-500ms. Long enough to be slow if you have to make billions of guesses, but still fast enough that when someone enters their correct password they're not sitting around waiting for you're login to complete.
If my database is something like:
salt1 + alex = aaaaaaa
salt2 + ben = bbbbbbbb
salt3 + kevin = ccccccc
* with 100,000 entries
This means if I want to find user = kevin in this database, I take the salt + username, and test if it produces a match in the database. Once I get to salt3 + kevin, and produce cccccc, and see that cccccc is in the database, I've now unmasked that user.
At 500ms, a single CPU can test 172,800 entries per day, which could easily scan the database. If it's millions, or tens of millions of users, you do need more resources, and if you want to unmask every user it will take some time, but it becomes plausible for a moderately sophisticated adversary with moderate resources.
The algorithms like bcrypt, scrypt etc are great for passwords, where depending on the password used, you need to make billions of guesses. However, if you reduce the problem space down to millions or thousands of guesses, because you already know the username, the email address, or the date of birth because this is not secret information but public information, these algorithms being slow helps significantly, but not enough to work alone.
Yes, strictly speaking a salt is not a secret, and would generally be stored with the data you are salting.
If you change the semantics and make the salt a secret that is stored separately, it does make this difficult to attack, but the advice I was given is it would be better to use hmac, which is already designed to work this way based on storing a secret.
Okay, that's what I thought. Under my current use-case, I think what I'm doing is quite adequate. But, your post is very relevant to what I think I'm going to need to do at some point soon, so thank you!
