3

The purpose is the same as with hashing: given set of confidential documents, I want to process them and store something secure like salted hashes/bcrypt. Later, when new document is given, I want to check if it already exists in database.

Something like leak monitoring.

The problem is that if this new document is slightly modified version of the original one, system should also say that they are very similar.

Trying to solve this task, I considered first normalizing text (getting rid of punctuation, letter case, truncation, etc.) and then doing fuzzy duplicate search (near-duplicates and shingling).

Anyway, I am not sure that it is secure: for example, if shingle window is rather small, then brute force is possible. For window length = 3 and 50 letters, we get 125k combinations and few collisions. Salting wouldn't help either: attacker knows algorithm and can organize brute forcing not as 'xyz', but as 'xyzsalt' and try all 125k 'xyz' combinations. Who knows what else can be wrong with security of this aproach?

So, that is why I want to ask: are there some secure algorithms for fuzzy matching/near-duplicate searching?

Improve this question
0

1 Answer 1

Reset to default
2

Hashing is indeed the opposite of what you are looking for (any change in the input leads to a completely different hash). You could try a perceptual hash instead.

As a side note regarding your hash/salt attempts:

  • why would you need salting? It is not like someone could reconstruct the original document (similar to reconstructing a password and comparing it to a hash -> thus the need for salting).
  • why bcrypt? This is a slow algorithm (perfect for passwords) but in your case you want speed, you do not need to slow down a potential attacker (again, nobody will reconstruct a document to hash it and compare to your hashes)
Improve this answer
2
  • Shingle algorithm uses multiple hashes for string ('window': h(win), h(ind), h(ndo), h(dow)). I don't want attacker to extract any sense from document's "fingerprint", because document is confidential. So it's quite easy to do brute force for small window size.
    – Mixo123
    Commented Jun 29, 2015 at 15:15
  • @Mixo123: I guess that the "window" will be word-based (no "inter-word window", as it would be too much). In that case, if someone is interested in extracting confidential information, he would hash words of interest and look for their hashes in your DB. So the speed will not be a factor in your advantage. This said, it completely depends on the actual algorithm and its implementation.
    – WoJ
    Commented Jun 30, 2015 at 8:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .