[Cfrg] Deoxys-II for AEAD

[Thomas Peyrin <[e-mail]>]

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.