title: Full text search on encrypted data
body: <p>Suppose I have a server storing encrypted text (end-to-end: server never sees plain text).</p>
  
  <p>I want to be able to do full text search on that text.<br />
  I know this is tricky, but my idea is to use the traditional full text design ("list" and "match" tables where words are stored and matched with ids from the content table). When users submit the encrypted text, they also send a salted MD5 of the words and respective matches. The salt used is unique for each user and is recovered from their password.<br/>
  (in short: the only difference is that the "list" table will contain hashed words)</p>
  
  <p>Now, how <em>vulnerable</em> would this system be?<br>
  Note that I said "how vulnerable" instead of "how safe", because I acknowledge that it can't be totally safe.<br>
  I DO understand the tradeoff between features (full text search) and security (disclosing some information from the word index). For example, I understand that an attacker able to get the list and match tables could get information about the original, encrypted text and <em>possibly</em> be able to decipher some words with statistical analysis (however, being the salt unique for each user, this would need to be repeated for each user).</p>
  
  <p>How serious would this threat be? And would there be any other serious threats?</p>
  
  <p>DISCLAIMER<br>
  What I'm trying to build (and with the help of a cryptographer for actual implementation; right now I'm just trying to understand wether this will be possible) is a consumer-grade product which will deal with confidential yet not totally secret data.<br>
  My goal is just to provide something <em>safe enough</em>, so that it would be easier for an attacker to try stealing users' passwords (e.g. breaching into clients - they're consumers, eventually) rather than spending a huge amount of time and computing power trying to brute force the index or run complicated statistical analysis.</p>
  
  <h2>Comments in response to @Matthew</h2>
  
  <p>(may be relevant for anyone else answering)</p>
  
  <ol>
  <li><p>As you noted, other solutions are not viable. Storing all the data inside the client means that users cannot access their data from other clients. Server-side encryption would work, but then we won't be able to give users the added security of client-side encryption.<br>The only "true alternative" is just to not implement search: while this is not a required feature, it's very important to me/us.</p></li>
  <li><p>The salt will be protected in the exactly same way as the users' decryption key (the one used to decrypt stored texts). Thus, if someone was able to capture the salt, he or she would likely be able to capture also the key, creating a much bigger issue.<br>To be precise, the key and the salt will be stored encrypted on the server. They will be decrypted by the client locally with the user's password and kept in memory; the server never sees the decrypted key and salt. Users can change passwords, then, and they just need to re-encrypt the key and the salt, and not all stored texts. This is a pretty standard approach in the industry, to my knowledge.</p></li>
  <li><p>Actually, the design of the database will be as follow (reporting relevant entries only). This design is like you proposed in your comment. It disallows proximity searches (not very relevant to us) and makes frequency less accurate.</p>
  
  <ul>
  <li>Table <code>content</code>, containing all encrypted texts. Columns are <code>content.id</code> and <code>content.text</code>.</li>
  <li>Table <code>words</code>, containing the list of all hashes. Columns are <code>words.id</code> and <code>words.hash</code>.</li>
  <li>Table <code>match</code>, that matches texts with hashes/words (in a one-to-many relationship). Columns are <code>match.content_id</code> and <code>match.word_id</code>.</li>
  </ul></li>
  <li><p>We would have to implement features like removing stopwords etc. Sure. That is not a big issue (will, of course, be done on the client). Eventually, those lists have always been of limited utility for international (i.e. non English-speaking) users.<br />
  We expect the lookup/insert ratio to be pretty high (i.e. many lookups, but rare inserts and mostly in bulk).</p></li>
  <li><p>Decrypting the whole hash database is certainly possible, but requires a brute force attack.<br/>
  Suppose the salt is kept safe (as per point 2 above). If the salt is long enough (you cited 32 bits... but why not 320? - just an example) that would take A LOT of time.</p></li>
  </ol>
  
  <p>To conclude... You confirmed my doubts about the possible risk of frequency analysis. However, I feel like this risk is <em>not so high</em>. Can you confirm that?<br/>
  Indeed, first of all the salt would be unique per each user. This means that one user must be attacked at time.<br />
  Second, by reporting words only once per text (no matter how many times they appear), frequency analysis becomes less reliable.<br />
  Third... Frequency analysis on hashed words doesn't sound as something as good as frequency analysis on a Caesar-shift, for example. There are 250,000 words in English alone (and, again, not all our users will be English-speaking), and even if some words are more common than others, I believe it'd be hard to do this attack anyway.</p>
  
  <p>PS: The data we'll be storing is messages, like instant messages. These are short, contain a lot of abbreviations, slang, etc. And every person has a different style in writing texts, further reducing the risk (in my opinion) of frequency attacks.</p>