Furthermore, I want to avoid revealing pairs of users with identical passwords, thus use a user-specific salt. Lastly, I would like to add a random challenge (aka nonce) into the mix to ensure an eavesdropper* can not use the final hash as the new "password". I will make an additional roundtrip to the webserver to obtain the salt and challenge before starting the password hashing. *) Yes, we are using SSL, but as a defense in depth I would like to make the implementation as solid as possible.
Especially the challenge is challenging. The only feasible implementation I know of, is first calculating the final password hash (using bcrypt, scrypt or PBKDF2) and then do one additional sha256_hmac round using the challenge. On the server-side we fetch the password hash from the database and perform the same additional sha256_hmac and compare the result.
Question #1: Am I correct that nowadays bcrypt should be at least 12 rounds, and PBKDF2-SHA256 at least 5000 rounds? So I should choose the 5000 rounds of PBKDF2-SHA256?
Question #2: Do there exist challenge-response mechanisms that can operate earlier in the process (e.g. on a once hashed password), so I can leave the bcrypt/PBKDF2 hardening to the webserver?
Question #3: Assuming no such challenge-response mechanism exists, is it better to abandon my challenge-response requirement and only apply a user-specific salt client-side and do thorough hardening server side? Would that result in an overall stronger system than using a challenge-response mechanism and less rounds?
EDIT: To summarize the long trail of comments below about the security of client-side hashing in general: the general opinion seems to be that the added complexity is not worth it and it is better to put the effort in auditing the server-side code and limiting server-side access for untrusted staff.