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

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.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in EUROCRYPT 2023
CryptanalysisAEADDuplex- based constructionsNIST lightweight competitionXoodyakRandom functions
Contact author(s)
henri gilbert @ ssi gouv fr
heim rachelle @ gmail com
louiza khati @ ssi gouv fr
yann rotella @ uvsq fr
2023-03-02: last of 3 revisions
2023-02-22: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.