Title: Exponential S-Boxes: a Link Between the S-Boxes of BelT and Kuznyechik/Streebog
Abstract: The block cipher Kuznyechik and the hash function Streebog were recently standardized by the Russian Federation. These primitives use a common 8-bit S-Box, denoted \pi, which is given only as a look-up table. The rationale behind its design is, for all practical purposes, kept secret by its authors. In a paper presented at Eurocrypt 2016, Biryukov et al. reverse-engineered this S-Box and recovered an unusual Feistel-like structure relying on finite field multiplications.
We provide a new decomposition of this S-Box and describe how we obtained it. The first step was the analysis of the 8-bit S-Box of the current standard block cipher of Belarus, BelT. This S-Box is a variant of a so-called exponential substitution, a concept we generalize into pseudo-exponential substitution. We derive distinguishers for such permutations based on properties of their linear approximation tables and notice that \pi shares some of them. We then show that \pi indeed has a decomposition based on a pseudo-exponential substitution. More precisely, we obtain a simpler structure based on an 8-bit finite field exponentiation, one 4-bit S-Box, a linear layer and a few modular arithmetic operations.
We also make several observations which may help cryptanalysts attempting to reverse-engineer other S-Boxes. For example, the visual pattern used in the previous work as a starting point to decompose \pi is mathematically formalized and the use of differential patterns involving operations other than exclusive-or is explored.