Generic Attack on Duplex-Based AEAD Modes using Random Function Statistics

Henri Gilbert; Rachelle Heim Boissier; Louiza Khati; Yann Rotella

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/262

Generic Attack on Duplex-Based AEAD Modes using Random Function Statistics

Henri Gilbert, ANSSI, France

Rachelle Heim Boissier

, LMV, UVSQ, Université Paris-Saclay, CNRS

Louiza Khati, ANSSI, France

Yann Rotella, LMV, UVSQ, Université Paris-Saclay, CNRS

Abstract

Duplex-based authenticated encryption modes with a sufficiently large key length are proven to be secure up to the birthday bound 2^(c/2), where c is the capacity. However this bound is not known to be tight and the complexity of the best known generic attack, which is based on multicollisions, is much larger: it reaches (2^c)/α where α represents a small security loss factor. There is thus an uncertainty on the true extent of security beyond the bound 2^(c/2) provided by such constructions. In this paper, we describe a new generic attack against several duplex-based AEAD modes. Our attack leverages random functions statistics and produces a forgery in time complexity O(2^(3c/4)) using negligible memory and no encryption queries. Furthermore, for some duplex-based modes, our attack recovers the secret key with a negligible amount of additional computations. Most notably, our attack breaks a security claim made by the designers of the NIST lightweight competition candidate Xoodyak. This attack is a step further towards determining the exact security provided by duplex-based constructions.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in EUROCRYPT 2023
Keywords: Cryptanalysis AEAD Duplex- based constructions NIST lightweight competition Xoodyak Random functions
Contact author(s): henri gilbert @ ssi gouv fr
heim rachelle @ gmail com
louiza khati @ ssi gouv fr
yann rotella @ uvsq fr
History: 2023-03-02: last of 3 revisions; 2023-02-22: received; See all versions
Short URL: https://ia.cr/2023/262
License: CC BY

BibTeX

@misc{cryptoeprint:2023/262,
      author = {Henri Gilbert and Rachelle Heim Boissier and Louiza Khati and Yann Rotella},
      title = {Generic Attack on Duplex-Based AEAD Modes using Random Function Statistics},
      howpublished = {Cryptology ePrint Archive, Paper 2023/262},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/262}},
      url = {https://eprint.iacr.org/2023/262}
}