International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Improving Generic Attacks Using Exceptional Functions

Authors:
Xavier Bonnetain , Université de Lorraine, Inria, LORIA, Nancy, France
Rachelle Heim Boissier , Université Paris-Saclay, UVSQ, Laboratoire de mathématiques de Versailles, Versailles, France
Gaëtan Leurent , Inria, Paris, France
André Schrottenloher , Univ Rennes, Inria, CNRS, IRISA, Rennes, France
Download:
DOI: 10.1007/978-3-031-68385-5_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: Over the past ten years, there have been many attacks on symmetric constructions using the statistical properties of random functions. 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}).
BibTeX
@inproceedings{crypto-2024-34266,
  title={Improving Generic Attacks Using Exceptional Functions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68385-5_4},
  author={Xavier Bonnetain and Rachelle Heim Boissier and Gaëtan Leurent and André Schrottenloher},
  year=2024
}