Adding key-committing AEAD implementations (CTX or UtC/RtC/HtE)

[brycx]

I think it would make sense to start thinking about adding key-committing AEADs to the library. In general there seem to be two recent proposals that transform non-committing AEs into committing ones.

The first, are the UtC/RtC/HtE constructions by Bellare & Hoang in https://eprint.iacr.org/2022/268. Second, we have CTX proposed by Chan & Rogaway in https://eprint.iacr.org/2022/1260.

The most notable difference is that the UtC/RtC transforms work for either nonce-based AEADs and MRAEs, respectively. CTX only works for nonce-based AEADs. Orion currently only supports nonce-based AEADs, but if we choose to go with CTX then we'd need to implement RtC/HtE later on, if we add MRAE as well and wish to add key-commitment there as well.

On the other hand, CTX is much simpler to implement than UtC/RtC/HtE. Further, CTX commits to the entire input set (key, nonce, ciphertext, ad), whereas UtC only commits to the key and needs HtE on top, to be fully committing. For this reason, I think it would be best to start with CTX.

Questions remaining:

• Should this be behind an experimental flag?
• The intention is to eventually replace the high-level AEAD implementation to be fully committing. Should the high-level interface be modified in the first release, even if gated behind a feature flag, or not?
• What sizes for the new authentication tags should be chosen? 256-bit seems to be a reasonable choice. This is important because the security of the commitment scheme is based on the collision-resistance of the hash function used for CTX.
• Do we add key-commitment to XChaCha20-Poly1305 only or ChaCha20-Poly1305 also (I think both are good, then it makes sense to start providing key-committing implementations in the hazardous layer and move it to high-level up later on)

[samuel-lucas6]

Hi, I saw your blog post on r/crypto, and that led me here. Interestingly, I'm also doing a master's and am doing my dissertation on committing AEAD, although I haven't started yet. Respect for simplifying the topic; the literature is a mess with the different terminology and overcomplicated language.

I think a patch worth considering is the modified padding fix by Loup Vaillant, which I implemented here. It uses free output after the Poly1305 key and can be implemented without introducing a timing difference between tag/commitment verification. However, it's not fully committing and does lead to a bit of ciphertext expansion.

From what I understand about CTX (please correct me if I'm wrong), it's not compatible with the ChaCha20-Poly1305 RFC because the tag is computed over the plaintext, not the ciphertext. That's rather a bummer as it basically means it's an entirely new algorithm.

I believe they suggest 160 bits to reduce ciphertext expansion, but I agree 256 bits makes more sense for proper collision resistance. I also agree with the idea of making things fully committing, but I would argue the best way of doing that is Encrypt-then-MAC until new committing AEADs are developed. The performance will generally be worse, but you can get implementations that are as fast as/slightly faster than ChaCha20-Poly1305 on at least certain machines with certain input sizes. For the performance trade-off, you get a fully and compactly committing scheme with better security against forgeries, less ciphertext expansion than most fixes, and no feeling of patching something up.

As there's no agreed approach for Encrypt-then-MAC as an AEAD, I started working on an Internet Draft a while back. I'll update it after doing my dissertation. Two new AEADs to keep an eye on though are AEGIS, which should be key-committing but not compactly committing, and Rocca-S, which should be at least (probably more than) key-committing as it has a 256-bit tag. Both are insanely fast, even holding up without AES-NI.

[brycx]

Sorry for taking so long to respond and thanks for reaching out!

I think a patch worth considering is the modified padding fix by Loup Vaillant, which I implemented here.

I wasn't aware of an implementation of this, but I have explored this. My stance remains as I mentioned in the post; I'll aim to provide a fully committing construction, such that users won't have to deal with making decisions on whether only key commitment is suffucient for their use-case.

From what I understand about CTX (please correct me if I'm wrong), it's not compatible with the ChaCha20-Poly1305 RFC because the tag is computed over the plaintext, not the ciphertext. That's rather a bummer as it basically means it's an entirely new algorithm.

I was confused about this as well, when I first read the paper, but I believe it still applies. On p. 10 we do have a definition of Π.E1(K, N, A, M) and Π.E2(K, N, A, M), the latter being the MAC. This implies Encrypt-and-MAC, but on the previous page they also say that GCM (a Encrypt-then-MAC scheme, like ChaCha20-Poly1305) satisfies these "structural demands".

The reasoning for this I believe can be found on pp. 2-3 where they state:

"The remarkable fact is that this extremely simple tweak to the nAE scheme not only works to commit to K, N, and A, but also to the underlying message M. This ultimately follows from the injectivity of the map from the ciphertext core C to the plaintext M when K, N, and A are all fixed."

Please let me know if you think I'm wrong here.

Re:

but I would argue the best way of doing that is Encrypt-then-MAC until new committing AEADs are developed

See my comment regarding CTX and Encrypt-then-MAC. I agree, this can also be solved by making a committing Encrypt-then-MAC, but then you also need to worry about canonical encoding of AD parameters. I'm currently more in favor of adding commitment to more well-known AEAD constructions instead of making new ones. Adding a new AEAD construction, purely for the benefit of key commitment, would also add a substantial amount of code to audit, compared to say, CTX.

As there's no agreed approach for Encrypt-then-MAC as an AEAD, I started working on an Internet Draft a while back. I'll update it after doing my dissertation. Two new AEADs to keep an eye on though are AEGIS, which should be key-committing but not compactly committing, and Rocca-S, which should be at least (probably more than) key-committing as it has a 256-bit tag. Both are insanely fast, even holding up without AES-NI.

Thanks, these are interesting and will keep an eye on it. Didn't know AEGIS/Rocca-S would be key committing.

[samuel-lucas6]

I'll aim to provide a fully committing construction, such that users won't have to deal with making decisions on whether only key commitment is suffucient for their use-case.

If combined with Hash-then-Encrypt, it should be fully committing. However, I fully understand your preference for CTX.

on the previous page they also say that GCM (a Encrypt-then-MAC scheme, like ChaCha20-Poly1305) satisfies these "structural demands".

Yes, I noticed that too. I'm not sure why the pseudocode is ambiguous. I've emailed Rogaway, so I'll let you know what he says if he replies. However, I believe you're correct that it works either way after a second thought.

Another thing is why is the associated data being processed by the inner MAC and the outer MAC? Like with Hash-then-Encrypt, it should be fine to avoid passing the associated data to the inner MAC.

The only other issue I see with CTX is that it requires using a library that supports the AEAD MAC separately from the AEAD one-shot interface. For example, the .NET crypto library supports AES-GCM and ChaCha20-Poly1305 but not GMAC or Poly1305 separately. Even NSec, a popular .NET libsodium binding, doesn't support Poly1305 separately, presumably due to misuse concerns. It would be annoying to add an additional dependency in such cases.

I'm currently more in favor of adding commitment to more well-known AEAD constructions instead of making new ones.

That makes sense. I agree CTX is the ideal construction in that regard and probably for universal performance too, aside from the associated data optimisation.

Didn't know AEGIS/Rocca-S would be key committing.

Hopefully Rocca-S and future AEADs will be fully committing.

If we don't speak again, best of luck with your thesis!

[brycx]

I've emailed Rogaway, so I'll let you know what he says if he replies.

Please do!

Another thing is why is the associated data being processed by the inner MAC and the outer MAC? Like with Hash-then-Encrypt, it should be fine to avoid passing the associated data to the inner MAC.

What I think you're referring to here are two different "inner MAC"s. For Hash-then-Encrypt, they do pass it during the evaluation of H(K, (N, A)), but the underlying AE still processes the AD as well, when talking about UtC and HtE. This is the same as CTX, which is basically a combination of HtE+UtC, in terms of commitment provided. The SE.Enc, in the pseudocode for HtE, refers to a key-committing AE (or what Bellare and Hoang call CMT-1) whereas SE.Enc for UtC/RtC pseudocode refers to a non-comitting AE (ambiguous notation reuse).

I think what we need to keep in mind here is that both approaches are designed to be put "on top" of an existing AE.

Edit: I looked at the wrong pseudo-code listing for HtE. You're right in that HtE does in fact just not pass the AD param to the CMT-1 AE. It's not immediately clear to me why this is the case, when comparing with CTX.

The only other issue I see with CTX is that it requires using a library that supports the AEAD MAC separately from the AEAD one-shot interface. For example, the .NET crypto library supports AES-GCM and ChaCha20-Poly1305 but not GMAC or Poly1305 separately. Even NSec, a popular .NET libsodium binding, doesn't support Poly1305 separately, presumably due to misuse concerns. It would be annoying to add an additional dependency in such cases.

I don't see how CTX is not usable with a one-shot API. You need K, N, A, T and all these are provided by one-shot APIs. You could simply call var buf = chacha20poly1305(k, n, a, m), where the buffer will contain both C and T. Then you'd just refer to the last 16 bytes of buf as T and set buf[buf.len() -16..] = H(K, N, A, buf[buf.len() -16..16]). Then, returning buf that is now C || T*.

If we don't speak again, best of luck with your thesis!

It's already done, but thanks anyway :) Wish you the best of luck with yours as well.

[samuel-lucas6]

Please do!

Ok he says you do a 'conventional AEAD operation' to generate the ciphertext core C and tag T, implying Encrypt-then-MAC is fine. However, he then said 'when you decrypt, you decrypt C to get the plaintext M and the tag T' that accompanies the plaintext'.

I think I'll have to reply to clarify Encrypt-then-MAC specifically as I'm assuming he's talking about an OCB style AEAD.

Edit: I looked at the wrong pseudo-code listing for HtE. You're right in that HtE does in fact just not pass the AD param to the CMT-1 AE. It's not immediately clear to me why this is the case, when comparing with CTX.

Yep, I'm pretty confident there's no issue with just passing it to the outer MAC and not the AEAD. I can ask about this as well in my reply.

I don't see how CTX is not usable with a one-shot API.

For encryption, there's no issue. However, with decryption, there are two issues:

1. The one-shot decryption API requires an AEAD tag, which you don't have with the CTX construction because it's not stored. Therefore, you need the MAC function separately to compute the AEAD tag over the ciphertext to use the API.
2. You can't compute the AEAD tag to do the T* verification because you have no separate AEAD MAC function (e.g. Poly1305). The one-shot encryption API would produce a different AEAD tag because you only have the ciphertext, not the plaintext.

If you're doing decryption before the tag computation, like the pseudocode, you might also want an unauthenticated encryption function. The .NET crypto library and NSec provide neither of these. I doubt most libraries provide GMAC separately from AES-GCM, although things may be slightly easier with ChaCha20-Poly1305 and Poly1305.

I think what we need to keep in mind here is that both approaches are designed to be put "on top" of an existing AE.

This is why the above may be problematic. Compared to things like UtC, CTX is more difficult to put on top of an existing scheme.

If you stored the tag, which is basically the libsodium fix plus hashing the associated data, this wouldn't be a problem. However, there would then be a timing side-channel because you're verifying the (key, nonce || associatedData || tag) and ciphertext separately. You'd check T* first using the stored AEAD tag (T), then you'd call the one-shot decryption API, which would throw an error if the ciphertext had been manipulated.

It's already done, but thanks anyway :) Wish you the best of luck with yours as well.

Bet you're glad that's out of the way. Thanks!

[brycx]

For encryption, there's no issue. However, with decryption, there are two issues:

Right. I keep on forgetting about the requirement during decryption, even when I worked on an implementation of CTX.

The .NET cryptography ecosystem offers much less availability/flexibility for these things, compared to Rust, in my experience.

In terms of this library though, we do provide access to Poly1305 through the hazardous API-layer, especially internally, so it shouldn't be a problem here. But this could mean it sees less adoption elsewhere, meaning this library, should it provide CTX, could end up providing a less popular commitment transformation. However, 1) we can always provide different approaches if this ends up being the case (CTX and UtC) 2) we won't know what other libraries will choose, but key commitment is needed now, so I think it's worth risking a less popular approach. Plus, it's most likely going behind a feature-flag so we're not committing (pun intended) to an API right away.

Bet you're glad that's out of the way.

Very much so :)

[brycx]

Experimental support (gated behind the experimental feature-flag) for this will be available in the 0.17.5 release.