Secure hashing when the input comes from a small space

I have a problem that I'll simplify here. Let's say I want to store a table of {person, fav color}. Only, I don't want anyone to ever be able to look up a person't favorite color; the only thing someone should be able to do is group people if their favorite color is exactly the same (not just merely similar). The obvious solution would be to not store the favorite color, but {person, hash(fav color)} using a good crypto hash(). Only, turns out that there is a very small list of color names, and anyone can easily enumerate all the colors, and compute the hash thereby reversing the hash and extracting the fav color for a person. I can stretch, but that makes computing hash() slow -- it needs to be a fast operation.

Basically, I have input x chosen from a small, easily enumerated space. I want a fast-to-compute function H that will guarantee x==y <=> H(x)==H(y) (with high probability). But knowing H(x) does not allow one to easily compute x.

I'm creating a secret key, and using H(x) as Hmac-Sha256(x, key).

Does this work? Is there a better, more accepted way of doing this?

• I don't think what you are looking for is possible, you probably need encryption for this, not hashing. Also salting a hash does not slow it down Aug 22 '18 at 23:43
• @RichieFrame I mean to say stretch, not self. Fixed. Encryption doesn't look like the right solution: I'd have to use a fixed IV for my comparison requirement; which means that I will leak information when prefixes are similar. Aug 23 '18 at 1:41
• What if I hire some people to infiltrate your color social network? One of whom has agreed to say their favorite color is red, another who will say orange, one yellow, one green, one blue, ... Aug 23 '18 at 2:26
• @MaartenBodewes, when using encryption with a fixed IV, common prefixes in the plaintext result in common prefixes in the cipher text. Aug 23 '18 at 5:13
• @FutureSecurity :) You may be taking the example too literally. As I said in the first sentence, I'm simplifying the scenario to highlight only the problem I'm looking to solve. In my case, the 'fav color' value is not under control of the user. Aug 23 '18 at 5:15

What you want is the below query is possible but the database is secure against; Frequency/Inference attacks

Select * FROM users WHERE 'fav_color' = RED


What we have; small values space for the color names as people's favorite colors. We can consider this is as an example of the small message space like gender, age, weight, scale, the illnesses they have, etc. The more the information is leaked the more to identify a target.

1. Case: Cryptographic Hash: Hash functions are considered as a candidate for a one-way function. This means that they are hard to invert. In hash terms, they need to have pre-image resistance. Keep in mind that they are deterministic in the sense that one gets the same hash value whenever the same input is hashed again.

Select * FROM users WHERE 'fav_color' = Hash(RED)

• Pre-image resistant: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage $$x'$$ such that $$h(x') = y$$ when given any $$y$$ for which a corresponding input is not known.

In a normal pre-image attack, the success of the attack requires around $$\mathcal{O}(2^n)$$ search to be successful. This can be executed random $$2^n$$ input search for the hash value. Since the input space is small, once the attacker access the database they can infer the input values very easily. If one assumes that they have all the knowledge of the system, they can prepare a hash table beforehand.

Using slow and memory hard hashing like Scrypt/Argon2id will not much against this attack. It will only make the attack time slower and very small input spaces like color will be still an easy target.

Using salt can kill the hash table/ rainbow tables, however, one cannot execute the query anymore since the same color name will have different values.

2. Case: Cryptographic Keyed Hash: Keyed hash function like HMAC and KMAC requires a key to operate and the security also relies on the key. They are also deterministic.

Select * FROM users WHERE 'fav_color' = HMAC-SHA256(RED)


In this case, the attacker has no chance of executing a search as in unkeyed hash function since the key prevents it. This is not preventing them to infer data from the tables. The frequency attack is possible as in the case of the CryptDB.

3. Case Encryption: We can remove the case of stream cipher since the no padding option will leak information about the data as $$\color{Blue}{\textbf{Blue}}$$ will be longer than $$\color{Red}{\textbf{Red}}$$. We may assume that with proper padding all the colors have the same plaintext size that result in the same block size.

Select * FROM users WHERE 'fav_color' = ENC(RED)


One can use ECB mode that enables equal queries like in CryptDB since it is not Ind-CPA secure. In this case, the attack same as in the HMAC case, look for the frequency.

Using Ind-CPA secure ciphers modes like CBC and CTR will hide the frequencies, however, that will remove the equality query.

4. Other options These are slow, however, can hide the frequency on the data at rest since these are using randomized encryptions.

• Once can use PIR (private information retrieval) schemes to access the data with the required fav_color. This may need a special design to access all.
• FHE (fully homomorphic encryption) base database; we will see.