Open access peer-reviewed compact

# Partition-Based Trapdoor Ciphers

By Arnaud Bannier and Eric Filiol

Submitted: December 5th 2016Reviewed: July 17th 2017Published: September 7th 2017

DOI: 10.5772/intechopen.70420

## 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.

### Keywords

• cryptography
• block ciphers
• backdoor
• trapdoor
• substitution-permutation network
• cryptanalysis

## 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’sDual_EC_DRBGstandard 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 theDUAL 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 ((2m)!)2κ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 F2m×F2κ(the product of the plaintext and ciphertext spaces) onto a subspace of F2m(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 F2nand hence corresponds with the XOR operation. The round function associated with the round key k is then defined by Fk:xF(x+k). If the round key k belongs to the coset a + b + V, then it holds that

Fk(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 PRINTCipherwere 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],,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])a[i+1]+V[i+1].E2

In this case, it is easy to see the all round functions Fk inherit such a property. The family of subspaces (V[i])iris 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))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.

WorkStructureKey dependence
Evertse [8]Linear structure (if any)Key independent
Leander et al. [9, 11]Exact cosetRound key dependent
Grassi et al. [12]Coset independentRound key independent
Our approachCoset independentRound 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 223 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 241 operations and 232 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 gf(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, Fc denotes its complement.

Let us denote the Galois field of order two by F2and 0n=(0,,0)the zero vector of F2n. All the vector spaces considered in this chapter are over the finite field F2. It is worthwhile to mention that (F2n)mwill be often identified with F2nm. The concatenation of two vectors x and y is denoted by (x || y).

An n-bit S-box is any permutation of F2n. If x and y are two elements of F2n, then x,y=i=0n1xiyi. If L:F2nF2mis a linear map, define L:F2mF2nby L(x),y=x,L(y)for every (x,y)F2n×F2m. In other words, Lis the transpose of L for the bilinear form ,.

Finally, we will denote the elements of F2nusing the hexadecimal notation. For instance, the element (1,0,1,1,1)of F25is 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 A, Bbe two partitions of E. Let f(A)denote the set {f(A)|AA}. We say that f maps Ato Bif f(A)=B. If A=B, we says that f preserves the partition A.

The two partitions {{x}|xE}and {E} are called the trivial partitions of E. Observe that, for any permutation f of E,

f({{x}|xE})={{x}|xE}andf({E})={E}.E3

That is, every permutation preserves the two trivial partitions. Moreover it should be highlighted that if f maps Ato Band if Ais nontrivial, then so is B.

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

07,10,23,36,42,51,65,74.E4

By definition,

f(A)={f(A)|AA}={f({0,1,4}),f({2,6}),f({3,7}),f({5})}={{7,0,2},{3,5},{6,4},{1}}.E5

The equality f(A)=Bholds, and thus f maps the partition Ato B.▴

Lemma 2.4. Let f be a permutation of E and A, Bbe two partitions of E. If for any part A of A, f(A) is a part of B, then f maps Ato 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 Abe a partition of F2n. Let V denote its part containing 0n. The partition Ais said to be linear if V is a subspace of F2nand if every part of Ais a coset of V in F2n, in other words, if

A={x+V|xF2n}=F2n/V.E6

We denote L(V)such a partition.

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

Example 2.7. Consider the subspaces V and W of F25defined by

V=span(07,1A)={00,07,1A,1D}andW=span(0E,12)={00,0E,12,1C}.E7

Since both V and W are two-dimensional subspaces of F25, the quotient spaces L(V)=F25/Vand L(W)=F25/Ware three-dimensional. In other words, the two linear partitions L(V)and L(W)have 23 = 8 parts. It can be verified that

L(V)={V,01+V,02+V,03+V,08+V,09+V,0A+V,0B+V},L(W)={W,01+W,02+W,03+W,04+W,05+W,06+W,07+W}.E8

For instance, the part0B+ V of the linear partition L(V)is the coset of V with respect to0B. Explicitly, it is equal to

0B+V={0B+00,0B+07,0B+1A,0B+1D}={0B,0C,11,16}.E9

Now, consider the permutation f of F25given in Figure 2.1. The image of0B+ V under f is

f(0B+V)=f({0B,0C,11,16})={0D,03,11,1F}={03+0E,03+00,03+12,03+1F}=03+W.E10

Observe that f(0B+V)is a coset of W so a part of 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 L(W), the permutation f maps L(V)to 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)=1E00. By contradiction, suppose that f is an affine transformation. Then, there exist a linear mapping L:F25F25and an element c of F25such that f(x)=L(x)+cholds for all x in F25. 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

for all x, y and z in F25. Observe that

f(00)+f(01)+f(02)=1E+08+04=1213=f(00+01+02).E12

Thus, f is not an affine transformation.▴

Lemma 2.8. Let V, W be two subspaces of F2nand f be a permutation of F2n, which maps L(V)to L(W). For any x in F2n, f maps x + V to f(x) + W.

Example 2.9. In Example 2.7, we have seen that f(0B+V)=03+W. Since f maps L(V)to L(W), the previous lemma states that f(0B+V)=f(0B)+W=0D+W. There is however no contradiction here because0Dbelongs to03+ W. Consequently, the cosets03+ W and0D+ 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 V1,V2,W1,W2be four subspaces of F2nand f be a permutation of F2n, which maps L(V1)to L(W1)and L(V2)to L(W2). Then f maps L(V1V2)to L(W1W2).

Proposition 2.11. Let V, W be two subspaces of F2nand f be a permutation of F2n, which maps L(V)to L(W). There exists an automorphism L of F2nsuch that L(V)=W. In particular, V and W are isomorphic.

Example 2.12. Consider again the permutation f of F25defined in Figure 2.8. As seen in the previous example, the permutation maps the linear partition L(V)to L(W). Then, Proposition 2.11 ensures that there exists a linear permutation L of F25such 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 F25

BV=(vi)i<5=(07,1A,01,02,08)andBW=(wi)i<5=(0E,12,01,02,04).E13

Then, the mapping L can be defined by L(vi) = wi 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 EK is just a permutation of the message space. Therefore, any partition Aof the plaintexts is mapped to the partition EK(A)of the ciphertexts. Nonetheless, to exploit the trapdoor, the designer needs to know the pair of partitions (A,EK(A)). The problem is that the output partition EK(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 EK(A)to be independent of the cipher key K. In other words, we want all the partitions EK(A)to be equal to a fixed partition 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 Ato a fixed partition 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 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 Aand Bbe two partitions of F2n. For each k in F2n, let αkdenote the permutation of F2ndefined by αk(x)=x+k. Then, the permutation αk maps Ato Bfor any k in F2nif and only if A=Band Ais 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

[nd]q=i=1d1qni+11qi.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 Fq. Therefore, the number of subspaces of F23is given by

d=03[3d]2=1+12312+(123)(122)(12)(122)+(123)(122)(121)(12)(122)(123)=1+7+7+1=16.E15

Since a linear partition of F23is uniquely determined by a subspace of F23, 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 span(2,4)={0,2,4,6}is L(span(2,4))={{0,2,4,6},{1,3,5,7}}.

Proposition 2.13 states that among the set of all the partitions of F2n, only the linear ones yield a unique output partition for every key. The Bell number Bm counts the number of partitions of a set of size m. Thus, the number of partitions of F2nis B2n. For n = 3, there are B8 = 4140 partitions in all. Hence, the linear partitions represent a fraction of 16/B8 ≈ 2−8.0. This ratio falls greatly as n increases. In fact, for n = 4, only 67/B16 ≈ 2−27.2 are linear and for n = 5, this ratio becomes 374/B32 ≈ 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,

α2(L(span(6))={f({0,6}),f({1,7}),f({2,4}),f({3,5})}={{2,4}, {3,5}, {0,6},{1,7}}=L(span(6)).E16

Thus, the permutation α2 preserves L(span(6)). 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.

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 F2nand V a subspace of F2n. Then, L(L(V))=L(L(V)). In particular, L maps a linear partition to another one.

Proof. Since L is an automorphism, we have

L(L(V))=L({x+V|xF2n})={L(x+V)|xF2n}={L(x)+L(V)|xF2n}={x+L(V)|xF2n}.E17

Moreover, L(V) is a subspace of F2nbecause L is a linear mapping. Consequently, L(L(V))=L(L(V)). ▪

If V and W are two subspaces of F2n, it is straightforward to design a linear permutation L of F2nmapping L(V)to L(W). Indeed, Proposition 2.15 establishes that L maps L(V)to 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 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 S0,…,Sm−1 be n-bit S-boxes.

• The addition of the round key k is denoted by αk:F2nmF2nm, xx+k.

• The substitution layer is denoted by σ and maps (xi)0i<mto (Si(xi))0i<m.

• The diffusion layer is a linear permutation denoted by π:F2nmF2nm.

The round function Fk associated with the round key k is defined by Fk=πσαk. The encryption function associated with the round keys K=(k[0],,k[r])in (F2nm)r+1is defined by

EK=αk[r]Fk[r1]Fk[0].E18

We can now prove the following result.

Theorem 2.17. Let Aand Bbe two partitions of F2nm. Suppose for any (r + 1)-tuples of round keys K=(k[0],,k[r])in (F2nm)r+1that the encryption function EK maps Ato B. Define A[0]=Aand for all 1ir, A[i]=(πσ)i(A). Then,

• A[r]=B;

• for any 0 ≤ i < r and for any k[i] in F2nm, Fk[i](A[i])=A[i+1];

• for any 0ir, A[i]is a linear partition.

Proof. Observe that for the round key k = 0nm, the key addition α0nmis the identity mapping on F2nm, and thus F0nm=πσα0nm=πσ. Now, choosing K=(k[0],,k[r])=(0nm,,0nm)gives

B=EK(A[0])=αk[r]Fk[r1]Fk[0](A[0])=α0nm(F0nm)r(A[0])=(πσ)r(A[0])=A[r].E19

Let 0i<rbe an integer. Let k[i] be any element of F2nm. Define k[j]=0nmfor all 0jrsuch that ji. By hypothesis, the equality αk[r]Fk[r1]Fk[0](A[0])=A[r]holds. Thus,

Fk[i]Fk[0](A[0])=(αk[r]Fk[r1]Fk[i+1])1(A[r]).E20

On one hand,

Fk[i]Fk[0](A[0])=Fk[i](Fk[i1]Fk[0])(A[0])=Fk[i](F0nm)i(A[0])=Fk[i](πσ)i(A[0])=Fk[i](A[i]).E21

On the other hand,

(αk[r]Fk[r1]Fk[i+1])1(A[r])=(α0nm(F0nm)r(i+1))1(A[r])=((πσ)r(i+1))1(A[r])=A[i+1].E22

Therefore, Fk[i](A[i])=A[i+1], or equivalently αk[i](A[i])=(πσ)1(A[i+1]). Since this equality holds for every k[i], Proposition 2.13 states that the partition A[i]is linear.

It remains to show that A[r]is linear as the previous argument holds only for i < r. Let k[r] be an element of F2nm. Define k[i] = 0nm for each 0i<r. Then,

A[r]=αk[r]Fk[r1]Fk[0](A[0])=αk[r](F0nm)r(A[0])=αk[r](A[r]).E23

Again, Proposition 2.13 implies that A[r]is linear and the result is proven. ▪

This theorem can be restated in the following way. First, the input partition Aand the output partition Bmust 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 Ato Bafter 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 0ir, let V[i] denote the part of A[i]containing 0. According to Theorem 2.17, A[i]=L(V[i]). Let 0i<rbe an integer. Then,

σ(L(V[i]))=L(W[i]).E24

where W[i] denotes the subspace π1(V[i+1]). In particular, the substitution layer must at least map one linear partition to another one.

Proof. By definition, πσ(A[i])=A[i+1]or, equivalently, σ(A[i])=π1(A[i+1]). This equality can be restated as

σ(L(V[i]))=π1(L(V[i+1])).E25

As π is an automorphism of F2nm, then so π−1 is. Next, Proposition 2.15 ensures that π1(L(V[i+1]))=L(π1(V[i+1])). 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 Aof the plaintext space to a partition Bof 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.

### 3. Structure of the substitution layer

In the remainder of this chapter, V and W will denote two subspaces of (F2n)m.

As explained in the previous section, it remains to understand how the substitution layer can map the linear partition L(V)to 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 L(V)to 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 L(V)to 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 S0, S1, S2 and S3 described in Figure 2.6. Its parameters are then m = 4 and n = 5. Observe that the S-box S2 was previously studied in Example 2.7. Define the two families EV=(vi)0i<7and EW=(wi)0i<7of elements of (F25)4by

v0=(10,00,00,17),v1=(08,00,00,17),v2=(04,00,00,0B),v3=(02,00,00,1C),v4=(01,00,00,1C),v5=(00,00,1A,00),v6=(00,00,07,00).w0=(10,00,00,15),w1=(08,00,00,1D),w2=(04,00,00,15),w3=(02,00,00,08),w4=(01,00,00,00),w5=(00,00,12,00),w6=(00,00,0E,00).E26

Finally, define V and W as the subspaces spanned by EVand EW, respectively. Note that the family EVis linearly independent because it is echelonized. Hence, EVis a basis of V. The same applies for EWand W. As a consequence, V and W are both seven-dimensional subspaces of (F25)4.

We claim that the substitution layer σ maps L(V)to L(W). Naturally, we will not verify this statement by hand because it requires to check for each of the 213 cosets of V that the 27 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 L(V)to 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 0,mand define the following mappings

TE:(F2n)m(F2n)EσE:(F2n)E(F2n)E(xi)0i<m(xi)iE(xi)iE(Si(xi))iE.E27

If E has cardinality p, then we identify (F2n)Ewith (F2n)p.

The mapping TE allows to shorten a vector of (F2n)mto 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 TE is a linear mapping. Observe that σ0,mis the substitution layer of the SPN. Moreover, the truncated substitution layer σ{i}and the S-box Si are equal for all 0i<m.

Proposition 2.22 (truncating to a few S-boxes). Suppose that σ maps L(V)to L(W). Let E be a nonempty subset of 0,m. Then, the permutation σE maps L(TE(V))to L(TE(W)).

Proof. Let x=(xi)iEbe an element of (F2n)E. Let y be the element of (F2n)mdefined by yi = xi if i belongs to E and yi=0notherwise. Thus, TE(y)=x. By hypothesis, σ maps L(V)to L(W). Hence, Lemma 2.8 implies that σ(y+V)=σ(y)+W. Next,

TE(σ(y+V))=TE(σ(y))+TE(W)E28

since TE is a linear mapping. Furthermore,

TE(σ(y+V))=TEσ({y+v|vV})={TEσ(y+v)|vV}={σE(TE(y+v))|vV}=σE({TE(y+v)|vV})=σE({TE(y)+TE(v)|vV})=σE(TE(y)+TE(V)).E29

Therefore, σE(x+TE(V))=TE(σ(y))+TE(W). In other words, the image of any part of L(TE(V))under σE lies in L(TE(W)). The result is a consequence of Lemma 2.4. ▪

Example 2.23. By choosing E={0,3}, the previous proposition ensures that the truncated substitution layer σ{0,3}maps L(T{0,3}(V))to L(T{0,3}(W)). First, it is easy to see that

T{0,3}(V)=span((10,17),(08,17),(04,0B),(02,1C),(01,1C)),T{0,3}(W)=span((10,15),(08,1D),(04,15),(02,08),(01,00)).E30

Again, we will not explicitly check that σ{0,3}maps L(T{0,3}(V))to L(T{0,3}(W))but limit ourselves to prove that the coset (07,03)+T{0,3}(V)is mapped to one coset of T{0,3}(W). Its image can be found using Lemma 2.8 as follow

σ{0,3}((07,03)+T{0,3}(V))=σ{0,3}((07,03))+T{0,3}(W)=(07,1A)+T{0,3}(W).E31

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

σ{0,3}((07,03)+(01,1C))=σ{0,3}(06,1F)=(S0(06),S3(1F))=(01,07)=(07,1A)+(06,1D).E32

This explains the second image.▴

Choosing E = {i} in Proposition 2.22 gives that the S-box Si maps L(T{i}(V))to L(T{i}(W)). As this result holds for each index i in 0,m, we deduce that

σ(L(V))=L(W)i0,m,Si(L(T{i}(V)))=L(T{i}(W)).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:

T{0}(V)=F25,T{1}(V)={00},T{2}(V)=span(07,1A),T{3}(V)=span(0B,17),T{0}(W)=F25,T{1}(W)={00},T{2}(W)=span(0B,17),T{3}(W)=span(08,15).E34

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

S2(L(span(07,1A)))=L(span(0B,17)),S3(L(span(0B,17)))=L(span(08,15)).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.

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 S0, S1, S2and S3where

S0=S1,S1=S1,S2=S2,S3=S3.E36

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

i0,4,Si(L(T{i}(V)))=L(T{i}(W)).E37

However, we will prove that σ′ does not map L(V)to L(W). Suppose by contradiction that it does. Then Proposition 2.22 ensures that σ{0,3}maps L(T{0,3}(V))to L(T{0,3}(W)). By Lemma 2.8,

σ{0,3}((07,03)+T{0,3}(V))=σ{0,3}(07,03)+T{0,3}(W)=(S0(07),S3(03))+T{0,3}(W)=(S1(07),S3(03))+T{0,3}(W)=(07,1A)+T{0,3}(W).E38

Then

σ{0,3}((07,03)+(01,1C))=σ{0,3}(06,1F)=(S0(06),S3(1F))=(S1(06),S3(1F))=(0C,07)=(07,1A)+(0B,1D).E39

This is a contradiction since (0B,1D) does not belong to T{0,3}(W)as can be seen in Figure 2.7. As a consequence, the substitution layer σ′ does not map L(V)to 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 L(V)to 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 Iof 0,m. Each part I of Irepresents a sub-problem, and its elements are the indices of the S-boxes involved in. By virtue of Proposition 2.22, it holds that

σ(L(V))=L(W)II,σI(L(TI(V)))=L(TI(W)).E2.2

The next section aims to find a sufficient condition on the partition Ito obtain the equivalence. In such a case, this means that combining the solutions of these sub-problems yields a substitution layer mapping L(V)to 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 0,m. The trivial product subspace associated with E, denoted by TrivE, is defined to be

TrivE={x(F2n)m|iEc,xi=0n}.E41

Moreover, we denote by VE the intersection of V and TrivE, that is VE=VTrivE={vV|iEc,vi=0n}. The subspace WE is defined in the same way.

Remark 2.26. It is easily seen that

TrivE=i=0m1TrivE[i]withTrivE[i]={{0n}ifiEc,F2nifiE.E42

Thus, a trivial product subspace is the Cartesian product of trivial spaces for each S-box; this justifies its name. Additionally, if EF, then TrivETrivF, and hence VEVFand WEWF.

The subspaces TrivE are essential in the study of the substitution layer because the latter always preserves the partition L(TrivE)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 0,m. If σ maps L(V)to L(W), then σ also maps L(VE)to L(WE).

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

V{0}=span((15,00,00,00),(0D,00,00,00),(03,00,00,00)).E43

Additionally, this figure also highlights the expected inclusions given by Remark 2.26. Observe that BV=(vi)0i<7is a basis of V. This new basis is more convenient than the echelonized basis EVpreviously introduced in Example 2.19 since all the VE are then easily described. It is worth noting that the same picture remains valid for the subspace W. For example,

W{0}=span((14,00,00,00),(0E,00,00,00),(01,00,00,00)).E44

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

According to Corollary 2.27, the substitution layer maps L(V{0})to L(W{0}). Next, truncate to E = {0} using Proposition 2.22 to obtain

S0(L(span(03,0D,15)))=L(span(01,0E,14)).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 S0 (see Example 2.24).▴

Definition 2.29 (projection PE). Let E be a subset of 0,m. The projection PE from (F2n)monto TrivE is defined by PE(x0,,xm1)=(y0,,ym1)where yi = xi if i belongs to E and yi = 0n otherwise.

Remark 2.30. It is not hard to see that PE is a linear mapping and that VE is always a subspace of PE(V). Moreover, it holds that TE(V)=TE(PE(V)).

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 Ibe a partition of 0,m. Then V equals the internal direct sum IIVIif and only if VI=PI(V)for any part I of I. In this case, the decomposition of an element v of V is v=IIPI(v).

Remark 2.32. Suppose that Iis a partition of 0,msuch that V=IIVI. The previous lemma, together with Remark 2.30, establishes that TI(V)=TI(VI)for each part I of I.

Proposition 2.33 (Substitution layer structure). Let Ibe a partition of 0,msatisfying both V=IIVIand W=IIWI. The permutation σ maps L(V)to L(W)if and only if σI maps L(TI(V))to L(TI(W))for any I in I.

The preceding proposition establishes that the converse of Implication 2.2 (page 21) holds whenever the partition Isatisfies both V=IIVIand W=IIWI. For such a partition, the problem of finding all the substitution layers σ mapping L(V)to L(W)can equivalently be broken down into the independent sub-problems of finding all the σI mapping L(TI(V))to L(TI(W))for each part I of I.

#### 3.3. Linked and independent S-boxes

Of course, there may be several partitions Isuch that V=IIVIand W=IIWI, 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 L(V)to L(W). For every partition Iof 0,m, V=IIVIif and only if W=IIWI.

The contrapositive of Lemma 2.34 is the following: if there exists a partition Isuch that V=IIVIand WIIWIor such that VIIVIand W=IIWI, then there exists no substitution layer mapping L(V)to L(W). Because we intend to study the substitution layers mapping L(V)to 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 Iof 0,m, it holds that

V=IIVIW=IIWI.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 0,msuch that V=IIVI.

Remark 2.37 (partial order on partitions). Recall that if Iand Jare two partitions of 0,m, then the partition Iis said to be finer than Jif for any part I in I, there exists a part J in Jsuch that IJ.

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 IIVIif and only if VI is equal to PI(V) for each part I of I. The eight-framed subspaces in the middle of Figure 2.9 are exactly those that satisfy VE=PE(V). Hence, the decomposition partitions are the partitions whose parts are selected from the following:

,{1},{2},{1,2},{0,3},{0,1,3},{0,2,3},{0,1,2,3}.E47

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

{{1},{2},{0,3}},{{1},{0,2,3}},{{2},{0,1,3}},{{0,3},{1,2}}and{{0,1,2,3}}.E48

In Figure 2.11, all the partitions of 0,4are 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.▴

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 Iof 0,msatisfying V=IIVIhas a least element denoted Ild.

Consequently, the only decomposition partition that will be considered in the remainder of this chapter is the least decomposition partition Ild. The following definition is inspired by Proposition 2.33 and Proposition 2.39.

Definition 2.40 (linked and independent S-boxes). Suppose that σ maps L(V)to L(W). Let I be a part of Ild.

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

Moreover, if V{i}={0nm}or V{i}=Triv{i}, the S-box Si is said to be inactive. Otherwise, Si 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 ≤ im be an integer. We have already noted that the substitution layer σ always preserves L({0nm})and L(Triv{i}). In addition, Proposition 2.33 ensures that σ maps L(V{i})to L(W{i}). Consequently, if V{i}={0nm}or if V{i}=Triv{i}, then V{i}= W{i}.

Suppose that the S-box Si is independent with regard to the subspaces V and W. As established by Proposition 2.33 and Remark 2.32, if Si is replaced with another S-box Si, then this new substitution layer still maps L(V)to L(W)provided that Simaps L(T{i}(V{i}))to L(T{i}(W{i})).

Suppose further that Si is active. By definition, {0nm}V{i}Triv{i}. Observe that the restriction of T{i} to Triv{i} is one-to-one, hence

{0n}=T{i}({0nm})T{i}(V{i})T{i}(Triv{i})=F2n.E49

Thus, T{i}(V{i}) is a nontrivial subspace of F2nand the requirement that Simaps L(T{i}(V{i}))to L(T{i}(W{i}))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 Si is inactive. By definition, V{i}={0nm}or V{i}=Triv{i}. Then, the equality V{i}=W{i}follows from Remark 2.41 and we have that

T{i}(V{i})=T{i}(W{i})={0n}orT{i}(V{i})=T{i}(W{i})=F2n.E50

In either case, the condition that Simaps L(T{i}(V{i}))to L(T{i}(W{i}))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 L(V)to 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 Ild={{1},{2},{0,3}}. By Proposition 2.33, the substitution layer maps L(V)to L(W)is and only if the following equalities hold:

σ{0,3}(L(T{0,3}(V)))=L(T{0,3}(W)),S1(L(T{1}(V))=L(T{1}(W)),S2(L(T{2}(V))=L(T{2}(W)).E51

Thus, the S-box S1 is independent of the other S-boxes, the same applies to S2 and the S-boxes S0 and S3 are linked together. As was already noted in Figure 2.9, we have that

V{1}={(00,00,00,00)}andV{2}=span((00,00,1A,00),(00,00,07,00)).E52

Therefore, the S-box S2 is active while S1 is inactive.▴

#### 3.4. The forbidden case

Throughout this section, we assume that the substitution layer σ maps L(V)to 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 Ibe a decomposition partition. Let I be a part of Isuch that #I ≥ 2 and let E be a nonempty proper subset of I. Suppose that VE=VI\E={0nm}and PE(V)=TrivE. Then, for all i in E, Si 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 Ild={{1},{2},{0,3}}. Its only part of cardinality greater than or equal to 2 is I={0,3}. The nonempty proper subsets of I are the E = {0} and E = {1}. According to Figure 2.9, we have V{0}{020}. 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 S0and S1; hence, its parameters are m = 2 and n = 3. Define the subspaces V′ and W′ of (F23)2by

V=W=span((4,4),(2,2),(1,1))={(x,x)|xF23}.E53

Finally, suppose that σ′ maps L(V)to L(W). It is easily seen that

V={(0,0)},V{0}={(0,0)},V{1}={(0,0)},V{0,1}=V,P(V)=Triv,P{0}(V)=Triv{0},P{1}(V)=Triv{1},P{0,1}(V)=V.E54

Thus, the least decomposition partition with regard to V′ and W′ is {{0, 1}}. The S-boxes S0and S1are then linked together. Choosing E = {0} in Proposition 2.43 ensures that S0must be affine. Similarly, we can prove that S1must also be affine by considering E = {1}. As a result, any substitution layer σ′ mapping L(V)to L(W)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 Ildand E be a non-empty proper subset of I.

• If VE is a trivial product subspace, then VE=Triv={0nm}.

• If PE(V) is a trivial product subspace, then PE(V)=TrivE.

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.

Theorem 2.46. Let n ≥ 2 and m be two positive integers. Let S0,…,Sm–1 be n-bit S-boxes. Define the permutation σ of (F2n)m, which maps the element (xi)0i<mto (Si(xi))0i<m. Let V and W be two subspaces of (F2n)msuch that σ maps L(V)to 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, σ = S0. By hypothesis, V is different from {0n} and F2n. Hence, L(V)is a nontrivial partition and S0 maps L(V)to 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, Ild={{i}|i0,m}. 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 Si. In this case, {0nm}V{i}Triv{i}. According to Lemma 2.31, the equality P{i}(V)=V{i}holds. Then, T{i}(V{i})=T{i}(P{i}(V))=T{i}(V)is a nontrivial subspace of F2n, so L(T{i}(V))is also nontrivial. Finally, Proposition 2.22 states that Si maps L(T{i}(V))to L(T{i}(W)), and thus the result holds in this case.

Now, suppose that some S-boxes are linked together. Then, there exists an element I of Ildsuch 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 PE(V) is not a trivial product subspace. Let p denote the cardinality of E. Recall that TE(PE(V))=TE(V). It follows that TE(V) is not a trivial product subspace of (F2n)p. According to Proposition 2.22, σE maps L(TE(V))to L(TE(W)). Note that E is a non-empty proper subset of I, so of 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 VE is not a trivial product subspace. Recall that σ maps L(VE)to L(WE). Proposition 2.22 ensures that σE maps L(TE(VE))to L(TE(WE)). It is easily seen that TE(VE) 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 PE(V), VE and VI\E are all trivial product subspaces. Then, Lemma 2.45 implies that PE(V) = TrivE and VE=VI\E={0nm}. 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 L(V)to 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 Ild={{1},{2},{0,3}}and deduce that:

• S1 is inactive;

• S2 is active and maps L(span(07,1A))to L(span(0E,12))(see Figure 2.2);

• S0 and S3 are linked together.

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

P{0}(V)=Triv{0}andP{3}(V)=span((00,00,00,0B),(00,00,00,1C)).E55

Thus, P{3}(V) is not a trivial product subspace. As in Example 2.24 and Figure 2.8, we see that S3 maps L(0B,1C)to L(08,15)by truncating σ and the subspaces P{3}(V), P{3}(W)to {3}. Now, we need to compute the following subspaces:

V{0}=span((03,00,00,00),(0D,00,00,00),(15,00,00,00))andV{3}=Triv.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 S0 maps L(03,0D,15)to L(01,0E,14). 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 S0, S1 and S2. Define the subspaces V and W of (F23)3by

V=W={(x,y,x+y)|x,yF23}E57

and assume that the substitution layer σ maps L(V)to L(W). By definition, it holds that P(V)={(0,0,0)}and P{0,1,2}(V)=V. Then, for each nonempty proper subset E of {0,1,2}, it is easily seen that PE(V)=TrivE. For instance,

P{0,1}(V)={(x,y,0)|x,yF23}=Triv{0,1}.E58

We know that V={(0,0,0)}and V{0,1,2}(V)=V. The other subspaces VE are the following:

V{0}={(0,0,0)},V{1}={(0,0,0)},V{2}={(0,0,0)},V{0,1}={(x,x,0)|xF23},V{0,2}={(x,0,x)|xF23},V{1,2}={(0,x,x)|xF23}.E59

Thus, the equality PE(V)=VEholds only for E=and E = {0,1,2}. Consequently, the least decomposition partition is Ild={{0,1,2}}, 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 PE(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 L(V)to L(W)where

V=W=T{0,1}(V{0,1})={(x,x)|xF23}.E60

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

V={(0,0)},V{0}={(0,0)},V{1}={(0,0)},V{0,1}=V,P(V)=Triv,P{0}(V)=Triv{0},P{1}(V)=Triv{1},P{0,1}(V)=V.E61

Thus, the least decomposition partition with regard to V′ and W′ is {{0,1}}. Since V{0}, V{1}, P{0}(V)and P{1}(V)are all trivial products, the first and second cases do not apply. Choosing E = {0} and E = {1} in the third case proves that S0 and S1 are affine mappings. Come back to the full substitution layer. Similarly, it is straightforward to verify that S2 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 L(V)to L(W)is necessarily affine.▴

In this chapter, we have studied a generic SPN mapping a partition Aof F2nmto a partition Bof F2nm, independently of the round keys used. Combining Theorem 2.17 and Corollary 2.18, we proved that there exist two families (V[i])0irand (W[i])0irof subspaces of F2nmsuch that the substitution layer σ maps L(V[i])to L(W[i])for each 0 ≤ ir. 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 DTS and LTS indexed by (F2n)2and defined for any (a, b) in (F2n)2by

DTS(a,b)=#{xF2n|S(x)+S(x+a)=b},LTS(a,b)=#{xF2n|a,x=b,S(x)}2n1.E62

Moreover, the S-box S is said to be differentially δ-uniform if DTS(a,b)δfor any (a, b) in (F2n)2with a ≠ 0. Similarly, S is linearly λ-uniform if |LTS(a,b)|λfor every (a, b) in (F2n)2with 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 2n12-uniform.

Recall that two permutations S1 and S2 of F2nare said to be equivalent if there exist two linear mappings L1, L2 of F2nand two elements v1, v2 of F2nsuch that

xF2n,S2(x)=L2(S1(L1(x)+v1))+v2.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 F2n. Suppose that S′ is an n-bit S-Box mapping L(V)to L(W). Proposition 2.11 ensures that there exists an automorphism L of F2nsuch that L(V)=W. Since L1(W)=V, Proposition 2.15 states that L−1 maps L(W)to L(V). Then, S=L1Sis equivalent to S′ and maps L(V)to L(V). This discussion establishes the following proposition.

Proposition 3.2. Let V and W be two subspaces of F2n. If S′ is an n-bit S-box mapping L(V)to L(W), then there exists an S-box S equivalent to S′ preserving L(V).

Remark 3.3. Conversely, suppose that S preserves L(V). Let W be any subspace isomorphic to V. Then find an automorphism L such that L(V) = W. By Proposition 2.15, LSmaps L(V)to 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 S2 respectively). Thus, we know that S′ maps L(V)to L(W)where V=span(07,1A)and W=span(0E,12). Following the proof of Proposition 2.11, an automorphism L of F25satisfying L(V) = W was constructed in Example 2.12. Its inverse L−1 and the composition S = L−1S′ are given in Figure 3.1. For instance, S(07)=L1(S(07))=L1(10)=18. It is easy to check in Figure 3.2 that S preserves the linear partition 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.▴

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 L(V)to L(W).

Throughout this section, we consider the following

• let V be a d-dimensional nontrivial subspace of F2n,

• let U be a complement space of V,

• let S be an n-bit S-box preserving L(V).

Therefore, the space F2ncan be written as the direct sum UV. In other words, every element x of F2ncan 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 L(V)where u lies in and we have

L(V)={[u]|uU}.E64

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

1dn1and1ndn1E65

because V is assumed to be a nontrivial subspace of F2n.

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 (τu)uUof V such that, for all x = u + v in F2n,

S(u+v)=ρ(u)+τu(v).E66

Conversely, if ρ is a permutation of U and if (τu)uUis a family of permutations of V, then the mapping S′ defined by S(u+v)=ρ(u)+τu(v)preserves L(V).

Proof. By hypothesis, S preserves 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]. Define then ρ(u)=u. For each element u of U, define the permutation τu of V, which maps v to S(u+v)+ρ(u). By construction, for any u in U and any v in V, we have

τu(v)=S(u+v)+ρ(u)andhenceS(u+v)=ρ(u)+τu(v).E67

The existence of the permutations ρ and τu is proven. Now, let us show their uniqueness. Suppose that there exist a permutation ρ˜of U and a family of permutations (τ˜u)uUof V satisfying the result. Let (u, v) be an element of U × V. By hypothesis, we have

ρ(u)+τu(v)=ρ˜(u)+τ˜u(v).E68

Because the sum of U and V is direct, it follows that ρ(u)=ρ˜(u)and τu(v)=τ˜u(v). The uniqueness of ρ and the τu follows.

Conversely, let ρ be a permutation of U and (τu)uUbe a family of permutations of V. Denote S′ the mapping from F2nto F2ndefined by S(u+v)=ρ(u)+τu(v). Since F2n=UVand ρ and the τu are permutations of U and V respectively, The mapping S′ is a permutation of F2n. Let u be an element of U. It holds that

S([u])={S(u+v)|vV}={ρ(u)+τu(v)|vV}=ρ(u)+{τu(v)|vV}=ρ(u)+V=[ρ(u)].E69

Hence, S′ preserves the linear partition L(V). ▪

This theorem allows us to design an S-box that preserves 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=span(01,02,08)={00,01,02,03,08,09,0A,0B}.E70

Figure 3.2 shows that S induces a permutation ρ of U. For instance, ρ(00)=02because 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 τu(v)=S(u+v)+ρ(u). For example,

τ02(1D)=S(02+1D)+ρ(02)=S(1F)+ρ(02)=12+08=1A.E71

The permutations τu are also given in Figure 3.3. Informally, the permutation ρ tells us how S permutes the parts of L(V)and the permutations (τu)uUdescribe how the elements are moved inside each part (Figure 3.4).▴

In the rest of this section, the permutation ρ and the family (τu)uUgiven 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 (τu)uU. However, these permutations are not defined on F2nbut on the subspaces U and V of F2n. Thus, the concept of linear or differential table is inexistent for such maps. To solve this problem, we define two isomorphisms between U and F2ndand between V and F2d. Then, we consider the maps induced by ρ and (τu)uUon these spaces.

Notation 3.7. Let BU=(ui)i<ndand BV=(vi)i<ndbe two bases of U and V respectively. Define the following mappings:

LU:F2ndULV:F2dV(xnd1,,x0)i0nd1xiui,(yd1,,y0)i=0d1yivi.E72

It is easily seen that LU and LV are both isomorphisms of vector spaces. Define the permutation ρ=LU1ρLUof F2nd. Finally, for each u in U, let τudenote the permutation LV1τuLVof F2d.

Example 3.8. Consider the bases BU=(01,02,08)and BV=(07,1A)and define the isomorphisms LU and LV. The permutation ρ′ of F23and the permutations τuof F22are given in Figure 3.5.

### 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. Denote at=LU(a)and bt=LU(b). Then,

LTS(a,b)=2d×LTρ(at,bt).E73

Remark 3.10. Consider the map LU:F2nF2nd. Then, ker(LU)=(ImLU)=U.Observe that UV=(U+V)=(F2n)={0}. Consequently, the restriction LU:VF2ndis one-to-one and thus onto because of the rank-nullity theorem.

Example 3.11. The restriction LU:VF23is given by the following table.

 a 00 05 0B 0E 13 16 18 1D LU⊺(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 ((LU)1(x))xF23, 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 LTS is exactly the linear table of ρ′ multiplied by 2d = 4. For instance, LTS(1D,16)=22×LTρ(5,2)=8because LU(1D)=5and LU(16)=2.▴

Corollary 3.12. The S-box S is at least linearly 2(n+d1)/2-uniform.

Proof. As noted in Remark 3.1, there exist two elements at and bt of F2ndboth nonzero such that |LTρ(at,bt)|2(nd1)/2. Let a and b denote the elements (LU)1(at)and (LU)1(bt)of F2n. Then, Theorem 3.9 implies that

|LTS(a,b)|=2d×|LTρ(at,bt)|2d×2(nd1)/2=2(n+d1)/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 2d+2-uniform if nd = 4. Similarly, any 2-bit S-Box is linearly 2-uniform, and hence S is at least 2d+1-uniform if nd = 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+d1)/2=2(5+21)/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=ua+vaand b=ub+vbbe elements of F2n. Denote ua=LU1(ua)and ub=LU1(ub). Then

i[ua]DTS(i,b)=j[ub]DTS(a,j)=2d×DTρ(ua,ub).E75

Especially, DTS(a,b)2d×DTρ(ua,ub).

The preceding theorem can be restated in the following way. If DTS 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 DTS involved in the differential uniformity of S.

Theorem 3.16. Let va and vb be two elements of V. Denote va=LV1(va)and vb=LV1(vb). Then

DTS(va,vb)=uUDTτu(va,vb).E76

Particularly, the subtable (DTS(va,vb))va,vbVis uniquely determined by the differential tables (DTτu)uU.

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 DTS([u1],[u2])is equal to the coefficient (x1, x2) of DTρmultiplied by 22, where xi=LV1(ui). For instance, if we consider the subtable

we can see that the sum of each row or column is equal to 8=22×DTρ(5,3)since LV(5) =09and LV(3) =03.

Finally, Theorem 3.16 ensures that the subtable DTS(V,V)=DTS([00],[00])is the sum of the differential tables (DTτu)uU.▴

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 2n2d1.

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 DTρis, the better.

• Finally, Theorem 3.16 teaches us that the sum of the differential distribution tables DTτushould be as low as possible.

Now, to design the S-box S, one needs to pick a permutation ρ′ of F2ndwith the smallest uniformities for linear and differential cryptanalysis. Then, one searches for permutations τuof F2dsatisfying 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.

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 216 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 (F210)8and (F210)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 S0, S1, S2, S3 and are defined in Figures 5A, 7A, 9A and 11A given in Appendix. They should not be confused with the secret S-boxes S0, S1, S2 and S3, 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: theShiftRowsand theMixColumnsoperations. The first part is a bundle permutation. The second evaluates in parallel the linear transformation M:(F210)4(F210)4processing four 10-bit bundles. Because of its linearity, M is only defined over the standard basis of (F210)4in Figure 3A in Appendix. For convenience, its inverse M−1 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.

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 theShiftRowsare 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 Si1(S(x))=xholding for each x in F210.

#### 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 (401024)252116.9and the absolute bias of a 10-round linear trail is upper bounded by (128512)25=250. Consequently, a differential cryptanalysis of the 10-round version of our cipher would require at least 2117 chosen plaintext/ciphertext pairs and a linear cryptanalysis would require 2100 known plaintext/ciphertext pairs.

Even if this is a rough approximation since it does not take into account the inter-column diffusion provided by theShiftRowsoperation, it suffices to prove the cipher’s practical resistance against classical differential and linear cryptanalysis. In fact, there are only 280 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 F210

V0=span(266,343,3ED,354,17F),W0=span(16A,11B,306,05E,0B8),V1=span(398,229,34C,251,37B),W1=span(04B,3B7,0D5,027,2C8),V2=span(0BA,155,307,37E,318),W2=span(1A9,095,107,36F,2A3),V3=span(1D1,21E,134,0DC,15A),W3=span(0F0,2FE,191,332,1A6).E78

Then, define the 40-dimensional subspaces V=i=07Vimod4and W=i=07Wimod4of message space (F210)8. Therefore, the linear partitions L(V)and L(W)are both made up with 240 cosets, each containing 240 elements.

The S-boxes S0, S1, S2 and S3 given in the specification of BEA-1 are actually derived from the secret S-boxes S0, S1, S2 and S3 given in Figures 4A, 6A, 8A and 10A in Appendix. The relation between the secret S-boxes Si and their modified versions Si 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 S0, S1, S2, and S3 are replaced with their secret counterparts S0, S1, S2, and S3. Then, the round function preserves the linear partition L(V)of (F210)8and the last round maps L(V)to L(W), no matter the round keys used. As a consequence, the full encryption maps L(V)to L(W).

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

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 Vi and Wi. Each of these subspaces of F210is 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 F280inherit 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 Vi and Wi could have been freely chosen among the five-dimensional subspaces of F210. 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 Vi and Wi.

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],,k[10]:

p[i+1]=Fk[i](p[i])andp[i+1]=Fk[i](p[i])for0i<11.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

((9441024)6×(9251024)2)11211.E80

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

Remark 4.5. The fact that theMixColumnsoperation 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 EK and EK is approximatively 2−11, even when the round keys are derived from a fixed cipher key K. To put it another way, if Pis a subset of the plaintext space (F210)8, it seems reasonable to assume that

#{pP|EK(p)=EK(p)}#P211.E4.1

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

{pP|EK(p)=EK(p)}{pP|EK(p)(y+W)}.E4.2

Combining (4.1) with (4.2), we conclude that approximately #P×211ciphertexts in C=Ek(P)belong to y + W. In addition, we have observed that the ciphertexts c = EK(p) such that EK(p)EK(p)are spread over the 240 cosets of W.

The backdoor of BEA-1 is hence the following. First, choose a set Pof 216 plaintexts uniformly chosen in one coset x + V and collect their ciphertexts C=EK(P)encrypted under an unknown cipher key K. Then search for the most represented coset of W in Cand denote by y one of its representatives. According to our experiments, this coset should have roughly 216–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 EK. 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 L(i=011Wi), provided that the S-boxes Si are replaced with their secret equivalents Si. This implies that if two cipher keys K and K′ are in the same coset of i=011Wi, 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 (9443925240)723.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 (S0||S1||S2||S3) 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 {05}×F25and F25×{05}of F210. It should be noted that {*0} is a complement space of {0*} in F210. The design of each secret S-box Si rests on a permutation S'iof F210preserving the linear partition L({0*}). Following Theorem 3.5, we just need to choose a permutation ρi of {*0} and a family (τi,u)u{*0}of permutations of {0*}. Then, we define S'ifor all x = u + v in F210by

S'i(x)=S'i(u+v)=ρi(u)+τ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'iagainst both differential and linear cryptanalysis.

Figure 1A in Appendix defines the linear mappings LViand LWi(for 0 ≤ i ≤ 4) over the standard basis of F210. It is worthwhile to note that these mappings are automorphisms of F210. Moreover, LVi({0*})=Viand LWi({0*})=Wi. By virtue of Proposition 2.15, we know that LVimaps L({0*})to L(Vi)and that LWimaps L({0*})to L(Wi). Last, but not least, define for each 0 ≤ i < 4 the secret S-box Si by

Si=LWiSi(LVi)1.E84

These S-boxes are given in Figures 4A, 6A, 8A and 10A in Appendix. Obviously, (LVi)1maps L(Vi)to L({0*}), then Sipreserves L({0*}), and LWimaps L({0*})to L(Wi). This implies the following proposition.

Proposition 4.6. For each 0 ≤ i < 4, the secret S-box Si maps L(Vi)to L(Wi).

Remark 4.7. If the reader is interested in an explicit definition of the permutations ρi and the families of permutations (τi,u)i{*0}, they can be recovered in the following way. First, compute Si=(LWi)1SiLViusing the tables of Figures 1A and 4A (or 6A, 8A, 10A). As noted previously, the permutation Sipreserves the linear partition L({0*}). 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 {*0}(Si(u)+{0*}). It is not hard to see that ρi(u) is simply equal to the element of F210, where the five leftmost bits are exactly the ones of Si(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 τi,u(v)=Si(u+v)+ρ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 Si(u+v). Naturally, the permutations ρi and τi,u can be seen as permutations of F25(instead of {*0} and {0*}) to obtain the more convenient definition

Si(uv)=(ρi(u)τi,u(v)).E85

The modified S-boxes Si given in the specification of BEA-1 are such that Si(x) = Si(x) for almost all input x in F210. For instance, S0(x)=S0(x)for all except 80 elements x in F210. 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 S0 compared to the original secret S-box S0. More generally, Si and Si have 80 different images for i in {0,1,2}. The last-modified S-box S3 is less close to it secret equivalent since S3 and S3 have 99 different images.

Consequently, if x is uniformly distributed over F210, then the equality Si(x) = Si(x) holds with probability qi where

q0=q1=q2=9441024andq3=9251024.E86

This implies that when x is uniformly distributed over (F210)8, the images of x under the secret and the modified substitution layers are equal with probability q=(i=03qi)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]=Fk[i](p[i])is equal to p[i+1]=Fk[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 q11. 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 F25. In order to have an explicit construction of this field, we consider the irreducible polynomial X5 + X2 + 1 over F2and define F25as the quotient ring F2[X]/(X5+X2+1). Let α denote the equivalence class of X in F25. By construction, the equality α5+α2+1=0holds, or equivalently, α5=α2+1. Each element of F25can hence be uniquely written as i=04xiαiwhere (x4,…, x0) belongs to F25. More precisely, the family (αi)i<5is a basis of F25seen as a 5-dimensional vector space over F2. The field F25will then be identified with (F2)5via the isomorphism from F25to F25mapping (x4,…, x0) to i=04xiαi. For instance, the element α2 + α + 1 in F25is identified with 07 in F25. Now define the 4 × 4 matrices MU and MV over F25by

It can be verified that these matrices are MDS. In other words, the [8, 4]-linear code having G=[Id4,MU]as generator matrix has minimal distance equals to 5, which is the maximum achievable.

Each of these matrices naturally induces an automorphism of (F25)4and hence of (F210)4. For instance, MU maps the element x=(x0,x1,x2,x3)to x × MU. Observe that we chose to see elements of (F210)4as 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=(00,02,00,00)of (F210)4under the automorphism induced by MU. First, x is identified with the element (0, α, 0, 0) of (F25)4. Then,

(0,α,0,0)×MU=(α(α4+α3+α2+α+1),α(α4+α2),α(α4+α2+1),α(α3+α2))=(α5+α4+α3+α2+α,α5+α3,α5+α3+α,α4+α3)=(α4+α3+α+1,α3+α2+1,α3+α2+α+1,α4+α3).E88

Therefore, (00,02,00,00)×MU=(1B,0D,0F,18).▴

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

M:(F210)4(F210)4(uivi)i<4(ρ(u)iτu(v)i)i<4E89

where ρ(u)=u×MUand τu(v)=v×MV+PUV(u). The strength of this construction is that M′ inherits the linear and differential branch numbers of MU and MV, as stated in the proposition hereunder. But first, we introduce the following example.

Example 4.9. Let us compute the image of x=(000,070,000,000)under M′. As a first step, observe that x can be written as

x=(0000,0310,0000,0000)=(uivi)i<4,E90

where u=(00,03,00,00)and v=(00,10,00,00). Let e9=(00,02,00,00)and e10=(00,01,00,00). Then u=e9+e10, it is indeed its decomposition over the standard basis of (F25)4. Thus, for any linear mapping L, it holds that L(u)=L(e9)+L(e10). The image of u under ρ can hence be computed by

ρ(u)=ρ(e9)+ρ(e10)=(1B,0D,0F,18)+(1F,14,15,0C)=(04,19,1A,14).E91

In the same way,

τu(v)=v×MV+PUV(e9)+PUV(e10)=(16,0E,14,02)+(0F,11,0C,16)+(11,0E,02,0A)=(08,11,1A,1E).E92

Consequently, M(x)=(0408,1911,1A1A,141E)=(088,331,35A,29E).▴

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=(uivi)i<4be a nonzero element of (F210)4. In order to prove that the differential branch number of M′ is equal to 5, we need to show that w10(x)+w10(M(x))is greater than or equal to 5. First, assume that u=(ui)i<4is nonzero. Using the fact that MU is MDS, we obtain the inequality w5(u)+w5(u×MU)5. Next,

5w5(u)+w5(ρ(u))=w10((ui0)i<4)+w10((ρ(u)i0)i<4)w10((uivi)i<4)+w10((ρ((u)iτu(v)i)i<4)=w10(x)+w10(M(x)).E93

Now, suppose that u = 0. It must be the case that v ≠ 0 as x is nonzero by definition. Again, it holds that w5(v)+w5(v×MV)5because MV is also MDS. Then,

5w5(v)+w5(τ0(v))=w10((0vi)i<4)+w10((0τ0(v)i)i<4)=w10(x)+w10(M(x)).E94

We have proven that w10(x)+w10(M(x))5for any nonzero element x of (F210)4. Consequently, the differential branch number of M′ is greater than or equal to 5. The equality BD(M)=5follows 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 {05}×F25and that the linear mappings LViand LWi(see Figure 1A) map respectively L({0*})to L(Vi)and L({0*})to L(Wi). It is then easily seen that M′ maps {0*}4 to itself. Thus, M′ preserves the partition L({0*}4)by Proposition 2.15. Finally, define

M=(LV0LV1LV2LV3)M(LW0LW1LW2LW3)1.E95

From its definition, it is straightforward to check that M maps the linear partition L(i=03Wi)to L(i=03Vi).

Example 4.11. We are going to compute M(000,080,000,000). First, we have that

(LW0LW1LW2LW3)1(000,080,000,000)=(LW01(000),LW11(080),LW21(000),LW31(000))=(000,070,000,000).E96

Then, the image of (000,070,000,000)under M′ is (088,331,35A,29E), as already established in Example 4.9. Finally,

M(000,080,000,000)=(LV0LV1LV2LV3)(088,331,35A,29E)=(15E,0BF,1E2,04F).E97

Indeed, LV0(088)=LV0(080)+LV0(008)=21D+343=15E. The three other bundles are computed in the same manner.▴

Because each mapping LVior LWioperates 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 L(i=03Wi)to L(i=03Vi).

In conclusion, Proposition 2.13 ensures that any key addition preserves all the linear partitions, and hence it preserves L(V). Next, it has been proven in Section 2.2 that every secret S-box Si maps L(Vi)to L(Wi). Thus, the secret substitution layer maps L(V)to L(W). It is clear that theShiftRowsoperation is linear and maps W to itself. According to Proposition 2.15, this mapping preserves L(W). Finally, theMixColumnoperation maps L(W)to 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 F26. Then, consider the subspaces V and W of F26defined by

V=span(01,02,10,20)={(x3,x2,0,0,x1,x0)|xF24},W=span(01,02,04,10)={(0,x3,0,x2,x1,x0)|xF24}.E98

Thus, L(V)={x+V|x{00,04,08,0C}}and L(W)={y+W|y{00,08,20,28}}.

Let S be the permutation of F26given in Figure 4.4. We defined another permutation S of F26satisfying S(x) = S(x) for any input x in F26except00, 01, 04, 05, 08, 09, 0Cand0D. 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

Fk:F26F26Fk:F26F26xS(x)+k,xS(x)+k,E99

representing respectively the secret and the modified round functions. Naturally, the key k can be any element of F26.

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

S(00+V)=08+W,S(08+V)=00+W,S(04+V)=28+W,S(0C+V)=20+W.E100

In contrast with the secret permutation S, the modified S-box S does not map L(V)to L(W). However, the equality S(x) = S(x) holds with probability 56/64assuming that x is uniformly distributed over F26. This can be stated equivalently as

#{xF26|S(x)=S(x)}=268=56.E101

It should also be noted that this statement remains valid when considering their inverse mappings, that is #{yF26|S1(y)=S1(y)}=56. Indeed, if x is an element of F26such that S(x) = S(x), then y = S(x) satisfies the equality S−1(x) = S−1(y). As a consequence,

#{xF26|S(x)=S(x)}#{yF26|S1(y)=S1(y)}.E102

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

Now, consider the subset Pof F26defined hereinafter. We assume that the round key is k =37. The image of Punder S and its encryption with F37 are given below.

It should be stressed that the coset04+ V is significantly more represented in Pthan any other coset of V. Since F37(P)maps the linear partition L(V)to 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 F37(P)has also ten elements.

As we have seen above, the modified round function F37does not map L(V)to L(W). Figure 4.5 displays the differences between the encryption of Pwith F37and its encryption with F37by highlighting the messages x in P such that S(x) ≠ S(x) (that is04, 05, and0D) and their images throughout the encryption.

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

Needless to say, there are also eight messages in F37(Q)lying in the same coset of W because the key addition preserves L(W).

We focus now to the set Pas a whole. According to the discussion above, we know that the most represented coset of W in F37(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 message0D, as illustrated in Figure 4.5. Consequently, the most represented coset in F37(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 C=F37(P)of encrypted messages. First, we have to determine the most represented coset in C. In our example, this coset is08+ W with nine messages, and u =08is one of its representatives.

Now, assume that k is the round key used to encrypt C. We need to find the coset of V which is mapped to u + W by the secret round function Fk. According to Lemma 2.8, Fk maps t + V to Fk(t) + W. A representative of this coset of V is then t = S−1(u + k). Finally, the score of the guessed key k is the number of messages Fk1(c)=S1(c+k)that belong to the theoretical coset t + V, that is to say

score(k)=#{cC|S1(c+k)(t+V)}.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 Pand the coset t+V=34+V=04+Vwhen using the right key. Thus, the score of k =37is equal to 10. In the same way, the score of k =07is the number of decrypted messages in the coset t+V=32+V=00+V, so score(07)=8.

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−1(x) = S−1(x) holds with probability 56/64. The most represented coset after the addition of the wrong key should then lose some elements by applying S−1. 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.

#### 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 Ccontaining the encrypted messages under the unknown key, given by

C={04,05,06,0D,0F,15,16,17,18,22,27,34,35,36,3A}.E104

Naturally, Cis included in the set c=F26of all possible ciphertexts. Similarly, the set of all possible round keys is denoted by k=F26. Next, define the keyed mapping

G:k×cF26(k,c)S1(c+k).E105

Each mapping Gk:cG(k,c)is the inverse of the round function Fk. The secret counterpart of G is G:(k,c)S1(c+k). Observe that for each round key k, the mapping Gk maps L(W)to L(V). It is also necessary to know the most represented coset u + W in 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 Kof k.

More generally, the parameters can be outlined as follows.

• The sets of all possible keys and ciphertexts are referred to as kand c.

• The keyed mapping G:k×cEtypically undoes (or partially undoes) one or two rounds of the encryption process.

• Its secret counterpart is denoted by G:k×cE. It is assumed that Gk maps a linear partition L(W)to another partition L(V)no matter the key k used.

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

• It is assumed that there is a coset of W containing significantly more ciphertexts than any other coset. The element u of cis a representative of this coset.

• Finally,NbCandis the number of candidate keys to return.

Remark 4.13. Taking a closer look at Algorithm 3, we can see that the structureCandrequires an efficient way to remove the lowest scored key. In our implementation,Candis 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 inCandis (almost) in constant time. Removing the lowest scored key is also in constant time. Thus, the time complexity of this cryptanalysis is O(#K×#C).

### 4. Cryptanalysis of BEA-1 using the backdoor

The algorithmSelectKeys(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 = 216 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 algorithmSelectKeysto find 215 candidates for the full 80-bit last round key k[11]. Next, relying on a property of the key schedule,SelectKeysis applied to these 215 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 215 candidates for the 40 remaining bits. Finally, deduce the 215 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 Pdenote the set of the 216 plaintexts uniformly chosen in one coset of V and let C={EK(p)|pP}denote the set of their ciphertexts. As said previously, we first need to find the most represented coset of W in C. Let Ui be the subspace of F210defined by Ui=LWi({*0})for each 0 ≤ i < 3. Since {*0} is a complement space of {0*} and LWiis an automorphism, we know that Ui is a complement space of LWi({0*})=Wi. Define U as the subspace i=07Uimod4of (F210)8. Of course, U is a complement space of W.

Let c be a ciphertext and u=(ui)i<8be 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, ci and ui are in the same coset of Wimod4 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 tablesRepWi such that, for each x in F210, RepWi[x]gives the representative in Ui of x + Wi. These tables are just arrays of 1024 integers. Then, the representative of c=(ci)i<8is just u=(RepWimod4[ci])i<8.

To find the most represented coset of W in 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 215 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 216 ciphertexts and 280 possible values of k[11], yielding an order of 296 time complexity.

To solve this problem, the 215 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 S3, being the most different from its secret equivalent. Following the notations ofSelectKeys, the set containing the ciphertexts is C{3,7}={(c3,c7)|cC}, and the set of the keys is K{3,7}={(k3,k7)|k3,k7F210}. The mapping used to partially decrypt the last round of these ciphertexts is

G{3,7}:(F210)2×(F210)2(F210)2((k3,k7),(c3,c7))(S31(c3+k3),S31(c7+k7)).E106

Its secret equivalent G{3,7} is obtained by replacing S3 with S3. The two remaining inputs of the algorithm are the representative u = (u3, u7) of the most represented coset of (W3)2, and the subspace (V3)2 of (F210)2. It is worth observing that G{3,7} maps L((W3)2)to L((V3)2)as required by the algorithm. RunningSelectKeyswith these arguments generates a setCandcontaining 215 candidates for (k3[11],k7[11])instead of 220.

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 k0[11], the set of the possible values for (ki[11])iEis

KE={(ki)iE|k0F210,(k3,k7)Cand}.E107

Following the idea of the first step, we define CE={(ci)iE|(ci)i<8C}and

GE:(F210)E×(F210)E(F210)E((ki)iE,(ci)iE)(Simod41(ci+ki))iE.E108

Then, define GE by replacing Si with Si and let VE denote the subspace iEVimod4of (F210)E. The setCandobtained by runningSelectKeyswith these parameters contains 215 candidates for (k0[11],k3[11],k7[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 S3, then S0, S1 and finally S2. The current indices are in the set E={0,3,4,7}. Similarly, we define

KE={(ki)iE|k4F210,(k0,k3,k7)Cand}E109

to include the information on k[11] gathered by the previous step. Finally, define CE, GE, GE and VE as above. Again, the algorithmSelectKeysyields 215 candidates for (ki[11])iE.

This time, let us take a closer look at the implementation of this step. Because #KE=225and #CE=216, a straightforward implementation ofSelectKeysrequires 241 partial round decryptions, as explained by Remark 4.13. Algorithm 5 provides our implementation ofSelectKeysfor this step. As we can see, the previous candidates are used to filter the ciphertexts before attacking k4 by brute force. For each of the 215 candidates, initializing the filter requires 216 partial decryptions. On average, it remains roughly 26 ciphertexts after the filtering process. The loop over k4 hence requires 216 partial decryptions. Consequently, this implementation performs about 232 partial decryptions instead of 241.

Naturally, the 215 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 215 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]=(k0[9],,k7[9])corresponds with (k0,,k7),

• k[10]=(k0[10],,k7[10])corresponds with (k8,,k15),

• k[11]=(k0[11],,k7[11])corresponds with (k16,,k23).

It is then easily seen that

(k0[10],k1[10],k2[10],k3[10])=(k0[11],k1[11],k2[11],k3[11])+(k4[11],k5[11],k6[11],k7[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 algorithmSelectKeysis 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

G:(F210)8×(F210){0,2,5,7}(F210)4((ki)i<8,(ci)i{0,2,5,7})(S01(c0+k0)+k0+k4,S11(c5+k5)+k1+k5,S21(c2+k2)+k2+k6,S31(c7+k7)+k3+k7).E111

Then, let G be the mapping from (F210)8×(F210){0,2,5,7}to (F210)4given by

G=(S0S1S2S3)1M1G.E112

Define G in the same way as before and let V=i=03Vi. Finally,run Selectkeysas 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 215 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 algorithmSelectKeys, 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−1. 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 (ki[10])4i<8. This fourth part intends to find 215 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 (F210)4and observe that

M(x)+k=M(x)+M(M1(k))=M(x+M1(k))=M(x+k)E113

where k=M1(k). Thus, the key addition and the mapping M can be switched provided that the key is replaced. According to this observation, define

(ki[10])4i<8=M1((ki[10])4i<8).E114

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

Thanks to this representation, candidates for the key (ki[10])4i<8can be obtained usingSelectKeysas in Part 2. To this end, we first need to partially undo the last round using k[11]. Following Figure 4.10, define

f:(F210){1,3,4,6}(F210)4(ci)i{1,3,4,6}M1(S01(c4+k4[11]),S11(c1+k1[11]),S21(c6+k6[11]),S31(c3+k3[11])).E115

The set {f((ci)i{1,3,4,6})|cC}of these “new” ciphertexts is denoted by C, and the corresponding coset representative is u=f((ui)i{1,3,4,6}). To be more consistent with Figure 4.10, the bundles of u′ and of the elements of Care 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 ofSelectKeysare the set CE={(ci)iE|(ci)4i<8C}, the mapping

GE:(F210)E×(F210)E(F210)E((ki)iE,(ci)iE)(Simod41(ci+ki))iE,E116

its equivalent GE and the subspace VE=iEVimod4of (F210)E. The other details are given in Algorithm 4. At the end of this part, every candidate k=(ki)4i<8for (ki[10])4i<8gives rise to a candidate k=M(k)for (ki[10])4i<8.

#### 4.5. Part 5: deducing the cipher key

Concatenating the candidates for (ki[10])4i<8with k[11] yields 215 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 (X0, X1, X2) of (F240)3to (Y0, Y1, Y2) according to the following equalities

Y0=X0+fi(X2),Y1=Y0+X1,Y2=Y1+X2,E117

where fi denotes the permutation of (F210)4defined for each X by

fi(X)=(3imod210,0,0,0)+(S0S1S2S3)M(X).E118

Using these notations, it easily seen that

X0=Y0+fi(Y1+Y2),X1=Y0+Y1,X2=Y1+Y2.E119

These equalities describe how to reverse each round of the key schedule, and thus how to recover the 215 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 Aof the plaintexts to a partition Bof 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 (A,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 Sdenote 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 Sas follows

min{#Supp(τ)|τS(F2n),SτS}.E120

This represents the minimal number of images under S we have to modify in order to obtain an S-box lying in 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 216 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.

## More

© 2017 The Author(s). Licensee IntechOpen. This compact is distributed under the terms of the Creative Commons Attribution-NonCommercial 4.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited.

## How to cite and reference

### Cite this compact Copy to clipboard

Arnaud Bannier and Eric Filiol (September 7th 2017). Partition-Based Trapdoor Ciphers, Partition-Based Trapdoor Ciphers, Arnaud Bannier and Eric Filiol, IntechOpen, DOI: 10.5772/intechopen.70420. Available from:

### Related Content

#### Partition-Based Trapdoor Ciphers

Authored by Arnaud Bannier

Next compact

#### Partition-Based Trapdoor Ciphers

By Arnaud Bannier and Eric Filiol

#### Advanced Technologies of Quantum Key Distribution

Authored by Sergiy Gnatyuk

First chapter

#### Security of Quantum Key Distribution Protocols

By Mhlambululi Mafu and Makhamisa Senekane

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

View all books