Comparing uniquely salted hashes

Question

I have a system which needs to compare hashed identifier values. I want to salt my hashes, to prevent them being cracked with a rainbow table.

However, the system needs to be able to compare the hashed identifiers, so it seems that the same salt needs to be used for every hash.

A common salt would help protect the data from a pre-existing rainbow table, but an attacker could brute force crack one hash, determine the common salt, then crack the remaining hashes.

My question is, is there a more secure way to store the identifiers whilst preserving the ability to use them for matching?

Answer 1

What kind of "matching" are you trying to do?

Do you really need to compare them to each other (which would be unusual)? Or do you just need to verify that a particular user knows a particular password (the normal use case)?

If you're just trying to do basic authentication, that's the way unique salting is supposed to work. The authentication system knows each unique salt, and when the user tries to log in, uses that user-specific salt to generate a hash from the presented password. If it matches, the authentication is successful.

There should be no reason to have to compare users' passwords to each other. In fact, by using the same salt across many users, then even if you're resistant to a hypothetical custom rainbow table, as soon as the attacker cracks one user's password, they've cracked that password for all users who use that password. This reduces the security value of proper hashing.

You can also have a sitewide additional salt ('pepper') if you'd like. But unless you're storing that pepper in an HSM, if the attacker compromises the system and can steal the hashes, they probably also have access to the code performing the authentication and can pull that pepper from disk or memory anyway.

Use large per-user salts - random enough and large enough to be virtually guaranteed to be unique across a very large user base.

Answer 2

I want to salt my hashes, to prevent them being cracked with a rainbow table.

However, the system needs to be able to compare the hashed identifiers, so it seems that the same salt needs to be used for every hash.

This is fundamentally incompatible. You can prevent an attacker from using a public rainbow table (e.g. from some website) by adding some value to each password, but the attacker could make their own, custom rainbow table, which includes your random value. The whole point of a salt being "unique, not secret", is that it thwarts any sort of rainbow table from being used.

If you manage to keep that value secret, your hashes remain safe. But if it leaks, it's nearly as bad as having no salt.

Encrypting (as suggested in a now-deleted answer) has nearly the same properties: if your encryption key remains secret, that's great; but if that leaks, you are back to a plain hash. In fact, encrypting is worse because you are actually back to a plain hash. In case of a secret value being mixed in with the hashing, at least an attacker still has to make their own, custom rainbow table instead of downloading a few gigabytes from the internet.

The secret value mixed in with hashing is typically called a "pepper" value, but I'm hesitant to use it here. Usually, the standard scenario is a database system that is separate from application code. If an attacker finds an SQL injection vulnerability and the database is configured properly, then an attacker cannot read arbitrary files on the filesystem. If there is a secret value in a config file which is applied to user passwords, then an attacker can never crack the hashes, because they are missing that secret value. Because you describe a custom scenario, I am not sure that this would be the same type of situation. Also, a pepper is additional to a salt, one would never recommend to leave out a salt in favor of pepper. But like the now-deleted answer also said, pepper without salt is better than nothing.

an attacker could brute force crack one hash, determine the common salt, then crack the remaining hashes.

And that is why you should mix in a big enough secret :). Anything north of 128 bits (16 bytes) is plenty for that purpose, you could use head -c 16 /dev/urandom | base64 to generate them. (On Windows, I'm not sure how to easily talk to the system's CSPRNG without third-party tools.)

is there a more secure way to store the identifiers whilst preserving the ability to use them for matching?

It becomes a question of how you define "matching", like Royce brings up. If, indeed, you need to match them for equality, then you run into the (to my knowledge) fundamental incompatibility of the two properties. But if, like Royce says, you need to just match them to the original password, then you could use a normal salt+pepper scheme, where the salt is unique for every entry, and the pepper is a global secret to prevent a leaked database from being catastrophic for weak passwords.