I'm currently debating whether to revert to a non-committing AEAD (ChaCha20-Poly1305) instead of a committing AEAD based on Encrypt-then-MAC (XChaCha20-BLAKE2b) for stream encryption. Borg backup made the switch, and non-committing AEADs have several advantages:

  1. Standardised
  2. Generally faster
  3. Less overhead due to short tags
  4. The done thing/easier to get right

Of course, the downside is that they're not committing. This is problematic when keys can be adversarial (e.g. password-based encryption with a server that knows the key). You end up missing what should be considered an essential security property.

So, to avoid potential attacks, you need to implement a fix, like Amazon did. Unfortunately, most don't provide associated data/message commitment still, and it's not clear how severe of an issue that is. Ignoring that, here are some options for key commitment that don't modify the AEAD algorithm:

  1. Padding fix: prepend 256 zeros to the plaintext. After decryption, check that they're zeros in constant time.
  2. Generic/UtC transform: use a collision-resistant cryptographic hash function/KDF to derive an encryption key and commitment tag. A nonce can be used or left out in the key derivation. You then append the commitment tag to the ciphertext and check this before or after decryption in constant time.
  3. libsodium fix: prepend a MAC of key || nonce || tag to the ciphertext. Verify this in constant time before decryption.
  4. Padding fix 2: prepend 256 zeros to the plaintext. For decryption, re-encrypt 256 zeros and compare it to the prepended zeros in constant time.

The idea would be to commit to the key in the first chunk of the stream to minimise overhead and complexity. Otherwise, the speed and storage may be worse than Encrypt-then-MAC.

However, surely all of these fixes leak information because there's a timing difference between the Poly1305 verification and key commitment check? That's potentially enough to exploit a partitioning oracle attack.

To completely avoid a timing leak, you would need to do the key commitment check at the same time as verifying the Poly1305 tag, which means you can't use most cryptographic library APIs. You'd have to manually combine ChaCha20 and Poly1305, which is similar in difficulty to implementing Encrypt-then-MAC yourself.

Should this be a concern? Why are the newer papers not talking about this (unless I missed it)? Encrypt-then-MAC done properly eliminates any leak and provides CMT-4 security (commit to all inputs) instead of the mere CMT-1 security (commit to the key) from these fixes.

  • $\begingroup$ On reflection, I think the best way around this is to do ChaCha20-Poly1305-then-MAC for the first chunk, which in my case is a pretty short header. Assuming committing once is enough, that's probably the best solution. $\endgroup$ Commented Aug 11, 2022 at 14:18
  • 1
    $\begingroup$ Could you expand on why you think that "surely all of these fixes leak information via timing"? I don't see that making constant-time implementation of verification and decryption is infeasible, or even hard. $\endgroup$
    – fgrieu
    Commented Aug 20, 2022 at 10:42
  • $\begingroup$ @fgrieu Is that clearer? It's the timing difference between Poly1305 and the key commitment fix that's the problem because they will return errors at different times. $\endgroup$ Commented Aug 20, 2022 at 11:10
  • 1
    $\begingroup$ Ah I get it now. I had missed you are thinking of using ChaCha20-Poly1305 as a black box (although it was already pretty clear). Indeed I can't think how to avoid a timing side channel. This makes "Should this be a concern?" relevant. $\endgroup$
    – fgrieu
    Commented Aug 20, 2022 at 16:02
  • 1
    $\begingroup$ @ANISHM18CS006 The padding fix implemented naively will lead to a timing difference, but the UtC/libsodium fixes shouldn't be a problem if you perform the check before decryption. However, I'm still convinced Encrypt-then-MAC is the way to go until committing AEADs are developed and standardised. Doing this type of patch each time is real ugly and can lead to more overhead than Encrypt-then-MAC. There's hope with Rocca-S, which has a 256-bit tag whilst being insanely fast. $\endgroup$ Commented Aug 26, 2022 at 17:43


Your Answer

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