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

Thomas Peyrin <thomas.peyrin@gmail.com> Wed, 24 June 2020 05:31 UTC

Return-Path: <thomas.peyrin@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 0AD643A0B97 for <cfrg@ietfa.amsl.com>; Tue, 23 Jun 2020 22:31:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.097
X-Spam-Level:
X-Spam-Status: No, score=-2.097 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id VN3faKECWfQJ for <cfrg@ietfa.amsl.com>; Tue, 23 Jun 2020 22:31:21 -0700 (PDT)
Received: from mail-pj1-x102f.google.com (mail-pj1-x102f.google.com [IPv6:2607:f8b0:4864:20::102f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D30933A07FC for <cfrg@irtf.org>; Tue, 23 Jun 2020 22:31:21 -0700 (PDT)
Received: by mail-pj1-x102f.google.com with SMTP id b7so1912560pju.0 for <cfrg@irtf.org>; Tue, 23 Jun 2020 22:31:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=ApFvlW2LDc316eBgL7BJEAv9b2xtmfcfWqkKN+Kt1dE=; b=J70IYbSBHqpr4tFAuK0WRGnoOpKddXckbDxrJy6tTE2rGFLdQnbWQOLAV7CY88fSGL 6c+KNWquEUdPJcbuecV3v4KcxBh2UPVMoA9GgQv3nXZJ9S69+8QQyCivxlFQ+dNrHsaj TR6SWtlb8nM09jCUxCZL1P5LGKPmVxnPJgS9Gd6dxoXRgo161XIslFhj2i5gta7+xJie B+XV/hIz5W3mqDJR5GwBn3naKVV0CB9lB2cpz1TZKDdAy4K31UsiuiBaogvwj34uGhaV wx1ZRYUBs+0fgmwzCryNIV6ZURLWCftTJ11oBNXDqUw1oepuOj8QRv/fChkJE0ET1Wcd O/xA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=ApFvlW2LDc316eBgL7BJEAv9b2xtmfcfWqkKN+Kt1dE=; b=XfT2Tqxm6Y89koI18HkYF0LMfhFPgaoHsU+rYoum60gnwa/RPxDqAPU4l5dJIE1mTI Ll3HoAwD7t+ikV7mNTE0MLNtEMZ2lzfUZ7bzsZlHOq6SeDLBbCNLLzfOYF5vREX/lGD/ CimDRFEeXLtNy39V2qIykng6dTP/RG9EtPLTCGt/XR9l1DzISHlQhCCPjSGfiSQvCkEv GGLotMxA30TqpkwztiFC85xFlCk5wDKbt7ryHvfl/xxw6Ka7zjFldJ7BBHQq5+OnDUBZ oMTvjVzEgVWXga8xTaMxqR2YCRNXdVYdARX1UCcWn2shgfbCNRz7xy6HkTlyWwkNfO+5 is1g==
X-Gm-Message-State: AOAM533YQaJ+DPog+zR/Kjzy/aCJ3rVyhp8OtfbRv3Hov7QnzwC0T2Eu 3IUcTln1+s/7Vc4j2SpEn4pPpjFT6B3wAGbPqFE=
X-Google-Smtp-Source: ABdhPJx2/cfj3Vn3vLtsBIgbTHLH6/nKmS4MU/BtS/MGx6QEc9wp4n0HaCOfgyxtzr2tcGp+rUdFEwczA/nD/2aRYCM=
X-Received: by 2002:a17:90a:2104:: with SMTP id a4mr26216630pje.1.1592976680813; Tue, 23 Jun 2020 22:31:20 -0700 (PDT)
MIME-Version: 1.0
References: <CAMr0u6=QJuG9mshppB6qeryk6qekVKgi9D=WqGoa_L4sNgtYLg@mail.gmail.com> <CAA0wV7TXftZXeteCy3=N_4ezXRTL852_R1kCCPYGFEhQNHGw2Q@mail.gmail.com> <4CFDB50C-6281-4AC8-A9DF-D0F79BF58C5C@ll.mit.edu> <CAA0wV7SjS8OA+QEPN6Dip09Y2Sp5=4WJkTVkRa2O0gnZf_m54w@mail.gmail.com> <924F2899-4D89-4691-80DD-73FD9EDAA520@ll.mit.edu>
In-Reply-To: <924F2899-4D89-4691-80DD-73FD9EDAA520@ll.mit.edu>
From: Thomas Peyrin <thomas.peyrin@gmail.com>
Date: Wed, 24 Jun 2020 13:31:08 +0800
Message-ID: <CAA0wV7Sg=pRt1s5L1NDGxOPoVkOyJFvjHJ32V_SeeS5UNRSzjQ@mail.gmail.com>
To: "Blumenthal, Uri - 0553 - MITLL" <uri@ll.mit.edu>
Cc: "Stanislav V. Smyshlyaev" <smyshsv@gmail.com>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="00000000000032106105a8cdc9f6"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/IYhxo6bS1B-oKjLqz71Rxb5al-I>
Subject: Re: [Cfrg] Do we need a selection contest for AEAD?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 24 Jun 2020 05:31:26 -0000

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>om>, 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
>
>