3

I am using attr_encrypted to store many fields. Trouble is I need to be able to search some of these fields.

Take User.name.

My current database has User.e_name and User.e_name_iv. While this seems to be reasonably secure, I can't search my database for 'Joe Bloggs'.

Hashing

I then considered adding a third hashed field (User.e_name_hash) that could be used to find a field based on the hashed search term. So the 'Joe Bloggs' search is hashed, compared to all other hashed entries, and the required record is found. But to do this, I'd have to have a constant salt across all data in that field in that table (also insecure).

Impasse

Having learned that a constant salt is horribly insecure, I've run out of ideas on how best to make encrypted fields searchable. My options are:

  1. Leave these fields plaintext.
  2. Keep these fields encrypted and add a hashed field with something like a constant lengthy salt with SHA512 (the salt would be constant within all records in each database field but unique to that field).
  3. Have my database decrypt every record every time a search is needed (doable now but inefficient as volume grows).

Note that the fields I need to search through are not super high sensitive - they're not akin to medical records or classified information.

What are your recommendations?

  • Why won't row-by-row decrypt-and-check work for you? ​ ​ ​ ​ ​ ​ ​ There are exactly two possibilities I can think of: ​ ​ ​ One is that the encrypted database will be stored by an untrusted party and you don't want that party to have to send you the whole encrypted database each time. ​ The other is that row-by-row decrypt-and-check would require too much computation. ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ – user49075 Aug 7 '17 at 2:10
  • Your second option is what I said in #3. – sscirrus Aug 7 '17 at 20:21
  • It seems to me that #3 actually describes the method I asked about, and that the options I thought of are causes of #3's inefficiency. ​ Is one of them significantly more of an obstacle than the other? ​ (i.e., bandwidth vs. computation) ​ ​ ​ ​ – user49075 Aug 7 '17 at 20:59
  • I suppose it's primarily to determine what the options are and on basis a decision should be made. In most of my DB tables, the volume isn't expected to be great so a full-table-decrypt isn't infeasible. In one or two tables however, the volume is likely to get quite large so I want to know what the best alternatives are (and any accompanying info on how to decide between them). – sscirrus Aug 8 '17 at 7:49
2

Edited: see important note at the end, which was added after I posted originally and then re-read the question.

The only thing I can think of is to build an indexed table using hashes. But, this will undoubtedly weaken your security since we are exchanging full encryption that (hopefully) does not leak any information about the contents for tables of hashes, which do leak information about the contents of a user's data (knowing the number of terms indexed for a given account gives an attack a toehold for frequency analysis among other things).

Note: I am making the following assumption: you have a different iv for each user.

Prior to a database row being encrypted, you can read the rows and tokenize them into a table that will index those items. You would then hash the tokens with a salt generated form the iv. So, now, for a given user, "secretfoo" is saved in the index as c9a60f248c3a99e2b7004061d5c74e5f2240426f1f0f95eaf5843aa875e68542.

When you search, you'll need to loop through all the ivs to generate all the salts, then perform a search for the token c9a60f248c3a99e2b7004061d5c74e5f2240426f1f0f95eaf5843aa875e68542 to find the record that contains 'secretfoo'.

This would be a faster search, but there is a trade of with speed for security here. Because you have essentially saved yourself a dictionary of hashes for a given word, if the database were to be exfiltrated, it's possible (but unlikely) that the indexed information could be used to assemble the original data. At the very least, it can be used to assemble metadata about the data. That being said, it would be computationally difficult.

Lets' assume you have 100,000 users with approximately 100 rows per user for a total table size of 100,000,000 rows of data.

Decrypting all 100,000,000 million to perform a non-indexed search will take mountains of time.

Under the paradigm above, you only have to generate 100,000 hashes and search for each of those once in the index to find the records you want.Additionally, we can match whole strings (the hash) and not have to perform any substring searches.

This has the advantage of computing 100,000 hashes and performing 100,000 searches on a BTREE indexed table that gives us good results.

As Mike Ounsworth pointed out, you are still going to have to decide what's sensitive and what's not sensitve data in order to do a search; however, having all the tokens SHA256 hashed is orders of magnitude better than plaintext.

EDITED:

After making my post, I re-read your question, and realized you've saved the iv in the database, which would make the index vulnerable to exfiltration.

The only way to fix that is to store the iv in a separate database that is not exposed to the web, and which can only be accessed via an API. This is a common setup in PCI compliant applications.

When making a query, your web-facing application would have to ask the secure server for the iv from which it would generate the hash, and perform the search.

This is a more complicated implementation, but if the iv is in the database that is web-facing, and it's exfiltrated, then all they have to do is loop through the ivs to decrypt the entire index.

  • +1 Thank you for this answer - I learned a few things! To the API point, I don't have enough resources/time to create a separate API for the iv's, so that option won't work. – sscirrus Aug 4 '17 at 17:44
2

You know the answer already: 3 if you want security.
If this gets too slow, you'll need a better computer, or more than one. As simple as that.

Anyways, please don't think you can decide how sensitive what data is, because this varies greatly for different persons and situations. Real story: A person losing 20% of the yearly income because it was known that he ate vanilla icecream. You can't imagine how this can happen? Exactly, that's why: Don't decide for other people what to keep secret and what not. .

  • 1
    I'd be curious to know what your real story refers to. That must be a very interesting story indeed. – Kaël Aug 4 '17 at 11:33
  • 2
    More like a sad one. Someone with a sort of extreme allergy since birth. Very short version, (skin) wounds for no reason anywhere on the body, and eating pretty much anything containing any form of wheat, cow milk, lemon acid (worst) and/or some other stuff (=90% of common food), makes the wounds much worse. Up to the point that going out of the house and/or keeping the same clothes on for more than some hours, was impossible because the amount of bleeding (if eating wrong stuff). ... – user155462 Aug 4 '17 at 11:51
  • 3
    Got money from the health care system for easing treatment and the higher costs for special food. Wanted normal food at least on special occasions, despite the following health problems. Some idiot reported it, money stopped. – user155462 Aug 4 '17 at 11:51
  • To some extent, developers DO decide how sensitive data is based on our decisions of what to encrypt, what levels of encryption to use, and so on. Who decides whether or not a project name has to be encrypted at rest? Unless there's a regulation or policy on the matter, it's may be left to the developer's judgment. Regardless, +1 for the ice cream story. – sscirrus Aug 4 '17 at 17:39
1

Take a look at CryptDB. It encrypts the whole database and runs queries on the encrypted data without decrypting it on the DB side. You do need to change your app a bit to work with CryptDB, but they authors claim these are minor changes. It is completely language agnostic.

Here is the whitepaper describing how it works.

0

Yup, that seems like an impasse alright. If you're looking for clever crypto truck, you won't find one.

One of the properties is encryption is called ciphertext indistinguishability which says that given a ciphertext and a random string, and attacker should not be able to tell which is which. As a corollary, if you have three ciphertexts, two of which came from the same plaintext, the attacker should not be able to tell which. This is the point of using unique salts or unique IVs for each record.

The idea of being able to search ciphertext clashes at a fundamental level with ciphertext indistinguishability.

The implication here is that you can't encrypt your search keys and still keep any kind of performance. You're going to need to decide which things are sensitive and accept that those are not searchable. You may be able to design around this to some extent by sticking random IDs on everything and having more lookup tables.

  • Your point about ciphertext indistinguishability is exactly right - it's why I'm concerned about using a constant salt on a field that's fairly predictable to begin with, such as a column with limited entry options. I may end up going with #3 on the basis that these columns won't be searched too often in my estimation. – sscirrus Aug 4 '17 at 17:41
  • How does one 'design around this' by using more lookup tables? Can you please provide an example of how I might do that - keep the data encrypted but also make it effectively searchable? – sscirrus Aug 4 '17 at 17:42
  • @sscirrus I am neither a database expert, nor do I know your datamodel, nor do I know the intended result of the search, but I'm imagining another table which gives you a list of row indices related to a particular user (pad that list to uniform length and encrypt it for added indistinguishability). Definitely not a drop-in replacement for search though... – Mike Ounsworth Aug 4 '17 at 18:15
0

If you need to keep your hot data (data that is being queried) in encrypted form, then decrypt as you do search, this would slow down your database and it would also prevent you from doing some advanced search optimization because you basically will be doing full table scans every time. The other option is TDE.

  • TDE (transparent Data Encryption), most database vendors support it now. and it basically encrypted at the tablespace files, your tables are encrypted while at rest and unencrypted while they are hot. this gives you a good security posture if you want your backups to be secure and trasportable. This method scales greatly , apple is probably using it.

hope this helps. If you clarify these requirements, I can go back and edit my suggestion.

  • Is your Data access, application that used the data secure ?
  • What database vendor do you have ? Oracle , Mysql, MSSQL.
  • Is you data store one of big data s ?
  • Is you database document based ?
  • Do you have control and access to your database ?

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.