What is the Risk of Rotating Keys

Question

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?

Answer 1

$\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.