You're right, salt just protects against rainbow tables, my mistake. Increasing the cost so that a single brute-force attack would take a few years/decades is a

You're right, salt just protects against rainbow tables, my mistake. Increasing the cost so that a single brute-force attack would take a few years/decades is actually fine. I don't see why it would then be "too simple to get the SSNs", given that you're using a different salt with each. Here's another idea: Use a secret salt, similar to AWS's secret id. Make it long enough that it would pretty much impossible to brute-force (do the calculations). Does that seem like a workable solution? Of course, if the "secret" isn't secure, then well, you're in trouble, and if the secret is in your code in plaintext... Yeah, it's an uphill battle. I'm sure someone more experienced than me here can provide some solution.