Do I have to have a different salt for each password? Should I use a different salt for each password?

In my system, there are no user names, only passwords.  When a user logins in, he types in one or more passwords and the server compares the results of the password(s) hashed many times (PBKDF2) for authentication.  Each password might unlock some subset of functions.

As I see it, salt has two purposes:


Decrease the feasability of using (rainbow) tables: The salt makes rainbow tables with just ascii characters useless and the cost of making rainbow tables for all possible salts is greater than that of brute-forcing the password.
Unique salts per password mean that users selecting the same password won't have identical authentication results.


In my situation, using a salt per-password makes authentication an O(n*n) problem, time that could be spent on adding rounds to the hash.  With a single salt, (1) is accomplished and (2) doesn't matter because there are no user names.

So, can I use just a single salt?
"In my system, there are no user names, only passwords."


This is the real problem.  Using the same value for both identification and authorization is usually a bad idea, for several reasons:


Two accounts cannot have the same password.
An on-line attacker needs only a single query to determine if any password in the system matches their guess; thus, they can attack all accounts in your system simultaneously with no more effort than attacking a just single account would take.
Since you cannot use per-account salts, an off-line attacker has the same advantage: they can hash each guessed password and then quickly match it against the table of valid hashes.


About the only time when using a single combined identifier/authenticator may be valid is when this identifier is randomly generated and known to have very high entropy (say, 128 bits or more).  With that much entropy, even the odds of guessing just one identifier out of millions of valid ones are acceptably low.  However, such long random tokens are generally impractical for humans to enter or memorize, so they're usually only practical in low-level automated protocols, e.g. as session identifiers.

You also write that:


  "When a user logins in, he types in one or more passwords [...]. Each password might unlock some subset of functions."


So it seems that, instead of the passwords being associated with user accounts, they're associated with some kind of roles.  That's a pretty interesting design, but I won't argue about its merits as such, compared to more traditional user account schemes; presumably you have some reason for designing your system like this.

However, what you could do is give names (or at least some kind of identifiers) to the roles, and have the users enter both the name as well as the password for each role they want to use.  That way, you can use the name to look up the relevant authentication record &mdash; which can then include a per-role salt &mdash; in the database.

In any case, naming your roles sounds like a good idea for other reasons too: surely there are times when you'd like to be able to refer to a particular role without divulging its password?