How exactly does encryption key rotation work?

Question

How exactly does encryption key rotation work? I understand it's a very good practice to continuously rotate your encryption keys for security purposes, but rotating a key would require too much work.

Case:

Let's just say I have a database storing 30GB of data, and we're using an internal key to encrypt data at rest, and I plan to rotate my keys every month.

Questions:

1. Does that mean all my data will be decrypted by the old key and re-encrypted by the new one every month?
2. The whole encryption-decryption would take a lot of time and compute resources.
3. If my DB ( or any encrypted dataset ) scales tomorrow, does that mean the same process would duplicate when my key rotates? This does not look like a scalable solution.

Other Details:

1. I've also seen AWS KMS rotates it's keys if we've selected the rotation option. How does AWS manage to rotate it's keys and all encrypted data for all the underlying services?

Presidium

How AWS does this in the backend is AWS internal secret. But its costly. Each new version, will add cost. This cost probably compensate all these compute resources AWS uses to do encryption-decryption transparently for you. – Slover

Thanks @Slover . Agreed. AWS has it's own standards, but is there a possible solution to do it for our own datasets (for our own keys) at a cheap cost? – Presidium

Generally you'd not re-cipher the entire database. You'd use multiple levels of keys using e.g. key derivation. Note that it is simple to e.g. encrypt keys using a different key. If the data remains static there is no need to re-encrypt it with a different key, but you may want to replace the key that gives you access to the data periodically (you protect against the key leaking, not so much the key being brute-forced or the data decrypted). This is also why you can change your password for HDD encryption. You only re-calculate the master key, the data key remains static. – Andino

Note that this question doesn't contain any programming, so it is much better at place at Information Security. It's a bit too solution specific for Cryptography. – Andino

Thanks @MaartenBodewes That was really useful. I'll read a little bit more about it. – Presidium

I also recommend to move this question over to security.stackexchange.com – Britannia

Answer 1

You need to familiarize yourself with Envelope Encryption. Each time you want to encrypt data in AWS, you first generate a unique data-key. You then encrypt your data with this key. This key is not the key that is rotated!

Then you take this key, and you encrypt it with a key from KMS. Now if you want to decrypt this data, you must first get the decrypted data key, and to decrypt this data key, you will need the KMS key.

Now if you want to rotate the key, you don't need to re-encrypt all the data, instead you need to decrypt the data key using your key to be rotated from KMS, and then get a new key, and re-encrypt the unencrypted data key. That way you don't need to re-encrypt all the data.

Elvera

Purpose of the key rotation is limit amout of data encrypted by a single key. If data are to be re-encrypted (even the data-keys) after the key rotation, then the system fails to fulfill the purpose of the key rotation. – Kinase

Note sure how this comment is related to my answer. Each data key is unique, but a KMS key will encrypt many data keys. Key rotation in AWS will not result in having to re-encrypt the entire data: forums.aws.amazon.com/thread.jspa?threadID=253682 – Elvera

Yes, that right. Even using the enveloped encryption that limits amout of encrypted data, the rotation is required capability for multiple industry standards (certifications). And I believe the guy in the forum has misses the point too. CMS can be used for AWS services and there you can rotate the keys. Without copy or re-encrypt. – Kinase

Interesting… so you encrypt a core key that itself never changes… I’ve been wondering about this for a while. – Curarize

Answer 2

Here are two important links that can help you understand envelop encryption and key rotation in AWS.

1. https://docs.aws.amazon.com/kms/latest/developerguide/concepts.html
2. https://docs.aws.amazon.com/kms/latest/developerguide/rotate-keys.html

I have quoted some important concepts from the above links:

Envelop encryption:

When you encrypt your data, your data is protected, but you have to protect your encryption key. One strategy is to encrypt it. Envelope encryption is the practice of encrypting plaintext data with a data key, and then encrypting the data key under another key.

Customer Master Keys

CMKs are created in AWS KMS. Symmetric CMKs and the private keys of asymmetric CMKs never leave AWS KMS unencrypted. This strategy differs from data keys. AWS KMS does not store, manage, or track your data keys. You must use them outside of AWS KMS.

Data Keys

Data keys are encryption keys that you can use to encrypt data, including large amounts of data and other data encryption keys. You can use AWS KMS customer master keys (CMKs) to generate, encrypt, and decrypt data keys. However, AWS KMS does not store, manage, or track your data keys, or perform cryptographic operations with data keys. You must use and manage data keys outside of AWS KMS.

Key rotation

When you enable automatic key rotation for a customer managed CMK, AWS KMS generates new cryptographic material for the CMK every year. AWS KMS also saves the CMK's older cryptographic material in perpetuity so it can be used to decrypt data that it encrypted. AWS KMS does not delete any rotated key material until you delete the CMK.

An important concept in Key rotation is the HSM backing key(HBK): (https://docs.aws.amazon.com/kms/latest/cryptographic-details/key-hierarchy.html)

Within the hierarchy of a specific CMK, the HBK can be thought of as a version of the CMK. When you want to rotate the CMK through AWS KMS, a new HBK is created and associated with the CMK as the active HBK for the CMK. The older HBKs are preserved and can be used to decrypt and verify previously protected data. But only the active cryptographic key can be used to protect new information.

Graz

Answer 3

Does that mean all my data will be decrypted by the old key and re-encrypted by the new one every month?

As already answered, the simple answer is no. But the previous answers miss the purpose of the key rotation

The reason behind the key rotation is limit amout of data encrypted by a single key.

How does AWS manage to rotate it's keys and all encrypted data for all the underlying services?

The basic idea (at least in KMS) is, that the KMS key is not a single key, but it is a set of keys, which the last one is the current one. You can imagine that as "key versioning". After each key rotation the current key is saved so you can still decrypt the previously encrypted ciphertext (data key - as mentioned in other answers). I believe in the KMS this whole set is hidden, but Azure KeyValt shows the whole set as key version.

 The whole encryption-decryption would take a lot of time and compute resources

No, you don't need to do anything. AWS manages the "key versions" for you. Even if you'd re-encrypt the envelope keys as suggested in another answer, then you would actually fail to fulfill the purpose of the key rotation.

The ciphertext generated by the KSM must contain some identification of the key version too, so the KMS is able to decrypt the ciphertext even after the key is rotated.

Kinase

Hi, as you said, we don't need to rotate the data our self when we enable the auto-rotate in KMS, but I wonder if we need to rotate the data key by our self? – Drusilladrusus

@Drusilladrusus not sure I understand your question. KMS generates new data key every encryption (or the data key can be cached for short time). Using KMS (or random data key) you don't need to do anything with it. – Kinase

I mean in the key rotation process, KMS rotates the master key, but didn't say anything about rotates the data key, so I wonder in that key rotation process, does KMS gonna rotate the data key as well? or do we need to do it manually? After a time of research, I found this Reddit post saying that KMS doesn't do it automatically because it's not necessary. here is the Reddit post: reddit.com/r/aws/comments/8tyieo/aws_kms_data_key_rotation – Drusilladrusus

@Drusilladrusus I feel there's misunderstanding. Purpose of the "rotation" is limiting amount of data encrypted with the same key, not to reencrypt anything. As data-key is random, it makes no sense to do anything with it. "Rotation" in KMS means creating a master key version (old versions still needs to be stored to decrypt existing ciphertext, it is just not visible outside) – Kinase

now that's much more make sense, thanks for the explaination. – Drusilladrusus

Answer 4

I was refreshing myself on AWS KMS keys recently (Mar 2024) and found that the documentation is still confusing. As others have noted, AWS uses envelope encryption which means the KMS key encrypts a data key. During standard key rotation, it's the KMS key that's rotated, not the data key. Now to clarify some things:

1. KMS key - this is like a container and contains metadata along with the key material (the bits that make up an actual encryption key). During KMS key rotation, only the key material is changed, not the actual KMS key ID. The older key material is kept for historical purposes in case it was used to encrypt something previously. KMS will figure out the correct historical key to use. Per AWS doc " AWS KMS saves all previous versions of the cryptographic material in perpetuity so you can decrypt any data encrypted with that KMS key."
2. Data key - this is the actual key used to encrypt the data and it is encrypted by the KMS key and stored as metadata within the storage area. I don't know why AWS didn't use the term data encryption key (DEK) which would make this so much clearer.
3. One thing to be clear on is that if there is a compromise of the DEK, KMS key rotation does not help. AWS doc clearly mentions "key rotation has no effect on the data that the KMS key protects. It does not rotate the data keys that the KMS key generated or re-encrypt any data protected by the KMS key, and it will not mitigate the effect of a compromised data key."
4. A few years ago, AWS used the term CMK to mean either "customer master key" or "customer managed key." Of course that did nothing to help people understand KMS clearly. Duh! They have deprecated the use of CMK as meaning "customer master key" and now use "KMS key" to mean "customer master key."

See https://docs.aws.amazon.com/kms/latest/developerguide/rotate-keys.html.

Been