# Improved Impossible Differentials and Zero-Correlation Linear Hulls of New Structure III

Authors: Jun He; Xuan Shen; Guoqiang Liu
Journal: Security and Communication Networks
 (2021)

---

## Abstract

Impossible differential cryptanalysis and zero-correlation linear cryptanalysis are two kinds of most effective tools for evaluating the security of block ciphers. In those attacks, the core step is to construct a distinguisher as long as possible. In this paper, we focus on the security of New Structure III, which is a kind of block cipher structure with excellent resistance against differential and linear attacks. While the best previous result can only exploit one-round linear layerP to construct impossible differential and zero-correlation linear distinguishers, we try to exploit more rounds to find longer distinguishers. Combining the Miss-in-the-Middle strategy and the characteristic matrix method proposed at EUROCRYPT 2016, we could construct 23-round impossible differentials and zero-correlation linear hulls when the linear layer P satisfies some restricted conditions. To our knowledge, both of them are 1 round longer than the best previous works concerning the two cryptanalytical methods. Furthermore, to show the effectiveness of our distinguishers, the linear layer of the round function is specified to the permutation matrix of block cipher SKINNY which was proposed at CRYPTO 2016. Our results indicate that New Structure III has weaker resistance against impossible differential and zero-correlation linear attacks, though it possesses good differential and linear properties.


---

## Body

## 1. Introduction

Block cipher structures are regarded as the backbones of block ciphers. When designing a new block cipher, the first step is to choose a proper structure. From the implementation aspect, the structures will significantly influence the implementation cost and latency of the block cipher. From the security part, the structures will affect the diffusion and interaction among different components and give guidance of the parameters of block cipher such as the number of iterated rounds accordingly. Therefore, cryptanalysis of block cipher structures also deserves much attention [1–4].So far, one of the most popular block cipher structures is the Feistel structure. It divides the input into two halves and updates one half every time. Since decryption of Feistel structures does not involve the inverse of round functions, the encryption and decryption enjoy similar structure and components, making its design more flexible, versatile, and economical. Its randomness [5] and resistance against Meet-in-the-Middle [6], yoyo [7], and quantum [8] attacks were widely considered. In [9], generalized Feistel structure (GFS) was proposed. While GFS preserves the advantages of Feistel structures, its branch size and round functions are lighter and more portable. GFS is further extended and classified into Type-II GFS, unbalanced GFS, and so on. As shown in Figure 1, Type-II GFS updates one half of branches and follows by a branch-wise circular shift, while unbalanced GFS uses a contracting or expanding round functions. Examples of those GFSs are CLEFIA [10], HIGHT [11], SMS4 [2], MARS [3], GMiMC [12], etc. Those schemes possess relatively high diffusion while keeping portable round function design.Figure 1
4-branch Type-II GFS (a), 4-branch contracting unbalanced GFS (b), and 4-branch expanding unbalanced GFS (c).
(a)(b)(c)The security of GFS has undergone careful evaluation. After its publication, the diffusion and security regarding differential and linear attacks of Type-II GFS were evaluated by counting the number of active S-boxes. At SAC 2010, the lower bound of active S-boxes with SP type round functions was evaluated [13]. Then, similar studies with respect to SPS and SPSP type round functions were performed [14, 15]. The impossible differential cryptanalysis and zero-correlation linear and integral cryptanalysis have also been taken into consideration. Based on the Miss-in-the-Middle strategy, Kim et al. [16] analyzed the impossible differential property using a matrix-based method. Yang et al. [17] and Zhang and Wu [18] proposed a search method for zero-correlation linear and integral distinguishers, respectively. At FSE 2015, Blondeau and Minier [19] noticed the links among the three analytical methods for Type-II GFS and performed systematic key recovery attacks. In addition, the security against Meet-in-the-Middle attack [20], known key attack [21], and quantum attack [22] has also been evaluated.With the improvement of generic analytical techniques, some new variants of GFS are proposed. At ACISP 2009, Choy et al. combined the generalized unbalanced Feistel networks with the MISTY structure and named it GF-NLFSR [23]. GF-NLFSR possess better security in the sense of differential and linear probability bounds. In 2011, Wu and Wang [24] put forward a unified method to assess the lower bounds of the minimal number of differential active S-boxes for block cipher structures. With this method, they presented 4 new structures, namely, New Structure I/II/III/IV. Among them, New Structure III features better properties against differential and linear attacks than other well-known structures like Type-I/II GFS, Skipjack structures, GF-NLFSR, and so on.Apart from the resistance against differential and linear cryptanalysis, the security evaluation of New Structure family mainly concentrates on the impossible differential and zero-correlation linear attacks. In [25], Cui and Jin constructed the first impossible differentials for New Structure family. They showed that there exist 15/∞/19/16-round impossible differentials for New Structure I/II/III/IV, respectively. Recently, in 2018, Fu et al. [26] further extended the results by exploiting the information of the round function. They constructed 16/∞/22/16-round impossible differentials by considering the SP type round functions. Moreover, 16/∞/22/16-round zero-correlation linear distinguishers were also built by similar methods. Compared with the above results, the impossible differentials of New Structure III were significantly improved.Inspired by the characteristic matrix method used at EUROCRYPT 2016 [27], we also study the security against impossible differential and zero-correlation linear attacks of New Structures III with SP type round functions in this paper. The distinguishers are constructed in two steps. We first derive the differential and linear propagation patterns. Then, contradictions are detected by adding some constraints to the linear layer of the round function. Taking advantage of the characteristic matrix method, more information of some rounds of linear layer P can be exploited instead of only one round. Therefore, more rounds of impossible differentials and zero-correlation linear hulls will be constructed. In this paper, we improve the best previous results of New Structure III by 1 round. Those results are summarized in Table 1.Table 1
Distinguishers of New Structure III.
Distinguisher typesDistinguisher roundsReferencesImpossible differentials19[25]Impossible differentials22[26]Impossible differentials23Section3Zero-correlation linear hulls22[26]Zero-correlation linear hulls23Section4The rest of this paper is organized as follows. In Section2, some notations and concepts will be introduced. Impossible differentials and zero-correlation linear hulls of New Structure III will be constructed in Sections 3 and 4, respectively. Section 5 concludes this paper.


## 2. Preliminary

In this section, we will introduce the impossible differentials and zero-correlation linear hulls. Then, detailed description of New Structure III will be depicted. Before that, we will first introduce some notations that will be used throughout this paper.


### 2.1. Notations

The state of the round function is regarded as ad-dimensional column vector v, and its i-th element is denoted as vi. The transpose of v is denoted as vT. Moreover, ei denotes the d-dimensional unit vector whose i-th element is nonzero and others are zero. Similarly, for a d × d matrix M, the element in row i and column j is defined as Mi,j. M−1 and MT are the inverse and transpose operations of M, respectively.In [27], a characteristic matrix method is proposed to evaluate the impossible differentials and zero-correlation linear hulls of SPN ciphers. The definition of a characteristic matrix is given below.Definition 1 (characteristic matrix) (see [27]).
LetP be a linear mapping, and it can be expressed as a d × d matrix; the characteristic matrix of P=pi,jd×d is defined as P∗=pi,j∗d×d, where(1)pi,j∗=0,pi,j=0,1,pi,j≠0.
The characteristic matrix is used to express the dependency between the input and output. For a characteristic matrixM, when Mi,j = 0, it means the i-th element of the output is independent of the j-th element of the input. Otherwise, Mi,j = 1. Based on this characteristic matrix method, the round function of SPN ciphers could be reflected as matrix multiplication. Denote Mt as the t-th power of M, and the multiplication of matrix is defined as(2)M×Mi,j=Mi,1⋅M1,jMi,2⋅M2,j…|Mi,d⋅Md,j,where “|” is the bitwise OR operation. Given that the nonlinear bijective function S [28] does not change the differential/mask pattern, if there exists one zero element in row i and column j of Mt, it means that the i-th element of the output is independent of the j-th element of the input for t-round SPN ciphers. In addition, if M works on a column vector v, it is also defined as(3)M×vi=Mi,1⋅v1|Mi,2⋅v2|…|Mi,d⋅vd.


### 2.2. Impossible Differentials

The impossible differential attack is a variant of differential attack, and it was proposed by Knudsen [29] and Biham et al. [30] independently. Different from differential attack which uses differential with high probability, impossible differential attack exploits differentials which occur with probability 0 instead. For an n-bit block cipher Ek with input difference α and output difference β, its differential probability is defined as the percentage of right inputs:(4)Prα⟶β=2−n#X|EkX⊕EkX⊕α=β.If the above probability equals zero, i.e.,(5)Prα⟶β=0,the differential from α to β is regarded to be impossible.At FSE 1999, Biham et al. [31] systematically introduced the Miss-in-the-Middle approach which is still the most commonly used strategy in searching for impossible differentials so far. It propagates the input difference of some rounds from the encryption direction with probability 1 and some rounds for the output difference from the decryption direction similarly. Then, the intermediate state is tested whether there is a contradiction. If detected, then an impossible differential is found.


### 2.3. Zero-Correlation Linear Hulls

The zero-correlation linear attack is a novel extension of linear cryptanalysis. It was first formalized by Bogdanov et al. in 2011 [32]. The zero-correlation linear attack utilizes linear hull whose correlation is zero. For a block cipher Ek, its linear approximation p(α, β) is defined as the percentage of inputs X that satisfy α⋅X = β⋅Ek(X), i.e.,(6)pα,β=2−n#X|α⋅X=β⋅EkX,where “⋅” means the inner product and α, β are the input mask and output mask, respectively. Then, the correlation of linear hull (α, β) is defined as(7)cα,β=2pα,β−1.Linear cryptanalysis employs linear hulls with high correlation, while zero-correlation linear cryptanalysis uses that with correlationc(α, β) = 0.Similar to the impossible differentials, the Miss-in-the-Middle approach could also be applied to the construction of zero-correlation linear hulls. The procedure is similar. The input mask propagates some rounds forward and the output mask propagates some rounds backward with probability 1. Then, the correlation of this linear hull is zero once the intermediate states are checked for the contradiction.


### 2.4. The New Structure Series of Block Cipher Structures

The New Structure series of block cipher structures were proposed by Wu et al. in 2011. They provided a generalized approach using integer programming to estimate the lower bound of the minimal active S-boxes for various structures. With this approach in hand, they are able to search for new structures with good immune against differential and linear attacks. The New Structure series were designed in this way. They could provide 22 active S-boxes with 25/22/21/24 rounds.The New Structure families are specified to be 4 branches, and only one-round function is employed in a single round. The diffusion and confusion are achieved by different combination of XOR, branch-wise circular shift, and nonlinear part. The schematic diagram is shown in Figure2.Figure 2
New Structures I, II, III, and IV.For New Structure III, its leftmost branch is first nonlinearly transformed by the round functionF. Then, the nonlinearly transformed state is XORed to its right branch. Finally, the branches are left circular shifted by 1. Assume that the input and output are (x0, x1, x2, x3) and (y0, y1, y2, y3), respectively; then, one-round transformation of New Structure III is(8)y0,y1,y2,y3=x1⊕Fx0,x2,x3,Fx0.For GFS and its extension, the round functions are flexible, versatile, and not necessarily bijective. However, round functions adopting Substitution-Permutation (SP) type structures are preferable. Since SP structure features better diffusion property and well-understood security, many block ciphers employing GFS use SP type round functions such as SMS4 [2], CLEFIA [10], and so on. The SP type round function consists of nonlinear layer S and linear layer P, where S is made up of d parallel s-bit S-boxes and P could be expressed as a d × d matrix operating on sd bits with word length s. It should be pointed out that both of the nonlinear layer S and linear layer P in this paper are bijective.To describe the differential/mask propagation through the linear layer, the proposition is shown below.Proposition 1 (see [33]).
LetP be a linear bijective layer; then,(i)
For any input-output differenceΔin⟶Δout, if the differential probability is nonzero, we always have Δout=PΔin.(ii)
For any input-output maskΛin⟶Λout, if the correlation is nonzero, we always have Λout=P−1TΛin.


## 2.1. Notations

The state of the round function is regarded as ad-dimensional column vector v, and its i-th element is denoted as vi. The transpose of v is denoted as vT. Moreover, ei denotes the d-dimensional unit vector whose i-th element is nonzero and others are zero. Similarly, for a d × d matrix M, the element in row i and column j is defined as Mi,j. M−1 and MT are the inverse and transpose operations of M, respectively.In [27], a characteristic matrix method is proposed to evaluate the impossible differentials and zero-correlation linear hulls of SPN ciphers. The definition of a characteristic matrix is given below.Definition 1 (characteristic matrix) (see [27]).
LetP be a linear mapping, and it can be expressed as a d × d matrix; the characteristic matrix of P=pi,jd×d is defined as P∗=pi,j∗d×d, where(1)pi,j∗=0,pi,j=0,1,pi,j≠0.
The characteristic matrix is used to express the dependency between the input and output. For a characteristic matrixM, when Mi,j = 0, it means the i-th element of the output is independent of the j-th element of the input. Otherwise, Mi,j = 1. Based on this characteristic matrix method, the round function of SPN ciphers could be reflected as matrix multiplication. Denote Mt as the t-th power of M, and the multiplication of matrix is defined as(2)M×Mi,j=Mi,1⋅M1,jMi,2⋅M2,j…|Mi,d⋅Md,j,where “|” is the bitwise OR operation. Given that the nonlinear bijective function S [28] does not change the differential/mask pattern, if there exists one zero element in row i and column j of Mt, it means that the i-th element of the output is independent of the j-th element of the input for t-round SPN ciphers. In addition, if M works on a column vector v, it is also defined as(3)M×vi=Mi,1⋅v1|Mi,2⋅v2|…|Mi,d⋅vd.


## 2.2. Impossible Differentials

The impossible differential attack is a variant of differential attack, and it was proposed by Knudsen [29] and Biham et al. [30] independently. Different from differential attack which uses differential with high probability, impossible differential attack exploits differentials which occur with probability 0 instead. For an n-bit block cipher Ek with input difference α and output difference β, its differential probability is defined as the percentage of right inputs:(4)Prα⟶β=2−n#X|EkX⊕EkX⊕α=β.If the above probability equals zero, i.e.,(5)Prα⟶β=0,the differential from α to β is regarded to be impossible.At FSE 1999, Biham et al. [31] systematically introduced the Miss-in-the-Middle approach which is still the most commonly used strategy in searching for impossible differentials so far. It propagates the input difference of some rounds from the encryption direction with probability 1 and some rounds for the output difference from the decryption direction similarly. Then, the intermediate state is tested whether there is a contradiction. If detected, then an impossible differential is found.


## 2.3. Zero-Correlation Linear Hulls

The zero-correlation linear attack is a novel extension of linear cryptanalysis. It was first formalized by Bogdanov et al. in 2011 [32]. The zero-correlation linear attack utilizes linear hull whose correlation is zero. For a block cipher Ek, its linear approximation p(α, β) is defined as the percentage of inputs X that satisfy α⋅X = β⋅Ek(X), i.e.,(6)pα,β=2−n#X|α⋅X=β⋅EkX,where “⋅” means the inner product and α, β are the input mask and output mask, respectively. Then, the correlation of linear hull (α, β) is defined as(7)cα,β=2pα,β−1.Linear cryptanalysis employs linear hulls with high correlation, while zero-correlation linear cryptanalysis uses that with correlationc(α, β) = 0.Similar to the impossible differentials, the Miss-in-the-Middle approach could also be applied to the construction of zero-correlation linear hulls. The procedure is similar. The input mask propagates some rounds forward and the output mask propagates some rounds backward with probability 1. Then, the correlation of this linear hull is zero once the intermediate states are checked for the contradiction.


## 2.4. The New Structure Series of Block Cipher Structures

The New Structure series of block cipher structures were proposed by Wu et al. in 2011. They provided a generalized approach using integer programming to estimate the lower bound of the minimal active S-boxes for various structures. With this approach in hand, they are able to search for new structures with good immune against differential and linear attacks. The New Structure series were designed in this way. They could provide 22 active S-boxes with 25/22/21/24 rounds.The New Structure families are specified to be 4 branches, and only one-round function is employed in a single round. The diffusion and confusion are achieved by different combination of XOR, branch-wise circular shift, and nonlinear part. The schematic diagram is shown in Figure2.Figure 2
New Structures I, II, III, and IV.For New Structure III, its leftmost branch is first nonlinearly transformed by the round functionF. Then, the nonlinearly transformed state is XORed to its right branch. Finally, the branches are left circular shifted by 1. Assume that the input and output are (x0, x1, x2, x3) and (y0, y1, y2, y3), respectively; then, one-round transformation of New Structure III is(8)y0,y1,y2,y3=x1⊕Fx0,x2,x3,Fx0.For GFS and its extension, the round functions are flexible, versatile, and not necessarily bijective. However, round functions adopting Substitution-Permutation (SP) type structures are preferable. Since SP structure features better diffusion property and well-understood security, many block ciphers employing GFS use SP type round functions such as SMS4 [2], CLEFIA [10], and so on. The SP type round function consists of nonlinear layer S and linear layer P, where S is made up of d parallel s-bit S-boxes and P could be expressed as a d × d matrix operating on sd bits with word length s. It should be pointed out that both of the nonlinear layer S and linear layer P in this paper are bijective.To describe the differential/mask propagation through the linear layer, the proposition is shown below.Proposition 1 (see [33]).
LetP be a linear bijective layer; then,(i)
For any input-output differenceΔin⟶Δout, if the differential probability is nonzero, we always have Δout=PΔin.(ii)
For any input-output maskΛin⟶Λout, if the correlation is nonzero, we always have Λout=P−1TΛin.


## 3. Impossible Differentials of New Structure III

In this section, we first give one-round differential propagation and then construct 23-round impossible differential distinguishers of New Structure III by the Miss-in-the-Middle method if the linear layerP satisfies some extra conditions. To describe the differential properties better, we first give some notations. ΔF(a) represents all possible output differences of the nonlinear function F when the input difference is a. Similarly, ΔFr(a) represents all possible output differences of the continuous r-round F when the input difference is a, and ΔF-r(a) represents all possible output differences of the continuous r-round F−1 (inverse of F) when the input difference is a.To construct impossible differentials, one-round differential propagation should be presented firstly. The property is given below.Proposition 2 (see [25, 26]).
For one-round encryption of New Structure III, let (a0, a1, a2, a3) and (b0, b1, b2, b3) be the input and output difference, respectively, and we have(9)b0=ΔFa0⊕a1,b1=a2,b2=a3,b3=ΔFa0.One-round differential propagation is given in Figure3, and we will study how to construct longer impossible differentials. The following theorem shows the impossible differential distinguisher.Figure 3
One-round differential propagation of New Structure III.Theorem 1.
For New Structure III with SP type round functions, if there existi, j such that (P∗)4i, j = 0 and P−1i, i = 0, the following 23-round differential is impossible:(10)0,α,0,0↛β,0,0,β,where α = ej, β = Pei, and P∗ denotes the characteristic matrix of the linear layer P.Proof.
The 23-round differential propagation of New Structure III is depicted in Figure4. It consists of 13-round encryption and 10-round decryption, whose last round is marked by red color and blue color, respectively. The details of differential propagation are given in Table 2, where ? denotes the unknown difference.
From the encryption direction, the input difference (0,α, 0, 0) propagates 13 rounds and the middle difference becomes (?, α4, ?, ?), where α4 = ΔF4(α). From the decryption direction, the output difference (β, 0, 0, β) is decrypted by 10 rounds to (?, β1⊕β2, ?, ?), where β1 = ΔF−1(β) and β2 = ΔF−2(β). If the middle differences could match each other, there must be(11)α4=β1⊕β2.
It indicates that(12)ΔF4α=ΔF−1β⊕ΔF−2β.
Considering the fact that the round functions are SP type,(13)ΔPSPSPSPSα=ΔS−1P−1β⊕ΔS−1P−1S−1P−1β.
For the left part of equation (13), according to the characteristic matrix method, the condition (P∗)4i, j = 0 indicates that the i-th element of the output ΔPSPSPSPS(α) is not influenced by the j-th element of α. Furthermore, if α = ej which means only the j-th element of α is nonzero, the i-th element of ΔPSPSPSPS(α) is zero.
For the right part of equation (13), when β = Pei, it becomes(14)ΔS−1P−1β⊕ΔS−1P−1β=ΔS−1P−1Pei⊕ΔS−1P−1S−1P−1Pei=ΔS−1ei⊕S−1P−1S−1ei.
Given that the nonlinear bijectiveS−1 does not change the difference pattern, it means that ΔS−1(ei) = ei. So, ΔS−1(ei)⊕ΔS−1P–1S−1(ei) = ei⊕ΔS−1P−1(ei). Moreover, when P−1i,i = 0, the i-th element of P−1(ei) is zero. Furthermore, the i-th element of ΔS−1P−1(ei) and ei⊕ΔS−1P−1(ei) is zero and nonzero, respectively.
For the two parts of equation (13), the i-th element of the left and the right is zero and nonzero, respectively. Thus, equation (13) cannot be established when the restricted conditions of P are satisfied. Therefore, the 23-round impossible differential is constructed.
To achieve the above 23-round impossible differentials, some extra limits of the linear layerP need to be satisfied according to Theorem 1. In fact, they can be achieved. For example, the permutation layer of block cipher SKINNY which was designed at CRYPTO 2016 [34] is(15)P=100000000010010001000000000100100010000010000001000100000100100010000000000000000100000000000000001000000000000000010000000000000000000100100000000010000001000000000100100000000000001001000000100000000010000001000000000100000010000010000000000100000100000016×16.
By calculating the characteristic matrix, (P∗)4 and P−1 are presented below. For P−1, every i (0 ≤ i ≤ 15) satisfies P−1i, i = 0. Therefore, those (i, j) pairs that make P4i, j = 0 will satisfy the condition in Theorem 1. There are 64 possible (i, j) pairs in total.(16)P∗4=1111111111110110111111111111001111111111111110011111111111111100110001111111011001101011111100110011110111111001100111101111110011011100111110101110011011110101011100111111101010111001111101011101011111110110111010111111001101111101111110011011111011111100,(17)P−1=0000100000000000000001000000000000000010000000000000000100000000000001000100010000000010001000100000000100010001000010001000100000000010000000100000000100000001000010000000100000000100000001000001000000000001100000000000100001000000000001000010000000000010.Figure 4
23-round impossible differentials of New Structure III.Table 2
23-round differential propagation of New Structure III.
Rounds0Α00Conditions100α02000α3α00040α1α10α1 = ΔF(α)500α1α16α100α17??α20α2 = ΔF2(α)80??α29α20??10??α3?α3 = ΔF3(α)11???α312α3???13?α4??α4 = ΔF4(α)13?β1⊕β2??14?β1β2?15?β10β216β2β100β2 = ΔF−2(β)170β1001800β1019000β120β1000β1 = ΔF−1(β)210ββ02200ββ23β00β


## 4. Zero-Correlation Linear Hulls of New Structure III

In this section, we first give one-round linear propagation and then construct 23-round zero-correlation linear hulls of New Structure III similarly by constructing impossible differentials. To describe the linear properties better, we first give some notations. ΛF(a) represents all possible output masks of the nonlinear function F when the input mask is a. Similarly, ΛFr(a) represents all possible output masks of the continuous r-round F when the input mask is a, and ΛF-r(a) represents all possible output masks of the continuous r-round F−1 (inverse of F) when the input mask is a.To construct zero-correlation linear hulls, one-round linear propagation should be presented firstly. The property is given below.Proposition 3 (see [26]).
For one round of New Structure III, let (a0, a1, a2, a3) and (b0, b1, b2, b3) be the input mask and output mask, respectively, and we have(18)b0=a1,b1=a2,b2=a3,b3=ΛFa0⊕a1.The above proposition can be easily proved with the linear propagation rules referred to [26]. One-round linear propagation is shown in Figure 5, and we will study how to construct longer zero-correlation linear hulls. The following theorem shows the zero-correlation linear hulls.Figure 5
One-round linear propagation of New Structure III.Theorem 2.
For New Structure III with SP type round functions, if there existi, j such that ((P∗)4)Ti, j = 0 and (P−1)Ti, i = 0, the following 23-round linear hulls are zero-correlation linear hulls:(19)0,0,α,0↛β,β,β,β,where α = ei, β = (P−1)Tej, and P∗ denotes the characteristic matrix of the linear layer P.Proof.
The 23-round linear propagation of New Structure III is depicted in Figure6. It consists of 10-round encryption and 13-round decryption, whose last round is marked by red color and blue color, respectively. The details of the linear propagation are given in Table 3, where ? denotes the unknown mask.
From the encryption direction, the input mask (0, 0,α, 0) will propagate to (α1⊕α2, ?, ?, ?) after 10 rounds with probability 1, where α1 = ΛF(α) and α2 = ΛF2(α). From the decryption direction, the output mask (β, β, β, β) is decrypted to (β4, ?, ?, ?) after 13 rounds with probability 1, where β4 = ΛF−4(β). If the intermediate masks could match each other, there must be(20)α1⊕α2=β4.
It indicates that(21)ΛFα⊕ΛF2α=ΛF−4β.
Considering the fact that the round functions are SP type, the above equation becomes(22)ΛPSα⊕ΛPSPSα=ΛS−1P−1S−1P−1S−1P−1β.
Furthermore, equation (22) can also become the following equation:(23)PΛSα⊕ΛSPSα=ΛS−1P−1S−1P−1S−1P−1β.
Given thatP is linear bijective, equation (23) becomes(24)ΛSα⊕ΛSPSα=ΛP−1S−1P−1S−1P−1S−1P−1β.
Note that the nonlinear bijectiveS does not change the mask pattern. Thus, for the left part of equation (24), if α = ei, ΛS(α)⊕ΛSPS(α) = ΛS(ei)⊕ΛSPS(ei) = ei⊕ΛSP(ei). When (P−1)Ti,i = 0, the i-th element of ΛSP(ei) and ei⊕ΛSP(ei) is zero and nonzero, respectively. Thus, it can be obtained that the i-th element of the left part for equation (24) is nonzero.
For the right part of equation (24), according to Proposition 1, when the mask β = (P−1)Tej, the mask will be ej through P−1. Furthermore, we have(25)ΛP−1S−1P−1S−1P−1S−1P−1β=ΛP−1S−1P−1S−1P−1S−1ej.
Since ((P∗)4)Ti, j = 0, according to the definition of the characteristic matrix and Proposition 1, the i-th element of ΛP−1S–1P–1S–1P–1S−1(ej) is zero.
Therefore, for the two parts of equation (24), the i-th element of the left and the right is zero and nonzero, respectively. So, equation (24) cannot be established when the restricted conditions of P are satisfied. Therefore, the 23-round zero-correlation linear hulls are constructed.
To achieve the above 23-round zero-correlation linear hulls, some extra limits of the linear layerP need to be satisfied according to Theorem 2. Note that they can be achieved as well. For example, for the permutation layer of block cipher SKINNY which is described in Section 3, (P∗)4 and P−1 are presented in equations (16) and (17), respectively. Also, they can easily satisfy the conditions in Theorem 2.Figure 6
23-round zero-correlation linear hulls of New Structure III.Table 3
23-round linear propagation of New Structure III.
Rounds00α0Conditions1000α2α00030α100α1 = ΛF(α)40α1α1050α1α1α16α1α1α1α17?α1⊕α2??α2 = ΛF2(α)8??α1⊕α2?9???α1⊕α210α1⊕α2???10β4???β4 = ΛF−4(β)11?0β3?12??0β313β3??0β3 = ΛF−3(β)1400β2?15?00β216β2?00β2 = ΛF−2(β)1700β1018000β119β1000β1 = ΛF−1(β)200β00210ββ0220βββ23ββββ


## 5. Conclusions

In this paper, we improved impossible differentials and zero-correlation linear hulls of New Structure III to 23 rounds. Both of them are 1 round longer than the best previous works. Firstly, through careful analysis of its differential and linear propagation rules, the intermediate states were derived after some rounds of encryption and decryption. Then, a contradiction was detected by exploiting the details of the permutation layer which should satisfy some constraints. To show the effectiveness of our constructions,P is specified to the permutation matrix of block cipher SKINNY and 64 distinguishers are detected. From the point of the length of distinguishers, our results indicate that New Structure III has weaker resistance against impossible differential and zero-correlation linear attacks than other GFSs such as SMS4 and MARS-like structures whose length of constructed distinguishers was only 12 rounds so far. Although a block cipher structure or concrete cipher may be designed to possess optimal resistance against one attack, it might be vulnerable to other cryptanalysis techniques since different attack methods start from differential perspective of view. Therefore, dedicated and comprehensive efforts will be necessary.



---

*Source: 6515844-2021-10-06.xml*