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 <uri@ll.mit.edu>
a écrit :

> 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* <uri@ll.mit.edu>
> Date: sam. 20 juin 2020 à 01:51
> Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
> To: Thomas Peyrin <thomas.peyrin@gmail.com>, Stanislav V. Smyshlyaev <
> smyshsv@gmail.com>
> Cc: CFRG <cfrg@irtf.org>
>
>
>
> Can you provide/compute security bounds for truncated synthetic IV?  Some
> (niche) use cases require it.
>
>
>
> *From: *Cfrg <cfrg-bounces@irtf.org> on behalf of Thomas Peyrin <
> thomas.peyrin@gmail.com>
> *Date: *Friday, June 19, 2020 at 1:47 PM
> *To: *"Stanislav V. Smyshlyaev" <smyshsv@gmail.com>
> *Cc: *CFRG <cfrg@irtf.org>
> *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 <smyshsv@gmail.com
> <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.
>
> 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
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>
>