I’m working on PCI DSS (Payment Card Industry Data Security Standards) compliance for my company and one of the bigger hurdles we’re looking at is cryptographic key rotation. Our biggest concern is rotating keys for data stored in a DB. It seems we have two solutions and one theoretical option available:
1) 3rd party vendor
There are several companies offering appliances that are essentially crypto proxies which act as a middle man between data and logic.
2) Home brew
We’ve considered storing a key version number next to the encrypted column in the database. When one key is to be disused, a new one is generated and every value stored with the old key revision number is decrypted and re-encrypted with the new key. Meanwhile, all of the data is still accessible as the old key is not invalidated until all rows using that ID have been updated.
3) Theoretical crypto magic
I’m no cryptography expert, but it seems that there should be some means of generating several symmetric keys that result in the same encrypted data. Those keys could then be split into a shared/private pair where the system requesting the data only knows the shared portion; the private portion is a secret known only to the machine performing the encryption. The private key can be invalidated on demand and a new pair generated. No machine need ever store the complete key.
I don’t know if this last scenario is possible. If it’s not out there yet, this may be an interesting market for such a scheme. If there is a workable solution, this may be the ideal solution.
Are there other solutions I’ve overlooked? If you’ve implemented key rotation on DB data, what method did you use?