4
$\begingroup$

Many of the presentations at The Third NIST Workshop on Block Cipher Modes of Operation 2023 complain about the lack of key commitment in AES-GCM.

But isn't that one application of "associated data?" For instance, can't one include a hash of the key (or something similar) in the associated data?

$\endgroup$
3
  • 1
    $\begingroup$ Related to the title, it's important to note that this is a much wider problem than just AES-GCM. Think of essentially any popular AEAD scheme and it's not committing, except for constructing one via generic composition (e.g. AES-CTR-then-HMAC). Even new schemes haven't had commitment as a design goal. For example, look at the CAESAR/NIST LWC competition papers and try to find commitment mentioned. This is despite the fact it should be present for security by default as it's intuitively what you'd expect from an AEAD. $\endgroup$ Oct 7, 2023 at 12:39
  • $\begingroup$ @samuel-lucas6 HMAC turned into beast, however, it is not theoretically proven to be not key committing, just very hard to achieve. $\endgroup$
    – kelalaka
    Oct 9, 2023 at 15:37
  • $\begingroup$ @kelalaka What do you mean? HMAC with any collision-resistant hash function or any keyed collision-resistant hash function/XOF (e.g. keyed BLAKE2b) is committing assuming you either a) use a single key for the AEAD and MAC, b) derive a separate AEAD encryption key and MAC key from the same master key using the collision-resistant MAC, or c) compute the MAC over the AEAD encryption key, nonce, and associated data (optionally also the ciphertext). The output should be 160+ bits. Several of the commitment papers have stated this, and it follows from the properties of cryptographic hash functions. $\endgroup$ Oct 9, 2023 at 18:10

2 Answers 2

6
$\begingroup$

But isn't that one application of "associated data?" For instance, can't one include a hash of the key (or something similar) in the associated data? Maybe I'm missing the point...

Actually, that doesn't help with GCM.

With GCM, the tag is computed by converting the message and the AAD into a polynomial, and evaluating that polynomial at a value $H$ (which depends on the key).

If you include the hash of the key into the AAD, all the attacker needs to do is:

  • Pick a nonce and two keys $K_1$, $K_2$, and the corresponding $H$ values $H_1, H_2$, and a target ciphertext message with one block unspecified.

  • Generate polynomial 1 (which depends on the hash of $K_1$) and the value that is xor'ed into the tag as the constant value (that value depends on the nonce and $K_1$), the unspecified block in the message will translate to a coefficient of the polynomial, which we will treat as an unknown.

  • Generate polynomial 2 (which depends on the hash of $K_2$) and the value that is xor'ed into the tag as the constant value (that value depends on the nonce and $K_2$), the unspecified block in the message will translate to a coefficient of the polynomial, which we will treat as an unknown.

  • Find the value of the unknown coefficient for which polynomial 1 (evaluated at $H_1$) is equal to polynomial 2 (evaluated at $H_2$). This is a linear equation in one variable, hence it is easy.

The solution of that gives you the open entry in the message; hence that, with the corresponding tag value (which is easy to compute) will validate with both $K_1$ and $K_2$, thus violating key commitment.

If you want a message that validates with $n$ different keys, that's pretty much the same procedure (except you need to solve $n-1$ linear equations in $n-1$ unknowns).

Now, one idea that does work with GCM is 'include a fixed block in the plaintext (say, all zeros), and reject the decryption if that block doesn't decrypt to the expected value'. This works with 12 byte nonces [1] (because it's a hard problem to find two distinct keys $k_1, k_2$ and a counter value $c$ (derived from the nonce) where $AES_{k_1}(c) = AES_{k_2}(c)$, which is what would be needed). It does add some extra ciphertext expansion, however, it also introduces a second path to reject messages, and so doing that without introducing a timing difference requires some care.

[1]: For nonces other than 12-bytes, you need two blocks of fixed data; that's because that uses a key dependent 'nonce -> counter' transformation; hence for a single fixed block, the problem becomes $AES_{k_1}(c_1) = AES_{k_2}(c_2)$, which is easy. With two fixed blocks, it becomes $AES_{k_1}(c_1) = AES_{k_2}(c_2) \wedge AES_{k_1}(c_1+1) = AES_{k_2}(c_2+1)$, which is hard...

$\endgroup$
5
  • 1
    $\begingroup$ I'm not sure, if the hash is included with the ciphertext then it would be bound to a specific key, right? If you first check if the key you have results in the hash and then verify the ciphertext, would any of the calculations actually matter? I'd call it cheating as it doesn't rely on GCM or the tag at all, but I think it should work? It definitely would not fit with the premise of the question - the AD is kinda pointless, basically you'd include a KCV and that doesn't need protection for complying with key commitment. I think the answer only works if the hash isn't included. $\endgroup$
    – Maarten Bodewes
    Oct 6, 2023 at 20:05
  • 1
    $\begingroup$ Thinking more about it: the hash is probably not considered part of the message but part of the authentication tag, in which case the point above doesn't work and the answer of poncho is again correct. I'll leave my upvote :) I'm now left wondering if you can at all fix a non-key-committing cipher without introducing an additional MAC, which of course defies the purpose. $\endgroup$
    – Maarten Bodewes
    Oct 6, 2023 at 20:29
  • $\begingroup$ @MaartenBodewes: actually, my last paragraph gives a way to fix GCM (with 12 byte nonces) in a way that doesn't involve an additional hash/MAC. Now, it's obviously not a generic solution... $\endgroup$
    – poncho
    Oct 6, 2023 at 21:15
  • $\begingroup$ Oh, yeah, because you can keep the value secret that way. Yes, obviously not generic but nevertheless an interesting fix, and if you first verify the tag then it isn't much of a problem. Doing a binary compare isn't the hardest function to do in constant time either if that's required. $\endgroup$
    – Maarten Bodewes
    Oct 6, 2023 at 21:26
  • 1
    $\begingroup$ @MaartenBodewes: actually, the concern was, if you gave this spec to an average coder, he is likely to do something like (in C) if (!tag_validates || plaintext.fixed_field != expected) fail();, which C specifically defines as nonconstant time. It's not hard to do the right thing; you have to realize it needs to be done... $\endgroup$
    – poncho
    Oct 6, 2023 at 21:30
2
$\begingroup$

This blog post gives a great summary of modern proposals for generic transformations from existing non-committing AEAD schemes to committing AEAD. The two excellent papers referenced are "Efficient Schemes for Committing Authenticated Encryption" by Mihir Bellare & Viet Tung Hoang; and, "On Committing Authenticated-Encryption" by John Chan & Phillip Rogaway.

Key commitment in GCM (or AEAD in general)[ ?]

The generic transformations defined by the above papers provide varying levels commitment (from just key commitment to the full commitment of all inputs) with no additional ciphertext expansion. From my reading, it can be said that the transformations consider two principle approaches. The first is fixing the production of the final tag to be the output of a difficult to forge function, like a collision-resistant PRF, instead of a polynomial. And, the second is creating an input-specific key which is the output of a hash.

The later paper uses a simplified approach which is a combination. The ciphertext $C$ & tag $\tau$ are processed normally, but then the final tag $\tau^* \leftarrow H(K, N, A, \tau)$ replaces $\tau$. But, this only effects the authentication tag, meaning it doesn't assist in any way in blending $n_{once}$ misuse-resistance & committing AEAD (e.g. further affecting the ciphertext randomization).

The former paper separates the approaches. First turning a non-committing AEAD scheme $\textsf{SE}$ into a key-committing $\textsf{CMT-1}$ scheme $\textsf{SE-1}$ by using a collision-resistant hash for the final tag production. Then, treating the $\textsf{SE-1}$ scheme to another generic transformation to a fully committing $\textsf{CMT-4}$ AEAD scheme $\textsf{SE-4}$ by replacing the encryption key $K$ with a keyed-hash output $L \leftarrow H(K, (N, A))$ & the associated data $A$ with an empty string $\epsilon$. This results in $\textsf{SE-1}(K, N, A, M)$ being transformed into $\textsf{SE-4}(L, N, \epsilon, M)$.


But isn't that one application of "associated data?" For instance, can't one include a hash of the key (or something similar) in the associated data?

The existing answer by poncho explains why just altering the associated data to include the hash of the inputs doesn't help in the case of AES-GCM.

However, this approach is essentially what is done in $\textsf{SE-4}$ schemes, except that the key becomes the hash of the inputs, instead of the hash of the inputs being used as the associated data.

$\endgroup$
1
  • $\begingroup$ Some more transforms/patches/schemes are specified in the third workshop papers: The Landscape of Committing Authenticated Encryption, KIVR, and Flexible Authenticated Encryption. There's a paper on making a committing AEAD via SHAKE from Joan Daemen. Then the AEGIS AEAD schemes from the CAESAR competition are key committing in some contexts. Rocca-S used to claim key commitment but no longer. $\endgroup$ Oct 7, 2023 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.