How does Amazon SSE-S3 key rotation work?

Question

I'm trying to wrap my mind around Amazon's Server Side Encryption options so I can start asking S3 to encrypt my data at rest when my applications upload files.

So far the AWS-Managed Encryption Keys option sounds like what I'm looking for (Model C):

But then it says

As an additional safeguard, this key itself is encrypted with a periodically rotated master key unique to Amazon S3 that is securely stored in separate systems under AWS control.

How does this rotation work? Does this mean that every time AWS rotates their key-encrypting key, they have to re-encrypt EVERY SINGLE Data Key stored in S3???

That seems crazy to me, and I don't want to sound crazy when I try to convince my boss that this is a good idea :)

Answer 1

For each object you upload, a new encryption key is generated, and used to encrypt the object before it's stored to disk.

Having the object stored encrypted means the it's computationally infeasible for someone in possession of the raw data as stored on disk to decrypt it... but, of course, anyone in possession of that key could decrypt it, so the keys have to be stored securely, and in a relatively useless form, and that's done by encrypting them with the master key.

To compromise the stored object, you have to have the specific encryption key for that object... but even if you have it, it's useless since it's also been encrypted. To get it decrypted, or at least have it used on your behalf, you have to have the master key, or have a trust relationship with an entity that controls the master key and can use it on your behalf.

So far, all I've really done is stated the obvious, of course.

The encryption keys, themselves, are tiny, only a few tens of bytes each. When the master key is rotated, the object-specific encryption keys are decrypted with the old key, and re-encrypted with the new key. The new versions are stored, and the old versions are discarded.

Since the keys are small, this is not the massive operation that would be required if the objects themselves were decrypted and re-encrypted... but it's only the per-object encryption keys that are decrypted and re-encrypted when the master key is rotated.

Several analogies could be drawn to an apartment complex, where keys are stored in a common lockbox, where changing the lockbox lock would restrict future access to individual apartments by restricting access to the individual apartment keys by restricting access to the common lockbox. The analogy breaks down, because physical keys are easily copied, among other reasons... but it's apparent, in this illustration, that changing the lockbox lock (relatively simple operation) would be unrelated to changing the lock on one or more apartments (a much more substantial operation).

The bottom line, in this scenario, they create a new secret key to encrypt/decrypt each object you upload, then store that secret key in an encrypted form... periodically, and transparently to you, they change their stored representation of that secret key as a preventative measure.