Hierarchical Key Rotation. Should I rotate the lowest level keys?

Question

I have a hierarchical key system designed for my project. In this system a block of data is encrypted using a Data Encryption Key (DEK). This DEK is encrypted using a Key Encryption Key (KEK) which is encrypted using a Master Key (MK). The KEK is used to encrypt multiple DEKs.

Figure 1. The key hierarchy

Now, when I have to decide on the rotation mechanism, rotating KEK and MK seems straight forward, I'm a little confused whether I have to rotate the DEK as well, which would involve re-encrypting many blocks of data again.

Answer 1

NIST thinks you should.

NIST SP800-57 Part 1 "Recommendation for Key Management (Part 1 - General)" lays out definitions and recommendations for encryption keys and their management. Under §5.3.6 Cryptoperiod Recommendations for Specific Key Types it covers DEKs:

6. Symmetric data-encryption key:

a. Type Considerations: A symmetric data-encryption key is used to protect stored data, messages, or communications sessions. Based primarily on the consequences of a compromise, a data-encryption key that is used to encrypt large volumes of data over a short period of time (e.g., for link encryption) should have a relatively short originator usage period. An encryption key used to encrypt less data over time could have a longer originator-usage period. The originator-usage period of a symmetric data-encryption key applies to the use of that key for encrypting information (see Section 5.3.5).

And Table 1 with the suggested cryptoperiods says:

Key Type	(Cryptoperiod) Originator-Usage Period (OUP)	(Cryptoperiod) Recipient-Usage Period
6. Symmetric Data Encryption Keys	<= 2 years	<= OUP + 3 years

Yes, re-encryption becomes part of the lifecycle when rotating DEKs. Maintaining multiple DEKs allows you to break up re-encryption and not be forced to re-encrypt the entire data set at one time.

Answer 2

It depends entirely on your threat model.

Ultimately, your DEK is the critical one - if someone has your data and your DEK then it is game over. Moreover, if someone has access to your data and the DEK then rotating all the other keys won't matter.

Still, only you can decide whether or not it is worth the effort to rotate the DEK. Hence the question: what is your threat model? What threats are you trying to mitigate in the first place by introducing 3 layers of keys? Presumably your question can be answered by simply considering why you did this in the first place.

What this doesn't help with

To get started, it helps to keep in mind the threats which this doesn't protects against. None of this helps if an attacker gains access to your running application. Your application will have access to the data and the DEK, so you're hosed no matter how many layers of keys you use.

What this may help with

Probably the main affect that rotating the DEK has is to protect against lost backups/old data (which happens more than you would think). If someone finds an old backup, can also find the current DEK, and the DEK was never rotated, then game over.

If someone finds an old backup but the DEK has been rotated and the old one thrown away, then the data in the backup is effectively useless and unrecoverable (which in this case is a good thing). This may be especially relevant to protect against an inside threat. Imagine a developer who made a copy of some data as a normal part of their work (perhaps they were trying to populate a test database with some realistic data?), and who also has access to the DEK. Even if the insider means no harm, that data may sit on their hard drive for a couple years, forgotten, until the wrong malware/hacker comes along and grabs everything off their machine.

There may be more advantages to rotating the DEK, but that is the first that comes to mind. Whether there are other advantages and whether or not that is worth the effort for you are questions that only you can decide.

Answer 3

First, you should have a clear threat model and a rationale for your choices: Why are you using a three layers of encryption keys? Why not two, or twenty? Why do you rotate the keys? How are you expecting the data to be stored?

And second, rotating the DEK doesn't neccessarily require re-encrypting many blocks of data (immediately).

Option A would be to change the DEK, generating new KEKs, DEKs and re-encrypting all the data. This is probably what you had in mind.

However, there are also other possibilities:

Option B would generate a new MK, re-encrypting all its KEKs, leaving The KEKs (and below) to be changed at its designed rotation time.

Option C would be, when generating a new MK, to encrypt within its block the old MK. The KEKs can include a serial number (or simply, a random id) identifying the MK that was used to protect it (alternatively, you could simply try decrypting them with every MK, until finding one which decrypts properly. you do have something like an HMAC (or an AEAD mode) to verify that decryption of the key blocks is correct, right?).

Although potentially useful for verification purposes, decrypting a block with random key A using algorithm X, to re-encrypt it with random key B with the same algorithm X, just for the sake of it, doesn't really seem needed...