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

"Blumenthal, Uri - 0553 - MITLL" <> Wed, 24 June 2020 13:06 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 747A33A0DD2 for <>; Wed, 24 Jun 2020 06:06:42 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.894
X-Spam-Status: No, score=-1.894 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=0.001, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id PL7SjitcELVW for <>; Wed, 24 Jun 2020 06:06:40 -0700 (PDT)
Received: from (LLMX2.LL.MIT.EDU []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E61523A0DCE for <>; Wed, 24 Jun 2020 06:06:39 -0700 (PDT)
Received: from ( by (unknown) with ESMTPS id 05OD6ZuG021328; Wed, 24 Jun 2020 09:06:35 -0400
From: "Blumenthal, Uri - 0553 - MITLL" <>
To: Thomas Peyrin <>
CC: "Stanislav V. Smyshlyaev" <>, CFRG <>
Thread-Topic: [Cfrg] Do we need a selection contest for AEAD?
Thread-Index: AQHWRl+/a1yZqWKXrUWtt9h91T1RYajgeYcA//++LgCAAEpIgP//vaEAgAdIAwCAADwwgA==
Date: Wed, 24 Jun 2020 13:06:34 +0000
Message-ID: <>
References: <> <> <> <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach: yes
user-agent: Microsoft-MacOutlook/16.37.20051002
x-originating-ip: []
Content-Type: multipart/signed; protocol="application/pkcs7-signature"; micalg=sha256; boundary="B_3675834394_145657971"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.216, 18.0.687 definitions=2020-06-24_07:2020-06-24, 2020-06-24 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-2004280000 definitions=main-2006240095
Archived-At: <>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 24 Jun 2020 13:06:42 -0000

Thomas, thank you!


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


From: Thomas Peyrin <>
Date: Wednesday, June 24, 2020 at 01:31
To: Uri Blumenthal <>
Cc: "Stanislav V. Smyshlyaev" <>om>, CFRG <>
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


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 ( of the Nonce-as-Tweak (NaT) PRF construction ( and the nonce and IV-based encryption scheme CTRT ( 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 could be applied on top of these modes optionally.   







Le sam. 20 juin 2020 à 02:19, Blumenthal, Uri - 0553 - MITLL <> 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.





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


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


From: Cfrg <> on behalf of Thomas Peyrin <>
Date: Friday, June 19, 2020 at 1:47 PM
To: "Stanislav V. Smyshlyaev" <>
Cc: CFRG <>
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.







Le sam. 20 juin 2020 à 01:32, Stanislav V. Smyshlyaev <> 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?


Stanislav, Alexey, Nick

Cfrg mailing list