[Cfrg] Deoxys-II for AEAD

Thomas Peyrin <thomas.peyrin@gmail.com> Thu, 21 November 2019 17:10 UTC

Return-Path: <thomas.peyrin@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id D75CB120169 for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 09:10:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, 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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 72Dw1xzJSWRE for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 09:10:53 -0800 (PST)
Received: from mail-oi1-x231.google.com (mail-oi1-x231.google.com [IPv6:2607:f8b0:4864:20::231]) (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 E1D12120096 for <cfrg@irtf.org>; Thu, 21 Nov 2019 09:10:52 -0800 (PST)
Received: by mail-oi1-x231.google.com with SMTP id e9so3853118oif.8 for <cfrg@irtf.org>; Thu, 21 Nov 2019 09:10:52 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=OK2YPwrySE4MWpd8s3PdBH8ivCLLIYh4Ybmw/9gddd4=; b=CzkznXO78AnSeWIDWGd9TtbqS6hCY6wngJtsuNTxFbpN/UHhqCDRzu8awnLAahLw+X Rq55O0ZLiTurq8NBiJ9dTmhDBNJdQzdp0sCvZU1yuaxn2NBR/+DYmXEcttJfnj2iu07E l6rQlDqXrstenN+jcWFI60gOSxQpMS7r7R2KVX5cMh9ZO8LlyY5vfHrtfU02NUtrILp1 Jsov6KUQGaqH1CNbFybwQpb9JMhqNTFey4Dx2yYRgKBT7AFu9UcNOF922NNaEcnkM/eZ 8F/5Jc11D1DKevb3ZjBVE5s42YT3Rdn5pslurzUE9vakINQInAVXYCgjYbszT16gVgSA 6VBw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=OK2YPwrySE4MWpd8s3PdBH8ivCLLIYh4Ybmw/9gddd4=; b=ZG0Iwy3mEZHF1nV2gPseWN3qkqzZQt1TcqZSYzjdJMQRQ3kJJdbwVEY5gEbVGEAty4 BwYR/Q/JtonfVqkIDZh3ecbyZENqJVxOJyK8g11cLqALGAE4xysB7wrYgc+K8cyxDFzb HkEW+m+b+yiMubFVvkKi6M8DYgVBCIBwZBD3ejcgm536pj9FFRVJ1nJca/UyTU40Jm+y 0lNt178OCMDw8ILqOrDf/waP0naYIZUfOi7btV/1bvu19JRkt/Pp06w5ebG8uV/xmuqW SYJ/BmBEPEbDflvA+Xr4+C6/OPO6+g/KWhyRQY0RQ7fkzy024FXWo0jFCEya7sjgDNJP HyfQ==
X-Gm-Message-State: APjAAAUhQtj2zxkcsmUs3pXKcpIygTHWvhiy54Dhkl7kNJmisbPsr/2c x0OGkcLaL025ylIsPk3QIBL8YSYIHMbHYYCphpw1DeWRLew=
X-Google-Smtp-Source: APXvYqzdjZhtek4vI7cEDCMBCyrnSyBZ7C6ThrI8xEIdJktBGkuXQNpTdzC2Fls++1l5ypSjJCsFWEEuT06emMXcSUc=
X-Received: by 2002:aca:cc10:: with SMTP id c16mr8896899oig.85.1574356251709; Thu, 21 Nov 2019 09:10:51 -0800 (PST)
MIME-Version: 1.0
From: Thomas Peyrin <thomas.peyrin@gmail.com>
Date: Fri, 22 Nov 2019 01:10:40 +0800
Message-ID: <CAA0wV7R9rUeNtoRko2pTKM_zRWnyQjzyA34+pCq_XJUS6iHC7A@mail.gmail.com>
To: cfrg@irtf.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/-BqD0HFtL40hyWvJAxlklEjVwFY>
Subject: [Cfrg] Deoxys-II 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: Thu, 21 Nov 2019 17:10:55 -0000

Dear all,

Following my presentation at yesterday’s CFRG meeting, we would like
to propose Deoxys-II for consideration at IRTF. Deoxys-II is the
winner of the CAESAR competition for Authenticated Encryption
(portfolio “defense in depth”) that terminated a few months ago after
a 5-year process that went through several rounds of selection

Deoxys-II is a nonce-misuse resistant beyond-birthday AEAD
(Authenticated Encryption with Associated Data) scheme, with two
versions: 128-bit key and 256-bit key. It is based on Deoxys-BC, a new
tweakable block cipher that reuses the AES round function, and SCT-2,
a nonce-misuse resistant AEAD operating mode. We believe it presents a
lot of interesting features from a security and efficiency point of

- It is a very simple, clean design, and offers a lot of flexibility

- It provides full 128-bit security for both privacy and authenticity
when the nonce is not reused (meaning the AE security bound is of the
form O(q/2^{128}), where q is the total number of encryption or
decryption queries). This is very different from block cipher-based
modes such as OCB3, GCM, or AES-GCM-SIV. To give a numerical example,
when encrypting 2^32 messages of 64 KB each, existing security proofs
ensure that the attacker against authenticity has an advantage of at
most 2^−37 for OCB3, 2^−41 for GCM, 2^-73 or AES-GCM-SIV, and 2^−94
for Deoxys-II.

- Nonce-misuse resistance: Deoxys-II provides very good resistance
when the nonce is reused. Actually, if the nonce is reused only a
small number of times, it retains most of its full 128-bit security as
the security degrades only linearly with the number of nonce
repetitions. This is very different from OCB3 and GCM (for which a
single nonce reuse breaks confidentiality and allows universal
forgeries). Compared to AES-GCM-SIV which is also nonce-misuse
resistant, Deoxys-II provides a larger security margin: for example,
when encrypting 2^32 messages of 64 KB each with the same nonce, the
attacker gets an advantage of about 2^−41 against AES-GCM-SIV versus
2^−51 for Deoxys-II.

- Deoxys-II security has been already analyzed by the designers and by
many third parties during the CAESAR competition (a few publication
venue examples among several others: CRYPTO 2016, ISCAS 2017,
INDOCRYPT 2017, FSE 2018, EUROCRYPT 2018, ISC 2018, 2*FSE 2019, …).
One can see some of these works listed on the Deoxys website:
https://sites.google.com/view/deoxyscipher   This provides very strong
confidence in the design.

- Deoxys-II is fully parallelizable, inverse-free (no need to
implement decryption for the internal tweakable block cipher) and
initialization-free. It provides very good software performances,
benefiting from the AES-NI instructions and general good performances
of AES on any platform. Benchmarks for efficiency comparison will be
produced soon, but one can expect a speed at about 1.5 AES-GCM-SIV for
long messages, and about the same speed as AES-GCM-SIV for short

- Constant time implementations for Deoxys-II are straightforward,
basically using directly bitslice implementations of AES.

- A tweakable block cipher (TBC) such as Deoxys-BC is a very valuable
primitive, that can be used to build easily lots of different more
complex schemes, with very strong security bounds (for example,
several NIST LWC candidates are based on a TBC and defining a hash out
of it). To the best of our knowledge, there is no standard TBC as of

- Deoxys-II is not covered by any patent.

More details on our design, reference implementations and test
vectors, can be found here: https://sites.google.com/view/deoxyscipher

The Deoxys-II team.