Necessity of Randomness of Salts?

Given the desire to have unique salts for each user of your system, is it actually necessary to create a cryptographically-random salt for each user?

If your system already has some other unique user identifier (be it an ID, user-name, or an Email address) is there any effective decrease in your security if you simply use that value as your salt? It results in a unique salt for each user, and does not require the additional generation and tracking of a new value per user.

-

If your system already has some other unique user identifier (be it an ID, user-name, or an EmailAddress) is there any effective decrease in your security if you simply use that value as your salt?

The salt in a hash actually forms two different purposes. Generally, it is acceptable for a salt to be known, so let us consider H() a hash function, S, some data and P something to protect. From this information we store H(S+P) and S. There are two consequences for the attacker in generating a rainbow table for H(S+P):

1. Either they can generate a huge rainbow table for the entire set of possibilities that might be S+P. The longer the data you wish to reverse in a hash, the larger the data storage requirement of the rainbow table, so extending the length of the hashed data makes it infeasible to reverse the hash by generating a generic rainbow table.
2. The attacker can generate a rainbow table for the specific fields of input missing for a specific salt. Clearly, the usefulness of a rainbow table is then restricted to a specific set of hashes to attack, since in theory all other hashes should be useless.

In the case of 1) anything you add as salt will do, quite literally. The problem is the case of two. The reason for using unique, random salts is that the chances of colliding salts for a specific hash output are vastly reduced. For example, hashing userid:fred:mypassword and userid:fred:myotherpassword, a rainbow table generated knowing the salt userid:fred and the correct construction of the hashed text would work across both cases.

-
As far as I can see, using a global (i.e. database-specific random) salt together with the user ID as the hash input would work similarily good for both 2. as a per-user random salt, as the attacker would have to create a rainbow table for one user on one system in both cases. Am I wrong here? –  Paŭlo Ebermann Jul 12 '11 at 22:21
@Paŭlo Thomas answers this in his comment with the two-password same salt problem. Perhaps I should have a 3) for that? Also, there is a practical consideration - what happens if you change user name for any reason? You'd need to recompute the hash, so you'd need the password to be input. That may or may not be acceptable to you. –  Ninefingers Jul 12 '11 at 22:27
Okay. For now, avoiding repeated passwords having the same hash is the only advantage I can see here. (And allowing user name change without password input - I suppose often this will not really be needed.) –  Paŭlo Ebermann Jul 12 '11 at 22:44

Salts must be unique. Randomness (with a "good" random generator) is sufficient to ensure uniqueness.

A per-user ID (e.g. the user login name) is not sufficient for uniqueness, because it does not capture some occurrences which do happen in practice:

• two users on two distinct systems (running the same software) which share the same ID (how many Joes and Bobs are out there ?)
• a user who decides to change his password (the old and the new password will then share the same salt)

Even if these two specific cases happen not to be a worry in your situation, you cannot be sure that you thought of all possible cases. On the other hand, a random salt, of sufficient length (say 128 bits or more) and filled with appropriately good random bits (from a cryptographically secure generator), provably yields the uniqueness you need (with overwhelming probability).

-
Why is it a problem if new and old password share the same salt? –  Paŭlo Ebermann Jul 12 '11 at 21:13
For the first point, I thought about using a system-specific global salt, combined with the user's login name. –  Paŭlo Ebermann Jul 12 '11 at 21:14
@Paũlo: old passwords are valuable for an attacker, because they could be valid passwords for the same user on other systems; old passwords can also be very new passwords: some (many ?) users "rotate" in a list of 2 or 3 passwords. –  Thomas Pornin Jul 12 '11 at 21:18
Paŭlo, if there's a global salt, then any two users using the same password will eventually have the very same cyphertext in the database. And even if you combine that salt with user ID's, an attacker will have quite a higher chance of retreiving the key with combining all the passwords with all the user ID's. Using a global salt value means XOR'ing the passwords with the very same salt value, and given the attacker has knowledge about the user ID's too (which themselves each act as a second, transparent salt here), it kind of goes pointless to use such a value at all. –  uygar.raf Jul 12 '11 at 21:19
@uygar: global salt + user ID, of course. –  Paŭlo Ebermann Jul 12 '11 at 21:20
show 3 more comments

The real purpose of the salt is to make it so that the attacker can't even start to use their resources to brute force until they know the salt, therefore buying valuable time to change passwords after a breach.

If the salts generated in any predictable manner, an attacker already has a head start on breaking your passwords - they can do all the computational work (in the form of rainbow tables for the salts they are interested in) in advance of actually breaching the system to get the password hashes.

Keep salts random, keep them long, keep them secret, and keep them individualized per-hash. You can add a global hash to that as an additional hash, but it should also be long and random, and you should have it planned in advance how to handle changing it often.

-