Léo Perrin
email: leo.perrin@inria.fr

Partitions in the S-Box of Streebog and Kuznyechik *

Keywords: Boolean functions, Kuznyechik, Streebog, Reverse-Engineering, Partitions, Cosets, TKlog

Streebog and Kuznyechik are the latest symmetric cryptographic primitives standardized by the Russian GOST. They share the same S-Box, 𝜋, whose design process was not described by its authors. In previous works, Biryukov, Perrin and Udovenko recovered two completely different decompositions of this S-Box. We revisit their results and identify a third decomposition of 𝜋. It is an instance of a fairly small family of permutations operating on 2𝑚 bits which we call TKlog and which is closely related to finite field logarithms. Its simplicity and the small number of components it uses lead us to claim that it has to be the structure intentionally used by the designers of Streebog and Kuznyechik. The 2𝑚-bit permutations of this type have a very strong algebraic structure: they map multiplicative cosets of the subfield GF(2 𝑚 ) * to additive cosets of GF(2 𝑚 ) * . Furthermore, the function relating each multiplicative coset to the corresponding additive coset is always essentially the same. To the best of our knowledge, we are the first to expose this very strong algebraic structure. We also investigate other properties of the TKlog and show in particular that it can always be decomposed in a fashion similar to the first decomposition of Biryukov et al., thus explaining the relation between the two previous decompositions. It also means that it is always possible to implement a TKlog efficiently in hardware and that it always exhibits a visual pattern in its LAT similar to the one present in 𝜋. While we could not find attacks based on these new results, we discuss the impact of our work on the security of Streebog and Kuznyechik. To this end, we provide a new simpler representation of the linear layer of Streebog as a matrix multiplication in the exact same field as the one used to define 𝜋. We deduce that this matrix interacts in a non-trivial way with the partitions preserved by 𝜋.

Introduction

Many symmetric primitives rely on S-Boxes as their unique source of non-linearity, including the AES [START_REF]Advanced Encryption Standard (AES)[END_REF]. Such objects are small functions mapping F 𝑚 2 to F 𝑛 2 which are often specified via their look-up tables.

Their choice is crucial as both the security and the efficiency of the primitive depends heavily on their properties. For example, a low differential uniformity [START_REF] Nyberg | Differentially uniform mappings for cryptography[END_REF] implies a higher resilience against differential attacks [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]BS91b]. On the other hand, the existence of a simple decomposition greatly helps with an efficient bitsliced or hardware implementation [START_REF] Li | Constructing S-boxes for lightweight cryptography with Feistel structure[END_REF][START_REF] Canteaut | Construction of lightweight S-boxes using Feistel and MISTY structures[END_REF]. Thus, algorithm designers are expected to provide detailed explanation about their choice of S-Box. Each cipher that was published at a cryptography or security conference has provided such explanations.

There are two prominent S-Boxes for which this information has not been provided. The first is the so-called "F-table" of Skipjack [U.S98], a lightweight block cipher designed by the American National Security Agency (NSA). The second is 𝜋, the 8-bit permutation used by the Russian standard hash function (nicknamed Streebog [START_REF]security: Hash function[END_REF]) and block cipher (nicknamed Kuznyechik [START_REF]security: Block ciphers[END_REF]), as well as the first version of the CAESAR candidate STRIBOBr1 [START_REF] Saarinen | The STRIBOBr1 authenticated encryption algorithm[END_REF] (which later changed its components for those of Whirlpool [START_REF] Markku-Juhani | Whirlbob, the whirlpool based variant of STRIBOB[END_REF]).

While Streebog and Kuznyechik were first published as national standards in Russia (GOST), they have since been included in other standards. For instance, both have been included by the IETF as RFC 6986 [START_REF] Dolmatov | Hash function[END_REF] and RFC 7801 [START_REF] Dolmatov | Gost r 34[END_REF] respectively. ISO/IEC is also in the process of adding Kuznyechik to their list of standard block ciphers, namely standard 18033-3 1 . S-Boxes have been found to be potential vehicules for the insertion of a backdoor in a symmetric algorithm. In 1997, Rijmen and Preneel suggested an S-Box generation strategy which ensured that a high probability linear transition existed [START_REF] Rijmen | A family of trapdoor ciphers[END_REF]. The idea was that only the designer would be able to know about this linear approximation but this claim was later proven wrong [WBDY98]. Later, Paterson designed a backdoored variant of the DES with modified S-Boxes [START_REF] Kenneth | Imprimitive permutation groups and trapdoors in iterated block ciphers[END_REF]. His overall approach was recently refined by Bannier et al. [START_REF] Bannier | Partition-based trapdoor ciphers[END_REF] to build a block cipher which preserves a partition of the plaintext space independently from the key.

In this context, cryptanalysts have tried to reverse-engineer the structure of poorly specified S-Boxes. The first such attempt occurred in the late 1970's, shortly after the publication of the DES: Hellman et al. identified some patterns in the S-Boxes of this block cipher [HMS + 76]. Much more recently, Biryukov et al. devised new tools for this purpose. For example, a statistical analysis of the differential and linear properties allowed them to show that the S-Box of Skipjack diplayed a higher resilience against linear attacks [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] than expected [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF].

More importantly in our case, they provided the first decomposition of the Russian S-Box, 𝜋, in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF][START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]. The corresponding structure operates on two branches, much like a Feistel or Misty structure. It is however much more complex than both of them as it involves finite field multiplications in GF(2 4 ) and a multiplexer. Later, Perrin and Udovenko found discrete logarithm-based decompositions of this component [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF]. They are very different from the previous decomposition but remain somewhat unsatisfactory due to the complex "arithmetic layer" they use. Their authors concluded that "We could not find sensible explanations for using a structure from any of our decompositions as an S-Box." In fact, the existence of these new structures raised more questions than it answered, although they "strengthen the idea that 𝜋 has a strong algebraic structure hardly compatible with the claims of randomness of the designers" [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF]. In the end, Perrin and Udovenko conjectured the existence of a "master decomposition" of which the decompositions of both [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] and [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] would be mere side effects.

Our Contribution. We show that the intuition in [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] was correct and present what we claim to be said "master decomposition". It holds that 𝜋, the S-Box used by the last two Russian standards, operates as follows:

⎧ ⎪ ⎨ ⎪ ⎩ 𝜋(0) = 𝜅(0) 𝜋(𝛼 0+17𝑗 ) = 𝜅(16 -𝑗) 𝜋(𝛼 𝑖+17𝑗 ) = 𝜅(16 -𝑖) ⊕ ( 𝛼 17 ) 𝑠(𝑗) for 𝑖 > 0 ,
where 𝛼 is a root of the primitive polynomial defining the finite field GF(2 8 ), where 𝑠 is a permutation of Z/15Z, and where 𝜅 : F 4 2 → GF(2 8 ) is an affine function such that any element 𝑥 ∈ GF(2 8 ) can be written as 𝑥 = 𝑥 4 ⊕ 𝜅(𝑥 𝜅 ) ⊕ 𝜅(0) with 𝑥 4 ∈ GF(2 4 ) and 𝑥 𝜅 ∈ F 4 2 . We also use "+" and "-" to denote integer addition and substration, and "⊕" denotes the addition in the finite field.

We generalize this new structure by allowing 𝜅 and 𝑠 to be picked in appropriate sets and call the resulting class of permutation TKlog. This new structure allows us to easily explain a particular property of 𝜋: it maps the partition of GF(2 8 ) into multiplicative cosets of GF(2 4 ) * to the partition of GF(2 8 ) into additive cosets of GF(2 4 ) * .2 Furthermore, the restriction of 𝜋 to each independent multiplicative coset is always the same simple function. Thus, not only does it map a simple partition of GF(2 8 ) to another one, it does so in a very straightforward way.

We also prove that such permutations can always be written in a fashion similar to the decomposition of [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] so our new decomposition provides the missing link between the first decomposition of [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] and the logarithm-based decomposition of [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF]. Using counting arguments, we show that the size of the set of the TKlogs operating on 8 bits and the number of affine 8-bit permutations are of comparable magnitudes, meaning that the probability that a random permutation is a TKlog instance is negligible. We therefore claim that the presence of this structure in 𝜋 is a deliberate choice by its designers. Using experimental arguments, we propose a simple generation algorithm of which 𝜋 would be a typical output.

Finally, we remark that the linear layer of Streebog is an MDS matrix with coefficients in GF(2 8 ) where the primitive polynomial used to define the representation of its elements is actually the same as the one used to define 𝜋 as a TKlog. Thus, the cosets interacting with 𝜋 also interact with the linear layer of Streebog. We provide a first discussion of the consequences of the new structure in 𝜋 in terms of security but leave their exploitation in a cryptanalysis as an open problem.

Outline. Section 2 recalls the background necessary, both in terms of mathematics and in terms of previous results. The TKlog, its relationship with 𝜋 and its partition-preserving property are presented in Section 3. We show that the TKlog is the "missing link" between [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] and [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] and list several consequences of this fact in Section 4. Then, we investigate the consequences of the fact that 𝜋 is a TKlog for the higher level primitives themselves in Section 5. We also present a new representation of the linear layer of Streebog which can be of independent intrerest. Finally, Section 6 concludes this paper.

Background

Notations and Basic Definitions

Finite Fields. There exists, up to isomorphisms, a unique finite field with 2 𝑛 elements which we denote GF(2 𝑛 ). We use "⊕" to denote the addition in the field and 𝑎 ⊙ 𝑏 or 𝑎𝑏 to denote the product of 𝑎, 𝑏 ∈ GF(2 𝑛 ). For all 𝑥 ∈ GF(2 𝑛 ), it holds that 𝑥 2 𝑛 ⊕ 𝑥 = 0.

If 𝑛 = 2𝑚 then we define the trace from GF(2 2𝑚 ) to GF(2 𝑚 ) as the function Tr 𝑚 : GF(2 2𝑚 ) → GF(2 𝑚 ) such that Tr 𝑚 (𝑥) = 𝑥 2 𝑚 ⊕ 𝑥. For any 𝛽 ∈ GF(2 2𝑚 ) such that Tr 𝑚 (𝛽) = 1, the elements of GF(2 2𝑚 ) can all be decomposed in a unique way into 𝑎𝛽 ⊕ 𝑏, where 𝑎 and 𝑏 are in GF(2 𝑚 ). The bijection mapping 𝑥 ∈ GF(2 2𝑚 ) to (𝑎, 𝑏) ∈ GF(2 𝑚 ) 2 such that 𝑥 = 𝑎𝛽 ⊕ 𝑏 is denoted Split 𝛽 , so that Split 𝛽 (𝑎𝛽 ⊕ 𝑏) = (𝑎, 𝑏). It is a linear function.

We use 𝑆 * to denote a set 𝑆 minus the element 0. Even though GF(2 𝑚 ) * is not an additive group, we call {𝑎 ⊕ 𝑥, 𝑥 ∈ GF(2 𝑚 ) * } an additive coset of GF(2 𝑚 ) * for the sake Partitions in the S-Box of Streebog and Kuznyechik of simplicity. If 𝑆 is a set and 𝑎 is a constant, we denote 𝑎 ⊕ 𝑆 = {𝑎 ⊕ 𝑥, 𝑥 ∈ 𝑆} and 𝑎𝑆 = 𝑎 ⊙ 𝑆 = {𝑎 ⊙ 𝑥, 𝑥 ∈ 𝑆}.

Binary Strings as Ring Elements. The field GF(2 𝑛 ) can be identified with F 2 [𝑋]/𝑝(𝑋) for some irreducible polynomial 𝑝 of degree 𝑛. If 𝛼 is a root of 𝑝 then we can represent all the elements of GF(2 𝑛 ) as ∑ 𝑛-1 𝑖=0 𝑥 𝑖 𝛼 𝑖 , where 𝑥 𝑖 ∈ F 2 . A binary string (𝑥 0 , ..., 𝑥 𝑛-1 ) ∈ F 𝑛 2 is therefore naturally interpreted as ∑ 𝑛-1 𝑖=0 𝑥 𝑖 𝛼 𝑖 ∈ GF(2 𝑛 ) in much the same way that it can also be interpreted as

∑ 𝑛-1 𝑖=0 𝑥 𝑖 2 𝑖 ∈ Z/2 𝑛 Z.
In this case, the binary representation of 𝑎 ⊕ 𝑏 for 𝑎, 𝑏 ∈ GF(2 𝑛 ) is indeed the XOR of the binary representations of 𝑎 and 𝑏.

Logarithms. For all 𝑥 ∈ GF(2 𝑛 ) * , the logarithm log 𝛼 (𝑥) is the integer of Z/(2 𝑛 -1)Z such that 𝛼 log 𝛼 (𝑥) = 𝑥. Such a function is not a permutation because it is not defined in 0. This problem can be solved in different ways. In [START_REF] Risto | On the nonlinearity of discrete logarithm in F 𝑛 2[END_REF], Hakala and Nyberg study the function which we denote log HN 𝛼 while Feng et al. in [START_REF] Feng | Maximal values of generalized algebraic immunity[END_REF] introduced another variant, a special case of which is a permutation of GF(2 𝑛 ) and which we call log FLY 𝛼 . These two functions map GF(2 𝑛 ) to Z/2 𝑛 Z and are defined by

log HN 𝛼 (𝑥) = ⎧ ⎪ ⎨ ⎪ ⎩ 2 𝑛 -1 if 𝑥 = 0 , 0 if 𝑥 = 1 , log 𝛼 (𝑥) if 𝑥 ̸ ∈ {0, 1} ,
and log FLY 𝛼 (𝑥) = ⎧ ⎪ ⎨ ⎪ ⎩ 0 if 𝑥 = 0 , 2 𝑛 -1 if 𝑥 = 1 , log 𝛼 (𝑥) if 𝑥 ̸ ∈ {0, 1} .
In other words log FLY

𝛼

, is a variant of log HN 𝛼 where the outputs of 0 and 1 are swapped. We remark that the built-in discrete logarithm in SAGE [START_REF]SageMath, the Sage Mathematics Software System[END_REF] actually implements log FLY 𝛼 on GF(2 𝑛 ) * . Another variant of the logarithm called "pseudo-logarithm" was introduced in [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] when investigating 𝜋 but we will not use it here.

Boolean Functions. Let 𝐹 : F 𝑛 2 → F 𝑚 2 be a function. The Linear Approximations Table (LAT) or Walsh transform of 𝐹 is the 2 𝑛 × 2 𝑚 matrix 𝒲 𝐹 such that

𝒲 𝐹 (𝑎, 𝑏) = ∑ 𝑥∈F 𝑛 2 (-1) 𝑎•𝑥⊕𝑏•𝐹 (𝑥) ,
where 𝑎 • 𝑏 is the usual scalar product in

F 𝑛 2 . The maximum value of |𝒲 𝐹 (𝑎, 𝑏)| for 𝑏 ̸ = 0 is the linearity of 𝐹 . The Difference Distribution Table (DDT) of 𝐹 is the 2 𝑛 × 2 𝑚 matrix 𝛿 𝐹 such that 𝛿 𝐹 (𝑎, 𝑏) = # {𝑥 ∈ F 𝑛 2 , 𝐹 (𝑥 ⊕ 𝑎) ⊕ 𝐹 (𝑥) = 𝑏} .
The maximum value of 𝛿 𝐹 (𝑎, 𝑏) for 𝑎 ̸ = 0 is the differential uniformity of 𝐹 . If 𝐴 and 𝐵 are affine permutations of F 𝑚 2 and F 𝑛 2 respectively, then 𝐹 is affine equivalent to 𝐺 = 𝐵 ∘ 𝐹 ∘ 𝐴. Furthermore, let 𝐿 𝐴 and 𝐿 𝐵 be the linear parts of 𝐴 and 𝐵. Then the LAT of 𝐺 is:

𝒲 𝐺 (𝑎, 𝑏) = 𝒲 𝐹 ( (𝐿 -1 𝐴 ) 𝑇 (𝑎), 𝐿 𝑇 𝐵 (𝑏) ) .
Affine-equivalence can be generalized into CCZ-Equivalence [START_REF] Carlet | Codes, bent functions and permutations suitable for DES-like cryptosystems[END_REF]: two functions 𝐹 :

F 𝑛 2 → F 𝑚 2 and 𝐺 : F 𝑛 2 → F 𝑚 2 are CCZ-equivalent if there exists an affine permutation 𝒜 of F 𝑛 2 × F 𝑚 2 such that {(𝑥, 𝐹 (𝑥)) , 𝑥 ∈ F 𝑛 2 } = 𝒜 ( {(𝑥, 𝐺(𝑥)) , 𝑥 ∈ F 𝑛 2 } ) .
This form of equivalence is known to preserve, among other things, the differential uniformity and the linearity.

On the S-Box 𝜋

While the specification of both Streebog and Kuznyechik have always been public, a complete design rationale has not been provided. In particular, its designers gave very little information about the design method of their S-Box. Its look-up table is given in Table 2 in Appendix 8. This lack of information prompted academics to try and reverse-engineer this S-Box. We present the two decompositions that were found by Biryukov, Perrin and Udovenko further below but first we summarize the information that the designers did provide.

From the Designers

At RusCrypto'13 [START_REF] Vassilij Shishkin | Принципы синтеза перспективного алгоритма блочного шифрования с длиной блока 128 бит [design principles of the perspective block encryption algorithm with a block length of 128 bits[END_REF], Shishkin gave a talk presenting the design principles of their upcoming block cipher (Kuznyechik was standardized in 2015). While they considered using S-Boxes from a known class of good S-Boxes, their prefered design approach was different. It is summarized in the following (translated) quote from their slides.

[The properties of S-Boxes designed via a] Random search with a specified parameter restriction

• are not optimal when considering the aggregate of the values of the basic cryptographic properties

• do not have a pronounced analytical structure

In other words, S-Boxes randomly generated trade their non-optimal cryptographic properties (differential uniformity, etc.) for the absence of an analytical structure which could be used by an attacker. Further in their presentation, they state that the number of bit operations needed to implement the S-Box should be minimized so as to help with both hardware and vectorized implementations. Those design criteria make sense; in fact, many algorithms use S-Boxes chosen with a similar rationale such as, for example, CLEFIA [SSA + 07]. However, up until the decomposition found by Biryukov et al. [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] (see Section 2.2.2) no efficient implementation strategy was known for 𝜋. Furthermore, this permutation was shown to be somewhat close to a finite field logarithm [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] (see Section 2.3), which seems at odd with the claimed lack of analytical structure.

TU-Decomposition

Because the design method of 𝜋 was not published, Biryukov et al. tried to look for additional design criteria or even for hidden structure using (and improving) techniques Partitions in the S-Box of Streebog and Kuznyechik from [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF]. Their results are presented in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF][START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]. They showed that 𝜋 has a TU-decomposition, i.e. that it is affine-equivalent to a permutation (𝑥, 𝑦) ↦ → ( 𝑇 𝑦 (𝑥), 𝑈 𝑇𝑦(𝑥) (𝑦) ) where both 𝑇 𝑦 and 𝑈 𝑥 are 4-bit permutations for all (𝑥, 𝑦) ∈ (F 4 2 ) 2 . They further provided a decomposition of both 𝑇 and 𝑈 , so that the overall structure of 𝜋 is as described in Figure 1a where 𝜈 0 , 𝜈 1 and 𝜎 are 4-bit permutations, 𝜑 is a 4-bit function such that 𝜑(𝑥) ̸ = 0 and ℐ is the multiplicative inversion in GF(2 4 ). The multiplexer selects the output of 𝜈 0 if the right branch is equal to 0 and the output of 𝜈 1 otherwise. The last components are 𝛼 and 𝜔, two 8-bit linear permutations which are linked by the following relation:

{ 𝛼 -1 (𝑥||0), 𝑥 ∈ F 4 2 } = { 𝜔(0||𝑥), 𝑥 ∈ F 4 2 } . ( 1

Discrete Logarithm

While investigating the S-Box of the Belarussian standard block cipher BelT [START_REF]Information technologies. Data protection. Cryptographic algorithms for encryption and integrity control[END_REF], Perrin and Udovenko found a completely different decomposition of 𝜋 [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF]. Indeed, they showed that it had the structure summarized in Figure 1b, i.e. that it was the composition of:

• a "pseudo-logarithm", i.e. a permutation obtained by inverting a "pseudo-exponential" which is itself built as a sequence [𝛼 0 , 𝛼 1 , 𝛼 2 , ..., 𝛼 𝑗-1 , 0, 𝛼 𝑗 , ..., 𝛼 2 𝑛 -2 ] for a generator 𝛼 of GF(2 8 ) * and some preimage 𝑗 for 0;

• a layer of modular arithmetic operations which they could not simplify,

• a 4-bit permutation 𝑞 ′-1 , and

• an 8-bit linear permutation 𝜔 ′ .

This decomposition uses the primitive polynomial 𝑝 min (𝑋) = 𝑋 8 ⊕ 𝑋 4 ⊕ 𝑋 3 ⊕ 𝑋 2 ⊕ 1 to define the finite field used in its logarithm. It is the first primitive polynomial of degree 8 in the lexicographic order as can be seen e.g. in Table C of [START_REF] Lidl | Finite fields[END_REF]. It is also the default polynomial used when building a finite field of size 2 8 in SAGE [START_REF]SageMath, the Sage Mathematics Software System[END_REF].

Relations Between the Decompositions

These decompositions are functionally equivalent since they both correspond to the same permutation 𝜋, and yet they have little to nothing in common. When evaluating the TU-decomposition, the input first goes through a linear layer mapping F 8 2 to (GF(2 4 )) 2 and then undergoes (𝑎, 𝑏) ↦ → (𝑎/𝑏, 𝑏), except if 𝑏 = 0. On the other hand, evaluating the log-based decomposition first requires using a variant of the discrete logarithm. What is the relation between these operations?

We thus find it surprising that both decompositions exist. Furthermore, none of them seems like a natural choice for building an S-Box. These observations led Perrin and Udovenko to the following conclusion [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF]:

we think it more likely that [the TU-decomposition and log-based decomposition are] a consequence of a strong algebraic structure used to design [𝜋], probably one related to a finite field exponential. Still this "master decomposition", from which the others would be consequences, remains elusive. Unfortunately, unless the Russian secret service release their design strategy, their exact process is likely to remain a mystery, if nothing else because of the existence of alternative decompositions: which exists by design and which is a mere side-effect of this design?

In the next section, we present what we believe to be this "master decomposition". It relies on a discrete logarithm, which relates it to the second decomposition, and it turns out that a TU-decomposition identical to the one of [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF] is always possible for permutations with a similar structure. We argue that this new decomposition is likely to be the one intended by the designers later in Section 5.1.

The TKlog

In this section, we introduce a new type of permutation which we call TKlog of which 𝜋 turns out to be a particular case. As Stribog and Kuznyechik were both designed by the "ТК-26"3 , we used the letters "TK" to name this structure. It has log-like properties, though mapping GF(2 2𝑚 ) to itself rather than to Z/2 2𝑚 Z, hence the "log" part of the name. More precisely, it maps the partition of GF(2 2𝑚 ) into multiplicative cosets of GF(2 𝑚 ) * to its partition into additive cosets of GF(2 𝑚 ) and its restriction to each multiplicative coset is essentially the same for all cosets. We define this structure in Section 3.1 and present the details of this partition-preserving property in Section 3.2.

The TKlog Permutation Structure

The TKlog. Let GF(2 2𝑚 ) = F 2 [𝑋]/𝑝(𝑋) be a finite field of even degree defined by a primitive polynomial 𝑝. The multiplicative subgroup GF(2 2𝑚 ) * is cyclic and generated by 𝛼 which is such that 𝑝(𝛼) = 0. In this context, 𝛼 2 𝑚 +1 is a generator of the multiplicative subgroup of the subfield GF(2 𝑚 ).

Definition 1 (TKlog). A TKlog is permutation operating on GF(2 2𝑚 ) = F 2 [𝑋]/𝑝(𝑋) for some primitive polynomial 𝑝 with root 𝛼. It is parametrized by:

• an affine function 𝜅 : F 𝑚 2 → GF(2 2𝑚 ) such that any 𝑥 ∈ GF(2 2𝑚 ) can be written 𝑥 = 𝑥 𝑚 ⊕ 𝜅(𝑥 𝜅 ) ⊕ 𝜅(0) for some 𝑥 𝑚 ∈ GF(2 𝑚 ) and 𝑥 𝜅 ∈ F 𝑚 2 , 4 and • a permutation 𝑠 of Z/(2 𝑚 -1)Z.
The corresponding TKlog is denoted T 𝜅,𝑠 and it works as follows:

⎧ ⎪ ⎨ ⎪ ⎩ T 𝜅,𝑠 (0) = 𝜅(0) , T 𝜅,𝑠 ( (𝛼 2 𝑚 +1 ) 𝑗 ) = 𝜅(2 𝑚 -𝑗), for 1 ≤ 𝑗 ≤ 2 𝑚 -1 , T 𝜅,𝑠 ( 𝛼 𝑖+(2 𝑚 +1)𝑗 ) = 𝜅(2 𝑚 -𝑖) ⊕ ( 𝛼 2 𝑚 +1 ) 𝑠(𝑗) , for 0 < 𝑖, 0 ≤ 𝑗 < 2 𝑚 -1 ,
where the fact that 1 ≤ 𝑗 ≤ 2 𝑚 -1 rather than 0 ≤ 𝑗 < 2 𝑚 -1 when 𝑥 ∈ GF(2 𝑚 ) * comes from the implicit use of Feng et al.'s logarithm. Algorithm 3 (in Appendix 9) evaluates such a permutation.

To convince ourselves that a TKlog instance as defined above is indeed a permutation, we define its functional inverse, TKexp. It uses Φ

𝜅 : GF(2 2𝑚 ) → F 𝑚 2 × GF(2 𝑚 ) which is the affine permutation such that Φ 𝜅 ( 𝜅(𝑥) ⊕ 𝑣 ) = (𝑥, 𝑣) for (𝑥, 𝑣) ∈ F 𝑚 2 × GF(2 𝑚
). The TKexp works as follows:

⎧ ⎪ ⎨ ⎪ ⎩ ( T -1 𝜅,𝑠 ∘ Φ -1 𝜅 ) (0, 0) = 0 , ( T -1 𝜅,𝑠 ∘ Φ -1 𝜅 ) (𝑘, 0) = 𝛼 (2 𝑚 +1)(2 𝑚 -𝑘) , ( T -1 𝜅,𝑠 ∘ Φ -1 𝜅 ) (𝑘, 𝑣) = 𝛼 2 𝑚 -𝑘+(2 𝑚 +1)𝑠 -1 (𝑗) where 𝑗 = log FLY 𝛼 (𝑣)/(2 𝑚 + 1) .
Alternatively, it can be evaluated using Algorithm 4 (in Appendix 9).

On the Substraction. The integer substraction in the input of 𝜅 is made necessary by the fact that 𝑖 ∈ {1, ..., 2 𝑚 }, so that the binary representation of 𝑖 does not always fit in 𝑚 bits. We therefore need a small function that maps {1, ..., 2 𝑚 } to {0, ..., 2 𝑚 -1} since the case 𝑖 = 0 is handled separately. A natural choice would obviously be 𝑖 ↦ → 𝑖 -1 but, in the case, we would need a different function when 𝑖 = 0. Indeed, since a FLY logarithm is used, we have 𝑗 ∈ {1, ..., 2 𝑚 -1} when 𝑖 = 0. Thus, we would need to compose 𝜅 with two different functions depending on whether 𝑖 = 0. On the other hand, the function 𝑖 ← 2 𝑚 -𝑖 maps both {1, ..., 2 𝑚 } to {0, ..., 2 𝑚 -1} and {1, ..., 2 𝑚 -1} to itself, meaning that it can be used in both cases. We could not find such a simple function when log HN 𝛼 is used.

The Particular case of 𝜋. The S-Box 𝜋 is a TKlog operating on 8 bits. For implementation purposes, we identify GF(2 8 ) with F 8 2 using the method we described in Section 2.1. When written as TKlog instance, 𝜋 uses the following components:

• the finite field GF(2 8 ) = F 2 [𝑋]/𝑝 min (𝑋) where 𝑝 min (𝑋) = 𝑋 8 ⊕ 𝑋 4 ⊕ 𝑋 3 ⊕ 𝑋 2 ⊕ 1
and its root 𝛼;

• an affine function 𝜅 mapping F 4 2 to F 8 2 such that 𝜅(0) = 0xFC with a linear part Λ defined by

Λ(1) = 12 , Λ(2) = 26 , Λ(4) = 24 , Λ(8) = 30 ,
where the numbers are written in hexadecimal form and where the linear function Λ verifies

{ 𝑥 4 ⊕ Λ(𝑦), 𝑥 4 ∈ GF(2 4 ), 𝑦 ∈ F 4 2 } = GF(2 8 ); and
• a permutation 𝑠 of Z/15Z defined in Table 1. The evaluation of 𝜋 using this structure is summarized in Algorithm 1. An implementation of 𝜋 based on this algorithm is given as a SAGE [START_REF]SageMath, the Sage Mathematics Software System[END_REF] script in Appendix 12. It is noteworthy that the default logarithm function in SAGE is log FLY 𝛼 , which simplifies the implementation of the function.

We actually obtained the TKlog structure by first decomposing 𝜋 and then generalizing the structure we found. A summary of our reverse-engineering process is given in Appendix 10. end if 13: end function

Cosets to Cosets

A Partition-Preserving Property

Recall that GF(2 𝑚 ) * is the field of size 2 𝑚 minus 0 and that it is contained in GF(2 2𝑚 ) * . Let 𝛼 be a multiplicative generator of GF(2 2𝑚 ) * so that 𝛼 2 𝑚 +1 is a multiplicative generator of GF(2 𝑚 ) * . The field GF(2 2𝑚 ) can be written in two different ways using the multiplicative cosets of GF(2 𝑚 ) * on one hand and the additive cosets of GF(2 𝑚 ) * on the other.

• All the elements in GF(2 2𝑚 ) * can be written as

𝛼 𝑖+(2 𝑚 +1)𝑗 = 𝛼 𝑖 ( 𝛼 2 𝑚 +1 ) 𝑗 , so that GF(2 2𝑚 ) = {0} ∪ ( 2 𝑚 ⋃ 𝑖=0 𝛼 𝑖 ⊙ GF(2 𝑚 ) * ) = GF(2 𝑚 ) ∪ ( 2 𝑚 ⋃ 𝑖=1 𝛼 𝑖 ⊙ GF(2 𝑚 ) *
) .

• As GF(2 𝑚 ) is a vector space of dimension 𝑚, there exists a vector space 𝑊 of elements of GF(2 2𝑚 ) of dimension 𝑚 such that GF(2 2𝑚 ) is the direct sum of 𝑊 and GF(2 𝑚 ). In this case, we can write

GF(2 2𝑚 ) = ⋃ 𝑤∈𝑊 𝑤 ⊕ GF(2 𝑚 ) = 𝑊 ∪ ( ⋃ 𝑤∈𝑊 𝑤 ⊕ GF(2 𝑚 ) * ) .
Both 𝑊 and GF(2 𝑚 ) are vector spaces of dimension 𝑚 and, in each decomposition, 2 𝑚 cosets of GF(2 𝑚 ) * are used. It is therefore possible to map these decompositions from one to the other. It is precisely what a TKlog does. More formally, the following theorem holds.

Theorem 1 (Cosets to Cosets). Let T 𝜅,𝑠 : GF(2 2𝑚 ) → GF(2 2𝑚 ) be a valid TKlog instance.

Then the following equalities are always true:

{ T 𝜅,𝑠 (GF(2 𝑚 )) = 𝜅 (F 𝑚 2 ) T 𝜅,𝑠 ( 𝛼 𝑖 ⊙ GF(2 𝑚 ) * ) = 𝜅(2 𝑚 -𝑖) ⊕ GF(2 𝑚 ) * , ∀𝑖 ̸ = 0 .
Corollary 1 (Vector spaces to affine spaces). Let T 𝜅,𝑠 : GF(2 2𝑚 ) → GF(2 2𝑚 ) be a valid TKlog instance. Then it always holds that

T 𝜅,𝑠 (GF(2 𝑚 )) = 𝜅 (F 𝑚 2 ) and T 𝜅,𝑠 (𝛼 2 𝑚 ⊙ GF(2 𝑚 )) = 𝜅(0) ⊕ GF(2 𝑚 ) ,
where all the spaces involved in these equalities are of dimension 𝑚. Furthermore,

GF(2 2𝑚 ) = { 𝑥 ⊕ 𝑦, 𝑥 ∈ GF(2 𝑚 ), 𝑦 ∈ 𝛼 2 𝑚 ⊙ GF(2 𝑚 ) } = { 𝑥 ⊕ 𝑦, 𝑥 ∈ 𝜅(0) ⊕ GF(2 𝑚 ), 𝑦 ∈ 𝜅(0) ⊕ 𝜅 (F 𝑚 2 )
} , so a TKlog maps two vector spaces of dimension 𝑚 spanning GF(2 2𝑚 ) to two affine spaces of dimension 𝑚 spanning GF(2 2𝑚 ).

As 𝜋 is a TKlog instance, Theorem 1 implies that it verifies the following set equalities

{ 𝜋 ( GF(2 4 ) ) = 𝜅(F 4 2 ) 𝜋 ( 𝛼 𝑖 ⊙ GF(2 4 ) * ) = 𝜅(16 -𝑖) ⊕ GF(2 𝑚 ) * , ∀𝑖 ̸ = 0 ,
and applying Corollary 1 yields 𝜋(𝛼 16 ⊙ GF(2 4 )) = 𝜅(0) ⊕ GF(2 4 ). These equalities are summarized in Figure 2 where relationships between complete affine spaces are represented by dashed and thick arrows while those linking sets of size 2 𝑚 -1 are represented by plain thin ones.

{0} GF(2 4 ) * 𝛼 16 ⊙ GF(2 4 ) * ... 𝛼 2 ⊙ GF(2 4 ) * 𝛼 1 ⊙ GF(2 4 ) * {0xFC} 𝜅((F 4 2 ) * ) 𝜅(15) ⊕ GF(2 4 ) * 𝜅(14) ⊕ GF(2 4 ) * ... 𝜅(0) ⊕ GF(2 4 ) * ...

The Simplicity of the TKlog Properties

The partitions dealt with in Theorem 1 have simple algebraic descriptions. Indeed, 𝑥, 𝑦 ∈ GF(2 2𝑚 ) * are in the same additive coset of GF(2 𝑚 ) * if and only if Tr 𝑚 (𝑥) = Tr 𝑚 (𝑦). Then, we remark that

( 𝛼 𝑖+(2 𝑚 +1)𝑗 ) 2 𝑚 -1 = 𝛼 (2 𝑚 -1)𝑖+(2 2𝑚 -1)𝑗 = 𝛼 (2 𝑚 -1)𝑖 , so that ( 𝛼 𝑖+(2 𝑚 +1)𝑗 ) 2 𝑚 -1 = ( 𝛼 𝑖 ′ +(2 𝑚 +1)𝑗 ′ ) 2 𝑚 -1 if and only if 𝑖 = 𝑖 ′ . Thus, 𝑥, 𝑦 ∈ GF(2 2𝑚 ) * are in the same multiplicative coset of GF(2 𝑚 ) * if and only if 𝑥 2 𝑚 -1 = 𝑦 2 𝑚 -1 .
Furthermore, 𝑥 ∈ GF(2 𝑚 ) * if and only if 𝑥 2 𝑚 -1 = 1. We deduce the following corollary of Theorem 1.

Corollary 2. Let T 𝜅,𝑠 : GF(2 2𝑚 ) → GF(2 2𝑚 ) be a valid TKlog instance. Then we always have that

𝑥 2 𝑚 -1 = 𝑦 2 𝑚 -1 ̸ = 1 ⇔ Tr 𝑚 (T 𝜅,𝑠 (𝑥)) = Tr 𝑚 (T 𝜅,𝑠 (𝑦)) ̸ = Tr 𝑚 (𝜅(0)) .
As a consequence, for any constant 𝑐 ∈ GF(2 2𝑚 )∖{0, 1}, we have the following implication involving only linear equations:

𝑥 2 𝑚 ⊕ 𝑐𝑥 = 𝑦 2 𝑚 ⊕ 𝑐𝑦 = 0 =⇒ (T 𝜅,𝑠 (𝑥)) 2 𝑚 ⊕ T 𝜅,𝑠 (𝑥) = (T 𝜅,𝑠 (𝑦)) 2 𝑚 ⊕ T 𝜅,𝑠 (𝑦) .
The interaction of a TKlog with these two partitions goes beyond mapping one to the other. Indeed, consider a more general structure corresponding to permutations 𝑃 such that:

𝑃 : ⎧ ⎪ ⎨ ⎪ ⎩ 0 ↦ → 𝜅 (𝑡 0 (0)) 𝛼 (2 𝑚 +1)𝑗 ↦ → 𝜅 (𝑡 0 (2 𝑚 -𝑗)) 𝛼 𝑖+(2 𝑚 +1)𝑗 ↦ → 𝜅 (𝑡 1 (2 𝑚 -𝑖)) ⊕ ( 𝛼 2 𝑚 +1 ) 𝑠𝑖(𝑗) for 𝑖 > 0 , ( 2
)
where 𝑡 0 and 𝑡 1 are permutations of F 𝑚 2 , and where 𝑠 𝑖 is a permutation of Z/(2 𝑚 -1)Z for all 𝑖 ∈ Z/(2 𝑚 + 1)Z. Any such 𝑃 is a permutation with the exact partition-preserving property described in Theorem 1 but its contributions on GF(2 𝑚 ) and on 𝜅(F 𝑚 2 ) each depend on both 𝑖 and 𝑗, even when we restrict ourselves to 𝑖 > 0. It is not the case for TKlogs; these permutations are far simpler.

Lemma 1 (Separation Property). Let T 𝜅,𝑠 : GF(2 2𝑚 ) → GF(2 2𝑚 ) be a valid TKlog instance. Then, for any 𝑖, 𝑗 such that 0 < 𝑖 ≤ 2 𝑚 and 0 ≤ 𝑗 < 2 𝑚 -1, it holds that

T 𝜅,𝑠 (𝛼 𝑖+(2 𝑚 +1)𝑗 ) = 𝜅(2 𝑚 -𝑖) ⏟ ⏞ ∈𝜅(F 𝑚 2 ) ⊕ (𝛼 2 𝑚 +1 ) 𝑠(𝑗) ⏟ ⏞ ∈GF(2 𝑚 ) *
, so that the contribution of 𝑖 is restricted to 𝜅(F 𝑚 2 ) and that of 𝑗 is restricted to GF(2 𝑚 ). In other words, a TKlog interacts with each multiplicative coset other than GF(2 𝑚 ) * in the exact same way, even though this property is in no way implied by Theorem 1.

We could not find any attack leveraging these surprising properties of 𝜋. However, we did find that these partitions interact in a non-trivial way with the linear layer of Streebog. We discuss the consequences of the presence of this structure in 𝜋 in Section 5.

The Missing Link

The TKlog structure is the missing link between the two previous decompositions of 𝜋. Its relationship with the logarithm-based decompositions of [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] is natural since both consist in a variant of the discrete logarithm followed by some arithmetic. The fact that 𝜋 has a TU-decomposition remains a priori surprising but, in Section 4.1, we show that it is always the case for TKlogs. We also list some of the consequences of this property in Section 4.2.

A TU-Decomposition Always Exists

TKlogs can always be expressed in a fashion very similar to the first decomposition of Biryukov et al. [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]. In order to establish it, we first derive the following lemma.

Lemma 2. There exists a function 𝛾

: (Z/(2 𝑚 + 1)Z) * → Z/(2 𝑚 -1)Z such that { 𝑥 ∈ GF(2 2𝑚 ), Tr(𝑥) = 1 } = { 𝛼 𝑖+(2 𝑚 +1)𝛾(𝑖) , 𝑖 ∈ Z/(2 𝑚 + 1)Z * } .
Proof. Let (𝑎, 𝑏) = Split 𝛽 (𝑥). If 𝑥 ̸ ∈ GF(2 𝑚 ), then 𝑎 ̸ = 0 and we can write 𝑥 = 𝑎(𝛽 ⊕ 𝑐) where 𝑐 = 𝑏/𝑎 is an element of GF(2 𝑚 ), so that Tr(𝛽 ⊕ 𝑐) = Tr(𝛽) = 1. As such a decomposition exists for all 𝑥 ̸ ∈ GF(2 𝑚 ), we deduce that the set

{ log FLY 𝛼 (𝑐 ⊕ 𝛽), 𝑐 ∈ GF(2 𝑚 ) }
must contain a representative of each equivalence class modulo 2 𝑚 + 1 as the contrary would imply that some elements 𝛼 𝑖+(2 𝑚 +1)𝑗 with 𝑖 ̸ = 0 could not be written 𝑎(𝛽 ⊕ 𝑐). As a consequence, { log FLY 𝛼 (𝑐 ⊕ 𝛽) mod (2 𝑚 + 1), 𝑐 ∈ GF(2 𝑚 ) } = {1, ..., 2 𝑚 } and there must therefore exist a function 𝛾 as described above such that

{ log FLY 𝛼 (𝑐 ⊕ 𝛽), 𝑐 ∈ GF(2 𝑚 ) } = { 1 + (2 𝑚 + 1)𝛾(1), ..., 2 𝑚 + (2 𝑚 + 1)𝛾(2 𝑚 ) } .
The lemma follows.

Theorem 2 (TU-Decomposition of the TKlog). The permutation T 𝜅,𝑠 of GF(2 2𝑚 ) has a TU-decomposition involving three 𝑚-bit permutations 𝜏, 𝜈 and 𝜎, and an 𝑚-bit function 𝜑.

It is given in Algorithm 2.

The specification of the subcomponents is given in the proof of this theorem.

Algorithm 2

The TU-decomposition of TKlog.

◁ Evaluation of ℎ = 𝑈 𝑇𝑎(𝑏) (𝑎) = 𝑈 ℓ (𝑎) 11: ℎ ← 𝜎 ( 𝜑(ℓ) ⊙ 𝑎 ) 12:
◁ Output linear layer 13:

return 𝜅(ℓ) ⊕ ℎ 14: end function Proof. Let (𝑎, 𝑏) = Split 𝛽 (𝑥). Intuitively, 𝑎 will correspond to the right-side branch of the TU-decomposition and 𝑏/𝑎 to the left-side one. In particular, the case 𝑎 = 0 is a special case. This proof is direct in the sense that it "simply" consists in defining the subcomponents 𝜏, 𝜎, 𝜈 and 𝜑 correctly and then checking that they work. a = 0. If 𝑎 = 0 then 𝑥 ∈ GF(2 𝑚 ), so that the definition of the TKlog yields T 𝜅,𝑠 (𝑥) = 𝜅 (𝜏 (𝑏)) where

𝜏 : ⎧ ⎨ ⎩ GF(2 𝑚 ) → F 𝑚 2 0 ↦ → 0 , 𝑏 ↦ → 2 𝑚 -log FLY (𝛼 2 𝑚 +1 ) (𝑏) if 𝑏 ̸ = 0 . Indeed, let 𝑥 = 𝑏 = 𝛼 (2 𝑚 +1)𝑗 for 0 < 𝑗 ≤ 2 𝑚 -1.
For 𝑏 ̸ = 0, 1, we have that log FLY (𝛼 2 𝑚 +1 ) (𝑏) = log 𝛼 (𝑏)/(2 𝑚 + 1) = 𝑗, so that 𝜅 (𝜏 (𝑏)) is indeed equal to T 𝜅,𝑠 (𝑥). For 𝑏 = 0, we also immediately have that 𝜅 (𝜏 (𝑏)) = T 𝜅,𝑠 (𝑥). For 𝑏 = 1, log FLY 𝛼 (𝑏) = 2 2𝑚 -1 = (2 𝑚 -1)(2 𝑚 + 1), so that 𝑗 = 2 𝑚 -1 which is indeed equal to log FLY (𝛼 2 𝑚 +1 ) (𝑏).

a ̸ = 0. Otherwise, since 𝑎 ̸ = 0 we can write 𝑥 = 𝑎(𝛽 ⊕ 𝑏/𝑎) and, as 0 and 1 are in GF(2 𝑚 ), we have that 𝑥 ̸ = 0, 1 so that log FLY 𝛼 (𝑥) = log 𝛼 (𝑥). In order to evaluate T 𝜅,𝑠 (𝑥), we need to find 𝑖 and 𝑗 such that 𝑎(𝛽 ⊕ 𝑏/𝑎) = 𝛼 𝑖+(2 𝑚 +1)𝑗 . It holds that Tr 𝑚 (𝑎) = 0 and Tr 𝑚 (𝛽 ⊕ 𝑏/𝑎) = 1, so we can apply Lemma 2 to write

{ 𝛽 ⊕ 𝑏/𝑎 = 𝛼 𝑖+(2 𝑚 +1)𝛾(𝑖) 𝑎 = 𝛼 (2 𝑚 +1)(𝑗-𝛾(𝑖)) . ( 3
)
We define the permutations 𝜈, 𝜎 and the function 𝜑 as follows.

• The permutation 𝜈 captures the way the logarithm and the arithmetic operation 𝑥 ↦ → 2 𝑚 -𝑥 operate on 𝑏/𝑎 to return the correct input for 𝜅:

𝜈 : { GF(2 𝑚 ) → F 4 2 𝑐 ↦ → 2 𝑚 - ( log 𝛼 (𝛽 ⊕ 𝑐) mod (2 𝑚 + 1) ) , so that 𝜈(𝑏/𝑎) = 2 𝑚 -𝑖.
• The permutation 𝜎 corresponds to the permutation 𝑠 applied on 𝑗:

𝜎 : ⎧ ⎪ ⎨ ⎪ ⎩ GF(2 𝑚 ) → GF(2 𝑚 ) 0 ↦ → 0 𝑐 ↦ → ( 𝛼 2 𝑚 +1 ) 𝑠 ( log (𝛼 2 𝑚 +1 ) (𝑐)
) when 𝑐 ̸ = 0 .

• The function 𝜑 corresponds to the function 𝛾 introduced because of Lemma 2. It is defined by

𝜑 : { F 𝑚 2 → GF(2 𝑚 ) 𝑖 ↦ → 𝛼 (2 𝑚 +1)𝛾(2 𝑚 -𝑖) ,
where 𝑖 ∈ F 𝑚 2 is interpreted as an element of Z/(2 𝑚 + 1)Z. Note that 𝜑(𝑖) ̸ = 0 for all 𝑖. Using that 𝜈(𝑏/𝑎) = 2 𝑚 -𝑖, we have

(𝜑 ∘ 𝜈)(𝑏/𝑎) = 𝜑(2 𝑚 -𝑖) = 𝛼 (2 𝑚 +1)𝛾(𝑖)
and, using Equation 3 as well, we obtain that (𝜑 ∘ 𝜈)(𝑏/𝑎) ⊙ 𝑎 = 𝛼 (2 𝑚 +1)𝛾(𝑖) ⊙ 𝛼 (2 𝑚 +1)(𝑗-𝛾(𝑖)) = 𝛼 (2 𝑚 +1)𝑗 .

Combining this result with the definition of 𝜎, we obtain that

𝜎 ( (𝜑 ∘ 𝜈)(𝑏/𝑎) ⊙ 𝑎 ) = 𝜎 ( 𝛼 (2 𝑚 +1)𝑗 ) = ( 𝛼 2 𝑚 +1
) 𝑠(𝑗) .

We can then write for any 𝑎 ̸ = 0 that

T 𝜅,𝑠 (𝑎𝛽 ⊕ 𝑏) = 𝜅 ( 𝜈(𝑏/𝑎) ⏟ ⏞ 2 𝑚 -𝑖 ) ⊕ 𝜎 ( (𝜑 ∘ 𝜈)(𝑏/𝑎) ⊙ 𝑎 ) ⏟ ⏞ (𝛼 2 𝑚 +1 ) 𝑠(𝑗)
.

When 𝑎 = 0, the term on the right of the XOR cancels out because 𝜎(0) = 0. Therefore, when 𝑎 = 0, we can write:

T 𝜅,𝑠 (𝑎𝛽 ⊕ 𝑏) = 𝜅 ( 𝜏 (𝑏) ) ⏟ ⏞ T𝜅,𝑠(𝑏) ⊕ 𝜎 ( (𝜑 ∘ 𝜈)(𝑏/𝑎) ⊙ 𝑎 ) ⏟ ⏞ 0 ,
which is the same expression as when 𝑎 ̸ = 0 except that the input of 𝜅 is changed from 𝜈(𝑏/𝑎) to 𝜏 (𝑏). As a consequence, it is possible to evaluate this function in two stages.

1. Let (𝑎, 𝑏) = Split 𝛽 (𝑥). If 𝑎 = 0, let ℓ = 𝜏 (𝑏); otherwise let ℓ = 𝜈(𝑏/𝑎).

Return 𝜅

(ℓ) ⊕ 𝜎 ( 𝜑(ℓ) ⊙ 𝑎 ) .
This process is exactly the one described in Algorithm 2, an observation which concludes the proof.

Ironically, the only "unsurprising" sub-component of 𝜋, namely the inverse function, is one of the reasons why we were able to reverse-engineer this S-Box in the first place. Had [the inversion] been replaced by a different (and possibly weaker!) S-Box, there would not have been any of the lines in the LAT which got our reverse-engineering started.

We can now see that, rather than luck, all of these events are direct consequences of the TKlog structure of 𝜋.

Incidentally, it provides an excellent method for spotting such structure should someone else decide to use one-and try to keep this fact hidden. In [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF], Perrin and Udovenko suggested to plot the variance of the absolute value of the coefficients in each row/column of the LAT. They noticed that, in the case of 𝜋, there was a sharp drop for some columns. Because of Lemma 3, we can see that this pattern is an inherent property of the TKlog which will therefore always betray the presence of such a structure. Furthermore, should the TKlog instance be obfuscated by composing it with affine layers, this pattern would remain and in fact provide some information about the linear part of said affine layers.

Furthermore, since a TKlog always has a TU-decomposition, it will always have a vector space of dimension 𝑛 = 2𝑚 inside the set of the coordinates of the zeroes of its LAT [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]. This other pattern can also be detected and thus identicate a TKlog instance to be such.

CCZ-Equivalence. Because of Theorem 2, we know that a TKlog is always affineequivalent to a permutation

𝑃 : (GF(2 𝑚 )) 2 → (F 𝑚 2 ) 2 such that 𝑃 (𝑏, 𝑎) = ( 𝑇 𝑎 (𝑏), 𝑈 𝑇𝑎(𝑏) (𝑎) ) where { 𝑇 𝑎 (𝑏) = 𝜏 (𝑏) × [𝑎 = 0] ⊕ 𝜈(𝑏/𝑎) × [𝑎 ̸ = 0] , 𝑈 𝑘 (𝑎) = 𝜎 (𝑎/𝜑(𝑘)) ,
where [𝑎 = 0] is a Boolean function mapping 0 to 1 and 𝑎 ̸ = 0 to 0 and where [𝑎

̸ = 0] = 1 ⊕ [𝑎 = 0].
As explained in [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF], the existence of such a decomposition where 𝑇 𝑟 is a permutation for all 𝑟 ∈ F 𝑚 2 is equivalent to the possibility of a so-called 𝑚-twist, an operation which preserves the CCZ-equivalence class but a priori does not preserve the AE-equivalence class. As a functional inversion also preserves the CCZ-Equivalence class, we deduce the following corollary of Theorem 2. Corollary 3. Let 𝑇 and 𝑈 be as defined above. Both the corresponding TKlog instance and its inverse are CCZ-equivalent to the function 𝐹 :

F 𝑚 2 × GF(2 𝑚 ) → F 𝑚 2 × GF(2 𝑚 ) such that 𝐹 (𝑏, 𝑎) = ( 𝑇 -1 𝑎 (𝑏), 𝑈 𝑏 (𝑎) ) where { 𝑇 -1 𝑎 (𝑏) = 𝜏 -1 (𝑏) × [𝑎 = 0] ⊕ ( 𝜈 -1 (𝑏) ⊙ 𝑎 ) × [𝑎 ̸ = 0] , 𝑈 𝑏 (𝑎) = 𝜎 (𝑎/𝜑(𝑏)) ,
Proof. By definition (see [START_REF] Canteaut | On CCZ-equivalence, extended-affine equivalence, and function twisting[END_REF]), the 𝑚-twist maps a function 𝑃 :

(𝑟, ℓ) ↦ → ( 𝑇 𝑟 (ℓ), 𝑈 𝑇𝑟(ℓ) (𝑟) ) to 𝐹 : (𝑟, ℓ) ↦ → ( 𝑇 -1 𝑟 (ℓ), 𝑈 ℓ (𝑟) )
. The corollary follows directly.

In the case of 𝜋, we generated the function 𝐹 𝜋 which is CCZ-equivalent to it as specified in Corollary 3. Its lookup-table is provided in the Supplementary Material for the sake of completeness (see Table 3). It of course has the same differential and extended Walsh spectra as 𝜋 and, again like 𝜋, all of its coordinates have degree 7. However, it is not a permutation: 15 elements in its image have 3 preimages, 75 have 2 and the 61 remainding ones have 1.

New Information on the Russian Primitives

In this section, we discuss the consequences of the fact that 𝜋 is (up to a translation) a TKlog instance for the primitives using it. First, we argue that the presence of a TKlog structure must be a deliberate choice from the designers (Section 5.1). We then introduce a new representation of the binary matrix used in Streebog in Section 5.2 which we use to highlight some interactions between the partitions preserved by 𝜋 and this linear component. Finally, we discuss our findings and their consequences in Section 5.3.

The Likely Design Process of 𝜋

In light of our results, we can deduce some information about the design process of 𝜋. First, we establish that the number of TKlog instances is extremely small, meaning that the choice of this structure must have been deliberate. Then, using some experimental results, we obtain a design process which yields results extremely similar to 𝜋.

Density of the TKlog set.

Apart from the high level algorithm, a TKlog operating on 8 bits is fully defined by three components: a primitive polynomial 𝑝 of degree 8 (there are 16 possible choices), an affine function 𝜅 : 𝑥 ↦ → Λ(𝑥) ⊕ 𝜅(0) where the 8 × 4 binary matrix Λ is such that Λ(F 4

2 ) and GF(2 4 ) span GF(2 8 ), and a permutation 𝑠 of Z/15Z. The matrix Λ must be such that its first column Λ 0 is not in GF(2 4 ), the second one is not in GF(2 4 ) ∪ (Λ 0 ⊕ GF(2 4 )), etc. so that there are (2 8 -2 4 )(2 8 -2 5 )(2 8 -2 6 )(2 8 -2 7 ) ≈ 2 30.3 choices for this matrix. As a consequence, there are about

16 ⏟ ⏞ 𝑝 × 2 30.3 ⏟ ⏞ Λ × 2 8 ⏟ ⏞ 𝜅(0) × 15! ⏟ ⏞ 𝑠 ≈ 2 82.6
distinct TKlog instances on 8 bits. This number is very small. To put it into perspective, there is a total of 2 8 ! ≈ 2 1684 permutations of F 8 2 out of which 2 8 × ∏ 7 𝑖=0 (2 8 -2 𝑖 ) ≈ 2 70.2 are affine. The number of TKlog instances is thus about 4000 times larger than the number of affine permutations.

Our point with these estimates is to give an intuition of how small the number of TKlogs is. A random permutation generator returning an affine permutation would be assumed to deliberately generate such object. In much the same way, the generation process that led the designers of Streebog to choose 𝜋 can be assumed to have deliberately returned a TKlog instance.

Claim. Given how small the number of TKlog is, we are confident that the designers of 𝜋 deliberately chose to use this structure.

Experimental Results. How good are the differential and linear properties of TKlog instances compared to those expected from a random permutation? To answer this question, we build upon the analysis of the S-Box of Skipjack in [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF] to introduce the following concepts.

Definition 2 (Anomaly of an S-Box). Let 𝐹 : F 𝑛 2 → F 𝑛 2 be a permutation, 𝑢(𝐹 ) be its differential uniformity, and 𝑁 𝑘 (𝐹 ) be the number of occurrences of 𝑘 in its DDT. The differential anomaly of 𝐹 is equal to

A d 𝐹 = -log 2 ( Pr [ 𝑢(𝐺) ≤ 𝑢(𝐹 ) and 𝑁 𝑢(𝐹 ) (𝐺) ≤ 𝑁 𝑢(𝐹 ) (𝐹 ) ] ) ,
where the probability is taken over all permutations 𝐺. If ℓ(𝐹 ) is the linearity of 𝐹 and 𝑁 ′ 𝑘 (𝐹 ) is the sum of the number of occurrences of 𝑘 and -𝑘 in the LAT of 𝐹 , then the linear anomaly of 𝐹 is equal to

A ℓ 𝐹 = -log 2 ( Pr [ ℓ(𝐺) ≤ ℓ(𝐺) and 𝑁 ′ ℓ(𝐹 ) (𝐺) ≤ 𝑁 ′ ℓ(𝐹 ) (𝐹 ) ] ) ,
where the probability is taken over all permutations 𝐺.

An S-Box with a differential anomaly close to 0 has differential properties close to those of a random S-Box or worse. The differential anomaly behaves as we would expect: when the differential uniformity decreases under its expected value, the anomaly increases. As it contains more information than the differential uniformity, it allows a comparison of S-Boxes for which this quantity is the same. From a cryptographic standpoint, the higher the anomaly the better as it means that the S-Box will provide a better security against differential attacks. The same can be said for the linear anomaly.

In [START_REF] Biryukov | On reverse-engineering S-boxes with hidden design criteria or structure[END_REF], Biryukov and Perrin provided formulas for computing the differential and linear anomalies based on the statistical distribution of the DDT and LAT coefficients presented in [START_REF] Daemen | Probability distributions of correlation and differentials in block ciphers[END_REF]. They also showed that the linear anomaly of the S-Box of Skipjack was equal to 55.4 so that this component could not have been generated randomly.

To try and gather more information about the design process of 𝜋, we generated 10 6 random 8-bit TKlog instances. We plotted the differential and linear anomalies of each of them in a two dimensional graph given in Figure 3. Each instance corresponds to a light gray point; darker points are obtained when multiple instances have the same differential and linear anomalies. We also put the anomalies of 𝜋, log FLY 𝛼 and log HN 𝛼 in the same graph for comparison. As we can see, the differential and linear anomalies of 𝜋 are somewhat good but not exceptional compared to those of a random TKlog. More precisely, an 8-bit TKlog instance has both a differential and linear anomaly at least as high as that of 𝜋 with probability about 2 -10.6 and it is not hard to obtain much better instances. They are also lower than those of both log FLY 𝛼 and log HN 𝛼 . However, none of our random instances have a better differential uniformity or linearity than 𝜋 (including log FLY 𝛼 and log HN 𝛼 ). Furthermore, 𝜋 is in the area of Figure 3 containing most instances with the same differential uniformity and linearity. Thus, its anomalies are on par with those of a random TKlog instance with the same differential uniformity and linearity.

Design Process Outline.

In light of the experimental results above, we can see that the following design process would yield a result very similar to 𝜋.

1. Figure out that the best possible differential uniformity for an 8-bit TKlog instance is 8 and the best linearity is 56, for example via extensive computer simulations.

Partitions in the S-Box of Streebog and Kuznyechik 2. Pick a TKlog instance at random among those with said differental uniformity and linearity-without taking the anomaly into account.

This strategy is natural as long as there is a reason to impose the use of a TKlogthough we cannot think of one. Since both the differential and linear anomalies of 𝜋 are inferior to those of log FLY 𝛼 and of log HN 𝛼 , the purpose of the use of a TKlog in this case could not be an improvement of the cryptographic properties of the discrete logarithm. More importantly, the very strong algebraic properties of such components which we described in Section 3.2 would a priori invite caution; even more so in the case of Streebog. Indeed, as we explain below, its linear layer interacts non-trivially with the corresponding partitions.

On the Linear Layer of Streebog

The binary matrix corresponding to the L operation of Streebog is given in Figure 4 where a black pixel corresponds to 1 and a white one to 0. As we can see, it has a strong structure. In [START_REF] Kazymyrov | Algebraic aspects of the russian hash standard GOST r 34[END_REF], Kazymyrov and Kazymyrova showed that it could be written as the composition of:

• a layer of 8-bit linear permutations ℓ which simply inverts the order of the bits in each byte,

• the multiplication by an 8 × 8 MDS matrix of GF(2 8 ) = F 2 [𝑋]/𝑃 KK (𝑋) where 𝑃 KK (𝑋) = 𝑋 8 ⊕ 𝑋 6 ⊕ 𝑋 5 ⊕ 𝑋 4 ⊕ 1 is a primitive polynomial of degree 8, and

• the inverse of the layer ℓ.

We used a very direct approach to try and simplify this structure: by setting each byte in a row to 1 one after the other, multiplying it by L, and then writing its bytes as elements of GF(2 8 ) = F 2 [𝑋]/𝑝 min (𝑋), we generated the matrix L F such that

L F = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣
⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ .
The polynomial used by Kazymrov and Kazymrova is the reciprocate of 𝑝 min , i.e. 𝑃 KK (1/𝑋) = 𝑝 min (𝑋)/𝑋 8 . In hindsight, it was obvious that the reversal of the bit order at the byte level in their expression of the linear layer could be removed by considering this polynomial instead.

In the end, if we let 𝐴 be the 8 × 8 matrix of elements of GF(2 8 ) corresponding to the internal state of Streebog and let P denote the transposition of 𝐴 (as is done in the specification of Streebog), then applying the whole linear part of the round function of Streebog can be written

(L ∘ P)(𝐴) = 𝐴 𝑇 × L F ,
where "×" denotes the usual matrix multiplication.

Additive to Multiplicative Cosets. The subfield GF(2 4 ) * has a particular interaction with L. Indeed, applying the matrix multiplication of Streebog to the vector 𝑥 𝑖 = [0, ..., 0, 𝑥, 0, ..., 0] of GF(2 8 ) 8 such that 𝑥 𝑖 𝑖 = 𝑥 and

𝑥 𝑖 𝑘 = 0 if 𝑘 ̸ = 𝑖 is equivalent to computing 𝑣 = 𝑥 𝑖 × L F = [ L F 𝑖,0 ⊙ 𝑥, ..., L F 𝑖,7 ⊙ 𝑥 ] , so that if 𝑥 ∈ GF(2 𝑚 ) * then 𝑣 𝑗 ∈ L F 𝑖,𝑗 ⊙ GF(2 𝑚 ) * , i.e
. it maps the subfield to its multiplicative cosets. However, it is unclear what happens when multiple cells of the input vector are active.

Kuznyechik. The linear layer of Kuznyechik is specified as an LFSR made of 16 cells, each of which is an element of GF(2 8 ), which is clocked 16 times. It can also be represented as a multiplication by a 16 × 16 matrix. However the representation of the field elements uses a different polynomial, namely 𝑝 kuz (𝑋) = 𝑋 8 ⊕ 𝑋 7 ⊕ 𝑋 6 ⊕ 𝑋 ⊕ 1. While 𝑝 min (𝑋) = 𝑋 8 ⊕ 𝑋 4 ⊕ 𝑋 3 ⊕ 𝑋 2 ⊕ 1 is the first primitive polynomial of degree 8 in lexicographic order, 𝑝 kuz is the last such polynomial of weight 5 (see Table C of [START_REF] Lidl | Finite fields[END_REF]).

Unlike the matrix multiplication in Streebog, the one in Kuznyechik cannot be written as a matrix multiplication in F 2 [𝑋]/𝑝 min (𝑋), so that the coset propagation described above for the hash function does not seem applicable to the block cipher.

Discussion

The consequences of the partition-preserving properties of 𝜋 and its non-trivial interaction with the linear layer are hard to assess.

In the literature, we can find other S-Boxes mapping cosets to cosets. For example, monomials map multiplicative cosets of the subfield to multiplicative cosets of the subfield: if 𝐹 : 𝑥 ↦ → 𝑥 𝑑 is a permutation of GF(2 2𝑚 ), then

𝐹 ( 𝛼 𝑖 ⊙ GF(2 𝑚 ) ) = 𝛼 𝑑×𝑖 ⊙ GF(2 𝑚 ) .
If we remove their affine components, the S-Boxes of the AES [START_REF]Advanced Encryption Standard (AES)[END_REF] and Misty1 [START_REF] Matsui | New block encryption algorithm MISTY[END_REF] (among many others) exhibit this behaviour. Yet, despite their appearance in some very prominent targets, multiplicative cosets have never been used in symmetric cryptanalysis. Note that algorithm designers always compose the inverse with unrelated affine layers so as to break its algebraic structure. This conservative decision is likely to prevent the use of multiplicative cosets to attack these ciphers in practice. It is not the case for additive cosets. In fact, the authors of [START_REF] Bannier | Partition-based trapdoor ciphers[END_REF] purposefully built an S-Box mapping additive cosets to additive cosets with the explicit purpose of using this pattern as a backdoor. They show that such a partition can be preserved if the linear layer is chosen carefully and can thus hold for an arbitrary number of rounds. The reason why Bannier et al. considered additive cosets is the following observation.

Partitions in the S-Box of Streebog and Kuznyechik Remark 1. If 𝐹 𝑘 : 𝑥 ↦ → 𝑥 ⊕ 𝑘 is a key addition in F 𝑛 2 and 𝑉 is a vector subspace of F 𝑛 2 , then

𝐹 𝑘 ( 𝑐 ⊕ 𝑉 ) = (𝑘 ⊕ 𝑐) ⊕ 𝑉 ,
so that the partition of F 𝑛 2 into additive cosets of 𝑉 is preserved under 𝐹 𝑘 independently from 𝑘.

In the cipher of Bannier et al., the key schedule can therefore be arbitrarily complex without hindering the backdoor. This property is not shared by the partition into multiplicative cosets.

The only case (other than the TKlog) we can think of where a partition into cosets is mapped to a different partition is that of (plain) discrete logarithms. Indeed, a Hakala-Nyberg type of logarithm operating on GF(2 2𝑚 ), which maps 𝛼 2 𝑚 -1 to 0, always maps multiplicative cosets of the subfield to additive cosets of Z/(2 𝑚 -1)Z. In this case, the multiplication is in the finite field and the addition over the integers. Since these two operations are completely different, we deem it unlikely that a cryptanalysis is aided by this property.

In the end, when looking at the impact of cosets on symmetric primitives, we have one of the following situations:

1. the partition into cosets cannot be iterated since the input partition and output partition are over completely different structures (case of the logarithm);

2. although the S-Box and linear layer are defined over similar structures, a small function was added with the explicit purpose of breaking this similarity (case of the AES and the affine permutation used in its S-Box); or 3. the S-Box and the linear layer were chosen with aligned structures that preserve the same partition so as to purposefully introduce a backdoor in a block cipher (backdoored cipher of of [START_REF] Bannier | Partition-based trapdoor ciphers[END_REF]).

Kuznyechik seems to be in the second situation. While the designers did not disclose their security analysis, it would make sense for them to choose the polynomial used to define the finite field in which the linear layer operates so as not to "align" it with the structure used to construct 𝜋.

However, Streebog falls in neither category. The input and output partitions are defined over the same structure (the finite field) so it is not in the first situation. The S-Box could have been composed with an affine layer breaking its relationship with GF(2 8 ) (like in the AES) or the linear layer could have been defined over a different finite field (like in Kuznyechik) but neither is the case so it does not fall in the second category either. Still, while the linear layer is defined over the same structure as the partitions preserved by the S-Box, these partitions are different and it is unclear how they may interact with the matrix multiplication. It is therefore not obvious that Streebog fits into the third category and the following question remains open.

Open Problem 1. Is there a way to leverage the partition-preserving property of 𝜋 to mount an attack against Streebog?

Conclusion

We have extracted a new structure from 𝜋 which we claim to be the one originally intended by its designers. Its generalization, the TKlog, is obtained by composing a discrete logarithm with a simple layer of arithmetic. The TKlog explains both previous decompositions of 𝜋, thus providing the missing link between these two results.

The knowledge of this decomposition allowed us to explain a very specific partitionpreserving property of 𝜋. Surprisingly, we also found a new expression of the linear layer of Streebog expressed in the same finite field as 𝜋. While we cannot leverage these properties to attack this hash function, we question the wisdom of this design choice. Indeed, when dealing with components defined over identical mathematical structures, academic designers break this alignment e.g. by composing their S-Boxes with unrelated affine permutations. We are of the opinion that it would have been more cautious to do the same in Streebog. We had the intuition for the overall structure of the TKlog because of observations on the TU-decomposition of Biryukov et al. which we present below.

Figure 5 recalls the TU-decomposition of 𝜋 and describes the notations used below. For each input 𝑐 of 𝜈 1 , i.e. for all 𝑐 ∈ F 4 2 , we can define two sets 𝐴 𝑐 and 𝐵 𝑐 as As we can see in Figure 5, if we apply 𝜋 to all the elements of 𝐴 𝑐 we obtain 16 elements out of which 15 are in 𝐵 𝑐 . Furthermore, as we recalled in Equation (1), it holds that { 𝛼 -1 (𝑥, 0), ∀𝑥 ∈ F 4 2 } = { 𝜔(0, 𝑥), ∀𝑥 ∈ F 4 2 } . We then have that 𝐵 𝑐 = 𝜔(𝜈 1 (𝑐), 0) ⊕ 𝐴 0 and that 𝐴 𝑐 is somehow related to 𝐴 0 using a finite field multiplication. We also noticed that these sets had a special relationship with the matrix multiplication used in Streebog.

𝐴 𝑐 = { 𝛼 -1 (𝑥, 𝑥 ⊙ ℐ(𝑐)),
Let L be the 64 × 64 binary matrix used in Streebog and let [𝑎, 0, ..., 0] × L = [𝑎 ′ 0 , ..., 𝑎 ′ 7 ]. If 𝑎 takes all values in 𝐴 𝑐 for some 𝑐 ∈ F 4 2 then 𝑎 ′ 𝑖 takes all values in 𝐴 𝑐𝑖 for some 𝑐 𝑖 . This property holds regardless of the position of 𝑎 in the initial vector. Since we knew from the work of Kazymrov and Kazymrova [START_REF] Kazymyrov | Algebraic aspects of the russian hash standard GOST r 34[END_REF] that L is somehow related to an MDS matrix with coefficients in GF(2 8 ), we deduced that the sets 𝐴 𝑐 had to have a particular relation with this field.

These observations, in combination with the fact that 𝜋 is somehow related to a logarithm [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF], gave us the intuition that the vector spaces 𝐴 𝑐 and the affine spaces 𝐵 𝑐 were in fact respectively the multiplicative and additive cosets of a unique vector space of dimension 4 which we quickly identified as the subfield.

This intuition allowed us to write a first very crude decomposition of 𝜋 which we improved iteratively by re-writing its subcomponents in progressively simpler ways. The final result of this long and tedious process was the decomposition of 𝜋 as a TKlog we then generalized.

Proof of Lemma 3

The following proof is essentially the same as the one in [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]; we only provide it for the sake of completeness.

Proof. We study 𝐹 = Φ 𝜅 ∘ T 𝜅,ℎ,𝑔𝑚,𝑠 ∘ Split -1 𝛽 . Let 𝑎 𝐿 , 𝑎 𝑅 and 𝑏 𝐿 ̸ = 0 be some 𝑚-bit linear masks. By definition, of the LAT and of 𝐹 , we have 12 Implementation of Our Decomposition

The following SAGE [START_REF]SageMath, the Sage Mathematics Software System[END_REF] script prints the lookup table of 𝜋 after generating it using its TKlog decomposition.

  The log-based decomposition.

Figure 1 :

 1 Figure 1: The decompositions of 𝜋 in the literature.

Algorithm 1

 1 A new decomposition of 𝜋. 1: function 𝜋(𝑥 ∈ GF(2 8 )) 𝑖 ← 𝑘 mod 17; 𝑗 ← ⌊𝑘/17⌋ ◁ 𝑥 = 𝛼 𝑖+17𝑗 7: if 𝑖 = 0 then ◁ Case where 𝑥 ∈ GF(2 4 ) 8: return 𝜅 (16 -𝑗) ◁ 𝑖 = 0 so 𝑗 ∈ {1, ..., 15} 9: else 10: return 𝜅(16 -𝑖) ⊕ (𝛼 17 ) 𝑠(𝑗) ◁ 𝑖 ̸ = 0 so 16 -𝑖 ̸ = 16

Figure 2 :

 2 Figure 2: The partition of GF(2 8 ) into multiplicative cosets of GF(2 4 ) * (left), additive cosets of GF(2 4 ) * (right), and the action of 𝜋 on them (arrows).

Figure 3 :

 3 Figure 3: The differential and linear anomalies of random 8-bit TKlog instances, 𝜋, log FLY 𝛼 and log HN 𝛼 .

Figure 4 :

 4 Figure 4: The 64 × 64 matrix L used in Streebog.

Figure 5 :

 5 Figure 5: The propagation of particular vector spaces through 𝜋.

𝒲

  𝐹 [𝑎 𝐿 ||𝑎 𝑅 , 𝑏 𝐿 ||0] = ∑ 𝑟∈GF(2 𝑚 ) ∑ ℓ∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •ℓ+𝑎 𝑅 •𝑟+(𝑏 𝐿 ||0)•𝐹 (𝑟||ℓ) = ∑ ℓ∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •ℓ+𝑏 𝐿 •𝜏 (ℓ) 𝑎 𝐿 •ℓ+𝑎 𝑅 •𝑟+𝑏 𝐿 •𝜈(ℓ/𝑟) .The first term, which corresponds to 𝑟 = 0, is equal to 𝒲 𝜏 [𝑎 𝐿 , 𝑏 𝐿 ]. To evaluate the second term (where 𝑟 ̸ = 0), we set 𝑢 = 𝜈(ℓ/𝑟) so that ℓ = 𝑟 ⊙ 𝜈 -1 (𝑢). Then we write∑ 𝑟∈GF(2 𝑚 ) * ∑ 𝑢∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •(𝑟⊙𝜈 -1 (𝑢))+𝑎 𝑅 •𝑟+𝑏 𝐿 •𝑢 = ∑ 𝑢∈GF(2 𝑚 ) (-1) 𝑏 𝐿 •𝑢 ⎛ ⎝ ∑ 𝑟∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •(𝑟⊙𝜈 -1 (𝑢))+𝑎 𝑅 •𝑟 -𝑏 𝐿 •𝑢 ∑ 𝑟∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •(𝑟⊙𝜈 -1 (𝑢))+𝑎 𝑅 •𝑟 -∑ 𝑢∈GF(2 𝑚 ) (-1) 𝑏 𝐿 •𝑢 ⏟ ⏞ =0The sum over 𝑟 corresponds to the evaluation of a Walsh coefficient of a linear function, namely 𝑟 ↦ → 𝑟×𝜈 -1 (𝑢). As a consequence, it is equal to 0 unless 𝑟 ↦ → 𝑎 𝑅 •𝑟⊕𝑎 𝐿 •(𝑟×𝜈 -1 (𝑢)) is constant.If 𝑎 𝐿 = 0, then this quantity is never constant. Thus, for 𝑎 𝐿 = 0, we have𝒲 𝐹 [𝑎 𝐿 ||𝑎 𝑅 , 𝑏 𝐿 ||0] = 0 + 𝒲 𝜏 [0, 𝑏 𝐿 ] = 0 . However, if 𝑎 𝐿 ̸ = 0, then 𝑟 ↦ → 𝑎 𝑅 • 𝑟 ⊕ 𝑎 𝐿 • (𝑟 ⊙ 𝜈 -1 (𝑢))is constant for exactly one value of 𝑢, in which case the sum is equal to 2 𝑚 . Therefore, we have in this case⎛ ⎝ ∑ 𝑢∈GF(2 𝑚 ) (-1) 𝑏 𝐿 •𝑢 ∑ 𝑟∈GF(2 𝑚 ) (-1) 𝑎 𝐿 •(𝑟⊙𝜈 -1 (𝑢))+𝑎 𝑅 •𝑟 ⎞ ⎠ ∈ {-2 𝑚 , +2 𝑚 }and we conclude that, if (𝑎 𝐿 , 𝑎 𝑅 ) ̸ = (0, 0) and 𝑏 𝐿 ̸ = 0, then𝒲 𝐹 [𝑎 𝐿 ||𝑎 𝑅 , 𝑏 𝐿 ||0] = ( 𝒲 𝜏 [𝑎 𝐿 , 𝑏 𝐿 ] ± 2 𝑚 ) [𝑎 𝐿 ̸ = 0] .The lemma follows.

1

  # !/ usr / bin / sage 2 3 from sage . all import * 4 5 # arithmetic machinery 6 N = 8 7 X = GF (2) . p ol yn o mi al _r i ng () . gen () 8 F = GF (2**8 , name = " a " , modulus = X **8+ X **4+ X **3+ X **2+1) 9 alpha = F . gen ()10xor = lambda x , y : Integer ( x ) . __xor__ ( Integer ( y ) ) 11 12 # arbitrary components 13 s = [0 , 12 , 9 , 8 , 7 , 4 , 14 , 6 , 5 , 10 , 2 , 11 , 1 , 3 , 13] 14 lamb da_vecto rs = [0 x12 , 0 x26 , 0 x24 , 0 x30 ] 15 cstte = 0 xFC 16 17 # subfunction 18 def kappa ( x ) : 19 result = 0 20 for j in xrange (0 , 4) : 21 if ( x >> j ) & 1 == 1: 22 result = xor ( result , la mbda_vec tors [ j ]) 23 return xor ( result , cstte ) 24 25 26 # generating pi 27 # --pi [0] 28 pi = [ kappa (0) ] 29 # --pi [ x ] for x > 0 30 for x in xrange (1 , 2** N ) : 31 l = int ( F . fetch_int ( x ) . _log_repr () ) 32 i , j = l % 17 , floor ( l / 17) 33 if i == 0: 34 y = kappa (16 -j ) 35 else : 36 gf_elmt = ( alpha **17) ** s [ j ] 37 y = xor ( kappa (16 -i ) , gf_elmt . i n t e g e r _ r e p r e s e n t a t i o n () ) 38 pi . append ( y ) 39 40 print pi

Table 1 :

 1 The look up table of the permutation 𝑠 of Z/15Z.

	𝑥	0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
	𝑠(𝑥) 0 12 9 8 7 4 14 6 5 10 2 11 1	3 13

  Partitions in the S-Box of Streebog and Kuznyechik [WBDY98] Hongjun Wu, Feng Bao, Robert H. Deng, and Qin-Zhong Ye. Cryptanalysis of Rijmen-Preneel trapdoor ciphers. In Kazuo Ohta and Dingyi Pei, editors, Advances in Cryptology -ASIACRYPT'98, volume 1514 of Lecture Notes in Computer Science, pages 126-132. Springer, Heidelberg, October 1998. Box 𝜋 was only specified via its look-up table. It is provided in Table 2. The function 𝐹 𝜋 is obtained from 𝜋 via Corollary 3. Its look-up table is provided in Table 3.

	8 Look-up Tables
	The S-

Table 2 :

 2 The look-up table of 𝜋. For example 𝜋(7A) = C6.

	.0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .A .B .C .D .E .F
	0. FC EE DD 11 CF 6E 31 16 FB C4 FA DA 23 C5 04 4D
	1. E9 77 F0 DB 93 2E 99 BA 17 36 F1 BB 14 CD 5F C1
	2. F9 18 65 5A E2 5C EF 21 81 1C 3C 42 8B 01 8E 4F
	3. 05 84 02 AE E3 6A 8F A0 06 0B ED 98 7F D4 D3 1F
	4. EB 34 2C 51 EA C8 48 AB F2 2A 68 A2 FD 3A CE CC
	5. B5 70 0E 56 08 0C 76 12 BF 72 13 47 9C B7 5D 87
	6. 15 A1 96 29 10 7B 9A C7 F3 91 78 6F 9D 9E B2 B1
	7. 32 75 19 3D FF 35 8A 7E 6D 54 C6 80 C3 BD 0D 57
	8. DF F5 24 A9 3E A8 43 C9 D7 79 D6 F6 7C 22 B9 03
	9. E0 0F EC DE 7A 94 B0 BC DC E8 28 50 4E 33 0A 4A
	A. A7 97 60 73 1E 00 62 44 1A B8 38 82 64 9F 26 41
	B. AD 45 46 92 27 5E 55 2F 8C A3 A5 7D 69 D5 95 3B
	C. 07 58 B3 40 86 AC 1D F7 30 37 6B E4 88 D9 E7 89
	D. E1 1B 83 49 4C 3F F8 FE 8D 53 AA 90 CA D8 85 61
	E. 20 71 67 A4 2D 2B 09 5B CB 9B 25 D0 BE E5 6C 52
	F. 59 A6 74 D2 E6 F4 B4 C0 D1 66 AF C2 39 4B 63 B6

Table 3 :

 3 The look-up table of 𝐹 𝜋 , a function CCZ-equivalent to 𝜋. 𝜅,𝑠 (𝑥 ∈ GF(2 2𝑚 ))

	.0 .1 .2 .3 .4 .5 .6 .7 .8 .9 .A .B .C .D .E .F
	0. 8C 42 87 C8 9E DF 13 54 B6 FB 3D 75 29 60 AA E1
	1. BC 70 E8 9A 53 25 BF C6 A9 D2 41 37 FD 84 1B 6E
	2. 0C D2 37 E8 6E BF 53 84 C6 1B FD 25 A9 70 9A 41
	3. 2C E3 59 BD A2 44 F0 15 D7 3E 8A 66 78 9F 21 CB
	4. 9C 8F 9D 11 B0 36 24 A7 F8 73 6B E9 4A C5 DE 52
	5. 1C 98 B3 2F F9 61 4D DB 72 E7 C4 5E 80 1A 35 A6
	6. 4C 1D 20 34 48 5B 6A 7E 83 99 A5 B2 CF D1 E6 F7
	7. FC 0F 0D 01 00 06 04 07 08 03 0B 09 0A 05 0E 02
	8. CC 6A CF A5 1D 7E D1 B2 20 48 E6 83 34 5B F7 99
	9. 5C 34 6A 5B CF F7 A5 99 1D 20 7E 48 D1 E6 B2 83
	A. 7C FB 75 87 E1 13 9E 60 54 AA 29 DF B6 42 C8 3D
	B. 3C A3 D9 7D 32 94 E0 45 67 CE BA 16 58 FF 81 2B
	C. EC 26 4B 62 85 A8 C7 ED 91 B4 D3 FA 1E 39 50 7F
	D. DC C4 1A DB 2F E7 35 F9 4D 80 5E 98 61 A6 72 B3
	E. 6C BA FF 45 7D CE 81 32 E0 58 16 A3 94 2B 67 D9
	F. AC 52 A7 F8 DE 8F 73 24 36 6B 9D C5 E9 B0 4A 11

1: function T 1: function T -1 𝜅,𝑠 (𝑥 ∈ GF(2 2𝑚 )) 𝛼 (𝑣)/(2 𝑚 + 1)

◁ Always an integer as (𝛼 2 𝑚 +1 ) 𝑗 = 𝑣 10:

return 𝛼 2 𝑚 -𝑘+(2 𝑚 +1)𝑠 -1 (𝑗) 𝑘 ∈ F 𝑚 2 so 𝑘 + 1 ∈ {1, ..., 2 𝑚 }

end function 10 How Did We Obtain the TKlog from 𝜋?

* This paper will appear in the IACR Transactions on Symmetric Cryptology.

Strictly speaking, GF(2 4 ) * is not an additive subgroup of GF(2 8 ). Thus, the set {𝑎 ⊕ 𝑥, 𝑥 ∈ GF(2 4 ) * } is not formally an additive coset. However, for the sake of simplicity, we will slightly abuse this term and call such sets "additive cosets of GF(2 4 ) * ".

The official name of this organisation is "Технический Комитет По Стандартизации Криптографическая Защита Информации", which stands for "Technical Committee for Standardization of cryptographic information protection"

 4 Equivalently, we can write that the linear part of 𝜅 mapping 𝑦 ∈ F 𝑚 2 to 𝜅(𝑦) ⊕ 𝜅(0) ∈ GF(2 2𝑚 ) maps F 𝑚 2 to a vector space in direct sum with the subfield GF(2 𝑚 ).

Partitions in the S-Box of Streebog and Kuznyechik

Acknowledgement

We thank the IACR ToSC reviewers for their careful reading and comments. We also thank Anne Canteaut for remarks that greatly improved the presentation of this paper. The work of the author was financed by a post-doc grant from the Fondation Sciences Mathématiques de Paris (FSMP.)

Partitions in the S-Box of Streebog and Kuznyechik

The existence of the TU-decomposition of Biryukov et al. is obviously a direct consequence of this theorem. The relationship between this decomposition and the original TKlog structure further allows us to better understand some of the patterns existing in this decomposition.

First, the component Biryukov et al. called 𝜈 0 plays the role of 𝜏 in Theorem 2. Since 𝜏 is essentially a logarithm in base 𝛼 -(2 𝑚 +1) , it is not surprising that 𝜈 0 was noted in [START_REF] Perrin | Exponential s-boxes: a link between the s-boxes of BelT and Kuznyechik/Streebog[END_REF] to be affine-equivalent to a logarithm.

Second, the linear layers 𝛼 and 𝜔 of the original decomposition are basically splitting GF(2 2𝑚 ) into GF(2 𝑚 ) 2 and then putting it back together, hence the relation presented in Equation 1. Furthermore, the output layer 𝜔 is more complex than the input layer 𝛼 since it also evaluates the linear part of 𝜅.

Properties Explained by the TU-Decomposition

Efficient Hardware Implementation. The knowledge of the decomposition from Theorem 2 allowed Biryukov et al. to significantly improve the implementation of 𝜋: they made a circuit implementing such a permutation with an area and delay divided by 2.5 and 8 respectively [BPU16b, Table 8]. We can expect similar gains for all 8-bit TKlogs.

Visual Artefact in the LAT. Biryukov et al. used a particular visual artefact in the LAT of 𝜋 to perform the first step of their TU-decomposition, namely the presence of columns with a lower number of different coefficients than the others. They showed that this pattern was a direct consequence of the structure they identified in this S-Box, namely the one imposed by Theorem 2. As a consequence, we can generalize their result to all TKlog instances. Lemma 3. Consider a TKlog instance T 𝜅,𝛼,𝑠 , let Split 𝛽 , 𝜏, 𝜎, 𝜈 and 𝜑 be the subfunctions used to implement its TU-decomposition as presented in Algorithm 2, and let 𝜑 𝜅 : GF(2 2𝑚 ) → GF(2 𝑚 ) × GF(2 𝑚 ) be the affine bijection such that 𝜑 𝜅 (𝜅(𝑥) ⊕ 𝑣) = (𝑥, 𝑣).

We further let 𝐹 be the permutation of GF(2 𝑚 ) 2 defined by 𝐹 = 𝜑 𝜅 ∘ T 𝜅,𝑠 ∘ Split -1 𝛽 , so that it consists in the TU-decomposition of T 𝜅,𝑠 without the input and output linear layers. Then, for (𝑎 𝐿 , 𝑎 𝑅 ) ̸ = (0, 0) and 𝑏 𝐿 ̸ = 0, we have

where [𝑎 𝐿 ̸ = 0] = 0 if 𝑎 𝐿 = 0 and 1 otherwise.

The proof of this lemma is essentially the same as the one Biryukov et al. gave in the full version of their paper [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]. For the sake of completeness, we also give it in Appendix 11.

Since 𝜏 is essentially a discrete logarithm, its non-linearity is always high, so that the pattern is always visible. Indeed, because of this high non-linearity, |𝒲 𝜏 [𝑎 𝐿 , 𝑏 𝐿 ]| can only take values much lower than 2 𝑚 , which implies that the low contrast will always be present.

In [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF], the authors of the original decomposition remarked that they had been lucky since the conjunction of circumstances that lead to the success of their decomposition seemed unlikely. In their own words (page 19 of [START_REF] Biryukov | Reverse-engineering the S-box of streebog, kuznyechik and STRIBOBr1[END_REF]):

[the visual pattern] is caused by the conjunction of three elements:

• the use of a multiplexer,

• the use of finite field inversion, and

• the fact that 𝜈 0 has good non-linearity.