Paper 2019/528

Anomalies and Vector Space Search: Tools for S-Box Analysis (Full Version)

Xavier Bonnetain, Léo Perrin, and Shizhu Tian

Abstract

S-boxes are functions with an input so small that the simplest way to specify them is their lookup table (LUT). Unfortunately, some algorithm designers exploit this fact to avoid providing the algorithm used to generate said lookup table. In this paper, we provide tools for finding the hidden structure in an S-box or to identify it as the output of a complex generation process rather than a random sample. We introduce various "anomalies". These real numbers are such that a property with an anomaly equal to $a$ should be found roughly once in a set of $2^a$ random S-boxes. First, we revisit the literature on S-box reverse-engineering to present statistical anomalies based on the distribution of the coefficients in the difference distribution table, linear approximation table, and for the first time, the boomerang connectivity table. We then count the number of S-boxes that have block-cipher like structures to estimate the anomaly associated to those. In order to recover these structures, we show that the most general tool for decomposing S-boxes is an algorithm efficiently listing all the vector spaces of a given dimension contained in a given set, and we present such an algorithm. Finally, we propose general methods to formally quantify the complexity of any S-box. It relies on the production of the smallest program evaluating it and on combinatorial arguments. Combining these approaches, we show that all permutations that are actually picked uniformly at random always have essentially the same cryptographic properties, and can never be decomposed in a simpler way. These conclusions show that multiple claims made by the designers of the latest Russian standards are factually incorrect.

Note: The paper was updated to take feedback from the Asiacrypt'19 reviewers into account.