There are multi-key attacks against some AEADs. In other words, multiple keys can be used to decrypt a message since multiple keys can be valid for an authentication tag. How would one go about adding key commitment to an AEAD like AES-GCM or ChaCha20-Poly1305? The three ways mentioned by libsodium are:

1. Key identifier in the nonce.
2. Key identifier in the additional data.
3. Zero padding prepended to each message that gets verified after decryption.

However, 3 could be vulnerable to timing attacks (since this verification occurs after verification of the authentication tag), and 1 makes handling the nonce more complicated. That leaves a key identifier in the additional data, but what's the best way of achieving this?

Could you just use the encryption key as additional data? Should you hash the key and use it as additional data? How about a keyed hash using the key and some other data?

• Including the key (or the hash of the key) in the AAD doesn't work - the linear algebra problem the attacker would use to find the ciphertext that decrypts with both would not be any harder. Now, your idea 3 would appear to work, and could be made constant timing with proper implementation (yes, I know it's a bad idea to assume implementors get things right...) Jan 25 at 14:24
• Are you sure? The key identifier notion seems to have been mentioned in several papers, but it's not clear how to actually create the identifier. Jan 25 at 14:28
• Also the constant timing issue is more about the delay between the library you're using saying that the authentication tag is valid and then the zero block check failing afterwards. Since it's not integrated into the library AEAD algorithm. Jan 25 at 14:30
• If my reading(skimming) of this paper eprint.iacr.org/2017/664.pdf is more or less correct, non-collision resistant MAC are more or less impossible to use for key-committing schemes. Jan 25 at 14:36

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:

1. 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.

1. 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.

1. 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).

• I'm not sure you're discussing the same attack. I'm referring to multiple keys being able to decrypt the message since multiple keys can be valid for the tag. Jan 25 at 15:37
• @Edgar: that is precisely the attack I am discussing; that the attacker finds a message that decrypts (to something) under multiple keys. Jan 25 at 16:29
• Fantastic answer.. quick follow up, I'm right in my understanding that non-commiting AEAD doesn't mean that the Ciphertext will decrypt to correct plaintext with multiple keys, just that the tag check will pass with multiple keys right? - if so, do we know what percentage of the possible keys the tag would pass for? Apr 5 at 12:31
• @Woodstock: your understanding is correct; all it gives the attacker is valid tag checks. As for the percentage of keys that would pass the valid tag check, that is tiny (circa $m 2^{-128}$, where $m$ is the message length in blocks); the point of this noncommitting attack is that, while this percentage is tiny, the attacker can pick which keys will reside in that tiny percentage... Apr 5 at 12:39