Generic attacks using random functions statistics

Cryptography relies on building blocks called primitives used within constructions to build more complex algorithms. The security of a scheme (i.e. of a construction instantiated with a primitive) is most often proven under some assumptions on the underlying primitive. However, security reductions only provide lower bounds on the security level. Generic attacks, i.e. attacks that do not rely on the existence of a primitive flaw, provide complementary information (namely, upper bounds on the security level).

Over the past ten years, the statistical properties of random functions have been a particularly fruitful tool to mount 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, we (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. We have since then improved this attack (Bonnetain et al., CRYPTO 2024) using so-called nested exceptional functions. This talk will present a variety of generic attacks based on functional graphs against hash functions, hash-based MACs and AEAD modes.