# Revisiting Impossible Differential Distinguishers of Two Generalized Feistel Structures

Authors: Xuan Shen; Lei Cheng; Bing Sun; Jun He
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Impossible differential attack is one of the most effective cryptanalytic methods for block ciphers. Its key step is to construct impossible differential distinguishers as long as possible. In this paper, we mainly focus on constructing longer impossible differential distinguishers for two kinds of generalized Feistel structures which arem-dataline CAST256-like and MARS-like structures. When their round function takes Substitution Permutation SP and Substitution Permutation Substitution SPS types, they are called CAST256SP/CAST256SPS and MARSSP/MARSSPS, respectively. For CAST256SP/CAST256SPS, the best known result for the length of the impossible differential distinguisher was m2+m/m2+m−1 rounds, respectively. With the help of the linear layer P, we can construct m2+m+Λ0/m2+m+Λ1-round impossible differential distinguishers, where Λ0 and Λ1 are non-negative numbers if P satisfies some restricted conditions. For MARSSPS, the best known result for the length of the impossible differential distinguisher was 3m−1 rounds. We can construct 3m-round impossible differential distinguishers which are 1 round longer than before. To our knowledge, the results in this paper are the best for the two kinds of generalized Feistel structures.


---

## Body

## 1. Introduction

Block ciphers are significant elements to construct symmetric cryptographic schemes. To design a block cipher, a proper structure needs to be selected carefully. Popular structures for designing block ciphers are Substitution Permutation Network (SPN) structures [1], Feistel structures [2], and generalized Feistel structures [3]. Since the encryption and decryption of generalized Feistel structures share the same round functions and similar structures, it makes the implementation more flexible and economical. Generalized Feistel structures have many types such as CAST256-like structure [4], MARS-like structure [5], and so on. At the same time, many famous block ciphers take generalized Feistel structures as their architectures, for example, CAST256 [6], MARS [7], and SMS4 [8].Many effective methods were proposed for evaluating the security of block ciphers in the past decades. Among them, impossible differential attack is one of the most effective methods. It was independently proposed by Knudsen [9] and Biham et al. [10]. So far, impossible differential attack has given exciting works for AES [11], Camellia [12], SMS4 [8], etc. Impossible differential attack has two steps. The first one is to construct an impossible differential distinguisher as long as possible. The second one is to exploit the distinguisher to recover the master key. Thus, constructing long impossible differentials is the core step to make this attack. So far, the most popular method to construct impossible differentials is the miss-in-the-middle method [10]. It obtains contradictions from the middle differences which are encrypted and decrypted with probability 1 for the input difference and the output difference, respectively. If the middle differences cannot be matched with each other, the impossible differential distinguisher is constructed. Moreover, some automatic methods were proposed to construct impossible differentials with the help of computers [13–16].As far as we know, many works paid attention to constructing impossible differential distinguishers ofm-dataline CAST256-like and MARS-like structures. For m-dataline CAST256-like structure, when the round function is any bijective transformation, m2-round impossible differentials were presented by the U method in [13]. Furthermore, when the round function takes SP type, 19/20-round impossible differentials of m=4-dataline CAST256-like structure were constructed in [17]. Very recently, when the round function takes SP type and SPS type, there existed m2+m/m2+m−1-round impossible differentials, respectively [18].Form-dataline MARS-like structure, when the round function is any bijective transformation, 2m−1-round impossible differentials were presented by the U method in [13]. This result was improved to 3m−1 rounds in [19]. Furthermore, when the round function takes SP type, 3m-round impossible differentials were found in [5]. Very recently, when the round function takes SPS type, 3m−3-round impossible differentials were constructed for some constrained linear layer P [18].Known results on impossible differentials ofm-dataline CAST256-like and MARS-like structures are presented in Table 1.Table 1
Known results on impossible differentials ofm-dataline CAST256-like and MARS-like structures.
CAST256SPCAST256SPSMARSSPSSourcem2m22m−1[13]——3m−1[19]19/20m=4——[17]m2+mm2+m−13m−3[18]m2+m+Λ0m2+m+Λ13mOurswhere R denotes the primitive index ofP and ∧0 = min{R − 2, m − 3}, ∧1 = min{R − 3, m − 3}.(1)Λ0=minR−2,m−3,Λ1=minR−3,m−3,In this paper, we mainly study the impossible differential distinguishers ofm-dataline CAST256-like and MARS-like structures. For these two structures, we construct longer impossible differential distinguishers with the details of the linear transformation P. Note that m≥4 and the linear transformation P is a bijective mapping throughout this paper. Moreover, R denotes the primitive index of P. Our contributions are presented below.(1)
Form-dataline CAST256-like structure, when the round function takes SP type (namely, CAST256SP), the previous best result was presented in [18]. They showed that m2+m-round impossible differentials were constructed for BP>2, where BP denotes the differential branch number of P. In this paper, we firstly remove the restricted condition and give m2+m-round impossible differentials for any bijective P. It expands the range of the linear layer P. Furthermore, if P satisfies the condition that R≥2, Λ0=minR−2,m−3-round impossible differentials are constructed. To satisfy the condition R≥2, some specific linear transformations P are also presented.(2)
Form-dataline CAST256-like structure, when the round function takes SPS type (namely, CAST256SPS), the previous best result was also presented in [18]. They showed that m2+m−1-round impossible differentials were constructed for R≥2. In this paper, if P satisfies some conditions, Λ1+1=minR−3,m−3+1-round impossible differentials are constructed. Moreover, some specific linear transformations P are presented for satisfying the restricted conditions.(3)
Form-dataline MARS-like structure, when the round function takes SPS type (namely, MARSSPS), the previous best result of MARSSPS was also presented in [19]. They showed that 3m−1-round impossible differentials were constructed with P satisfying the bijective condition. In this paper, if P has 0 element in the diagonal line, we can construct 3m-round impossible differentials which are 1 round longer than those in [19].This paper is organized as follows. In Section2, we give some notations and definitions that will be used in this paper. Then, with the help of P, we construct longer impossible differential distinguishers of m-dataline CAST256-like and MARS-like structures in Sections 3 and 4, respectively. Finally, Section 5 concludes this paper.


## 2. Preliminary

### 2.1. Notations

In this section, we give some notations used in this paper (Table2). Note that all vectors used in our paper are column vectors and X0 is the most significant element for a vector X=X0,X1,…,Xn−2,Xn−1, where Xi is defined by the i-th element of X.Table 2
Notations used in this paper.
⊕XOR operationΔXTwo vectors make XOR operation, i.e.,X⊕X′G°FXComposition of functionF and G, i.e., GFXMiThei-th column of matrix M=Mi,jn×nΟn-Dimension zero vector?Uncertainn-dimension difference valueeiOnly thei-th element of vector e is nonzero and the others are zeroet˜Thet-th element of vector e is zero and the others are arbitrary valuesΔFΔXThe output difference ofF when the given input difference is ΔXIt should be pointed out that whenF is a nonlinear bijective function, ΔFΔX has many possible output difference values when the input difference ΔX≠O. Thus, if some ΔFΔX XORed each other, take ΔFlΔX to distinguish them, where l≥1. For example,(2)ΔFΔX⊕ΔFΔX=ΔF1ΔX⊕ΔF2ΔX=⊕l=12ΔFlΔX.In addition, similar to the definition ofΔFΔX, ΔFtΔX is defined by the output difference that ΔX propagates after continuous t rounds of F.


### 2.2. Definitions

Definition 1.
(SP networks) (see [1]). Let S0,…,Sn−1:0,1d⟶0,1d be nonlinear bijections, P:F2dn⟶F2dn be the bijective linear layer, and k=k0,k1,…,kn−1∈0,1nd be the round key. Then, the round function RoundSP:0,1nd×0,1nd⟶0,1nd is defined by(3)RoundSPx,k=P°Sx⊕k=PS0x0⊕k0,…,Sn−1xn−1⊕kn−1.
Similarly, the round functionRoundSPS is defined by(4)RoundSPSx,k=S°P°Sx⊕k.
In this paper, the round functions ofm-dataline CAST256-like and MARS-like structures take SP type and SPS type.Definition 2.
(Hamming weight) (see [20]). Let x be an n-dimension vector, and the Hamming weight of x is defined by(5)Hx=#i|xi≠0,i=0,1,…,n−1.
According to the definition,Hx=0 is equivalent to x=O. It implies that Hx≥1 when x≠O. Furthermore, Hx=1 is equivalent to x=ei for some i.Definition 3.
(differential branch number) (see [1]). Let fx=Mx be a linear mapping, where M is a matrix over GF2d. Then, the differential branch number of f is defined by(6)Bf=minx≠OHx+HMx.
Note that iff is a bijective linear mapping, according to the definition, Bf≥2.Definition 4.
(characteristic matrix) (see [20]). For P=pi,j∈F2dn×n, denote Z as the integer ring, and the characteristic matrix of P is defined as P∗=pi,j∗∈Zn×n, where(7)pi,j∗=0,pi,j=0,1,pi,j≠0.
According to the definition of characteristic matrix, for an SPN cipher,pi,j∗=0 means that the i-th output block of one-round function is independent of the j-th input block. Generally, let P∗t=qi,jn×n; then, qi,j=0 means that the i-th output block of the t-round SPN cipher is independent of the j-th input block.
For a matrixM, M>0 means that all elements of M are positive.Definition 5.
(primitive index of linear transformation) (see [20]). The primitive index of the linear transformation P is defined as(8)R=mint|P∗t>0,t∈Z+.
According to the above definition, ifR≥2, there exists at least one 0 element in P∗t for 1≤t≤R−1.


## 2.1. Notations

In this section, we give some notations used in this paper (Table2). Note that all vectors used in our paper are column vectors and X0 is the most significant element for a vector X=X0,X1,…,Xn−2,Xn−1, where Xi is defined by the i-th element of X.Table 2
Notations used in this paper.
⊕XOR operationΔXTwo vectors make XOR operation, i.e.,X⊕X′G°FXComposition of functionF and G, i.e., GFXMiThei-th column of matrix M=Mi,jn×nΟn-Dimension zero vector?Uncertainn-dimension difference valueeiOnly thei-th element of vector e is nonzero and the others are zeroet˜Thet-th element of vector e is zero and the others are arbitrary valuesΔFΔXThe output difference ofF when the given input difference is ΔXIt should be pointed out that whenF is a nonlinear bijective function, ΔFΔX has many possible output difference values when the input difference ΔX≠O. Thus, if some ΔFΔX XORed each other, take ΔFlΔX to distinguish them, where l≥1. For example,(2)ΔFΔX⊕ΔFΔX=ΔF1ΔX⊕ΔF2ΔX=⊕l=12ΔFlΔX.In addition, similar to the definition ofΔFΔX, ΔFtΔX is defined by the output difference that ΔX propagates after continuous t rounds of F.


## 2.2. Definitions

Definition 1.
(SP networks) (see [1]). Let S0,…,Sn−1:0,1d⟶0,1d be nonlinear bijections, P:F2dn⟶F2dn be the bijective linear layer, and k=k0,k1,…,kn−1∈0,1nd be the round key. Then, the round function RoundSP:0,1nd×0,1nd⟶0,1nd is defined by(3)RoundSPx,k=P°Sx⊕k=PS0x0⊕k0,…,Sn−1xn−1⊕kn−1.
Similarly, the round functionRoundSPS is defined by(4)RoundSPSx,k=S°P°Sx⊕k.
In this paper, the round functions ofm-dataline CAST256-like and MARS-like structures take SP type and SPS type.Definition 2.
(Hamming weight) (see [20]). Let x be an n-dimension vector, and the Hamming weight of x is defined by(5)Hx=#i|xi≠0,i=0,1,…,n−1.
According to the definition,Hx=0 is equivalent to x=O. It implies that Hx≥1 when x≠O. Furthermore, Hx=1 is equivalent to x=ei for some i.Definition 3.
(differential branch number) (see [1]). Let fx=Mx be a linear mapping, where M is a matrix over GF2d. Then, the differential branch number of f is defined by(6)Bf=minx≠OHx+HMx.
Note that iff is a bijective linear mapping, according to the definition, Bf≥2.Definition 4.
(characteristic matrix) (see [20]). For P=pi,j∈F2dn×n, denote Z as the integer ring, and the characteristic matrix of P is defined as P∗=pi,j∗∈Zn×n, where(7)pi,j∗=0,pi,j=0,1,pi,j≠0.
According to the definition of characteristic matrix, for an SPN cipher,pi,j∗=0 means that the i-th output block of one-round function is independent of the j-th input block. Generally, let P∗t=qi,jn×n; then, qi,j=0 means that the i-th output block of the t-round SPN cipher is independent of the j-th input block.
For a matrixM, M>0 means that all elements of M are positive.Definition 5.
(primitive index of linear transformation) (see [20]). The primitive index of the linear transformation P is defined as(8)R=mint|P∗t>0,t∈Z+.
According to the above definition, ifR≥2, there exists at least one 0 element in P∗t for 1≤t≤R−1.


## 3. Revisiting Impossible Differential Distinguishers ofm-Dataline CAST256-Like Structure

In this section, the brief description ofm-dataline CAST256-like structure is first presented. Moreover, the differential propagation rules are investigated from the encryption and decryption directions. Furthermore, when the round function takes SP type and SPS type, respectively, longer impossible differential distinguishers will be constructed for some linear layers P.


### 3.1.m-Dataline CAST256-Like Structure

Anm-dataline CAST256-like structure consists of r rounds, and each round is depicted in Figure 1. Let X0i−1,X1i−1,…,Xm−1i−1 be the input of the i-th round and X0i,X1i,…,Xm−1i and Ki−1 be the output and the round key of the i-th round, respectively. One-round encryption is defined by(9)X0i=Xm−1i−1,Xji=Xj−1i−1,1≤j≤m−2,Xm−1i=FXm−1i−1⊕Ki−1⊕Xm−2i−1,where F is the round function and Xji−1∈F2dn,0≤j≤m−1,i≥1.Figure 1
One-round encryption ofm-dataline CAST256-like structure.To construct impossible differentials, one-round differential propagations from the encryption and decryption directions need to be studied. They are described as follows.Proposition 1.
LetΔXi−1 and ΔXi be the i-th round input difference and output difference of m-dataline CAST256-like structure. From the encryption direction, one-round differential propagation is given below:(10)ΔX0i=ΔXm−1i−1,ΔXji=ΔXj−1i−1,1≤j≤m−2,ΔXm−1i=ΔFΔXm−1i−1⊕ΔXm−2i−1.
From the decryption direction, one-round differential propagation is given below:(11)ΔXji−1=ΔXj+1i,0≤j≤m−3,ΔXm−2i−1=ΔFΔX0i⊕ΔXm−1i,ΔXm−1i−1=ΔX0i.
According to the encryption process ofm-dataline CAST256-like structure, the above proposition can be proved. In the encryption direction, the input difference α,O,O,…,O,Oα∈F2dn,α≠O is encrypted 3m−3 rounds with probability 1 as described in Table 3. Moreover, in the decryption direction, the output difference O,O,…,O,O,ββ∈F2dn,β≠O is decrypted mm−1 rounds with probability 1. The differential characteristic is given in Table 4.
From Tables3 and 4, the following proposition can be obtained.Table 3
3m−3-round differential characteristic of m-dataline CAST256-like structure from the encryption direction.
RoundαOO⋯OO1OαO⋯OO2OOα⋯OO⋮⋮⋮⋮⋮⋮⋮m−1OOO⋯OαmαOO⋯OΔFαm+1ΔFααO⋯OΔF2α⋮⋮⋮⋮⋮⋮⋮2m−1ΔFm−1αΔFm−2αΔFm−3α⋯ΔFα?2m?ΔFm−1αΔFm−2α⋯ΔF2α?2m+1??ΔFm−1α⋯ΔF3α?⋮⋮⋮⋮⋮⋮⋮3m−3???⋯ΔFm−1α?Table 4
mm−1-round differential characteristic of m-dataline CAST256-like structure from the decryption direction.
RoundOOO⋯Oβ1OOO⋯βO2OO⋯βOO⋮⋮⋮⋮⋮⋮⋮m−1βOO⋯OOmOO⋯OΔFββ⋮⋮⋮⋮⋮⋮⋮2mOO⋯O⊕l=12ΔFlββ⋮⋮⋮⋮⋮⋮⋮3mOO⋯O⊕l=13ΔFlββ⋮⋮⋮⋮⋮⋮⋮mm−1??⋯?⊕l=1m−1ΔFlββProposition 2.
Form-dataline CAST256-like structure, after encrypting 2m+r0≤r≤m−3 rounds with the input difference α,O,O,…,O,O, the following differential holds with probability 1:(12)α,O,O,…,O,O⟶2m+r?,?,?,…,?,?,ΔFr+2α,?.
Likewise, after decryptingmm−1 rounds with the output difference O,O,…,O,O,β, the following differential holds with probability 1:(13)O,O,…,O,O,β⟶mm−1?,?,…,?,?,⊕l=1m−1ΔFlβ,β.


### 3.2. Constructing Impossible Differential Distinguishers ofm-Dataline CAST256-Like Structure with SP-Type Round Function

When the round functionF of m-dataline CAST-like structure is made up of SP type, we exploit the details of the linear layer P to construct longer impossible differential distinguishers. Firstly, two lemmas are presented as follows.Lemma 1.
IfG is a bijective mapping, ΔGα=O if and only if α=Δ.
SinceG is bijective, according to the bijective property, Lemma 1 can be easily proved. It also means that α≠O, ΔGα≠O. Especially, for S layer in SP type and SPS type which is a nonlinear bijective mapping, it does not change the nonzero difference positions for the differential propagation according to Lemma 1. It also implies that HΔSα=Hα.Lemma 2.
ForS layer in SP type and SPS type, if t≥1 and(14)⊕l=1tΔSlei≠O,the equation ⊕l=1tΔSlei=ei holds.Proof.
Firstly, we recall the definition ofei. It denotes that only the i-th element of n-dimension vector e is nonzero and the others are zero. According to Lemma 1 and ⊕l=1tΔSlei≠O,(15)⊕l=1tΔSlei=ei.
According to Lemma2, for Hα=1⇔α=ei, when ⊕l=1tΔSlα≠O, the following equation holds:(16)H⊕l=1tΔSlα=Hα=1.Theorem 1.
Form-dataline CAST256-like structure with SP-type round function, if Hα=Hβ=1, we can construct m2+m-round impossible differential distinguishers for any bijective linear layer P as follows:(17)α,O,O,…,O,O⟶m2+mO,O,…,O,O,β.Proof.
From the encryption and decryption directions, the differential with the inputα,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible, the following equation must hold:(18)ΔF2α=⊕l=1m−1ΔFlβ.
TakingF=P∘S into consideration, the above equation becomes(19)ΔP∘S∘P∘Sα=⊕l=1m−1ΔP∘Slβ.
SinceP is a linear bijective mapping,(20)PΔS∘P∘Sα=P⊕l=1m−1ΔSlβ⇔ΔS∘P∘Sα=⊕l=1m−1ΔSlβ.
For the left part of equation (20),(21)HΔS∘P∘Sα=HΔP∘Sα≥BP−HΔSα.
SinceHΔSα=Hα=1 and BP≥2,(22)HΔS∘P∘Sα≥BP−HΔSα=BP−Hα≥1.Case 1: whenHΔS∘P∘Sα>1, note that H⊕l=1m−1ΔSlβ=Hβ=1 according to Lemma 2, and the left and right parts of equation (20) have different Hamming weights. So, equation (20) does not hold.Case 2: whenHΔS∘P∘Sα=1, assume that ΔS∘P∘Sα=et. Take β=ej, where j≠t. According to Lemma 2, ⊕l=1m−1ΔSlβ=ej≠et. The left and right parts of equation (20) could not match each other. So, equation (20) does not hold.
Therefore, combined with the above two cases, equation (20) does not hold. It means that the middle differences could not match each other, and the 2m+mm−1=m2+m-round differential is impossible.
In [18], m2+m-round impossible differential distinguishers were also constructed, but the linear layer P is restricted to that satisfying the condition BP>2. However, in Theorem 1, the restricted condition of P is removed and it is expanded to any bijective linear layer.
To construct longer impossible differential distinguishers, we need to exploit the details of the linear layerP. When the primitive index of the linear layer P satisfies R≥2, the following theorem is given.Theorem 2.
Form-dataline CAST256-like structure with SP-type round function, if R≥2 and Hα=Hβ=1, L-round impossible differential distinguishers α,O,O,…,O,O⟶O,O,…,O,O,β could be constructed, where(23)L=m2+m+minR−2,m−3.Proof.
To prove this theorem, we compareR with m−1 for two cases.Case 1: when2≤R≤m−1, minR−2,m−3=R−2. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m+R−2 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(24)ΔFRα=⊕l=1m−1ΔFlβ.TakingF=P∘S into consideration, the above equation becomes(25)ΔP∘S∘⋯∘P∘S︸Rα=⊕l=1m−1ΔP∘Slβ.SinceP is a linear bijective mapping,(26)ΔS∘P∘S∘⋯∘P∘S︸R−1α=⊕l=1m−1ΔSlβ.In the left part of equation (26), there exists at least one 0 element in the matrix P∗R−1=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯∘P∘S︸R−1α must be 0.In the right part of equation (26), since Hβ=1, we take β=ei. According to Lemma 2., ⊕l=1m−1ΔSlβ=ei. So, the i-th element of ⊕l=1m−1ΔSlβ is not equal to 0.Therefore, equation (26) cannot hold. In this case, we can construct 2m+R−2+mm−1=m2+m+R−2-round impossible differential distinguishers.Case 2: whenR>m−1, minR−2,m−3=m−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 3m−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(27)ΔFm−1α=⊕l=1m−1ΔFlβ.TakingF=P∘S into consideration, the above equation becomes(28)ΔP∘S∘⋯∘P∘S︸m−1α=⊕l=1m−1ΔP∘Slβ.SinceP is a linear bijective mapping,(29)ΔS∘P∘S∘⋯∘P∘S︸m−2α=⊕l=1m−1ΔSlβ.In the left part of equation (29), since R>m−1, there exists at least one 0 element in the matrix P∗m−2=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯∘P∘S︸m−2α must be 0.In the right part of equation (29), it is similar to Case 1. Thus, if we take β=ei, the i-th element of ⊕l=1m−1ΔSlβ is not equal to 0.Therefore, equation (29) does not hold. In this case, we can construct 3m−3+mm−1=m2+2m−3-round impossible differential distinguishers.
Combined with the above two cases, we can constructL-round impossible differential distinguishers, where(30)L=m2+m+R−2,2≤R≤m−1,m2+m+m−3,R>m−1.
It is equivalent toL=m2+m+minR−2,m−3.
In [18], m2+m-round impossible differential distinguishers were constructed. According to Theorem 2, we can construct m2+m+minR−2,m−3-round impossible differentials which are Λ0=minR−2,m−3 rounds longer than before. The restricted condition R≥2 can be satisfied easily. We present some specific linear transformations P satisfying the condition. For example, we first present MC of Skinny block cipher [21] below:(31)PMC=1011100001101010.
With the definition ofR, we calculate R=3 for PMC. According to Theorem 2, if the linear transformation P takes PMC and m≥4, Λ0=minR−2,m−3=1. Therefore, we can construct m2+m+1-round impossible differential distinguishers for m-dataline CAST256-like structure with SP-type round function. They are Λ0=1 round longer than those in [18]. Moreover, we present another example. For the linear transformation of Skinny block cipher which is SR∘MC, it is given below:(32)PSkinny=10 0 0 0 0 0 0 0 010 010 0010 0 0 0 0 0 0 0 010 0100 010 0 0 0 010 0 0 0 0 010 0 010 0 0 0 010 010 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0010 0 0 0 0 0 0 0 0 0 0 0 0 00 010 0 0 0 0 0 0 0 0 0 0 0 00 0 010 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 010 010 0 0 0 00 0 0 010 0 0 0 0 010 0 0 00 0 0 0 010 010 0 0 0 0 0 00 0 0 0 0 010 010 0 0 0 0 010 0 0 0 0 0 0 0 010 0 0 0 0010 0 0 0 0 0 0 0 010 0 0 00 010 0 0 0 010 0 0 0 0 0 00 0 010 0 0 0 010 0 0 0 0 016×16.
We calculateR=6 for PSkinny. According to Theorem 2, if the linear transformation P takes PSkinny and m≥7, Λ0=minR−2,m−3=4. Therefore, we can construct m2+m+4-round impossible differential distinguishers. They are Λ0=4 rounds longer than those in [18].
In brief, combined with Theorem1 and Theorem 2, for m-dataline CAST256-like structure with SP-type round function, the results on the impossible differential distinguishers have been improved. Especially, when R>2, we can construct longer impossible differentials.


### 3.3. Constructing Impossible Differential Distinguishers ofm-Dataline CAST256-Like Structure with SPS-Type Round Function

Form-dataline CAST256-like structure with SPS-type round function, m2+m−1-round impossible differential distinguishers were constructed for R≥2 [18]. In this section, we will construct longer impossible differential distinguishers with the details of P. We present the following theorem as follows.Theorem 3.
Form-dataline CAST256-like structure with SPS-type round function, if R≥3,∃Pt=ei and 0=qi,j∈P∗minR,m−1, we can construct L-round impossible differential distinguishers α,O,O,…,O,O⟶O,O,…,O,O,β, where Hα=Hβ=1 and(33)L=m2+m+minR−3,m−3.Proof.
To prove this theorem, we compareR with m for two cases.Case 1: when3≤R≤m, minR−3,m−3=R−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m+R−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(34)ΔFR−1α=⊕l=1m−1ΔFlβ.TakingF=S∘P∘S into consideration, the above equation becomes(35)ΔS∘P∘S∘⋯S∘P∘S︸R−1α=⊕l=1m−1ΔS∘P∘Slβ.In the left part of equation (35), there exists at least one 0 element in the matrix P∗R−1=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯S∘P∘S︸R−1α must be 0.In the right part of equation (35), when one column of P is ei, assume that the t-th column of P is ei, i.e., Pt=ei, taking β=et and ΔS∘P∘Sβ=ΔS∘P∘Set=ΔS∘Pet=ΔSei=ei. Furthermore, according to Lemma 2,(36)⊕l=1m−1ΔS∘P∘Slet=⊕l=1m−1ei=ei.So, thei-th element of ⊕l=1m−1ΔS∘P∘Slβ is not equal to 0.Therefore, equation (35) does not hold. In this case, we can construct 2m+R−3+mm−1=m2+m+R−3-round impossible differential distinguishers.Case 2: whenR>m, minR−3,m−3=m−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 3m−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(37)ΔFm−1α=⊕l=1m−1ΔFlβ.TakingF=S∘P∘S into consideration, the above equation becomes(38)ΔS∘P∘S∘⋯S∘P∘S︸m−1α=⊕l=1m−1ΔS∘P∘Slβ.In the left part of equation (38), since R>m, there exists at least one 0 element in the matrix P∗m−1. It is similar to Case 1, and we can construct 3m−3+m2−m=m2+2m−3-round impossible differential distinguishers.
Combined with the above two cases, we can constructL-round impossible differential distinguishers, where(39)L=m2+m+R−3,3≤R≤m,m2+m+m−3,R>m.
It is equivalent toL=m2+m+minR−3,m−3.
In [18], m2+m−1-round impossible differential distinguishers were constructed. According to Theorem 3, we can construct Λ1+1=minR−3,m−3+1=minR−2,m−2 rounds longer than before. Moreover, we present a specific linear transformation P satisfying the restricted condition in Theorem 3. For PSkinny which is described in Section 3.2, we calculate R=6. PSkinny and PSkinny∗R−1=PSkinny∗5 are given below, respectively.(40)10 0 0 0 0 0 0 0 010 010 0010 0 0 0 0 0 0 0 010 0100 010 0 0 0 010 0 0 0 0 010 0 010 0 0 0 010 010 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0010 0 0 0 0 0 0 0 0 0 0 0 0 00 010 0 0 0 0 0 0 0 0 0 0 0 00 0 010 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 010 010 0 0 0 00 0 0 010 0 0 0 0 010 0 0 00 0 0 0 010 010 0 0 0 0 0 00 0 0 0 0 010 010 0 0 0 0 010 0 0 0 0 0 0 0 010 0 0 0 0010 0 0 0 0 0 0 0 010 0 0 00 010 0 0 0 010 0 0 0 0 0 00 0 010 0 0 0 010 0 0 0 0 0,287222537648115222873225876421157228532248765211872225326487152115211221322501301152112253220 01321152112253230 01521122112253130 032121121243221102321111222430211123221113224102121231211432211021732123244361140217321236443011432173212364440117321232143641401.
Whenm≥6 and PSkinny∗minR,m−1=PSkinny∗R−1=PSkinny∗5=qi,j16×16, we can find that the 4-th column of PSkinny is e9 and 0=q9,12∈PSkinny∗5. Therefore, PSkinny satisfies the restricted condition in Theorem 3. Moreover, Λ1+1=minR−2,m−2=4. Thus, for m-dataline CAST256-like structure with SPS-type round function, if P takes PSkinny and m≥6, we can construct 4-round impossible differentials longer than those in [18].


## 3.1.m-Dataline CAST256-Like Structure

Anm-dataline CAST256-like structure consists of r rounds, and each round is depicted in Figure 1. Let X0i−1,X1i−1,…,Xm−1i−1 be the input of the i-th round and X0i,X1i,…,Xm−1i and Ki−1 be the output and the round key of the i-th round, respectively. One-round encryption is defined by(9)X0i=Xm−1i−1,Xji=Xj−1i−1,1≤j≤m−2,Xm−1i=FXm−1i−1⊕Ki−1⊕Xm−2i−1,where F is the round function and Xji−1∈F2dn,0≤j≤m−1,i≥1.Figure 1
One-round encryption ofm-dataline CAST256-like structure.To construct impossible differentials, one-round differential propagations from the encryption and decryption directions need to be studied. They are described as follows.Proposition 1.
LetΔXi−1 and ΔXi be the i-th round input difference and output difference of m-dataline CAST256-like structure. From the encryption direction, one-round differential propagation is given below:(10)ΔX0i=ΔXm−1i−1,ΔXji=ΔXj−1i−1,1≤j≤m−2,ΔXm−1i=ΔFΔXm−1i−1⊕ΔXm−2i−1.
From the decryption direction, one-round differential propagation is given below:(11)ΔXji−1=ΔXj+1i,0≤j≤m−3,ΔXm−2i−1=ΔFΔX0i⊕ΔXm−1i,ΔXm−1i−1=ΔX0i.
According to the encryption process ofm-dataline CAST256-like structure, the above proposition can be proved. In the encryption direction, the input difference α,O,O,…,O,Oα∈F2dn,α≠O is encrypted 3m−3 rounds with probability 1 as described in Table 3. Moreover, in the decryption direction, the output difference O,O,…,O,O,ββ∈F2dn,β≠O is decrypted mm−1 rounds with probability 1. The differential characteristic is given in Table 4.
From Tables3 and 4, the following proposition can be obtained.Table 3
3m−3-round differential characteristic of m-dataline CAST256-like structure from the encryption direction.
RoundαOO⋯OO1OαO⋯OO2OOα⋯OO⋮⋮⋮⋮⋮⋮⋮m−1OOO⋯OαmαOO⋯OΔFαm+1ΔFααO⋯OΔF2α⋮⋮⋮⋮⋮⋮⋮2m−1ΔFm−1αΔFm−2αΔFm−3α⋯ΔFα?2m?ΔFm−1αΔFm−2α⋯ΔF2α?2m+1??ΔFm−1α⋯ΔF3α?⋮⋮⋮⋮⋮⋮⋮3m−3???⋯ΔFm−1α?Table 4
mm−1-round differential characteristic of m-dataline CAST256-like structure from the decryption direction.
RoundOOO⋯Oβ1OOO⋯βO2OO⋯βOO⋮⋮⋮⋮⋮⋮⋮m−1βOO⋯OOmOO⋯OΔFββ⋮⋮⋮⋮⋮⋮⋮2mOO⋯O⊕l=12ΔFlββ⋮⋮⋮⋮⋮⋮⋮3mOO⋯O⊕l=13ΔFlββ⋮⋮⋮⋮⋮⋮⋮mm−1??⋯?⊕l=1m−1ΔFlββProposition 2.
Form-dataline CAST256-like structure, after encrypting 2m+r0≤r≤m−3 rounds with the input difference α,O,O,…,O,O, the following differential holds with probability 1:(12)α,O,O,…,O,O⟶2m+r?,?,?,…,?,?,ΔFr+2α,?.
Likewise, after decryptingmm−1 rounds with the output difference O,O,…,O,O,β, the following differential holds with probability 1:(13)O,O,…,O,O,β⟶mm−1?,?,…,?,?,⊕l=1m−1ΔFlβ,β.


## 3.2. Constructing Impossible Differential Distinguishers ofm-Dataline CAST256-Like Structure with SP-Type Round Function

When the round functionF of m-dataline CAST-like structure is made up of SP type, we exploit the details of the linear layer P to construct longer impossible differential distinguishers. Firstly, two lemmas are presented as follows.Lemma 1.
IfG is a bijective mapping, ΔGα=O if and only if α=Δ.
SinceG is bijective, according to the bijective property, Lemma 1 can be easily proved. It also means that α≠O, ΔGα≠O. Especially, for S layer in SP type and SPS type which is a nonlinear bijective mapping, it does not change the nonzero difference positions for the differential propagation according to Lemma 1. It also implies that HΔSα=Hα.Lemma 2.
ForS layer in SP type and SPS type, if t≥1 and(14)⊕l=1tΔSlei≠O,the equation ⊕l=1tΔSlei=ei holds.Proof.
Firstly, we recall the definition ofei. It denotes that only the i-th element of n-dimension vector e is nonzero and the others are zero. According to Lemma 1 and ⊕l=1tΔSlei≠O,(15)⊕l=1tΔSlei=ei.
According to Lemma2, for Hα=1⇔α=ei, when ⊕l=1tΔSlα≠O, the following equation holds:(16)H⊕l=1tΔSlα=Hα=1.Theorem 1.
Form-dataline CAST256-like structure with SP-type round function, if Hα=Hβ=1, we can construct m2+m-round impossible differential distinguishers for any bijective linear layer P as follows:(17)α,O,O,…,O,O⟶m2+mO,O,…,O,O,β.Proof.
From the encryption and decryption directions, the differential with the inputα,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible, the following equation must hold:(18)ΔF2α=⊕l=1m−1ΔFlβ.
TakingF=P∘S into consideration, the above equation becomes(19)ΔP∘S∘P∘Sα=⊕l=1m−1ΔP∘Slβ.
SinceP is a linear bijective mapping,(20)PΔS∘P∘Sα=P⊕l=1m−1ΔSlβ⇔ΔS∘P∘Sα=⊕l=1m−1ΔSlβ.
For the left part of equation (20),(21)HΔS∘P∘Sα=HΔP∘Sα≥BP−HΔSα.
SinceHΔSα=Hα=1 and BP≥2,(22)HΔS∘P∘Sα≥BP−HΔSα=BP−Hα≥1.Case 1: whenHΔS∘P∘Sα>1, note that H⊕l=1m−1ΔSlβ=Hβ=1 according to Lemma 2, and the left and right parts of equation (20) have different Hamming weights. So, equation (20) does not hold.Case 2: whenHΔS∘P∘Sα=1, assume that ΔS∘P∘Sα=et. Take β=ej, where j≠t. According to Lemma 2, ⊕l=1m−1ΔSlβ=ej≠et. The left and right parts of equation (20) could not match each other. So, equation (20) does not hold.
Therefore, combined with the above two cases, equation (20) does not hold. It means that the middle differences could not match each other, and the 2m+mm−1=m2+m-round differential is impossible.
In [18], m2+m-round impossible differential distinguishers were also constructed, but the linear layer P is restricted to that satisfying the condition BP>2. However, in Theorem 1, the restricted condition of P is removed and it is expanded to any bijective linear layer.
To construct longer impossible differential distinguishers, we need to exploit the details of the linear layerP. When the primitive index of the linear layer P satisfies R≥2, the following theorem is given.Theorem 2.
Form-dataline CAST256-like structure with SP-type round function, if R≥2 and Hα=Hβ=1, L-round impossible differential distinguishers α,O,O,…,O,O⟶O,O,…,O,O,β could be constructed, where(23)L=m2+m+minR−2,m−3.Proof.
To prove this theorem, we compareR with m−1 for two cases.Case 1: when2≤R≤m−1, minR−2,m−3=R−2. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m+R−2 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(24)ΔFRα=⊕l=1m−1ΔFlβ.TakingF=P∘S into consideration, the above equation becomes(25)ΔP∘S∘⋯∘P∘S︸Rα=⊕l=1m−1ΔP∘Slβ.SinceP is a linear bijective mapping,(26)ΔS∘P∘S∘⋯∘P∘S︸R−1α=⊕l=1m−1ΔSlβ.In the left part of equation (26), there exists at least one 0 element in the matrix P∗R−1=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯∘P∘S︸R−1α must be 0.In the right part of equation (26), since Hβ=1, we take β=ei. According to Lemma 2., ⊕l=1m−1ΔSlβ=ei. So, the i-th element of ⊕l=1m−1ΔSlβ is not equal to 0.Therefore, equation (26) cannot hold. In this case, we can construct 2m+R−2+mm−1=m2+m+R−2-round impossible differential distinguishers.Case 2: whenR>m−1, minR−2,m−3=m−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 3m−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(27)ΔFm−1α=⊕l=1m−1ΔFlβ.TakingF=P∘S into consideration, the above equation becomes(28)ΔP∘S∘⋯∘P∘S︸m−1α=⊕l=1m−1ΔP∘Slβ.SinceP is a linear bijective mapping,(29)ΔS∘P∘S∘⋯∘P∘S︸m−2α=⊕l=1m−1ΔSlβ.In the left part of equation (29), since R>m−1, there exists at least one 0 element in the matrix P∗m−2=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯∘P∘S︸m−2α must be 0.In the right part of equation (29), it is similar to Case 1. Thus, if we take β=ei, the i-th element of ⊕l=1m−1ΔSlβ is not equal to 0.Therefore, equation (29) does not hold. In this case, we can construct 3m−3+mm−1=m2+2m−3-round impossible differential distinguishers.
Combined with the above two cases, we can constructL-round impossible differential distinguishers, where(30)L=m2+m+R−2,2≤R≤m−1,m2+m+m−3,R>m−1.
It is equivalent toL=m2+m+minR−2,m−3.
In [18], m2+m-round impossible differential distinguishers were constructed. According to Theorem 2, we can construct m2+m+minR−2,m−3-round impossible differentials which are Λ0=minR−2,m−3 rounds longer than before. The restricted condition R≥2 can be satisfied easily. We present some specific linear transformations P satisfying the condition. For example, we first present MC of Skinny block cipher [21] below:(31)PMC=1011100001101010.
With the definition ofR, we calculate R=3 for PMC. According to Theorem 2, if the linear transformation P takes PMC and m≥4, Λ0=minR−2,m−3=1. Therefore, we can construct m2+m+1-round impossible differential distinguishers for m-dataline CAST256-like structure with SP-type round function. They are Λ0=1 round longer than those in [18]. Moreover, we present another example. For the linear transformation of Skinny block cipher which is SR∘MC, it is given below:(32)PSkinny=10 0 0 0 0 0 0 0 010 010 0010 0 0 0 0 0 0 0 010 0100 010 0 0 0 010 0 0 0 0 010 0 010 0 0 0 010 010 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0010 0 0 0 0 0 0 0 0 0 0 0 0 00 010 0 0 0 0 0 0 0 0 0 0 0 00 0 010 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 010 010 0 0 0 00 0 0 010 0 0 0 0 010 0 0 00 0 0 0 010 010 0 0 0 0 0 00 0 0 0 0 010 010 0 0 0 0 010 0 0 0 0 0 0 0 010 0 0 0 0010 0 0 0 0 0 0 0 010 0 0 00 010 0 0 0 010 0 0 0 0 0 00 0 010 0 0 0 010 0 0 0 0 016×16.
We calculateR=6 for PSkinny. According to Theorem 2, if the linear transformation P takes PSkinny and m≥7, Λ0=minR−2,m−3=4. Therefore, we can construct m2+m+4-round impossible differential distinguishers. They are Λ0=4 rounds longer than those in [18].
In brief, combined with Theorem1 and Theorem 2, for m-dataline CAST256-like structure with SP-type round function, the results on the impossible differential distinguishers have been improved. Especially, when R>2, we can construct longer impossible differentials.


## 3.3. Constructing Impossible Differential Distinguishers ofm-Dataline CAST256-Like Structure with SPS-Type Round Function

Form-dataline CAST256-like structure with SPS-type round function, m2+m−1-round impossible differential distinguishers were constructed for R≥2 [18]. In this section, we will construct longer impossible differential distinguishers with the details of P. We present the following theorem as follows.Theorem 3.
Form-dataline CAST256-like structure with SPS-type round function, if R≥3,∃Pt=ei and 0=qi,j∈P∗minR,m−1, we can construct L-round impossible differential distinguishers α,O,O,…,O,O⟶O,O,…,O,O,β, where Hα=Hβ=1 and(33)L=m2+m+minR−3,m−3.Proof.
To prove this theorem, we compareR with m for two cases.Case 1: when3≤R≤m, minR−3,m−3=R−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 2m+R−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(34)ΔFR−1α=⊕l=1m−1ΔFlβ.TakingF=S∘P∘S into consideration, the above equation becomes(35)ΔS∘P∘S∘⋯S∘P∘S︸R−1α=⊕l=1m−1ΔS∘P∘Slβ.In the left part of equation (35), there exists at least one 0 element in the matrix P∗R−1=qi,jn×n. Assume that qi,j=0, and when we take α=ej, the i-th element of ΔS∘P∘S∘⋯S∘P∘S︸R−1α must be 0.In the right part of equation (35), when one column of P is ei, assume that the t-th column of P is ei, i.e., Pt=ei, taking β=et and ΔS∘P∘Sβ=ΔS∘P∘Set=ΔS∘Pet=ΔSei=ei. Furthermore, according to Lemma 2,(36)⊕l=1m−1ΔS∘P∘Slet=⊕l=1m−1ei=ei.So, thei-th element of ⊕l=1m−1ΔS∘P∘Slβ is not equal to 0.Therefore, equation (35) does not hold. In this case, we can construct 2m+R−3+mm−1=m2+m+R−3-round impossible differential distinguishers.Case 2: whenR>m, minR−3,m−3=m−3. From the encryption and decryption directions, the differential with the input α,O,O,…,O,O and the output O,O,…,O,O,β propagates 3m−3 and mm−1 rounds, respectively. According to Proposition 2, if the differential is possible,(37)ΔFm−1α=⊕l=1m−1ΔFlβ.TakingF=S∘P∘S into consideration, the above equation becomes(38)ΔS∘P∘S∘⋯S∘P∘S︸m−1α=⊕l=1m−1ΔS∘P∘Slβ.In the left part of equation (38), since R>m, there exists at least one 0 element in the matrix P∗m−1. It is similar to Case 1, and we can construct 3m−3+m2−m=m2+2m−3-round impossible differential distinguishers.
Combined with the above two cases, we can constructL-round impossible differential distinguishers, where(39)L=m2+m+R−3,3≤R≤m,m2+m+m−3,R>m.
It is equivalent toL=m2+m+minR−3,m−3.
In [18], m2+m−1-round impossible differential distinguishers were constructed. According to Theorem 3, we can construct Λ1+1=minR−3,m−3+1=minR−2,m−2 rounds longer than before. Moreover, we present a specific linear transformation P satisfying the restricted condition in Theorem 3. For PSkinny which is described in Section 3.2, we calculate R=6. PSkinny and PSkinny∗R−1=PSkinny∗5 are given below, respectively.(40)10 0 0 0 0 0 0 0 010 010 0010 0 0 0 0 0 0 0 010 0100 010 0 0 0 010 0 0 0 0 010 0 010 0 0 0 010 010 0 010 0 0 0 0 0 0 0 0 0 0 0 0 0 0010 0 0 0 0 0 0 0 0 0 0 0 0 00 010 0 0 0 0 0 0 0 0 0 0 0 00 0 010 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 010 010 0 0 0 00 0 0 010 0 0 0 0 010 0 0 00 0 0 0 010 010 0 0 0 0 0 00 0 0 0 0 010 010 0 0 0 0 010 0 0 0 0 0 0 0 010 0 0 0 0010 0 0 0 0 0 0 0 010 0 0 00 010 0 0 0 010 0 0 0 0 0 00 0 010 0 0 0 010 0 0 0 0 0,287222537648115222873225876421157228532248765211872225326487152115211221322501301152112253220 01321152112253230 01521122112253130 032121121243221102321111222430211123221113224102121231211432211021732123244361140217321236443011432173212364440117321232143641401.
Whenm≥6 and PSkinny∗minR,m−1=PSkinny∗R−1=PSkinny∗5=qi,j16×16, we can find that the 4-th column of PSkinny is e9 and 0=q9,12∈PSkinny∗5. Therefore, PSkinny satisfies the restricted condition in Theorem 3. Moreover, Λ1+1=minR−2,m−2=4. Thus, for m-dataline CAST256-like structure with SPS-type round function, if P takes PSkinny and m≥6, we can construct 4-round impossible differentials longer than those in [18].


## 4. Revisiting Impossible Differential Distinguishers ofm-Dataline MARS-Like Structure

In this section, we first introducem-dataline MARS-like structure and present the differential propagation rules from the encryption and decryption directions. Then, when the round function takes SPS type, 3m-round impossible differential distinguishers will be constructed. It should be pointed out that m≥4 and m should be even number in this section.


### 4.1.m-Dataline MARS-Like Structure

Anm-dataline MARS-like structure consists of r rounds, and each round is depicted in Figure 2.Figure 2
One-round encryption ofm-dataline MARS-like structure.LetX0i−1,X1i−1,…,Xm−1i−1 be the input of the i-th round and X0i,X1i,…,Xm−1i and Ki−1 be the output and the round key of the i-th round, respectively. One-round encryption is defined by(41)Xji=FX0i−1⊕Ki−1⊕Xj+1i−1,0≤j≤m−2,Xm−1i=X0i−1,where F is the round function and Xji−1∈F2dn,0≤j≤m−1,i≥1.


### 4.2. Constructing Impossible Differential Distinguishers ofm-Dataline MARS-Like Structure with SPS-Type Round Function

To construct impossible differentials, one-round differential propagations from the encryption and decryption directions need to be studied. They are described as follows.Proposition 3.
LetΔXi−1 and ΔXi be the i-th round input difference and output difference of m-dataline MARS-like structure. From the encryption direction, one-round differential propagation is presented below:(42)ΔXji=ΔFΔX0i−1⊕ΔXj+1i−1,0≤j≤m−2,ΔXm−1i=ΔX0i−1.
From the decryption direction, one-round differential propagation is presented below:(43)ΔX0i−1=ΔXm−1i,ΔXji−1=ΔFΔXm−1i⊕ΔXj−1i,1≤j≤m−1.
According to the encryption process of MARS-like structure, the above proposition can be proved. Moreover, from the encryption direction, the input differenceO,O,…,O,O,αα∈F2dn,α≠O is encrypted 3m/2 rounds with probability 1 as described in Table 5. In this table, a0∈ΔFα,ai∈ΔFa0⊕a1⊕⋯⊕ai−1,i≥1,A=a0⊕a1⊕⋯⊕am/2. Similarly, from the decryption direction, the output difference α,O,O,…,O,O is decrypted 3m/2 rounds with probability 1 as described in Table 6. In this table, b0∈ΔFα,bi∈ΔFb0⊕b1⊕⋯⊕bi−1,i≥1,B=b0⊕b1⊕⋯⊕bm/2.
If3m/2+3m/2=3m-round differential O,O,…,O,O,α⟶3mα,O,O,…,O,O is a possible differential, the middle differences need to match each other. Thus, the following equations need to be satisfied:(44)A=a0⊕a1⊕⋯⊕am/2,B=b0⊕b1⊕⋯⊕bm/2,A=B⊕bm/2,A=B⊕bm/2−1,⋮A=B⊕b2,A⊕α⊕a0=B⊕b1,A⊕a1=B⊕α⊕b0,A⊕a2=B,⋮A⊕am/2=B.
Solving the above equations,(45)bm/2=bm/2−1=⋯=b2=a2=⋯=am/2−1=am/2=O,a0⊕b1=a1⊕b0=α.
SinceF is bijective, according to Lemma 1,(46)a2=ΔFa0⊕a1=O,b2=ΔFb0⊕b1=O,⇔a0⊕a1=O,b0⊕b1=O,⇔a1=a0,b1=b0.
Thus,(47)a0⊕b1=a0⊕b0=α⇔ΔF1α⊕ΔF2α=α.
When the round functionF of m-dataline MARS-like structure takes SPS type, the impossible differential distinguishers can be constructed with the following theorem.Table 5
3m/2-round differential characteristic of m-dataline MARS-like structure from the encryption direction.
RoundOOOO⋯Oα1OOOO⋯αO⋮⋮⋮⋮⋮⋮⋮⋮m−1αOOO⋯OOma0a0a0a0⋯a0α⋮⋮⋮⋮⋮⋮⋮3m/2A⋯AA⊕α⊕a0A⊕a1⋯A⊕am/2Table 6
3m/2-round differential characteristic of m-dataline MARS-like structure from the decryption direction.
RoundαOOO⋯OO1OαOO⋯OO⋮⋮⋮⋮⋮⋮⋮⋮m−1OOOO⋯Oαmαb0b0b0⋯b0b0⋮⋮⋮⋮⋮⋮⋮3m/2B⊕bm/2⋯B⊕b1B⊕α⊕b0B⋯BTheorem 4.
Form-dataline MARS-like structure with SPS-type round function, if there exists one 0 element in the diagonal line of P, 3m-round impossible differential distinguishers can be constructed as follows:(48)α,O,O,…,O,O⟶3mO,O,…,O,O,α,where Hα=1.Proof.
Whenα,O,O,…,O,O⟶3mO,O,…,O,O,α is a 3m-round possible differential, the following equation needs to be satisfied:(49)ΔF1α⊕ΔF2α=α.
Given thatF takes SPS type, the above equation becomes(50)ΔS°P°S1α⊕ΔS°P°S2α=α.
Since∃pt,t=0,pt,t∈P, we take α=et,ΔSα=et,ΔP°Sα=et˜, where et˜ denotes that the t-th element of n-dimension vector e is 0 and the others can be arbitrary values. Moreover, ΔS°P°Sα=et˜. Furthermore, ΔS°P°S1α⊕ΔS°P°S2α=et˜ which conflicts with α=et in the t-th element. Therefore, equation (50) does not hold.
In [19], 3m−1-round impossible differential distinguishers were constructed for m-dataline MARS-like structure with SPS-type round function. According to Theorem 4, we can construct 1 round longer than before. Moreover, some specific linear transformations P satisfying the condition in Theorem 4 are presented. For example, MC of Midori block cipher [22] is described below:(51)PMC∗=01111011110111104×4.
In this matrix, we can observe thatp0,0=p1,1=p2,2=p3,3=0. Therefore, PMC∗ satisfies the restricted condition in Theorem 4. Furthermore, PMC and PSkinny described in Section 3.2 also satisfy the condition.


## 4.1.m-Dataline MARS-Like Structure

Anm-dataline MARS-like structure consists of r rounds, and each round is depicted in Figure 2.Figure 2
One-round encryption ofm-dataline MARS-like structure.LetX0i−1,X1i−1,…,Xm−1i−1 be the input of the i-th round and X0i,X1i,…,Xm−1i and Ki−1 be the output and the round key of the i-th round, respectively. One-round encryption is defined by(41)Xji=FX0i−1⊕Ki−1⊕Xj+1i−1,0≤j≤m−2,Xm−1i=X0i−1,where F is the round function and Xji−1∈F2dn,0≤j≤m−1,i≥1.


## 4.2. Constructing Impossible Differential Distinguishers ofm-Dataline MARS-Like Structure with SPS-Type Round Function

To construct impossible differentials, one-round differential propagations from the encryption and decryption directions need to be studied. They are described as follows.Proposition 3.
LetΔXi−1 and ΔXi be the i-th round input difference and output difference of m-dataline MARS-like structure. From the encryption direction, one-round differential propagation is presented below:(42)ΔXji=ΔFΔX0i−1⊕ΔXj+1i−1,0≤j≤m−2,ΔXm−1i=ΔX0i−1.
From the decryption direction, one-round differential propagation is presented below:(43)ΔX0i−1=ΔXm−1i,ΔXji−1=ΔFΔXm−1i⊕ΔXj−1i,1≤j≤m−1.
According to the encryption process of MARS-like structure, the above proposition can be proved. Moreover, from the encryption direction, the input differenceO,O,…,O,O,αα∈F2dn,α≠O is encrypted 3m/2 rounds with probability 1 as described in Table 5. In this table, a0∈ΔFα,ai∈ΔFa0⊕a1⊕⋯⊕ai−1,i≥1,A=a0⊕a1⊕⋯⊕am/2. Similarly, from the decryption direction, the output difference α,O,O,…,O,O is decrypted 3m/2 rounds with probability 1 as described in Table 6. In this table, b0∈ΔFα,bi∈ΔFb0⊕b1⊕⋯⊕bi−1,i≥1,B=b0⊕b1⊕⋯⊕bm/2.
If3m/2+3m/2=3m-round differential O,O,…,O,O,α⟶3mα,O,O,…,O,O is a possible differential, the middle differences need to match each other. Thus, the following equations need to be satisfied:(44)A=a0⊕a1⊕⋯⊕am/2,B=b0⊕b1⊕⋯⊕bm/2,A=B⊕bm/2,A=B⊕bm/2−1,⋮A=B⊕b2,A⊕α⊕a0=B⊕b1,A⊕a1=B⊕α⊕b0,A⊕a2=B,⋮A⊕am/2=B.
Solving the above equations,(45)bm/2=bm/2−1=⋯=b2=a2=⋯=am/2−1=am/2=O,a0⊕b1=a1⊕b0=α.
SinceF is bijective, according to Lemma 1,(46)a2=ΔFa0⊕a1=O,b2=ΔFb0⊕b1=O,⇔a0⊕a1=O,b0⊕b1=O,⇔a1=a0,b1=b0.
Thus,(47)a0⊕b1=a0⊕b0=α⇔ΔF1α⊕ΔF2α=α.
When the round functionF of m-dataline MARS-like structure takes SPS type, the impossible differential distinguishers can be constructed with the following theorem.Table 5
3m/2-round differential characteristic of m-dataline MARS-like structure from the encryption direction.
RoundOOOO⋯Oα1OOOO⋯αO⋮⋮⋮⋮⋮⋮⋮⋮m−1αOOO⋯OOma0a0a0a0⋯a0α⋮⋮⋮⋮⋮⋮⋮3m/2A⋯AA⊕α⊕a0A⊕a1⋯A⊕am/2Table 6
3m/2-round differential characteristic of m-dataline MARS-like structure from the decryption direction.
RoundαOOO⋯OO1OαOO⋯OO⋮⋮⋮⋮⋮⋮⋮⋮m−1OOOO⋯Oαmαb0b0b0⋯b0b0⋮⋮⋮⋮⋮⋮⋮3m/2B⊕bm/2⋯B⊕b1B⊕α⊕b0B⋯BTheorem 4.
Form-dataline MARS-like structure with SPS-type round function, if there exists one 0 element in the diagonal line of P, 3m-round impossible differential distinguishers can be constructed as follows:(48)α,O,O,…,O,O⟶3mO,O,…,O,O,α,where Hα=1.Proof.
Whenα,O,O,…,O,O⟶3mO,O,…,O,O,α is a 3m-round possible differential, the following equation needs to be satisfied:(49)ΔF1α⊕ΔF2α=α.
Given thatF takes SPS type, the above equation becomes(50)ΔS°P°S1α⊕ΔS°P°S2α=α.
Since∃pt,t=0,pt,t∈P, we take α=et,ΔSα=et,ΔP°Sα=et˜, where et˜ denotes that the t-th element of n-dimension vector e is 0 and the others can be arbitrary values. Moreover, ΔS°P°Sα=et˜. Furthermore, ΔS°P°S1α⊕ΔS°P°S2α=et˜ which conflicts with α=et in the t-th element. Therefore, equation (50) does not hold.
In [19], 3m−1-round impossible differential distinguishers were constructed for m-dataline MARS-like structure with SPS-type round function. According to Theorem 4, we can construct 1 round longer than before. Moreover, some specific linear transformations P satisfying the condition in Theorem 4 are presented. For example, MC of Midori block cipher [22] is described below:(51)PMC∗=01111011110111104×4.
In this matrix, we can observe thatp0,0=p1,1=p2,2=p3,3=0. Therefore, PMC∗ satisfies the restricted condition in Theorem 4. Furthermore, PMC and PSkinny described in Section 3.2 also satisfy the condition.


## 5. Conclusions

In this paper, we investigated impossible differential distinguishers ofm-dataline CAST256-like structure and m-dataline MARS-like structure. Longer impossible differentials for them were constructed with the help of the linear transformation P. Moreover, given that the dual relationship between impossible differentials and zero correlation linear hulls which is presented by Sun Bing et al. at CRYPTO 2015, our results may also be applied to construct zero correlation linear hulls of these two structures. In brief, our results not only are useful to improve the impossible differential attack on these two structures from the cryptanalysis view but also provide guidance to select better linear transformation for improving the security from the designer’s view.



---

*Source: 5582711-2021-06-01.xml*