4

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.

3
  • 1
    I'm tempted to move this to Cryptography.SE - let's see how it does here first, though.
    – Rory Alsop
    Apr 28, 2023 at 12:02
  • This question can be better answered at Crypto SE. I suggest to move the question there.
    – mentallurg
    Apr 28, 2023 at 16:35
  • "What would be more efficient?" - an array column or the separate table would be cleaner, but whatever scheme you use, check that your dbms supports in index on it.
    – Bergi
    Apr 28, 2023 at 21:50

4 Answers 4

5

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.
8
  • What if I use the encryption key as the salt for hashing trigrams? If the salt is only known by client, the attacker won't know the initial info, so there'd be no opportuny for a brute-force, right?
    – v_slav.b
    Apr 28, 2023 at 18:17
  • 5
    This would be a home-made HMAC. It's entirely unclear how secure your specific scheme for combining a key with a hash algorithm would be, and you could run into all kinds of unexpected cryptographic issues. The benefit of a standard HMAC algorithm (e. g. the one from RFC 2104) is that is has been designed specifically as a combination of a hash algorithm and a key, and it has been extensively checked both conceptually and practically.
    – Ja1024
    Apr 28, 2023 at 19:41
  • HMAC trigrams still leave an uncomfortably large attack surface, especially if the attacker can influence the user to create certain documents Apr 28, 2023 at 21:42
  • I'm not sure an attacker can make the user calculate HMACs in the scenario described by the OP, but what the trigram HMACs potentially do allows is a frequency analysis.
    – Ja1024
    Apr 28, 2023 at 22:18
  • I think it is a way to go, thank you very much. I just didn't realize at first that the idea with the salt I proposed is almost like using HMAC as I simply didn't know how it works. I'm really sorry to bother you again, yet could you please check the last paragraph of the post (edited) and tell if the other idea I've come up with is good or bad?
    – v_slav.b
    Apr 30, 2023 at 15:30
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.

2

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.

11
  • Thanks for your response! What if I use the random offset trick as described in my comment to the Ja1024's respond? It was proposed as a way to make frequency analysis a little more difficult, and seems to be a possible way to deal with the attacks you've described as the attacker will get absolutely different sets of values everytime they submit the same or similar document. To make that work, any random offset must be a multiple of the length of the truncated version of the hash so there are no intersections
    – v_slav.b
    Apr 30, 2023 at 23:01
  • And yea, the array of hashes has to be shuffled everytime of course
    – v_slav.b
    May 1, 2023 at 0:04
  • @v_slav.b: I don't understand how random offset can help. The problem is that the same plain text trigram will always be encoded into the same value. For instance, you have no matter how complex encryption or hashing, and according to your algorithm "car" will be encoded by "81f7e62165d4..." and "can" is encoded by "95a7d9fce446...". The attacker does not know what "81f7e62165d4..." and "95a7d9fce446..." are. But it is knows that the frequency of "can" in English is approximately 15 times higher that the frequency of "car"...
    – mentallurg
    May 1, 2023 at 2:25
  • 1
    @v_slav.b: ... But when attacker sees that "95a7d9fce446..." occurs 90 times and "81f7e62165d4..." occurs 6 times, then the attacker will expect that the probability is very high that "95a7d9fce446..." means "can" and "81f7e62165d4..." means "car, and the probability is very low that it is vice versa.
    – mentallurg
    May 1, 2023 at 2:27
  • 1
    @v_slav.b: And don't focus on frequencies only. Other attacks remain still possible. For instance, chosen plaintext attack. Let say, the attacker makes user to upload a document that consists of a word "can" repeated 1000 times. Then if the encrypted result contains 16 values each repeated 62-63 times, then it would be clear that all these 16 values represent the trigram "can". I simplify it show the idea...
    – mentallurg
    May 1, 2023 at 6:49
1

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.

11
  • Thank you for your detailed response! As I've been thinking about it, I came up with another rather straightforward idea: what if I just use one salt per note and then use MySQL's SHA2 function in SELECT request? Yes, it would have to calculate hashes for every trigram over and over again as the salt will differ from note to note, and I thought it would be very slow, but as I tested it now on like 50000 rows, it keeps showing 0.00s spent on calculating. To prevent brute-force, the trigrams need to be sent to the server in hashed form too, with salt per user (HMAC). What do you think?
    – v_slav.b
    May 1, 2023 at 12:12
  • It won't save from what you've described in the last paragraph though, but I will look into what you have advised.
    – v_slav.b
    May 1, 2023 at 12:13
  • @v_slav.b You cannot use database features to calculate hashes here, since that would require access to the sensitive plaintext data. In your threat model, you want the DB to only handle encrypted data. You might have to think more carefully about which actor gets to know what. Having a separate salt/key per document also defeats the point of having a search index. At some point, it gets easier to treat the server as dumb encrypted block storage (literally just put/get/delete for arbitrary blobs), and do everything else client-side (creating and updating indices, searching the indices).
    – amon
    May 1, 2023 at 12:35
  • but the server won't be receiving plaintext. As I said, the trigrams will be arriving there in hashed form via HMAC using user's encryption key which is only available for client. So it's basically double hashing: first with encryption key, second with note's unique salt. And I don't understand why would using a column index be impossible as the values stored in the database are going to be compared as they are with double-hashed trigrams from request.
    – v_slav.b
    May 1, 2023 at 13:26
  • @v_slav.b If the ngrams are already transmitted in hashed form, what value would it have to hash them again in the DB? In this kind of end-to-end-encrypted architectures, the database is assumed to be an attacker (if not now, then maybe compromised by an attacker in the future). Or do you only want to protect data at rest? Then this could make sense, but it would be a radically different threat model concerned e.g. about someone obtaining decommissioned hard drives.
    – amon
    May 1, 2023 at 13:30

You must log in to answer this question.

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