You're missing a threat model
I see two obvious threat, both involving being able to query your database. There surely are others (suggestions welcome):
- A - An attacker stole your DB (and server salt) and wants to infer the Facebook IDs of all your users
- B - An attacker knows the Facebook information of a specific user and wants to figure out if they exist in your DB (without breaking all its entries)
- C - An attacker with exactly the same capabilities can also change the code running on your server, adding information stealers that will report the IDs/passwords of users as they log in over time
Let's now look into your proposals
- Use same server salt for all hashes.
This is still necessary to avoid pre-made rainbow tables, but indeed will only slow down any attack carried out for A or B. Make sure to combine with a slow hashing function to further increase the cost of finding your hashed IDs for A.
- Encrypt the Facebook user_id instead of hashing.
How do you decrypt your IDs when a user logs in? Surely the decryption key is stored somewhere. You could store the encryption/decryption key on a separate physical device, so that decryption attempts must take place on the server rather than truly offline, since the key can't be taken. There might also be systems that can alert you when a threshold of decryption requests is reached but this is not my area, I don't know if it exists (just note you can't rely on your server to do that because of the threat model; your server is fallen).
You could also store the salt in that device, and then in both cases the security is a factor of how long it takes an attacker to encrypt/hash a known user ID with all possible keys/salts. I am not a crypto expert at all so I can't give any orders of magnitude on what's best to do but intuitively a crypto scheme with a large key is better (also probably more computationally expensive).
- Create dynamic salt as a function of the user_id - something like:
Hash(Hash(user_id) + user_id)
Well, this is rather useless. If you want to complicate an attack for the A threat, then you need to ensure that the additional information is independent from the ID you hash. For instance, an email address or date of birth will vary from user to user, effectively increasing the input search space of your attacker. The B threat is completely unaffected since all the Facebook data is already available to your attacker.
Here it's hard to do something against B... If they know your hashing algorithm and can check if a specific hash is in your DB you can't do much. But again this is more likely the same capabilities as threat C, which is even more serious. Of course good hashing practice is important to slow down an offline bruteforce attack but you also need to consider the other issues you'll face in such a scenario. You should find out how to detect attacks and alert your customers that they might be phished or spammed because of a breach on your service (as a motivated attack will eventually have retrieved all the user IDs).