Subject: [Cfrg] A standard for committing authenticated encryption

From: Paul Grubbs <[email-masked]>
Date: Mon, 11 Nov 2019 18:57:33 -0500

Hello all,

A 'committing' authenticated encryption (cAE) scheme is one for which it is
hard to find a ciphertext having multiple correct decryption keys.*  More
formally, a cAE scheme's ciphertexts are binding commitments. AE security
of a scheme does not imply its ciphertexts are binding commitments, and
widely-used AE schemes like Galois/Counter Mode and two-key
encrypt-then-MAC are not cAE [1]. This has already led to attacks on
already-deployed protocols like message franking [2]; cAE is also needed in
protocols like OPAQUE [3, 4] that may soon be standardized and deployed,
and is useful elsewhere (e.g., group messaging/MLS).

Though cAE is needed in practice, there is no standards document explaining
cAE and defining secure schemes. I think such a document would be really
helpful to researchers and practitioners alike, so I'd like to initiate
some discussion in the mailing list ahead of the CFRG meeting at IETF 106
next week, where hopefully Nick will present a few slides to get people
thinking about cAE.

Right now, I'd really like to know whether people think this is needed or
useful, and what they'd like to see out of an eventual RFC. Also, if you've
ever needed committing AE or have encountered a setting where encryption
keys and/or ciphertexts can be adversarially chosen, I'd love to hear about
it.

Thanks everybody!

*Some prior work [5] calls this and other similar properties 'robustness'.
Since 'robust' is already an overloaded term in cryptography, I prefer
'committing'.

[1] Message Franking via Committing Authenticated Encryption (
https://eprint.iacr.org/2017/664)
[2] Fast Message Franking: From Invisible Salamanders to Encryptment (
https://eprint.iacr.org/2019/016.pdf)
[3] OPAQUE draft (https://tools.ietf.org/html/draft-krawczyk-cfrg-opaque-03)
[4] OPAQUE in TLS draft (
https://tools.ietf.org/html/draft-sullivan-tls-opaque-00)
[5] Security of Symmetric Primitives under Incorrect Usage of Keys (
https://eprint.iacr.org/2017/288)

---

From: Yevgeniy Dodis <[email-masked]>
Date: Mon, 11 Nov 2019 19:11:05 -0500

I am highly biased, but I think the idea is fantastic. I will be happy to
participate in this if you guys decide to go ahead...

Of course, to be upfront, one needs to understand that cAE requires some
use of collision-resistant hashing. So, in
terms of current implementations, could be close to an order of magnitude
slower than encrypt-then-MAC or OCB
schemes based on only a block cipher (e.g., AES).

So this might not be for everybody if speed in concerned. But a clear
standard, with appropriate warnings (more secure,
wider applicability, but potentially slower), seems like a great idea.

Yevgeniy

On Mon, Nov 11, 2019 at 6:57 PM Paul Grubbs <[email-masked]> wrote:

> Hello all,
>
> A 'committing' authenticated encryption (cAE) scheme is one for which it
> is hard to find a ciphertext having multiple correct decryption keys.*
> More formally, a cAE scheme's ciphertexts are binding commitments. AE
> security of a scheme does not imply its ciphertexts are binding
> commitments, and widely-used AE schemes like Galois/Counter Mode and
> two-key encrypt-then-MAC are not cAE [1]. This has already led to attacks
> on already-deployed protocols like message franking [2]; cAE is also needed
> in protocols like OPAQUE [3, 4] that may soon be standardized and deployed,
> Though cAE is needed in practice, there is no standards document
> explaining cAE and defining secure schemes. I think such a document would
> be really helpful to researchers and practitioners alike, so I'd like to
> initiate some discussion in the mailing list ahead of the CFRG meeting at
> IETF 106 next week, where hopefully Nick will present a few slides to get
> people thinking about cAE.
>
> [3] OPAQUE draft (
> https://tools.ietf.org/html/draft-krawczyk-cfrg-opaque-03)
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Paul Grubbs <[email-masked]>
Date: Tue, 12 Nov 2019 11:36:12 -0500

Thanks Yevgeniy! Yes, our "Invisible Salamanders" paper shows
collision-resistant hashing is required if one wants commitments to be
small. This doesn't necessarily imply a huge efficiency penalty over what
is currently used, though - for example, Signal's AEAD (CBC-then-HMAC)
already uses collision-resistant hashing. Also, SHA256 instructions are
increasingly available in new CPUs, which will make collision resistance
cheaper still. Without the need for small commitments, cAE can be nearly as
efficient as GCM, but with a different set of tradeoffs.

(Incidentally, these kinds of subtleties are exactly why I think an RFC is
sorely needed!)

On Mon, Nov 11, 2019 at 7:11 PM Yevgeniy Dodis <[email-masked]> wrote:

>> *Some prior work [5] calls this and other similar properties
>> 'robustness'. Since 'robust' is already an overloaded term in cryptography,
>> I prefer 'committing'.
>>