# 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:

1. 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.

2. 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?

-
How many valid passwords are there in your database? –  CodesInChaos Aug 30 '12 at 15:30

"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 — which can then include a per-role salt — 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?

-
What about the user entering a single string composed of their username and their password (possibly with a separator)? Doesn't this schema have exactly the same strength as the classical one? –  maaartinus Aug 30 '12 at 18:12
Sure, that's fine — it doesn't matter how they enter the name and password, as long as the backend code gets some kind of user/role identifier that's not also doing double duty as a secret authentication code. Having two separate input boxes/lines/prompts/whatever for the username and password is just a common user interface convention. –  Ilmari Karonen Aug 30 '12 at 18:52
What I meant wasn't the UI, but using the whole string the way the OP proposed, i.e., something like searching for PBKDF2(username + ":" + password). –  maaartinus Aug 30 '12 at 20:37
That's also OK. You can toss the username into PBKDF2 along with the password if you like, it'll just act as a sort of an extra ad hoc salt (but you should still use a proper random per-user salt too, because usernames can be predictable). The point of having the username part there is that, because it's not meant to be secret, you can store it in plain in the database and use it to look up the correct record to test the password against. –  Ilmari Karonen Aug 30 '12 at 20:53

The purpose of a salt is to prevent multi target attacks. Rainbow tables are just one, rather overrated special case of multi-target attacks. A single salt won't prevent multi-target attacks.

In your system that means than an attacker who isn't interested in attacking a specific user, can simply check his candidate password against all passwords at the same time. So his chances of cracking a some users scale with the number of users you have.

This means users of your system should have stronger passwords than users of normal systems.

-