Cryptanalytic Properties of Mealy Machines

This paper proposes a systematic approach to compute cryptanalytic properties of arbitrary Mealy machines or S-functions. Based on the geometric approach to cryptanalysis, we provide a uniform formula for any cryptanalytic property of such a function, as long as the property is compatible with the way its input and output are split into chunks. Examples include linear, (quasi) differential, (ultrametric) integral, differential-linear, and boomerang properties. To illustrate our results, we compute these properties for several important examples, including modular additions, the Chi- and ChiChi-functions, and the SHA-1 step function. As proof-of-concept applications, we construct a boomerang distinguisher for the Subterranean permutation, and show how to compute the correlations of conditional linear approximations in partitioning-based differential-linear attacks more accurately. Our results also lead to a new approach to compute the algebraic normal form of the inverse of the Chi-function.