Strategies for Rotating MYSQL Encryption Keys

Question

I have a web app that connects to a MYSQL database which has some encrypted data in it. The encrypted data is encrypted using the the mysql AES_ENCRYPT function and a key.

Now, this key has been static for a while, and we're looking at methods to change the key (and ideally change the key periodically). My problem is that I have about 20 million records that are encrypted with this key. So I need to decrypt them, re-encrypt them in with a new key, and save them off again, with minimal downtime for the server.

I'm thinking, I could run 2 databases in parallel, and have a separate process copying over the data with a new key (and somehow making sure records are in sync) and once it's done, switch to the alternate database. But, this would take a really long time, and would be a pain to run anytime we want to change the key in the future. I'm also wondering if there's something clever I could do at the web app level.

I've looked for other column-level encryption methods to make key rotation easier in future key changes, and haven't seen many options. I've looked at encrypting the entire database with mysql data-at-rest encryption (and I might implement that too), but I'd like reads from root and mysql users to be encrypted as well for an extra layer of security.

Anybody have any ideas, or any experience with this kind of thing? I'm sure other people have had this same problem but haven't found anything online.

Answer 1

You could use a static seed, a key derivation function, and a counter or salt.

I'm making this suggestion because it reads as if all your records are encrypted with the same key. That way, if the key were ever to leak, it would expose all your records.

One of the more common approaches for preventing this kind of scenario is to use ephemeral keys, one for each record. That way, if the encryption key for the record is leaked, only the record is exposed. Additionally, you don't have to worry about static keys.

1. Generate a static seed once.
2. Use e.g. PBKDF2 as a key derivation function.
3. For each record, increment a counter or generate a salt, and also feed that into the KDF.
4. Use the result for en- and decrypting the record.

The table must be extended to include the counter/salt in its unencrypted form. That alone cannot be used to encrypt or decrypt the record, so is safe in plain text.

Of course, securing the static seed is exactly as hard as securing your current static password - the safety feature really is only that gaining access to one key for AES_ENCRYPT exposes only one record.

If you're worried about the seed staying static, you can use the DES_ENCRYPT function/feature for storing a few (up to 10) passwords on the database server in a file. You'd have to generate your seed via DES_ENCRYPT from a static string and one of the stored passwords for every use of AES_ENCRYPT, and store the salt and DES key number in the record.

This does enable you to rotate seeds as well - but the key numbers cannot change, or render records un-decryptable.

The upside of this would be that you would never have to store the password in the application code. Given a key_num of 5 and a randomly generated seed of deadbeef, you encrypt like this:

AES_ENCRYPT('my data',
  CONVERT(PBKDF2('SHA256', 
    DES_ENCRYPT('some static string', 5),
    'deadbeef', 1, 0, false) USING utf8)
);

---

On migration, the simplest way forward would be to implement a strategy of updating records when they're updated. Just add an empty salt and key_num field, and when they are empty use the old method. When they're set, use the method outlined above.

If you do want to re-encrypt records, that fallback would also allow you to do so bit by bit, e.g. via a slow script.