Xjyuk

We have a scenario where we need to prevent two users from using the same identifier. The identifier is sensitive (e.g. a social security number), so we do not want to store it in our DB. We just want to store some sort of hash that allows us to prevent subsequent users from using it again. And we want to do it securely, so that in the event that the database ever leaked, an attacker could not figure out the original values.

Is it possible to do securely? What is the recommended way?

Based on some research, it seems like a HMAC might work. If that's the case, what's the recommended algorithm? Should it be something slow (like scrypt with a fixed key salt), so that if the key is ever exposed, it's still difficult to uncover the values? Or is there no protection against that?

I think you're not too far from a possible solution (aka using a modern KDF and effectively treating this like a password). However, there are some more considerations (which were already mentioned in comments):

1. SSNs have very low entropy, which means that brute-force is an especially easy attack


2. Since you need to find if the SSN has been used anywhere, you basically have to operate without a salt, which also makes brute-forcing substantially easier.

The combination of 1 & 2 would make a KDF a bad idea, even though it is your only option. As a result, finding a different business solution may be in order. However, I think there are a few steps you can take to mitigate the risk if SSN matching is an absolute requirement:

1. Make sure and use a large "pepper". Peppers are less commonly used with passwords, so in case you aren't familiar: using a pepper basically means adding a large, constant, random string to the SSN before hashing which is not stored in the database. In this case I would use an especially long pepper. So in practice, this means that you create a 256 bit key that is not stored in the database or codebase but which is added to the SSN before hashing it. You would store it in an environment variable in your production server, or in your CD pipeline, so it is not readily accessible to developers (since they are sometimes the attacker, unfortunately). The reason for this is that if your database leaks but the attacker doesn't have the pepper, then they cannot bruteforce the SSNs (because bruteforcing the SSN would basically require first bruteforcing your 256 bit key, which is impossible).


2. Use a very large cost function. All modern KDFs have a configurable cost function, that increases the time it takes to buid the hash (therefore making brute force harder). For something like this I'd set an even-higher-than-usual cost function. I'd probably tune it so that your systems take 1-2 seconds to hash the SSN+pepper. Go even higher if your users can tolerate the wait! This won't fix your bruteforce issue, but it will help.


3. Anonymize these hashed SSNs! Basically, store them in a table by themselves with no way to associate them with any other data in the system (i.e. don't assign an autoincrementing id to this table or an entry time, since those might correlate with other tables). Have one table with just one column that is for this purpose and this purpose only. While the SSN alone is still personal information, it is much less dangerous to your users if it is leaked by itself without any further information. Having a table with just the hashed SSNs will still allow you to verify if an SSN has been entered before, so your overall goal can still be accomplished.

So again, your best bet might simply be to find a completely different way to do this without using SSNs. However, if this is an absolute business requirement, then the above steps can go a long way to securing your customer's personal data. Still, I would also check with regulatory requirements for your industry to make sure that you abide by all applicable rules.