Subject: [Cfrg] Do we need a selection contest for AEAD?

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Fri, 19 Jun 2020 20:32:03 +0300

Dear CFRG,

The chairs would like to ask for opinions whether it seems reasonable to
initiate an AEAD mode selection contest in CFRG, to review modern AEAD modes
and recommend a mode (or several modes) for the IETF.

We’ve recently had a CAESAR contest, and, of course, its results have to be
taken into account very seriously. In addition to the properties that were
primarily addressed during the CAESAR contest (like protection against
side-channel attacks, authenticity/limited privacy damage in case of nonce
misuse or release of unverified plaintexts, robustness in such scenarios as
huge amounts of data), the following properties may be especially important
for the usage of AEAD mechanisms in IETF protocols:
1) Leakage resistance.
2) Incremental AEAD.
3) Commitment AEAD (we've had a discussion in the list a while ago).
4) RUP-security (it was discussed in the CAESAR contest, but the finalists
may have some issues with it, as far as I understand).
5) Ability to safely encrypt a larger maximum number of bytes per key
(discussed in QUIC WG).

Does this look reasonable?
Any thoughts about the possible aims of the contest?
Any other requirements for the mode?

Regards,
Stanislav, Alexey, Nick

---

From: Thomas Peyrin <[email-masked]>
Date: Sat, 20 Jun 2020 01:46:50 +0800

Dear all,

I will be actually sending an RFC draft of Deoxys in the coming weeks like
I promised a few months ago (really sorry, with the COVID-19 confining with
young kids at home, I couldn't advance on it). It will contain misuse
resistant mode (with stronger guarantees than AES-GCM-SIV), leakage
resilient mode with different levels of resilience, the possiblity to
encrypt 2^124 bytes per key. We are currently analyzing the INT-RUP
security of it. All this for about the same efficiency as AES-GCM-SIV.

Regards,

Thomas.

Le sam. 20 juin 2020 à 01:32, Stanislav V. Smyshlyaev <[email-masked]> a
écrit :

> We’ve recently had a CAESAR contest, and, of course, its results have to
> be taken into account very seriously. In addition to the properties that
> were primarily addressed during the CAESAR contest (like protection against
> (discussed in QUIC WG)..
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2020 17:51:16 +0000

Can you provide/compute security bounds for truncated synthetic IV?  Some (niche) use cases require it.

From: Cfrg <[email-masked]> on behalf of Thomas Peyrin <[email-masked]>
Date: Friday, June 19, 2020 at 1:47 PM
To: "Stanislav V. Smyshlyaev" <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

Dear all, 

I will be actually sending an RFC draft of Deoxys in the coming weeks like I promised a few months ago (really sorry, with the COVID-19 confining with young kids at home, I couldn't advance on it). It will contain misuse resistant mode (with stronger guarantees than AES-GCM-SIV), leakage resilient mode with different levels of resilience, the possiblity to encrypt 2^124 bytes per key. We are currently analyzing the INT-RUP security of it. All this for about the same efficiency as AES-GCM-SIV.

Regards,

Thomas.

Le sam. 20 juin 2020 à 01:32, Stanislav V. Smyshlyaev <[email-masked]> a écrit :

Dear CFRG,

The chairs would like to ask for opinions whether it seems reasonable to initiate an AEAD mode selection contest in CFRG, to review modern AEAD modes and recommend a mode (or several modes) for the IETF.

We’ve recently had a CAESAR contest, and, of course, its results have to be taken into account very seriously. In addition to the properties that were primarily addressed during the CAESAR contest (like protection against side-channel attacks, authenticity/limited privacy damage in case of nonce misuse or release of unverified plaintexts, robustness in such scenarios as huge amounts of data), the following properties may be especially important for the usage of AEAD mechanisms in IETF protocols:

1) Leakage resistance.
2) Incremental AEAD.
3) Commitment AEAD (we've had a discussion in the list a while ago).
4) RUP-security (it was discussed in the CAESAR contest, but the finalists may have some issues with it, as far as I understand).

5) Ability to safely encrypt a larger maximum number of bytes per key (discussed in QUIC WG)..

Regards,

Stanislav, Alexey, Nick

---

From: Thomas Peyrin <[email-masked]>
Date: Sat, 20 Jun 2020 02:17:07 +0800

Dear Uri,

Yes. We recommend to use a tag size of 128 bits for our mode, but in case a
smaller tag size \tau is required, the security claims will drop according
to \tau.

Regards,

Thomas.

---------- Forwarded message ---------
De : Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Date: sam. 20 juin 2020 à 01:51
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
To: Thomas Peyrin <[email-masked]>, Stanislav V. Smyshlyaev <
[email-masked]>
Cc: CFRG <[email-masked]>

Can you provide/compute security bounds for truncated synthetic IV?  Some
(niche) use cases require it.

*From: *Cfrg <[email-masked]> on behalf of Thomas Peyrin <
[email-masked]>
*Date: *Friday, June 19, 2020 at 1:47 PM
*To: *"Stanislav V. Smyshlyaev" <[email-masked]>
*Cc: *CFRG <[email-masked]>
*Subject: *Re: [Cfrg] Do we need a selection contest for AEAD?

Dear all,

Regards,

Thomas.

Le sam. 20 juin 2020 à 01:32, Stanislav V. Smyshlyaev <[email-masked]
<smyshsv@gmail..com>> a écrit :

Dear CFRG,

The chairs would like to ask for opinions whether it seems reasonable to
initiate an AEAD mode selection contest in CFRG, to review
modern AEAD modes and recommend a mode (or several modes) for the IETF.

1) Leakage resistance.
2) Incremental AEAD.

Regards,

Stanislav, Alexey, Nick

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2020 18:19:35 +0000

Yes. We recommend to use a tag size of 128 bits for our mode, 

Yes I realize that. ;-)

but in case a smaller tag size \tau is required, the security claims will drop according to \tau.

Could you please provide the exact relationship between \tau, number of messages (or encrypted blocks), and, e.g., the probability of collision? I’m looking for the formulas binding those together.

Thanks!

---------- Forwarded message ---------
De : Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Date: sam. 20 juin 2020 à 01:51
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
To: Thomas Peyrin <[email-masked]>, Stanislav V. Smyshlyaev <[email-masked]>
Cc: CFRG <[email-masked]>

Dear all, 

Regards,

Thomas.

Dear CFRG,

1) Leakage resistance.
2) Incremental AEAD.

Regards,

Stanislav, Alexey, Nick

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Fri, 19 Jun 2020 18:29:34 +0000

The other thing of concern is “once you’ve found one forgery, how difficult is it to find another?”  For some AEAD’s (GCM, Poly1305-based), it’s easy; for other AEADs (HMAC-based), it’s not.

From: Cfrg <[email-masked]> On Behalf Of Blumenthal, Uri - 0553 - MITLL
Sent: Friday, June 19, 2020 2:20 PM
To: Thomas Peyrin <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

Yes I realize that. ;-)

Thanks!

---------- Forwarded message ---------
De : Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>>
Date: sam. 20 juin 2020 à 01:51
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
To: Thomas Peyrin <[email-masked]<mailto:[email-masked]>>, Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>>
Cc: CFRG <[email-masked]<mailto:[email-masked]>>

From: Cfrg <[email-masked]<mailto:[email-masked]>> on behalf of Thomas Peyrin <[email-masked]<mailto:[email-masked]>>
Date: Friday, June 19, 2020 at 1:47 PM
To: "Stanislav V. Smyshlyaev" <[email-masked]<mailto:[email-masked]>>
Cc: CFRG <[email-masked]<mailto:[email-masked]>>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

Dear all,

Regards,

Thomas.

Le sam. 20 juin 2020 à 01:32, Stanislav V. Smyshlyaev <[email-masked]<mailto:smyshsv@gmail..com>> a écrit :
Dear CFRG,

[email-masked]<mailto:[email-masked]>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 19 Jun 2020 18:34:04 +0000

True. Thankfully, not in my use case – but of interest in general. 

Though, the cost of doing HMAC on each and every operation may (at least in some use cases) outweigh the risk of having subsequent forgeries “easy”. Of course, it would be nice to have a quantitative expression of that “ease”.

TNX!

Yes I realize that. ;-)

Thanks!

---------- Forwarded message ---------
De : Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Date: sam. 20 juin 2020 à 01:51
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
To: Thomas Peyrin <[email-masked]>, Stanislav V. Smyshlyaev <[email-masked]>
Cc: CFRG <[email-masked]>

Dear all, 

Regards,

Thomas.

Dear CFRG,

1) Leakage resistance.
2) Incremental AEAD.

Regards,

Stanislav, Alexey, Nick

---

From: Mihir Bellare <[email-masked]>
Date: Fri, 19 Jun 2020 12:11:40 -0700

With regard to requirements for the mode, I would suggest to also consider
adding nonce hiding.

AEAD is understood as providing message privacy for any choices of nonces,
as long as they don't repeat. (Ignoring the nonce-misuse aspect, which is
orthogonal to what follows.) But, as pointed out in [BNT19]
<https://eprint.iacr.org/2019/624>, this isn't really true. There are
choices of non-repeating nonces that, if transmitted with the ciphertext as
necessary to allow decryption, compromise message privacy. This does not
contradict the AEAD definition, because the syntax of the latter gives the
decryptor the nonce and leaves the implementer to ensure it gets there.
Nonce hiding AE (which has a modified syntax and security definition, as
per the above paper) fills this gap.

This problem does not arise with random nonces. But the promise of AEAD was
to provide privacy with arbitrary nonces. A standard should either do this
fully (nonce hiding) or come with restrictions to only use, say, random
nonces.

Nonce hiding is also of interest for anonymity and meta-data privacy. With
regular AEAD, nonces that are sequence numbers can (if visible to the
adversary) reveal information, as pointed out by Bernstein
<https://groups.google.com/g/crypto-competitions/c/n5ECGwYr6Vk/m/bsEfPWqSAU4J>
and
CHAE <https://chae.cr.yp.to/whitepaper.html>. This is prevented in part by
nonce hiding.

For such reasons, nonce hiding is targeted in the AE mode of QUIC.

Mihir

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 19 Jun 2020 14:31:29 -0700

On Fri, Jun 19, 2020 at 12:12 PM Mihir Bellare <[email-masked]> wrote:

> This problem does not arise with random nonces. But the promise of AEAD
> was to provide privacy with arbitrary nonces. A standard should either do
> this fully (nonce hiding) or come with restrictions to only use, say,
> random nonces.
>
> <https://groups.google.com/g/crypto-competitions/c/n5ECGwYr6Vk/m/bsEfPWqSAU4J> and
> CHAE <https://chae.cr.yp.to/whitepaper.html>. This is prevented in part
> by nonce hiding.
>

Mihir,

Thanks for flagging this. As you imply here, QUIC has a very ad hoc nonce
hiding construction, in part because we didn't have a well-studied common
construction to fall back on.

-Ekr

---

From: Daniel Franke <[email-masked]>
Date: Fri, 19 Jun 2020 17:48:06 -0400

> CHAE <https://chae.cr.yp.to/whitepaper.html>. This is prevented in part

 This was, indeed, quite the inconvenience when we were designing Network
Time Security. We had to mandate random nonces in order to satisfy our
privacy goals, and then we had to choose AES-SIV as the MTI AEAD algorithm
because random 12-byte nonces generated in response to replayable requests
lead to a non-negligible risk of collision. A standard for nonce hiding
would have been very useful to us.

---

From: Wasa Bee <[email-masked]>
Date: Sun, 21 Jun 2020 11:24:44 -0700

The holy-grail would be an AEAD that can be implemented with resistance 
against power/EM side channels for embedded systems. In addition, 
embedded systems sometimes have no prng - a symmetric key is embedded at 
manufacture time and all communication make use of a stream cipher with 
a counter as nonce.

On 19/06/2020 14:48, Daniel Franke wrote:
> On Fri, Jun 19, 2020 at 3:13 PM Mihir Bellare <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
> 
>     With regard to requirements for the mode, I would suggest to also
>     consider adding nonce hiding.
> 
>     AEAD is understood as providing message privacy for any choices of
>     nonces, as long as they don't repeat. (Ignoring the nonce-misuse
>     aspect, which is orthogonal to what follows.) But, as pointed out in
>     [BNT19] <https://eprint.iacr.org/2019/624>, this isn't really true.
>     There are choices of non-repeating nonces that, if transmitted with
>     the ciphertext as necessary to allow decryption, compromise message
>     privacy. This does not contradict the AEAD definition, because the
>     syntax of the latter gives the decryptor the nonce and leaves the
>     implementer to ensure it gets there. Nonce hiding AE (which has a
>     modified syntax and security definition, as per the above paper)
>     fills this gap.
> 
>     This problem does not arise with random nonces. But the promise of
>     AEAD was to provide privacy with arbitrary nonces. A standard should
>     either do this fully (nonce hiding) or come with restrictions to
>     only use, say, random nonces.
> 
>     Nonce hiding is also of interest for anonymity and meta-data
>     privacy. With regular AEAD, nonces that are sequence numbers can (if
>     visible to the adversary) reveal information, as pointed out by
>     Bernstein
>     CHAE <https://chae.cr.yp.to/whitepaper.html>. This is prevented in
>     part by nonce hiding. 
> 
> 
>   This was, indeed, quite the inconvenience when we were designing 
> Network Time Security. We had to mandate random nonces in order to 
> satisfy our privacy goals, and then we had to choose AES-SIV as the MTI 
> AEAD algorithm because random 12-byte nonces generated in response to 
> replayable requests lead to a non-negligible risk of collision. A 
> standard for nonce hiding would have been very useful to us.
>

---

From: "Martin Thomson" <[email-masked]>
Date: Mon, 22 Jun 2020 11:40:10 +1000

> 5) Ability to safely encrypt a larger maximum number of bytes per key 

I might suggest expanding this a little to include better bounds for attacker advantage in both single-user and multi-user settings.  We're digging into the mu analysis of AES-GCM and finding that the bounds aren't entirely satisfactory under some sets of assumptions.  In part, that demonstrates some lack in the research into the properties of the AEAD.  But it does show some of the limitations of the ciphers themselves.

To give a concrete example, the mu analysis of AES-GCM in https://eprint.iacr.org/2018/993.pdf ends up being dominated by a term that places the total number of blocks encrypted against the block size (\sigma.B/2^n in Equation (1) from the same paper, which - if you consider \sigma to be largely inflexible as I do - might be better restated as \sigma^2/u/2^n where u is the number of users or distinct keys).  Some back of the envelope calculations show that a \sigma of 2^70 is almost plausible, which means that the distribution of usage across large numbers of keys is the only real safeguard remaining.

This isn't cause for immediate concern, partly because I think that the threat model implied by the analysis isn't totally realistic.  However, it demonstrates how we have less headroom in these ciphers than might be immediately obvious.  AES has an option for larger keys, which helps in some cases, but it doesn't come with a larger block size.  The huge amount of use this cipher gets means that we probably need to pay attention to this when it comes to selecting a potential successor.

---

From: Thomas Peyrin <[email-masked]>
Date: Wed, 24 Jun 2020 13:31:08 +0800

Dear Uri,

I am planning to propose 3 different AEAD modes to be used with the Deoxys
tweakable block cipher:
- one very simple, very efficient online beyond birthday bound single-pass
mode (aka Deoxys-I, extremely similar to TAE or \ThetaCB3). To compete with
AES-GCM which does not provide beyond birthday bound and is slower.
- one efficient beyond birthday bound misuse-resistant two-pass mode (aka
Deoxys-II, somehow similar to SIV). To compete with AES-GCM-SIV, which has
weaker nonce-respecting and nonce-misuse security guarantees for the same
performances.
- one very high-security full leakage resilient mode with strong multi-user
security (aka TEDT mode https://eprint.iacr.org/2019/137.pdf)

Note that all these modes will be able to cipher up to 2^128 data and the
tag can be truncated. For Deoxys-II, the bounds are basically the NSIV
composition (https://eprint.iacr.org/2015/1049) of the Nonce-as-Tweak (NaT)
PRF construction (https://tosc.iacr.org/index.php/ToSC/article/view/637/605)
and the nonce and IV-based encryption scheme CTRT (
https://eprint.iacr.org/2015/1049). In short, the terms of the security
bound are:   (3\mu-2)q / 2^n   +  q/(2^n - \mu)  +   2(\mu - 1) \rho /
2^(t-4)  +  \rho^2 / 2^(n+t-3)
where n is the block size (128 in our case), t is the tweak size (128 in
our case), q is the number of oracle queries, \rho is the total number of
128-bit blocks queried, \mu is the maximum number of times a nonce can be
reused. If the tag is truncated to s bits, the terms will become
essentially:
(3\mu-2)q / 2^s   +  q 2^{n-s} / (2^n - \mu)   +  2(\mu - 1) \rho / 2^s  +
 \rho^2 / 2^(n+s-1)

For nonce-hiding, I wonder if/how the constructions in
https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes
optionally.

Regards,

Thomas.

Le sam. 20 juin 2020 à 02:19, Blumenthal, Uri - 0553 - MITLL <[email-masked]>
a écrit :

> Could you please provide the *exact* relationship between \tau, number of
> messages (or encrypted blocks), and, e.g., the probability of collision?
> I’m looking for the formulas binding those together.
>
>
>
> Thanks!
>
>
>
>
>
> De : *Blumenthal, Uri - 0553 - MITLL* <[email-masked]>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 24 Jun 2020 13:06:34 +0000

Thomas, thank you!

(I’ll ask if/when I have more questions.)

From: Thomas Peyrin <[email-masked]>
Date: Wednesday, June 24, 2020 at 01:31
To: Uri Blumenthal <[email-masked]>
Cc: "Stanislav V. Smyshlyaev" <[email-masked]>, CFRG <[email-masked]>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

Dear Uri, 

I am planning to propose 3 different AEAD modes to be used with the Deoxys tweakable block cipher:

- one very simple, very efficient online beyond birthday bound single-pass mode (aka Deoxys-I, extremely similar to TAE or \ThetaCB3). To compete with AES-GCM which does not provide beyond birthday bound and is slower. 

- one efficient beyond birthday bound misuse-resistant two-pass mode (aka Deoxys-II, somehow similar to SIV). To compete with AES-GCM-SIV, which has weaker nonce-respecting and nonce-misuse security guarantees for the same performances. 

- one very high-security full leakage resilient mode with strong multi-user security (aka TEDT mode https://eprint.iacr.org/2019/137.pdf)

Note that all these modes will be able to cipher up to 2^128 data and the tag can be truncated. For Deoxys-II, the bounds are basically the NSIV composition (https://eprint.iacr.org/2015/1049) of the Nonce-as-Tweak (NaT) PRF construction (https://tosc.iacr.org/index.php/ToSC/article/view/637/605) and the nonce and IV-based encryption scheme CTRT (https://eprint.iacr.org/2015/1049). In short, the terms of the security bound are:   (3\mu-2)q / 2^n   +  q/(2^n - \mu)  +   2(\mu - 1) \rho / 2^(t-4)  +  \rho^2 / 2^(n+t-3)

where n is the block size (128 in our case), t is the tweak size (128 in our case), q is the number of oracle queries, \rho is the total number of 128-bit blocks queried, \mu is the maximum number of times a nonce can be reused. If the tag is truncated to s bits, the terms will become essentially:

(3\mu-2)q / 2^s   +  q 2^{n-s} / (2^n - \mu)   +  2(\mu - 1) \rho / 2^s  +  \rho^2 / 2^(n+s-1) 

For nonce-hiding, I wonder if/how the constructions in https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes optionally.   

Regards,

Thomas.

Le sam. 20 juin 2020 à 02:19, Blumenthal, Uri - 0553 - MITLL <[email-masked]> a écrit :

Yes I realize that. ;-)

Thanks!

---------- Forwarded message ---------
De : Blumenthal, Uri - 0553 - MITLL <[email-masked]>
Date: sam. 20 juin 2020 à 01:51
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
To: Thomas Peyrin <[email-masked]>, Stanislav V. Smyshlyaev <[email-masked]>
Cc: CFRG <[email-masked]>

Dear all, 

Regards,

Thomas.

Dear CFRG,

1) Leakage resistance.
2) Incremental AEAD.

Regards,

Stanislav, Alexey, Nick

---

From: Paul Grubbs <[email-masked]>
Date: Wed, 24 Jun 2020 12:34:30 -0400

I think an AEAD competition is a great idea. Recently I've been studying
the AEAD landscape, and there seem to be a lot of gaps between the needs of
applications/protocols and the properties widely-used schemes provide. To
address this and get a sense of which needs are most pressing, it might be
good to have the first round be more of a "meta-competition" for discussing
and prioritizing requirements and use cases. The result of this would be an
(ideally small) list of well-defined design targets, for which people can
propose schemes in subsequent rounds.

I'd also like to suggest another use case for AEAD: ZK-friendly AEAD modes.
These modes would be compatible with efficient ZK proof systems and would
make it easy to prove properties of plaintexts in zero knowledge.

---

From: Yevgeniy Dodis <[email-masked]>
Date: Wed, 24 Jun 2020 13:09:08 -0400

I support Paul's idea. I feel AEAD landscape is getting a bit out of
hand, even despite the CEASAR competition.
Would be good to bring back more structure and understanding, so when
people in the industry need an AEAD scheme,
they have a clear guide what to choose from. Whether this is
committing, remotely-keyed, ZK-friendly, lightweight,
side-channel-resistant, nonce-misuse resistant, nonce-hiding,
beyond-birthday, etc.

On Wed, Jun 24, 2020 at 12:34 PM Paul Grubbs <[email-masked]> wrote:
>
> I think an AEAD competition is a great idea. Recently I've been studying the AEAD landscape, and there seem to be a lot of gaps between the needs of applications/protocols and the properties widely-used schemes provide. To address this and get a sense of which needs are most pressing, it might be good to have the first round be more of a "meta-competition" for discussing and prioritizing requirements and use cases. The result of this would be an (ideally small) list of well-defined design targets, for which people can propose schemes in subsequent rounds.
>
> I'd also like to suggest another use case for AEAD: ZK-friendly AEAD modes. These modes would be compatible with efficient ZK proof systems and would make it easy to prove properties of plaintexts in zero knowledge.
>
> On Fri, Jun 19, 2020 at 1:32 PM Stanislav V. Smyshlyaev <[email-masked]> wrote:
>>
>> Dear CFRG,
>>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 24 Jun 2020 17:14:12 +0000

I don't support that idea, because different use cases require different "optimizations". My use case doesn't care for nonce hiding, but cares very much for performance, and for the ability to have defined security bounds for truncated synthetic IV. 

There is no "one size fits all", or "one champion fits all". Even CAESAR results may not be granular enough (several categories, with a winner in each one).

Or are you planning to have a *separate* competition for *each* of those listed below: 

On 6/24/20, 13:09, "Cfrg on behalf of Yevgeniy Dodis" <[email-masked] on behalf of [email-masked]> wrote:

---

From: Mridul Nandi <[email-masked]>
Date: Wed, 24 Jun 2020 23:04:45 +0530

Dear all,

I think we are lacking formal added security requirements of AEAD.
Beyond the classical definition of AEAD, it would be really interesting if
we can list the additional features in a more formal way..   So I like the
idea of "meta-competition" for discussing and prioritizing requirements and
use cases.  After looking at the outcome of the discussion we may decide
whether a competition is indeed helpful or not.  Even if we decide not to
proceed with a competition, the community can try to design satisfying
certain features discussed in that meta-competition..  This would at least
help to understand which features are meaningful and how/where it is
meaningful to pursue further research in this direction.

Thanks and regards,
Mridul Nandi
Associate Professor
Indian Statistical Institute
Kolkata

On Wed, Jun 24, 2020 at 10:44 PM Blumenthal, Uri - 0553 - MITLL <
[email-masked]> wrote:

> I don't support that idea, because different use cases require different
> "optimizations". My use case doesn't care for nonce hiding, but cares very
> much for performance, and for the ability to have defined security bounds
> for truncated synthetic IV.
>
> There is no "one size fits all", or "one champion fits all". Even CAESAR
> results may not be granular enough (several categories, with a winner in
> each one).
>
> On 6/24/20, 13:09, "Cfrg on behalf of Yevgeniy Dodis" <cfrg-bounces@irtf..org
> on behalf of [email-masked]> wrote:
>
>     > I think an AEAD competition is a great idea. Recently I've been
> studying the AEAD landscape, and there seem to be a lot of gaps between the
> needs of applications/protocols and the properties widely-used schemes
> provide. To address this and get a sense of which needs are most pressing,
> it might be good to have the first round be more of a "meta-competition"
> for discussing and prioritizing requirements and use cases. The result of
> this would be an (ideally small) list of well-defined design targets, for
> which people can propose schemes in subsequent rounds.
>     >
>     > I'd also like to suggest another use case for AEAD: ZK-friendly AEAD
> modes. These modes would be compatible with efficient ZK proof systems and
> would make it easy to prove properties of plaintexts in zero knowledge.
>     >
>     >> The chairs would like to ask for opinions whether it seems
> reasonable to initiate an AEAD mode selection contest in CFRG, to review
>     >> We’ve recently had a CAESAR contest, and, of course, its results
> have to be taken into account very seriously. In addition to the properties
> that were primarily addressed during the CAESAR contest (like protection
> against side-channel attacks, authenticity/limited privacy damage in case
> of nonce misuse or release of unverified plaintexts, robustness in such
> scenarios as huge amounts of data), the following properties may be
> especially important for the usage of AEAD mechanisms in IETF protocols:
>     >> 1) Leakage resistance.
>     >> 2) Incremental AEAD.
>     >> 4) RUP-security (it was discussed in the CAESAR contest, but the
> finalists may have some issues with it, as far as I understand).

---

From: Thomas Peyrin <[email-masked]>
Date: Thu, 25 Jun 2020 01:53:06 +0800

As a co-designer of Deoxys, my view is obviously biased here. I think a
competition will only be successful if we have people submitting schemes
(that's very easy) and much more importantly people analyzing them (that's
very hard). Are we sure that we currently have the manpower and enough
incentives to bring researchers around the world to work on that ?

I speak as a researcher that worked on designing schemes and trying to
break others during competitions. Cryptanalysis is a very very unrewarding
task: if you work a lot and eventually manage to break a crypto competition
design (lucky situation), you will actually get a paper and it will never
be cited (the design is dead). Most of the time, you spend weeks/months
trying to break a design and nothing comes out, and sometimes it really
feels like you wasted your time. My point is that cryptanalysis work is the
most valuable asset here, and I don't think we should ditch all the
cryptanalysis work that was provided during the CAESAR competition. First,
because it would be a waste, and secondly because it would send quite a
negative message to all people actually doing the cryptanalysis work. Why
would I spend time on breaking designs if in the end the competition
results are kind of ignored?

As a side point, CAESAR was organized generally by the symmetric-key crypto
community and was already focusing on just 3 use-cases. Even with that, I
would say in general it didn't get the traction that everyone hoped for. I
fear that with a competition with many targets, this will get even worse.
Perhaps a way to go would be to check what use-cases are already handled by
existing designs (I think most of them already have a satisfactory scheme)
and do specialized competitions for more recent and more exotic security
notions ? This would focus the manpower where it is actually needed.

Regards,

Thomas.

---

From: Mihir Bellare <[email-masked]>
Date: Wed, 24 Jun 2020 11:43:52 -0700

> for discussing and prioritizing requirements and use cases.
>

Responding here both to the above and to Thomas's post about Deoxys. I
think we need to step back to consider that what we call AEAD is not
providing the message privacy that we think it is, and how that affects
standardization.

RFC 5116 <https://tools.ietf.org/html/rfc5116> says:  "there is no need to
coordinate the details of the nonce format between the encrypter and the
decrypter, as long the entire nonce is sent or stored with the ciphertext
and is thus available to the decrypter ... the nonce MAY be stored or
transported with the ciphertext ... "

What [BNT19] <https://eprint.iacr.org/2019/624.pdf> points out is that if
you send the nonce with the ciphertext, for certain choices of nonces, you
can compromise privacy of the message. This is kind of obvious in
retrospect; the nonce can be message dependent. The difficulty is that in
AEAD (which we call AE1), the nonce is assumed magically provided to the
decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19]
<https://eprint.iacr.org/2019/624.pdf> defines a stronger AE2 goal which
does what AEAD seems to have been understood to do, namely provide message
privacy for any (non-repeating) choice of nonces, even if they are
transmitted. This is done via nonce hiding, so the latter is not just about
hiding the nonce itself (which is an added benefit) but, even before that,
about hiding the message when nonces are visible.

Message-dependent nonces are not a likely choice, but they are allowed
under RFC 5116. If one continues to use AEAD, I think in future standards,
language as used in RFC 5116 should be changed to say that it is only with
nonces that do not depend on the message (like random numbers or sequence
numbers) or nonces that are not transmitted. But it is a burden for
implementers to have to figure out if their nonces are conforming. With
AE2, they don't need to; any (non-repeating) nonce choices, even message
dependent, are fine.

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <[email-masked]>
wrote:
For nonce-hiding, I wonder if/how the constructions in
https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes
optionally.

As above, it isn't just for nonce hiding that one would want to apply the
above; it is to have message privacy even for transmitted nonces, meaning
what AEAD was thought to provide. I think the goal for Deoxys and future AE
schemes should be AE2 for this reason.

 As to the methods, yes, one could use them to get AE2. But the bounds
mostly admit a birthday term. You seem to have worked to get good bounds
for Deoxys, so perhaps one could find a direct way to get AE2 for Deoxys
without sacrificing something in the bounds?

Mihir

<https://tools.ietf.org/html/rfc5116>

<https://tools.ietf.org/html/rfc5116>

<https://tools.ietf.org/html/rfc5116>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Wed, 24 Jun 2020 19:00:19 +0000

As I said, some of us do not need nonce hiding, and do not want to pay the performance/complexity price for having it.

From: Cfrg <[email-masked]> on behalf of Mihir Bellare <[email-masked]>
Date: Wednesday, June 24, 2020 at 14:45
To: Paul Grubbs <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?

it might be good to have the first round be more of a "meta-competition" for discussing and prioritizing requirements and use cases.

Responding here both to the above and to Thomas's post about Deoxys. I think we need to step back to consider that what we call AEAD is not providing the message privacy that we think it is, and how that affects standardization. 

RFC 5116 says:  "there is no need to coordinate the details of the nonce format between the encrypter and the decrypter, as long the entire nonce is sent or stored with the ciphertext and is thus available to the decrypter ... the nonce MAY be stored or transported with the ciphertext ... "

What [BNT19] points out is that if you send the nonce with the ciphertext, for certain choices of nonces, you can compromise privacy of the message. This is kind of obvious in retrospect; the nonce can be message dependent. The difficulty is that in AEAD (which we call AE1), the nonce is assumed magically provided to the decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19] defines a stronger AE2 goal which does what AEAD seems to have been understood to do, namely provide message privacy for any (non-repeating) choice of nonces, even if they are transmitted. This is done via nonce hiding, so the latter is not just about hiding the nonce itself (which is an added benefit) but, even before that, about hiding the message when nonces are visible. 

Message-dependent nonces are not a likely choice, but they are allowed under RFC 5116. If one continues to use AEAD, I think in future standards, language as used in RFC 5116 should be changed to say that it is only with nonces that do not depend on the message (like random numbers or sequence numbers) or nonces that are not transmitted. But it is a burden for implementers to have to figure out if their nonces are conforming. With AE2, they don't need to; any (non-repeating) nonce choices, even message dependent, are fine.

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <[email-masked]> wrote:

As above, it isn't just for nonce hiding that one would want to apply the above; it is to have message privacy even for transmitted nonces, meaning what AEAD was thought to provide. I think the goal for Deoxys and future AE schemes should be AE2 for this reason. 

 As to the methods, yes, one could use them to get AE2. But the bounds mostly admit a birthday term. You seem to have worked to get good bounds for Deoxys, so perhaps one could find a direct way to get AE2 for Deoxys without sacrificing something in the bounds?

Mihir

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 30 Jun 2020 23:33:09 +0000

Hi Stanislav, Alexey, and Nick,

It would be great for CFRG to review modern AEAD modes and their properties, but instead of holding a contest at this time, I suggest focusing on the applicability of these properties to IETF protocols.  It would be valuable for the community to get to a better understanding of which properties have the most applications, and which are niceties and which are nececessities. In the same vein, having a deeper understanding about the scenarios that have led to security failures in the field would help to motivate properties like robustness and leakage resilience.  So I suggest having a call for presentations and documents that includes these broader topics around AEAD.  If nothing else, it could be a prelude to a contest.

The list of properties below is a great start; nonce hiding and resistance to multiple forgery attacks are also worth considering (and have been raised by others I believe).

Regards,

David

> On Jun 19, 2020, at 1:32 PM, Stanislav V. Smyshlyaev <[email-masked]> wrote:
> 
> Dear CFRG,
>

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 30 Jun 2020 23:41:01 +0000

Hi Mihir,

Please see inline:

On Jun 24, 2020, at 2:43 PM, Mihir Bellare <[email-masked]<mailto:[email-masked]>> wrote:

RFC 5116<https://tools.ietf.org/html/rfc5116> says:  "there is no need to coordinate the details of the nonce format between the encrypter and the decrypter, as long the entire nonce is sent or stored with the ciphertext and is thus available to the decrypter ... the nonce MAY be stored or transported with the ciphertext ... "

What [BNT19]<https://eprint.iacr.org/2019/624.pdf> points out is that if you send the nonce with the ciphertext, for certain choices of nonces, you can compromise privacy of the message. This is kind of obvious in retrospect; the nonce can be message dependent. The difficulty is that in AEAD (which we call AE1), the nonce is assumed magically provided to the decryptor; the AEAD model does not say it is safe to transmit it.  [BNT19]<https://eprint.iacr.org/2019/624.pdf> defines a stronger AE2 goal which does what AEAD seems to have been understood to do, namely provide message privacy for any (non-repeating) choice of nonces, even if they are transmitted. This is done via nonce hiding, so the latter is not just about hiding the nonce itself (which is an added benefit) but, even before that, about hiding the message when nonces are visible.

I agree that RFC 5116 would benefit from the addition of the caveat that you suggest, but I do not see how it is a burden for implementers to determine if their nonces are conforming.  For the sake of completeness, I suppose that the RFC should also tell implementers that nonces should not be key-dependent.

regards,

David

On Tue, Jun 23, 2020 at 10:31 PM Thomas Peyrin <[email-masked]<mailto:[email-masked]>> wrote:
For nonce-hiding, I wonder if/how the constructions in https://eprint.iacr.org/2019/624.pdf could be applied on top of these modes optionally.

Mihir

---

From: "David McGrew (mcgrew)" <[email-masked]>
Date: Tue, 30 Jun 2020 23:42:00 +0000

Hi Mridul,

+1 to the meta-competition.   I like the name :-)

David

On Jun 24, 2020, at 1:34 PM, Mridul Nandi <[email-masked]<mailto:[email-masked]>> wrote:

Dear all,

I think we are lacking formal added security requirements of AEAD. Beyond the classical definition of AEAD, it would be really interesting if we can list the additional features in a more formal way..   So I like the idea of "meta-competition" for discussing and prioritizing requirements and use cases.  After looking at the outcome of the discussion we may decide whether a competition is indeed helpful or not.  Even if we decide not to proceed with a competition, the community can try to design satisfying certain features discussed in that meta-competition..  This would at least help to understand which features are meaningful and how/where it is meaningful to pursue further research in this direction.

Thanks and regards,
Mridul Nandi
Associate Professor

On Wed, Jun 24, 2020 at 10:44 PM Blumenthal, Uri - 0553 - MITLL <[email-masked]<mailto:[email-masked]>> wrote:
I don't support that idea, because different use cases require different "optimizations". My use case doesn't care for nonce hiding, but cares very much for performance, and for the ability to have defined security bounds for truncated synthetic IV.

On 6/24/20, 13:09, "Cfrg on behalf of Yevgeniy Dodis" <cfrg-bounces@irtf..org on behalf of [email-masked]<mailto:[email-masked]>> wrote:

    On Wed, Jun 24, 2020 at 12:34 PM Paul Grubbs <[email-masked]<mailto:[email-masked]>> wrote:
    >
    > I think an AEAD competition is a great idea. Recently I've been studying the AEAD landscape, and there seem to be a lot of gaps between the needs of applications/protocols and the properties widely-used schemes provide. To address this and get a sense of which needs are most pressing, it might be good to have the first round be more of a "meta-competition" for discussing and prioritizing requirements and use cases.. The result of this would be an (ideally small) list of well-defined design targets, for which people can propose schemes in subsequent rounds.
    >
    > On Fri, Jun 19, 2020 at 1:32 PM Stanislav V. Smyshlyaev <[email-masked]<mailto:[email-masked]>> wrote:
    >>
    >> Dear CFRG,
    >>
    >> The chairs would like to ask for opinions whether it seems reasonable to initiate an AEAD mode selection contest in CFRG, to review modern AEAD modes and recommend a mode (or several modes) for the IETF..
    >>