SQL Server Column Level Encryption - Rotating Keys

We are thinking about using SQL Server Column (cell) Level Encryption for sensitive data. There should be no problem when we initially encryption the column, but we have requirements that every year the Encryption Key needs to change. It seems that this requirement may be problem.

Assumption: The table that includes the column that has sensitive data will have 500 million records.

Below are the steps we have thought about implementing. During the encryption/decryption process is the data online, and also how long would this process take?

• Initially encrypt the column
• New Year
• Decrypt the column
• Encrypt the column with new key.

Question : When the column is being decrypted/encrypted is the data online (available to be query)? Does SQL Server provide feature that allows for key changes while the data is online?

BarDev

Re-encrypting the data-at-rest is going to be prohibitive. 500M records to update will generate tremendous log, a lot of data IO, will last hours if not days, overall will be quite disruptive. Not to mention that an operational error might leave the entire database perfectly encrypted (ie. w/o a key to decrypt it).

What I would recommend is to rotate the keys higher on the key hierarchy:

• Use a symmetric key to encrypt the data.
• Change the symmetric key periodically, eg. once a week generate a new one, encrypt new data with the new one but don't change old data
• encrypt the symmetric keys with a certificate
• use DECRYPTBYKEYAUTOCERT to decrypt the data, which will handle picking the right symmetric key automatically
• when required, rotate the certificate that encrypts the symmetric keys. Symmetric key support multiple certificate encryption, so it is perfectly feasible to add a new certificate, add encryption by the new certificate to all symmetric keys, then drop old certificate

Similar schemes to this are often deployed by large companies. Re-encrypting all the data is seldom done, because is so prohibitive. Using multiple symmetric keys and generating new ones every so often will reduce the amount of possible privacy loss if a symmetric key gets compromised. Rotating the certificate used to decrypt the symmetric keys gives the desired mitigation of certificate compromise as a compromised certificate will not be able to access data after the rotation, even though the data is still encrypted with the same old symmetric keys.

It is true that I can envision an attack on which if I have access to the certificate I can extract all the symmetric key material, then when the certificate rotates, I can in theory use the saved key material to decrypt the data (using means other than SQL Server). But this is no different that saying that 'if I have access to a compromised certificate before is rotated, I can decrypt all the data and save the decrypted data', and this puts the attack in a new light, since no amount of after the fact key rotation will recuperate data that is already lost to the attacker.

You can certainly write an application to do the decryption/encryption (SELECT the data out, decrypt it, re-encrypt it with the new key and UPDATE it back in -- the sensitive data will never be stored unencrypted in this way), however you are creating a huge amount of overhead for an annual key rotation which will only get larger as your DB grows. There is also the problem of having to maintain two keys for as long as it takes to do the re-encryption dance (maybe an hour now, maybe a few days next year depending on your growth rate and encryption complexity...)

You may want to assess the business/security logic behind the annual change requirement and see if you can get equivalent security by implementing sane controls on the decryption keys and a requirement to change keys "in the event of a compromise or suspected compromise" instead...