24

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.

e-sushi
  • 17,891
  • 12
  • 83
  • 229
GWLlosa
  • 659
  • 1
  • 6
  • 8

4 Answers4

15

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.

  • 1
    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
  • 1
    @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. –  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
10

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

Thomas Pornin
  • 86,974
  • 16
  • 242
  • 314
  • 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
  • 5
    @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
  • 2
    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
  • My point is, if the attacker has user ID's, and the cyphertexts, salt value makes it harder for the attacker to use differential cryptanalysis. In this case, using a global salt is (at least in theory) not any safer than using any salt at all, since the attacker will have access to a lot of user data to work with. Combining a global salt with user ID will make it impossible to see if two passwords are same just by looking at the cyphertext with plain eye, but it won't help against cryptanalysis at all. – uygar.raf Jul 12 '11 at 21:26
  • @uygar: The global salt will only avoid reusing the same tables between different databases where the user might have an account (with same user name), and to recognize whether the user has the same password there. – Paŭlo Ebermann Jul 12 '11 at 22:05
  • @Paulo the problem with non-random salts is that the generated passwords will be predictable, like Windows, which makes it a lot easier to brute-force the passwords, since a string will always hash to the same value –  Jul 12 '11 at 23:04
4

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.

Stephanie
  • 141
  • 5
3

The purpose of a salt is to make it difficult to precompute the inverse hash table, and to prevent the birthday weakness. Neither of these require the salt be random, just unique.

For a real life example, by default Kerberos uses your username and realm as the salt. Given the nature of Kerberos it absolutely must be predictable for a given user. But since username+realm is unique, you cannot precompute a rainbow table once and use it against every site in the world. Even in the weaker configuration using realm-only salts, you'd have to recompute it for every domain you wished to attack.

jldugger
  • 131
  • 2