PCI compliance requires annual rotation of keys. The definition of "rotation of keys" that I keep coming across is decrypting your data, then re-encrypting with a new key. Really? Everyone out there is decrypting / encrypting all their encrypted data every year?
Currently, I've got 16 databases across 3 servers, with multiple tables in each database – and this will just continue to grow. Doing this manually introduces a huge opportunity for mistake, rendering my data unreadable. Yes, I could write something to do this…but is this really what everyone is doing?
So the question is are you handling this manually or can you recommend an affordable (subjective, I know) 3rd party tool?
I've seen some suggestions out there about "changing" the keys higher up in the hierarchy. We use the oft recommended hierarchy of Database Master Key encrypting a Certificate, which encrypts a Symmetric Key, which encrypts the data.
First, this doesn't seem to meet the definition of "rotating the keys". Second, even if I change the DMK or the Cert, this doesn't prevent the data from being decrypted with the same Symmetric Key that presumably bad guy has stolen / cracked.
Best Answer
Your definition of "rotating keys" is correct. You need to decrypt the data with the "old" key and re-encrypt it with the "new" key. There are plenty of shops that do this on an annual basis, and yes - it's a lot of work and best done by an automated program (you can probably write your own tool - I'm not aware of any third-party ones but I'm sure they exist).
<Rant>
The interpretation of the PCI-DSS 2.0 requirement 3.6.4 "Cryptographic key changes for keys that have reached the end of their cryptoperiod (for example, after a defined period of time has passed …" as "You have to rotate keys annually or the world will end" is shortsighted, and in my/my auditor's opinions incorrect: If you are using a sufficiently strong algorithm (e.g. AES-256) and have no known breaches of your key rotating your keys doesn't provide you substantially better security - in fact it creates a new exposure (the old key needs to be made available to a program for as long as it takes to decrypt/re-encrypt your data - Even if the machine doing that work is secure it still involves putting the key in more than one place).
Note that if you want to make this argument successfully you need two things: An auditor that has a basic understanding of cryptography, and a defensible policy that flies in the face of NIST publication 800-57 (specifically the "recommended cryptoperiods" table). Our policy for example requires AES-256 (which is free from practical attacks, and would take forever to brute-force) and forces a key rotation when someone with direct access to the keys is terminated (key sysadmin staff, certain C-level officers).
</Rant>