Re: [Cfrg] Deoxys-II for AEAD

denis bider <denisbider.ietf@gmail.com> Thu, 21 November 2019 20:33 UTC

Return-Path: <denisbider.ietf@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 A66181200B1 for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 12:33:12 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 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, HTML_MESSAGE=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 ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id I3vIuNG44JSO for <cfrg@ietfa.amsl.com>; Thu, 21 Nov 2019 12:33:10 -0800 (PST)
Received: from mail-ot1-x32d.google.com (mail-ot1-x32d.google.com [IPv6:2607:f8b0:4864:20::32d]) (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 7CF7B1208E8 for <cfrg@irtf.org>; Thu, 21 Nov 2019 12:33:10 -0800 (PST)
Received: by mail-ot1-x32d.google.com with SMTP id m15so4174836otq.7 for <cfrg@irtf.org>; Thu, 21 Nov 2019 12:33:10 -0800 (PST)
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=/MDdWbPSwqTFCr1Xw2HrrkbDf+LA8CoNR1qQ+RRcd9g=; b=rZBegymHurkjHdiJuA8IZcW4NfRknbgTjxyUGGvwkTX6zv4sGOYG5EoD9iW4COkUO7 Ycx1m1e/fpTOX3QjwH36BeNgsJpNgrOyModt585CMAJYJge3+3Lh1T1itKgZ1dFrXpAc vxO0cSLBDQBK8VdeWpRaWuqbYE6QTkclo1gaPYsYikXfVTiAAHRyNJLzlIHcQ/xyGDYv oa9iNqwQNh2355OWVc5uFOWpxlC9yFvp1dTOmi0bPc5ZPEWmJGJmO8P1blcFD/p86uLB vtIX742xfzSuDEquuGx+Jljruhwz7EZcg4GYBfshUaxIw/M70/XlGVZc4H4BMSKhmzyk ENvw==
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=/MDdWbPSwqTFCr1Xw2HrrkbDf+LA8CoNR1qQ+RRcd9g=; b=WRW4pyE/Okmf0sT45WCVb3t4v1fqL2qK6zXc3y5t8hri06DN8sjXgOFB5NH46D5Exv anRbLlBa90skW/ixvBHxp6MobmVWVIdlljjVOtbuJfN29mdrRQYgun1Yrx/0giMuckKB 3EG5uOrWdty02M6uOF4wtSDQPxlNqhsKSRDgx7eqSZB50TkSU5sAAiCmzCrmB88zWJF7 8p751fdTgGwQyguzAguY37XP+6tqseHPUunteXku9bcqctbb662o8lMLbjAYEraCABY3 MinhlgCI+dp2Uzpvu+Yu4Zx8SsXfUc/DVm42LZbOydZDQW4lzZMv3iIqwy0QGvInpibH OnIA==
X-Gm-Message-State: APjAAAXjXeAjp/QqmxFu+pDjIntPoI9p4N4HxnVaDTFW23nOMOY4mLqH jTgiw7l0Pc5uyhJH3ZZSw4m+GTzyVv9Qn1mM0q4=
X-Google-Smtp-Source: APXvYqwIQrJou1LfnGJFpS+YYvt1fpx6Aw5W2S0DRY5B9TB+LwEsH6ljk1EB+DrLPHdfa511XuCtY9fuDZ2NmwQiR8c=
X-Received: by 2002:a9d:5507:: with SMTP id l7mr7417075oth.146.1574368389856; Thu, 21 Nov 2019 12:33:09 -0800 (PST)
MIME-Version: 1.0
References: <CAA0wV7R9rUeNtoRko2pTKM_zRWnyQjzyA34+pCq_XJUS6iHC7A@mail.gmail.com>
In-Reply-To: <CAA0wV7R9rUeNtoRko2pTKM_zRWnyQjzyA34+pCq_XJUS6iHC7A@mail.gmail.com>
From: denis bider <denisbider.ietf@gmail.com>
Date: Thu, 21 Nov 2019 14:32:59 -0600
Message-ID: <CADPMZDC9UDpNL+OTxg1XGJ2vkTLP9Axb_XQWrUVb1XdXLUZDgw@mail.gmail.com>
To: Thomas Peyrin <thomas.peyrin@gmail.com>
Cc: Cfrg <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000009f80dd0597e134a7"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Vq6pej3RMNm6VT3IFhK3ybbboAA>
Subject: Re: [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 20:33:13 -0000

Two comments:

- I'm not a cryptographer, only a user, but the described properties sound
awesome!

- Have you considered making the reference implementations available under
a license other than GPL?

This is not going to fly very far until (and unless) BSD-licensed,
MIT-licensed, fully public domain, or anything other than GPL
implementations are available.

denis

On Thu, Nov 21, 2019 at 11:11 AM Thomas Peyrin <thomas.peyrin@gmail.com>
wrote:

> 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
> (https://competitions.cr.yp.to/caesar-submissions.html).
>
> 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
> view.
>
>
> - 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
> messages.
>
> - 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
> today.
>
> - 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.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>