How would one go about adding key commitment to an AEAD like AES-GCM or ChaCha20-Poly1305?
First off, let us start by reviewing how AES-GCM/Poly1305 works internally (and how these key commitment attacks work).
Here's a top level overview of how they work (and AES-GCM and Poly1305 work largely the same at this level): first the ciphertext and AAD are combined to form a series of field elements $M_n, M_{n-1}, ..., M_1$; the details of how they are combined differ between the two; however they both have the property that they can control the value of a specific message block $M_i$ by adjusting a specific ciphertext block.
Then, the take a key dependent value $H$, and compute in some finite field the polynomial:
$$M_n H^n + M_{n-1} H^{n-1} + ... + M_i H^i + ... + M_1 H^1 + F(key, nonce)$$
And that is the tag (well, not quite in Poly1305; the final addition is done modulo $2^{128}$, however that is only a minor complication for this attack).
The finite fields differ between the two (GCM uses $GF(2^{128})$, while Poly1305 uses the prime field $GF(2^{130}-5)$), but that doesn't matter.
Now, the attacker who is trying to find a message that has the same tag for two different keys (and hence would be accepted as valid under both keys) controls the ciphertext, and knows everything (the AAD, the key, the H values, and the values of $F(key, nonce)$. So, what the attacker can do is fix the entire ciphertext (except for the part that contributes to $M_i$), and combine those parts of the tag computation into known constants $C, C'$, and then look for a value of the remaining ciphertext block that gives rise to an $M_i$ value that satisfies:
$$M_i H^i + C = M_iH'^i + C'$$
(where $H, H'$ are the internal $H$ values of the two keys). This is an easily solved problem, leading to the message that would have the same tag value for both messages (and since the attacker knows everything, he can easily compute that common value). Actually, it's a bit more complicated for Poly1305, as not all $M_i$ values can be obtained from a ciphertext block, however a nontrivial fraction can, and so the attacker can find such a value by adjusting another ciphertext block with not that much effort.
Ok, now that we have reviewed the attack, let us examine how well these three ideas would fare:
- Key identifier in the nonce
In the above attack, this would modify the value $F(key, nonce)$ values to be dependent on the key; however that is already dependent on the key, and so the attack would proceed exactly as planned.
- Key identifier in the additional data.
In the above attack, this would modify some $M_j$ values (the ones that are dependent on the AAD); however $j \ne i$, and because the attacker would know these $M_j$ values, this would just modify the $C, C'$ values that appear in the above attack, and so would not complicate this attack at all.
- Zero padding prepended to each message that gets verified after decryption
The above attack doesn't address this at all. Instead, this defense happens during the actual decryption step; in this step, the crucial plaintext block would be computed $P_i = C_i \oplus F( key, nonce, i )$, and to find two different keys that decrypt the $P_i$ block to all zeros (which is required for the message to be accepted with both keys), the attacker would need to find two keys where $F( key, nonce, i ) = F( key', nonce, i )$; there is no known weakness in either AES or ChaCha20 that could be exploited, hence the best attack known would be a birthday collision attack. This indicates that to get a security strength of $2^k$ against this attack, we would need to prepend $2k$ zeroes (which may involve a collision attack across several blocks; this doesn't change the analysis).
