1
$\begingroup$

Suppose I have a server and a client. The client has a list of arbitrary strings and the server is supposed to filter this list using white and black lists kept on the server side. It would be nice not to share the list of the strings to the server and the white/black lists to the client. For example, a list of open applications at the client side is sensitive data, and the white/black lists are not supposed to be exposed from the server to the outer world as well. I'm wondering whether it's possible to check the client strings against the white/black lists keeping them private at all parties. The only way I can see now is:

  1. Client: split the list of strings to a list of split-by-whitespaces strings list and hash each element.
  2. Server: do the same for the white and black lists.
  3. Server: compare the client and the server hashes.

This solution has a lot of downsides. Is it possible to re-implement it in other way somehow? Or, is the idea feasible at all? Thank you.

$\endgroup$
0
$\begingroup$

I see two problems;

  • The number of keywords is very small and a dictionary attack is possible from the server.

    for i in English_Dictionary
    if Hash(i) == target_hash
    return success

    Also, one can use Rainbow tables, too. To overcome these, you will need to add salt to your plaintext to prevent any dictionary or rainbow attacks from the server side.

    There are more advanced methods for protection, as;

    • The search on encrypted data which is started with the Song et. al's idea.
    • There is another method, which may be too slow, use FHE techniques. You can totally blind the server.
    • If the client asking whether this string is black or white, you can also use Private Information Retrieval (PIR) techniques. There is an FHE PIR implementation.
  • Also, the frequency of the hit may leak information 1,2. The frequency attack really depends on the application. The method listed above, not the salt, can overcome the frequency attack, too.

$\endgroup$
  • $\begingroup$ Hi, thank you for the answer. I've also heard about fuzzy hashing (SSDEEP as an implementation). Is it another way to go to? $\endgroup$ – lsh Oct 4 '18 at 11:13
  • $\begingroup$ It is designed for spam detection. If messages are very similar, it is expected to have the same or very close hashes. This is different from Cryptography. You will still need a salt againts the dictionary attacks. $\endgroup$ – kelalaka Oct 4 '18 at 11:21
  • $\begingroup$ So there is no way of generating some values (digest?; that I was confused with fuzzy hashing with) of out strings and compare those values for similarities, in principle? $\endgroup$ – lsh Oct 4 '18 at 11:32
  • $\begingroup$ With cryptographic hashes you can perform. I told you about possible attacks. Please read rainbow tables. Nilsimsa Hash ( Fuzzy Hash) doesn't change the result. $\endgroup$ – kelalaka Oct 4 '18 at 11:43
  • $\begingroup$ Yeah, I'm aware of what dictionary attacks, salt and rainbows are, but I still feel very stupid trying to understand the methods like FHE. They are totally out of my understanding, but I find your answer laconic and really helpful to me. I wish I could upvote, but I can only accept your answer. Thank you! $\endgroup$ – lsh Oct 4 '18 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.