It's somewhat optimistic to assume that the adversary knows no passwords - even if you can't create a user, phishing one isn't that hard. That makes recovering the salt much easier.
Well yeah, but then you're proposing a brute force against the salt and the salt can be anything of any length.
So if you're assuming a salt that can contain standard latin letters and digits and is 256 in length, that's 62^256 possible variations.
Do note that I'm not saying here that MD5_HMAC doesn't have flaws, but it definitely doesn't have the same flaws as MD5, cracking it ain't easy and I can't find a reference for an instance in which this was actually done.
Well, I thought it was assumed :) ... since salting a hash has inherent vulnerabilities if you're not doing it right and HMAC is a sane way to do it.
I really don't get this argument that since MD5 is fast to compute, that's the reason it is vulnerable. That's not true, MD5 is vulnerable for other reasons, like collision attacks are possible, preimage vulnerabilities were demonstrated, huge rainbow tables are precalculated and so on and so forth.
However, HMAC_MD5 does not have the same vulnerabilities and increasing the size of the salt increases the time of a brute force attack exponentially. 62^256 is a freakishly big number and it doesn't matter much if you divide the work by 100,000 computation units. But if that makes you feel uncomfortable, you can always increase the salt to 1000 chars.
And I simply don't buy that we have enough computation power in this world to brute force something with 62^1000 computational complexity.
Phishing the password from one user and recovering the salt shouldn't be useful in the first place. The parent example was only meant to show how difficult it is to recover a salt even with multiple examples of its use, not to give a real life example of password hash use. (Which was my point)
That said, I don't know how you would obtain a list of hashed passwords without also getting the associated list of salts (wouldn't they be in the same database?), so it is kind of a moot point. The different salts are intended to prevent against the ability to have a single rainbow table to crack every password in the database.
Instead, you need a table for each salt, which means that you basically have to brute force the entire database. This still doesn't really help if you are using something fast like MD5, as brute force solution will be possible with that algorithm. Which is why you want something reasonably slow.
Having the exact salt in the same database as the user data defeats the purpose of the salt.
Normally you have a global salt, somewhere in your source-code, which you combine with the per-user generated salt. It also doesn't have to be something obvious in the database (like a column named user_salt :)), you could just use something like HMAC_MD5(global_salt, email + username + joined_date) for each user.
Of course, this may seem like security by obscurity, but even in the case of SSH you keep your private key safe and as a business if you have both your database and your source-code compromised, you're fucked anyway.
The purpose of the salt is to defeat time/space tradeoff attacks by inflating the required space to the point of impracticality. ie. 20 bits of salt will increase the size of the rainbow table required a million times.
