Unified foundations for the linear and differential cryptanalysis of permutation-based cryptography

The first part of this thesis develops a general approach to symmetric-key cryptanalysis. It brings together linear, differential and integral cryptanalysis in a single framework, and extends these techniques in several ways. A universal notion of trails is introduced, leading to a systematic method to evaluate the properties of iterated functions. The theory provides a unified description of extensions of linear cryptanalysis, and clarifies the connections between them. For differential cryptanalysis, it leads to the definition of quasidifferentials trails, which make it possible to estimate the probability of differential characteristics without relying on assumptions of probabilistic independence. In integral cryptanalysis, it suggests a spectrum of properties between zero-sums and saturation. These can be obtained and analyzed using a new theory of ultrametric trails, that generalizes division or monomial trails.

The second part of this thesis turns to applications of cryptanalysis. Using a characterization of invariants as eigenvectors of correlation matrices that follows from the first part, weak key attacks on reduced-round Midori-64 and Mantis are given. The South-Korean and American format-preserving encryption standards FEA and FF3-1 are broken using multidimensional linear cryptanalysis. Differential attacks on Rectangle, KNOT and Speck are reevaluated using quasidifferential trails, showing that some of these attacks were invalid and that others work only for a subset of keys. A new generic attack on contracting Feistel ciphers leads to attacks on the Chinese commercial encryption standard SM4 with a reduced number of rounds. The security of several arithmetization-oriented primitives is analyzed, leading to attacks on some instances of GMiMC-erf, GMiMC-crf, HadesMiMC and the Legendre PRF. An attack on the backdoored cipher LowMC-M is given, and two new backdoored ciphers that follow more standard design principles are proposed. Finally, it is shown how linear cryptanalysis can be used to analyze the security of side-channel countermeasures.