Can I query on row-encrypted data in my database?

Question

Please let me know if any of my assumptions are incorrect.

Say I had a database, where all of the rows of a database column is encrypted at the application level using a single passphrase, "SECRET", using password based key derivation:

Both the random salt and IV ensure that encrypting the same data for two different rows will produce different encrypted values. However, if an attacker has read access to my database and is able to brute-force the encryption of a single row, they would then know my "SECRET" passphrase and could decrypt all of the encrypted rows.

Does this mean that the main benefit in using a random salt and IV for each row is that it hides the frequency of values of my encrypted data? For example, the downside to not using a random salt and IV would be that an attacker could look at my database and see "50 rows have value X, 49 rows have value Y, and 1 row has value Z" but would not know what X, Y, and Z actually are unless they could also crack the encryption? Are there more reasons to use a random salt/IV per row?

Say I needed to query my database for the values that are encrypted. Does using a random salt and IV make the query "Give me the rows that have value N" impossible? How can I protect my data with encryption and still be able to query on it, and what kinds of common threats would I then be vulnerable to?

Answer 1

First off, it isn't just frequency you are protecting. If the attacker cracked value X in your example, he now knows all 50 rows. Let's say the rows are users, and the encrypted value is a password. Attacker has now just popped all 50 users at once. That's more valuable than just knowing 50 entries were the same.

Random salt and IV per row doesn't make your query impossible, per se, but does make it really difficult without doing a lot of other gyrations. Look up the term "homomorphic encryption" which offers a number of ways to perform some searches over encrypted data. In practice, this isn't really scalable, or done in production, but it isn't impossible.

https://en.wikipedia.org/wiki/Homomorphic_encryption

"How much security" to sacrifice for functionality, is really a question only you can answer. What is your threat model? What's the value of the data being protected? Security has to be in service of your business goals, not an end unto itself. It has a cost which must be less than the value it brings. If the attacker gets control of your search function, they get all your data any way.

In practice, if your data can fit in memory, your best bet may be to decrypt the data, search in memory over the plain text, and leave the data encrypted on disk. If you can't, you may have to leak partial information by breaking the stored data up into searchable-sized subchunks.

You don't want to give up the masking nature of the same plain text encrypting to different cipher texts if your protected information is something like passwords, or credit card numbers. Anything an attacker can run a forward encryption on can be used for a known plaintext attack.

Example: Baddie (with read access to your database - but not the secret) signs up for your service as a legit user, and provides "password" as her password. She then pops the database, finds her own record, and now knows all the other users who also picked "password." Very bad.

Answer 2

Yes, the main purpose of using a IV/salt is to ensure that the same input to an encryption/hash function does not yield the same output. If you do not use a random IV/salt, the same encrypted/hashed value will show up the same way in your database.

Querying encrypted data is not impossible, just very, very slow. If you need to use the encrypted field in a where, join, or an order by clause, you will have to use a function to read the IV/salt and then decrypt the value on a row by row basis.