# Improvements for Finding Impossible Differentials of Block Cipher Structures

Authors: Yiyuan Luo; Xuejia Lai
Journal: Security and Communication Networks
 (2017)

---

## Abstract

We improve Wu and Wang’s method for finding impossible differentials of block cipher structures. This improvement is more general than Wu and Wang’s method where it can find more impossible differentials with less time. We apply it on Gen-CAST256, Misty, Gen-Skipjack, Four-Cell, Gen-MARS, SMS4, MIBS,Camellia⁎, LBlock, E2, and SNAKE block ciphers. All impossible differentials discovered by the algorithm are the same as Wu’s method. Besides, for the 8-round MIBS block cipher, we find 4 new impossible differentials, which are not listed in Wu and Wang’s results. The experiment results show that the improved algorithm can not only find more impossible differentials, but also largely reduce the search time.


---

## Body

## 1. Introduction

Impossible differential cryptanalysis, introduced by Biham et al. [1] and Knudsen [2] independently, is a special case of differential cryptanalysis that uses differentials with probability zero to sieve the right keys from the wrong keys. It is one of the most powerful attacks for block ciphers and is considered in many block cipher designs [3–10]. The best cryptanalytic results for some block ciphers are obtained by impossible differential cryptanalysis [1, 11]. For example, the currently best attack on the 31-round Skipjack is still the impossible differential cryptanalysis by Biham et al. [1].The key step in impossible differential cryptanalysis of a block cipher is to find the longest impossible differential. Given two variablesx1,x2∈F2n, the difference of x1 and x2 is usually denoted as Δx=x1⊕x2. An impossible differential for an n-subblock block cipher is in the form (Δin↛rΔout), where Δin=(Δx1,…,Δxn) and Δout=(Δy1,…,Δyn). (Δin↛rΔout) means the probability of the output difference is Δout after r rounds of a block cipher for an input difference Δin is zero. At the first glance, impossible differentials are obtained manually by observing the block cipher structure. However, since the emergence of impossible differential cryptanalysis, automated techniques for finding impossible differentials have been introduced.The first automated technique is called theShrinking method introduced by Biham et al. [1]. This method is simple but very useful. It only considers truncated differentials whose differences distinguish only between zero and arbitrary nonzero difference. Given a block cipher, the adversary first designs a mini version of this block cipher, which scales down the block cipher but preserves the global structure. Then the adversary exhaustively searches for this mini cipher and obtains some truncated impossible differentials. Usually these truncated impossible differentials of the mini cipher remain impossible differentials in the normal version. This method can deal with most block ciphers in the real world. However, it becomes very slow if the number of subblocks of a block cipher is as large as 16, since exhaustive search on the mini version of this type of cipher is still a heavy load for most computers.The second automated technique is based on the miss in the middle approach. This method combines two differentials, one from the input and the other from the output, both with probability 1. However, these two differentials cannot meet in the middle since they can never be equal in the middle. TheU method [12, 13] and the UID method [14] both belong to this category. In the U method and the UID method, the adversary first represents the block cipher structure as a matrix; then given a differential pair (Δin,Δout), he calculates the m-round intermediate difference from Δin forwardly and the (r-m)-round intermediate difference from Δout backwardly by the matrix method. If there is a contradiction for these two intermediate differences, then an impossible differential (Δin↛rΔout) is verified. Representing a block cipher by the matrix has been a popular method in impossible differential and integral and zero correlation linear cryptanalysis [8, 10, 15–20].In [21], Wu and Wang extend the U-method and UID method to a more generalized method which does not use the miss in the middle approach. They treat the r-round block cipher structure as a system of equations, which describe the propagation behavior of differences in the inner primitives, especially sbox permutations or branch swapping of the block cipher structure. To judge if a truncated differential (Δin,Δout) is impossible, they predict information about unknown variables from the known ones iteratively. Finally a truncated differential is verified by checking the constrained conditions in the system. This method is similar to a linear programming method for solving optimization problems.In [22], Sun et al. show that Wu and Wang’s automatic search method can find all impossible differentials of a cipher that are independent of the choices of the inner primitives. However, Wu and Wang’s method can only find all truncated impossible differentials since the choice of truncated difference may result in missing some impossible differentials. Wu and Wang’s method only considers differences Δin=(x1,…,xn) and Δout=(y1,…,yn), where xi and yi are zero or nonzero values. They assign an indicator to indicate the choice of xi and yi, representing by 0 a subblock without difference and by 1 a subblock with a difference. The relationships between nonzero differences have been omitted. For example, yi may be equal to some xj, where 1≤i,j≤n. If some linear constraints between nonzero variables in Δin and Δout are needed, Wu and Wang claimed their method could still work by translating all linear constraints into the system of equations. However, this method increases the run complexity and implementation of the search method. Since it changes the equation system for every value of (Δin,Δout) and if the relationship between Δin and Δout is complicated, the matrix will be very large.The idea of the UID method is that it represents the differential with symbols and utilizes the propagation property of the linear accumulated symbols. The idea of the Wu-Wang method is to utilize solving linear equations to determine an impossible differential. We show that the Wu-Wang method can be improved by combining the idea of the UID method and Wu-Wang method. Instead of using 1 to represent the nonzero difference, we use a letter symbol to represent a difference and different symbols represent different nonzero values. This method can represent more relationships between these subblocks. For example, ifΔin=(a,0,0,a) and Δout=(a,0,0,b) for a 4-subblock structure where a and b are different nonzero values, then we have x1=x4=y1 and y4≠x1. In our method, the matrix of the system does not need to be changed with (Δin,Δout). We also improve the Wu-Wang method by simplifying the test of whether there are solutions for linear systems. Since the most time consuming part is the matrix operation, our improved method can find more impossible differentials in less time.We implement the method in java language and apply it to many block cipher structures, including Gen-CAST256 [15], Gen-Skipjack [23], Four-Cell [24], Gen-MARS [12], Gen-RC6 [23], SMS4 [14], Misty [25], MIBS [26], Camellia∗ [27], LBlock [28], E2 [29], and SNAKE [30] ones. For these block ciphers, we rediscover all known impossible differentials. Especially for the 8-round MIBS cipher, we find 4 new impossible differentials, which are not listed in Wu and Wang’s work. Our improvement largely reduced the run time for finding impossible differentials. In [31], the results for MIBS, LBlock, and E2 are obtained in a few hours on a 2.66 GHz processor with MAGMA package. However, our results for MIBS, LBlock, and E2 are obtained within 10 seconds on a 2.20 GHz processor.


## 2. Preliminaries

In this section we introduce some basic concepts and notions used in this paper. We first introduce the block cipher structures. Next we review the solvability of a system of linear equations.


### 2.1. Block Cipher Structures

There are mainly two block cipher structures, which are the Feistel structure and its generalizations and the substitute permutation network (SPN). The round function of most of those structures consists of three basic operations: the sbox look-up, the exclusive-or addition (Xor), and the branch swapping, where the only nonlinear component is the sbox look-up operation. In differential cryptanalysis, the Xor differences of plaintext/ciphertext pairs are considered; we omit the key and constant addition since they have no relevance to our analysis. We assume that a block cipher structure hasn subblocks (branches), and the input and output differences are denoted by (Δx1,…,Δxn) and (Δy1,…,Δyn), respectively.


### 2.2. The Solvability of a Linear System

Now we review the basics in linear algebra of determining the solvability of a system of linear equations. Letm,  n be two positive integers, m<n; let Ax=b be a system of m linear equations with n variables, where A is m×n matrix over F2; and x=(x1,…,xn) and b=(b1,…,bm) are two bit vectors; then the augmented m×(n+1) matrix B=A∣b can determine the solvability of the linear system.A regular method is to deduce the reduced row echelon form (a.k.a. row canonical form) of matrixB by Gauss-Jordan elimination algorithm. The reduced row echelon form of a matrix is unique and denoted by B′. One starts to check B′ from the last row to the first, to see if there exists a row in which the first n entries are zeros and the last entry is nonzero. If there are such rows, then the linear system has no solution. For example, if the augmented matrix B of a linear system in reduced row echelon form is (1)B′=100b1010b2000b3,where b3 is nonzero, then the linear system has no solution.


## 2.1. Block Cipher Structures

There are mainly two block cipher structures, which are the Feistel structure and its generalizations and the substitute permutation network (SPN). The round function of most of those structures consists of three basic operations: the sbox look-up, the exclusive-or addition (Xor), and the branch swapping, where the only nonlinear component is the sbox look-up operation. In differential cryptanalysis, the Xor differences of plaintext/ciphertext pairs are considered; we omit the key and constant addition since they have no relevance to our analysis. We assume that a block cipher structure hasn subblocks (branches), and the input and output differences are denoted by (Δx1,…,Δxn) and (Δy1,…,Δyn), respectively.


## 2.2. The Solvability of a Linear System

Now we review the basics in linear algebra of determining the solvability of a system of linear equations. Letm,  n be two positive integers, m<n; let Ax=b be a system of m linear equations with n variables, where A is m×n matrix over F2; and x=(x1,…,xn) and b=(b1,…,bm) are two bit vectors; then the augmented m×(n+1) matrix B=A∣b can determine the solvability of the linear system.A regular method is to deduce the reduced row echelon form (a.k.a. row canonical form) of matrixB by Gauss-Jordan elimination algorithm. The reduced row echelon form of a matrix is unique and denoted by B′. One starts to check B′ from the last row to the first, to see if there exists a row in which the first n entries are zeros and the last entry is nonzero. If there are such rows, then the linear system has no solution. For example, if the augmented matrix B of a linear system in reduced row echelon form is (1)B′=100b1010b2000b3,where b3 is nonzero, then the linear system has no solution.


## 3. Mathematical Models for Finding IDs of Block Cipher Structures

Our improvement is based on Wu and Wang’s method. If the nonlinear sboxSi in a block cipher structure is a permutation, then there is a constraint on the input difference xi and output difference yi for Si; that is, xi and yi can only both be zero or both be nonzero, denoted by xi~yi. The intermediate value of a block cipher structure is called the state. The state is updated with the round structure. In order to find impossible differential for an r-round block cipher structure, we first set differential variables for the states and then transform the r-round block cipher structure into a system of linear equations and constraints, denoted by S. Then for a given differential (Δin,Δout), where Δin=(a1,…,an) and Δout=(b1,…,bn), we can check if it is impossible by solving S with initial values (a1,…,an,b1,…,bn); if S has no solution, then Δin↛rΔout.Here we take the 5-round Feistel structure as an example. We first assign differential variables for 5-round Feistel structure. In Figure1, Fi,  1≤i≤5 are permutations; the output difference of Fi for input difference Xi is Yi; thus Xi~Yi. According to the computation graph of 5-round Feistel structure, we obtain the following system S of equations and constraints: (2)X0⊕X2⊕Y1=0,X1~Y1,X1⊕X3⊕Y2=0,X2~Y2,X2⊕X4⊕Y3=0,X3~Y3,X3⊕X5⊕Y4=0,X4~Y4,X4⊕X6⊕Y5=0,X5~Y5. In order to check if (a,0)→(a,0) is an impossible differential where a is a nonzero value, we solve the above system with X0=a,  X1=0,  X5=0, and  X6=a. Since X1~Y1 and X5~Y5 we have Y1=0 and Y5=0. From linear equations of S, we get Y3=0; thus X3=0 since X3~Y3; next from linear equations S we obtain Y2=0; however X2=a and X2~Y2; thus the system S has no solution and (a,0)→(a,0) is an impossible differential for 5-round Feistel structure.Figure 1
State variables for 5-round Feistel structure.Now we want to find all impossible differentials for 5-round Feistel structure; we enumerate all the possible differential pairs(Δin,Δout)∈{(0,a),(a,0),(a,a),(0,b),(b,0),(b,b),(b,a),(a,b)}, where a and b are two different nonzero values. For each value of (Δin,Δout), we judge if it is an impossible differential; after all cases are tested, we will find all impossible differentials.Thus the general algorithm for finding allr-round impossible differentials for a block cipher structure is outlined as follows:(1)
Generate all the possible differential pairs(Δin,Δout) in a set D.(2)
Assign differential variables according to the computation figure of ther-round block cipher structure. Generate the system S of linear equations and constraints with the differential variables.(3)
For each(Δin,Δout)∈D, solve the system S with initial value (Δin,Δout) and check if S has no solution. If there is no solution, then (Δin→Δout) is an impossible differential. After all cases are checked we obtain all impossible differentials.


## 4. The Detailed Algorithm

In this section we describe the detailed algorithm and implementation details.


### 4.1. Generate All Possible Differential Pairs

We use symbolsai,  bi,  1≤i≤n, to denote different 2n as the nonzero values. For a block cipher structure, the input difference is (ΔI1,…,ΔIn), where ΔIi∈{0,a1,…,an}, and the output difference is (ΔO1,…,ΔOn), where ΔOi∈{0,a1,…,an,b1,…,bn}. Note that the input difference and output difference will not be zero since this will be trivial in differential cryptanalysis. Thus there are total ((n+1)n-1)·((2n+1)n-1) differential pairs. This value is large for many block cipher structures.However, an impossible differential(ΔI1,…,ΔIn)↛(ΔO1,…,ΔOn) for a block cipher structure is usually simple; that is, there are very few nonzero values in (ΔI1,…,ΔIn) and (ΔO1,…,ΔOn). Since the input or output differential are complicate, it will propagate fast due to the round structure of the cipher. Thus it is reasonable to consider simple differential pairs. Actually all the impossible differentials found for block cipher structures in the literature are simple.In this paper we only consider the input difference(ΔI1,…,ΔIn), where ΔIi∈{0,a}, and the output difference (ΔO1,…,ΔOn), where ΔOi∈{0,a,b}. Thus there are total (2n-1)(3n-1) differential pairs that need to be checked.


### 4.2. Generate the SystemS

Given a block cipher structure, we first need to draw the computational figure and assign differential variables, as introduced in the analysis of 5-round Feistel structure. This step is varying according to different block cipher structures. However, since most block cipher structures iterate the same round structure for several times, these variables are regular and easy to implement in a computer program. As in the analysis of 5-round Feistel structure, the input difference of a nonlinear permutation is denoted by variableXi and the output difference is denoted by variable Yi. Thus if we see a variable Yi, it must be some output difference of a nonlinear permutation.For a block cipher structure withr rounds, there are p variables Xi,  0≤i≤p, and q numbers of variables Yi,  1≤i≤q. The numbers p and q are determined by the round structure and the round number r. For the r-round Feistel structure, p=r+2 and q=r. We first denote all variables in a variable vector as (3)X¯=X0,…,Xp-1,Y1,…,Yq,and then linear equations in system S can be written as MX¯=0, where M is a kr×(p+q) matrix over F2 and0 is a (p+q)-dimensional zero vector, where k is the number of linear equations in one round of the block cipher structure. The augmented matrix of these linear equations is B=M∣0. For the 5-round Feistel structure, the augmented matrix B is denoted in Table 1.Table 1
The5×13 augmented matrix of 5-round Feistel structure.
0
1
2
3
4
5
6
7
8
9
10
11
12
X
0
X
1
X
2
X
3
X
4
X
5
X
6
Y
1
Y
2
Y
3
Y
4
Y
5
0
1
1
0
1
0
0
0
0
1
0
0
0
0
0
2
0
1
0
1
0
0
0
0
1
0
0
0
0
3
0
0
1
0
1
0
0
0
0
1
0
0
0
4
0
0
0
1
0
1
0
0
0
0
1
0
0
5
0
0
0
0
1
0
1
0
0
0
0
1
0The set of constraints inS can be maintained as a map N. Let id(Xi) denote the index of the variable Xi in vector X¯; given a constraint Xi~Yi, we add (id(Xi),id(Yi)) into the map N. For the 5-round Feistel structure, N={1,7,2,8,3,9,4,10,5,11}. In the real implementation, it is noted that, for most block cipher structures, the distance between constraints Xi and Yi is fixed and determined by the round structure and the round number; that is, id(Yi)-id(Xi) is a constant. For example, the distance of constraints  Xi and Yi for a r-round Feistel structure is r+1. Thus the map N is not needed to be implemented but only the fixed index distance is needed. This observation facilitates the real implementation of the algorithm.


### 4.3. Determine the Solvability ofS

In the beginning, we assign a symbol “?” to each variable in the variable vectorX¯, which means every variable is undetermined. Given a differential pair (Δin,Δout), we need to check if there exist solutions of the system S with the initial value (Δin,Δout). We first need to initialize the variable vector X¯ according to (Δin,Δout). As in the 5-round Feistel structure, for a differential pair Δin=(a,0),  Δout=(a,0), the variable vector X¯ is initialized as follows:X0X1X2X3X4X5X6Y1Y2Y3Y4Y5a0???0a?????For a constraintXi~Yi, the algorithm updates (Xi,Yi) and detects contradictions as follows.(i)
The valueXi is updated:
(a)
IfXi=0 and Yi= ?, then Yi is set to 0.(b)
IfXi is a nonzero symbol and Yi= ?, then Yi is set to the nonzero symbol “∗.”(c)
IfXi=0 and Yi is an nonzero symbol, then we obtain a contradiction.(ii)
The valueYi is updated:
(a)
IfYi=0 and Xi= ?, then Xi is set to 0.(b)
IfYi=0 and Xi is an nonzero symbol, then we obtain a contradiction.We use⊕ to denote the symmetrical difference (Xor) of X1 and X2. For example, if X1={a1} and X2={b1}, then X1⊕X2={a1,b1}; if X1={a1} and X2={0}, then X1⊕X2={a1}; if X1={a1} and X2={a1,b1}, then X1⊕X2={b1}.The functionUpdateMatrix(B,X¯) updates the augmented matrix B according to the variable vector X¯. If the ith variable in X¯ is 0, then the corresponding ith column of B is set to a zero vector. As in [21], this method keeps solutions of the augmented matrix B unchanged. If X¯i is not in the set {0,?,∗}, we check each row of B; if the value of the ith column at the rth row Br,i is 1, then we set Xor X¯i to the last element of the rth row of B and set Br,i to 0 (Algorithm 1).Algorithm 1:Function UpdateMatrix(B,X¯).
// Update the augmented matrix  B  according to the variable vector  X¯
(1)K← the size of X¯;
(2)for  i←0  to  K-1  do
(3)t←X¯[i];
(4)if  t  is  0  then
(5)Every element of the ith column of B is set to 0.
(6)else if  t  is not “?” and t  is not “∗”   then
(7)L← the number of rows of B;
(8)for  r←0  to  L-1  do
(9)if  B[r,i]  is  1  then
(10)B[r,i]←0;
(11)B[r,K-1]←B[r,K-1]⊕t;
(12)end
(13)end
(14)end
(15)endThe functionUpdateVector(X¯,N,j,J) updates the jth variable X¯j with the value J; at the same time all constraints in N are maintained. As described in the beginning of this subsection, the function updates X¯j with the value J by checking each constraint in N and returns true if it succeeds or false if there is a contradiction. There are many subcases, as described in the detailed algorithm. During the updating process, there may be contradictions. For example, if X¯j={a} and J={a,b} which means J=a⊕b, there is a contradiction since a⊕b can never be a. If J is {0} but the corresponding variable which is the sbox output of X¯j is nonzero or J is {0} but the corresponding variable which is the sbox input of X¯j is nonzero, there will be contradictions (Algorithm 2).Algorithm 2:Function UpdateVector(X¯,N,j,J).
//  Update the variable vector  X¯  according to the variable  (j,J)  where  J  is the value
of the  jth variable in  X¯. N  is the array of constraints.
input: the variable vector X¯, the constraint array N, (j,J).
output: A boolean flag indicates if the update procedure success.
(1) flag←true;
(2)foreach  a∈N  do
(3)k0←a[0]; k1←a[1];
(4)if  j  is equal to  k0  then
(5)if  J⊕X¯k0  is not 0  then
(6)flag ←false; //  Ex. J=a⊕b  but  X¯k0=a, a contradiction.
(7)return  flag;
(8)else if  J  is 0 and  X¯k0  is ? then
(9)if  X¯[k1]  is not 0 then flag ←false;
(10)return  flag;
(11)end
(12)X¯k0←0;  X¯k1←0;
(13)else if  J  is a nonzero value  then
(14)X¯k0←J;  X¯k1←∗;
(15)end
(16)else if  j  is equal to  k1  then
(17)if  J⊕X¯k1  is not 0 then flag ←false
(18)return  flag;
(19)else if  X¯k1  is ? and  J  is 0 then
(20)X¯k1←0;  X¯k0←0;
(21)end
(22)end
(23)end
(24)return  flag;The functionReducedRowEchelon(B) transforms the ι×κ matrix B into the reduced row echelon form by Gauss-Elimination algorithm. Note that every element in the first κ-1 columns of B is in F2, while elements in the last column of B are represented by a set of symbols. Thus the Xor operation in the last column of B is the symmetrical difference operation. The readers can refer to [32] for the detailed algorithm of transforming a matrix into the reduced row echelon form.The detailed algorithm for checking if a differential is impossible is described in Algorithm3. In Algorithm 3, the variable vector X¯ is first initialized according to the differential pair (Δin,Δout) and the constraint array N. Then the algorithm continues checks if there is a contradiction with a loop test until B and X¯ are not updated any more. During the loop the algorithm first updates B according to X¯ by theUpdateMatrix(B,X¯) function and then transforms B into the reduced row echelon form by theReducedRowEchelon(B) function to see if B has solutions. If B has no solutions, the algorithm obtains a contradiction and stops. Otherwise if there exists a solution for a variable from the reduced row echelon form, the index and the value of the variable are denoted as (j,J). The algorithm updates the variable vector X¯ with (j,J) by theUpdateVector(X¯,N,j,J) function; if the updating process returns false, a contradiction is obtained and the algorithm stops; otherwise, the algorithm continues to run.Algorithm 3:The algorithm for checking an impossible differential.
input: A differential pair (Δin,Δout) and the system S
output: A boolean flag indicates if (Δin,Δout) is an impossible differential
(1)B is the ι×κ augmented matrix of S;
(2)X¯ is the κ-1 dimension variable vector;
(3)N is the map of constraints of S;
(4) flag←false;
(5) index←true;
(6) Initialize every variable inX¯ according to (Δin,Δout) and the constraints in N;
(7)while  index  do
(8)UpdateMatrix (B, X¯) // Update  B  according to  X¯;
/
∗  Transform  B  into the reduced-row-echelon form by Gauss-Jordan Elimination  ∗/
(9)ReducedRowEchelon (B);
(10)if  B has no solution then
(11)flag←true;
(12)break;
(13)else
(14)index ← false;
(15)count← 0;
(16)for  i←ι   to  1 do
(17)v→← Row i of B;
(18)if the sum of the first κ-1 elements of v→ is 1 then
(19)j← the index of the element 1 in v→;
(20)J← the last element of v→; //the solution of the  jth  variable in  X¯
(21)/∗  update the variable vector  X¯  with  (j,J)  and return true if there is
no contradiction and return false otherwise. ∗/
(22)b←UpdateVector (X¯, N, j, J);
(23)if  b is false then
(24)flag ← true;
(25)return flag;
(26)else
(27)index ← true;
(28)end
(29)end
(30)end
(31)end
(32)end
(33)return  flag;


### 4.4. Complexity

For theι×κ matrix B and the κ-1 dimension vector X¯, the time complexity of the functionUpdateMatrix is ι·κ, the time complexity of the functionReducedRowEchelon is ι2·κ, and the time complexity of the functionUpdateVector is a constant c, while loop continues running κ/2 times since there at most κ-1 values in X¯ and in each loop either 2 variables are updated or there is a contradiction. Thus the total complexity of the algorithm is (c/2)·ι2κ2, where c is a small constant. The space complexity is dominated by storing the matrix B and is about ι·κ. The time complexity of the Wu-Wang method is T·ι2κ2 and this T is much larger than our c. The Wu-Wang method stores 3 matrices; thus its space complexity is at least triple our method.


### 4.5. Comparison with Previous Method

In [31], Wu and Wang proved that the U-method and the UID method are specific cases of the Wu-Wang method. They found that their method can find longer impossible differential for the MIBS cipher than by U-method and the UID method. However, in the UID method, for an impossible differential pair ((ΔI1,…,ΔIn),(ΔO1,…,ΔOn)), the relationship between input variables and output variables is considered since UID method uses symbols to denote values. For example, the UID method considers the relation between ΔIi and ΔOj and checks if they are equal; however the U-method and Wu-Wang method only use 0 and 1 to denote zero and nonzero values, which omit the relationship between input and output differentials.Our improved method combines the advantages of the UID method and Wu-Wang method. Every impossible differential found by the UID method and Wu-Wang method can be found by our improved method. As Wu and Wang’s method, impossible differentials found by our improved method must be correct if the algorithm is implemented correctly. Compared with Wu and Wang’s method, our improved method is more complete. The symbol representation of a difference can represent more relationships between different difference values. Thus it can find more impossible differentials and the matrixB does not change with different values of (Δin,Δout) in the beginning of the algorithm, while, in the Wu-Wang method, to add linear relationships between nonzero values in (Δin,Δout), the matrix B must change with different values of (Δin,Δout). This will consume more time during the run of the algorithm.The most time consuming part in the algorithm is the matrix operation. To check if the augmented matrix has any solutions, the Wu-Wang method needs to compute the rank of the matricesM and B. We show that this step is not required since we can check the solvability of the system from the reduced row echelon form of the matrix B, as introduced in the preliminaries section. Thus our improvement largely reduces the search time of finding impossible differentials of a block cipher structure.


## 4.1. Generate All Possible Differential Pairs

We use symbolsai,  bi,  1≤i≤n, to denote different 2n as the nonzero values. For a block cipher structure, the input difference is (ΔI1,…,ΔIn), where ΔIi∈{0,a1,…,an}, and the output difference is (ΔO1,…,ΔOn), where ΔOi∈{0,a1,…,an,b1,…,bn}. Note that the input difference and output difference will not be zero since this will be trivial in differential cryptanalysis. Thus there are total ((n+1)n-1)·((2n+1)n-1) differential pairs. This value is large for many block cipher structures.However, an impossible differential(ΔI1,…,ΔIn)↛(ΔO1,…,ΔOn) for a block cipher structure is usually simple; that is, there are very few nonzero values in (ΔI1,…,ΔIn) and (ΔO1,…,ΔOn). Since the input or output differential are complicate, it will propagate fast due to the round structure of the cipher. Thus it is reasonable to consider simple differential pairs. Actually all the impossible differentials found for block cipher structures in the literature are simple.In this paper we only consider the input difference(ΔI1,…,ΔIn), where ΔIi∈{0,a}, and the output difference (ΔO1,…,ΔOn), where ΔOi∈{0,a,b}. Thus there are total (2n-1)(3n-1) differential pairs that need to be checked.


## 4.2. Generate the SystemS

Given a block cipher structure, we first need to draw the computational figure and assign differential variables, as introduced in the analysis of 5-round Feistel structure. This step is varying according to different block cipher structures. However, since most block cipher structures iterate the same round structure for several times, these variables are regular and easy to implement in a computer program. As in the analysis of 5-round Feistel structure, the input difference of a nonlinear permutation is denoted by variableXi and the output difference is denoted by variable Yi. Thus if we see a variable Yi, it must be some output difference of a nonlinear permutation.For a block cipher structure withr rounds, there are p variables Xi,  0≤i≤p, and q numbers of variables Yi,  1≤i≤q. The numbers p and q are determined by the round structure and the round number r. For the r-round Feistel structure, p=r+2 and q=r. We first denote all variables in a variable vector as (3)X¯=X0,…,Xp-1,Y1,…,Yq,and then linear equations in system S can be written as MX¯=0, where M is a kr×(p+q) matrix over F2 and0 is a (p+q)-dimensional zero vector, where k is the number of linear equations in one round of the block cipher structure. The augmented matrix of these linear equations is B=M∣0. For the 5-round Feistel structure, the augmented matrix B is denoted in Table 1.Table 1
The5×13 augmented matrix of 5-round Feistel structure.
0
1
2
3
4
5
6
7
8
9
10
11
12
X
0
X
1
X
2
X
3
X
4
X
5
X
6
Y
1
Y
2
Y
3
Y
4
Y
5
0
1
1
0
1
0
0
0
0
1
0
0
0
0
0
2
0
1
0
1
0
0
0
0
1
0
0
0
0
3
0
0
1
0
1
0
0
0
0
1
0
0
0
4
0
0
0
1
0
1
0
0
0
0
1
0
0
5
0
0
0
0
1
0
1
0
0
0
0
1
0The set of constraints inS can be maintained as a map N. Let id(Xi) denote the index of the variable Xi in vector X¯; given a constraint Xi~Yi, we add (id(Xi),id(Yi)) into the map N. For the 5-round Feistel structure, N={1,7,2,8,3,9,4,10,5,11}. In the real implementation, it is noted that, for most block cipher structures, the distance between constraints Xi and Yi is fixed and determined by the round structure and the round number; that is, id(Yi)-id(Xi) is a constant. For example, the distance of constraints  Xi and Yi for a r-round Feistel structure is r+1. Thus the map N is not needed to be implemented but only the fixed index distance is needed. This observation facilitates the real implementation of the algorithm.


## 4.3. Determine the Solvability ofS

In the beginning, we assign a symbol “?” to each variable in the variable vectorX¯, which means every variable is undetermined. Given a differential pair (Δin,Δout), we need to check if there exist solutions of the system S with the initial value (Δin,Δout). We first need to initialize the variable vector X¯ according to (Δin,Δout). As in the 5-round Feistel structure, for a differential pair Δin=(a,0),  Δout=(a,0), the variable vector X¯ is initialized as follows:X0X1X2X3X4X5X6Y1Y2Y3Y4Y5a0???0a?????For a constraintXi~Yi, the algorithm updates (Xi,Yi) and detects contradictions as follows.(i)
The valueXi is updated:
(a)
IfXi=0 and Yi= ?, then Yi is set to 0.(b)
IfXi is a nonzero symbol and Yi= ?, then Yi is set to the nonzero symbol “∗.”(c)
IfXi=0 and Yi is an nonzero symbol, then we obtain a contradiction.(ii)
The valueYi is updated:
(a)
IfYi=0 and Xi= ?, then Xi is set to 0.(b)
IfYi=0 and Xi is an nonzero symbol, then we obtain a contradiction.We use⊕ to denote the symmetrical difference (Xor) of X1 and X2. For example, if X1={a1} and X2={b1}, then X1⊕X2={a1,b1}; if X1={a1} and X2={0}, then X1⊕X2={a1}; if X1={a1} and X2={a1,b1}, then X1⊕X2={b1}.The functionUpdateMatrix(B,X¯) updates the augmented matrix B according to the variable vector X¯. If the ith variable in X¯ is 0, then the corresponding ith column of B is set to a zero vector. As in [21], this method keeps solutions of the augmented matrix B unchanged. If X¯i is not in the set {0,?,∗}, we check each row of B; if the value of the ith column at the rth row Br,i is 1, then we set Xor X¯i to the last element of the rth row of B and set Br,i to 0 (Algorithm 1).Algorithm 1:Function UpdateMatrix(B,X¯).
// Update the augmented matrix  B  according to the variable vector  X¯
(1)K← the size of X¯;
(2)for  i←0  to  K-1  do
(3)t←X¯[i];
(4)if  t  is  0  then
(5)Every element of the ith column of B is set to 0.
(6)else if  t  is not “?” and t  is not “∗”   then
(7)L← the number of rows of B;
(8)for  r←0  to  L-1  do
(9)if  B[r,i]  is  1  then
(10)B[r,i]←0;
(11)B[r,K-1]←B[r,K-1]⊕t;
(12)end
(13)end
(14)end
(15)endThe functionUpdateVector(X¯,N,j,J) updates the jth variable X¯j with the value J; at the same time all constraints in N are maintained. As described in the beginning of this subsection, the function updates X¯j with the value J by checking each constraint in N and returns true if it succeeds or false if there is a contradiction. There are many subcases, as described in the detailed algorithm. During the updating process, there may be contradictions. For example, if X¯j={a} and J={a,b} which means J=a⊕b, there is a contradiction since a⊕b can never be a. If J is {0} but the corresponding variable which is the sbox output of X¯j is nonzero or J is {0} but the corresponding variable which is the sbox input of X¯j is nonzero, there will be contradictions (Algorithm 2).Algorithm 2:Function UpdateVector(X¯,N,j,J).
//  Update the variable vector  X¯  according to the variable  (j,J)  where  J  is the value
of the  jth variable in  X¯. N  is the array of constraints.
input: the variable vector X¯, the constraint array N, (j,J).
output: A boolean flag indicates if the update procedure success.
(1) flag←true;
(2)foreach  a∈N  do
(3)k0←a[0]; k1←a[1];
(4)if  j  is equal to  k0  then
(5)if  J⊕X¯k0  is not 0  then
(6)flag ←false; //  Ex. J=a⊕b  but  X¯k0=a, a contradiction.
(7)return  flag;
(8)else if  J  is 0 and  X¯k0  is ? then
(9)if  X¯[k1]  is not 0 then flag ←false;
(10)return  flag;
(11)end
(12)X¯k0←0;  X¯k1←0;
(13)else if  J  is a nonzero value  then
(14)X¯k0←J;  X¯k1←∗;
(15)end
(16)else if  j  is equal to  k1  then
(17)if  J⊕X¯k1  is not 0 then flag ←false
(18)return  flag;
(19)else if  X¯k1  is ? and  J  is 0 then
(20)X¯k1←0;  X¯k0←0;
(21)end
(22)end
(23)end
(24)return  flag;The functionReducedRowEchelon(B) transforms the ι×κ matrix B into the reduced row echelon form by Gauss-Elimination algorithm. Note that every element in the first κ-1 columns of B is in F2, while elements in the last column of B are represented by a set of symbols. Thus the Xor operation in the last column of B is the symmetrical difference operation. The readers can refer to [32] for the detailed algorithm of transforming a matrix into the reduced row echelon form.The detailed algorithm for checking if a differential is impossible is described in Algorithm3. In Algorithm 3, the variable vector X¯ is first initialized according to the differential pair (Δin,Δout) and the constraint array N. Then the algorithm continues checks if there is a contradiction with a loop test until B and X¯ are not updated any more. During the loop the algorithm first updates B according to X¯ by theUpdateMatrix(B,X¯) function and then transforms B into the reduced row echelon form by theReducedRowEchelon(B) function to see if B has solutions. If B has no solutions, the algorithm obtains a contradiction and stops. Otherwise if there exists a solution for a variable from the reduced row echelon form, the index and the value of the variable are denoted as (j,J). The algorithm updates the variable vector X¯ with (j,J) by theUpdateVector(X¯,N,j,J) function; if the updating process returns false, a contradiction is obtained and the algorithm stops; otherwise, the algorithm continues to run.Algorithm 3:The algorithm for checking an impossible differential.
input: A differential pair (Δin,Δout) and the system S
output: A boolean flag indicates if (Δin,Δout) is an impossible differential
(1)B is the ι×κ augmented matrix of S;
(2)X¯ is the κ-1 dimension variable vector;
(3)N is the map of constraints of S;
(4) flag←false;
(5) index←true;
(6) Initialize every variable inX¯ according to (Δin,Δout) and the constraints in N;
(7)while  index  do
(8)UpdateMatrix (B, X¯) // Update  B  according to  X¯;
/
∗  Transform  B  into the reduced-row-echelon form by Gauss-Jordan Elimination  ∗/
(9)ReducedRowEchelon (B);
(10)if  B has no solution then
(11)flag←true;
(12)break;
(13)else
(14)index ← false;
(15)count← 0;
(16)for  i←ι   to  1 do
(17)v→← Row i of B;
(18)if the sum of the first κ-1 elements of v→ is 1 then
(19)j← the index of the element 1 in v→;
(20)J← the last element of v→; //the solution of the  jth  variable in  X¯
(21)/∗  update the variable vector  X¯  with  (j,J)  and return true if there is
no contradiction and return false otherwise. ∗/
(22)b←UpdateVector (X¯, N, j, J);
(23)if  b is false then
(24)flag ← true;
(25)return flag;
(26)else
(27)index ← true;
(28)end
(29)end
(30)end
(31)end
(32)end
(33)return  flag;


## 4.4. Complexity

For theι×κ matrix B and the κ-1 dimension vector X¯, the time complexity of the functionUpdateMatrix is ι·κ, the time complexity of the functionReducedRowEchelon is ι2·κ, and the time complexity of the functionUpdateVector is a constant c, while loop continues running κ/2 times since there at most κ-1 values in X¯ and in each loop either 2 variables are updated or there is a contradiction. Thus the total complexity of the algorithm is (c/2)·ι2κ2, where c is a small constant. The space complexity is dominated by storing the matrix B and is about ι·κ. The time complexity of the Wu-Wang method is T·ι2κ2 and this T is much larger than our c. The Wu-Wang method stores 3 matrices; thus its space complexity is at least triple our method.


## 4.5. Comparison with Previous Method

In [31], Wu and Wang proved that the U-method and the UID method are specific cases of the Wu-Wang method. They found that their method can find longer impossible differential for the MIBS cipher than by U-method and the UID method. However, in the UID method, for an impossible differential pair ((ΔI1,…,ΔIn),(ΔO1,…,ΔOn)), the relationship between input variables and output variables is considered since UID method uses symbols to denote values. For example, the UID method considers the relation between ΔIi and ΔOj and checks if they are equal; however the U-method and Wu-Wang method only use 0 and 1 to denote zero and nonzero values, which omit the relationship between input and output differentials.Our improved method combines the advantages of the UID method and Wu-Wang method. Every impossible differential found by the UID method and Wu-Wang method can be found by our improved method. As Wu and Wang’s method, impossible differentials found by our improved method must be correct if the algorithm is implemented correctly. Compared with Wu and Wang’s method, our improved method is more complete. The symbol representation of a difference can represent more relationships between different difference values. Thus it can find more impossible differentials and the matrixB does not change with different values of (Δin,Δout) in the beginning of the algorithm, while, in the Wu-Wang method, to add linear relationships between nonzero values in (Δin,Δout), the matrix B must change with different values of (Δin,Δout). This will consume more time during the run of the algorithm.The most time consuming part in the algorithm is the matrix operation. To check if the augmented matrix has any solutions, the Wu-Wang method needs to compute the rank of the matricesM and B. We show that this step is not required since we can check the solvability of the system from the reduced row echelon form of the matrix B, as introduced in the preliminaries section. Thus our improvement largely reduces the search time of finding impossible differentials of a block cipher structure.


## 5. Applications and Experiment Results

We implement the algorithm in java language and apply it to many block cipher structures, including Gen-CAST256 [33], Misty [25], Gen-Skipjack [23], Four-Cell [24], Gen-MARS [33], Gen-RC6 [33], SMS4 [34], MIBS [26], Camellia∗ [27, 31], LBlock [28], E2 [29], and SNAKE [30]. We present the java code of this algorithm and complete impossible differential results in GitHub [35]. To reduce the space of this paper, we present some of the impossible differential results in Table 2. The fileImpossible Differential.txt in [35] lists the complete impossible differential results for these block cipher structures. Most impossible differentials discovered by our algorithm are the same as the Wu-Wang method.Table 2
Summary of impossible differentials (IDs) of some well-known block ciphers structures found by different methods.
Block cipher
UID [14]
Wu-Wang [31]
This paper
Gen-Skipjack
16:(0,0,0,a)↛16(b,0,0,b)
—
Same as UID
Gen-CAST256
19:(0,0,0,a)↛19(a,0,0,0)
—
Same as UID
Four-Cell
18:(a,0,0,0)↛18(b,b,0,0)
—
Same as UID
Gen-MARS
11:(0,0,0,a)↛11(a,0,0,0)
—
Same as UID
Gen-RC6
9:(0,0,a,0)↛9(0,a,0,0)
—
Same as UID
9:(a,0,0,0)↛9(0,0,0,a)
SMS4
11:(0,0,0,a)↛11(a,0,0,0)
—
Same as UID
Misty
—
—
4
:
(
0
,
a
)
↛
4
(
b
,
b
)
SNAKE
—
—
11
:
(
0,0
,
0,0
,
0,0
,
a
,
0
)
↛
11
(
0,0
,
b
,
0,0
,
0,0
,
0
)
Camellia∗
—
8-round, 4 IDs
Same as Wu-Wang
MIBS
—
8-round, 6 IDs
8-round, 10 IDs
LBlock
—
14-round, 80 IDs
Same as Wu-Wang
E2
—
6-round, 56 IDs
Same as Wu-WangMoreover, for the 8-round MIBS, we find new 4 impossible differentials, which are not found by the Wu-Wang method since these 4 new impossible differentials are not simple truncated impossible differentials. MIBS is a 16-subblock Feistel structure with substitution and permutation (SP) round function. In the SP round function, the 8 subblocks are first substituted by 8 sboxes; then an8×8 matrix is applied as the permutation. The permutation matrix P is (4)1101101101111110111011010111001110111001110111001110011010110111.There are total 10 impossible differentials found for 8-round MIBS by our improved algorithm. The new four 8-round impossible differentials found are listed in Table 3.Table 3
Impossible differentials for 8-round MIBS. There are 4 new found impossible differentials.a and b are nonzero values and a and b can have the same value.
Number
Δ
i
n
Δ
o
u
t
Reference
1
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
0
,
a
,
0,0
)
(
b
,
0,0
,
0,0
,
0,0
,
b
;
0,0
,
0,0
,
0,0
,
0,0
)
This paper
2
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
0
,
a
,
0,0
)
(
0,0
,
0,0
,
b
,
0,0
,
b
;
0,0
,
0,0
,
0,0
,
0,0
)
3
(
0,0
,
0,0
,
0,0
,
0,0
;
a
,
0,0
,
0,0
,
0,0
,
a
)
(
0,0
,
0,0
,
0
,
b
,
0,0
;
0,0
,
0,0
,
0,0
,
0,0
)
4
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
a
,
0,0
,
a
)
(
0,0
,
0,0
,
0
,
b
,
0,0
;
0,0
,
0,0
,
0,0
,
0,0
)
5
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
a
,
0,0
,
0,0
,
0
)
(
0,0
,
0,0
,
b
,
0,0
,
0
;
0,0
,
0,0
,
0,0
,
0,0
)
6
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
a
,
0,0
,
0,0
,
0
)
(
0,0
,
0,0
,
0,0
,
0
,
b
;
0,0
,
0,0
,
0,0
,
0,0
)
7
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
a
,
0,0
,
0
)
(
0,0
,
b
,
0,0
,
0,0
,
0
;
0,0
,
0,0
,
0,0
,
0,0
)
[31]
8
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
a
,
0,0
,
0
)
(
0,0
,
0,0
,
0,0
,
b
,
0
;
0,0
,
0,0
,
0,0
,
0,0
)
9
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
0,0
,
a
,
0
)
(
0,0
,
0,0
,
b
,
0,0
,
0
;
0,0
,
0,0
,
0,0
,
0,0
)
10
(
0,0
,
0,0
,
0,0
,
0,0
;
0,0
,
0,0
,
0,0
,
0
,
a
)
(
0,0
,
b
,
0,0
,
0,0
,
0
;
0,0
,
0,0
,
0,0
,
0,0
)Compare with Wu and Wang’s algorithm, this improvement is more general since it not only finds more impossible differentials for a block cipher structures, but also has better efficiency. The results for MIBS are obtained on a 2.66 GHz processor with MAGMA package in a few hours by Wu and Wang’s algorithm [31]. However, our results for MIBS are obtained on a 2.20 GHz processor in java language in less than 10 seconds. Thus, the algorithm presented in this paper is more efficient than Wu and Wang’s algorithm.


## 6. Conclusion

In this paper we improve Wu and Wang’s algorithm for finding impossible differentials of block cipher structures. The improved method is more general than Wu and Wang’s method where it can find more impossible differentials with less time. We apply this method to many block cipher structures. The experiment results show that this improvement can largely reduce the search time for the impossible differentials of a block cipher, since there are known relationships between impossible differential and integral and zero correlation linear cryptanalysis [22, 36, 37]. This method can be used as a cryptanalytic tool to evaluate the security of a block cipher against these kinds of cryptanalysis.



---

*Source: 5980251-2017-08-29.xml*