# What is the Risk of Rotating Keys

This may be a difficult question

• So, $$C_1$$ = AES-GCM($$k_1$$, nonce, message) where nonce = HMAC(key,message). $$C_2$$ = AES-CBC($$k_2$$, iv, $$C_1$$).
• Now, a security breach occurs. The adversary obtains $$k_1$$ and $$C_2$$ because they are the most vulnerable parts of my encryption scheme. I change the keys in this instance and re-encrypt the database.
• Now, $$C_3$$ = AES-GCM($$k_3$$, nonce, message). $$C_4$$ = AES-CBC($$k_4$$, nonce, $$C_3$$).
• Then there is another data breach. The adversary now has $$k_3$$ and $$C_4$$.

1.) If the adversary has $$k_1$$, $$k_3$$, $$C_2$$ and $$C_4$$ can he decrypt the messages?

TL,DR explanation

In my encryption scheme, I have two sets of 256 bit secret keys [$$c_1$$,$$c_2$$] used to encrypt data. The first key is used by my customers to encrypt data using AES-GCM. The second key is used to encrypt the data once again using AES-CBC with PKCS#7 padding before being saved on the server. Please assume I never repeat the same 96-bit nonce when using AES-GCM. My message length is short and the number of messages encrypted will remain well below 1 billion.

How would a worst-case scenario play out assuming the adversary already has the customer key? If an adversary obtains the data on the database I will change the keys and re-encrypt the data using the new keys. If an adversary then obtains all of the data once again can he break my encryption assuming he has the customers key?

• This question might be better suited on security.SE rather than here on crypto.SE. Apr 5 '19 at 16:53
• Keep in mind that old copies of ciphertexts (backups, captured in transit, etc) will always be decryptable with their old keys. This doesn't immediately create a new risk (assuming secure generation of keys and secure key management), but it does mean that stolen old keys is just as big of a threat as stolen current keys, if that data still is sensitive. In this case, with strong encryption algorithms, the use of multiple encryption layers "only" adds limited protection against threats like an insider snooping in the database Apr 5 '19 at 18:14
• What I understand from your question is that you are a service provider to store the data of the client encrypted first the client key than your key. Once the adversary access the client key, you will let him get the data as you think that he is the client. If the adversary cannot access the double encrypted files, he cannot brute-force the encryption since he will not get ciphertext-plaintext pair. Even he has access, then you AES-256 will protect you. Note: while using AES-GCM make sure that the client is not resuing IV. Apr 5 '19 at 18:29
• There is also the slight possibility of CBC padding oracle attacks, although the window to exploit them may be too small. Dear user67220, could you please extract out the technical questions about GCM / CBC in this scenario? The other parts of this question are better asked at security.stackexchange.com. Apr 6 '19 at 10:38

$$\newcommand{\AE}{\mathit{AE}}$$ Let $$\AE$$ be an authenticated cipher (AES-GCM) and $$E$$ an unauthenticated cipher (AES-CBC).

Let $$k_1$$ and $$k_2$$ be independent uniform random. Let $$m$$ be a message. Let $$c_1 = \AE_{k_1}(m)$$ and $$c_2 = E_{k_2}(c_1)$$. If the adversary knows $$k_1$$ and $$c_2$$, but not $$k_2$$ or $$c_1$$, can they learn anything about $$m$$?

The answer is no: the security of $$\AE$$ and the randomness in the initial choice of $$k_1$$ is irrelevant; if an adversary could learn anything about $$m$$ from the ciphertext $$c_2$$, that would violate the semantic security of $$E_{k_1}$$.

In particular, if we had an algorithm $$A(k_1, c_2)$$ which returned $$m$$ with probability $$\varepsilon$$, we could use this as a ciphertext distinguisher for the cipher $$E$$ with advantage at least $$\varepsilon$$: pick a key $$k_1$$ uniformly at random, and submit challenge messages $$m_0 = \AE_{k_1}(m)$$ and any other $$m_1 \ne m_0$$; then, given a challenge ciphertext $$c = E_{k_2}(m_b)$$ for unknown $$b$$, run $$A(k_1, c)$$ and guess $$b = 0$$ if $$A$$ returns $$m$$, and $$b = 1$$ if not.

What if you re-encrypt the same messages with fresh independent keys? Same deal.

There are operational issues to worry about too:

• Is eavesdropping of $$k_1$$ and $$c_2$$ (and $$k_3$$ and $$c_4$$, etc.) the only power of the adversary, or can they forge and modify things too?
• If the adversary can influence $$c_1$$, motivating the use of the authenticated cipher AES-GCM, can they influence $$c_2$$? Naive use of AES-CBC may expose you to padding oracle attacks.
• Rotating keys doesn't prevent an adversary from using old keys to decrypt old ciphertexts. It only prevents them from using old keys to decrypt new ciphertexts or vice versa. If the adversary ever records old ciphertexts, then any future disclosure of the old keys will reveal the plaintexts.
• The narrow cryptographic question here—of whether $$m \mapsto (k_1, E_{k_2}(\AE_{k_1}(m)))$$ has semantic security or ciphertext indistinguishability—isn't affected by the additional details about key rotation. But what is the bigger picture here—what resources do you have, what are you trying to do with them, what attack surfaces does the adversary have to exploit these resources, and what are you trying to prevent the adversary from doing? Do you have a living design document setting all of this down? This is bigger picture is where you should focus your efforts to make sure your whole design is sound before worrying about little cryptographic details.
• Thank you for your help. The system I am developing I hope will minimize the adversary's ability to obtain or influence all that you mention. When I am complete would you recommend I publish details on my implementation here or on security.stackexchange.com? I feel like what I implement should be able to withstand public scrutiny but this of course allows the public access to intellectual property and likely makes me more vulnerable to attack. Apr 10 '19 at 15:34
• You should assume the adversary knows the system; security should come from design of the system and secrecy only of the keys. You have an ethical obligation to your users to share with them, and with any experts they want to consult, the details of how the system attains any security you claim: the more of it you keep secret, the more you are tempted to lie to yourself and your users about its security, and the less scrutiny it can ever receive. That said, neither crypto.SE nor security.SE is the right forum for posting full living design documents—they're for narrowly scoped questions. Apr 11 '19 at 1:54