# Protect the original message of a hash from brute force

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?

• Salts are not used to randomize results, their main task is to separate users (and to avoid having the same result when two users use the same weak input). Of course you store the salt of each user and can then use it exactly for that user. Rainbow table attacks don't attack single users. They reduce the complexity to attack all users at once (when compared to attack each user sequentially). In general, the first idea for "bad entropy" should always be password-based key derivation, like Argon2. – tylo Dec 14 '19 at 16:44

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.

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

• But then how would you distribute the key for HMAC to the different clients? – Giulio Micheloni Dec 12 '19 at 20:58
• @GiulioMicheloni The OP did not mention about distributing the data. OP talks about storing it and comparing it. – kelalaka Dec 12 '19 at 21:01
• @Giulio Micheloni maybe with a KEM – SamG101 Dec 12 '19 at 22:35
• Indeed I don't need to distribute the key. I should have made clear if same info is provided twice, the request would be rejected, and no two same hash is stored. In this case can I assume the data be secure if the key is not leaked? – R. Wang Dec 14 '19 at 3:25
• @R.Wang updated the answer. – kelalaka Dec 14 '19 at 9:20