On the S-Box of Streebog and Kuznyechik

Cryptography is the science dealing with information security: how can we communicate in such a way that an eavesdropper cannot spy on us? As communications are done via computers, the techniques enabling such protections are algorithms that prevent attackers from accessing the information without using a key: unless the key is known, it is impossible to read/modify the data. When the same key is used to process the information before sending and after receiving, we talk about symmetric cryptography.

It is necessary to continuously analyse these algorithms as they may eventually turn out to have flaws. This threat is not theoretical as cryptographic algorithms have failed in this way in the past. To take a recent example, the hash function SHA-1 was found to yield collisions, a critical failure for such an algorithm [4].

The algorithms that are used are usually those that have been standardized by some standardizing body (e.g. the American NIST, ISO/IEC, etc.). Each standardizing body has its own internal process for choosing ciphers.

This process can be completely opaque as evidenced by the standardization of the DUAL_EC PRNG by the American NIST. This algorithm turned out to have been imposed by the NSA and to likely contain a backdoor, as detailed in [8]. In this case, the algorithm was standardized basically because the NSA said it had to be. This is not a unique instance: the Russian algorithms discussed on this page were also designed secretly and then standardized without any competition or other forms of transparency. It is obviously very difficult to trust algorithms standardized in this fashion: where is the third party analysis? Where are the designers' explanations?

In order to foster trust, a much better strategy consists in organizing open competitions. For instance the AES and hash function NIST competitions yielded the standardization of algorithms that are now well trusted. This trust comes from the analysis received by these algorithms before they were standardized and from the quality of the theoretical frameworks used to construct them, frameworks which were carefully explained by their designers.

The AES, SHA-3 and the DUAL_ EC algorithms were all standardized by the same institution (the NIST), suggesting that assessing the quality of a standard is not as simple as looking at its origin.

Streebog is a cryptographic hash function. It was standardized by the Russian Federation in 2012. Kuznyechik is a block cipher which was standardized by the same country in 2015.

Both are intended to be used in Russia. At the time of this writing, their authors are also pushing for their standardization by ISO/IEC.

One of the basic building block to construct symmetric algorithms is the block cipher. For example the AES, one of the most widely used and well studied symmetric cryptographic algorithms, is a block cipher. So is Kuznyechik. It is also common to use a block cipher to construct a hash function using a block cipher: it is the case of SHA-2, a very common hash function, and of Streebog.

Block ciphers are built by iterating a so-called round function whose goal is to provide a weak version of the properties that the block cipher is expected to fulfil. By iterating these rounds, the properties of their composition gets stronger, and after sufficiently many rounds it provides these properties in full. A key property is non-linearity. In practice, it is usually provided by a small component called S(ubstitution)-box. An S-box is a function operating on a small enough input that its output can be specified by its lookup table. The round function then contains the parallel application of said S-box over the whole state.

The Russian algorithms both use the same S-box, π. It is specified via its lookup table (Figure 1).

The cryptographic properties of the S-box play a crucial role in the security of the algorithm because they are the only source of non-linearity. They are also at the center of the security arguments given by algorithm designers. In fact, designers are expected to explain how the S-box they used was designed and why they chose the structure their S-box has. For example, the AES has an S-box which is based on the multiplicative inverse in the finite field \(\mathrm{GF}(2^8)\). This choice is motivated by the fact that both the linearity and the differential uniformity ¹ of this permutation are the lowest known to be possible.

While the multiplicative inverse, and in fact the very S-box of the AES, are popular choices for constructing 8-bit S-boxes, they are not the only possiblity. I made a survey of the literature and compiled a list of all the 8-bit S-boxes I could get my hands on² during my PhD [2]. They are sorted by structure in Figure 2. As we can see, the structures used vary a lot, from clear mathematical description to block cipher-like structures. These differences correspond to different goals. While it is necessary to have good cryptographic properties, it is also essential that the S-box be easy to implement for example in hardware. Depending on the priority of these constraints, the designers will use different structures.

In order to benefit from the easy implementation allowed by a given structure, it is necessary that the structure be public. More importantly, in order for cryptographers to be able to analyse the cipher properly, it is necessary that they are given all the information available and in particular the structure used to construct the S-box. It could be that the S-box interacts in an undesirable way with other components of the cipher and this interaction can only be noticed if the structure is known.

To see an example of the kind of constraints and trade-offs that naturally occur when designing an S-box, you can have a look at at this e-mail sent to the CFRG mailing list by one of the designers of the Belarussian standard, BelT. He explains why they decided to choose an S-box based on a discrete exponentiation—a choice I personally see nothing wrong with.

The authors of Streebog and Kuznyechik have provided little to no information about their design process. Several cryptographers have tried to ask them about the structure of their S-box during conferences. The usual answer was equivalent to saying that they were picked at random from some set. They also claim to have lost the generation algorithm. Given the importance of the S-box, this loss should be worrying in and of itself.

With my co-authors Aleksei Udovenko and Alex Biryukov, we first identified two different decompositions of π which were published at two peer-reviewed venues: the conference EUROCRYPT'16 for the first [6] and the IACR Transactions on Symmetric Cryptology for the second [7]. However, below, I will mostly talk about the third decomposition which has been published³ in a later edition of the IACR Transactions on Symmetric Cryptology [1]. It is based on a structure which I called TKlog.

Any function operating on \(n\) bits can be written as a function over a finite field \(\mathbb{F}_{2^n}\). The exact correspondence between the finite field elements and their binary representation is not unique; it is determined by a specific polynomial. In the case of \(\pi\), this field is \(\mathbb{F}_{2^8}\). It contains, as a subset, the finite field \(\mathbb{F}_{2^4}\). As these sets are fields, we can define an addition (which here corresponds to a XOR, denoted "\(\oplus\)") and a multiplication⁶ (denoted "\(\odot\)").

The S-box \(\pi\) (as well as all TKlogs) maps the subset \(\{ a \odot x, x \in \mathbb{F}_{2^4}^* \}\) of \(\mathbb{F}_{2^8}\) to a subset of the form \(\{ b \oplus x, x \in \mathbb{F}_{2^4}^* \}\). This phenomenon is summarized in Figure 3. This means that \(\pi\) maps a simple partition of its input to a simple partition of its output.

Even worse, all \(x \in \mathbb{F}_{2^8}\) can be written⁷ as \(a \odot b\) with \(b \in \mathbb{F}_{2^4}\) and we then have that if \(a \neq 1\) then \(\pi(a \odot b) = f(a) \oplus g(b)\) for some functions \(f\) and \(g\). In other words, the output can divided into two halves, each of which depends only on one half of the input. However, in the input, the definition of these halves is not linear. As an other consequence, the way \(\pi\) acts on each subset \(\{ a \odot x, x \in \mathbb{F}_{2^4}^* \}\) of \(\mathbb{F}_{2^8}\) for \(a \neq 1\) is always the same. Note also that \(g\) is a permutation of \(\mathbb{F}_{2^4}\), meaning that its output is also in this subset.

First of all, that is very strong algebraic structure where they previously claimed that there was none.

Second, Arnaud Bannier established in his PhD thesis [10] that, in order to construct a block cipher with a backdoor of a certain type, it was necessary to construct an S-box mapping sets of the form \(\{ b \oplus x, x \in V \}\) to ones of the form \(\{ b \oplus x, x \in W \}\), where \(V\) and \(W\) are vector subspaces of \(\mathbb{F}_{2^n}\) (for instance, \(\mathbb{F}_{2^4}\) is a vector subspace of \(\mathbb{F}_{2^8}\)).

That is not quite the situation we have here as \(\pi\) has such a partition in its output but not in its input. However, in the case of Streebog, the linear layer interacts in a weird way (which we have yet to completely understand) with sets of both shapes, i.e. \(\{ b \oplus x, x \in \mathbb{F}_{2^4} \}\) and \(\{ b \odot x, x \in \mathbb{F}_{2^4} \}\).

By the way, this linear layer was originally specified as a \(64 \times 64\) binary matrix, i.e. using only 0 and 1, while it is simply described by an \(8 \times 8\) matrix with elements in \(\mathbb{F}_{2^8}\). It is strange that this structure was not disclosed by the designers, especially considering that it is a natural choice: such matrices defined over \(\mathbb{F}_{2^8}\) are common in symmetric cryptography; the AES itself uses one. Why then keep it secret?

Incidentally, the design process of this matrix is also unknown. Reverse-engineering it is an open problem!

First of all, I would like to emphasize that I have not found an attack leveraging these properties.

Still, I don't know the answer to the question above and, to put it bluntly, I don't think we need to know. What I think matters is whether or not this structure can lead to attacks against these algorithms. As explained in the answer to the previous question, it is a possibility. If it is indeed an exploitable flaw, why and how it ended up in these ciphers is their designers' problem, not the users'. The generation process of their S-box may have been compromised by someone else for all we know—which highlights the main issue behind these algorithms: while I have recovered the structure that was used to generate this component…

That is why I recommend that, until their designers provide a detailed explanation of their complete design process, you do not use these algorithms and, should you be in a position to make such a decision, that you do not standardize them.