Using hashed trigrams to search over encrypted data

Question

For practice, I write let's call it a notebook app that stores users' notes in AES-encrypted form. For encryption, I use a password-based intermediate key technique as described here. Actually, the exact encryption method doesn't matter here, just so you know that only the client has the ability to decrypt the notes.

I want to implement a basic search algorithm that would let users search over their notes. Obviously, you can't just encrypt the search phrase and search it over the database or something like that, so here's an idea:

When a user creates or updates a note, the client-side algorithm creates a list of its trigrams, filters duplicates, then hashes each one of them, and then passes it to the server where it's stored alongside the encrypted note text in the database. When hashing trigrams, the user's personal salt has to be used.

When searching, the same thing applies to the search phrase and the database tries to search notes by given hashed trigrams.

So I have a couple of questions about this idea:

• Would it be secure enough?
• Would it decrease security if the hashes of trigrams get truncated to save some space? To handle collisions, the decrypted text could be checked on the client to verify it does have matches.
• What would be more efficient?
  • To store trigrams of a note as string divided by spaces in a separate column, then search them with LIKE or REGEXP statement
  • Or to store them in a separate table with one row per trigram with a foreign key, and search over them with = operator

Edit after some comments:

To prevent brute-force, the encryption key (or even a hashed version of it) could be used as the salt for hashing trigrams. I suppose it can work because the key can only be known by client. Is it a good way to deal with it, or there are drawbacks of this approach I fail to see?

As I've been told that using the same string as a salt and as a key could be a bad idea, there's an alternative way: we generate this "trigram salt" when the user signs up, encrypt it with the encryption key and store it in the database, then use its decrypted form as mentioned above.

Answer 1

Hashing 3-character strings is useless, because the hash can be trivially broken with brute force (i. e. trying out all possible combinations). So your approach would effectively reveal the trigrams of the plaintext, giving an attacker the chance to systematically approximate the content.

I see two options:

• Use a hash-based message authentication code (HMAC) for the trigrams with the user's key as the HMAC key. This way, only the client can calculate HMACs from plaintext trigrams, not an attacker. When a new note is created, the client tokenizes the note, calculates the trigram HMACs and sends the HMACs to the server, so that they can be stored in the database. When a note should be searched, the client calculates the HMACs from the search string and passes them to the server for a full text search in the database. Note that while the HMACs don't reveal the trigrams themselves, this scheme still leaks the frequencies of the trigrams. An attacker could try to correlate the HMACs with common trigrams of the language used in the notes (e. g. English) and find out what the notes likely contains.
• Tokenize the text and then encrypt the entire collection of tokens with the user's key. Of course that means the full text has to be performed client-side after the user has provided the password.

Answer 2

As others have mentioned, the brute force is much too easy on this scheme.

An option that was not previously mentioned is symmetric searchable encryption. These schemes are also not perfect but likely better than hashed trigrams.

Answer 3

Attacks on the described scheme

Besides the problem with frequency of trigrams mentioned by "Ja1024", the described scheme has two further problems. It is vulnerable to a Known-plaintext attack and to a Chosen-plaintext attack.

To make search possible, you have to encode the same trigram always in the same way. Otherwise the same part contained in different document will be not found.

Known-plaintext attack: Without having any information, each encoded trigram can correspond to one of 17576 (=262626, in case only 26 lower case English letter used) plain trigrams. But if the attacker knows the plain text of one of the documents, then the attacker will reduce the number of possible pre-images for each trigram to 50 or 100 instead of 17576.

Chosen-plaintext attack: The attacker creates a document and several copies with small modifications, e.g. only single letter changed. Then the attacker cause the user to upload these document to your server. Then the attacker compares the sets of trigrams. The sets of encoded trigrams on the server will be almost identical and will have a few differences only. The attacker will know then, what encoded trigrams correspond to the modified document element. Thus, the attacker will know the plain text for these encoded trigrams. When repeated, more and more trigrams can be restored.

If the Chosen-plaintext attack attack can be done sufficiently many times, then plain text can be restored for every encoded trigram.

Even if Chosen-plaintext attack can be done only a limited number of times, it can still essentially simplify the frequency analysis. Frequency analysis deals with probabilities. Often there are multiple candidates that have very close frequency and the attacker has to try multiple candidates for the same encoded value. This leads to an exponentially growing number of combinations to test. But the two attacks described above can essentially simplify frequency analysis.

It is not full text search

Suppose you found a solution to prevent restoring of plain data. There is one more point to consider. Please pay attention that the described scheme is not a full text search and that's why cannot be as efficient. For instance, full text search allows to consider different forms of the same word, allows to find synonyms, e.g. if user is searching for a "car", also "vehicle" and "truck" may be found. Or if user is searching for "fruit", also "fruits", also typos like "friut" and "friuts", also synonyms like "apples" will be found. None of this will work in your case.

Answer 4

If you really need server-side ngram search on encrypted data, then yes, this hashed-trigram approach is to be among the most practical options. However, it is easy to leak information like this.

A critical part of the security of this scheme is that the ngram hashes are "salted" per user, i.e. are calculated using a keyed hash or HMAC function. Thus, two users with the same document but different keys will get a different hashed ngram set. Truncating the hashes does not reduce security in any way, it might even help by making hashes less distinguishable. However, this will reduce search performance a bit, by making false positive hits more likely.

There is however the problem that the hashed ngrams disclose a frequency distribution of ngrams in the document. Some ngrams are very frequent in English language, some less so. By comparing the hashed ngram distribution in your database index with the expected distribution, it might be possible to probabilistically reconstruct some messages. This becomes even more important when the attacker can provide a document that you store with this encrypted method. Then they could correlate the known ngrams with the entries in your database index, and use that as their Rosetta stone for decoding parts of the document contents. Mentallurg's answer discusses these problems in more detail.

Such attacks can be made more difficult by adding a large number of random hashes to the index. This will reduce search performance (depending on how much you truncate the hashes), but it can increase privacy in a manner similar to k-anonymity models.

To reduce information leakage, using fixed-size bloom filters might be preferable. A bloom filter is a bit vector that represents a set of values. Adding a value to the set involves hashing the data with multiple different hash functions (or a keyed hash functions with multiple keys), using the hashes as indices into the bit vector, and setting those bits. To query whether an entry exists in the set, you check whether the bits at these indices are set. The size of the bit vector, the number of hash functions, and the number of entries affect the false positive rate. You can additionally set random bits, which will increase the false positive rate. If all documents are indexed with a bit vector of same size, and have the same percentage of bits set, then it would become more difficult for an attacker to extract useful information them. This can be made even harder if the hash functions don't map entries to a single set of indices, but to multiple potential sets, and select one of them at random (at the cost of making querying more complicated, because you'd have to check all potential positions).

Information leakage can also occur during querying. In your context, a query consists of repeated questions “in which documents does the ngram abc occur?”. Under the keywords “private information retrieval”, “oblivious transfer”, or “private set intersection” you'll find lots of existing solutions, some of them cryptographically safe. A non-cryptographic method would involve not just sending your actual queries, but also sending plausible alternative queries. When using truncated hashed identifiers, you can generate such queries as random numbers. But since this will lead to additional data transfer and to false positives, this will likely reduce search performance. It is also possible that this noise is not sufficient to mask the data distributions of the true queries – ngram hashes or bloom filter indices that occur in multiple queries are more likely to be real.