Store hashes for a finite set of strings that would be extremely time consuming to reverse via table lookup but also allow grouping

Question

Lets say I have finite set of strings (lets say half a billion). There can never be any other strings I would need to store other than these half a billion strings. The strings may be repeated in my database. I need a safe way to store these values so that I can take user input, run it through the same hash and test if the value exists. I also need a way to be able to group values that were the same before the hash without to much exposure to the original value. Lastly values may be added at any point in time, so the grouping of values can't be done prior to hashing. I will never need to know the original string value that was hashed.

I need to be able to group rows based on this value, but I don't need to know what the original value was they were grouped by.

For brevity of my question, if I used a hash (CRC-32) by itself I would end up with values in the following table. (I'm not going to use CRC-32, it's for an example because it's hash is short and easy to demonstrate the question. I'd most likely used bcrypt or PBKDF2)

                   Original
                   Value
Id Name  Hash      Not Stored
-----------------------------
1  Erik  68EFFF54  Apple       
2  Tim   1A69B44E  Orange
3  John  68EFFF54  Apple       

So obviously Erik and John have the same hash they can be grouped. However because they have the same exact hash within a finite set of values, it wouldn't be too hard for a malicious user to get all the possible values, run the hash against them all and obtain a lookup table.

Using a Salt does not seem to solve the problem because if the database compromised, it wouldn't be too hard to create a table with lookups that included the salts (obviously it would take longer, but I doubt any significance).

I could use a Pepper but if the code was compromised this could also be a problem.

It seems to me the best solution is to have a column where I hash the value+pepper+salt. This column would be used to search for user input. But I'm still stumped has to how I would be able to create a secure way to group values.

(I'm also aware that CRC32 is not really a hash, it's just a checksum and that they serve completely different functions :)

Answer 1

I am no expert in the field, but this seems a good use case for a Hardware Security Module which encrypts all hashes before storing them in the DB.

Using the appropriate algorithms, Identical hashes would be identical when encrypted, hence your indexing need would be satisfied.

An attacker with access to the database would be unable to rebuild the hashes. In order to build a lookup table the attacker would require prolonged access to the HSM. This should satisfy your security requirements.