Protect the original message of a hash from brute force

Question

My apologies for the somewhat inaccurate terminology.

Basically I have some simple messages (entropy ~50 bits) the user will use for registration. The messages should remain private, and I don't plan to keep that in my database. However, I do need to keep a hash so that I know when the same message is used again. (this is quite similar to ProtonMail registration)

Using simple hash it would be trivial to run through all possible messages to find the original messages from the hash, even if a really slow algorithm is used. Besides, a random salt probably can't be used as I need to check if the hash against all previous hashes.

Besides encrypting the database, I am thinking if an HMAC construct would help here. I assume the attacker cannot find the original message from the hash, if she couldn't find the key (where the key is not distributed, locally stored), and finding the key would be computationally infeasible if only the hash table is leaked. Is this correct? Is there a better solution?

Answer 1

First of all, even the entropy is 50-bit, it is not easy to list all possible string to execute an attack on the data set.

Using hash function can hide the data itself due to pre-image resistance, however, the same data can have the same hash since the hash functions are deterministic. Therefore, it can reveal information, especially there is also side frequency information about the data. This is a modern frequency attack^[*] and also applies the ECB block cipher mode ^[‡] of operation. Also, collisions in hash functions are inevitable due to the pigeonhole principle, to reduce the birthday attack probability use SHA3-512 so that the probability will be so small $\mathcal{O}(2^{256})$ for finding a collision with %50 probability. Of course in the adversaries advantage, 50% is too big. This is not a problem for 512-bit hash output, however, one must consider it in the other cases.

In the case that you have only 50-bit space (not 50-bit entropy), it is quite possible to build a rainbow table to attack your hash values, i.e. finding pre-images. If you consider that the bitcoin miner calculates $2^{67}$ double SHA-256 hash values in a second, then 50-bit space is quite accessible. The mitigation against the rainbow table attack (The rainbow tables are dead) is using salt, however, that you want to avoid.

You should use HMAC-SHA3 so that you will have a keyed hash that also provides unforgeability. Since HMAC requires a key, the attackers cannot find the original message or forge a new one, that we expect computationally infeasible. The rainbow table doesn't apply since the attackers don't know the key.

However, even with HMAC, frequency attack condition still applies if the same data occurs multiple times that can leak information. Meaningful possible mitigation is using salt that prevents you from directly comparing the values, or in another term separating the domains of the user.

In short, yes use HMAC-SHA3 or HMAC-Blake2.

update per comment:

Can I assume the data be secure if the key is not leaked?

HMAC is not encryption, it is a keyed hash function for message authentication. The real security issue for message authentication is unforgeability. No, the attackers cannot find. Even if, they are able to find out out one to forge, it doesn't mean that they found your message, actually they need to find another one to forge because there is already one.

---

^{[*] Read from this question How can frequency analysis be applied to modern ciphers? or the below articles.}

• ^{Inference Attacks on Property-Preserving Encrypted Databases, by Naveed et. al. Applied frequency attack on electronic medical records.}
• ^{On the Difficulty of Securing Web Applications using CryptDB, by Akın and Sunar, example how to infer the data form Hospital records.}

^{[‡] One might not even call it a block cipher mode of operation.}