1

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?

  • This looks like an XY problem: you have the unknown problem X which you are trying to solve by having the hashes comparable. Only now you run into problems since this implicates security. Instead of rethinking X to find alternative ways to solve it you stay with Y and ask here for a solution to solve it. If you would provide X too one could maybe help you to solve the real problem. – Steffen Ullrich Apr 10 at 12:16
  • 1
    @SteffenUllrich Unfortunately I can't describe the actual system in too much detail for confidentiality reasons. I am considering alternative approaches to this issue, including different approaches, but I've asked this question in case this kind of comparison is a solved problem. – Chris Parton Apr 10 at 12:28
  • 4
    I'm afraid without any indication why you want to be able to compare hashed data for equality, it's difficult to give advice on how to use alternative systems. – MechMK1 Apr 10 at 12:32
  • @MechMK1 I totally understand. I expected as much, but given confidentiality constraints I decided to ask the question anyway, on the off chance there was some obvious solution I was missing. – Chris Parton Apr 10 at 22:25
2

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.

  • I do indeed need to compare them to each other. I can't go into much more detail than that for confidentiality purposes, I'm afraid. Passwords are already stored with unique salts and hashed thousands of times with a strong algorithm. I didn't realise that a global salt was called a pepper, good to know :) – Chris Parton Apr 10 at 22:24
  • Salts make direct comparison of hashes impossible, by design. If you can compare two hashes to each other to see if they are the same, then if you crack one of them, you get the other one for no additional work. So if 10,000 users choose 'password' as their password, then cracking one cracks all 10,000. I do not know of a way to enable direct comparison without drastically reducing user security in this way. – Royce Williams Apr 11 at 7:33
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.

  • Thanks for the detailed answer, you've pretty much confirmed my own thoughts on the matter. Seems like the best case for this approach is to use a large random salt that isn't stored on the filesystem. Passwords are already stored with unique salts and hashed thousands of times with a strong algorithm, so no problem there. – Chris Parton Apr 10 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.