# Impossible Differential Distinguishers of Two Generalized Feistel Structures

Authors: Huili Wang; Wenping Ma; Lang Liao; Yushan Li; Linfeng Zheng
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Generalized Feistel structures are widely used in the design of block ciphers. In this paper, we focused on retrieving impossible differentials for two kinds of generalized Feistel structures: CAST256-like structure with Substitution-Permutation (SP) or Substitution-Permutation-Substitution (SPS) round functions (namedCAST256SP and CAST256SPS, respectively) and MARS-like structure with SP/SPS round function (named MARSSP and MARSSPS, respectively). Known results show that for bijective round function, CAST256-like structures and MARS-like structures have (m2−1) and (2m−1) rounds impossible differentials, respectively. By our observation, there existed (m2+m) rounds impossible differentials in CAST256SP and (3m−3) rounds impossible differentials in MARSSPS (this result does not require the P layer to be invertible). When the diffusion layer satisfied some special conditions, CAST256SPS had (m2+m−1) rounds impossible differentials and MARSSPS had (3m−3) rounds impossible differentials.


---

## Body

## 1. Introduction

The architecture is one of the most important parts of a block cipher. It will directly affect the implementation performance and the round number. Among them, SP structure [1], Feistel structure [2], and generalized Feistel structure [3] are the most often used architectures. The SP structure is a simple and clear block cipher model which is designed to implement Shannon’s suggestions of confusion and diffusion. This architecture was adopted by the famous block cipher AES [1]. Besides, many block ciphers, including Camellia, E2, and CLEFIA [4–6] adopt such kind of round functions. Except for the SP structure, the Feistel structure is another important structure, and there are a lot of block ciphers employing this architecture, such as DES, GOST, E2, and Camellia [2, 4, 6, 7]. In [3], Nyberg first introduced generalized Feistel structures. The generalized Feistel structures are generalized forms of the classical Feistel cipher. These structures reserve some advantages of the classical Feistel cipher such as encryption-decryption similarity and flexibility in the design of round functions. A large number of ciphers like CAST256, MARS, CLEFIA [5, 8, 9], etc. use these structures as their architectures.Impossible differential cryptanalysis was first proposed by Knudsen [10] and Biham et al. [11]. This cryptanalysis uses impossible differentials to discard the wrong keys. This cryptanalysis has been used to attack Skipjack, AES, Camellia, ARIA [11–14], etc. and get many good results. The key step of impossible differential cryptanalysis is to find the longest impossible differentials [15]. For generalized Feistel structures, since only part of the data was processed in each round, there always exist long rounds impossible differentials, and this makes these ciphers vulnerable to impossible differential cryptanalysis.Since the powerful efficiencies of impossible differential cryptanalysis, many experts work on finding impossible differential distinguisher for several block cipher structures, and lots of remarkable results are achieved. In [16], u-method was provided by Kim et al. to find impossible differentials of block ciphers structures and was later extended by Bouillaguet et al. [17]; this method uses the inconsistencies of the elements in set u to find impossible differentials. It is worthwhile for the declaration that several longest impossible differentials of some famous block cipher structures are obtained by this method. As is mentioned in [16], for m-dataline CAST256-like structure and m-dataline MARS-like structure, existed the longest round number of impossible differentials are m2 and 2m respectively. However, u-method is too general and some important longer impossible differentials are ignored [12], and the longest differential distinguishers of several architectures like GF-NLFSR [18, 19], Feistel ciphers [15], SPN [20], and MISTY [21] are obtained by other methods. In [22], a new automatic method was proposed to find more impossible differentials.It is well known that nonzero linear combinations of several linearly independent vectors cannot be zero. Based on this matter of fact, we present some new inconsistencies to construct impossible distinguishers of CAST256-like structures and MARS-like structures with SP and SPS round function. To our knowledge, the best result is m-dataline CAST256-like cipher hasm2 rounds impossible differential distinguisher and m-dataline MARS-like cipher has 2m rounds impossible differential distinguisher. Our results show that for m-dataline CAST256SP and CAST256SPS, there exists (m2+m−1) rounds impossible differential distinguishers and for MARSSP and MARSSPS, there exists (3m−3) rounds impossible differential distinguishers.This paper is organized as follows: Section2 introduces some preliminaries. Section 3 focuses on finding impossible differential distinguisher of m-dataline CAST256-like structures with SP/SPS round function. Section 4 works on finding impossible differential distinguisher of m-dataline MARS-like structures with SP/SPS round function. Section 5 concludes this paper.


## 2. Guidelines for Manuscript Preparation

Throughout this paper, we will use the symbols, described in Table1.Table 1
Symbols.
⊕XOR operationΔxThe XOR difference ofx and x′ωXThe number of nonzero components of vectorXΔfΔxThe output difference off when the given input difference is Δx|Matrices concatenationg°fxComposition of functionf and g, i.e., gfxMiThei-th column of matrix M=Mi,jn×nei1,…,irVector with nonzero values only in thei1,…,ir-th components0n-dimension zero vectorUUncertain differenceIt is well known that iff is a linear bijection, then ΔfΔx=fΔx, else ΔfΔx may have several possible values; in this case, we can choose any one for further discussion, and we will use ΔfiΔx to distinguish them.Next, we will first describe these two structures, and then lay out some basic definitions and notations.


### 2.1. CAST256-like Structure

Anm-dataline CAST256-like network consists of r rounds, each round is defined as follows.LetX1i−1,X2i−1,…,Xmi−1 be the input of the i-th round, X1i,X2i,…,Xmi and ki be the output and the round key of the -th round, respi=1,2,….X1i,…,Xmi=RoundCAST256X1i−1,…,Xmi−1 is defined as(1)X1i=Xmi−1,Xj+1i=Xji−1,1≤j≤m−1;Xmi=Fki,Xmi−1⊕Xm−1i−1,where F is the round function (Figure 1 describes one round of 4-dataline CAST256-like network).Figure 1
One round of 4-dataline CAST256-like structure.


### 2.2. Mars-like Structure

Anm-daaline MARS-like network consists of r rounds; each round is defined as follows.LetX1i−1,X2i−1,…,Xmi−1 be the input of the i-th round, X1i,X2i,…,Xmi and ki be the output and the round key of the -th round, respi=1,2,….X1i,…,Xmi=RoundMARSX1i−1,…,Xmi−1 is defined as(2)Xji=Fki,X1i−1⊕Xj+1i−1,1≤j≤m−1;Xmi=X1i−1,where F is the round function (Figure 2 describes one round of 4-dataline CAST256-like network).Figure 2
One round of 4-dataline MARS-like structure.


### 2.3. Notations

According to the definition of round functionf, these two cipher structures can be classified into many substructures. Major round functions under study are based on SP structure and SPS structure, which are two basic structures of modern ciphers.Definition 1 (See [1]) (SP network).
LetS1,…,Sn:0,1d⟶0,1dbe nonlinear bijections, P(3)0,1nd⟶0,1ndbe a linear transformation (there is no limit that P is a bijection), k=k1,…,kn∈0,1nd is the round key, then the round function Roundsp(4)0,1nd×0,1nd⟶0,1nd,of SP network (SPN) is defined by(5)RoundSPx,k=PS1x1⊕k1,…,Snxn⊕kn.
We useCAST256SP (resp. CAST256SPS) to denote CAST256-like structure with SP(resp. SPS) type round function and MARSSP (resp. MARSSPS ) for MARS-like structure with SP(resp. SPS) type round function.Definition 2 (See [15]).
(χ−function) χ:F2dn⟶F2n is defined as(6)χx1,…,xn=θx1,…,θxnwhere θ:F2d⟶F2 is defined by(7)θx=1,ifx≠0;0,ifx=0.
LetX=x1,…,xn, function χs:F2dn⟶F2 is defined by χSX=θxS.Definition 3φ−function.
Let1≤r≤n; then φr:F2dn⟶F2d is defined as φrx1,…,xn=xr.Definition 4 (See [1]) (differential branch number).
Letfx=Mx be a linear mapping, where M is a matrix over GF2d. Then the differential branch number of f is defined by(8)Brf=minx≠0wx+wM×x.


## 2.1. CAST256-like Structure

Anm-dataline CAST256-like network consists of r rounds, each round is defined as follows.LetX1i−1,X2i−1,…,Xmi−1 be the input of the i-th round, X1i,X2i,…,Xmi and ki be the output and the round key of the -th round, respi=1,2,….X1i,…,Xmi=RoundCAST256X1i−1,…,Xmi−1 is defined as(1)X1i=Xmi−1,Xj+1i=Xji−1,1≤j≤m−1;Xmi=Fki,Xmi−1⊕Xm−1i−1,where F is the round function (Figure 1 describes one round of 4-dataline CAST256-like network).Figure 1
One round of 4-dataline CAST256-like structure.


## 2.2. Mars-like Structure

Anm-daaline MARS-like network consists of r rounds; each round is defined as follows.LetX1i−1,X2i−1,…,Xmi−1 be the input of the i-th round, X1i,X2i,…,Xmi and ki be the output and the round key of the -th round, respi=1,2,….X1i,…,Xmi=RoundMARSX1i−1,…,Xmi−1 is defined as(2)Xji=Fki,X1i−1⊕Xj+1i−1,1≤j≤m−1;Xmi=X1i−1,where F is the round function (Figure 2 describes one round of 4-dataline CAST256-like network).Figure 2
One round of 4-dataline MARS-like structure.


## 2.3. Notations

According to the definition of round functionf, these two cipher structures can be classified into many substructures. Major round functions under study are based on SP structure and SPS structure, which are two basic structures of modern ciphers.Definition 1 (See [1]) (SP network).
LetS1,…,Sn:0,1d⟶0,1dbe nonlinear bijections, P(3)0,1nd⟶0,1ndbe a linear transformation (there is no limit that P is a bijection), k=k1,…,kn∈0,1nd is the round key, then the round function Roundsp(4)0,1nd×0,1nd⟶0,1nd,of SP network (SPN) is defined by(5)RoundSPx,k=PS1x1⊕k1,…,Snxn⊕kn.
We useCAST256SP (resp. CAST256SPS) to denote CAST256-like structure with SP(resp. SPS) type round function and MARSSP (resp. MARSSPS ) for MARS-like structure with SP(resp. SPS) type round function.Definition 2 (See [15]).
(χ−function) χ:F2dn⟶F2n is defined as(6)χx1,…,xn=θx1,…,θxnwhere θ:F2d⟶F2 is defined by(7)θx=1,ifx≠0;0,ifx=0.
LetX=x1,…,xn, function χs:F2dn⟶F2 is defined by χSX=θxS.Definition 3φ−function.
Let1≤r≤n; then φr:F2dn⟶F2d is defined as φrx1,…,xn=xr.Definition 4 (See [1]) (differential branch number).
Letfx=Mx be a linear mapping, where M is a matrix over GF2d. Then the differential branch number of f is defined by(8)Brf=minx≠0wx+wM×x.


## 3. Impossible Differential Distinguishers of Cast256-like Structure

### 3.1. Two Important Differential Characteristics of CAST256-like Structure

Lemma 1 (See [23]).
For them-dataline CAST256-like structure, any nontrivial differential characteristic of the round function must be with the following form:(9)ΔX1i,…,ΔXm−1i,ΔXmi⟶ΔXmi,ΔX1i,…,ΔXm−2i,Δy⊕Xm−1i.AndΔy denotes the output difference of the round function. From Lemma 1, we have.Proposition 1.
LetΔX be one round differential characteristic of m-dataline CAST256-like structure, then the following equations hold with probability 1.(1)
ΔXki=ΔXk−1i−1 for 2≤k≤m−1(2)
ΔX1i=ΔXmi−1(3)
ΔXmi−1=ΔFΔXmi−1⊕ΔXm−1i−1Proposition1 can be verified directly from Lemma 1. In the following, we concentrate on two special differences which will help us to find the impossible differentials.Observation 1.
Let1≤k0≤m−2 and ΔX1i−1,…,ΔXmi−1⟶ΔX1i,…,ΔXmi be the same as in the previous observation, if ΔXki−1=O,k≠k0α,k=k0, then(10)ΔXki=O,k≠k0+1,α,k=k0+1.Observation 2.
Let1≤k0≤m−2 and ΔX1i+m,…,ΔXmi+m be the output difference of the i+m round, if ΔXji+m=O,j≤k0;U,k0≤j≤m−2;Δ,j=m−1;α,j=m., then(11)ΔXji=O,j≤k0−1;U,k0−1≤j≤m−2;Δ⊕ΔFα,j=m−1;α,j=m.
We can conclude the following Lemma.Lemma 2.
For them-dataline CAST256-like structure, there exists a rounds differential characteristic(12)α,O,…,O⟶2m−1−roundU,…,U,ΔF2α,ΔFα,U⟶1−roundU,…,U,ΔF2α,U.from encryption direction and an mm−1 rounds differential characteristic(13)U,…,U,⊕m−1k=1ΔFkα,α⟵mm−1−roundO,…,O,α,from the decryption direction, both with probability 1.Proof.
If the input difference is chosen asΔX10,…,ΔXm0=α,O,…,O, according to Observation 1,(14)ΔX1m−2,…,ΔXmm−2=O,…,O,α,O.
Applying Proposition1 repeatedly, the following equations must hold(15)ΔXm−1m−1=ΔXm−2m−2=O,ΔXmm−1=ΔFΔXmm−2⊕ΔXm−1m−2=α,ΔXm−1m=ΔXm−2m−1=ΔXm−3m−2=O,ΔXmm=ΔFΔXmm−1⊕ΔXm−1m−1=ΔFα.
Then we arrive to(16)ΔX1m+2=ΔXmm+1=ΔFΔXmm⊕ΔXm−1m=ΔF2α,ΔXm−12m−1=ΔX1m+1=ΔFα,ΔXm−22m−1=ΔXm−12m=ΔX1m+2=ΔF2α,which implies the differential(17)α,O,…,O⟶2m−1−roundU,…,U,ΔF2α,ΔFα,U⟶1−roundU,…,U,ΔF2α,Uexists.
From the decryption direction, if the output difference is set asO,…,O,α, then by Observation 2, after m rounds decryption, the input difference (from the encryption direction) is O,…,O,ΔFα,α, and applying Observation 2m−2 times, we may clarify this Lemma (in Tables 2 and 3, we listed the whole procedure).Table 2
(2m−1) rounds differential characteristics of the m-dataline CAST256-like structure from the encryption direction.
Round/output diff↓αOO…OOtextbf01OαO…OO……m−1OOO…OαmαOO…OΔFαm+1ΔFααO…OΔF2α……2m−1UUU…ΔFαα2mUUU…ΔF2αUTable 3
mm−1 rounds differential characteristics of the m-dataline CAST256-like structure from the decryption direction.
1UUU…⊕k=1m−1ΔFkαα2αUU…U⊕k=1m−2ΔFkα……mm−3+1OOO…⊕k=12ΔFkαα……mm−2+1OOO…ΔF1αα……mm−1OOO…αORound/input diff↑OOOOα


### 3.2. Impossible Differentials for CAST256-like Structure with SP/SPS Round Function

Theorem 1.
AssumeA is the permutation layer of CAST256SP, where A is a n×n matrix over GF2d. Let Ω1=i1,…,ix, Ω2=j1,…,jy⊆1,2,…,n, if Ai1,…,Aix, Aj1,…,Ajy are linearly independent, then for any n-dimension vector eΩ1, eΩ2,(18)eΩ1,O,…,O⟶O,…,O,eΩ2is an m2+m−1 rounds impossible differential of CAST256SP.Proof.
According to Lemma2, we have ΔXm−12m−1=ΔFΩ1=ΔP°SeΩ1 from the encryption direction and ΔXm−12m−1=⊕k=1m−1ΔFkΩ2=⊕k=1m−1ΔP°SkΩ2 from the decryption direction.
By the definition ofeΩ1, we get(19)ΔP°SeΩ1=ΔPΔSeΩ1=⊕xu=1φuΔSeΩ1×Aiu.
Similarly,(20)⊕m−1k=1ΔP°SeΩ2=⊕m−1k=1ΔPΔSkeΩ2=P⊕m−1k=1ΔSkeΩ2=A×⊕m−1k=1ΔSkeΩ2=⊕yv=1φv⊕m−1k=1ΔSkeΩ2×Ajv.
SinceAi1,…,Aix, Aj1,…,Ajy are linearly independent and ΔSeiu≠0, we have(21)⊕xu=1φuΔSeΩ×Aiu⊕⊕yv=1φv⊕m−1k=1ΔSkeΩ2×Ajv≠0.
This indicatesΔP°SeΩ1≠⊕k=1m−1ΔP°SkeΩ2, which means eΩ1,O,…,O⟶O,…,O,eΩ2 is an (m2+m−1) rounds impossible differential of CAST256SP.
For most designs of permutation layer, we can easily find thesei1,…,ix, j1,…,jy, which satisfy the condition of Theorem 1.Corollary 1.
AssumeA is the diffusion layer of CAST256SP, if A is a n×n invertible matrix, Ω1=i1,…,ix, j1,…,jy⊆1,2,…,n and Ω1∩Ω2=∅, then for any n-dimension vector eΩ1, eΩ2, eΩ1,O,…,O⟶O,…,O,eΩ2 is an (m2+m−1) rounds impossible differential of CAST256SP.By considering the2m rounds differential proposed in Lemma 2, we can find an m2+m round impossible differential. And the result is concluded as follows.Theorem 2.
Assumen×n matrix A is the permutation layer of CAST256SP and BrA>2, then for any n-dimension vector α, if wα=1, then α,O,…,O⟶O,O,…,α is an (m2+m) rounds impossible differential of CAST256SP.Proof.
Let the input and output difference of (m2+m−1) rounds CAST256SP be α,O,…,O and O,…,O,α, respectively. By Lemma 2, we can conclude that from the encryption direction, the difference of the 2nd left most branch of 2m round is ΔP°S°P°Sα, while from the decryption direction, this difference is ⊕k=1m−1ΔP°Skα.
If differentialα,O,…,O⟵mm−1−roundO,…,O,α is possible, then equation is possible; then equation(22)ΔP°S°P°Sα⊕⊕m−1k=1ΔP°Skα=A×ΔS°P°Sα⊕⊕k=1m−1ΔSkα=0is possible.
Since for any1≤k≤m−1, χΔSkα=χα, so w⊕k=1m−1ΔSkα is at most 1. We also notice wΔS°P°Sα≥BrA−wΔsα>1; thus, ΔS°P°Sα⊕⊕k=1m−1ΔSkα, which means that α,O,…,O⟶O,O,…,α is an (m2+m) rounds impossible differential.
ForCAST256SPS, we have similar results.Theorem 3.
Assumen×n matrix A is the diffusion layer of CAST256SPS, if A has entry “0”, then there exists (m2+m−1) rounds impossible differentials of CAST256SPS.Proof.
Without loss of generality, we can assume that there exists1≤i,l,j≤n, such that Al,i≠0 and Al,i=0. Let the input and output difference of (m2+m−1) rounds CAST256SPS be ei,O,…,O and O,…,O,ej, respectively. Since ΔXm−12m−1=ΔFei=⊕k=1m−1ΔFkej and F=S°P°S, we have(23)ΔS°P°Sei=ΔSΔPΔSei=ΔSA×ΔSei=ΔSφiΔSei×Ai,⊕m−1k=1ΔS°P°Skej=⊕m−1k=1ΔSkφjΔSkej×Aj.
ForAl,i≠0, we have χlAi≠0, since S layer are parallel bijections and φiei≠0, we may obtain φiΔSei≠0, so χφiΔSei×Ai=χAi. And for χlAi≠0, we have(24)χlφiΔSei×Ai=χlAi=1,so we conclude(25)χlΔS°P°Sei=χlΔSφiΔSei×Ai=χlφiΔSei×Ai=1.
ForAl,i=0, we have χlAi=0, which implies χlφjΔSkej×Aj=0; thus, the two equations below hold:(26)χlΔSkφjΔSkej×Aj=0,χl⊕m−1k=1ΔSkφjΔSkej×Aj=0.
This meansΔXm−12m−1=ΔS°P°Sei≠⊕k=1m−1ΔS°P°Sej=ΔXm−12m−1, which leads contradiction. This implies ei,O,…,O⟶O,…O,ej is an (m2+m−1) rounds impossible differential of CAST256SPS.
Now we consider a special case, when permutation layer is designed as a binary matrix.Corollary 2.
AssumeA is the permutation layer of CAST256SPS, where A is a n×n binary matrix with rankA≥2; then for some 1≤i,j≤n, there exists (m2+m−1) rounds impossible differential ei,O,…,O⟶O,…O,ej, where rankA denotes the rank of matrix A.Proof.
SincerankA≥2, we know there exist some 1≤i,j,l≤n, such that Ai≠Aj and Al,i≠Al,j. This means Al,i=1Al,j=0 or Al,i=0Al,j=1. Thus, by Theorem 3, we can conclude the result.
Corollary2 indicates that for binary permutation layer, if its rank exceeds 2, then we can find such impossible differentials. Obviously, this condition is compatible for almost every design.


## 3.1. Two Important Differential Characteristics of CAST256-like Structure

Lemma 1 (See [23]).
For them-dataline CAST256-like structure, any nontrivial differential characteristic of the round function must be with the following form:(9)ΔX1i,…,ΔXm−1i,ΔXmi⟶ΔXmi,ΔX1i,…,ΔXm−2i,Δy⊕Xm−1i.AndΔy denotes the output difference of the round function. From Lemma 1, we have.Proposition 1.
LetΔX be one round differential characteristic of m-dataline CAST256-like structure, then the following equations hold with probability 1.(1)
ΔXki=ΔXk−1i−1 for 2≤k≤m−1(2)
ΔX1i=ΔXmi−1(3)
ΔXmi−1=ΔFΔXmi−1⊕ΔXm−1i−1Proposition1 can be verified directly from Lemma 1. In the following, we concentrate on two special differences which will help us to find the impossible differentials.Observation 1.
Let1≤k0≤m−2 and ΔX1i−1,…,ΔXmi−1⟶ΔX1i,…,ΔXmi be the same as in the previous observation, if ΔXki−1=O,k≠k0α,k=k0, then(10)ΔXki=O,k≠k0+1,α,k=k0+1.Observation 2.
Let1≤k0≤m−2 and ΔX1i+m,…,ΔXmi+m be the output difference of the i+m round, if ΔXji+m=O,j≤k0;U,k0≤j≤m−2;Δ,j=m−1;α,j=m., then(11)ΔXji=O,j≤k0−1;U,k0−1≤j≤m−2;Δ⊕ΔFα,j=m−1;α,j=m.
We can conclude the following Lemma.Lemma 2.
For them-dataline CAST256-like structure, there exists a rounds differential characteristic(12)α,O,…,O⟶2m−1−roundU,…,U,ΔF2α,ΔFα,U⟶1−roundU,…,U,ΔF2α,U.from encryption direction and an mm−1 rounds differential characteristic(13)U,…,U,⊕m−1k=1ΔFkα,α⟵mm−1−roundO,…,O,α,from the decryption direction, both with probability 1.Proof.
If the input difference is chosen asΔX10,…,ΔXm0=α,O,…,O, according to Observation 1,(14)ΔX1m−2,…,ΔXmm−2=O,…,O,α,O.
Applying Proposition1 repeatedly, the following equations must hold(15)ΔXm−1m−1=ΔXm−2m−2=O,ΔXmm−1=ΔFΔXmm−2⊕ΔXm−1m−2=α,ΔXm−1m=ΔXm−2m−1=ΔXm−3m−2=O,ΔXmm=ΔFΔXmm−1⊕ΔXm−1m−1=ΔFα.
Then we arrive to(16)ΔX1m+2=ΔXmm+1=ΔFΔXmm⊕ΔXm−1m=ΔF2α,ΔXm−12m−1=ΔX1m+1=ΔFα,ΔXm−22m−1=ΔXm−12m=ΔX1m+2=ΔF2α,which implies the differential(17)α,O,…,O⟶2m−1−roundU,…,U,ΔF2α,ΔFα,U⟶1−roundU,…,U,ΔF2α,Uexists.
From the decryption direction, if the output difference is set asO,…,O,α, then by Observation 2, after m rounds decryption, the input difference (from the encryption direction) is O,…,O,ΔFα,α, and applying Observation 2m−2 times, we may clarify this Lemma (in Tables 2 and 3, we listed the whole procedure).Table 2
(2m−1) rounds differential characteristics of the m-dataline CAST256-like structure from the encryption direction.
Round/output diff↓αOO…OOtextbf01OαO…OO……m−1OOO…OαmαOO…OΔFαm+1ΔFααO…OΔF2α……2m−1UUU…ΔFαα2mUUU…ΔF2αUTable 3
mm−1 rounds differential characteristics of the m-dataline CAST256-like structure from the decryption direction.
1UUU…⊕k=1m−1ΔFkαα2αUU…U⊕k=1m−2ΔFkα……mm−3+1OOO…⊕k=12ΔFkαα……mm−2+1OOO…ΔF1αα……mm−1OOO…αORound/input diff↑OOOOα


## 3.2. Impossible Differentials for CAST256-like Structure with SP/SPS Round Function

Theorem 1.
AssumeA is the permutation layer of CAST256SP, where A is a n×n matrix over GF2d. Let Ω1=i1,…,ix, Ω2=j1,…,jy⊆1,2,…,n, if Ai1,…,Aix, Aj1,…,Ajy are linearly independent, then for any n-dimension vector eΩ1, eΩ2,(18)eΩ1,O,…,O⟶O,…,O,eΩ2is an m2+m−1 rounds impossible differential of CAST256SP.Proof.
According to Lemma2, we have ΔXm−12m−1=ΔFΩ1=ΔP°SeΩ1 from the encryption direction and ΔXm−12m−1=⊕k=1m−1ΔFkΩ2=⊕k=1m−1ΔP°SkΩ2 from the decryption direction.
By the definition ofeΩ1, we get(19)ΔP°SeΩ1=ΔPΔSeΩ1=⊕xu=1φuΔSeΩ1×Aiu.
Similarly,(20)⊕m−1k=1ΔP°SeΩ2=⊕m−1k=1ΔPΔSkeΩ2=P⊕m−1k=1ΔSkeΩ2=A×⊕m−1k=1ΔSkeΩ2=⊕yv=1φv⊕m−1k=1ΔSkeΩ2×Ajv.
SinceAi1,…,Aix, Aj1,…,Ajy are linearly independent and ΔSeiu≠0, we have(21)⊕xu=1φuΔSeΩ×Aiu⊕⊕yv=1φv⊕m−1k=1ΔSkeΩ2×Ajv≠0.
This indicatesΔP°SeΩ1≠⊕k=1m−1ΔP°SkeΩ2, which means eΩ1,O,…,O⟶O,…,O,eΩ2 is an (m2+m−1) rounds impossible differential of CAST256SP.
For most designs of permutation layer, we can easily find thesei1,…,ix, j1,…,jy, which satisfy the condition of Theorem 1.Corollary 1.
AssumeA is the diffusion layer of CAST256SP, if A is a n×n invertible matrix, Ω1=i1,…,ix, j1,…,jy⊆1,2,…,n and Ω1∩Ω2=∅, then for any n-dimension vector eΩ1, eΩ2, eΩ1,O,…,O⟶O,…,O,eΩ2 is an (m2+m−1) rounds impossible differential of CAST256SP.By considering the2m rounds differential proposed in Lemma 2, we can find an m2+m round impossible differential. And the result is concluded as follows.Theorem 2.
Assumen×n matrix A is the permutation layer of CAST256SP and BrA>2, then for any n-dimension vector α, if wα=1, then α,O,…,O⟶O,O,…,α is an (m2+m) rounds impossible differential of CAST256SP.Proof.
Let the input and output difference of (m2+m−1) rounds CAST256SP be α,O,…,O and O,…,O,α, respectively. By Lemma 2, we can conclude that from the encryption direction, the difference of the 2nd left most branch of 2m round is ΔP°S°P°Sα, while from the decryption direction, this difference is ⊕k=1m−1ΔP°Skα.
If differentialα,O,…,O⟵mm−1−roundO,…,O,α is possible, then equation is possible; then equation(22)ΔP°S°P°Sα⊕⊕m−1k=1ΔP°Skα=A×ΔS°P°Sα⊕⊕k=1m−1ΔSkα=0is possible.
Since for any1≤k≤m−1, χΔSkα=χα, so w⊕k=1m−1ΔSkα is at most 1. We also notice wΔS°P°Sα≥BrA−wΔsα>1; thus, ΔS°P°Sα⊕⊕k=1m−1ΔSkα, which means that α,O,…,O⟶O,O,…,α is an (m2+m) rounds impossible differential.
ForCAST256SPS, we have similar results.Theorem 3.
Assumen×n matrix A is the diffusion layer of CAST256SPS, if A has entry “0”, then there exists (m2+m−1) rounds impossible differentials of CAST256SPS.Proof.
Without loss of generality, we can assume that there exists1≤i,l,j≤n, such that Al,i≠0 and Al,i=0. Let the input and output difference of (m2+m−1) rounds CAST256SPS be ei,O,…,O and O,…,O,ej, respectively. Since ΔXm−12m−1=ΔFei=⊕k=1m−1ΔFkej and F=S°P°S, we have(23)ΔS°P°Sei=ΔSΔPΔSei=ΔSA×ΔSei=ΔSφiΔSei×Ai,⊕m−1k=1ΔS°P°Skej=⊕m−1k=1ΔSkφjΔSkej×Aj.
ForAl,i≠0, we have χlAi≠0, since S layer are parallel bijections and φiei≠0, we may obtain φiΔSei≠0, so χφiΔSei×Ai=χAi. And for χlAi≠0, we have(24)χlφiΔSei×Ai=χlAi=1,so we conclude(25)χlΔS°P°Sei=χlΔSφiΔSei×Ai=χlφiΔSei×Ai=1.
ForAl,i=0, we have χlAi=0, which implies χlφjΔSkej×Aj=0; thus, the two equations below hold:(26)χlΔSkφjΔSkej×Aj=0,χl⊕m−1k=1ΔSkφjΔSkej×Aj=0.
This meansΔXm−12m−1=ΔS°P°Sei≠⊕k=1m−1ΔS°P°Sej=ΔXm−12m−1, which leads contradiction. This implies ei,O,…,O⟶O,…O,ej is an (m2+m−1) rounds impossible differential of CAST256SPS.
Now we consider a special case, when permutation layer is designed as a binary matrix.Corollary 2.
AssumeA is the permutation layer of CAST256SPS, where A is a n×n binary matrix with rankA≥2; then for some 1≤i,j≤n, there exists (m2+m−1) rounds impossible differential ei,O,…,O⟶O,…O,ej, where rankA denotes the rank of matrix A.Proof.
SincerankA≥2, we know there exist some 1≤i,j,l≤n, such that Ai≠Aj and Al,i≠Al,j. This means Al,i=1Al,j=0 or Al,i=0Al,j=1. Thus, by Theorem 3, we can conclude the result.
Corollary2 indicates that for binary permutation layer, if its rank exceeds 2, then we can find such impossible differentials. Obviously, this condition is compatible for almost every design.


## 4. Impossible Differential Distinguishers of MARS-like Structure

### 4.1. Two Important Differential Characteristics of MARS-like Structure

The following lemma is trivial.Lemma 3.
For the m-dataline MARS-like cipher, any nontrivial differential characteristic of the round function must be with the formΔX1i,…,ΔXm−1i,ΔXmi⟶ΔX2i⊕Δy,…,ΔXmi⊕Δy,ΔX1i, and Δy denotes the output difference of the round function.
From Lemma3, we can verify the properties as below.Proposition 2.
LetΔX1i,…,ΔXm−1i,ΔXmi⟶ΔX2i⊕Δy,…,ΔXmi⊕Δy,ΔX1i be one round differential characteristic of m-dataline MARS-like structure, then we have(1)
ΔXji+1=ΔXj+1i⊕ΔFΔX1i for 1≤j≤m−1(2)
ΔXmi+1=ΔX1iObservation 3.
Let1≤r≤m−1, then for the m-dataline MARS-like structure, there exists the following 1 round differential characteristic with probability 1:(27)Δx,…,Δx,Δt1,…,Δtm−r⟶Δx⊕Δ,…,Δx⊕Δ,Δt1⊕Δ,…,Δtm−r⊕Δ,Δx,where Δ=ΔFΔx.Observation 4.
Let1≤k0≤m−1 and ΔX1i,…,ΔXmi⟶ΔX1i+1,…,ΔXmi+1 be the same as in the previous propositions; following this, if(28)ΔXki+1=O,k≠k0;α,k=k0,then(29)ΔXki=O,k≠k0+1;α,k=k0+1.
Based on these two Observations, we can conclude the Lemma below.Lemma 4.
For the m-dataline MARS-like structure, there exists a2m−3 rounds differential characteristic O,…,O,α⟶2m−3roundA,A,U,…,U,U from encryption direction and an m rounds differential characteristic α,ΔFα,ΔFα,…,ΔFα⟵mroundα,O,…,O from the decryption direction, both with probability 1, where denotes one fixed difference and denotes some uncertain difference(s).Proof.
LetΔX10,…,ΔXm0=O,…,O,α be the input difference, then according to Proposition 3, after (m−1) rounds cascade, the output difference is turned into ΔX1m−1,…,ΔXmm−1=α,O,…,O, then by Proposition 2, it holds ΔX1m=⋯=ΔXm−1m applying Proposition 3 recursively, we have ΔX12m−3=ΔX22m−3.
From the decryption direction, if the output difference is chosen asΔX1m,ΔX2m,…,ΔXmm=α,O,…,O, then by Observation 4, we have ΔX11,ΔX21,…,ΔXm1=O,…,O,α. According to Proposition 2, we may obtain ΔX10,ΔX20,…,ΔXm0=α,ΔFα,ΔFα,…,ΔFα (in Tables 4 and 5, we listed the whole procedure).Table 4
The (2m-3) rounds differential characteristics of the m-dataline MARS-like structure from the encryption directionΔi=ΔFΔi−1⊕Δi−1 for 1≤i≤m−1 and Δ0=Δ0=ΔFα.
Round/output diff↓OO…OαO1……m−1αO…OOOmΔ0Δ0…Δ0Δ0αm+1Δ1Δ1…Δ1UΔ0……2m−3Δm−3Δm−3…UUΔm−4Table 5
m rounds differential characteristics of the m-dataline MARS-like structure from the decryption direction.
1αΔFαΔFα…ΔFαΔFα…OOO…Oαm−1…mOαO…OORound/input diff↑αOOOO


### 4.2. Retrieving Impossible Differential for MARS-Like Structure with SP/SPS Round Function

Before we start this section, we will introduce the definition of collect set.Definition 5.
(collect set) Let M be an s×t matrix over GF2d, x=x1,…,xt is a binary vector. Then the collect setColx,M is defined as Colx,M=Mi:xi≠0,1≤i≤t, the characteristic function of Colx,M is defined as(30)ChColx,M=1,the vectors in Colx,Mare linearly independent;0,the vectors in Colx,Mare linearly dependent.
Thepattern of Colx,M is defined as(31)PatColx,M=χM×y:y=y1,…,ytT,yi∈GF2d,χy=x.Theorem 4.
Assumen×n matrix A over GF2d is the permutation layer of MARSSP, if there exists nonzero n-dimension vector Δx over GF2d such that ChColχΔxχΔx,AE=1 then 0,…,0,y⟶Δx,0,…,0 is a 3m−3 rounds impossible differential of MARSSP, where y represents any nonzero vector.Proof.
By Lemma4 we have(32)ΔX12m−3=Δx,ΔX22m−3=ΔP°SΔx=A×ΔSΔx,from the decryption direction.
We assumeA×ΔSΔx=Δx, then(33)AE×ΔSΔxΔx=0.
This indicatesColχΔSΔxχΔx,AE are linearly dependent, which is contradictory with ChColχΔxχΔx,AE=1. So A×ΔSΔx≠Δx, i.e., ΔX1i≠ΔX2i. However, by Lemma 4, we have from the encryption direction, and this leads to a contradiction. Thus O,…,O,y⟶Δx,O,…,O is an impossible differential of MARSSP.Corollary 3.
Assumen×n matrix A over GF2d is the permutation layer of MARSSP, if the branch number of A is BrA, then for any nonzero n-dimension vector Δx over such that wΔx<DA/2, then O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSP, where y represents any nonzero vector.Proof.
According to Definition4, for any wΔx<BrA/2, wA×ΔSΔx≥BrA−wΔx>BrA/2 which implies A×ΔSΔx≠Δx; thus, O,…,O,y⟶Δx,O,…,O is an impossible differential of MARSSP.Theorem 5.
Assumen×n matrix A over GF2d is the permutation layer of MARSSPS, if there exists nonzero n-dimension vector Δx over GF2d such that χΔx∉PatColχΔx,A then O,…,O,y⟶Δx,O,…,O is an 3m−3 rounds impossible differential of MARSSPS, where y represents any nonzero vector.Proof.
By Lemma4 we have,(34)ΔX1i=Δx,ΔX2i=ΔS°P°SΔx=ΔSA×ΔSΔx,from the decryption direction.
SinceχΔSA×ΔSΔx=χA×ΔSΔx∈PatColχΔx,A and χΔx∉PatColχΔx,A, we can conclude ΔX12m−3≠ΔX22m−3. Thus, O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSPS.
According to Theorem5, the case that the binary matrix employment is characterized as follows.Corollary 4.
Assumen×n binary matrix A is the diffusion layer of MARSSPS, if exists 1≤i1<i2≤n and 1≤j1<j2≤n, such that i1,i2≠j1,j2 and(35)Ai1,j1=0,Ai1,j2≠0,Ai2,j1≠0,Ai2,j2=0,then for any ej1,j2 and nonzero vector y,O,…,O,y⟶ej1,j2,O,…,O is a 3m−3 rounds impossible differential of MARSSPS.Proof.
We have(36)φiA×ΔSej1,j2=⊕nk=1Ai,k×φkΔSej1,j2=⊕k∈j1,j2Ai,k×φkΔSej1,j2.
Which tellsχi1ΔSA×ΔSΔx=χi2ΔSA×ΔSΔx=1. However, by the definition of ej1,j2, we have www and i1,i2≠j1,j2. Thus, χej1,j2∉PatColχej1,j2,A.
Compared with other designs, binary diffusion layer has an obvious advantage in implementation and thus is a very common design, and for this case, the conditions of Corollary4 are satiable for most of the time.
ForMARSSPS, we can tell that if ΔX13m−3,..,ΔXm3m−3=ΔX,O,…,O, then ΔX12m−3=Δx and ΔX22m−3=ΔS°P°SΔx. One can see ΔX12m−3=ΔX22m−3 can be represented by ΔSPΔSΔx=Δx. Notice wΔSPΔSΔx=wPΔSΔx, we can change “MARSSP” by “MARSSPS” in Corollary 3.Corollary 5.
Assumen×n matrix A over GF2d is the diffusion layer of MARSSPS, if the branch number of A is DA, then for any nonzero n-dimension vector Δx over GF2d such that wΔx<DA/2, then O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSPS, where y represents any nonzero n-dimension vector.


## 4.1. Two Important Differential Characteristics of MARS-like Structure

The following lemma is trivial.Lemma 3.
For the m-dataline MARS-like cipher, any nontrivial differential characteristic of the round function must be with the formΔX1i,…,ΔXm−1i,ΔXmi⟶ΔX2i⊕Δy,…,ΔXmi⊕Δy,ΔX1i, and Δy denotes the output difference of the round function.
From Lemma3, we can verify the properties as below.Proposition 2.
LetΔX1i,…,ΔXm−1i,ΔXmi⟶ΔX2i⊕Δy,…,ΔXmi⊕Δy,ΔX1i be one round differential characteristic of m-dataline MARS-like structure, then we have(1)
ΔXji+1=ΔXj+1i⊕ΔFΔX1i for 1≤j≤m−1(2)
ΔXmi+1=ΔX1iObservation 3.
Let1≤r≤m−1, then for the m-dataline MARS-like structure, there exists the following 1 round differential characteristic with probability 1:(27)Δx,…,Δx,Δt1,…,Δtm−r⟶Δx⊕Δ,…,Δx⊕Δ,Δt1⊕Δ,…,Δtm−r⊕Δ,Δx,where Δ=ΔFΔx.Observation 4.
Let1≤k0≤m−1 and ΔX1i,…,ΔXmi⟶ΔX1i+1,…,ΔXmi+1 be the same as in the previous propositions; following this, if(28)ΔXki+1=O,k≠k0;α,k=k0,then(29)ΔXki=O,k≠k0+1;α,k=k0+1.
Based on these two Observations, we can conclude the Lemma below.Lemma 4.
For the m-dataline MARS-like structure, there exists a2m−3 rounds differential characteristic O,…,O,α⟶2m−3roundA,A,U,…,U,U from encryption direction and an m rounds differential characteristic α,ΔFα,ΔFα,…,ΔFα⟵mroundα,O,…,O from the decryption direction, both with probability 1, where denotes one fixed difference and denotes some uncertain difference(s).Proof.
LetΔX10,…,ΔXm0=O,…,O,α be the input difference, then according to Proposition 3, after (m−1) rounds cascade, the output difference is turned into ΔX1m−1,…,ΔXmm−1=α,O,…,O, then by Proposition 2, it holds ΔX1m=⋯=ΔXm−1m applying Proposition 3 recursively, we have ΔX12m−3=ΔX22m−3.
From the decryption direction, if the output difference is chosen asΔX1m,ΔX2m,…,ΔXmm=α,O,…,O, then by Observation 4, we have ΔX11,ΔX21,…,ΔXm1=O,…,O,α. According to Proposition 2, we may obtain ΔX10,ΔX20,…,ΔXm0=α,ΔFα,ΔFα,…,ΔFα (in Tables 4 and 5, we listed the whole procedure).Table 4
The (2m-3) rounds differential characteristics of the m-dataline MARS-like structure from the encryption directionΔi=ΔFΔi−1⊕Δi−1 for 1≤i≤m−1 and Δ0=Δ0=ΔFα.
Round/output diff↓OO…OαO1……m−1αO…OOOmΔ0Δ0…Δ0Δ0αm+1Δ1Δ1…Δ1UΔ0……2m−3Δm−3Δm−3…UUΔm−4Table 5
m rounds differential characteristics of the m-dataline MARS-like structure from the decryption direction.
1αΔFαΔFα…ΔFαΔFα…OOO…Oαm−1…mOαO…OORound/input diff↑αOOOO


## 4.2. Retrieving Impossible Differential for MARS-Like Structure with SP/SPS Round Function

Before we start this section, we will introduce the definition of collect set.Definition 5.
(collect set) Let M be an s×t matrix over GF2d, x=x1,…,xt is a binary vector. Then the collect setColx,M is defined as Colx,M=Mi:xi≠0,1≤i≤t, the characteristic function of Colx,M is defined as(30)ChColx,M=1,the vectors in Colx,Mare linearly independent;0,the vectors in Colx,Mare linearly dependent.
Thepattern of Colx,M is defined as(31)PatColx,M=χM×y:y=y1,…,ytT,yi∈GF2d,χy=x.Theorem 4.
Assumen×n matrix A over GF2d is the permutation layer of MARSSP, if there exists nonzero n-dimension vector Δx over GF2d such that ChColχΔxχΔx,AE=1 then 0,…,0,y⟶Δx,0,…,0 is a 3m−3 rounds impossible differential of MARSSP, where y represents any nonzero vector.Proof.
By Lemma4 we have(32)ΔX12m−3=Δx,ΔX22m−3=ΔP°SΔx=A×ΔSΔx,from the decryption direction.
We assumeA×ΔSΔx=Δx, then(33)AE×ΔSΔxΔx=0.
This indicatesColχΔSΔxχΔx,AE are linearly dependent, which is contradictory with ChColχΔxχΔx,AE=1. So A×ΔSΔx≠Δx, i.e., ΔX1i≠ΔX2i. However, by Lemma 4, we have from the encryption direction, and this leads to a contradiction. Thus O,…,O,y⟶Δx,O,…,O is an impossible differential of MARSSP.Corollary 3.
Assumen×n matrix A over GF2d is the permutation layer of MARSSP, if the branch number of A is BrA, then for any nonzero n-dimension vector Δx over such that wΔx<DA/2, then O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSP, where y represents any nonzero vector.Proof.
According to Definition4, for any wΔx<BrA/2, wA×ΔSΔx≥BrA−wΔx>BrA/2 which implies A×ΔSΔx≠Δx; thus, O,…,O,y⟶Δx,O,…,O is an impossible differential of MARSSP.Theorem 5.
Assumen×n matrix A over GF2d is the permutation layer of MARSSPS, if there exists nonzero n-dimension vector Δx over GF2d such that χΔx∉PatColχΔx,A then O,…,O,y⟶Δx,O,…,O is an 3m−3 rounds impossible differential of MARSSPS, where y represents any nonzero vector.Proof.
By Lemma4 we have,(34)ΔX1i=Δx,ΔX2i=ΔS°P°SΔx=ΔSA×ΔSΔx,from the decryption direction.
SinceχΔSA×ΔSΔx=χA×ΔSΔx∈PatColχΔx,A and χΔx∉PatColχΔx,A, we can conclude ΔX12m−3≠ΔX22m−3. Thus, O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSPS.
According to Theorem5, the case that the binary matrix employment is characterized as follows.Corollary 4.
Assumen×n binary matrix A is the diffusion layer of MARSSPS, if exists 1≤i1<i2≤n and 1≤j1<j2≤n, such that i1,i2≠j1,j2 and(35)Ai1,j1=0,Ai1,j2≠0,Ai2,j1≠0,Ai2,j2=0,then for any ej1,j2 and nonzero vector y,O,…,O,y⟶ej1,j2,O,…,O is a 3m−3 rounds impossible differential of MARSSPS.Proof.
We have(36)φiA×ΔSej1,j2=⊕nk=1Ai,k×φkΔSej1,j2=⊕k∈j1,j2Ai,k×φkΔSej1,j2.
Which tellsχi1ΔSA×ΔSΔx=χi2ΔSA×ΔSΔx=1. However, by the definition of ej1,j2, we have www and i1,i2≠j1,j2. Thus, χej1,j2∉PatColχej1,j2,A.
Compared with other designs, binary diffusion layer has an obvious advantage in implementation and thus is a very common design, and for this case, the conditions of Corollary4 are satiable for most of the time.
ForMARSSPS, we can tell that if ΔX13m−3,..,ΔXm3m−3=ΔX,O,…,O, then ΔX12m−3=Δx and ΔX22m−3=ΔS°P°SΔx. One can see ΔX12m−3=ΔX22m−3 can be represented by ΔSPΔSΔx=Δx. Notice wΔSPΔSΔx=wPΔSΔx, we can change “MARSSP” by “MARSSPS” in Corollary 3.Corollary 5.
Assumen×n matrix A over GF2d is the diffusion layer of MARSSPS, if the branch number of A is DA, then for any nonzero n-dimension vector Δx over GF2d such that wΔx<DA/2, then O,…,O,y⟶Δx,O,…,O is a 3m−3 rounds impossible differential of MARSSPS, where y represents any nonzero n-dimension vector.


## 5. Conclusion

Generalized Feistel structures are of great importance in modern block cipher design. Evaluating the strength of these structures can help us in constructing a security cipher. Among all the cryptanalysis technologies, impossible differential cryptanalysis is one of the most powerful attacks. This paper provides an improvement in finding the longest impossible differentials for two generalized Feistel structures named the CAST256-like structure and the MARS-like structure.This paper bridges some links between impossible differentials and linear transformations. We provide some sufficient conditions on the linear transformations. By our results, people may find the possible longer impossible differentials by verifying some properties of the linear transformations. Thus, the properties we list in this paper should be considered carefully when using these two structures.



---

*Source: 8828504-2020-09-22.xml*