Tim Beyne
COSIC, KU Leuven, Belgium

Michiel Verbauwhede
COSIC, KU Leuven, Belgium

Keywords: Geometric approach, Integral cryptanalysis, Ultrametric integral cryptanalysis, Arithmetization-oriented primitives

Abstract

Integral and ultrametric integral cryptanalysis are generalized to finite rings of prime characteristic $p$ that are isomorphic to a product of fields. This extends, for instance, the complete state of the art in integral cryptanalysis from $\mathbf{F}_2^n$ to $\mathbf{F}_q^n$, for all prime powers $q$. A compact representation of transition matrices, based on convex polyhedra, is introduced to ensure that the proposed methods are computationally efficient even for large p. Automated tools are developed and applied to a few generic and several concrete primitives. The analysis shows that previous degree estimates for Feistel-GMiMC, HadesMiMC, AES-prime, small-pSquare and mid-pSquare are overly optimistic. Furthermore, except for AES-prime, these primitives do not meet their design criteria unless their number of rounds is increased.