Store a Cryptographic Hash with look-up capability

Question

I want to be able to store the hash of a piece of text in a database and then allow a third-party to confirm its existence if they know the original text.

I do not want to store the original text, only the hash.

This text may be sensitive, so I feel that the hash should be salted; however, I can't salt each piece of text with its own random salt as I would need to know the salt used for each original piece of text before I can perform the look-up.

I could use a single (private) salt that is used for all text values; but this seems weak.

Is there a cryptographically strong solution to this?

Answer 1

If you need a really safe system with salting and key-stretching, then there is no way to make the hashes searchable. It is the same problem as with storing passwords:

• With salting you prevent rainbow table attacks, but one has to read the salt first before you can verify the data-hash.
• With key-stretching (making the hash slow) you can thwart brute-force attacks, but one cannot quickly verify many/all data-hashes.

This makes using safe hashes and searchability mutually exclusive. It depends on the required level of security, whether you can go without the salt, or if you can switch to less safe encryption.

One way out of this problem could be, to encrypt the data, without storing the key. This requires the user to enter a password every time he uses the service. From this user password you would then generate a key with a key-derivation-function and keep the key in memory as long as necessary.

Answer 2

You might consider using a detached signature rather than a simple hash value, if your application isn't vulnerable to the "learn the remaining information attack".

For example: Alice has a database of sensitive documents on a secured computer that is normally turned off. Before that computer is turned off, Alice uses that computer with that computer's private key to cryptographically sign each document, generating a different detached signature for each document. (The cryptographic signature algorithm internally uses some cryptographically secure hash algorithm to generate a full-width hash value). Then Alice copies those detached signatures to a USB stick and then puts that USB stick in a separate server that Alice keeps turned on and allows the public to access.

Later, Bob has some allegedly sensitive document in hand and wonders if it is the same as one of those previous documents. So Bob hashes the document in hand using the same hash algorithm, and uses the standard verification algorithm to see if it verifies against any of the detached signatures. (There's a 16-bit truncated hash value stored in each standard PGP detached signature, so software could be written to use a binary search to quickly find any signature(s) that might match, then if there are any matches, use the slow public-key algorithm to verify). The result will always be one of:

• No match: No, that document is definitely not on the secured computer.
• Match: Yes, that document definitely was on the secured computer.

(It's considered practically impossible to have false positives or false negatives).

details:

• "How does a public key verify a signature?"
• "How are detached signatures used to verify a file's integrity and authenticity?"
• "What happens when you verify a detached signature?"
• "Making and verifying signatures"

Answer 3

If you have relatively few pieces of text (for example, around N = 1000 pieces of text), and it's OK for your system to occasionally give a "false positive", you might consider using a truncated hash.

For example: Alice has a database of around N = 1000 sensitive documents on a secured computer that is normally turned off. Alice is willing to have a false positive error rate of e = 1/100. Before that computer is turned off, Alice uses that computer with any cryptographically secure hash function (SHA-3, BLAKE, Argon2, etc.) to hash each document (perhaps using the same publicly-published salt value for all 1000), then truncate the hash to log2( N/e ) = log2( 1000 * 100 ) = around 17 bits, then copy those 17-bit truncated hashes to a USB stick and then puts that USB stick in a separate server that Alice keeps turned on and allows the public to access.

Later, Bob has some allegedly sensitive document in hand and wonders if it is the same as one of those previous documents. So Bob hashes the document in hand, and compare its 17-bit truncated hash to each of the roughly 1000 hash values on the server (possibly using a relatively quick binary search). The result will always be one of:

• No match: No, that document is definitely not on the secured computer
• Match: That document might be on the secured computer.

This algorithm is fairly resistant to the "learn the remaining information attack", because there are so many false positives it's difficult for an attacker to figure out which one is the actual remaining information.

If someone randomly generates a bunch of documents (none of which exactly match any of the sensitive documents), I expect about 1% of those documents to have a coincidentally-matching hash value, giving the "false positive" of "That document might be on the secured computer". The remaining 99% of those documents give the correct "No, that document is definitely not on the secured computer".