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

Thomas, thank you!

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

From: Thomas Peyrin <thomas.peyrin@gmail.com>
Date: Wednesday, June 24, 2020 at 01:31
To: Uri Blumenthal <uri@ll.mit.edu>
Cc: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>, CFRG <cfrg@irtf.org>
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 <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> 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

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

Attachment: smime.p7s