Secure method of encrypting data within a database

Question

I'm designing a program which makes queries to a database stored locally which could potentially contain a lot of sensitive information. As such the information must be kept secure as possible from any possible attack. I plan on doing this by encrypting the data by AES-256 in CBC mode. The encryption / decryption key will be kept secure.

My question is, using this scheme, how should the database be encrypted to ensure the data is kept secure against attacks? Originally I planned on encrypting the database cell by cell (with each row having 10 or so columns) and storing a unique, randomly generated IV for each row.

However, to my understanding of the generated stream this could cause problems as I would be using the same key + IV combination to encrypt / decrypt all the cells of this row. This would allow an attacker to potentially compute the XOR of two cells and reveal enough information where they could decrypt the entire row (two-time pad). I know this is more of a problem in CTR mode but I have read that it could also be a problem in CBC if two of the cells began with the same sequence of bytes. Please correct me if I misunderstand the concept of this type of attack as I am still a little unsure of its exact mechanism.

Encrypting the entire database itself is not very pretty and obviously will cause performance issues if the database is large enough. Therefore, the only other method I could think of is having EACH CELL have a unique, random IV which on the surface seems like a lot of extra data to have to store but I will go this route if need be.

Just as a side note; this program isn't being implemented anywhere in which security will be an issue. It is more of a side project for myself to learn the intricacies of cryptography and ways of defending against attacks. Thank you for all your help in advance!

Answer 1

Using the same key and IV for different, independently encrypted cells is a bad idea, regardless of which encryption algorithm you use. It would allow attackers to find either XORs of cells (with CTR) or at least equality of prefixes (with CBC).

If you are going to use authenticated encryption, you need to choose whether the MAC applies to each cell independently (which adds data anyway) or the row as a whole.

• If you choose the row as a whole, you might want to encrypt the whole row as one, too, since you'll need to read all of it anyway. But if the MAC verification is much faster than decryption, you might still want per-cell encryption with a row-wide MAC.

• If you choose per-cell MACs, you are already adding significant data, so you might be able to get away with a per-cell IV too. Or you might be even more determined to avoid adding any extra data, depends on your requirements.

If you end up wanting to do per-cell encryption, but can't have per-cell IVs, CTR is probably your best bet. With CTR the IVs don't need to be random, just unique, so you can calculate the per-cell IV as an offset from the row IV/nonce. Just make sure your offset algorithm will always result in a unique input to each CTR block. E.g. if cells can be at most 256 blocks long, you could use the rightmost byte within the cell, the next one for a cell index and the rest for the row nonce.

CBC is also an option, if you can derive a per-cell IV from the row IV in an unpredictable way. E.g. using $HMAC(k, r || i)$, where $r$ is the row IV and $i$ the row index. That's slower, though. (You could also use the block cipher to derive it.)

Regardless, you should also make sure that the key and IV will differ when a cell is overwritten. With a per-row IV that means the whole row needs to be rewritten with a new IV.

All in all, it's probably simpler to either just have the whole row encrypted and authenticated as a whole or have each cell with their own IV and MAC. Those options allow you to just use an authenticated encryption mode, too.