Subject: [Cfrg] Deoxys-II for AEAD

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 01:10:40 +0800

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.

---

From: denis bider <[email-masked]>
Date: Thu, 21 Nov 2019 14:32:59 -0600

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 <[email-masked]>
wrote:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Nov 2019 20:54:39 +0000

How does Deoxys-II compare to AES-GCM-SIV+ (not AES-GCM-SIV)? E.g., https://tools.ietf.org/html/rfc8452 and https://eprint.iacr.org/2017/168.pdf ?

I don’t see how you can be faster than POLYVAL…

From: Cfrg <[email-masked]> on behalf of denis bider <[email-masked]>
Date: Thursday, November 21, 2019 at 3:33 PM
To: Thomas Peyrin <[email-masked]>
Cc: CFRG <[email-masked]>
Subject: Re: [Cfrg] Deoxys-II for AEAD

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 <[email-masked]> wrote:

Dear all,

The Deoxys-II team.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Nov 2019 21:14:17 +0000

I confess to being confused with the CAESAR process. It's web site does not say anything about completion, and lists two candidates (1st and 2nd choices) for each of the three portfolios.

Speaking of Deoxys - the site refers to the paper https://competitions.cr.yp.to/round3/deoxysv141.pdf 
The paper refers to http://www1.spms.ntu.edu.sg/~syllab/Deoxys , which doesn't exist any more. 

What gives???

On 11/21/19, 12:11 PM, "Cfrg on behalf of Thomas Peyrin" <[email-masked] on behalf of [email-masked]> wrote:

    Dear all,

    

    

    

    The Deoxys-II team.

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 05:31:33 +0800

Hi Denis,

Sure, I think MIT license would make sense. We will add optimized
implementations soon, we will take this occasion to change licenses of
all implementations that we provide on the website.

Regards,

Thomas.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 21 Nov 2019 13:34:05 -0800

On Thu, Nov 21, 2019 at 9:11 AM Thomas Peyrin <[email-masked]>
wrote:

> to propose Deoxys-II for consideration at IRTF.

I think it'd be nice to have an informational RFC for Deoxys-II.

I'll +1 requests for a liberally licensed high-quality implementation...
and also pseudocode implementations in the RFC.

I'm also curious about benchmarks against AES-GCM-SIV.

-- 
Tony Arcieri

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 05:43:05 +0800

Hi Uri,

For long messages, on processors with a PCLMULQDQ instruction,
AES-GCM-SIV will be indeed faster than Deoxys-II. Yet, this might not
be the case on less fancy software platforms or in hardware. Besides,
there is no initialisation needed in Deoxys-II, so for short messages
the efficiency should be very similar.

In any case, independently of the high-end server efficiency, we
believe Deoxys-II provides interesting features listed in my previous
email. Also, I would like to emphasize that trust in a symmetric key
cipher is something extremely valuable and is provided by the actual
cryptanalysis performed on the scheme. As a winner of the CAESAR
competition, Deoxys-II went through extensive cryptanalysis from the
symmetric-key crypto community.

Regards,

Thomas.

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 05:48:48 +0800

Hi Uri,

the final timeline of the competition is given on this page:
https://competitions.cr.yp.to/caesar.html

Indeed, for each of the three portfolio, two candidates are given:
- "Lightweight applications": ASCON is 1st choice and ACORN is 2nd choice
- "High-performance applications": both AEGIS-128 and OCB are 1st choices
- "Defense in depth": Deoxys-II is 1st choice and COLM is 2nd choice

Sorry the broken link, but we have changed our website for Deoxys, it
is now located at: https://sites.google.com/view/deoxyscipher/accueil

Regards,

Thomas.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Nov 2019 21:52:06 +0000

Thanks!

On 11/21/19, 4:49 PM, "Thomas Peyrin" <[email-masked]> wrote:

    Hi Uri,

    
    
    Regards,
    
    Thomas.

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 05:55:42 +0800

Hi Tony,

Sure, we would be glad to draft a RFC, but I am not sure what is the
exact process.

Some benchmarks and comparison with AES-GCM can already be found on
Supercop CAESAR results page (yet, these Deoxys-II implementations are
not fully optimized). We will provide more benchmarks when we will be
fully done with our implementations.

Regards,

Thomas.

Le ven. 22 nov. 2019 à 05:34, Tony Arcieri <[email-masked]> a écrit :
>
> On Thu, Nov 21, 2019 at 9:11 AM Thomas Peyrin <[email-masked]> wrote:
>>
> I'll +1 requests for a liberally licensed high-quality implementation... and also pseudocode implementations in the RFC.
>

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 05:56:22 +0800

Hi Rich,

Of course. Detailed test vectors are already available on the website.

Regards,

Thomas.

Le ven. 22 nov. 2019 à 05:39, Salz, Rich <[email-masked]> a écrit :
> And of course test vectors.

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 21 Nov 2019 13:59:52 -0800

> Sure, we would be glad to draft a RFC, but I am not sure what is the

If you ultimately want an informational RFC about Deoxys-II, a draft
describing it is the place to start. You might look at RFC 8452
(AES-GCM-SIV) for inspiration:

https://tools.ietf.org/html/rfc8452

Once you have a draft, you can ask the CFRG to adopt it as a work item. If
it's accepted by the CFRG as a work item, and eventually approved and
published as an RFC, then IETF protocols can begin using it.

-- 
Tony Arcieri

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 06:08:40 +0800

I see, thanks. We'll work on that then !

Regards,

Thomas.

Le ven. 22 nov. 2019 à 06:00, Tony Arcieri <[email-masked]> a écrit :
>
> On Thu, Nov 21, 2019 at 1:55 PM Thomas Peyrin <[email-masked]> wrote:
>>
> If you ultimately want an informational RFC about Deoxys-II, a draft describing it is the place to start. You might look at RFC 8452 (AES-GCM-SIV) for inspiration:
>
> Once you have a draft, you can ask the CFRG to adopt it as a work item. If it's accepted by the CFRG as a work item, and eventually approved and published as an RFC, then IETF protocols can begin using it.
>
> --
> Tony Arcieri

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 06:13:14 +0800

Actually, would it make sense to separate the tweakable block cipher
(TBC) from the AEAD operating mode ?  A TBC can be used for other
purposes than AEAD.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Thu, 21 Nov 2019 22:10:05 +0000

No, those benchmarks you refer to appear to be against the "old" GCM-SIV, which is almost twice as slow. You'd need to compare with the current implementation (efficient did not get to CAESAR because it was created a few years after the competition began).

Regards,
Uri

Sent from my iPhone

> On Nov 21, 2019, at 16:56, Thomas Peyrin <[email-masked]> wrote:
> 
> Hi Rich,
>

---

From: Tony Arcieri <[email-masked]>
Date: Thu, 21 Nov 2019 14:16:57 -0800

> (TBC) from the AEAD operating mode ?  A TBC can be used for other

You could have a separate section in the draft documenting its usage as a
tweakable block cipher, in addition to one documenting it as an AEAD mode.

See RFC 8452 Section 6 for an example of how to split the AEAD interface
into its own section.

--
Tony Arcieri

---

From: Thomas Peyrin <[email-masked]>
Date: Fri, 22 Nov 2019 06:19:17 +0800

Hi Uri,

actually, I was referring to GCM, not GCM-SIV. Indeed, AES-GCM-SIV is
not benchmarked at all in CAESAR Supercop results.

Regards,

Thomas.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 21 Nov 2019 21:39:19 +0000

*   I'll +1 requests for a liberally licensed high-quality implementation... and also pseudocode implementations in the RFC.