# Hash function for a small, enumerable set of elements

Suppose you have a set of elements, that is relatively small (e.g. 100M) and its elements can be easily enumerated. For example phone numbers, that have a maximum fixed length and they are composed of only digits.

I would like to find a way for parties involved in an open communication to reference to elements without mentioning them in cleartext, so that only who "knows" a given element can understand that a message is referring to it.

For example, if elements would be arbitrary large files, parties may identify them by MD5 or SHA1 and communicate mentioning the hashes. Only the party that has the same file may understand that a hash actually refers to that file. This is based on the difficulty to invert the hashing function and to the fact that the set arbitrarly large files is almost infinite.

This mechanism however doesn't seem to work well when the set of the elements is small and enumerable.

QUESTION: do you envision another pattern the parties can implement to openly communicate and reference to the shared elements, without revealing their value?

• Re: but the salt would then supposed to be shared among the users. The reason to use a salt when hashing data (like, for example, passwords) is to counter things like rainbow tables. Depending on the individual scenario, a salt doesn’t have to be secret – it can be public (since a known salt doesn’t help pre-calculating the other hashes which use different salts). – e-sushi Apr 17 '18 at 13:10
• "I'd like to build a solution where phone numbers are publicly shared as sort of user identifiers."; might I ask what the goal is? Why aren't you using (say) completely random user identifiers? Is one of the requirements "if you know somebody's phone number, you can deduce their identifier?" – poncho Apr 17 '18 at 13:12
• Can you clarify why you want to protect those phone numbers when they are publicly shared? What’s your goal? Publicly shared data can hardly be secret. People can/will share an ID which maps to a phone number and everyone having an ID can lookup its phone number. You can’t prevent that. (It’s like trying this by encrypting each phone number. Users would need access to the key to decrypt it so that they can actually lookup the phone number. Once the key is known, it can be shared – voiding protection efforts.) You can make ID “guessing” hard by choose large, random IDs, but that’s about it. – e-sushi Apr 17 '18 at 13:19
• Hard key derivation function? That's used in the case of passwords as there are only a "few" passwords in the real world relative to cryptographic keys. – Paul Uszak Apr 17 '18 at 13:21
• @PaulUszak Assuming your hard means “memory hard” – What would you gain from using things like Argon2? The DB would be an ID-to-PhoneNr lookup thing, where IDs only have to be created/calculated once upon creation of a new PhoneNr entry. So, you’ld only be making things hard on the creation side of things (server or user desktop when adding new PhoneNrs) – it doesn’t gain you anything when trying to protect against potential “attackers” compared to using a decently long (meaning bit count) output of a HMAC, a TRNG, or a CSPRNG. (I’ld probably choose the later as it’s the most convenient.) – e-sushi Apr 17 '18 at 13:44

## 1 Answer

To the best of my understanding, you're trying to make phone->ID an irreversible transformation. For long inputs, hashing would suffice, but there are so few possible inputs (phones) that enumeration is feasible and even a slow PBKDF won't make mapping prohibitively difficult.

Strong security is impossible in this scenario. The best you can do is slow down the data gathering process. To do that, you have to be the only one able to perform the transformation; that requires keeping a secret. It's not a salt then, but a key. The transformation can be hash(phone+key) or just encryption of the phone with the key - if the key is leaked, the security is broken either way.

Preferably, I'd suggest that you consider alternative approaches. If it's a way to find "friends", do you have to reveal the ID right away? For instance, when one enters a phone number, you only send a friend request to that number's corresponding ID if it exists, without confirming whether it does. Only upon request confirmation do you reveal the ID. Can be combined with a friends-of-friends system to limit random requests.

Don't count on this for much. But, combined with limits on accounts and friend requests, and some monitoring for suspicious activity, it could make mapping the users take more effort than it's worth. If and only if that mapping actually isn't worth much.