Generic attacks based on functional graphs

The purpose of this talk is to introduce generic attacks based on functional graphs. 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 is based on exceptional random functions, i.e., functions whose graph admits a large component with an exceptionally small cycle. This attack has since then been improved by Bonnetain et al. (eprint 2024) using so-called nested exceptional functions. They also improved several attacks against hash combiners using exceptional random functions.