Partition-Based Trapdoor Ciphers

Abstract

Trapdoors are a two-face key concept in modern cryptography. They are primarily related to the concept of trapdoor function used in asymmetric cryptography. A trapdoor function is a one-to-one mapping that is easy to compute, but for which its inverse function is difficult to compute without special information, called the trapdoor. It is a necessary condition to get reversibility between the sender and the receiver for encryption or between the signer and the verifier for digital signature. The trapdoor mechanism is always fully public and detailed. The second concept of trapdoor relates to the more subtle and perverse concept of mathematical backdoor, which is a key issue in symmetric cryptography. In this case, the aim is to insert hidden mathematical weaknesses, which enable one who knows them to break the cipher. Therefore, the existence of a backdoor is a strongly undesirable property. This book deals with this second concept and is focused on block ciphers or, more specifically, on substitution-permutation networks (SPN). Inserting a backdoor in an encryption algorithm gives an effective cryptanalysis of the cipher to the designer.

Preface

1. Introduction

Despite the fact that in the late 90s/early 2000s, citizens have partially obtained the freedom for using cryptography, the recent years have shown that more than ever, governments and intelligence agencies still try to control and bypass the cryptographic means used for the protection of data and of private life. Snowden leaks have been a first upheaval. A tremendous number of secret projects conducted by NSA and GCHQ have been revealed to the public opinion. They have shed a new light on the permanent attempt to control the use of cryptography by a growing number of governments.

The recurring approaches and attempts consist in making the implementation of backdoors mandatory. The simplest and naive approach consists in enforcing key escrowing at the operators’ level. But point-to-point encryption solutions like telegram, signal or proton mail enable to prevent it. A number of different backdoor techniques are regularly mentioned or proposed.

The most critical aspect in embedding backdoors lies on the fact that hackers or analysts may find them more or less easily and worse may exploit them. This is the reason why operators or developers are very reluctant to accept backdoors until now. In case of leak, they inevitably lose users’ confidence and favor the development of trusted services abroad. In fact, the backdoor issue arises due to the fact that only implementation backdoors (at the protocol/implementation/management level) are generally considered.

In this book, we address the most critical issue of backdoors: mathematical or by-design backdoors. In other words, the backdoor is put directly in the mathematical design of the encryption algorithm. While the algorithm is totally public, proving that there is a backdoor, identifying it and exploiting it, is generally an intractable problem, unless you know the backdoor [1]. To some extent, the RSA’s Dual_EC_DRBG standard case falls within this category [2]. Other nonpublic examples are known within the military cryptanalysis community and partially revealed to the public, thanks to the 1995 Hans Buehler case [3]. This kind of backdoor is the most difficult one to address and there is quite no public work on that topic. It is generally the technical realm of a few among the most eminent intelligence agencies, namely NSA and GCHQ, which moreover have the ability and power to step in and to influence the international standardization processes. Our objective is to explain that it is probably possible to design and put such backdoors. In this book, we consider a particular case among many other possibilities of trapdoors.

This book is organized as follows. In the next section, we explore the concept of backdoors and trapdoors and we identify two main categories. We also present the state-of-the-art, history and previous work regarding backdoors, mostly in symmetric cryptography. The rest of this book focuses on substitution-permutation networks (or SPN for short) which are a special class of block encryption systems, mapping a partition of the plaintexts to a partition of the ciphertexts, independently of the round keys used.

Chapter 2 explores the concept of linear partitions and their relationships with substitution-permutation networks. We show in Section 2 that in our case, the study of the full cipher can be restricted to the substitution layer without loss of generality. Then in Section 3, we explore this latter primitive and show that the problem can be restricted further to the study of a single S-box.

In Chapter 3, we discuss how to design a suitable S-box which preserves a linear partition and, at the same time, which resists linear and differential cryptanalysis. From those theoretical results, we have designed a full AES-like encryption system, called BEA-1, presented in Chapter 4. Section 1 gives the full specifications of this cipher. Then Section 2 deals with the design of its backdoor. In Section 3, we sketch the basic ideas underlying the BEA-1 cryptanalysis while in Section 4, we present our cryptanalysis of BEA-1 under the assumption we have the full knowledge of the backdoor.

Chapter 5 concludes this book and explore new ideas and trends in encryption backdoors. The full description of cryptographic primitives used in BEA-1 is given in Appendix.

2. The concept of backdoor

2.1. Definition and classification proposal

Trapdoors are a two-face key concept in modern cryptography. They are primarily related to the concept of trapdoor function used in asymmetric cryptography. A trapdoor function is a one-to-one mapping that is easy to compute, but for which its inverse function is difficult to compute without special information, called the trapdoor. It is a necessary condition to get reversibility between the sender and the receiver for encryption or between the signer and the verifier for digital signature. The trapdoor mechanism is always fully public and detailed. The security and the core principle are based on the existence of a secret information, the private key, which is essentially part of the trapdoor. In other words, the private key can be seen as the trapdoor.

The second concept of trapdoor relates to the more subtle and perverse concept of mathematical backdoor, which is a key issue in symmetric cryptography. In this case, the aim is to insert hidden mathematical weaknesses which enable one who knows them to break the cipher. Nonetheless, mathematical backdoors may be extended to asymmetric cryptography, see for example the case of the DUAL EC_DRBG [2], or the case of trapdoor primes addresses recently in [4]. Therefore, the existence of a backdoor is a strongly undesirable property.

In the rest of this section, we will oppose the term of trapdoor, the desirable property, to that of backdoor, the undesirable one. While the term of trapdoor has been already used in the very few literature covering the second face of this problem, we suggest however to use the term of backdoor to describe the issue of hidden mathematical weaknesses. This would avoid ambiguity and maybe would favor the research work around a topic which is nowadays mostly addressed by governmental entities in the context of cryptography control and regulations.

Inserting backdoors in encryption algorithms underlies quite systematically the choice of cryptographic standards (DES, AES…). The reason is that the testing, validation and selection processes are always conducted by governmental entities (NIST or equivalent) with the technical support of secret entities (NSA or equivalent). So an interesting and critical research area is: “how easy and feasible is it to design and to insert backdoors in encryption algorithms?”. In this book, we intend to address one very particular case of this question. It is important to keep in mind that a backdoor may be itself defined in the following two ways.

• As a “natural weakness” known, but none disclosed, only by the tester, validator or final decision-maker. The best historic example is that of the differential cryptanalysis. Following Biham and Shamir’s seminal work in 1991 [5], NSA acknowledged that it was aware of that cryptanalysis years ago [6]. Most of experts estimate that it was nearly 20 years ahead. However a number of non public, commercial block ciphers in the early 90s might have been be weak with respect to differential cryptanalysis.

• As an intended design weakness put by the author of the algorithm. To the authors knowledge, there is no known case for public algorithms yet.

As far as symmetric cryptography is concerned, there are two major families of cipher systems for which the issue of backdoor must be considered differently.

• Stream ciphers. Their design complexity is rather low since they mostly rely on algebraic primitives: LFSRs and Boolean functions which have intensely been studied in the open literature Until the late 70s, backdoors relied on the fact that quite all algorithms were proprietary and hence secret. It was then easy to hide nonprimitive polynomials, weak-combining Boolean functions… The Hans Buehler case in 1995 [3] shed light on that particular case.

• Block ciphers. This class of encryption algorithms is rather recent (end of the 70s for the public part). They exhibit so a huge combinatorial complexity that it is reasonable to think to backdoors. As described in [7] for a κ-bit secret key and an m-bit input/output block cipher there are ${{((2}^m)!)}^{2^{\kappa }}$ possible such block ciphers. For such an algorithm, the number of possible internal states is so huge that we are condemned to have only a local view of the system, that is, the round function or the basic cryptographic primitives. We cannot be sure that there is no degeneration effect at a higher level. This point has been addressed in [7] when considering linear cryptanalysis. Therefore, it seems reasonable to think that this combinatorial richness of block ciphers may be used to hide backdoors.

Since block ciphers are now the most widely used encryption algorithms by the general public and the industry, we will focus on them in the rest of this book. Backdoors in stream ciphers have quite never been exposed to the public.

2.2. Previous work

Regarding the previous work, we can consider two aspects. The first one relates to authors who have considered structures on the input and output spaces of round functions to build key distinguishing or key recovery attacks. In this case, it is possible to suppose that those structures are “natural” structures. The second case is directly linked to the topic covered in this book. It relates to the design of backdoors based on such structures. Exploiting these hidden structures then leads to a tractable cryptanalysis. In this respect, we can see those structures as “intended” and no longer “natural”.

2.2.1. Attacks using space structures

Among the very first previous works that have considered structures in the plaintext and ciphertext spaces is the contribution of Evertse [8]. This paper introduced the linear structures for block ciphers, which map a subspace of ${\mathbb{F}}_2^m\times {\mathbb{F}}_2^{\kappa }$ (the product of the plaintext and ciphertext spaces) onto a subspace of ${\mathbb{F}}_2^m$ (the ciphertext space). Then, the author showed that if such a linear structure exists, then known-plaintext and chosen-plaintext attacks faster than exhaustive search are possible.

Later, Leander et al. [9] developed a new cryptanalysis, called invariant subspace attack, breaking the PRINTCipher [10] for a significant fraction of its keys. The general idea of this attack can be outlined as follows. Let F denote the SP-layer of a substitution-permutation network, that is, the round function without the key addition. Then, assume that F maps a coset of a given subspace V to another coset of V. In other words, there exist a and b such that $F(a+V)=b+V$. Here, the addition is made in ${\mathbb{F}}_2^n$ and hence corresponds with the XOR operation. The round function associated with the round key k is then defined by $F_k:x\mapsto F(x+k)$. If the round key k belongs to the coset a + b + V, then it holds that

$F_k(b+V)=F(b+k+V)=F(a+V)=b+V,$E1

hence the name of invariant subspace. Therefore, if every round key lies in this particular coset, the affine subspace b + V is preserved by the full encryption process. Such a property enables a very efficient distinguisher. As additional results, they also showed that the invariant subspace attack

• implies a truncated differential attack to be possible (the probability of the truncated differential characteristic is however highly key-dependent);

• implies the existence of strongly biased linear approximations for weak keys (independently of the number of rounds).

This attack has been generalized in 2015 by Leander et al. [11]. They proposed a generic algorithm that is able to detect invariant subspaces. Indeed, their initial invariant subspaces on PRINTCipher were found empirically.

Following the idea of the invariant subspace attack, Grassi et al. [12] introduced the subspace trail cryptanalysis. Given r + 1 subspaces $V^{[0]},\dots ,V^{[r]}$, it is assumed that the image of any coset of V^[i] under the SP-network is included in a coset of V^[i+1]. That is to say, for each a^[i], there exists a^[i+1] such the following inclusion holds

$F(a^{[i]}+V^{[i]})\subseteq a^{[i+1]}+V^{[i+1]}.$E2

In this case, it is easy to see the all round functions F_k inherit such a property. The family of subspaces ${(V^{[i]})}_{i\le r}$ is said to be a subspace trail. Naturally, the dimension of V^[i] must be lower than or equal to the dimension of V^[i+1]. In contrast to the invariant subspace attack, Grassi et al. relaxed the assumption that the coset has to be invariant. Here, the considered subset becomes the coset of possibly different increasingly dimensional subspaces throughout the encryption. However, the authors also required this property to hold for each coset of V^[0] instead of one. Therefore, this cryptanalysis is not a generalization but a variation of the invariant subspace attack. As will become clear in Section 2 of Chapter 2, the family of backdoors covered in this book is closely related to constant-dimensional subspace trails.

Let us mention that in [13], the authors introduced nonlinear invariant subspaces by considering a general Boolean function g such that $g(F(x))\oplus g(x)$ is constant. Finally, Table 1.1 summarized the structures considered by the attacks presented in this section and compared it with our work.

Work	Structure	Key dependence
Evertse [8]	Linear structure (if any)	Key independent
Leander et al. [9, 11]	Exact coset	Round key dependent
Grassi et al. [12]	Coset independent	Round key independent
Our approach	Coset independent	Round key independent

Table 1.1.

Comparison of existing work with respect to input and output space structures.

2.2.2. Backdoor design and structures

One of the first trapdoor ciphers was created in 1997 by Rijmen and Preneel [14]. Their S-boxes are constructed to have one high correlation between the zero mapping and a sum of certain output bits. The knowledge of this correlation yields a high potential linear trail which is used to recover a part of the key with linear cryptanalysis. Such a weakness is generally pointed out by the first line of the S-boxes’ correlation matrices. Yet, if the output size of the S-boxes is large enough, their computation is too expensive. Relying on this fact, the authors claimed that their trapdoor is undetectable, even if one knows its global design. Nevertheless, Wu et al. [15] disproved this by discovering a way to recover the trapdoor. It is worthwhile to mention that in practice, if a real cipher containing a trapdoor is given, the presence of the trapdoor will certainly not be revealed.

More recently in [16], the authors created non-surjective S-boxes embedding a parity check to create a trapdoor cipher. The message space is thus divided into cosets and leads to create an attack on this DES-like cipher in less than 2²³ operations. The security of the whole algorithm, particularly against linear and differential cryptanalysis is not given and the authors admit that their attack is dependent on the first and last permutation of the cipher. Finally, the non-surjective S-boxes may lead to detect easily the trapdoor by simply calculating the image of each input vector. This problem is naturally avoided in a substitution-permutation network in which S-boxes are bijective by definition.

Our approach is mainly a generalization of the ideas presented by Paterson in [17]. In this article, a DES-like trapdoor cipher exploiting a weakness induced by the round functions is presented. The group generated by the round functions acts imprimitively on the message space. In other words, the round function preserves a partition of the message space no matter the round key used, and hence, the same applies to the full cipher. This partition forms the trapdoor. Paterson then introduced a trapdoor cipher composed of 32 rounds and using an 80-bit key. The trapdoor enables recovery of the key using 2⁴¹ operations and 2³² chosen plaintexts. Even if the mathematical material to build the trapdoor is given, no general algorithm details the S-boxes’ construction. Furthermore, as the author says, S-boxes using these principles are incomplete: half of the ciphertext bits are independent of half of the plaintext bits. Finally, the security against a differential attack is said to be not as high as one might expect. Moreover, the author wondered whether the partition of the message space had to be linear, that is to say, made up with every coset of a linear subspace. Caranti et al. [18] provided a first answer to Paterson’s question, by proving that if the group generated by the round functions is imprimitive, then the partition of the message space must be linear. In his thesis [19], Harpes considered trapdoor ciphers mapping a partition of the plaintexts to a partition of the ciphertexts. As these partitions are not necessarily equal, this family generalizes Paterson’s one. Harpes suggested using this trapdoor with its partitioning cryptanalysis.

Partition-Based Trapdoor Cipher

This chapter intends to study Substitution-Permutation Networks mapping a partition of the plaintexts to a partition of the ciphertexts, independently of the round keys used. All the results of this and the following chapters comes from [20].

1. Linear partitions

Let us begin with some notations and conventions.

Notation 2.1. Let m and n denote positive integers. For two maps f and g, the composition $g\circ f$ (or simply gf) denotes the evaluation of f followed by g. For any set E, let #E denotes its cardinality. If F is a subset of E, F^c denotes its complement.

Let us denote the Galois field of order two by ${\mathbb{F}}_2$ and $0_n=(\mathrm{0,}\dots ,0)$ the zero vector of ${\mathbb{F}}_2^n$. All the vector spaces considered in this chapter are over the finite field ${\mathbb{F}}_2$. It is worthwhile to mention that ${({\mathbb{F}}_2^n)}^m$ will be often identified with ${\mathbb{F}}_2^{nm}$. The concatenation of two vectors x and y is denoted by (x || y).

An n-bit S-box is any permutation of ${\mathbb{F}}_2^n$. If x and y are two elements of ${\mathbb{F}}_2^n$, then $⟨x,y⟩={\sum }_{i=0}^{n-1}{x}_i{y}_i$. If $L:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^m$ is a linear map, define $L^{⊺}:{\mathbb{F}}_2^m\to {\mathbb{F}}_2^n$ by $⟨L^{⊺}(x),y⟩=⟨x,L(y)⟩$ for every $(x,y)\in {\mathbb{F}}_2^n\times {\mathbb{F}}_2^m$. In other words, $L^{⊺}$ is the transpose of L for the bilinear form $⟨\cdot ,\cdot ⟩$.

Finally, we will denote the elements of ${\mathbb{F}}_2^n$ using the hexadecimal notation. For instance, the element $(\mathrm{1,0,1,1,1})$ of ${\mathbb{F}}_2^5$ is denoted by 17.

Since we are concerned with ciphers that associate a partition of the ciphertext space to another partition of the plaintext space, let us introduce the following definition.

Definition 2.2. Let f be a permutation of E and $\mathcal{A}$, $\mathcal{B}$ be two partitions of E. Let $f(\mathcal{A})$ denote the set $\mathrm{\{}f(A)|A\in \mathcal{A}\mathrm{\}}$. We say that f maps $\mathcal{A}$ to $\mathcal{B}$ if $f(\mathcal{A})=\mathcal{B}$. If $\mathcal{A}=\mathcal{B}$, we says that f preserves the partition $\mathcal{A}$.

The two partitions $\mathrm{\left\{}\mathrm{\right\{}x\mathrm{\left\}}\right|x\in E\mathrm{\}}$ and {E} are called the trivial partitions of E. Observe that, for any permutation f of E,

$\begin{array}{ccc}f(\mathrm{\{}\mathrm{\left\{}x\mathrm{\right\}}|x\in E\mathrm{\}})=\mathrm{\{}\mathrm{\left\{}x\mathrm{\right\}}|x\in E\mathrm{\}}& \text{and}& f(\mathrm{\{}E\mathrm{\}})=\mathrm{\left\{}E\mathrm{\right\}}.\end{array}$E3

That is, every permutation preserves the two trivial partitions. Moreover it should be highlighted that if f maps $\mathcal{A}$ to $\mathcal{B}$ and if $\mathcal{A}$ is nontrivial, then so is $\mathcal{B}$.

Example 2.3. Let E denote the set $〚0,8〚$ and consider the two partitions $\mathcal{A}$, $\mathcal{B}$ of E defined by $\mathcal{A}=\mathrm{\left\{}\mathrm{\right\{}\mathrm{0,1,4}\mathrm{\}},\mathrm{\{}\mathrm{2,6}\mathrm{\}},\mathrm{\{}\mathrm{3,7}\mathrm{\}},\mathrm{\{}5\mathrm{\left\}}\mathrm{\right\}}$ and $\mathcal{B}=\mathrm{\left\{}\mathrm{\right\{}\mathrm{0,2,7}\mathrm{\}},\mathrm{\{}1\mathrm{\}},\mathrm{\{}\mathrm{3,5}\mathrm{\}},\mathrm{\{}\mathrm{4,6}\mathrm{\left\}}\mathrm{\right\}}$. Let f be the permutation of E defined by

$\begin{array}{llllllll}0\mapsto 7,\hfill & 1\mapsto 0,\hfill & 2\mapsto 3,\hfill & 3\mapsto 6,\hfill & 4\mapsto 2,\hfill & 5\mapsto 1,\hfill & 6\mapsto 5,\hfill & 7\mapsto 4.\hfill \end{array}$E4

By definition,

$\begin{array}{lll}f(\mathcal{A})=\mathrm{\{}\hspace{0.17em}f(A)|A\in \mathcal{A}\mathrm{\}}\hfill & =\hfill & \mathrm{\{}\hspace{0.17em}f(\mathrm{\{}0,1,4\mathrm{\}}),f(\mathrm{\{}2,6\mathrm{\}}),f(\mathrm{\{}3,7\mathrm{\}}),f(\mathrm{\left\{}5\mathrm{\right\}})\mathrm{\}}\hfill \\ \hfill & =\hfill & \mathrm{\left\{}\begin{array}{cccc}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\mathrm{\{}7,0,2\mathrm{\}},& \mathrm{\{}3,5\mathrm{\}},& \hspace{0.17em}\mathrm{\{}6,4\mathrm{\}},& \hspace{0.17em}\mathrm{\left\{}1\mathrm{\right\}}\end{array}\mathrm{\right\}}.\hfill \end{array}$E5

The equality $f(\mathcal{A})=\mathcal{B}$ holds, and thus f maps the partition $\mathcal{A}$ to $\mathcal{B}$.▴

Lemma 2.4. Let f be a permutation of E and $\mathcal{A}$, $\mathcal{B}$ be two partitions of E. If for any part A of $\mathcal{A}$, f(A) is a part of $\mathcal{B}$, then f maps $\mathcal{A}$ to $\mathcal{B}$.

In this chapter, we will consider a special kind of partitions that is composed of all the cosets of a linear subspace. Such partitions have already been introduced by [19, Definition 4.4] and are recalled below.

Definition 2.5 (linear partition). Let $\mathcal{A}$ be a partition of ${\mathbb{F}}_2^n$. Let V denote its part containing 0_n. The partition $\mathcal{A}$ is said to be linear if V is a subspace of ${\mathbb{F}}_2^n$ and if every part of $\mathcal{A}$ is a coset of V in ${\mathbb{F}}_2^n$, in other words, if

$\mathcal{A}=\mathrm{\{}x+V|x\in {\mathbb{F}}_2^n\mathrm{\}}={\mathbb{F}}_2^n/V.$E6

We denote $\mathcal{L}(V)$ such a partition.

Remark 2.6. It turns out that the linear partitions associated with the two trivial subspaces of ${\mathbb{F}}_2^n$, that is {0_n} and ${\mathbb{F}}_2^n$, correspond with the two trivial partitions of ${\mathbb{F}}_2^n$. Moreover, if V is a nontrivial subspace of ${\mathbb{F}}_2^n$, then the linear partition $\mathcal{L}(V)$ is also nontrivial.

Example 2.7. Consider the subspaces V and W of ${\mathbb{F}}_2^5$ defined by

$\begin{array}{ccc}V=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})=\mathrm{\{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}},\mathtt{1}\mathtt{\text{D}}\mathrm{\}}& \text{and}& W=\text{span}(\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{2})=\mathrm{\{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{2},\mathtt{1}\mathtt{\text{C}}\mathrm{\}}.\end{array}$E7

Since both V and W are two-dimensional subspaces of ${\mathbb{F}}_2^5$, the quotient spaces $\mathcal{L}(V)={\mathbb{F}}_2^5/V$ and $\mathcal{L}(W)={\mathbb{F}}_2^5/W$ are three-dimensional. In other words, the two linear partitions $\mathcal{L}(V)$ and $\mathcal{L}(W)$ have 2³ = 8 parts. It can be verified that

$\begin{array}{l}\mathcal{L}(V)=\mathrm{\{}V,\mathtt{0}\mathtt{1}+V,\mathtt{0}\mathtt{2}+V,0\mathtt{3}+V,\mathtt{0}\mathtt{8}+V,\mathtt{0}\mathtt{9}+V,\mathtt{0}\mathtt{A}+V,\mathtt{0}\mathtt{B}+V\mathrm{\}},\\ \mathcal{L}(W)=\mathrm{\{}W,\mathtt{0}\mathtt{1}+W,\mathtt{0}\mathtt{2}+W,\mathtt{0}\mathtt{3}+W,\mathtt{0}\mathtt{4}+W,\mathtt{0}\mathtt{5}+W,\mathtt{0}\mathtt{6}+W,\mathtt{0}\mathtt{7}+W\mathrm{\}}.\end{array}$E8

For instance, the part 0B + V of the linear partition $\mathcal{L}(V)$ is the coset of V with respect to 0B. Explicitly, it is equal to

$\mathtt{0}\mathtt{\text{B}}+V=\mathrm{\{}\mathtt{0}\mathtt{\text{B}}+\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{\text{B}}+\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{\text{B}}+\mathtt{1}\mathtt{\text{A}},\mathtt{0}\mathtt{\text{B}}+\mathtt{1}\mathtt{\text{D}}\mathrm{\}}=\mathrm{\{}\mathtt{0}\mathtt{\text{B}},\mathtt{0}\mathtt{\text{C}},\mathtt{1}\mathtt{1},\mathtt{1}\mathtt{6}\mathrm{\}}.$E9

Now, consider the permutation f of ${\mathbb{F}}_2^5$ given in Figure 2.1. The image of 0B + V under f is

$\begin{array}{cc}f(\mathtt{0}\mathtt{\text{B}}+V)\hfill & =f(\mathrm{\{}\mathtt{0}\mathtt{\text{B}},\mathtt{0}\mathtt{\text{C}},\mathtt{1}\mathtt{1},\mathtt{1}\mathtt{6}\mathrm{\}})=\mathrm{\{}\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{3},\mathtt{1}\mathtt{1},\mathtt{1}\mathtt{\text{F}}\mathrm{\}}\hfill \\ \hfill & =\mathrm{\{}\mathtt{0}\mathtt{3}+\mathtt{0}\mathtt{\text{E}},\mathtt{0}\mathtt{3}+\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{3}+\mathtt{1}\mathtt{2},\mathtt{0}\mathtt{3}+\mathtt{1}\mathtt{\text{F}}\mathrm{\}}=\mathtt{0}\mathtt{3}+W.\hfill \end{array}$E10

Figure 2.1.

The permutation f of Example 2.7.

Observe that $f(\mathtt{0}\mathtt{B}+V)$ is a coset of W so a part of $\mathcal{L}(W)$. The images of all cosets of V under f are displayed in Figure 2.2. Since any of them is a part of $\mathcal{L}(W)$, the permutation f maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. It is worthwhile to observe that a permutation mapping a linear partition to another one does not need to be itself linear or even affine. Indeed, f is certainly not linear as $f(00)=1E\ne 00$. By contradiction, suppose that f is an affine transformation. Then, there exist a linear mapping $L:{\mathbb{F}}_2^5\to {\mathbb{F}}_2^5$ and an element c of ${\mathbb{F}}_2^5$ such that $f(x)=L(x)+c$ holds for all x in ${\mathbb{F}}_2^5$. Therefore,

$f(x)+f(y)+f(z)=L(x)+c+L(y)+c+L(z)+c=L(x+y+z)+c=f(x+y+z)$E11

Figure 2.2.

The permutation f mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$ where $V=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{A})$ and $W=\text{span}(\mathtt{0}\mathtt{E},\mathtt{1}\mathtt{2})$.

for all x, y and z in ${\mathbb{F}}_2^5$. Observe that

$f(\mathtt{0}\mathtt{0})+f(\mathtt{0}\mathtt{1})+f(\mathtt{0}\mathtt{2})=\mathtt{1}\mathtt{\text{E}}+\mathtt{0}\mathtt{8}+\mathtt{0}\mathtt{4}=\mathtt{1}\mathtt{2}\ne \mathtt{1}\mathtt{3}=f(\mathtt{0}\mathtt{0}+\mathtt{0}\mathtt{1}+\mathtt{0}\mathtt{2}).$E12

Thus, f is not an affine transformation.▴

Lemma 2.8. Let V, W be two subspaces of ${\mathbb{F}}_{\mathtt{2}}^n$ and f be a permutation of ${\mathbb{F}}_2^n$, which maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. For any x in ${\mathbb{F}}_2^n$, f maps x + V to f(x) + W.

Example 2.9. In Example 2.7, we have seen that $f(\mathtt{0}\mathtt{\text{B}}+V)=\mathtt{0}\mathtt{3}+W$. Since f maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$, the previous lemma states that $f(\mathtt{0}\mathtt{\text{B}}+V)=f(\mathtt{0}\mathtt{\text{B}})+W=\mathtt{0}\mathtt{\text{D}}+W$. There is however no contradiction here because 0D belongs to 03 + W. Consequently, the cosets 03 + W and 0D + W are equal.▴

The following two propositions are interesting properties of linear partitions, which will be used in the rest of this chapter.

Proposition 2.10. Let $V_1,V_2,W_1,W_2$ be four subspaces of ${\mathbb{F}}_2^n$ and f be a permutation of ${\mathbb{F}}_2^n$, which maps $\mathcal{L}(V_1)$ to $\mathcal{L}(W_1)$ and $\mathcal{L}(V_2)$ to $\mathcal{L}(W_2)$. Then f maps $\mathcal{L}(V_1\cap V_2)$ to $\mathcal{L}(W_1\cap W_2)$.

Proposition 2.11. Let V, W be two subspaces of ${\mathbb{F}}_2^n$ and f be a permutation of ${\mathbb{F}}_2^n$, which maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. There exists an automorphism L of ${\mathbb{F}}_2^n$ such that $L(V)=W$. In particular, V and W are isomorphic.

Example 2.12. Consider again the permutation f of ${\mathbb{F}}_2^5$ defined in Figure 2.8. As seen in the previous example, the permutation maps the linear partition $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Then, Proposition 2.11 ensures that there exists a linear permutation L of ${\mathbb{F}}_2^5$ such that L(V) = W. Consider the bases (07,1A) and (0E,12) of V and W respectively and complete them into the following bases of ${\mathbb{F}}_2^5$

$\begin{array}{ccc}{\mathcal{B}}_V=(\mathrm{}{v}_i{)}_{i<5}=(\mathrm{}\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}},\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{8})& \text{and}& {\mathcal{B}}_W=(\mathtt{}{w}_i{)}_{i<\mathtt{5}}=(\mathtt{}\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{2},\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{4}).\end{array}$E13

Then, the mapping L can be defined by L(v_i) = w_i for each i < 5. This linear transformation will be used in the next chapter.▴

2. Substitution-permutation networks and partitions

This section aims at studying an SPN, which maps a partition of the plaintexts to a partition of the ciphertexts. When the cipher key K is fixed, the encryption function E_K is just a permutation of the message space. Therefore, any partition $\mathcal{A}$ of the plaintexts is mapped to the partition $E_K(\mathcal{A})$ of the ciphertexts. Nonetheless, to exploit the trapdoor, the designer needs to know the pair of partitions $(\mathcal{A},E_K(\mathcal{A})\mathrm{})$. The problem is that the output partition $E_K(\mathcal{A})$ depends a priori on the cipher key K, which is unknown to the attacker. The simplest way to solve this problem is to require the partition $E_K(\mathcal{A})$ to be independent of the cipher key K. In other words, we want all the partitions $E_K(\mathcal{A})$ to be equal to a fixed partition $\mathcal{B}$.

As with differential and linear cryptanalysis, taking account of the exact effect of the key schedule seems to be a challenging problem. Therefore, the key schedule will deliberately be omitted throughout this chapter. This amounts to consider an SPN mapping a partition $\mathcal{A}$ to a fixed partition $\mathcal{B}$, independently of the round keys used.

2.1. The key addition and diffusion layer

Substitution-permutation networks belong to the class of iterated block ciphers. As every iterated block cipher, the encryption function consists in applying a simple keyed operation called round function several times. A different round key is used for each iteration of the round function. In practice, these rounds keys are extracted from a master key using an algorithm called key schedule. In an SPN, the round function is made up of three distinct stages: a key addition, a substitution layer and a permutation or diffusion layer. The substitution layer consists of the parallel evaluation of several S-boxes and is the only part of the cipher, which is not linear or affine. Then, the diffusion layer is the evaluation of some linear mappings (generally one).

Before tackling the full cipher, we look at its basic operations and primitives. The attacker knows the specifications of the substitution and diffusion layers, but he does not know the round key used in the key addition. Therefore, the key addition should not be considered as one operation but rather as a family of permutations. To get back to the subject at hand, we must first determine the partitions $\mathcal{A}$, which are mapped to a unique partition under the action of all round keys.

The next proposition explains the fundamental property of linear partitions according to the key addition. This result was introduced by Harpes in [19]. Later, Caranti et al. gave a similar result expressed for imprimitive groups in [18]. For convenience, we restate this result with our own notations.

Proposition 2.13. Let n be a positive integer. Let $\mathcal{A}$ and $\mathcal{B}$ be two partitions of ${\mathbb{F}}_2^n$. For each k in ${\mathbb{F}}_2^n$, let ${\alpha }_k$ denote the permutation of ${\mathbb{F}}_2^n$ defined by ${\alpha }_k(x)=x+k$. Then, the permutation α_k maps $\mathcal{A}$ to $\mathcal{B}$ for any k in ${\mathbb{F}}_2^n$ if and only if $\mathcal{A}=\mathcal{B}$ and $\mathcal{A}$ is a linear partition.

Even if this result was easily obtained, it has maybe the most important impact on our study. Due to this result and its generalization given later in the next section, only linear partitions will be considered. By definition, the linear partitions are quotient spaces and hence highly structured algebraic objects. Consequently, the apparent combinatorial aspect of our study is reduced to an algebraic problem. This result is indeed quite restrictive since the linear partitions account for a small proportion of all partitions.

Example 2.14. Let n and k be nonnegative integers and q be a prime power. The q-binomial (or Gaussian) coefficient is defined by

${\left[\begin{array}{c}n\\ d\end{array}\right]}_q={\displaystyle {\displaystyle \prod _{i=1}^d}}\frac{1-q^{n-i+1}}{1-q^i}.$E14

It can be proved that this coefficient counts the number of d-dimensional subspaces of an n-dimensional vector space over the finite field ${\mathbb{F}}_q$. Therefore, the number of subspaces of ${\mathbb{F}}_2^3$ is given by

$\begin{array}{cc}{\displaystyle {\displaystyle \sum _{d=0}^3}}{\left[\begin{array}{c}3\hfill \\ d\hfill \end{array}\right]}_2\hfill & =1+\frac{1-2^3}{1-2}+\frac{(1-2^3)(1-2^2)}{(1-2)(1-2^2)}+\frac{(1-2^3)(1-2^2)(1-2^1)}{(1-2)(1-2^2)(1-2^3)}\hfill \\ \hfill & =1+7+7+1=16.\hfill \end{array}$E15

Since a linear partition of ${\mathbb{F}}_2^3$ is uniquely determined by a subspace of ${\mathbb{F}}_2^3$, there are exactly 16 linear partitions. All these partitions are represented graphically at the top of Figure 2.3. For instance, the linear partition associated with the subspace $\text{span}(\mathtt{2},\mathtt{4})=\mathrm{\{}\mathtt{0},\mathtt{2},\mathtt{4},\mathtt{6}\mathrm{\}}$ is $\mathcal{L}(\text{span}(\mathtt{2},\mathtt{4}))=\mathrm{\left\{}\mathrm{\right\{}\mathtt{0},\mathtt{2},\mathtt{4},\mathtt{6}\mathrm{\}},\mathrm{\{}\mathtt{1},\mathtt{3},\mathtt{5},\mathtt{7}\mathrm{\left\}}\mathrm{\right\}}$.

Figure 2.3.

Every linear partitions and key addition in ${\mathbb{F}}_2^3$.

Proposition 2.13 states that among the set of all the partitions of ${\mathbb{F}}_2^n$, only the linear ones yield a unique output partition for every key. The Bell number B_m counts the number of partitions of a set of size m. Thus, the number of partitions of ${\mathbb{F}}_2^n$ is $B_{2^n}$. For n = 3, there are B₈ = 4140 partitions in all. Hence, the linear partitions represent a fraction of 16/B₈ ≈ 2^−8.0. This ratio falls greatly as n increases. In fact, for n = 4, only 67/B₁₆ ≈ 2^−27.2 are linear and for n = 5, this ratio becomes 374/B₃₂ ≈ 2^−78.2. This underlines how Proposition 2.13 is restrictive.

All the key additions are given at the bottom of Figure 2.3. The reverse implication of Proposition 2.13 states that any linear partition is preserved by all the key additions. For instance,

$\begin{array}{cc}{\alpha }_2(\mathcal{L}(\text{span}(\mathtt{6}))\hfill & =\mathrm{\{}f(\mathrm{\{}\mathtt{0},\mathtt{6}\mathrm{\}}),f(\mathrm{\{}\mathtt{1},\mathtt{7}\mathrm{\}}),f(\mathrm{\{}\mathtt{2},\mathtt{4}\mathrm{\}}),f(\mathrm{\{}\mathtt{3},\mathtt{5}\mathrm{\}})\mathrm{\}}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hfill \\ \hfill & =\mathrm{\left\{}\mathrm{\right\{}\mathtt{2},\mathtt{4}\mathrm{\}},\mathrm{\{}\mathtt{3},\mathtt{5}\mathrm{\}},\mathrm{\{}\mathtt{0},\mathtt{6}\mathrm{\}},\mathrm{\{}\mathtt{1},\mathtt{7}\mathrm{\left\}}\mathrm{\right\}}=\mathcal{L}(\text{span}(\mathtt{6})).\hfill \end{array}$E16

Thus, the permutation α₂ preserves $\mathcal{L}(\text{span}(\mathtt{6})\mathrm{})$. Figure 2.4 illustrates graphically that this linear partition is preserved by all the key additions. It is then not hard to check that the same holds for every linear partition given in Figure 2.3.▴

Figure 2.4.

The key additions preserving the partition $\mathcal{L}(\text{span}(\mathtt{6})\mathrm{})$.

Now that we know linear partitions are of major importance, we focus on how the diffusion layer deals with these partitions.

Proposition 2.15. Let n be a positive integer. Let L be an automorphism of ${\mathbb{F}}_2^n$ and V a subspace of ${\mathbb{F}}_2^n$. Then, $L(\mathcal{L}(V))=\mathcal{L}(L(V)\mathrm{})$. In particular, L maps a linear partition to another one.

Proof. Since L is an automorphism, we have

$\begin{array}{cc}L(\mathcal{L}(V))\hfill & =L(\mathrm{\{}x+V|x\in {\mathbb{F}}_2^n\mathrm{\}})=\mathrm{\{}L(x+V)|x\in {\mathbb{F}}_2^n\mathrm{\}}\hfill \\ \hfill & =\mathrm{\{}L(x)+L(V)|x\in {\mathbb{F}}_2^n\mathrm{\}}=\mathrm{\{}{x}^{\prime }+L(V)|x^{\prime }\in {\mathbb{F}}_2^n\mathrm{\}}.\hfill \end{array}$E17

Moreover, L(V) is a subspace of ${\mathbb{F}}_2^n$ because L is a linear mapping. Consequently, $L(\mathcal{L}(V))=\mathcal{L}(L(V)\mathrm{})$. ▪

If V and W are two subspaces of ${\mathbb{F}}_2^n$, it is straightforward to design a linear permutation L of ${\mathbb{F}}_2^n$ mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Indeed, Proposition 2.15 establishes that L maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ is and only if $L(V)=W$. In other words, we only need to consider the image of V and not the whole linear partition $\mathcal{L}(V)$.

2.2. From the encryption function to the substitution layer

Along with the two results of the previous section, we can now address our main issue. For the rest of this chapter, we consider a generic SPN whose parameters are defined as follows.

Definition 2.16 (SPN). Let m, n and r be positive integers. A substitution-permutation network is an iterated block cipher whose encryption function is defined as follows. Let S₀,…,S_m−1 be n-bit S-boxes.

• The addition of the round key k is denoted by ${\alpha }_k:{\mathbb{F}}_2^{nm}\to {\mathbb{F}}_2^{nm}$, $x\mapsto x+k$.

• The substitution layer is denoted by σ and maps ${(x_i)}_{0\le i<m}$ to ${(S_i(x_i)\mathrm{})}_{0\le i<m}$.

• The diffusion layer is a linear permutation denoted by $\pi :{\mathbb{F}}_2^{nm}\to {\mathbb{F}}_2^{nm}$.

The round function F_k associated with the round key k is defined by $F_k=\pi \sigma {\alpha }_k$. The encryption function associated with the round keys $K=(\mathrm{}{k}^{[0]},\dots ,k^{[r]})$ in ${({\mathbb{F}}_2^{nm})}^{r+1}$ is defined by

$E_K={\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[0]}}.$E18

We can now prove the following result.

Theorem 2.17. Let $\mathcal{A}$ and $\mathcal{B}$ be two partitions of ${\mathbb{F}}_2^{nm}$. Suppose for any (r + 1)-tuples of round keys $K=(\mathrm{}{k}^{[0]},\dots ,k^{[r]})$ in ${({\mathbb{F}}_2^{nm})}^{r+1}$ that the encryption function E_K maps $\mathcal{A}$ to $\mathcal{B}$. Define ${\mathcal{A}}^{[0]}=\mathcal{A}$ and for all $1\le i\le r$, ${\mathcal{A}}^{[i]}=(\mathrm{}\pi \sigma {)}^i(\mathcal{A})$. Then,

• ${\mathcal{A}}^{[r]}=\mathcal{B}$;

• for any 0 ≤ i < r and for any k^[i] in ${\mathbb{F}}_2^{nm}$, $F_{k^{[i]}}({\mathcal{A}}^{[i]})={\mathcal{A}}^{[i+1]}$;

• for any $0\le i\le r$, ${\mathcal{A}}^{[i]}$ is a linear partition.

Proof. Observe that for the round key k = 0_nm, the key addition ${\alpha }_{0_{nm}}$ is the identity mapping on ${\mathbb{F}}_2^{nm}$, and thus $F_{0_{nm}}=\pi \sigma {\alpha }_{0_{nm}}=\pi \sigma$. Now, choosing $K=(\mathrm{}{k}^{[0]},\dots ,k^{[r]}{)=(0}_{nm},\dots {,0}_{nm})$ gives

$\begin{array}{cc}\mathcal{B}=E_K({\mathcal{A}}^{[0]})\hfill & ={\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[0]}}({\mathcal{A}}^{[0]})={\alpha }_{0_{nm}}(F_{0_{nm}}{)}^r({\mathcal{A}}^{[0]})\hfill \\ \hfill & ={(\pi \sigma )}^r({\mathcal{A}}^{[0]})={\mathcal{A}}^{[r]}.\hfill \end{array}$E19

Let $0\le i<r$ be an integer. Let k^[i] be any element of ${\mathbb{F}}_2^{nm}$. Define $k^{[j]}{=0}_{nm}$ for all $0\le j\le r$ such that $j\ne i$. By hypothesis, the equality ${\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[0]}}({\mathcal{A}}^{[0]})={\mathcal{A}}^{[r]}$ holds. Thus,

$F_{k^{[i]}}\dots F_{k^{[0]}}({\mathcal{A}}^{[0]})=({\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[i+1]}}{)}^{-1}({\mathcal{A}}^{[r]}).$E20

On one hand,

$\begin{array}{c}{F}_{k^{[i]}}\dots F_{k^{[0]}}({\mathcal{A}}^{[0]})=F_{k^{[i]}}(F_{k^{[i-1]}}\dots F_{k^{[0]}})({\mathcal{A}}^{[0]})=F_{k^{[i]}}{(F_{0_{nm}})}^i({\mathcal{A}}^{[0]})\\ =F_{k^{[i]}}{(\pi \sigma )}^i({\mathcal{A}}^{[0]})=F_{k^{[i]}}({\mathcal{A}}^{[i]}).\end{array}$E21

On the other hand,

$\begin{array}{ll}{({\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[i+1]}})}^{-1}({\mathcal{A}}^{[r]})\hfill & ={({\alpha }_{0_{nm}}{(F_{0_{nm}})}^{r-(i+1)})}^{-1}({\mathcal{A}}^{[r]})\hfill \\ \hfill & ={({(\pi \sigma )}^{r-(i+1)})}^{-1}({\mathcal{A}}^{[r]})={\mathcal{A}}^{[i+1]}.\hfill \end{array}$E22

Therefore, $F_{k^{[i]}}({\mathcal{A}}^{[i]})={\mathcal{A}}^{[i+1]}$, or equivalently ${\alpha }_{k^{[i]}}({\mathcal{A}}^{[i]})=(\pi \sigma {)}^{-1}({\mathcal{A}}^{[i+1]})$. Since this equality holds for every k^[i], Proposition 2.13 states that the partition ${\mathcal{A}}^{[i]}$ is linear.

It remains to show that ${\mathcal{A}}^{[r]}$ is linear as the previous argument holds only for i < r. Let k^[r] be an element of ${\mathbb{F}}_2^{nm}$. Define k^[i] = 0_nm for each $0\le i<r$. Then,

${\mathcal{A}}^{[r]}={\alpha }_{k^{[r]}}{F}_{k^{[r-1]}}\dots F_{k^{[0]}}({\mathcal{A}}^{[0]})={\alpha }_{k^{[r]}}{(F_{0_{nm}})}^r({\mathcal{A}}^{[0]})={\alpha }_{k^{[r]}}({\mathcal{A}}^{[r]}).$E23

Again, Proposition 2.13 implies that ${\mathcal{A}}^{[r]}$ is linear and the result is proven. ▪

This theorem can be restated in the following way. First, the input partition $\mathcal{A}$ and the output partition $\mathcal{B}$ must be linear. This result generalizes Proposition 2.13 in the sense that it applies to the full cipher and not only to the key addition. As was pointed out earlier, linear partitions are very specific partitions. This means that our combinatorial hypothesis implies to consider only algebraic objects.

Second, we have only supposed that the encryption function maps $\mathcal{A}$ to $\mathcal{B}$ after r rounds. Nevertheless, Theorem 2.17 ensures that each iteration of the round function also maps a fixed linear partition to another one. As a consequence, the study of the full cipher is reduced to the study of the round function. Additionally, this result can be strengthened as follows.

Corollary 2.18. Keep the notations of Theorem 2.17. For all $0\le i\le r$, let V^[i] denote the part of ${\mathcal{A}}^{[i]}$ containing 0. According to Theorem 2.17, ${\mathcal{A}}^{[i]}=\mathcal{L}(V^{[i]})$. Let $0\le i<r$ be an integer. Then,

$\sigma (\mathcal{L}(V^{[i]}))=\mathcal{L}(W^{[i]}).$E24

where W^[i] denotes the subspace ${\pi }^{-1}(V^{[i+1]})$. In particular, the substitution layer must at least map one linear partition to another one.

Proof. By definition, $\pi \sigma ({\mathcal{A}}^{[i]})={\mathcal{A}}^{[i+1]}$ or, equivalently, $\sigma ({\mathcal{A}}^{[i]})={\pi }^{-1}({\mathcal{A}}^{[i+1]})$. This equality can be restated as

$\sigma (\mathcal{L}(V^{[i]}))={\pi }^{-1}(\mathcal{L}(V^{[i+1]})\mathrm{}).$E25

As π is an automorphism of ${\mathbb{F}}_2^{nm}$, then so π⁻¹ is. Next, Proposition 2.15 ensures that ${\pi }^{-1}(\mathcal{L}(V^{[i+1]}))=\mathcal{L}({\pi }^{-1}(V^{[i+1]})\mathrm{})$. The result follows. ▪

A diagrammatic representation of Theorem 2.17 and Corollary 2.18 is given in Figure 2.5. This highlights that the input partition is always transformed in the same way through each basic operation of the encryption process. The results obtained so far can be summarized as follows: if an SPN maps a partition $\mathcal{A}$ of the plaintext space to a partition $\mathcal{B}$ of the ciphertext space no matter the round keys used, then the substitution layer has to map at least one linear partition to another one. This shows that our study can be reduced to the substitution layer without loss of generality.

Figure 2.5.

Results of Section 2.2.

3. Structure of the substitution layer

In the remainder of this chapter, V and W will denote two subspaces of ${({\mathbb{F}}_2^n)}^m$.

As explained in the previous section, it remains to understand how the substitution layer can map the linear partition $\mathcal{L}(V)$ to $\mathcal{L}(W)$. This problem is far more complex for the substitution layer than it was for the diffusion layer. The reasons for this are twofold. First, the substitution layer is nonlinear. It is even the only part of the SPN, which is not affine. As a consequence, to map the linear partition $\mathcal{L}(V)$ to $\mathcal{L}(W)$, we have to consider all the parts of both partitions and not only the subspaces V and W, as was the case for the diffusion layer (see Proposition 2.15).

Second, the substitution layer should not be considered as a whole, but as the parallel application of its S-boxes. Therefore our problem becomes the following. Given two subspaces V and W, what are the necessary and/or sufficient conditions on the S-boxes for the substitution layer to map $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

Before going any further, let us introduce an example that we will continue throughout this section.

Example 2.19. Consider the substitution layer made up of the four 5-bit S-boxes S₀, S₁, S₂ and S₃ described in Figure 2.6. Its parameters are then m = 4 and n = 5. Observe that the S-box S₂ was previously studied in Example 2.7. Define the two families ${\mathcal{E}}_V=(\mathrm{}{v}_i{)}_{0\le i<7}$ and ${\mathcal{E}}_W=(\mathrm{}{w}_i{)}_{0\le i<7}$ of elements of ${({\mathbb{F}}_2^5)}^4$ by

$\begin{array}{ll}{v}_0\hfill & =(\mathtt{1}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{7}),\hfill \\ v_1\hfill & =(\mathrm{}\mathtt{0}\mathtt{8},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{7}),\hfill \\ v_2\hfill & =(\mathtt{}\mathtt{0}\mathtt{4},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{B}),\hfill \end{array}\begin{array}{ll}{v}_3\hfill & =(\mathrm{}\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{C}),\hfill \\ v_4\hfill & =(\mathrm{}\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{C}),\hfill \\ v_5\hfill & =(\mathrm{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{A},\mathtt{0}\mathtt{0}),\hfill \\ v_6\hfill & =(\mathtt{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{0}).\hfill \end{array}\begin{array}{ll}{w}_0\hfill & =(\mathrm{}\mathtt{1}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{5}),\hfill \\ w_1\hfill & =(\mathrm{}\mathtt{0}\mathtt{8},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{D}),\hfill \\ w_2\hfill & =(\mathrm{}\mathtt{0}\mathtt{4},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{5}),\hfill \end{array}\begin{array}{ll}{w}_3\hfill & =(\mathrm{}\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{8}),\hfill \\ w_4\hfill & =(\mathrm{}\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),\hfill \\ w_5\hfill & =(\mathrm{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{2},\mathtt{0}\mathtt{0}),\hfill \\ w_6\hfill & =(\mathrm{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{E},\mathtt{0}\mathtt{0}).\hfill \end{array}$E26

Figure 2.6.

Specification of the S-boxes used throughout Section 3.

Finally, define V and W as the subspaces spanned by ${\mathcal{E}}_V$ and ${\mathcal{E}}_W$, respectively. Note that the family ${\mathcal{E}}_V$ is linearly independent because it is echelonized. Hence, ${\mathcal{E}}_V$ is a basis of V. The same applies for ${\mathcal{E}}_W$ and W. As a consequence, V and W are both seven-dimensional subspaces of ${({\mathbb{F}}_2^5)}^4$.

We claim that the substitution layer σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Naturally, we will not verify this statement by hand because it requires to check for each of the 2¹³ cosets of V that the 2⁷ images of its elements under σ lies in the same coset of W. However, the reader who is relectant to accept this claim is encouraged to check it with a computer.▴

3.1. Truncating the substitution layer

To understand how the substitution layer can map $\mathcal{L}(V)$ to $\mathcal{L}(W)$, we will adopt a divide and conquer strategy. That is to say, we want to break down this problem into several independent sub-problems, each involving less S-boxes than the full substitution layer. The first idea is to truncate the substitution layer and the subspaces V and W to get a local view of what happens on some S-boxes.

Definition 2.20 (truncation and substitution layer). Let E be any non-empty subset of $〚\mathrm{0,}m〚$ and define the following mappings

$\begin{array}{cc}{\text{T}}_E:({\mathbb{F}}_2^n{)}^m\to {({\mathbb{F}}_2^n)}^E& {\sigma }_E:({\mathbb{F}}_2^n{)}^E\to {({\mathbb{F}}_2^n)}^E\\ {(x_i)}_{0\le i<m}\mapsto {(x_i)}_{i\in E}& {(x_i)}_{i\in E}\mapsto {(S_i(x_i)\mathrm{})}_{i\in E}.\end{array}$E27

If E has cardinality p, then we identify ${({\mathbb{F}}_2^n)}^E$ with ${({\mathbb{F}}_2^n)}^p$.

The mapping T_E allows to shorten a vector of ${({\mathbb{F}}_2^n)}^m$ to keep only the coordinates whose indices belong to E. The application σ_E is a substitution layer truncated to the S-boxes whose indices lie in E.

Remark 2.21. Note that T_E is a linear mapping. Observe that ${\sigma }_{〚\mathrm{0,}m〚}$ is the substitution layer of the SPN. Moreover, the truncated substitution layer ${\sigma }_{\mathrm{\left\{}i\mathrm{\right\}}}$ and the S-box S_i are equal for all $0\le i<m$.

Proposition 2.22 (truncating to a few S-boxes). Suppose that σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Let E be a nonempty subset of $〚\mathrm{0,}m〚$. Then, the permutation σ_E maps $\mathcal{L}({\text{T}}_E(V)\mathrm{})$ to $\mathcal{L}({\text{T}}_E(W)\mathrm{})$.

Proof. Let $x=(\mathrm{}{x}_i{)}_{i\in E}$ be an element of ${({\mathbb{F}}_2^n)}^E$. Let y be the element of ${({\mathbb{F}}_2^n)}^m$ defined by y_i = x_i if i belongs to E and $y_i{=0}_n$ otherwise. Thus, ${\text{T}}_E(y)=x$. By hypothesis, σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Hence, Lemma 2.8 implies that $\sigma (y+V)=\sigma (y)+W$. Next,

${\text{T}}_E(\sigma (y+V))={\text{T}}_E(\sigma (y)\mathrm{})+{\text{T}}_E(W)$E28

since T_E is a linear mapping. Furthermore,

$\begin{array}{cc}{\text{T}}_E(\sigma (y+V))\hfill & ={\text{T}}_E\sigma (\mathrm{\{}y+v|v\in V\mathrm{\}})=\mathrm{\{}{\text{T}}_E\sigma (y+v)|v\in V\mathrm{\}}\hfill \\ \hfill & =\mathrm{\{}{\sigma }_E({\text{T}}_E(y+v)\mathrm{})|v\in V\mathrm{\}}={\sigma }_E(\mathrm{\{}{\text{T}}_E(y+v)|v\in V\mathrm{\}})\hfill \\ \hfill & ={\sigma }_E(\mathrm{\{}{\text{T}}_E(y)+{\text{T}}_E(v)|v\in V\mathrm{\}})={\sigma }_E({\text{T}}_E(y)+{\text{T}}_E(V)\mathrm{}).\hfill \end{array}$E29

Therefore, ${\sigma }_E(x+{\text{T}}_E(V))={\text{T}}_E(\sigma (y)\mathrm{})+{\text{T}}_E(W)$. In other words, the image of any part of $\mathcal{L}({\text{T}}_E(V)\mathrm{})$ under σ_E lies in $\mathcal{L}({\text{T}}_E(W)\mathrm{})$. The result is a consequence of Lemma 2.4. ▪

Example 2.23. By choosing $E=\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}$, the previous proposition ensures that the truncated substitution layer ${\sigma }_{\mathrm{\{}0,3\mathrm{\}}}$ maps $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\{}0,3\mathrm{\}}}(V)\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\{}0,3\mathrm{\}}}(W)\mathrm{})$. First, it is easy to see that

$\begin{array}{l}{\text{T}}_{\mathrm{\{}0,3\mathrm{\}}}(V)=\text{span}((\mathtt{1}\mathtt{0},\mathtt{1}\mathtt{7}),(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{7}),(\mathtt{0}\mathtt{4},\mathtt{0}\mathtt{\text{B}}),(\mathtt{0}\mathtt{2},\mathtt{1}\mathtt{\text{C}}),(\mathtt{0}\mathtt{1},\mathtt{1}\mathtt{\text{C}})),\\ {\text{T}}_{\mathrm{\{}0,3\mathrm{\}}}(W)=\text{span}((\mathtt{1}\mathtt{0},\mathtt{1}\mathtt{5}),(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{\text{D}}),(\mathtt{0}\mathtt{4},\mathtt{1}\mathtt{5}),(\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{8}),(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{0})).\end{array}$E30

Again, we will not explicitly check that ${\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}$ maps $\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V)\mathrm{})$ to $\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\mathrm{})$ but limit ourselves to prove that the coset $(\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V)$ is mapped to one coset of $\text{T}{\text{}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)$. Its image can be found using Lemma 2.8 as follow

$\begin{array}{cc}{\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}((\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V))\hfill & ={\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}((\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})\mathtt{})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\hfill \\ \hfill & =(\mathtt{}\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W).\hfill \end{array}$E31

The images of every element of this coset are given in Figure 2.7. For instance,

$\begin{array}{c}{\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}((\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+(\mathtt{0}\mathtt{1},\mathtt{1}\mathtt{\text{C}}))={\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(\mathtt{0}\mathtt{6},\mathtt{1}\mathtt{\text{F}})=(S_0(\mathtt{0}\mathtt{6}),S_3(\mathtt{1}\mathtt{\text{F}}))=(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{7})\\ =(\mathtt{}\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})+(\mathtt{0}\mathtt{6},\mathtt{1}\mathtt{\text{D}}).\end{array}$E32

Figure 2.7.

σ_{0,3} mapping a coset of T_{0,3}(V) to a coset of T_{0,3}(W).

This explains the second image.▴

Choosing E = {i} in Proposition 2.22 gives that the S-box S_i maps $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W)\mathrm{})$. As this result holds for each index i in $〚\mathrm{0,}m〚$, we deduce that

$\begin{array}{ccc}\sigma (\mathcal{L}(V))=\mathcal{L}(W)& \Rightarrow & \forall i\in 〚\mathrm{0,}m〚,S_i(\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)))=\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W)\mathrm{}).\end{array}$E2.1

However, the equivalence does not hold in general. Hence, this only gives a necessary condition on each S-box. In other words, this means that we can lose information when considering each S-box independently. The next example stresses this fact.

Example 2.24. In our example, the truncated subspaces T_{i}(V) and T_{i}(W) are the following:

$\begin{array}{l}{\text{T}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V)={\mathbb{F}}_2^5,{\text{T}}_{\mathrm{\left\{}1\mathrm{\right\}}}(V)=\mathrm{\left\{}\mathtt{0}\mathtt{0}\mathrm{\right\}},{\text{T}}_{\mathrm{\left\{}2\mathrm{\right\}}}(V)=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}}),{\text{T}}_{\mathrm{\left\{}3\mathrm{\right\}}}(V)=\text{span}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{7}),\\ {\text{T}}_{\mathrm{\left\{}0\mathrm{\right\}}}(W)={\mathbb{F}}_2^5,{\text{T}}_{\mathrm{\left\{}1\mathrm{\right\}}}(W)=\mathrm{\left\{}\mathtt{0}\mathtt{0}\mathrm{\right\}},{\text{T}}_{\mathrm{\left\{}2\mathrm{\right\}}}(W)=\text{span}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{7}),{\text{T}}_{\mathrm{\left\{}3\mathrm{\right\}}}(W)=\text{span}(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{5}).\end{array}$E34

First, observe that the truncated subspaces for S₀ and S₁ are trivial. Hence, the associated linear partitions are also trivial and no information on S₀ or S₁ can be drawn from 2.1. Yet, the last two truncated subspaces are nontrivial and 1 gives the following equalities:

$\begin{array}{l}{S}_2(\mathcal{L}(\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})))=\mathcal{L}(\text{span}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{7})\mathrm{}),\\ S_3(\mathcal{L}(\text{span}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{7})))=\mathcal{L}(\text{span}(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{5})\mathrm{}).\end{array}$E35

The first property has already been highlighted in Example 2.7 and in Figure 2.2. The second one is represented in Figure 2.8.

Figure 2.8.

The S-box S₃ mapping $\mathcal{L}(V^{\prime })$ to $\mathcal{L}(W^{\prime })$ where $V^{\prime }=\text{span}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{7})$ and $W^{\prime }=\text{span}(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{5})$.

Let us now show that the converse of Implication 2.1 does not hold in general. Consider the substitution layer σ′ made up of the four S-boxes ${S^{\prime }}_0$, ${S^{\prime }}_1$, ${S^{\prime }}_2$ and ${S^{\prime }}_3$ where

$\begin{array}{ccc}{S^{\prime }}_0=S_1,& {S^{\prime }}_1=S_1,& \begin{array}{cc}{S^{\prime }}_2=S_2,& {S^{\prime }}_3=S_3.\end{array}\end{array}$E36

Thus, this new substitution layer differs from σ by only one S-box. Recall that the linear partition associated with ${\text{T}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V)={\text{T}}_{\mathrm{\left\{}0\mathrm{\right\}}}(W)$ is trivial. Therefore, ${S^{\prime }}_0$ necessarily preserves this partition. As the other S-boxes remain the same, the right side of 2.1 still holds for σ′, that is

$\forall i\in 〚\mathrm{0,4}〚,{S^{\prime }}_i(\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)))=\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W)\mathrm{}).$E37

However, we will prove that σ′ does not map $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Suppose by contradiction that it does. Then Proposition 2.22 ensures that ${{\sigma }^{\prime }}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}$ maps $\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V)\mathrm{})$ to $\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\mathrm{})$. By Lemma 2.8,

$\begin{array}{c}{{\sigma }^{\prime }}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}((\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V))={{\sigma }^{\prime }}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\\ =(\mathrm{}{S^{\prime }}_0(\mathtt{0}\mathtt{7}),{S^{\prime }}_3(\mathtt{0}\mathtt{3})\mathrm{})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\\ =(\mathrm{}{S}_1(\mathtt{0}\mathtt{7}),S_3(\mathtt{0}\mathtt{3})\mathrm{})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)=(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})+{\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W).\end{array}$E38

Then

$\begin{array}{c}{{\sigma }^{\prime }}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}((\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{3})+(\mathtt{0}\mathtt{1},\mathtt{1}\mathtt{\text{C}}))={{\sigma }^{\prime }}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(\mathtt{0}\mathtt{6},\mathtt{1}\mathtt{\text{F}})=({S^{\prime }}_{\mathtt{0}}(\mathtt{0}\mathtt{6}),{S^{\prime }}_3(\mathtt{1}\mathtt{\text{F}}))=(S_1(\mathtt{0}\mathtt{6}),S_{\mathtt{3}}(\mathtt{1}\mathtt{F})\mathtt{})\\ =(\mathrm{}\mathtt{0}\mathtt{\text{C}},\mathtt{0}\mathtt{7})=(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})+(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{\text{D}}).\end{array}$E39

This is a contradiction since (0B,1D) does not belong to $\text{T}{\text{}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)$ as can be seen in Figure 2.7. As a consequence, the substitution layer σ′ does not map $\mathcal{L}(V)$ to $\mathcal{L}(W)$.▴

As shown in the previous example, truncating the substitution layer and the subspaces V and W to each S-box independently of the others is too restrictive in general. This suggests that some S-boxes can in a way be linked together. That is to say, considering them independently results in a loss of information on the subspaces V and W. Recall that we are interested in splitting the problem of finding all the substitution layers σ mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$ into several independent smaller problems. Taking into account that some S-boxes can be linked together, we require the following:

• a sub-problem can involve several S-boxes;

• the same S-box cannot be involved in two different sub-problems (in other words, the sub-problems are independent);

• each S-box is involved in one sub-problem (possibly trivial).

This is naturally formalized by a partition $\mathcal{I}$ of $〚\mathrm{0,}m〚$. Each part I of $\mathcal{I}$ represents a sub-problem, and its elements are the indices of the S-boxes involved in. By virtue of Proposition 2.22, it holds that

$\begin{array}{ccc}\sigma (\mathcal{L}(V))=\mathcal{L}(W)& \Rightarrow & \forall I\in \mathcal{I},{\sigma }_I(\mathcal{L}(\text{T}{\text{}}_I(V)))=\mathcal{L}(\text{T}{\text{}}_I(W)\mathrm{}).\end{array}$E2.2

The next section aims to find a sufficient condition on the partition $\mathcal{I}$ to obtain the equivalence. In such a case, this means that combining the solutions of these sub-problems yields a substitution layer mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$ and vice versa.

3.2. Structure of the subspaces V and W

With the aim of ending up with partitions for which the converse of 2.2 holds, let us introduce a few definitions and notations.

Definition 2.25 (trivial product). Let E be a subset of $〚\mathrm{0,}m〚$. The trivial product subspace associated with E, denoted by Triv_E, is defined to be

${\text{Triv}}_E=\mathrm{\{}x\in {({\mathbb{F}}_2^n)}^m|\forall i\in E^c,x_i{=0}_n\mathrm{\}}.$E41

Moreover, we denote by V_E the intersection of V and Triv_E, that is $V_E=V\cap {\text{Triv}}_E=\mathrm{\{}v\in V|\forall i\in E^c,v_i{=0}_n\mathrm{\}}$. The subspace W_E is defined in the same way.

Remark 2.26. It is easily seen that

$\begin{array}{ccc}{\text{Triv}}_E={\displaystyle {\displaystyle \prod _{i=0}^{m-1}}}{\text{Triv}}_E^{[i]}& \text{with}& {\text{Triv}}_E^{[i]}=\{\begin{array}{cc}{\mathrm{\{}0}_n\mathrm{\}}& \text{if}i\in E^c,\\ {\mathbb{F}}_2^n& \text{if}i\in E.\end{array}\end{array}$E42

Thus, a trivial product subspace is the Cartesian product of trivial spaces for each S-box; this justifies its name. Additionally, if $E\subseteq F$, then ${\text{Triv}}_E\subseteq {\text{Triv}}_F$, and hence $V_E\subseteq V_F$ and $W_E\subseteq W_F$.

The subspaces Triv_E are essential in the study of the substitution layer because the latter always preserves the partition $\mathcal{L}({\text{Triv}}_E)$ regardless of its S-boxes. This result, together with Proposition 2.10, establishes the following corollary.

Corollary 2.27. Let E be a subset of $〚\mathrm{0,}m〚$. If σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$, then σ also maps $\mathcal{L}(V_E)$ to $\mathcal{L}(W_E)$.

Example 2.28. All the subspaces V_E are graphically represented in Figure 2.9. For instance,

$V_{\mathrm{\left\{}0\mathrm{\right\}}}=\text{span}((\mathtt{1}\mathtt{5},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})\mathtt{}).$E43

Figure 2.9.

The subspaces V_E, W_E for each subset E of {0,1,2,3}.

Additionally, this figure also highlights the expected inclusions given by Remark 2.26. Observe that ${\mathcal{B}}_V=(\mathtt{}{v}_i{)}_{\mathtt{0}\le i<\mathtt{7}}$ is a basis of V. This new basis is more convenient than the echelonized basis ${\mathcal{E}}_V$ previously introduced in Example 2.19 since all the V_E are then easily described. It is worth noting that the same picture remains valid for the subspace W. For example,

$W_{\mathrm{\left\{}0\mathrm{\right\}}}=\text{span}((\mathtt{1}\mathtt{4},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{\text{E}},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})\mathrm{}).$E44

This emphasizes that when the substitution layer maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$, the subspaces V and W have the same structure.

According to Corollary 2.27, the substitution layer maps $\mathcal{L}(V_{\mathrm{\left\{}0\mathrm{\right\}}})$ to $\mathcal{L}(W_{\mathrm{\left\{}0\mathrm{\right\}}})$. Next, truncate to E = {0} using Proposition 2.22 to obtain

$S_0(\mathcal{L}(\text{span}(\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{D},\mathtt{1}\mathtt{5})))=\mathcal{L}(\text{span}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{4})\mathrm{}).$E45

This property is depicted in Figure 2.10. Finally, it should be underlined that with Proposition 2.22 alone, no property can be established on the S-box S₀ (see Example 2.24).▴

Figure 2.10.

The S-box S₀ mapping $\mathcal{L}(V^{\prime })$ to $\mathcal{L}(W^{\prime })$ where $V^{\prime }=\text{span}(\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{\text{D}},\mathtt{1}\mathtt{5})$ and $W^{\prime }=\text{span}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{4})$.

Definition 2.29 (projection P_E). Let E be a subset of $〚\mathrm{0,}m〚$. The projection P_E from ${({\mathbb{F}}_2^n)}^m$ onto Triv_E is defined by $\text{P}{}_E(x_0,\dots ,x_{m-1})=(y_0,\dots ,y_{m-1})$ where y_i = x_i if i belongs to E and y_i = 0_n otherwise.

Remark 2.30. It is not hard to see that P_E is a linear mapping and that V_E is always a subspace of P_E(V). Moreover, it holds that ${\text{T}}_E(V)={\text{T}}_E({\text{P}}_E(V)\mathrm{})$.

The next lemma gives some relations between the previous definitions. It is quite important and will be used several times by the end of the current chapter.

Lemma 2.31. Let $\mathcal{I}$ be a partition of $〚\mathrm{0,}m〚$. Then V equals the internal direct sum ${\oplus }_{I\in \mathcal{I}}{V}_I$ if and only if $V_I={\text{P}}_I(V)$ for any part I of $\mathcal{I}$. In this case, the decomposition of an element v of V is $v={\sum }_{I\in \mathcal{I}}{\text{P}}_I(v)$.

Remark 2.32. Suppose that $\mathcal{I}$ is a partition of $〚\mathrm{0,}m〚$ such that $V={\oplus }_{I\in \mathcal{I}}{V}_I$. The previous lemma, together with Remark 2.30, establishes that ${\text{T}}_I(V)={\text{T}}_I(V_I)$ for each part I of $\mathcal{I}$.

Proposition 2.33 (Substitution layer structure). Let $\mathcal{I}$ be a partition of $〚\mathrm{0,}m〚$ satisfying both $V={\oplus }_{I\in \mathcal{I}}{V}_I$ and $W={\oplus }_{I\in \mathcal{I}}{W}_I$. The permutation σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ if and only if σ_I maps $\mathcal{L}(\text{T}{\text{}}_I(V)\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_I(W)\mathrm{})$ for any I in $\mathcal{I}$.

The preceding proposition establishes that the converse of Implication 2.2 (page 21) holds whenever the partition $\mathcal{I}$ satisfies both $V={\oplus }_{I\in \mathcal{I}}{V}_I$ and $W={\oplus }_{I\in \mathcal{I}}{W}_I$. For such a partition, the problem of finding all the substitution layers σ mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$ can equivalently be broken down into the independent sub-problems of finding all the σ_I mapping $\mathcal{L}({\text{T}}_I(V)\mathrm{})$ to $\mathcal{L}({\text{T}}_I(W)\mathrm{})$ for each part I of $\mathcal{I}$.

3.3. Linked and independent S-boxes

Of course, there may be several partitions $\mathcal{I}$ such that $V={\oplus }_{I\in \mathcal{I}}{V}_I$ and $W={\oplus }_{I\in \mathcal{I}}{W}_I$, each yielding a different decomposition of the substitution layer. A few of these decompositions are certainly more interesting or easier to solve. The purpose of this section is to study such partitions. Let us begin with the following lemma.

Lemma 2.34. Suppose that σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. For every partition $\mathcal{I}$ of $〚\mathrm{0,}m〚$, $V={\oplus }_{I\in \mathcal{I}}{V}_I$ if and only if $W={\oplus }_{I\in \mathcal{I}}{W}_I$.

The contrapositive of Lemma 2.34 is the following: if there exists a partition $\mathcal{I}$ such that $V={\oplus }_{I\in \mathcal{I}}{V}_I$ and $W\ne {\oplus }_{I\in \mathcal{I}}{W}_I$ or such that $V\ne {\oplus }_{I\in \mathcal{I}}{V}_I$ and $W={\oplus }_{I\in \mathcal{I}}{W}_I$, then there exists no substitution layer mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Because we intend to study the substitution layers mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$, Lemma 2.34 suggests to assume the following.

Assumption 2.35. For the remainder of this section, we assume that for any partition $\mathcal{I}$ of $〚\mathrm{0,}m〚$, it holds that

$V={\displaystyle \underset{I\in \mathcal{I}}{\oplus }}{V}_I\iff W={\displaystyle \underset{I\in \mathcal{I}}{\oplus }}{W}_I.$E46

Proposition 2.33, together with the preceding assumption, suggests the following definition.

Definition 2.36 (decomposition partition). A decomposition partition (with respect to V and W) is a partition of $〚\mathrm{0,}m〚$ such that $V={\oplus }_{I\in \mathcal{I}}{V}_I$.

Remark 2.37 (partial order on partitions). Recall that if $\mathcal{I}$ and $\mathcal{J}$ are two partitions of $〚\mathrm{0,}m〚$, then the partition $\mathcal{I}$ is said to be finer than $\mathcal{J}$ if for any part I in $\mathcal{I}$, there exists a part J in $\mathcal{J}$ such that $I\subseteq J$.

Example 2.38. The purpose of this example is to find all the decomposition partitions with regard to V and W. By virtue of Lemma 2.31, the subspace V can be decomposed as ${\oplus }_{I\in \mathcal{I}}{V}_I$ if and only if V_I is equal to P_I(V) for each part I of $\mathcal{I}$. The eight-framed subspaces in the middle of Figure 2.9 are exactly those that satisfy $V_E={\text{P}}_E(V)$. Hence, the decomposition partitions are the partitions whose parts are selected from the following:

$\varnothing ,\mathrm{\left\{}1\mathrm{\right\}},\mathrm{\left\{}2\mathrm{\right\}},\mathrm{\left\{}\mathrm{1,2}\mathrm{\right\}},\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}},\mathrm{\left\{}\mathrm{0,1,3}\mathrm{\right\}},\mathrm{\left\{}\mathrm{0,2,3}\mathrm{\right\}},\mathrm{\left\{}\mathrm{0,1,2,3}\mathrm{\right\}}.$E47

It is then easy to check that the decomposition partitions of V are:

$\begin{array}{lll}\mathrm{\left\{}\mathrm{\right\{}1\mathrm{\}},\mathrm{\{}2\mathrm{\}},\mathrm{\{}\mathrm{0,3}\mathrm{\left\}}\mathrm{\right\}},\hfill & \mathrm{\left\{}\mathrm{\right\{}1\mathrm{\}},\mathrm{\{}\mathrm{0,2,3}\mathrm{\left\}}\mathrm{\right\}},\hfill & \mathrm{\left\{}\mathrm{\right\{}2\mathrm{\}},\mathrm{\{}\mathrm{0,1,3}\mathrm{\left\}}\mathrm{\right\}},\hfill \\ \mathrm{\left\{}\mathrm{\right\{}\mathrm{0,3}\mathrm{\}},\mathrm{\{}\mathrm{1,2}\mathrm{\left\}}\mathrm{\right\}}\hfill & \text{and}\hfill & \mathrm{\left\{}\mathrm{\right\{}\mathrm{0,1,2,3}\mathrm{\left\}}\mathrm{\right\}}.\hfill \end{array}$E48

In Figure 2.11, all the partitions of $〚\mathrm{0,4}〚$ are ordered by the “finer-than” relation, and the decomposition partitions are emphasized. What stands out is that the decomposition partition {{1}, {2}, {0, 3}} is finer than all other decomposition partitions.▴

Figure 2.11.

The partitions $\mathcal{I}$ of {0, 1, 2, 3} such that $V={\oplus }_{I\in \mathcal{I}}{V}_I$.

The existence of this least decomposition partition in the example above is a very welcome and nontrivial property. This means that all the truncated substitution layers obtained using Proposition 2.33 are the smallest possible. Thus, such a partition should be preferred to any other decomposition partition. We will now prove that this least decomposition partition always exists.

Proposition 2.39. The set of the partitions $\mathcal{I}$ of $〚\mathrm{0,}m〚$ satisfying $V={\oplus }_{I\in \mathcal{I}}{V}_I$ has a least element denoted ${\mathcal{I}}_{\text{ld}}$.

Consequently, the only decomposition partition that will be considered in the remainder of this chapter is the least decomposition partition ${\mathcal{I}}_{\text{ld}}$. The following definition is inspired by Proposition 2.33 and Proposition 2.39.

Definition 2.40 (linked and independent S-boxes). Suppose that σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Let I be a part of ${\mathcal{I}}_{\text{ld}}$.

• If I = {i}, the S-box S_i is said to be independent of the other S-boxes.

  Moreover, if $V_{\mathrm{\left\{}i\mathrm{\right\}}}{=\mathrm{\{}0}_{nm}\mathrm{\}}$ or $V_{\mathrm{\left\{}i\mathrm{\right\}}}={\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}}$, the S-box S_i is said to be inactive. Otherwise, S_i is active.

• If #I ≥ 2, then the S-boxes whose indices lie in I are said to be linked together.

Remark 2.41. Let 0 ≤ i ≤ m be an integer. We have already noted that the substitution layer σ always preserves $\mathcal{L}{(\mathrm{\{}0}_{nm}\mathrm{\}})$ and $\mathcal{L}({\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}})$. In addition, Proposition 2.33 ensures that σ maps $\mathcal{L}(V_{\mathrm{\left\{}i\mathrm{\right\}}})$ to $\mathcal{L}(W_{\mathrm{\left\{}i\mathrm{\right\}}})$. Consequently, if $V_{\mathrm{\left\{}i\mathrm{\right\}}}{=\mathrm{\{}0}_{nm}\mathrm{\}}$ or if $V_{\mathrm{\left\{}i\mathrm{\right\}}}={\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}}$, then V_{i}= W_{i}.

Suppose that the S-box S_i is independent with regard to the subspaces V and W. As established by Proposition 2.33 and Remark 2.32, if S_i is replaced with another S-box ${S^{\prime }}_i$, then this new substitution layer still maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ provided that ${S^{\prime }}_i$ maps $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$.

Suppose further that S_i is active. By definition, ${\{0}_{nm}\}⊈V_{\mathrm{\left\{}i\mathrm{\right\}}}⊈{\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}}$. Observe that the restriction of T_{i} to Triv_{i} is one-to-one, hence

${\{0}_n\mathrm{\}}={\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}{(\{0}_{nm}\mathrm{\}})⊈{\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})⊈{\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}({\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}})={\mathbb{F}}_2^n.$E49

Thus, T_{i}(V_{i}) is a nontrivial subspace of ${\mathbb{F}}_2^n$ and the requirement that ${S^{\prime }}_i$ maps $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$ is also nontrivial. Therefore, an independent active S-box can be chosen independently of the other S-boxes but has to respect the structure of the subspaces V and W.

Now suppose that S_i is inactive. By definition, $V_{\mathrm{\left\{}i\mathrm{\right\}}}{=\mathrm{\{}0}_{nm}\mathrm{\}}$ or $V_{\mathrm{\left\{}i\mathrm{\right\}}}={\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}}$. Then, the equality $V_{\mathrm{\left\{}i\mathrm{\right\}}}=W_{\mathrm{\left\{}i\mathrm{\right\}}}$ follows from Remark 2.41 and we have that

${\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})={\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W_{\mathrm{\left\{}i\mathrm{\right\}}}{)=\{0}_n\mathrm{\}}\text{or}{\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})={\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W_{\mathrm{\left\{}i\mathrm{\right\}}})={\mathbb{F}}_2^n.$E50

In either case, the condition that ${S^{\prime }}_i$ maps $\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$ to $\mathcal{L}({\text{T}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W_{\mathrm{\left\{}i\mathrm{\right\}}})\mathrm{})$ is trivial, and any S-box fulfills it. As a consequence, an independent inactive S-box can be freely chosen. In other words, such an S-box has no impact on the fact that σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

Finally, suppose that some S-boxes are linked together. If only one of these S-boxes is replaced independently of the others, then the desired property of the substitution layer may not hold.

Example 2.42. As we have seen in Example 2.38 and Figure 2.11, the least decomposition partition with regard to the subspaces V and W is ${\mathcal{I}}_{\text{ld}}=\mathrm{\left\{}\mathrm{\right\{}1\mathrm{\}},\mathrm{\{}2\mathrm{\}},\mathrm{\{}\mathrm{0,3}\mathrm{\left\}}\mathrm{\right\}}$. By Proposition 2.33, the substitution layer maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ is and only if the following equalities hold:

$\begin{array}{cc}{\sigma }_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(V)))=\mathcal{L}({\text{T}}_{\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}}(W)\mathrm{}),& \begin{array}{cc}{S}_1(\mathcal{L}({\text{T}}_{\mathrm{\left\{}1\mathrm{\right\}}}(V)\mathrm{})& =\mathcal{L}({\text{T}}_{\mathrm{\left\{}1\mathrm{\right\}}}(W)\mathrm{}),\\ S_2(\mathcal{L}({\text{T}}_{\mathrm{\left\{}2\mathrm{\right\}}}(V)\mathrm{})& =\mathcal{L}({\text{T}}_{\mathrm{\left\{}2\mathrm{\right\}}}(W)\mathrm{}).\end{array}\end{array}$E51

Thus, the S-box S₁ is independent of the other S-boxes, the same applies to S₂ and the S-boxes S₀ and S₃ are linked together. As was already noted in Figure 2.9, we have that

$\begin{array}{ccc}{V}_{\mathrm{\left\{}1\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})\mathrm{\}}& \text{and}& V_{\mathrm{\left\{}2\mathrm{\right\}}}=\text{span}((\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{\text{A}},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7},\mathtt{0}\mathtt{0})\mathtt{}).\end{array}$E52

Therefore, the S-box S₂ is active while S₁ is inactive.▴

3.4. The forbidden case

Throughout this section, we assume that the substitution layer σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. In order to prove the last main theorem of this chapter, we need to consider the following particular case.

Proposition 2.43. Let $\mathcal{I}$ be a decomposition partition. Let I be a part of $\mathcal{I}$ such that #I ≥ 2 and let E be a nonempty proper subset of I. Suppose that $V_E=V_{I\backslash E}{=\mathrm{\{}0}_{nm}\mathrm{\}}$ and $\text{P}{}_E(V)={\text{Triv}}_E$. Then, for all i in E, S_i is an affine mapping.

If the subspace V satisfies the assumption of the proposition above, then at least one of S-boxes has to be affine. Nowadays, an SPN whose substitution layer has an affine S-box cannot be taken seriously. Additionally, such a cipher is likely to be very weak to differential and linear cryptanalysis. This discussion explains the title of this section.

Example 2.44. As seen in Example 2.38, the least decomposition partition is ${\mathcal{I}}_{\text{ld}}=\mathrm{\left\{}\mathrm{\right\{}1\mathrm{\}},\mathrm{\{}2\mathrm{\}},\mathrm{\{}\mathrm{0,3}\mathrm{\left\}}\mathrm{\right\}}$. Its only part of cardinality greater than or equal to 2 is $I=\mathrm{\left\{}\mathrm{0,3}\mathrm{\right\}}$. The nonempty proper subsets of I are the E = {0} and E = {1}. According to Figure 2.9, we have $V_{\mathrm{\left\{}0\mathrm{\right\}}}\ne {\mathrm{\{}0}_{20}\mathrm{\}}$. Consequently, Proposition 2.43 does not apply to this example, and this is good news because none of the S-boxes is affine. Otherwise, this would have disproved the contrapositive of Proposition 2.43.

Now let us introduce another example. Consider a substitution layer σ′ made up of two 3-bit S-boxes ${S^{\prime }}_0$ and ${S^{\prime }}_1$; hence, its parameters are m = 2 and n = 3. Define the subspaces V′ and W′ of ${({\mathbb{F}}_2^3)}^2$ by

$V^{\prime }=W^{\prime }=\text{span}((\mathtt{4},\mathtt{4}),(\mathtt{2},\mathtt{2}),(\mathtt{1},\mathtt{1}))=\mathrm{\{}(x,x)|x\in {\mathbb{F}}_{\mathtt{2}}^3\mathrm{\}}.$E53

Finally, suppose that σ′ maps $\mathcal{L}(V^{\prime })$ to $\mathcal{L}(W^{\prime })$. It is easily seen that

$\begin{array}{llll}{V^{\prime }}_{\varnothing }=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}0\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}1\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}=V,\hfill \\ {\text{P}}_{\varnothing }(V^{\prime })={\text{Triv}}_{\varnothing },\hfill & {\text{P}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V^{\prime })={\text{Triv}}_{\mathrm{\left\{}0\mathrm{\right\}}},\hfill & {\text{P}}_{\mathrm{\left\{}1\mathrm{\right\}}}(V^{\prime })={\text{Triv}}_{\mathrm{\left\{}1\mathrm{\right\}}},\hfill & {\text{P}}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}(V^{\prime })=V.\hfill \end{array}$E54

Thus, the least decomposition partition with regard to V′ and W′ is {{0, 1}}. The S-boxes ${S^{\prime }}_0$ and ${S^{\prime }}_1$ are then linked together. Choosing E = {0} in Proposition 2.43 ensures that ${S^{\prime }}_0$ must be affine. Similarly, we can prove that ${S^{\prime }}_1$ must also be affine by considering E = {1}. As a result, any substitution layer σ′ mapping $\mathcal{L}(V^{\prime })$ to $\mathcal{L}(W^{\prime })$ is necessary affine. These subspaces are thus completely prohibited as the whole cipher is then affine.▴

3.5. Reduction to one S-box

To prove our main result about the substitution layer, we need the following preliminary lemma.

Lemma 2.45. Let I be a part of ${\mathcal{I}}_{\text{ld}}$ and E be a non-empty proper subset of I.

• If V_E is a trivial product subspace, then $V_E={\text{Triv}}_{\varnothing }{=\mathrm{\{}0}_{nm}\mathrm{\}}$.

• If P_E(V) is a trivial product subspace, then ${\text{P}}_E(V)={\text{Triv}}_E$.

Now we have all the results needed, let us state and prove the main result of Section 3 which is depicted in Figure 2.12.

Figure 2.12.

Diagrammatic representation of Theorem 2.46.

Theorem 2.46. Let n ≥ 2 and m be two positive integers. Let S₀,…,S_m–1 be n-bit S-boxes. Define the permutation σ of ${({\mathbb{F}}_2^n)}^m$, which maps the element ${(x_i)}_{0\le i<m}$ to ${(S_i(x_i)\mathrm{})}_{0\le i<m}$. Let V and W be two subspaces of ${({\mathbb{F}}_2^n)}^m$ such that σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Suppose that V is not a trivial product subspace. Then, at least one of the S-boxes maps a nontrivial linear partition to another one.

Proof. Let us prove this result by complete induction on the number m of S-boxes. Suppose that m = 1. In this case, σ = S₀. By hypothesis, V is different from {0_n} and ${\mathbb{F}}_2^n$. Hence, $\mathcal{L}(V)$ is a nontrivial partition and S₀ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

Let m ≥ 2 be an integer. Suppose that the result holds for any positive integer strictly lower than m. First, suppose that all the S-boxes are independent. In other words, ${\mathcal{I}}_{\text{ld}}=\mathrm{\left\{}\mathrm{\right\{}i\mathrm{\left\}}\right|i\in 〚\mathrm{0,}m〚\mathrm{\}}$. If each S-box is inactive, then V is a trivial product subspace, a contradiction with our hypothesis. Thus, there exists at least one active S-box S_i. In this case, ${\mathrm{\{}0}_{nm}\mathrm{\}}⊈V_{\mathrm{\left\{}i\mathrm{\right\}}}⊈{\text{Triv}}_{\mathrm{\left\{}i\mathrm{\right\}}}$. According to Lemma 2.31, the equality $\text{P}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)=V_{\mathrm{\left\{}i\mathrm{\right\}}}$ holds. Then, $\text{T}{}_{\mathrm{\left\{}i\mathrm{\right\}}}(V_{\mathrm{\left\{}i\mathrm{\right\}}})=\text{T}{}_{\mathrm{\left\{}i\mathrm{\right\}}}(\text{P}{}_{\mathrm{\left\{}i\mathrm{\right\}}}(V))=\text{T}{}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)$ is a nontrivial subspace of ${\mathbb{F}}_2^n$, so $\mathcal{L}(\text{T}{}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)\mathrm{})$ is also nontrivial. Finally, Proposition 2.22 states that S_i maps $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(V)\mathrm{})$ to $\mathcal{L}(\text{T}{\text{}}_{\mathrm{\left\{}i\mathrm{\right\}}}(W)\mathrm{})$, and thus the result holds in this case.

Now, suppose that some S-boxes are linked together. Then, there exists an element I of ${\mathcal{I}}_{\text{ld}}$ such that #I ≥ 2. Next, at least one of the following three cases holds.

1. Suppose that there exists a nonempty proper subset E of I such that P_E(V) is not a trivial product subspace. Let p denote the cardinality of E. Recall that ${\text{T}}_E({\text{P}}_E(V))={\text{T}}_E(V)$. It follows that T_E(V) is not a trivial product subspace of ${({\mathbb{F}}_2^n)}^p$. According to Proposition 2.22, σ_E maps $\mathcal{L}({\text{T}}_E(V)\mathrm{})$ to $\mathcal{L}({\text{T}}_E(W)\mathrm{})$. Note that E is a non-empty proper subset of I, so of $〚\mathrm{0,}m〚$. Hence p < m, so the induction hypothesis ensures that at least one of the S-boxes of σ_m maps a nontrivial partition to another one.

2. Suppose that there exists a nonempty proper subset E of I such that V_E is not a trivial product subspace. Recall that σ maps $\mathcal{L}(V_E)$ to $\mathcal{L}(W_E)$. Proposition 2.22 ensures that σ_E maps $\mathcal{L}({\text{T}}_E(V_E)\mathrm{})$ to $\mathcal{L}({\text{T}}_E(W_E)\mathrm{})$. It is easily seen that T_E(V_E) is not a trivial product subspace. As before, the result is a consequence of the induction hypothesis.

3. Suppose that there exists a nonempty proper subset E of I such that ${\text{P}}_E(V)$, V_E and V_I\E are all trivial product subspaces. Then, Lemma 2.45 implies that P_E(V) = Triv_E and $V_E=V_{I\backslash E}{=\mathrm{\{}0}_{nm}\mathrm{\}}$. According to Proposition 2.43, the S-boxes whose indices belong to E are affine mappings. Combining Proposition 2.15 and 2.13, we see that these S-boxes map any non-trivial linear partition to another one.

In any case, the result holds for this integer m. The result follows by induction. ▪

Example 2.47. It is worthwhile to note that the proof of Theorem 2.46 is constructive. Therefore, it gives a method to find necessary conditions on the S-boxes for the substitution layer to map $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Let us apply this method to our main example.

The first step is equivalent to what had been done in Examples 2.38 and 2.42. Consider the least decomposition partition ${\mathcal{I}}_{\text{ld}}=\mathrm{\left\{}\mathrm{\right\{}1\mathrm{\}},\mathrm{\{}2\mathrm{\}},\mathrm{\{}\mathrm{0,3}\mathrm{\left\}}\mathrm{\right\}}$ and deduce that:

• S₁ is inactive;

• S₂ is active and maps $\mathcal{L}(\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})\mathrm{})$ to $\mathcal{L}(\text{span}(\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{2})\mathrm{})$ (see Figure 2.2);

• S₀ and S₃ are linked together.

Now, consider the part I = {0,3} of ${\mathcal{I}}_{\text{ld}}$. Thus, the nonempty proper subsets of I are {0} and {3}. The first case requires to compute the following projections:

${\text{P}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V)={\text{Triv}}_{\mathrm{\left\{}0\mathrm{\right\}}}\text{and}{\text{P}}_{\mathrm{\left\{}3\mathrm{\right\}}}(V)=\text{span}((\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{\text{B}}),(\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{\text{C}})\mathtt{}).$E55

Thus, P_{3}(V) is not a trivial product subspace. As in Example 2.24 and Figure 2.8, we see that S₃ maps $\mathcal{L}(\mathtt{0}\mathtt{\text{B}},\mathtt{1}\mathtt{\text{C}})$ to $\mathcal{L}(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{5})$ by truncating σ and the subspaces ${\text{P}}_{\mathrm{\left\{}3\mathrm{\right\}}}(V)$, ${\text{P}}_{\mathrm{\left\{}3\mathrm{\right\}}}(W)$ to {3}. Now, we need to compute the following subspaces:

$\begin{array}{ccc}{V}_{\mathrm{\left\{}0\mathrm{\right\}}}=\text{span}((\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}),(\mathtt{1}\mathtt{5},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})\mathtt{})& \text{and}& V_{\mathrm{\left\{}3\mathrm{\right\}}}={\text{Triv}}_{\varnothing }.\end{array}$E56

Since V_{0} is not a trivial product subspace, the second case apply. Then, truncate the substitution layer σ and the subspaces V_{0} and W_{0} to prove that S₀ maps $\mathcal{L}(\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{\text{D}},\mathtt{1}\mathtt{5})$ to $\mathcal{L}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{4})$. This property was stressed in Example 2.28 and Figure 2.9. Finally, recall that the third case does not apply to these subspaces, as observed in Example 2.44.▴

The preceding example covers only the first and the second cases in the treatment of linked S-boxes given by the proof of Theorem 2.46. To illustrate the third case, we introduced the following example.

Example 2.48. Let n = m = 3. Thus, the substitution layer σ is made up of three 3-bit S-boxes denoted by S₀, S₁ and S₂. Define the subspaces V and W of ${({\mathbb{F}}_2^3)}^3$ by

$V=W=\mathrm{\{}(x,y,x+y)|x,y\in {\mathbb{F}}_2^3\mathrm{\}}$E57

and assume that the substitution layer σ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. By definition, it holds that ${\text{P}}_{\varnothing }(V)=\mathrm{\{}(\mathtt{0},\mathtt{0},\mathtt{0})\mathrm{\}}$ and ${\text{P}}_{\mathrm{\left\{}\mathrm{0,1,2}\mathrm{\right\}}}(V)=V$. Then, for each nonempty proper subset E of {0,1,2}, it is easily seen that ${\text{P}}_E(V)={\text{Triv}}_E$. For instance,

${\text{P}}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}(V)=\mathrm{\{}(x,y,\mathtt{0})|x,y\in {\mathbb{F}}_2^3\mathrm{\}}={\text{Triv}}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}.$E58

We know that $V_{\varnothing }=\mathrm{\{}(\mathtt{0},\mathtt{0},\mathtt{0})\mathrm{\}}$ and $V_{\mathrm{\left\{}\mathrm{0,1,2}\mathrm{\right\}}}(V)=V$. The other subspaces V_E are the following:

$\begin{array}{lll}{V}_{\mathrm{\left\{}0\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & V_{\mathrm{\left\{}1\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & V_{\mathrm{\left\{}2\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0},\mathtt{0})\mathrm{\}},\hfill \\ V_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}=\mathrm{\{}(x,x,\mathtt{0})|x\in {\mathbb{F}}_2^3\mathrm{\}},\hfill & V_{\mathrm{\left\{}\mathrm{0,2}\mathrm{\right\}}}=\mathrm{\{}(x,\mathtt{0},x)|x\in {\mathbb{F}}_2^3\mathrm{\}},\hfill & V_{\mathrm{\left\{}\mathrm{1,2}\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},x,x)|x\in {\mathbb{F}}_2^3\mathrm{\}}.\hfill \end{array}$E59

Thus, the equality ${\text{P}}_E(V)=V_E$ holds only for $E=\varnothing$ and E = {0,1,2}. Consequently, the least decomposition partition is ${\mathcal{I}}_{\text{ld}}=\mathrm{\left\{}\mathrm{\right\{}\mathtt{0},\mathtt{1},\mathtt{2}\mathrm{\left\}}\mathrm{\right\}}$, and hence, all the S-boxes are linked together.

From now on, we follow the method given in the proof of Theorem 2.46. As previously noted, for each nonempty proper subset E of {0,1,2}, the projection P_E(V) is a trivial product. Therefore, the first case does not apply to this example. We move on to the second case. By induction, the substitution layer and the subspaces V_{0,1} and W_{0,1} are truncated to {0,1}. Hence, we now consider the permutation σ′ = σ_{0,1}, which maps $\mathcal{L}(V^{\prime })$ to $\mathcal{L}(W^{\prime })$ where

$V^{\prime }=W^{\prime }=\text{T}{\text{}}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}(V_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}})=\mathrm{\{}(x,x)|x\in {\mathbb{F}}_2^3\mathrm{\}}.$E60

Such a substitution layer has already been studied in Example 2.44. Recall that

$\begin{array}{llll}{V^{\prime }}_{\varnothing }=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}0\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}1\mathrm{\right\}}}=\mathrm{\{}(\mathtt{0},\mathtt{0})\mathrm{\}},\hfill & {V^{\prime }}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}=V,\hfill \\ {\text{P}}_{\varnothing }(V^{\prime })={\text{Triv}}_{\varnothing },\hfill & {\text{P}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V^{\prime })={\text{Triv}}_{\mathrm{\left\{}0\mathrm{\right\}}},\hfill & {\text{P}}_{\mathrm{\left\{}1\mathrm{\right\}}}(V^{\prime })={\text{Triv}}_{\mathrm{\left\{}1\mathrm{\right\}}},\hfill & {\text{P}}_{\mathrm{\left\{}\mathrm{0,1}\mathrm{\right\}}}(V^{\prime })=V.\hfill \end{array}$E61

Thus, the least decomposition partition with regard to V′ and W′ is {{0,1}}. Since ${V^{\prime }}_{\mathrm{\left\{}0\mathrm{\right\}}}$, ${V^{\prime }}_{\mathrm{\left\{}1\mathrm{\right\}}}$, ${\text{P}}_{\mathrm{\left\{}0\mathrm{\right\}}}(V^{\prime })$ and ${\text{P}}_{\mathrm{\left\{}1\mathrm{\right\}}}(V^{\prime })$ are all trivial products, the first and second cases do not apply. Choosing E = {0} and E = {1} in the third case proves that S₀ and S₁ are affine mappings. Come back to the full substitution layer. Similarly, it is straightforward to verify that S₂ must be affine by truncating σ and the subspaces V_{0,2}, W_{0,2} to {0,2}. To summarize, we have proven that any substitution layer mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$ is necessarily affine.▴

In this chapter, we have studied a generic SPN mapping a partition $\mathcal{A}$ of ${\mathbb{F}}_2^{nm}$ to a partition $\mathcal{B}$ of ${\mathbb{F}}_2^{nm}$, independently of the round keys used. Combining Theorem 2.17 and Corollary 2.18, we proved that there exist two families ${(V^{[i]})}_{0\le i\le r}$ and ${(W^{[i]})}_{0\le i\le r}$ of subspaces of ${\mathbb{F}}_2^{nm}$ such that the substitution layer σ maps $\mathcal{L}(V^{[i]})$ to $\mathcal{L}(W^{[i]})$ for each 0 ≤ i ≤ r. This result has been illustrated in Figure 2.5.

First, suppose that all the V^[i] are trivial products. In such a case, the diffusion layer of the cipher is probably not playing its role (or the round number is very small). As is generally the case, suppose that there is no diffusion layer in the last round of the SPN. Then, the input and the output partitions are both linear partitions associated with a trivial product subspace. This implies that some ciphertext bits are independent of some plaintext bits. Such a property must be avoided in any good cipher.

Now, suppose that at least one of the V^[i] is not a trivial product. This second case is far more interesting than the previous one. By virtue of Theorem 2.46, at least one of the S-boxes must map a nontrivial linear partition to another one, as illustrated in Figure 2.12.

Thus, we have proven in this chapter that any good partition-based trapdoor SPN has at least on S-box mapping a nontrivial linear partition to another one. The following chapter aims to design such an S-box with the best security against both differential and linear cryptanalysis.

Analysis of a backdoor S-box

Differential [21] and linear [22] cryptanalysis are considered as the most important attacks against block ciphers [23]. The resistance of an S-box against these attacks is assessed by its difference distribution table and its linear approximation table respectively.

Let S be an n-bit S-box. The difference distribution table and the linear distribution table of S are the two families DT_S and LT_S indexed by ${({\mathbb{F}}_2^n)}^2$ and defined for any (a, b) in ${({\mathbb{F}}_2^n)}^2$ by

$\begin{array}{l}D{T}_S(a,b)=\#\mathrm{\{}x\in {\mathbb{F}}_2^n|S(x)+S(x+a)=b\mathrm{\}},\\ L{T}_S(a,b)=\#\mathrm{\{}x\in {\mathbb{F}}_2^n|⟨a,x⟩=⟨b,S(x)⟩\mathrm{\}}-2^{n-1}.\end{array}$E62

Moreover, the S-box S is said to be differentially δ-uniform if $\mathrm{D}{\mathrm{T}}_S(a,b)\le \delta$ for any (a, b) in ${({\mathbb{F}}_2^n)}^2$ with a ≠ 0. Similarly, S is linearly λ-uniform if $\left|\mathrm{L}{\mathrm{T}}_S(a,b)\right|\le \lambda$ for every (a, b) in ${({\mathbb{F}}_2^n)}^2$ with b ≠ 0. It is worthwhile to mention that the smaller the differential uniformity is, the more resistant S is against differential cryptanalysis. The same applies for linear cryptanalysis.

Remark 3.1. It can be proven that any n-bit S-box is at least linearly $2^{\frac{n-1}{2}}$-uniform.

Recall that two permutations S₁ and S₂ of ${\mathbb{F}}_2^n$ are said to be equivalent if there exist two linear mappings L₁, L₂ of ${\mathbb{F}}_2^n$ and two elements v₁, v₂ of ${\mathbb{F}}_2^n$ such that

$\begin{array}{cc}\forall x\in {\mathbb{F}}_2^n,& S_2(x)=L_2(S_1(L_1(x)+v_1)\mathrm{})+v_2.\end{array}$E63

It is well known that equivalent permutations have the same differential uniformity and the same linear uniformity, see for instance [24, 25]. More precisely, their differential tables are equal up to row and column permutations. This result holds for linear tables up to the sign of the coefficients.

Let V and W be two subspaces of ${\mathbb{F}}_2^n$. Suppose that S′ is an n-bit S-Box mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Proposition 2.11 ensures that there exists an automorphism L of ${\mathbb{F}}_2^n$ such that $L(V)=W$. Since $L^{-1}(W)=V$, Proposition 2.15 states that L⁻¹ maps $\mathcal{L}(W)$ to $\mathcal{L}(V)$. Then, $S=L^{-1}\circ S^{\prime }$ is equivalent to S′ and maps $\mathcal{L}(V)$ to $\mathcal{L}(V)$. This discussion establishes the following proposition.

Proposition 3.2. Let V and W be two subspaces of ${\mathbb{F}}_2^n$. If S′ is an n-bit S-box mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$, then there exists an S-box S equivalent to S′ preserving $\mathcal{L}(V)$.

Remark 3.3. Conversely, suppose that S preserves $\mathcal{L}(V)$. Let W be any subspace isomorphic to V. Then find an automorphism L such that L(V) = W. By Proposition 2.15, $L\circ S$ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

As with Section 3, let us introduce an example that we will continue throughout this section.

Example 3.4. Consider the 5-bit S-box S′ given in Figure 3.1. This S-box has already been met twice in Examples 2.7 and 2.19 (refered to as f and S₂ respectively). Thus, we know that S′ maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ where $V=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})$ and $W=\text{span}(\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{2})$. Following the proof of Proposition 2.11, an automorphism L of ${\mathbb{F}}_2^5$ satisfying L(V) = W was constructed in Example 2.12. Its inverse L⁻¹ and the composition S = L⁻¹S′ are given in Figure 3.1. For instance, $S(\mathtt{0}\mathtt{7})=L^{-1}(S^{\prime }(\mathtt{0}\mathtt{7}))=L^{-1}(\mathtt{1}\mathtt{0})=\mathtt{1}\mathtt{8}$. It is easy to check in Figure 3.2 that S preserves the linear partition $\mathcal{L}(V)$. Finally, it is worth observing how Figures 2.2 and 3.2 look similar. This explains our choices to construct the automorphism L.▴

Figure 3.1.

Construction of the S-box S used throughout Chapter 3.

Figure 3.2.

The permutation S preserving $\mathcal{L}(V)$ where $V=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})$.

By virtue of Proposition 3.2, we can assume without loss of generality that V = W in our study of the linear and differential properties of an S-box mapping $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

Throughout this section, we consider the following

• let V be a d-dimensional nontrivial subspace of ${\mathbb{F}}_2^n$,

• let U be a complement space of V,

• let S be an n-bit S-box preserving $\mathcal{L}(V)$.

Therefore, the space ${\mathbb{F}}_2^n$ can be written as the direct sum $U\oplus V$. In other words, every element x of ${\mathbb{F}}_2^n$ can be uniquely written as the sum x = u + v where u and v belong to U and V, respectively. Let [u] denote the coset of V with respect to u. Thus, [u] = u + V is the unique part of $\mathcal{L}(V)$ where u lies in and we have

$\mathcal{L}(V)=\mathrm{\{}[u]|u\in U\mathrm{\}}.$E64

Since V is d-dimensional, the complement space U is (n – d)-dimensional. In addition, we have the following inequalities

$\begin{array}{ccc}1\le d\le n-1& \text{and}& 1\le n-d\le n-1\end{array}$E65

because V is assumed to be a nontrivial subspace of ${\mathbb{F}}_2^n$.

The following theorem describes the structure of permutations preserving a linear partition. It can be seen as a corollary of the Krasner-Kaloujnine embedding theorem [26]. However, for convenience, we give a direct constructive proof.

Theorem 3.5. There exist a unique permutation ρ of U and a unique family of permutations ${({\tau }_u)}_{u\in U}$ of V such that, for all x = u + v in ${\mathbb{F}}_2^n$,

$S(u+v)=\rho (u)+{\tau }_u(v).$E66

Conversely, if ρ is a permutation of U and if ${({\tau }_u)}_{u\in U}$ is a family of permutations of V, then the mapping S′ defined by $S^{\prime }(u+v)=\rho (u)+{\tau }_u(v)$ preserves $\mathcal{L}(V)$.

Proof. By hypothesis, S preserves $\mathcal{L}(V)$. Thus, S induces a permutation ρ of U defined as follows. Let u be an element of U. Hence, there exists a unique u′ in U such as $f([u])=[u^{\prime }]$. Define then $\rho (u)=u^{\prime }$. For each element u of U, define the permutation τ_u of V, which maps v to $S(u+v)+\rho (u)$. By construction, for any u in U and any v in V, we have

$\begin{array}{ccc}{\tau }_u(v)=S(u+v)+\rho (u)& \text{and}\text{hence}& S(u+v)=\rho (u)+{\tau }_u(v).\end{array}$E67

The existence of the permutations ρ and τ_u is proven. Now, let us show their uniqueness. Suppose that there exist a permutation ${\displaystyle \tilde{\rho }}$ of U and a family of permutations ${({{\displaystyle \tilde{\tau }}}_u)}_{u\in U}$ of V satisfying the result. Let (u, v) be an element of U × V. By hypothesis, we have

$\rho (u)+{\tau }_u(v)={\displaystyle \tilde{\rho }}(u)+{{\displaystyle \tilde{\tau }}}_u(v).$E68

Because the sum of U and V is direct, it follows that $\rho (u)={\displaystyle \tilde{\rho }}(u)$ and ${\tau }_u(v)={{\displaystyle \tilde{\tau }}}_u(v)$. The uniqueness of ρ and the τ_u follows.

Conversely, let ρ be a permutation of U and ${({\tau }_u)}_{u\in U}$ be a family of permutations of V. Denote S′ the mapping from ${\mathbb{F}}_2^n$ to ${\mathbb{F}}_2^n$ defined by $S^{\prime }(u+v)=\rho (u)+{\tau }_u(v)$. Since ${\mathbb{F}}_2^n=U\oplus V$ and ρ and the τ_u are permutations of U and V respectively, The mapping S′ is a permutation of ${\mathbb{F}}_2^n$. Let u be an element of U. It holds that

$\begin{array}{cc}{S}^{\prime }([u])& =\mathrm{\{}{S}^{\prime }(u+v)|v\in V\mathrm{\}}=\mathrm{\{}\rho (u)+{\tau }_u(v)|v\in V\mathrm{\}}\\ & =\rho (u)+\mathrm{\{}{\tau }_u(v)|v\in V\mathrm{\}}=\rho (u)+V=[\rho (u\mathrm{})].\end{array}$E69

Hence, S′ preserves the linear partition $\mathcal{L}(V)$. ▪

This theorem allows us to design an S-box that preserves $\mathcal{L}(V)$ using permutations with smaller domains. Furthermore, these permutations can be chosen arbitrarily.

Example 3.6. Consider the complement subspace U of V defined by

$U=\text{span}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{8})=\mathrm{\{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{8},\mathtt{0}\mathtt{9},\mathtt{0}\mathtt{\text{A}},\mathtt{0}\mathtt{\text{B}}\mathrm{\}}.$E70

Figure 3.2 shows that S induces a permutation ρ of U. For instance, $\rho (00)=02$ because S maps the part [00] to [02]. The whole permutation ρ is given in Figure 3.3. For each u in U, define the permutation τ_u of V by ${\tau }_u(v)=S(u+v)+\rho (u)$. For example,

${\tau }_{02}(\mathtt{1}\mathtt{\text{D}})=S(\mathtt{0}\mathtt{2}+\mathtt{1}\mathtt{\text{D}})+\rho (\mathtt{0}\mathtt{2})=S(\mathtt{1}\mathtt{\text{F}})+\rho (\mathtt{0}\mathtt{2})=\mathtt{1}\mathtt{2}+\mathtt{0}\mathtt{8}=\mathtt{1}\mathtt{\text{A}}.$E71

Figure 3.3.

The permutation S preserving $\mathcal{L}(V)$ where $V=\text{span}(\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})$.

The permutations τ_u are also given in Figure 3.3. Informally, the permutation ρ tells us how S permutes the parts of $\mathcal{L}(V)$ and the permutations ${({\tau }_u)}_{u\in U}$ describe how the elements are moved inside each part (Figure 3.4).▴

Figure 3.4.

The linear transformations L_U and L_V.

In the rest of this section, the permutation ρ and the family ${({\tau }_u)}_{u\in U}$ given by Theorem 3.5 are fixed.

The goal of this part is to express the linear and differential properties of S according to the ones of the permutations ρ and ${({\tau }_u)}_{u\in U}$. However, these permutations are not defined on ${\mathbb{F}}_2^n$ but on the subspaces U and V of ${\mathbb{F}}_2^n$. Thus, the concept of linear or differential table is inexistent for such maps. To solve this problem, we define two isomorphisms between U and ${\mathbb{F}}_2^{n-d}$ and between V and ${\mathbb{F}}_2^d$. Then, we consider the maps induced by ρ and ${({\tau }_u)}_{u\in U}$ on these spaces.

Notation 3.7. Let ${\mathcal{B}}_{\mathcal{U}}=(\mathrm{}{u}_i{)}_{i<n-d}$ and ${\mathcal{B}}_{\mathcal{V}}=(\mathrm{}{v}_i{)}_{i<n-d}$ be two bases of U and V respectively. Define the following mappings:

$\begin{array}{cc}{L}_U:{\mathbb{F}}_2^{n-d}\to U& L_V:{\mathbb{F}}_2^d\to V\\ (x_{n-d-1},\dots ,x_0)\mapsto {\displaystyle {\sum }_{i-0}^{n-d-1}{x}_i{u}_i,}& (y_{d-1},\dots ,y_0)\mapsto {\displaystyle {\sum }_{i=0}^{d-1}{y}_i{v}_i.}\end{array}$E72

It is easily seen that L_U and L_V are both isomorphisms of vector spaces. Define the permutation ${\rho }^{\prime }=L_U^{-1}\rho L_U$ of ${\mathbb{F}}_2^{n-d}$. Finally, for each u in U, let ${{\tau }^{\prime }}_u$ denote the permutation $L_V^{-1}{\tau }_u{L}_V$ of ${\mathbb{F}}_2^d$.

Example 3.8. Consider the bases ${\mathcal{B}}_U=(\mathrm{}\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{8})$ and ${\mathcal{B}}_V=(\mathrm{}\mathtt{0}\mathtt{7},\mathtt{1}\mathtt{\text{A}})$ and define the isomorphisms L_U and L_V. The permutation ρ′ of ${\mathbb{F}}_2^3$ and the permutations ${{\tau }^{\prime }}_u$ of ${\mathbb{F}}_2^2$ are given in Figure 3.5.▴

Figure 3.5.

The family of permutations ${({{\tau }^{\prime }}_u)}_{u\in U}$ and the permutation ρ′.

1. Linear approximation table

The next theorem links the linear tables of S and ρ′. The coefficients of the linear approximation table of S taken into account by this result are in practice the greatest. Thus, they generally determine the linear uniformity of S.

Theorem 3.9. Let a and b be two elements of $V^{\perp }$. Denote $a^t=L_U^{⊺}(a)$ and $b^t=L_U^{⊺}(b)$. Then,

$L{T}_S(a,b{)=2}^d\times L{T}_{{\rho }^{\prime }}(a^t,b^t).$E73

Remark 3.10. Consider the map $L_U^{⊺}:{\mathbb{F}}_2^n\to {\mathbb{F}}_2^{n-d}$. Then, $\ker (L_U^{⊺})=(\mathrm{Im}{L}_U{)}^{\perp }=U^{\perp }.$ Observe that $U^{\perp }\cap V^{\perp }=(\mathrm{}U+V{)}^{\perp }=(\mathrm{}{\mathbb{F}}_2^n{)}^{\perp }=\mathrm{\left\{}0\mathrm{\right\}}$. Consequently, the restriction $L_U^{⊺}:V^{\perp }\to {\mathbb{F}}_2^{n-d}$ is one-to-one and thus onto because of the rank-nullity theorem.

Example 3.11. The restriction $L_U^{⊺}:V^{\perp }\to {\mathbb{F}}_2^3$ is given by the following table.

a	00	05	0B	0E	13	16	18	1D
$L_U^{⊺}(a)$	0	1	7	6	3	2	4	5

Reorder the rows and the columns of the linear approximation table of S to begin with ${((L_U^{⊺}{)}^{-1}(x)\mathrm{})}_{x\in {\mathbb{F}}_2^3}$, as suggested by Theorem 3.9. The reordered linear table is shown in Figure 3.6. Each dot “⋅” in this figure stands for the integer 0. With this order, it is easily seen that the top left part of LT_S is exactly the linear table of ρ′ multiplied by 2^d = 4. For instance, ${\text{LT}}_S(\mathtt{1}\mathtt{\text{D}},\mathtt{1}\mathtt{6}{)=2}^2\times {\text{LT}}_{{\rho }^{\prime }}(\mathtt{5},\mathtt{2})=-8$ because $L_U^{⊺}(\mathtt{1}\mathtt{\text{D}})=5$ and $L_U^{⊺}(\mathtt{1}\mathtt{6})=2$.▴

Figure 3.6.

The reordered linear table of S.

Corollary 3.12. The S-box S is at least linearly $2^{(n+d-1)/2}$-uniform.

Proof. As noted in Remark 3.1, there exist two elements a^t and b^t of ${\mathbb{F}}_2^{n-d}$ both nonzero such that $\left|{\text{LT}}_{{\rho }^{\prime }}(a^t,b^t)\right|\ge 2^{(n-d-1)/2}$. Let a and b denote the elements ${(L_U^{⊺})}^{-1}(a^t)$ and ${(L_U^{⊺})}^{-1}(b^t)$ of ${\mathbb{F}}_2^n$. Then, Theorem 3.9 implies that

$\left|{\text{LT}}_S(a,b)\right|{=2}^d\times |{\text{LT}}_{{\rho }^{\prime }}(a^t,b^t)|\ge 2^d\times 2^{(n-d-1)/2}{=2}^{(n+d-1)/2}.$E74

Observe that a and b are nonzero and the result is proven. ▪

Remark 3.13. It is well-known that any 4-bit S-box is at least linearly 4-uniform, see for example [27]. As a consequence, the permutation S is at least 2^d+2-uniform if n–d = 4. Similarly, any 2-bit S-Box is linearly 2-uniform, and hence S is at least 2^d+1-uniform if n – d = 2.

Example 3.14. It is easily seen that S is linearly 8-uniform in Figure 3.6. The lower bound given by Corollary 3.12 is $2^{(n+d-1)/2}{=2}^{(5+2-1)/2}=8$. Therefore, this bound is tight on this example.▴

2. Differential distribution table

Unlike linear cryptanalysis, where only a local view of the table was provided, the results for differential cryptanalysis bring both local and global outlooks.

Theorem 3.15. Let $a=u_a+v_a$ and $b=u_b+v_b$ be elements of ${\mathbb{F}}_2^n$. Denote ${u^{\prime }}_a=L_U^{-1}(u_a)$ and ${u^{\prime }}_b=L_U^{-1}(u_b)$. Then

${\displaystyle {\displaystyle \sum _{i\in [u_a]}}}{\text{DT}}_S(i,b)={\displaystyle {\displaystyle \sum _{j\in [u_b]}}}{\text{DT}}_S(a,j{)=2}^d\times {\text{DT}}_{{\rho }^{\prime }}({u^{\prime }}_a,{u^{\prime }}_b).$E75

Especially, ${\text{DT}}_S(a,b)\le 2^d\times {\text{DT}}_{{\rho }^{\prime }}({u^{\prime }}_a,{u^{\prime }}_b)$.

The preceding theorem can be restated in the following way. If DT_S is rearranged coset by coset, a simple operation enables recovery of DTρ′. On the other hand, the next theorem is similar to Theorem 3.9 but for differential cryptanalysis. Again, it generally highlights the coefficients of DT_S involved in the differential uniformity of S.

Theorem 3.16. Let v_a and v_b be two elements of V. Denote ${v^{\prime }}_a=L_V^{-1}(v_a)$ and ${v^{\prime }}_b=L_V^{-1}(v_b)$. Then

${\text{DT}}_S(v_a,v_b)={\displaystyle {\displaystyle \sum _{u\in U}}}{\text{DT}}_{{{\tau }^{\prime }}_u}({v^{\prime }}_a,{v^{\prime }}_b).$E76

Particularly, the subtable ${({\text{DT}}_S(v_a,v_b)\mathrm{})}_{v_a,v_b\in V}$ is uniquely determined by the differential tables ${({\text{DT}}_{{{\tau }^{\prime }}_u})}_{u\in U}$.

Example 3.17. To illustrate Theorems 3.15 and 3.16, reorder the rows and the columns of the differential table of S as presented in Figure 3.7. With this order, we can see the differential table of ρ′ by considering the differential table of S coset by coset. In fact, Theorem 3.15 states that the sum of all elements in the same row or column of the subtable ${\text{DT}}_S([u_1],[u_2])$ is equal to the coefficient (x₁, x₂) of ${\text{DT}}_{{\rho }^{\prime }}$ multiplied by 2², where $x_i=L_V^{-1}(u_i)$. For instance, if we consider the subtable

Figure 3.7.

The reordered differential table of S.

we can see that the sum of each row or column is equal to ${8=2}^2\times {\text{DT}}_{{\mathit{\rho }}^{\prime }}(\mathtt{5},\mathtt{3})$ since L_V(5) = 09 and L_V(3) = 03.

Finally, Theorem 3.16 ensures that the subtable ${\text{DT}}_S(V,V)={\text{DT}}_S([\mathtt{0}\mathtt{0}],[\mathtt{0}\mathtt{0}])$ is the sum of the differential tables ${({\text{DT}}_{{{\tau }^{\prime }}_u})}_{u\in U}$.▴

Corollary 3.18. The permutation S is at least δ-uniform for the differential cryptanalysis where δ denotes the even integer directly greater than or equal to $\frac{2^n}{2^d-1}$.

Example 3.19. In Figure 3.7, we can see that S is differentially 12-uniform. Thus, this S-box reaches the lower bound given by Corollary 3.18.▴

3. The design of a trapdoor S-box

First, let us summarize the theorems of this section.

• Theorem 3.9 implies to reduce at most the linear uniformity of ρ′ to keep the one of S as small as possible.

• In the same way, Theorem 3.15 implies to reduce at most the differential uniformity of ρ′.

• The same theorem also stresses that the greater the number of nonzero coefficients of ${\text{DT}}_{{\rho }^{\prime }}$ is, the better.

• Finally, Theorem 3.16 teaches us that the sum of the differential distribution tables $D{T}_{{{\tau }^{\prime }}_u}$ should be as low as possible.

Now, to design the S-box S, one needs to pick a permutation ρ′ of ${\mathbb{F}}_2^{n-d}$ with the smallest uniformities for linear and differential cryptanalysis. Then, one searches for permutations ${{\tau }^{\prime }}_u$ of ${\mathbb{F}}_2^d$ satisfying the last condition. This search can be conducted randomly over every d-bit S-boxes. Finally, construct the S-box S as in the converse of Theorem 3.5. If the differential and linear uniformities of S are too far from the lower bounds given by Corollaries 3.12 and 3.18 and by Remark 3.13, then start again. In practice, these bounds are reached (or almost reached) after a small number of iterations.

Moreover, observe that the closer the dimension d of V from n is, the weaker the S-box S is against linear cryptanalysis and the stronger S is against differential cryptanalysis. The lower bounds given by Corollaries 3.12 and 3.18 and by Remark 3.13 are given in Figure 3.8 for each 3 ≤ n ≤ 8.

Figure 3.8.

Lower bounds for the linear (left) and differential (right) uniformities of S.

Finally, it should be highlighted that these results can be used to easily prove that a given S-box does not map any linear partition to another one. For instance, the linear and differential uniformities of the S-box of Rijndeal [11] are far below the lower bounds given by Corollaries 3.12 and 3.18, no matter what the dimension d of the subspace V is. As a consequence, this S-box does not map any linear partition to another linear one.

Backdoored Encryption Algorithm 1

BEA-1 [28] (Backdoored Encryption Algorithm) is an AES-like cipher together with a backdoor based on the theory developed in Chapters 2 and 3. This cipher is designed to resist linear and differential cryptanalysis. Nonetheless, the backdoor enables recovery of the full 120-bit cipher key in just a few seconds on a laptop computer using 2¹⁶ chosen plaintext blocks, as presented in [29].

This chapter is organized as follows. First, the specification of the cipher BEA-1 and its security analysis against linear and differential cryptanalysis are given in Section 1. Then, Section 2 explains the hidden property of the algorithm and its design. To conclude, the cryptanalysis exploiting the backdoor is detailed in Sections 3 and 4.

1. Presentation of BEA-1

The cipher BEA-1 is directly inspired by Rijndael [7], the block cipher designed by Joan Daemen and Vincent Rijmen, now known as the AES. Our algorithm encrypts 80-bit plaintext blocks using a 120-bit cipher key. Unlike the AES, the internal state is not seen as a matrix of bytes but as an array of 10-bit bundles. Therefore, the message and key spaces are respectively ${({\mathbb{F}}_2^{10})}^8$ and ${({\mathbb{F}}_2^{10})}^{12}$.

1.1. Specification of the encryption process

The encryption consists in applying 11 times a simple keyed operation called round function to the data block. A different 80-bit round key is used for each iteration of the round function. Since the last round is slightly different and uses two round keys, the encryption requires twelve 80-bit round keys. These round keys are derived from the 120-bit cipher key using a key schedule.

Like any other substitution-permutation network, the round function is made up of three stages: a key addition, a substitution layer and a diffusion layer.

• The key addition is just a bitwise “exclusive or” (XOR) between the data block and the round key.

• The substitution layer consists in the parallel evaluation of four different 10-bit S-boxes and is the only part of the cipher that is not affine. These S-boxes are referred to as S₀, S₁, S₂, S₃ and are defined in Figures 5A, 7A, 9A and 11A given in Appendix. They should not be confused with the secret S-boxes S₀, S₁, S₂ and S₃, only used in the design and the cryptanalysis of BEA-1.

• Following the design principles of the AES, the diffusion layer comes in two parts: the ShiftRows and the MixColumns operations. The first part is a bundle permutation. The second evaluates in parallel the linear transformation $M:({\mathbb{F}}_2^{10}{)}^4\to {({\mathbb{F}}_2^{10})}^4$ processing four 10-bit bundles. Because of its linearity, M is only defined over the standard basis of ${({\mathbb{F}}_2^{10})}^4$ in Figure 3A in Appendix. For convenience, its inverse M⁻¹ is also in the same figure.

The pseudo-codes for the key schedule and the encryption algorithm are both given in Figure 4.1. To provide an overview of their structures, the first step of the key schedule and the round function is illustrated in Figure 4.2. This representation also emphasizes the similarities between our algorithm and the AES.

Figure 4.1.

The key schedule and the encryption function of BEA-1.

Figure 4.2.

Diagrammatic representations of the key schedule and the round function of BEA-1.

Remark 4.1. The decryption is straightforward from the encryption since all the primitives are bijective. Thus, to decrypt, we just have to apply the inverse operations in the reverse order. It should be stressed that the key addition and the ShiftRows are involutions; therefore the same operations are used in the decryption process. Finally, note that the inverse S-boxes are not given here but can be computed by using the equation $S_i^{-1}(S(x))=x$ holding for each x in ${\mathbb{F}}_2^{10}$.

1.2. Differential and linear cryptanalysis

In [7], Daemen and Rijmen introduced the differential and the linear branch numbers of a linear transformation. With an exhaustive search, it can be checked that the differential and linear branch numbers of M are both equal to 5, which is the maximum. This implies that any 2-round trail has at least 5 active S-boxes. Thus, a 10-round trail involves at least 25 active S-boxes.

Note that all the S-boxes are (at most) differentially 40-uniform and linearly 128-uniform. Therefore, the probability of any 10-round differential trail is upper bounded by ${(\frac{40}{1024})}^{25}\approx 2^{-116.9}$ and the absolute bias of a 10-round linear trail is upper bounded by ${(\frac{128}{512})}^{25}{=2}^{-50}$. Consequently, a differential cryptanalysis of the 10-round version of our cipher would require at least 2¹¹⁷ chosen plaintext/ciphertext pairs and a linear cryptanalysis would require 2¹⁰⁰ known plaintext/ciphertext pairs.

Even if this is a rough approximation since it does not take into account the inter-column diffusion provided by the ShiftRows operation, it suffices to prove the cipher’s practical resistance against classical differential and linear cryptanalysis. In fact, there are only 2⁸⁰ different plaintext/ciphertext pairs for a fixed cipher key.

2. Design of the backdoor

The presentation of secret structure of BEA-1 comes in two parts. First, Section 2.1 explains the nature of this backdoor and provides all the results needed to address the cryptanalysis. Then, the design of BEA-1’s primitives is given in Sections 2.2 and 2.3. The reader who just wants to understand how the backdoor works can skip these two sections. Indeed, they are more technical and are also independent of the remainder of this chapter.

2.1. The linear partitions throughout the encryption

As said in introduction, the backdoor of BEA-1 relies on the theoretical framework developed in Chapters 2 and 3. Thus, it should not be surprising that linear partitions must play a key role in it. For this purpose, let us introduce the following 5-dimensional subspaces of ${\mathbb{F}}_2^{10}$

$\begin{array}{ll}{V}_0=\text{span}(\mathtt{2}\mathtt{6}\mathtt{6},\mathtt{3}\mathtt{4}\mathtt{3},\mathtt{3}\mathtt{\text{E}}\mathtt{\text{D}},\mathtt{3}\mathtt{5}\mathtt{4},\mathtt{1}\mathtt{7}\mathtt{\text{F}}),\hfill & W_0=\text{span}(\mathtt{1}\mathtt{6}\mathtt{\text{A}},\mathtt{1}\mathtt{1}\mathtt{\text{B}},\mathtt{3}\mathtt{0}\mathtt{6},\mathtt{0}\mathtt{5}\mathtt{\text{E}},\mathtt{0}\mathtt{\text{B}}\mathtt{8}),\hfill \\ V_1=\text{span}(\mathtt{3}\mathtt{9}\mathtt{8},\mathtt{2}\mathtt{2}\mathtt{9},\mathtt{3}\mathtt{4}\mathtt{\text{C}},\mathtt{2}\mathtt{5}\mathtt{1},\mathtt{3}\mathtt{7}\mathtt{\text{B}}),\hfill & W_1=\text{span}(\mathtt{0}\mathtt{4}\mathtt{\text{B}},\mathtt{3}\mathtt{\text{B}}\mathtt{7},\mathtt{0}\mathtt{\text{D}}\mathtt{5},\mathtt{0}\mathtt{2}\mathtt{7},\mathtt{2}\mathtt{\text{C}}\mathtt{8}),\hfill \\ V_2=\text{span}(\mathtt{0}\text{B}\mathtt{\text{A}},\mathtt{1}\mathtt{5}\mathtt{5},\mathtt{3}\mathtt{0}\mathtt{7},\mathtt{3}\mathtt{7}\mathtt{\text{E}},\mathtt{3}\mathtt{1}\mathtt{8}),\hfill & W_2=\text{span}(\mathtt{1}\mathtt{\text{A}}\mathtt{9},\mathtt{0}\mathtt{9}\mathtt{5},\mathtt{1}\mathtt{0}\mathtt{7},\mathtt{3}\mathtt{6}\mathtt{\text{F}},\mathtt{2}\mathtt{\text{A}}\mathtt{3}),\hfill \\ V_3=\text{span}(\mathtt{1}\mathtt{\text{D}}\mathtt{1},\mathtt{2}\mathtt{1}\mathtt{\text{E}},\mathtt{1}\mathtt{3}\mathtt{4},\mathtt{0}\mathtt{\text{D}}\mathtt{\text{C}},\mathtt{1}\mathtt{5}\mathtt{\text{A}}),\hfill & W_3=\text{span}(\mathtt{0}\mathtt{\text{F}}\mathtt{0},\mathtt{2}\mathtt{\text{F}}\mathtt{\text{E}},\mathtt{1}\mathtt{9}\mathtt{1},\mathtt{3}\mathtt{3}\mathtt{2},\mathtt{1}\mathtt{\text{A}}\mathtt{6}).\hfill \end{array}$E78

Then, define the 40-dimensional subspaces $V={\displaystyle {\prod }_{i=0}^7}{V}_{i\text{mod}4}$ and $W={\displaystyle {\prod }_{i=0}^7}{W}_{i\text{mod}4}$ of message space ${({\mathbb{F}}_2^{10})}^8$. Therefore, the linear partitions $\mathcal{L}(V)$ and $\mathcal{L}(W)$ are both made up with 2⁴⁰ cosets, each containing 2⁴⁰ elements.

The S-boxes S₀, S₁, S₂ and S₃ given in the specification of BEA-1 are actually derived from the secret S-boxes S₀, S₁, S₂ and S₃ given in Figures 4A, 6A, 8A and 10A in Appendix. The relation between the secret S-boxes S_i and their modified versions S_i will be detailed later in Section 2.2. In the first place, let us state the following theorem relating BEA-1 to the theory of partition-based backdoor ciphers.

Theorem 4.2. Consider the encryption function of BEA-1 where the modified S-boxes S₀, S₁, S₂, and S₃ are replaced with their secret counterparts S₀, S₁, S₂, and S₃. Then, the round function preserves the linear partition $\mathcal{L}(V)$ of ${({\mathbb{F}}_2^{10})}^8$ and the last round maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$, no matter the round keys used. As a consequence, the full encryption maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$.

More precisely, Figure 4.3 depicts the evolution of the linear partition $\mathcal{L}(V)$ throughout each primitive of the (secret) encryption process. For instance, we can see that the S-box S_i maps the linear partition $\mathcal{L}(V_i)$ to $\mathcal{L}(W_i)$, and hence, the substitution layer maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Similarly, the diffusion layer comes back to the original partition, since it maps $\mathcal{L}(W)$ to $\mathcal{L}(V)$.

Figure 4.3.

The linear partitions throughout the encryption.

Remark 4.3. Theorem 4.2, as well as Theorem 18 stated hereinafter, will be proven in Sections 2.2 and 2.3. Indeed, they establish the main properties of the backdoor and are hence closely related to the design of the cipher’s primitives.

Thanks to Theorem 4.2, we can now explain our choices for the V_i and W_i. Each of these subspaces of ${\mathbb{F}}_2^{10}$ is a five-dimensional linear code whose minimal distance is equal to 4. This property ensures that the Hamming distance of any two different elements lying in the same coset is at least equal to 4. The subspaces V nd W of ${\mathbb{F}}_2^{80}$ inherit this property. Thus, if p is a plaintext, then any other plaintext p′ lying in the same coset of V differs from p in at least four bits. Considering the secret encryption function, Theorem 4.2 establishes that their ciphertexts c and c′ belong to the same coset of W. Thus, c and c′ have at least four different bits. As it will become clear in the next two sections, the subspaces V_i and W_i could have been freely chosen among the five-dimensional subspaces of ${\mathbb{F}}_2^{10}$. We surmised that using linear codes with high minimal distance should reduce the likelihood of observing the backdoor by accident, hence our choice for the V_i and W_i.

Having explained the main property of the secret encryption function, now is the time to introduce the following theorem establishing a link between the secret cipher and BEA-1.

Theorem 4.4. Let F and E denote the round function and the encryption function of BEA-1 using the secret S-boxes. Let $p=p^{[0]}$ be any plaintext. Define the following elements with respect to the round keys $k^{[0]},\dots ,k^{[10]}$:

$\begin{array}{cccc}{p}^{[i+1]}=F_{k^{[i]}}(p^{[i]})& \text{and}& p^{[i+1]}=F_{k^{[i]}}(p^{[i]})& \text{for}0\le i<11.\end{array}$E79

Assume that the round keys k^[0],…,k^[10] are independent and uniformly distributed. The probability that all the equalities p^[i] = p^[i] hold for each 1 ≤ i ≤ 11 is given by

${({\left(\frac{944}{1024}\right)}^6\times {\left(\frac{925}{1024}\right)}^2)}^{11}\approx 2^{-11}.$E80

Therefore, the probability that p is encrypted equally with E and E can be approximated by 2⁻¹¹.

Remark 4.5. The fact that the MixColumns operation is replaced with a key addition in the last round of BEA-1 does not matter in Theorem 4.4. For the sake of simplicity, we then ignore this detail. This explains why the last round key k^[11] does not appear in the statement of this result.

Needless to say, the hypothesis that the round keys are independent and uniformly distributed is mathematically wrong in any practical cryptanalysis. Indeed, the twelve 80-bit round keys are all extracted from one 120-bit cipher key. However, the cipher key needs to have (at least) 960 bits to provide independence and uniform distribution to its round keys. Such a cipher key must be related to the concept of long-key cipher defined in [30]. Nonetheless, if the cipher key is uniformly distributed, the same applies for each round key.

In our cryptanalysis of BEA-1, we are given plaintexts with their ciphertexts encrypted under a fixed cipher key. Even if we forget about the independence of the round keys, each plaintext must be encrypted with a random cipher key to make use of Theorem 4.4.

Fortunately, our experiments suggest that the proportion of the plaintexts encrypted equally with E_K and E_K is approximatively 2⁻¹¹, even when the round keys are derived from a fixed cipher key K. To put it another way, if $\mathcal{P}$ is a subset of the plaintext space ${({\mathbb{F}}_2^{10})}^8$, it seems reasonable to assume that

$\#\mathrm{\{}p\in \mathcal{P}|E_K(p)=E_K(p)\mathrm{\}}\approx \frac{\#\mathcal{P}}{2^{11}}.$E4.1

Now, suppose that $\mathcal{P}$ is included in a coset of V denoted by x + V. As the secret encryption function E_K maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$ (see Theorem 4.2), we know that the image of $\mathcal{P}$ under E_K is included in a coset of W. More precisely, Lemma 2.8 establishes that $E_K(\mathcal{P})$ is included in y + W where y = E_K(x). Hence,

$\mathrm{\{}p\in \mathcal{P}|E_K(p)=E_K(p)\mathrm{\}}\subseteq \mathrm{\{}p\in \mathcal{P}|E_K(p)\in (y+W)\mathrm{\}}.$E4.2

Combining (4.1) with (4.2), we conclude that approximately $\#\mathcal{P}\times 2^{-11}$ ciphertexts in $\mathcal{C}=E_k(\mathcal{P})$ belong to y + W. In addition, we have observed that the ciphertexts c = E_K(p) such that $E_K(p)\ne E_K(p)$ are spread over the 2⁴⁰ cosets of W.

The backdoor of BEA-1 is hence the following. First, choose a set $\mathcal{P}$ of 2¹⁶ plaintexts uniformly chosen in one coset x + V and collect their ciphertexts $\mathcal{C}=E_K(\mathcal{P})$ encrypted under an unknown cipher key K. Then search for the most represented coset of W in $\mathcal{C}$ and denote by y one of its representatives. According to our experiments, this coset should have roughly 2^16–11 = 32 elements, and the second most represented coset is unlikely to have more than six elements. As a consequence of the preceding discussion, we know that the coset x + V is mapped to y + W by the secret encryption function E_K. This information can then be used to recover the cipher key K with a low computation cost, as detailed later in Sections 3 and 4.

To conclude this section, observe that no particular property of the key schedule has been used. It can be proven that each round of the key schedule preserves the linear partition $\mathcal{L}({\prod }_{i=0}^{11}{W}_i)$, provided that the S-boxes S_i are replaced with their secret equivalents S_i. This implies that if two cipher keys K and K′ are in the same coset of ${\prod }_{i=0}^{11}{W}_i$, then we can approximate the probability that each pair of round keys k^[i] and k′^[i] are in the same coset of W by ${{(944}^3\cdot 925\cdot 2^{-40})}^7\approx 2^{-3.5}$. However, for this property to be easily exploitable, the round keys ought to stay in the same coset of V instead of W (which can be simply achieved by switching the mappings M and (S₀||S₁||S₂||S₃) in the key schedule). Therefore, if compared with our cryptanalysis, this property appears not to be very useful and was intentionally left as a wrong track.

2.2. The substitution layer

The nature of the hidden property of BEA-1 having been emphasized, this and the following sections detail the design of the cipher’s primitives and prove Theorems 4.2 and 4.4 stated above. As explained in introduction, these two sections are aimed at the reader who wants to understand how BEA-1 was made. For a first read, it is possible to jump directly to Section 3 explaining the basic principle of the cryptanalysis using the backdoor.

Let {0*} and {*0} denote respectively the subspaces ${\mathrm{\{}0}_5\mathrm{\}}\times {\mathbb{F}}_2^5$ and ${\mathbb{F}}_2^5\times {\mathrm{\{}0}_5\mathrm{\}}$ of ${\mathbb{F}}_2^{10}$. It should be noted that {*0} is a complement space of {0*} in ${\mathbb{F}}_2^{10}$. The design of each secret S-box S_i rests on a permutation $S{\text{'}}_i$ of ${\mathbb{F}}_2^{10}$ preserving the linear partition $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$. Following Theorem 3.5, we just need to choose a permutation ρ_i of {*0} and a family ${({\tau }_{i,u})}_{u\in \mathrm{\{}*0\mathrm{\}}}$ of permutations of {0*}. Then, we define $S{\text{'}}_i$ for all x = u + v in ${\mathbb{F}}_2^{10}$ by

$S{\text{'}}_i(x)=S{\text{'}}_i(u+v)={\rho }_i(u)+{\tau }_{i,u}(v),$E83

where u is in {*0} and v in {0*}. The permutations ρ_i and τ_i,u were selected following the method given in Section 3, in order to maximize the resistance of $S{\text{'}}_i$ against both differential and linear cryptanalysis.

Figure 1A in Appendix defines the linear mappings $L_{V_i}$ and $L_{W_i}$ (for 0 ≤ i ≤ 4) over the standard basis of ${\mathbb{F}}_2^{10}$. It is worthwhile to note that these mappings are automorphisms of ${\mathbb{F}}_2^{10}$. Moreover, $L_{V_i}(\mathrm{\{}0*\mathrm{\}})=V_i$ and $L_{W_i}(\mathrm{\{}0*\mathrm{\}})=W_i$. By virtue of Proposition 2.15, we know that $L_{V_i}$ maps $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$ to $\mathcal{L}(V_i)$ and that $L_{W_i}$ maps $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$ to $\mathcal{L}(W_i)$. Last, but not least, define for each 0 ≤ i < 4 the secret S-box S_i by

$S_i=L_{W_i}\circ {S^{\prime }}_i\circ {(L_{V_i})}^{-1}.$E84

These S-boxes are given in Figures 4A, 6A, 8A and 10A in Appendix. Obviously, ${(L_{V_i})}^{-1}$ maps $\mathcal{L}(V_i)$ to $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$, then ${S^{\prime }}_i$ preserves $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$, and $L_{W_i}$ maps $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$ to $\mathcal{L}(W_i)$. This implies the following proposition.

Proposition 4.6. For each 0 ≤ i < 4, the secret S-box S_i maps $\mathcal{L}(V_i)$ to $\mathcal{L}(W_i)$.

Remark 4.7. If the reader is interested in an explicit definition of the permutations ρ_i and the families of permutations ${({\tau }_{i,u})}_{i\in \mathrm{\{}*0\mathrm{\}}}$, they can be recovered in the following way. First, compute ${S^{\prime }}_i=(\mathrm{}{L}_{W_i}{)}^{-1}\circ S_i\circ L_{V_i}$ using the tables of Figures 1A and 4A (or 6A, 8A, 10A). As noted previously, the permutation ${S^{\prime }}_i$ preserves the linear partition $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$. To obtain its decomposition, we just have to follow the proof of Theorem 3.5. Thus, for each u in {*0}, define ρ_i(u) as the unique element of $\mathrm{\{}*0\mathrm{\}}\cup ({S^{\prime }}_i(u)+\mathrm{\{}0*\mathrm{\}})$. It is not hard to see that ρ_i(u) is simply equal to the element of ${\mathbb{F}}_2^{10}$, where the five leftmost bits are exactly the ones of ${S^{\prime }}_i(u)$ and the five remaining bits are all zero. Finally, for each u in {*0}, let τ_i,u be the permutation of {0*} defined by ${\tau }_{i,u}(v)={S^{\prime }}_i(u+v)+{\rho }_i(u)$. Again, τ_i,u(v) is just the 10-bit vector having its five leftmost bits all zero and its five rightmost bits identical to the ones of ${S^{\prime }}_i(u+v)$. Naturally, the permutations ρ_i and τ_i,u can be seen as permutations of ${\mathbb{F}}_2^5$ (instead of {*0} and {0*}) to obtain the more convenient definition

${S^{\prime }}_i(u\parallel v)=({\rho }_i(u)\parallel {\tau }_{i,u}(v)\mathrm{}).$E85

The modified S-boxes S_i given in the specification of BEA-1 are such that S_i(x) = S_i(x) for almost all input x in ${\mathbb{F}}_2^{10}$. For instance, $S_0(x)=S_0(x)$ for all except 80 elements x in ${\mathbb{F}}_2^{10}$. The images of these 80 particular points are emphasized in Figures 4A and 5A. These modifications were chosen so as to improve the differential and linear resistances of S₀ compared to the original secret S-box S₀. More generally, S_i and S_i have 80 different images for i in {0,1,2}. The last-modified S-box S₃ is less close to it secret equivalent since S₃ and S₃ have 99 different images.

Consequently, if x is uniformly distributed over ${\mathbb{F}}_2^{10}$, then the equality S_i(x) = S_i(x) holds with probability q_i where

$\begin{array}{ccc}{q}_0=q_1=q_2=\frac{944}{1024}& \text{and}& q_3=\frac{925}{1024}.\end{array}$E86

This implies that when x is uniformly distributed over ${({\mathbb{F}}_2^{10})}^8$, the images of x under the secret and the modified substitution layers are equal with probability $q=(\mathrm{}{\prod }_{i=0}^3{q}_i{)}^2$.

Let p = p^[0] be a plaintext. In the following, we use the notations of Theorem 4.4. If k^[i] is uniformly distributed, then so is p^[i] + k^[i]. Thus, $p^{[i+1]}=F_{k^{[i]}}(p^{[i]})$ is equal to $p^{[i+1]}=F_{k^{[i]}}(p^{[i]})$ with probability q. Assuming moreover that the round keys are independent implies that the events p^[i] = p^[i] for each 1 ≤ i ≤ 11 are independent. Therefore, the probability that the equalities p^[i] = p^[i] hold for all 1 ≤ i ≤ 11 is given by q¹¹. This discussion proves Theorem 4.4.

2.3. The diffusion layer

Some components used to design the linear transformation M are defined over the finite field ${\mathbb{F}}_{2^5}$. In order to have an explicit construction of this field, we consider the irreducible polynomial X⁵ + X² + 1 over ${\mathbb{F}}_2$ and define ${\mathbb{F}}_{2^5}$ as the quotient ring ${\mathbb{F}}_2[X]/(X^5+X^2+1)$. Let α denote the equivalence class of X in ${\mathbb{F}}_{2^5}$. By construction, the equality ${\alpha }^5+{\alpha }^2+1=0$ holds, or equivalently, ${\alpha }^5={\alpha }^2+1$. Each element of ${\mathbb{F}}_{2^5}$ can hence be uniquely written as ${\displaystyle {\sum }_{i=0}^4}{x}_i{\alpha }^i$ where (x₄,…, x₀) belongs to ${\mathbb{F}}_2^5$. More precisely, the family ${({\alpha }^i)}_{i<5}$ is a basis of ${\mathbb{F}}_{2^5}$ seen as a 5-dimensional vector space over ${\mathbb{F}}_2$. The field ${\mathbb{F}}_{2^5}$ will then be identified with ${({\mathbb{F}}_2)}^5$ via the isomorphism from ${\mathbb{F}}_2^5$ to ${\mathbb{F}}_{2^5}$ mapping (x₄,…, x₀) to ${\displaystyle {\sum }_{i=0}^4}{x}_i{\alpha }^i$. For instance, the element α² + α + 1 in ${\mathbb{F}}_{2^5}$ is identified with 07 in ${\mathbb{F}}_2^5$. Now define the 4 × 4 matrices M_U and M_V over ${\mathbb{F}}_{2^5}$ by

$\begin{array}{ccc}\left(\begin{array}{llll}a\hfill & b\hfill & c\hfill & d\hfill \\ b\hfill & a\hfill & d\hfill & c\hfill \\ c\hfill & d\hfill & a\hfill & b\hfill \\ d\hfill & c\hfill & b\hfill & a\hfill \end{array}\right)& M_U:\{\begin{array}{l}a={\alpha }^4+{\alpha }^2,\hfill \\ b={\alpha }^4+{\alpha }^3+{\alpha }^2+\alpha +1,\hfill \\ c={\alpha }^3+{\alpha }^2,\hfill \\ d={\alpha }^4+{\alpha }^2+1,\hfill \end{array}& M_V:\{\begin{array}{l}a={\alpha }^3+{\alpha }^2+1,\hfill \\ b={\alpha }^4+{\alpha }^3+{\alpha }^2+\alpha ,\hfill \\ c={\alpha }^4+{\alpha }^2+\alpha \hfill \\ d={\alpha }^3.\hfill \end{array}\end{array}$E87

It can be verified that these matrices are MDS. In other words, the [8, 4]-linear code having $G=[{\text{Id}}_4,M_U]$ as generator matrix has minimal distance equals to 5, which is the maximum achievable.

Each of these matrices naturally induces an automorphism of ${({\mathbb{F}}_{2^5})}^4$ and hence of ${({\mathbb{F}}_2^{10})}^4$. For instance, M_U maps the element $x=(\mathrm{}{x}_0,x_1,x_2,x_3)$ to x × M_U. Observe that we chose to see elements of ${({\mathbb{F}}_2^{10})}^4$ as row vectors to keep the common notations of linear codes.

Example 4.8. To illustrate these notations, let us compute the image of the element $x=(\mathtt{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})$ of ${({\mathbb{F}}_2^{10})}^4$ under the automorphism induced by M_U. First, x is identified with the element (0, α, 0, 0) of ${({\mathbb{F}}_{2^5})}^4$. Then,

$\begin{array}{c}(\mathrm{0,}\alpha \mathrm{,0,0})\times M_U=(\alpha ({\alpha }^4+{\alpha }^3+{\alpha }^2+\alpha +1),\alpha ({\alpha }^4+{\alpha }^2),\alpha ({\alpha }^4+{\alpha }^2+1),\alpha ({\alpha }^3+{\alpha }^2))\\ =\begin{array}{ccc}({\alpha }^5+{\alpha }^4+{\alpha }^3+{\alpha }^2+\alpha ,& {\alpha }^5+{\alpha }^3,& \begin{array}{cc}{\alpha }^5+{\alpha }^3+\alpha ,& {\alpha }^4+{\alpha }^3)\end{array}\end{array}\\ =({\alpha }^4+{\alpha }^3+\alpha +1,{\alpha }^3+{\alpha }^2+1,{\alpha }^3+{\alpha }^2+\alpha +1,{\alpha }^4+{\alpha }^3).\end{array}$E88

Therefore, $(\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})\times M_U=(\mathtt{}\mathtt{1}\mathtt{\text{B}},\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{\text{F}},\mathtt{1}\mathtt{8})$.▴

As was the case for the secret S-boxes S_i, the linear transformation M rests upon the linear transformation M′ defined as follows

$\begin{array}{l}{M}^{\prime }:{({\mathbb{F}}_2^{10})}^4\to {({\mathbb{F}}_2^{10})}^4\hfill \\ {(u_i\parallel v_i)}_{i<4}\mapsto {(\rho {(u)}_i\parallel {\tau }_u{(v)}_i)}_{i<4}\hfill \end{array}$E89

where $\rho (u)=u\times M_U$ and ${\tau }_u(v)=v\times M_V+P_{U\to V}(u)$. The strength of this construction is that M′ inherits the linear and differential branch numbers of M_U and M_V, as stated in the proposition hereunder. But first, we introduce the following example.

Example 4.9. Let us compute the image of $x=(\mathrm{}\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0})$ under M′. As a first step, observe that x can be written as

$x=(\mathrm{}\mathtt{0}\mathtt{0}\parallel \mathtt{0}\mathtt{0},\mathtt{0}\mathtt{3}\parallel \mathtt{1}\mathtt{0},\mathtt{0}\mathtt{0}\parallel \mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\parallel \mathtt{0}\mathtt{0})=(u_i\parallel v_i{)}_{i<4},$E90

where $u=(\mathtt{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{3},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})$ and $v=(\mathrm{}\mathtt{0}\mathtt{0},\mathtt{1}\mathtt{0},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})$. Let $e_9=(\mathtt{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})$ and $e_{10}=(\mathrm{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0})$. Then $u=e_9+e_{10}$, it is indeed its decomposition over the standard basis of ${({\mathbb{F}}_2^5)}^4$. Thus, for any linear mapping L, it holds that $L(u)=L(e_9)+L(e_{10})$. The image of u under ρ can hence be computed by

$\rho (u)=\rho (e_9)+\rho (e_{10})=(\mathtt{1}\mathtt{\text{B}},\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{\text{F}},\mathtt{1}\mathtt{8})+(\mathtt{1}\mathtt{\text{F}},\mathtt{1}\mathtt{4},\mathtt{1}\mathtt{5},\mathtt{0}\mathtt{\text{C}})=(\mathtt{0}\mathtt{4},\mathtt{1}\mathtt{9},\mathtt{1}\mathtt{\text{A}},\mathtt{1}\mathtt{4}).$E91

In the same way,

$\begin{array}{cc}{\tau }_u(v)\hfill & =v\times M_V+P_{U\to V}(e_9)+P_{U\to V}(e_{10})\hfill \\ \hfill & =(\mathtt{}\mathtt{1}\mathtt{6},\mathtt{0}\mathtt{\text{E}},\mathtt{1}\mathtt{4},\mathtt{0}\mathtt{2})+(\mathtt{0}\mathtt{\text{F}},\mathtt{1}\mathtt{1},\mathtt{0}\mathtt{\text{C}},\mathtt{1}\mathtt{6})+(\mathtt{1}\mathtt{1},\mathtt{0}\mathtt{\text{E}},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{\text{A}})=(\mathtt{0}\mathtt{8},\mathtt{1}\mathtt{1},\mathtt{1}\mathtt{\text{A}},\mathtt{1}\mathtt{\text{E}}).\hfill \end{array}$E92

Consequently, $M^{\prime }(x)=(\mathtt{0}\mathtt{4}\parallel \mathtt{0}\mathtt{8},\mathtt{1}\mathtt{9}\parallel \mathtt{1}\mathtt{1},\mathtt{1}\mathtt{\text{A}}\parallel \mathtt{1}\mathtt{\text{A}},\mathtt{1}\mathtt{4}\parallel \mathtt{1}\mathtt{\text{E}})=(\mathtt{0}\mathtt{8}\mathtt{8},\mathtt{3}\mathtt{3}\mathtt{1},\mathtt{3}\mathtt{5}\mathtt{\text{A}},\mathtt{2}\mathtt{9}\mathtt{\text{E}})$.▴

Proposition 4.10. The linear and the differential branch numbers of M′ are both equal to 5. Thus, M′ is a perfect diffusion layer.

Proof. Let $x=(\mathtt{}{u}_i\parallel v_i{)}_{i<\mathtt{4}}$ be a nonzero element of ${({\mathbb{F}}_2^{10})}^4$. In order to prove that the differential branch number of M′ is equal to 5, we need to show that ${\text{w}}_{10}(x)+{\text{w}}_{10}(M^{\prime }(x))$ is greater than or equal to 5. First, assume that $u=(\mathrm{}{u}_i{)}_{i<4}$ is nonzero. Using the fact that M_U is MDS, we obtain the inequality ${\text{w}}_5(u)+{\text{w}}_5(u\times M_U)\ge 5$. Next,

$\begin{array}{l}5\le {\text{w}}_5(u)+{\text{w}}_5(\rho (u))={\text{w}}_{10}({(u_i\parallel 0)}_{i<4})+{\text{w}}_{10}({(\rho {(u)}_i\parallel 0)}_{i<4})\hfill \\ \le {\text{w}}_{10}({(u_i\parallel v_i)}_{i<4})+{\text{w}}_{10}((\rho {({(u)}_i\parallel {\tau }_u{(v)}_i)}_{i<4})={\text{w}}_{10}(x)+{\text{w}}_{10}(M^{\prime }(x)).\hfill \end{array}$E93

Now, suppose that u = 0. It must be the case that v ≠ 0 as x is nonzero by definition. Again, it holds that ${\text{w}}_5(v)+{\text{w}}_5(v\times M_V)\ge 5$ because M_V is also MDS. Then,

$\begin{array}{l}5\le {\text{w}}_5(v)+{\text{w}}_5({\tau }_0(v))={\text{w}}_{10}({(0\parallel v_i)}_{i<4})+{\text{w}}_{10}({(0\parallel {\tau }_0{(v)}_i)}_{i<4})\hfill \\ ={\text{w}}_{10}(x)+{\text{w}}_{10}(M^{\prime }(x)).\hfill \end{array}$E94

We have proven that ${\text{w}}_{10}(x)+{\text{w}}_{10}(M^{\prime }(x))\ge 5$ for any nonzero element x of ${({\mathbb{F}}_2^{10})}^4$. Consequently, the differential branch number of M′ is greater than or equal to 5. The equality ${\mathcal{B}}_{\text{D}}(M^{\prime })=5$ follows as 5 is the maximum achievable. Similarly, it can be proven that M′ has also the maximum linear branch number. It follows that M′ is a perfect diffusion layer and the result is proven. ▪

Recall that the notation {0*} denotes the subspace ${\mathrm{\{}0}_5\mathrm{\}}\times {\mathbb{F}}_2^5$ and that the linear mappings $L_{V_i}$ and $L_{W_i}$ (see Figure 1A) map respectively $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$ to $\mathcal{L}(V_i)$ and $\mathcal{L}(\mathrm{\{}0*\mathrm{\}})$ to $\mathcal{L}(W_i)$. It is then easily seen that M′ maps {0*}⁴ to itself. Thus, M′ preserves the partition $\mathcal{L}{(\mathrm{\{}0*\mathrm{\}}}^4)$ by Proposition 2.15. Finally, define

$M=(\mathrm{}{L}_{V_0}\parallel L_{V_1}\parallel L_{V_2}\parallel L_{V_3})\circ M^{\prime }\circ {(L_{W_0}\parallel L_{W_1}\parallel L_{W_2}\parallel L_{W_3})}^{-1}.$E95

From its definition, it is straightforward to check that M maps the linear partition $\mathcal{L}({\prod }_{i=0}^3{W}_i)$ to $\mathcal{L}({\prod }_{i=0}^3{V}_i)$.

Example 4.11. We are going to compute $M(\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{8}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0})$. First, we have that

$\begin{array}{l}(L_{W_0}\parallel L_{W_1}\parallel L_{W_2}\parallel L_{W_3}{)}^{-1}(\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{8}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0})\\ =(\mathrm{}{L}_{W_0}^{-1}(\mathtt{0}\mathtt{0}\mathtt{0}),L_{W_1}^{-1}(\mathtt{0}\mathtt{8}\mathtt{0}),L_{W_2}^{-1}(\mathtt{0}\mathtt{0}\mathtt{0}),L_{W_3}^{-1}(\mathtt{0}\mathtt{0}\mathtt{0}))=(\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0}).\end{array}$E96

Then, the image of $(\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{7}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0})$ under M′ is $(\mathtt{0}\mathtt{8}\mathtt{8},\mathtt{3}\mathtt{3}\mathtt{1},\mathtt{3}\mathtt{5}\mathtt{\text{A}},\mathtt{2}\mathtt{9}\mathtt{\text{E}})$, as already established in Example 4.9. Finally,

$\begin{array}{c}M(\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{8}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{0}\mathtt{0})=(L_{V_0}\parallel L_{V_1}\parallel L_{V_2}\parallel L_{V_3})(\mathtt{0}\mathtt{8}\mathtt{8},\mathtt{3}\mathtt{3}\mathtt{1},\mathtt{3}\mathtt{5}\mathtt{\text{A}},\mathtt{2}\mathtt{9}\mathtt{\text{E}})\\ =(\mathtt{}\mathtt{1}\mathtt{5}\mathtt{\text{E}},\mathtt{0}\mathtt{\text{B}}\mathtt{\text{F}},\mathtt{1}\mathtt{\text{E}}\mathtt{2},\mathtt{0}\mathtt{4}\mathtt{\text{F}}).\end{array}$E97

Indeed, $L_{V_0}(\mathtt{0}\mathtt{8}\mathtt{8})=L_{V_0}(\mathtt{0}\mathtt{8}\mathtt{0})+L_{V_0}(\mathtt{0}\mathtt{0}\mathtt{8})=\mathtt{2}\mathtt{1}\mathtt{\text{D}}+\mathtt{3}\mathtt{4}\mathtt{3}=\mathtt{1}\mathtt{5}\mathtt{\text{E}}$. The three other bundles are computed in the same manner.▴

Because each mapping $L_{V_i}$ or $L_{W_i}$ operates on different bundles and is invertible, it is clear that the linear and differential branch numbers of M are the same as M′. This discussion completes the proof of the following corollary.

Corollary 4.12. The linear mapping M is a perfect diffusion layer, which maps $\mathcal{L}({\prod }_{i=0}^3{W}_i)$ to $\mathcal{L}({\prod }_{i=0}^3{V}_i)$.

In conclusion, Proposition 2.13 ensures that any key addition preserves all the linear partitions, and hence it preserves $\mathcal{L}(V)$. Next, it has been proven in Section 2.2 that every secret S-box S_i maps $\mathcal{L}(V_i)$ to $\mathcal{L}(W_i)$. Thus, the secret substitution layer maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. It is clear that the ShiftRows operation is linear and maps W to itself. According to Proposition 2.15, this mapping preserves $\mathcal{L}(W)$. Finally, the MixColumn operation maps $\mathcal{L}(W)$ to $\mathcal{L}(V)$ by Corollary 4.12. This discussion is summarized in Figure 4.3 and proves Theorem 4.2 previously given in Section 2.1.

3. Main idea of the cryptanalysis

As we have seen in Section 2.1, the cipher BEA-1 does not map a linear partition to another one but behaves as though it did for a nonnegligible fraction of the message space. This nontrivial property can be used to recover the cipher key in an operational cryptanalysis. But before considering the full cipher, we give the main idea of this attack.

3.1. A detailed example

To explain how to take advantage of this backdoor, we introduce a toy example. First, let us mention that all the notations of this section are independent of the remainder of this chapter. The message space of this toy cipher is simply ${\mathbb{F}}_2^6$. Then, consider the subspaces V and W of ${\mathbb{F}}_2^6$ defined by

$\begin{array}{c}V=\text{span}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{1}\mathtt{0},\mathtt{2}\mathtt{0})=\mathrm{\{}(x_3,x_2\mathrm{,0,0,}{x}_1,x_0)|x\in {\mathbb{F}}_2^4\mathrm{\}},\\ W=\text{span}(\mathtt{0}\mathtt{1},\mathtt{0}\mathtt{2},\mathtt{0}\mathtt{4},\mathtt{1}\mathtt{0})=\mathrm{\{}(\mathrm{0,}{x}_3\mathrm{,0,}{x}_2,x_1,x_0)|x\in {\mathbb{F}}_2^4\mathrm{\}}.\end{array}$E98

Thus, $\mathcal{L}(V)=\mathrm{\{}x+V|x\in \mathrm{\{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{4},\mathtt{0}\mathtt{8},\mathtt{0}\mathtt{\text{C}}\mathrm{\}}\mathrm{\}}$ and $\mathcal{L}(W)=\mathrm{\{}y+W|y\in \mathrm{\{}\mathtt{0}\mathtt{0},\mathtt{0}\mathtt{8},\mathtt{2}\mathtt{0},\mathtt{2}\mathtt{8}\mathrm{\}}\mathrm{\}}$.

Let S be the permutation of ${\mathbb{F}}_2^6$ given in Figure 4.4. We defined another permutation S of ${\mathbb{F}}_2^6$ satisfying S(x) = S(x) for any input x in ${\mathbb{F}}_2^6$ except 00, 01, 04, 05, 08, 09, 0C and 0D. The images of these eight specific points under S are also given in Figure 4.4. By analogy with Section 2, the permutation S represents the secret S-box used to design the trapdoor whereas S represents the modified S-box given in the specification of the algorithm. Lastly, define the following keyed mappings

$\begin{array}{ll}{F}_k:{\mathbb{F}}_2^6\to {\mathbb{F}}_2^6\hfill & F_k:{\mathbb{F}}_2^6\to {\mathbb{F}}_2^6\hfill \\ x\mapsto S(x)+k,\hfill & x\mapsto S(x)+k,\hfill \end{array}$E99

Figure 4.4.

The theoretical and the modified S-boxes.

representing respectively the secret and the modified round functions. Naturally, the key k can be any element of ${\mathbb{F}}_2^6$.

It can be easily verified that the secret S-box S maps $\mathcal{L}(V)$ to $\mathcal{L}(W)$. In fact, we have that

$\begin{array}{ll}S(\mathtt{0}\mathtt{0}+V)=\mathtt{0}\mathtt{8}+W,\hfill & S(\mathtt{0}\mathtt{8}+V)=\mathtt{0}\mathtt{0}+W,\hfill \\ S(\mathtt{0}\mathtt{4}+V)=\mathtt{2}\mathtt{8}+W,\hfill & S(\mathtt{0}\mathtt{C}+V)=\mathtt{2}\mathtt{0}+W.\hfill \end{array}$E100

In contrast with the secret permutation S, the modified S-box S does not map $\mathcal{L}(V)$ to $\mathcal{L}(W)$. However, the equality S(x) = S(x) holds with probability ${}^{56}{/}_{\text{}64}$ assuming that x is uniformly distributed over ${\mathbb{F}}_2^6$. This can be stated equivalently as

$\#\mathrm{\{}x\in {\mathbb{F}}_2^6|S(x)=S(x{)\mathrm{\}}=2}^6-8=56.$E101

It should also be noted that this statement remains valid when considering their inverse mappings, that is $\#\mathrm{\{}y\in {\mathbb{F}}_2^6|S^{-1}(y)=S^{-1}(y)\mathrm{\}}=56$. Indeed, if x is an element of ${\mathbb{F}}_2^6$ such that S(x) = S(x), then y = S(x) satisfies the equality S⁻¹(x) = S⁻¹(y). As a consequence,

$\#\mathrm{\{}x\in {\mathbb{F}}_2^6|S(x)=S(x)\mathrm{\}}\le \#\mathrm{\{}y\in {\mathbb{F}}_2^6|S^{-1}(y)=S^{-1}(y)\mathrm{\}}.$E102

The converse inequality can be proven in the same way, establishing the equality.

Now, consider the subset $\mathcal{P}$ of ${\mathbb{F}}_2^6$ defined hereinafter. We assume that the round key is k = 37. The image of $\mathcal{P}$ under S and its encryption with F₃₇ are given below.

It should be stressed that the coset 04 + V is significantly more represented in $\mathcal{P}$ than any other coset of V. Since $F_{\mathtt{3}\mathtt{7}}(\mathcal{P})$ maps the linear partition $\mathcal{L}(V)$ to $\mathcal{L}(W)$, the messages belonging to the same coset of V are all mapped to the same coset of W. Therefore, the most represented coset of W in $F_{\mathtt{3}\mathtt{7}}(\mathcal{P})$ has also ten elements.

As we have seen above, the modified round function F₃₇ does not map $\mathcal{L}(V)$ to $\mathcal{L}(W)$. Figure 4.5 displays the differences between the encryption of $\mathcal{P}$ with F₃₇ and its encryption with F₃₇ by highlighting the messages x in P such that S(x) ≠ S(x) (that is 04, 05, and 0D) and their images throughout the encryption.

Figure 4.5.

Encryption with F₃₇ and F₃₇.

To explain these differences, let us first consider the set $\mathcal{Q}$ of the ten messages lying in both $\mathcal{P}$ and 04 + V. Knowing that the equality S(x) = S(x) holds with probability ${}^{56}{/}_{\text{}64}$ when x is uniformly distributed, it seems reasonable to assume that only $10{\times }^{56}{/}_{\text{}64}=8.75$ messages of $\mathcal{Q}$ will remain in the same coset when computing their images under S. By comparing with the actual messages in $\mathcal{Q}$, we can see that this is a good approximation since eight messages in $S(\mathcal{Q})$ belong to the same coset of W.

Needless to say, there are also eight messages in $F_{\mathtt{3}\mathtt{7}}(\mathcal{Q})$ lying in the same coset of W because the key addition preserves $\mathcal{L}(W)$.

We focus now to the set $\mathcal{P}$ as a whole. According to the discussion above, we know that the most represented coset of W in $F_{\mathtt{3}\mathtt{7}}(\mathcal{P})$ has at least eight elements. We have seen that the images under S of messages lying in the same coset may not stay together. Nonetheless, the converse can also be true, and messages in different cosets may end up in the same coset. This is exactly what happens with the message 0D, as illustrated in Figure 4.5. Consequently, the most represented coset in $F_{\mathtt{3}\mathtt{7}}(\mathcal{P})$ has actually nine elements.

The fact that the most represented coset may not only lose but occasionally retrieve elements should be seen as a side effect. Its impact remains low when

• one coset has significantly more elements than all other cosets (say at least 5 times more), and

• when the number of messages is lower than the total number of cosets.

We must nevertheless keep this fact in mind to understand why the right key will not necessarily have the best score.

It is now time to explain how to recover the round key using only the set $\mathcal{C}=F_{\mathtt{3}\mathtt{7}}(\mathcal{P})$ of encrypted messages. First, we have to determine the most represented coset in $\mathcal{C}$. In our example, this coset is 08 + W with nine messages, and u = 08 is one of its representatives.

Now, assume that k is the round key used to encrypt $\mathcal{C}$. We need to find the coset of V which is mapped to u + W by the secret round function F_k. According to Lemma 2.8, F_k maps t + V to F_k(t) + W. A representative of this coset of V is then t = S⁻¹(u + k). Finally, the score of the guessed key k is the number of messages $F_k^{-1}(c)=S^{-1}(c+k)$ that belong to the theoretical coset t + V, that is to say

$\text{score}(k)=\#\mathrm{\{}c\in C|S^{-1}(c+k)\in (t+V)\mathrm{\}}.$E103

Figure 4.6 illustrates the scoring process applied to the right key (37) and to a wrong key (07). We naturally recover the set $\mathcal{P}$ and the coset $t+V=\mathtt{3}\mathtt{4}+V=\mathtt{0}\mathtt{4}+V$ when using the right key. Thus, the score of k = 37 is equal to 10. In the same way, the score of k = 07 is the number of decrypted messages in the coset $t+V=\mathtt{3}\mathtt{2}+V=\mathtt{0}\mathtt{0}+V$, so $\text{score}(\mathtt{0}\mathtt{7})=8$.

Figure 4.6.

Decryption with the right key and with a wrong key.

Let us now explain why a wrong key tends to have a lower score than the right key. First, the addition of the wrong key randomizes the cosets and the messages within. Recall that when the input x is uniformly distributed, the equality S⁻¹(x) = S⁻¹(x) holds with probability ${}^{56}{/}_{\text{}64}$. The most represented coset after the addition of the wrong key should then lose some elements by applying S⁻¹. Thus, the score of any wrong key should be lower than or equal to 8.

It goes without saying that the previous discussion gives just the main idea of the cryptanalysis. For some wrong keys, the side effects are significant, and their scores can even be higher than the score of the right key, as shown in Figure 4.7. Indeed, the key 37 is one the four best keys but is not the one that has the highest score (0B). For this reason, we will not only return the best key but also the NbCand candidate keys having the highest scores when running this cryptanalysis.

Figure 4.7.

The scores for each key.

3.2. Formalization of the attack

The aim of this section is to formalize and to generalize the cryptanalysis introduced previously in Section 3.1. As we have just seen, this attack really begins in Figure 4.6. The very first data needed is the set $\mathcal{C}$ containing the encrypted messages under the unknown key, given by

$\mathcal{C}=\mathrm{\{}\mathtt{0}\mathtt{4},\mathtt{0}\mathtt{5},\mathtt{0}\mathtt{6},\mathtt{0}\mathtt{\text{D}},\mathtt{0}\mathtt{\text{F}},\mathtt{1}\mathtt{5},\mathtt{1}\mathtt{6},\mathtt{1}\mathtt{7},\mathtt{1}\mathtt{8},\mathtt{2}\mathtt{2},\mathtt{2}\mathtt{7},\mathtt{3}\mathtt{4},\mathtt{3}\mathtt{5},\mathtt{3}\mathtt{6},\mathtt{3}\mathtt{\text{A}}\mathrm{\}}.$E104

Naturally, $\mathcal{C}$ is included in the set $\mathcal{c}={\mathbb{F}}_2^6$ of all possible ciphertexts. Similarly, the set of all possible round keys is denoted by $\mathcal{k}={\mathbb{F}}_2^6$. Next, define the keyed mapping

$\begin{array}{l}G:\mathcal{k}\times \mathcal{c}\to {\mathbb{F}}_2^6\\ (k,c)\mapsto S^{-1}(c+k).\end{array}$E105

Each mapping $G_k:c\mapsto G(k,c)$ is the inverse of the round function F_k. The secret counterpart of G is $G:(k,c)\mapsto S^{-1}(c+k)$. Observe that for each round key k, the mapping G_k maps $\mathcal{L}(W)$ to $\mathcal{L}(V)$. It is also necessary to know the most represented coset u + W in $\mathcal{C}$. Using these notations, the cryptanalysis is formalized in Algorithm 3. Finally, to include potential information on the round keys, this attack processes only a subset $\mathcal{K}$ of $\mathcal{k}$.

More generally, the parameters can be outlined as follows.

• The sets of all possible keys and ciphertexts are referred to as $\mathcal{k}$ and $\mathcal{c}$.

• The keyed mapping $G:\mathcal{k}\times \mathcal{c}\to E$ typically undoes (or partially undoes) one or two rounds of the encryption process.

• Its secret counterpart is denoted by $G:\mathcal{k}\times \mathcal{c}\to E$. It is assumed that G_k maps a linear partition $\mathcal{L}(W)$ to another partition $\mathcal{L}(V)$ no matter the key k used.

• The set of the given ciphertexts is denoted by $\mathcal{C}$. The set of the keys that must be scored by this attack is denoted by $\mathcal{K}$.

• It is assumed that there is a coset of W containing significantly more ciphertexts than any other coset. The element u of $\mathcal{c}$ is a representative of this coset.

• Finally, NbCand is the number of candidate keys to return.

Remark 4.13. Taking a closer look at Algorithm 3, we can see that the structure Cand requires an efficient way to remove the lowest scored key. In our implementation, Cand is a sorted array of couples (s, L) where L is a list containing the keys having the score s. Since there are very few different scores, the sorted insertion in Cand is (almost) in constant time. Removing the lowest scored key is also in constant time. Thus, the time complexity of this cryptanalysis is $O(\#\mathcal{K}\times \#\mathcal{C})$.

4. Cryptanalysis of BEA-1 using the backdoor

The algorithm SelectKeys (see Algorithm 3) detailed into the previous section enables recovery of information on the last round key, using the fact that the round function acts as a function mapping a linear partition to another one with high probability. In this section, we explain how this algorithm can be used to recover the full 120-bit cipher key in just a few seconds on a laptop computer.

This cryptanalysis requires N = 2¹⁶ chosen plaintexts and their corresponding ciphertexts encrypted under one unknown cipher key K. As BEA-1 operates on 80-bit blocks, this amounts to 2 × 640 KiB of data. The plaintexts only need to be uniformly chosen in one coset of V, and there is no requirement on the cipher key.

Our cryptanalysis is naturally divided in five distinct parts. First, we give a brief overview of each part. By hypothesis, all the plaintexts are in the same coset of V. As explained in Section 2.1, a coset of W should be more represented among the ciphertexts. The first part is aimed at finding a representative u of this coset. The second part consists in using the algorithm SelectKeys to find 2¹⁵ candidates for the full 80-bit last round key k^[11]. Next, relying on a property of the key schedule, SelectKeys is applied to these 2¹⁵ candidates to find the right last key in a third part. So far, we have recovered 80 bits of the cipher key. Knowing the last round key, it is then possible to undo the last round of each ciphertext. The fourth part is really close to the first one and provides 2¹⁵ candidates for the 40 remaining bits. Finally, deduce the 2¹⁵ candidate cipher keys from k^[11] and the preceding candidates. The last part involves testing these cipher keys on the plaintext/ciphertext pairs available to find the right one.

The presentation of our cryptanalysis is structured as follows. First, we provide the full attack in Algorithm 4. Then, each part of this algorithm is detailed in one dedicated section. It should be noted that we keep the notations of Section 2 (and not those of Section 3) in the remainder of this chapter. This work has been presented at the RusKrypto 2017 conference [31].

4.1. Part 1: finding the right output coset

Let $\mathcal{P}$ denote the set of the 2¹⁶ plaintexts uniformly chosen in one coset of V and let $\mathcal{C}=\mathrm{\{}{E}_K(p)|p\in \mathcal{P}\mathrm{\}}$ denote the set of their ciphertexts. As said previously, we first need to find the most represented coset of W in $\mathcal{C}$. Let U_i be the subspace of ${\mathbb{F}}_2^{10}$ defined by $U_i=L_{W_i}(\mathrm{\{}*0\mathrm{\}})$ for each 0 ≤ i < 3. Since {*0} is a complement space of {0*} and $L_{W_i}$ is an automorphism, we know that U_i is a complement space of $L_{W_i}(\mathrm{\{}0*\mathrm{\}})=W_i$. Define U as the subspace ${\prod }_{i=0}^7{U}_{i\text{mod}4}$ of ${({\mathbb{F}}_2^{10})}^8$. Of course, U is a complement space of W.

Let c be a ciphertext and $u=(\mathrm{}{u}_i{)}_{i<8}$ be in U. Because both U and W are product spaces, it is easily seen that u is the unique representative in U of the coset c + W if, and only if, c_i and u_i are in the same coset of W_imod4 for each i < 8. We deduce the following efficient way to compute the representative in U of the coset c + W. First, precompute the four tables RepW_i such that, for each x in ${\mathbb{F}}_2^{10}$, $\mathtt{\text{Rep}}{\mathtt{\text{W}}}_i[x]$ gives the representative in U_i of x + W_i. These tables are just arrays of 1024 integers. Then, the representative of $c=(\mathrm{}{c}_i{)}_{i<8}$ is just $u=(\mathrm{}\mathtt{\text{Rep}}{\mathtt{\text{W}}}_{i\text{mod}4}[c_i{])}_{i<8}$.

To find the most represented coset of W in $\mathcal{C}$, we first compute the representative in U of each ciphertext as described above. Then, we search for the representative that occurs the most. Any naive algorithm should work since there are only 2¹⁵ representatives.

4.2. Part 2: obtaining candidates for the last round key

This part is intended to find candidates for the last round key k^[11] using the algorithm SelectKeys (see Algorithm 3) to undo the last round of BEA-1. However, if this algorithm is naively applied, then the last round has to be undone for each of the 2¹⁶ ciphertexts and 2⁸⁰ possible values of k^[11], yielding an order of 2⁹⁶ time complexity.

To solve this problem, the 2¹⁵ candidates for k^[11] are obtained bundle by bundle, as illustrated in Figure 4.8. First, we partially decrypt the bundles of index 3 and 7. We begin by these bundles since they both involve the S-box S₃, being the most different from its secret equivalent. Following the notations of SelectKeys, the set containing the ciphertexts is ${\mathcal{C}}_{\mathrm{\left\{}\mathrm{3,7}\mathrm{\right\}}}=\mathrm{\{}(c_3,c_7)|c\in \mathcal{C}\mathrm{\}}$, and the set of the keys is ${\mathcal{K}}_{\mathrm{\left\{}\mathrm{3,7}\mathrm{\right\}}}=\mathrm{\{}(k_3,k_7)|k_3,k_7\in {\mathbb{F}}_2^{10}\mathrm{\}}$. The mapping used to partially decrypt the last round of these ciphertexts is

$\begin{array}{l}{G}_{\mathrm{\left\{}\mathrm{3,7}\mathrm{\right\}}}:({\mathbb{F}}_2^{10}{)}^2\times ({\mathbb{F}}_2^{10}{)}^2\to ({\mathbb{F}}_2^{10}{)}^2\\ ((k_3,k_7),(c_3,c_7)\mathrm{})\mapsto (S_3^{-1}(c_3+k_3),S_3^{-1}(c_7+k_7)\mathrm{}).\end{array}$E106

Figure 4.8.

Cryptanalysis using the backdoor (Part 2).

Its secret equivalent G_{3,7} is obtained by replacing S₃ with S₃. The two remaining inputs of the algorithm are the representative u = (u₃, u₇) of the most represented coset of (W₃)², and the subspace (V₃)² of ${({\mathbb{F}}_2^{10})}^2$. It is worth observing that G_{3,7} maps $\mathcal{L}((W_3{)}^2)$ to $\mathcal{L}((V_3{)}^2)$ as required by the algorithm. Running SelectKeys with these arguments generates a set Cand containing 2¹⁵ candidates for $(k_3{}^{[11]},k_7{}^{[11]})$ instead of 2²⁰.

From now on, each step seeks to add a new bundle to our candidates for the last round key k^[11]. The next bundle to add has index 0. Let E denote the set {0, 3, 7} of the current bundle’s indices. Since we have no information on the value of $k_0{}^{[11]}$, the set of the possible values for ${(k_i{}^{[11]})}_{i\in E}$ is

${\mathcal{K}}_E=\mathrm{\{}(k_i{)}_{i\in E}|k_0\in {\mathbb{F}}_2^{10},(k_3,k_7)\in \mathtt{\text{Cand}}\mathrm{\}}.$E107

Following the idea of the first step, we define ${\mathcal{C}}_E=\mathrm{\{}(c_i{)}_{i\in E}|{(c_i)}_{i<8}\in \mathcal{C}\mathrm{\}}$ and

$\begin{array}{ll}{G}_E\hfill & :{({\mathbb{F}}_2^{10})}^E\times ({\mathbb{F}}_2^{10})E\to ({\mathbb{F}}_2^{10})E\hfill \\ \hfill & ({(k_i)}_{i\in E},{(c_i)}_{i\in E})\mapsto {(}_{S_{i\text{mod}4}^{-1}(c_i+k_i))i\in E}.\hfill \end{array}$E108

Then, define G_E by replacing S_i with S_i and let V_E denote the subspace ${\prod }_{i\in E}{V}_{i\text{mod}4}$ of ${({\mathbb{F}}_2^{10})}^E$. The set Cand obtained by running SelectKeys with these parameters contains 2¹⁵ candidates for $(k_0{}^{[11]},k_3{}^{[11]},k_7{}^{[11]})$.

According to Algorithm 4, the index of the next bundle is 4. Actually, the order of the bundle’s indices was chosen such as to involve the S-boxes S₃, then S₀, S₁ and finally S₂. The current indices are in the set $E=\mathrm{\left\{}\mathrm{0,3,4,7}\mathrm{\right\}}$. Similarly, we define

${\mathcal{K}}_E=\mathrm{\{}(k_i{)}_{i\in E}|k_4\in {\mathbb{F}}_2^{10},(k_0,k_3,k_7)\in \mathtt{\text{Cand}}\mathrm{\}}$E109

to include the information on k^[11] gathered by the previous step. Finally, define ${\mathcal{C}}_E$, G_E, G_E and V_E as above. Again, the algorithm SelectKeys yields 2¹⁵ candidates for ${(k_i{}^{[11]})}_{i\in E}$.

This time, let us take a closer look at the implementation of this step. Because $\#{\mathcal{K}}_E{=2}^{25}$ and $\#{\mathcal{C}}_E{=2}^{16}$, a straightforward implementation of SelectKeys requires 2⁴¹ partial round decryptions, as explained by Remark 4.13. Algorithm 5 provides our implementation of SelectKeys for this step. As we can see, the previous candidates are used to filter the ciphertexts before attacking k₄ by brute force. For each of the 2¹⁵ candidates, initializing the filter requires 2¹⁶ partial decryptions. On average, it remains roughly 2⁶ ciphertexts after the filtering process. The loop over k₄ hence requires 2¹⁶ partial decryptions. Consequently, this implementation performs about 2³² partial decryptions instead of 2⁴¹.

Naturally, the 2¹⁵ candidates for the full round key k^[11] are obtained by repeating this method for the four remaining bundles. We will conclude by observing that the complexity of each step decreases since the filtering process improves as the algorithm progresses.

4.3. Part 3: finding the last round key

So far, we have found 2¹⁵ candidates for the 80-bit key k^[11]. This part intends to recover the right key among these candidates, relying on the key schedule’s structure. Let us consider the last round of the key schedule in order to derive a relation between k^[10] and k^[11]. In Figure 4.2:

• $k^{[9]}=(\mathrm{}{k}_0{}^{[9]},\dots ,k_7{}^{[9]})$ corresponds with $(k_0,\dots ,k_7)$,

• $k^{[10]}=(\mathrm{}{k}_0{}^{[10]},\dots ,k_7{}^{[10]})$ corresponds with $(k_8,\dots ,k_{15})$,

• $k^{[11]}=(\mathrm{}{k}_0{}^{[11]},\dots ,k_7{}^{[11]})$ corresponds with $(k_{16},\dots ,k_{23})$.

It is then easily seen that

$(k_0^{[10]},k_1^{[10]},k_2^{[10]},k_3^{[10]})=(k_0^{[11]},k_1^{[11]},k_2^{[11]},k_3^{[11]})+(k_4^{[11]},k_5^{[11]},k_6^{[11]},k_7^{[11]}).$E110

Thus, the 40 leftmost bits of k^[10] are determined by k^[11]. Using this equality, it is possible to partially decrypt the last two rounds for every candidate for k^[11]. Again, the algorithm SelectKeys is used to distinguish between candidates.

Instead of wasting time understanding the definition of G stated hereinafter, we encourage the reader to compare it with Figure 4.9, which speaks for itself. Let us consider

$\begin{array}{l}{G}^{\prime }:(F_2^{10}{)}^8\times ({\mathbb{F}}_2^{10})\mathrm{\left\{}\mathrm{0,2,5,7}\mathrm{\right\}}\mapsto ({\mathbb{F}}_2^{10})4\\ ((k_i{)}_{i<8},(c_i{)}_{i\in \mathrm{\left\{}\mathrm{0,2,5,7}\mathrm{\right\}}})\mapsto (S_0^{-1}(c_0+k_0)+k_0+k_4,S_1^{-1}(c_5+k_5)+k_1+k_5,\\ S_2^{-1}(c_2+k_2)+k_2+k_6,S_3^{-1}(c_7+k_7)+k_3+k_7).\end{array}$E111

Figure 4.9.

Cryptanalysis using the backdoor (Part 3).

Then, let G be the mapping from ${(F_2^{10})}^8\times {({\mathbb{F}}_2^{10})}^{\mathrm{\left\{}\mathrm{0,2,5,7}\mathrm{\right\}}}$ to ${({\mathbb{F}}_2^{10})}^4$ given by

$G=(\mathrm{}{S}_0\parallel S_1\parallel S_2\parallel S_3{)}^{-1}\circ M^{-1}\circ G^{\prime }.$E112

Define G in the same way as before and let $V^{\prime }={\prod }_{i=0}^3{V}_i$. Finally, run Selectkeys as in line 12 of Algorithm 4. The candidate that has the highest score is then the last round key k^[11].

To explain why Parts 2 and 3 of this cryptanalysis are complementary, let us take a closer look at the 2¹⁵ candidates obtained previously. Most of them are in fact really close to k^[11]; more precisely, they have at most three bundles different from k^[11]. This observation is not surprising because when decrypting the last round, each bundle of the key affects only one bundle of the output. As a direct consequence, close candidates give rise to close one-round decrypted ciphertexts. This explains why the algorithm SelectKeys, as used in Part 2, may assign similar scores to close candidates.

By contrast, the mapping G defined above yields very different outputs when used with close candidate keys. Such a property comes from the high diffusion provided by M⁻¹. Thus, this part is more effective where the previous part has its main weakness. Moreover, the side effects are limited here since we decrypt two rounds instead of one.

4.4. Part 4: obtaining candidates for the remaining bits

The round function of the key schedule being bijective, it is sufficient to know the 120 output bits of the last round to compute the cipher key. Until now, we have recovered the last round key k^[11], accounting for 80 of these 120 bits. The 40 remaining bits are the 40 rightmost bits of k^[10], also denoted by ${(k_i{}^{[10]})}_{4\le i<8}$. This fourth part intends to find 2¹⁵ candidates for these unknown bits.

Since the key k^[11] is now known, it is possible to undo the last round for every ciphertext. The cryptanalysis is then reduced to the attack of the second to last round. However, the method used in Part 2 cannot be directly applied here since the second to last round involves the MDS mapping M. Let x and k be elements of ${({\mathbb{F}}_2^{10})}^4$ and observe that

$M(x)+k=M(x)+M(M^{-1}(k))=M(x+M^{-1}(k))=M(x+k^{\prime })$E113

where $k^{\prime }=M^{-1}(k)$. Thus, the key addition and the mapping M can be switched provided that the key is replaced. According to this observation, define

${(k_{i^{\prime }}{}^{[10]})}_{4\le i<8}=M^{-1}((k_i{}^{[10]}{)}_{4\le i<8}).$E114

Therefore, the last two rounds of BEA-1 can equivalently be represented as in Figure 4.10.

Figure 4.10.

Cryptanalysis using the backdoor (Part 4).

Thanks to this representation, candidates for the key ${({k^{\prime }}_i{}^{[10]})}_{4\le i<8}$ can be obtained using SelectKeys as in Part 2. To this end, we first need to partially undo the last round using k^[11]. Following Figure 4.10, define

$\begin{array}{l}f:({\mathbb{F}}_2^{10}{)}^{\mathrm{\left\{}\mathrm{1,3,4,6}\mathrm{\right\}}}\to ({\mathbb{F}}_2^{10}{)}_4\\ (c_i)i\in \mathrm{\left\{}\mathrm{1,3,4,6}\mathrm{\right\}}\mapsto M^{-1}(S_0^{-1}(c_4+k_4{}^{[11]}),S_1^{-1}(c_1+k_1{}^{[11]}),\\ S_2^{-1}(c_6+k_6{}^{[11]}),S_3^{-1}(c_3+k_3{}^{[11]})\mathrm{}).\end{array}$E115

The set $\mathrm{\{}f((c_i{)}_{i\in \mathrm{\left\{}\mathrm{1,3,4,6}\mathrm{\right\}}})|c\in \mathcal{C}\mathrm{\}}$ of these “new” ciphertexts is denoted by ${\mathcal{C}}^{\prime }$, and the corresponding coset representative is $u^{\prime }=f((u_i{)}_{i\in \mathrm{\left\{}\mathrm{1,3,4,6}\mathrm{\right\}}})$. To be more consistent with Figure 4.10, the bundles of u′ and of the elements of ${\mathcal{C}}^{\prime }$ are indexed from 4 to 7 included. The remainder of the attack is similar to Part 2 as the candidates are obtained bundle by bundle. The first step gets candidates for the bundle’s indices 4 and 7. The second and the third steps add the indices 5 and 6, respectively. If E denotes the set of the current bundle’s indices, then the parameters of SelectKeys are the set ${{\mathcal{C}}^{\prime }}_E=\mathrm{\{}({c^{\prime }}_i{)}_{i\in E}|{({c^{\prime }}_i)}_{4\le i<8}\in {\mathcal{C}}^{\prime }\mathrm{\}}$, the mapping

$\begin{array}{l}{G}_E:({\mathbb{F}}_2^{10}{)}^E\times ({\mathbb{F}}_2^{10})E\to ({\mathbb{F}}_2^{10}{)}^E\\ (({k^{\prime }}_i{)}_{i\in E},({c^{\prime }}_i{)}_{i\in E})\mapsto (S_{i\text{mod}4}^{-1}({c^{\prime }}_i+{k^{\prime }}_i)\mathrm{}{)}_{i\in E,}\end{array}$E116

its equivalent G_E and the subspace $V_E={\displaystyle {\prod }_{i\in E}}{V}_{i\text{mod}4}$ of ${({\mathbb{F}}_2^{10})}^E$. The other details are given in Algorithm 4. At the end of this part, every candidate $k^{\prime }=(\mathrm{}{k^{\prime }}_i{)}_{4\le i<8}$ for ${({k^{\prime }}_i{}^{[10]})}_{4\le i<8}$ gives rise to a candidate $k=M(k^{\prime })$ for ${(k_i{}^{[10]})}_{4\le i<8}$.

4.5. Part 5: deducing the cipher key

Concatenating the candidates for ${(k_i{}^{[10]})}_{4\le i<8}$ with k^[11] yields 2¹⁵ candidates for the output of the key schedule’s last round. To obtain the corresponding candidates for the cipher key, we need to reverse the rounds of the key schedule.

Referring to Figure 4.2, the ith round of the key schedule maps the element (X₀, X₁, X₂) of ${({\mathbb{F}}_2^{40})}^3$ to (Y₀, Y₁, Y₂) according to the following equalities

$\begin{array}{ccc}{Y}_0=X_0+f_i(X_2),& Y_1=Y_0+X_1,& Y_2=Y_1+X_2,\end{array}$E117

where f_i denotes the permutation of ${({\mathbb{F}}_2^{10})}^4$ defined for each X by

$f_i(X{)=(3}^i\text{mod}{2}^{10}\mathrm{,0,0,0})+(S_0\parallel S_1\parallel S_2\parallel S_3)\circ M(X).$E118

Using these notations, it easily seen that

$X_0=Y_0+f_i(Y_1+Y_2),X_1=Y_0+Y_1,X_2=Y_1+Y_2.$E119

These equalities describe how to reverse each round of the key schedule, and thus how to recover the 2¹⁵ candidate cipher keys.

Finally, it just remains to test these candidate cipher keys to complete the cryptanalysis. To be efficient, choose one plaintext/ciphertext pair (p, c) and check whether or not the encryption of p under the candidate K is equal to c. In case of equality, repeat this process for all pairs available to prevent false positive results. Otherwise, the candidate is discarded. Obviously, the right cipher key is the one that passes all tests.

Conclusion

In this book, we have addressed the following issue: “is it possible to design a mathematical backdoor which would rely mostly on suitable partitionning techniques of the plaintext and ciphertext spaces, independently of the round keys?”. We had in mind initially to exploit combinatorial properties of the core primitives.

The overall conclusion we get is that if we want to design such a backdoor, the only solution is to stay in the algebraic domain and no specifically combinatorial tools or primitive are possible. Let us summarize in details the main results.

If we wish to design any encryption system that maps any partition $\mathcal{A}$ of the plaintexts to a partition $\mathcal{B}$ of the ciphertexts, independently of the round keys then

• the round function must map a linear partition to another one, and

• at least one S-box must do the same.

Here, the backdoor is precisely the knowledge of the pair $(\mathcal{A},\mathcal{B})$. This result implies that the partitions considered for the backdoor belong to the algebraic domain and not to the combinatorial one. We are condemned to consider highly structured algebraic objects.

For the candidate S-boxes which make it possible to design such a backdoor, we have performed a detailed study with respect to their linear and differential tables. We have given lower bounds on their linear and differential uniformities and we have explained how to (nearly) achieve them.

The study presented in this book shows that the linear and differential tables of these backdoor S-boxes are highly structured. Thus, we have proved that our backdoor class implies necessarily a high algebraic structure. We conjecture that the reverse may be also true: any algebraic structure can be used to design a backdoor cipher. In terms of backdoor detectability, we also surmise that it is easy to detect and identify our backdoor from the results presented in this book.

As future works, we would primarily address the two following issues. First, what would the results be if we consider dependent round keys? In other words, we would like to consider a key schedule algorithm which therefore would be part of the backdoor.

Second, we want to explore and formalize exhaustively a criterion which would help either to design better hidden backdoors or, on the contrary, to evaluate the presence of a potential backdoor. The first idea of criterion is the following. Let $\mathcal{S}$ denote the set of the S-boxes mapping a linear partition to another linear partition. For any S-box S we define the distance with respect to $\mathcal{S}$ as follows

$\min \mathrm{\{}\#\text{Supp}(\tau )|\tau \in \mathfrak{S}({\mathbb{F}}_2^n),S\circ \tau \in \mathcal{S}\mathrm{\}}.$E120

This represents the minimal number of images under S we have to modify in order to obtain an S-box lying in $\mathcal{S}$. In other words, the aim is to have a distance measure to a backdoor S-box. In Chapter 4, Section 2, we have first considered secret S-boxes mapping linear partitions to another ones. Unfortunately, as mentioned previously, the structure of their linear and differential tables is likely to betray the existence of a backdoor and can be used to find it. This is the reason why, we have then modified the S-boxes. These new S-boxes “behave” similarly to their secret counterparts with high probability. We have published a first-algorithm proposal [32] denoted BEA-1 (Backdoored Encryption Algorithm version 1) whose backdoor is based on this property. It operates on 80-bit data blocks using a 120-bit cipher key and is directly inspired by the AES. The knowledge of the backdoor enables recovery of the full cipher key in just a few seconds on a laptop computer using only 2¹⁶ chosen plaintext blocks.

We also hope to develop our work further to explore the different classes of possible backdoors. In order to have a clearer view of the research presented in this book, we outline a tentative starting classification of backdoor techniques. Of course, we hope that other authors will have a critical cross-view of it and will make it evolve.

• Backdoors based on a single mathematical weakness. The backdoor is essentially put in the core cryptographic primitives, exploits algebraic or combinatorial properties and is independent of the key and the plaintext.

• Backdoors based on the combination of mixed techniques. Here, the backdoor relies on the combination of several factors: algebraic properties, combinatorial properties, environmental use of the algorithm (for example the nature of the plaintext encoding). Each aspects being taken separately, it is not possible to see the backdoor. Only the combined and global view makes it possible to see it, possibly. This approach seems promising in the light our study of real-life governmental encryption algorithms proposed in a more or less recent past.

  Laval, France

  May 26th, 2017

See Figures 1A to 11A.

Figure 1A.

The transformation mappings given over the standard basis of ${\mathbb{F}}_2^{10}$.

Figure 2A.

The linear mappings over ${({\mathbb{F}}_2^{10})}^4$ associated to M_U, M_V and the linear mapping P_U→V.

Figure 3A.

Specification of the diffusion M and its inverse M⁻¹.

Figure 4A.

Specification of the secret S-box S₀.

Figure 5A.

Specification of the modified S-box S₀.

Figure 6A.

Specification of the secret S-box S₁.

Figure 7A.

Specification of the modified S-box S₁.

Figure 8A.

Specification of the secret S-box S₂.

Figure 9A.

Specification of the modified S-box S₂.

Figure 10A.

Specification of the secret S-box S₃.

Figure 11A.

Specification of the modified S-box S₃.