Paper 2024/488

Improving Generic Attacks Using Exceptional Functions

Xavier Bonnetain, Université de Lorraine, CNRS, Inria, LORIA, Nancy, France
Rachelle Heim Boissier, Université Paris-Saclay, UVSQ, CNRS, Laboratoire de mathématiques de Versailles, Versailles, France
Gaëtan Leurent, Inria, Paris, France
André Schrottenloher, Univ Rennes, Inria, CNRS, IRISA, Rennes, France

Over the past ten years, the statistical properties of random functions have been particularly fruitful for generic attacks. Initially, these attacks targeted iterated hash constructions and their combiners, developing a wide array of methods based on internal collisions and on the average behavior of iterated random functions. More recently, Gilbert et al. (EUROCRYPT 2023) introduced a forgery attack on so-called duplex-based Authenticated Encryption modes which was based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle. In this paper, we expand the use of such functions in generic cryptanalysis with several new attacks. First, we improve the attack of Gilbert et al. from O(2^3c/4) to O(2^2c/3), where c is the capacity. This new attack uses a nested pair of functions with exceptional behavior, where the second function is defined over the cycle of the first one. Next, we introduce several new generic attacks against hash combiners, notably using small cycles to improve the complexities of the best existing attacks on the XOR combiner, Zipper Hash and Hash-Twice. Last but not least, we propose the first quantum second preimage attack against Hash-Twice, reaching a quantum complexity O(2^3n/7).

Available format(s)
Attacks and cryptanalysis
Publication info
CryptanalysisGeneric attackDuplex-based modesHash CombinersRandom Functions
Contact author(s)
xavier bonnetain @ inria fr
rachelle heim @ uvsq fr
gaetan leurent @ inria fr
andre schrottenloher @ inria fr
2024-03-28: revised
2024-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xavier Bonnetain and Rachelle Heim Boissier and Gaëtan Leurent and André Schrottenloher},
      title = {Improving Generic Attacks Using Exceptional Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/488},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.