# New Search Method for Sbox-Related Impossible Differentials

Authors: Yi Zhang; Xuan Shen; Guoqiang Liu; Chao Li
Journal: Security and Communication Networks
 (2022)

---

## Abstract

The impossible differential attack is one of the most fundamental tools of cryptanalysis and has been successfully applied to a large variety of block ciphers. In a typical impossible differential attack, the foundation and first step is to construct an impossible differential. Nowadays, two kinds of most commonly used approaches in impossible differential construction are the matrix-based and tool-aided automatic search methods. In this paper, we proposed a new search method combining an early-abort strategy with the guess-and-determine technique to find longer impossible differentials. Compared with the previous matrix-based search methods, ours has taken the details of Sbox into consideration, while compared with the tool-aided methods, ours is independent of a third-party solver and is applicable to ciphers with large (≥8 bits) Sboxes, which could be tough work for tool-aided methods to cover. Therefore, more accurate results could be obtained. To prove the effectiveness of our method, it is applied to CSA and FOX64. For CSA, 23/24/25-round impossible differentials were found for CSA-BC. This improved the longest impossible differential distinguisher so far by 1/2/3 rounds. And 25-round key recovery attacks are performed against CSA-BC and CSA, which are the longest impossible differential attack by now. For FOX64, we proved that an impossible differential for its round function always implies an impossible differential for 4-round FOX64, and new types of impossible differentials were able to be found. Our method has its own advantage in dealing with large Sboxes, and it may be a possible direction to search for Sbox-related impossible differentials.


---

## Body

## 1. Introduction

Block ciphers play a fundamental role in symmetric-key cryptography. Apart from encryption, it could also be used as primitives in stream ciphers, hash functions, authenticated encryption schemes, and so on. The confidence in the security of a block cipher is largely derived from its resistance against known attacks, among which the differential attack and its variants might be one of the most well-known instances. The differential attack has been successfully applied to many block ciphers, stream ciphers, and hash functions, and numerous variants have been derived, including impossible differential cryptanalysis, truncated differential cryptanalysis, higher order differential cryptanalysis, multiple differential cryptanalysis, and differential-linear cryptanalysis. Among them, the impossible differential attack is one of the most basic tools for block cipher analysis. The impossible differential attack was proposed by Knudsen [1] and Biham et al. [2] independently and has been applied to large numbers of block ciphers successfully, such as AES, Skipjack, and HIGHT [2–4].As a variant of differential attack, impossible differential attack exploits differentials, which occur with probability zero. Usually, two steps are taken to recover keys in a typical impossible differential attack. The first step is to detect a differential for the reduced-round target block cipher with probability zero. The second step is to guess some key materials and eliminate those that satisfy a probability-zero differential distinguisher. During the attack procedure, constructing impossible differentials in the first step is the key point and foundation of impossible differential attacks.


### 1.1. Construction of Impossible Differentials

An impossible differential is usually constructed by the miss-in-the-middle strategy. First, it propagates the input difference forward and the output difference backward with probability 1 for some rounds. Then, if a contradiction is detected in the middle state, the differential is supposed to be impossible.With ad hoc approaches for a specific cipher being studied extensively, generic search models for impossible differentials have been developed. In [5], Kim et al. proposed a matrix-based search method called U-method. They first convert the differential propagation for one round encryption or decryption by a matrix, which identifies the relationship between the input and output blocks. Then, a matrix operation is defined and applied to describe round iteration. If contradictions are found in the middle state matrix, an impossible differential is detected and could further be specified. This method is extended to the UID [6] and Wu and Wang [7] method with a more detailed description of the structure and contradiction afterward. When applied to a specific block cipher of structure, this method could utilize the properties of those structures, and better results are acquired [8–10]. Those matrix-based methods are easy to implement and require little computational and space resources. However, information on the nonlinear component is hardly used except that the Sboxes are bijective.A generic and systematic method to take detailed information on Sboxes into consideration in impossible differential construction has not appeared until the automatic analytical model was introduced to cryptanalysis. In 2011, Mouha et al. [11] used the mixed-integer linear programming (MILP) model to search the security bounds against differential and linear attacks. Then, these kinds of automatic tools are widely applied to integral, meet-in-the-middle, rotational-XOR differential attacks and so on [12–14]. In EUROCRYPT 2017, an MILP-based automatic search model was developed [15] for impossible differential attack. In this method, the differential properties of linear and nonlinear components are expressed as linear inequalities, and the differential search process is modeled as an inequality system and then fed to a third-party solver. If some error codes indicating the system is infeasible are returned, then the differential is expected to be impossible. In ASIACRYPT 2020 [16], another automatic search model was put forward to search for impossible differentials by describing the propagation of values instead of differences. With those automatic tools, the precision of analytical results is improved. However, when the size of the Sbox is large (e.g., ≥8 bits), modeling the properties of the Sbox usually involves large numbers of inequalities, which is a tough task for the third-party solvers to handle.


### 1.2. Our Contributions

In this paper, we proposed an Sbox-related impossible differential search method and further improved it by introducing the guess-and-determine and the early-abort technique to reduce the complexity. To demonstrate the effectiveness of our method, we applied it to CSA-BC and FOX64 whose Sboxes are both of 8-bit size. Our main contributions are as follows:(i)
Based on the guess-and-determine strategy and early-abort technique, a new search method for Sbox-related impossible differentials was developed. Compared with previous matrix-based search methods, ours could exploit more detailed information on the nonlinear primitives. At the same time, our search method is independent of third-party solvers and possesses high performance in dealing with large size Sboxes.(ii)
For CSA-BC, 23/24/25-round impossible differentials were found with our search method in less than 5 seconds, which improved previous works by 1/2/3 rounds. Then, we mounted a 25-round impossible differential attack against CSA-BC using the impossible differentials found by our method. Finally, the key recovery attack is extended to 25-round CSA. And those key recovery attacks are the longest impossible differential attacks against CSA-BC and CSA by now. The results are listed in Table1.(iii)
For FOX64, the relationship between 4-round impossible differentials and its round function is discovered. Then, a framework is derived to verdict whether a 4-round differential(1)u1,u2,u3,u4,u1,u2,u3,u4⟶v1,v2,v3,v4,v1,v2,v3,v4is possible or not, which allows more flexibility in differential patterns compared with previous works. And for the first time, detailed information on Sboxes is taken into consideration in the construction of impossible differentials for FOX64. As a result, new types of impossible differentials were able to be identified. The results are listed in Table 2.Table 1
Impossible differential attack against CSA-BC and CSA.
CipherrKeyrDistData complexityTime complexityReferenceCSA-BC2120244.5222.7[17]CSA−BC∗\22\\[18]CSA-BC2523/24/25258.5261.5Section4CSA2120243.5221.7[17]CSA2524258.5261.5Section4rKey/rDist = length of key recovery attack/distinguisher. ∗The key recovery attack may be invalid since not enough data could be collected.Table 2
4-round impossible differentials for FOX64.
Impossible differential patternConstraintsReference0,u,0,u↛v1,v2,v1,v3u,vi≠0[33]τ−1u↛σvu=v[34]oru↛iovwtu+wtu⊕v≤4[35]0,0,u1,u2↛v1,v2,v3,v4ui,vi≠0Section5Note that the differences in the two branches of FOX64 are equal; for simplicity, only one branch is shown in this table.The rest of this paper is organized as follows. In Section2, we will introduce the basics. Method to construct impossible differential is introduced in Section 3. The results of CSA-BC and FOX64 are presented in Sections 4 and 5, respectively. Section 6 concludes this paper.


## 1.1. Construction of Impossible Differentials

An impossible differential is usually constructed by the miss-in-the-middle strategy. First, it propagates the input difference forward and the output difference backward with probability 1 for some rounds. Then, if a contradiction is detected in the middle state, the differential is supposed to be impossible.With ad hoc approaches for a specific cipher being studied extensively, generic search models for impossible differentials have been developed. In [5], Kim et al. proposed a matrix-based search method called U-method. They first convert the differential propagation for one round encryption or decryption by a matrix, which identifies the relationship between the input and output blocks. Then, a matrix operation is defined and applied to describe round iteration. If contradictions are found in the middle state matrix, an impossible differential is detected and could further be specified. This method is extended to the UID [6] and Wu and Wang [7] method with a more detailed description of the structure and contradiction afterward. When applied to a specific block cipher of structure, this method could utilize the properties of those structures, and better results are acquired [8–10]. Those matrix-based methods are easy to implement and require little computational and space resources. However, information on the nonlinear component is hardly used except that the Sboxes are bijective.A generic and systematic method to take detailed information on Sboxes into consideration in impossible differential construction has not appeared until the automatic analytical model was introduced to cryptanalysis. In 2011, Mouha et al. [11] used the mixed-integer linear programming (MILP) model to search the security bounds against differential and linear attacks. Then, these kinds of automatic tools are widely applied to integral, meet-in-the-middle, rotational-XOR differential attacks and so on [12–14]. In EUROCRYPT 2017, an MILP-based automatic search model was developed [15] for impossible differential attack. In this method, the differential properties of linear and nonlinear components are expressed as linear inequalities, and the differential search process is modeled as an inequality system and then fed to a third-party solver. If some error codes indicating the system is infeasible are returned, then the differential is expected to be impossible. In ASIACRYPT 2020 [16], another automatic search model was put forward to search for impossible differentials by describing the propagation of values instead of differences. With those automatic tools, the precision of analytical results is improved. However, when the size of the Sbox is large (e.g., ≥8 bits), modeling the properties of the Sbox usually involves large numbers of inequalities, which is a tough task for the third-party solvers to handle.


## 1.2. Our Contributions

In this paper, we proposed an Sbox-related impossible differential search method and further improved it by introducing the guess-and-determine and the early-abort technique to reduce the complexity. To demonstrate the effectiveness of our method, we applied it to CSA-BC and FOX64 whose Sboxes are both of 8-bit size. Our main contributions are as follows:(i)
Based on the guess-and-determine strategy and early-abort technique, a new search method for Sbox-related impossible differentials was developed. Compared with previous matrix-based search methods, ours could exploit more detailed information on the nonlinear primitives. At the same time, our search method is independent of third-party solvers and possesses high performance in dealing with large size Sboxes.(ii)
For CSA-BC, 23/24/25-round impossible differentials were found with our search method in less than 5 seconds, which improved previous works by 1/2/3 rounds. Then, we mounted a 25-round impossible differential attack against CSA-BC using the impossible differentials found by our method. Finally, the key recovery attack is extended to 25-round CSA. And those key recovery attacks are the longest impossible differential attacks against CSA-BC and CSA by now. The results are listed in Table1.(iii)
For FOX64, the relationship between 4-round impossible differentials and its round function is discovered. Then, a framework is derived to verdict whether a 4-round differential(1)u1,u2,u3,u4,u1,u2,u3,u4⟶v1,v2,v3,v4,v1,v2,v3,v4is possible or not, which allows more flexibility in differential patterns compared with previous works. And for the first time, detailed information on Sboxes is taken into consideration in the construction of impossible differentials for FOX64. As a result, new types of impossible differentials were able to be identified. The results are listed in Table 2.Table 1
Impossible differential attack against CSA-BC and CSA.
CipherrKeyrDistData complexityTime complexityReferenceCSA-BC2120244.5222.7[17]CSA−BC∗\22\\[18]CSA-BC2523/24/25258.5261.5Section4CSA2120243.5221.7[17]CSA2524258.5261.5Section4rKey/rDist = length of key recovery attack/distinguisher. ∗The key recovery attack may be invalid since not enough data could be collected.Table 2
4-round impossible differentials for FOX64.
Impossible differential patternConstraintsReference0,u,0,u↛v1,v2,v1,v3u,vi≠0[33]τ−1u↛σvu=v[34]oru↛iovwtu+wtu⊕v≤4[35]0,0,u1,u2↛v1,v2,v3,v4ui,vi≠0Section5Note that the differences in the two branches of FOX64 are equal; for simplicity, only one branch is shown in this table.The rest of this paper is organized as follows. In Section2, we will introduce the basics. Method to construct impossible differential is introduced in Section 3. The results of CSA-BC and FOX64 are presented in Sections 4 and 5, respectively. Section 6 concludes this paper.


## 2. Preliminaries

This section will describe the impossible differential and some techniques to reduce complexity in cryptanalysis. Before that, we will first introduce some notations used throughout this paper.Denote byFq the finite fields with q elements, and Fq∗ contains all nonzero elements of Fq. Numbers over F28 are expressed in hexadecimal, and the prefix 0x is omitted. The number of elements in set A is denoted by #A. For simplicity, consecutive variables vi,vi+1,…,vj are denoted as vi−j.


### 2.1. Impossible Differential

The difference forx,y∈F2n is defined as u=x⊕y. A differential u,v for Fr is that the input difference of Fr is u, and its output difference is v. When there does not exist any plaintext that satisfies the differential, that is,(2)#x∈F2n|Frx⊕Frx⊕u=v=0,then this differential is said to be impossible. To simplify the probability evaluation of differentials, differential characteristic is proposed.Anr-round differential characteristic for iterated block cipher is defined as u0,u1,…,ur that the input difference is u0 and the output difference after round i is ui. Then, the probability of the differential is the sum of all its differential characteristics. A differential is impossible, implying that all characteristics are impossible. Otherwise, there exists at least one characteristic whose probability is greater than zero. That is, denote by Pru0,u1,…,ur the probability for differential characteristic u0,u1,…,ur, and then an r-round differential u,v is impossible if for all ui∈F2n, 1≤i≤r−1,(3)∑u0=u,ur=v,ui∈F2n,1≤i≤r−1Pru0,u1,…,ur=0.Otherwise, the differential is possible, and there exists a set ofui such that(4)Pru0,u1,…,ur>0.


### 2.2. Guess-and-Determine Technique

The guess-and-determine technique is a commonly used technique to decrease the computational workload in cryptanalysis, and it also has wide application in stream cipher cryptanalysis [19–21]. The guess-and-determine technique exploits the relationship among internal values. It guesses certain bits and makes use of the relationship to determine the remaining bits, thus decreasing the complexity of trying the remaining bits. A typical procedure of the guess-and-determine technique is to derive the relationship first and then exhaustively guess over a relatively small proportion of state to recover the whole state. Finally, the attacker checks the correctness by comparing it with known conditions. Assume that the exploited internal relationship f maps t-bit t<n state st to other n−t-bit state sn−t; say(5)fx0,x1,…,xt−1,xt,…,xn−1=c⇒xt,…,xn−1=f′x0,x1,…,xt−1,where c∈F2n. Then the internal state can be divided into two parts st and sn−t accordingly. Hereinafter, bits in st are called free variables as they should be enumerated, and those in sn−t are called controlled variables as they are deduced by the free variables. To recover an n-bit state, the original complexity is O2n. After such partition, the complexity could be reduced to O2t,t<n. In our search model, the internal relationship f is constructed by the fact that possible characteristics shall meet in the middle states. And the candidate state is determined by whether it is in accordance with the Differential Distribution Table (DDT) of the Sboxes.


### 2.3. Early-Abort Technique

The early-abort technique is noticed as early as in the differential attack against DES [22]; it has numerous successful applications in key recovery attacks against block ciphers and public-key encryption schemes designing [23, 24]. Instead of guessing all the required unknown bits at a time, it partially checks whether a candidate pair could produce the expected difference by guessing only a small fraction of keys. Since some useless pairs are discarded before the next guess, the computational workload could be decreased consequently. When this idea is applied to the search for impossible differential, according to (3) and (4), if one possible characteristic is detected, then this differential must be possible, and the check process for other characteristics could be terminated. In addition, when testing whether a single characteristic is possible or not, if one condition is found to be dissatisfied, this characteristic is impossible, and the cost of computing other variables would be saved.


## 2.1. Impossible Differential

The difference forx,y∈F2n is defined as u=x⊕y. A differential u,v for Fr is that the input difference of Fr is u, and its output difference is v. When there does not exist any plaintext that satisfies the differential, that is,(2)#x∈F2n|Frx⊕Frx⊕u=v=0,then this differential is said to be impossible. To simplify the probability evaluation of differentials, differential characteristic is proposed.Anr-round differential characteristic for iterated block cipher is defined as u0,u1,…,ur that the input difference is u0 and the output difference after round i is ui. Then, the probability of the differential is the sum of all its differential characteristics. A differential is impossible, implying that all characteristics are impossible. Otherwise, there exists at least one characteristic whose probability is greater than zero. That is, denote by Pru0,u1,…,ur the probability for differential characteristic u0,u1,…,ur, and then an r-round differential u,v is impossible if for all ui∈F2n, 1≤i≤r−1,(3)∑u0=u,ur=v,ui∈F2n,1≤i≤r−1Pru0,u1,…,ur=0.Otherwise, the differential is possible, and there exists a set ofui such that(4)Pru0,u1,…,ur>0.


## 2.2. Guess-and-Determine Technique

The guess-and-determine technique is a commonly used technique to decrease the computational workload in cryptanalysis, and it also has wide application in stream cipher cryptanalysis [19–21]. The guess-and-determine technique exploits the relationship among internal values. It guesses certain bits and makes use of the relationship to determine the remaining bits, thus decreasing the complexity of trying the remaining bits. A typical procedure of the guess-and-determine technique is to derive the relationship first and then exhaustively guess over a relatively small proportion of state to recover the whole state. Finally, the attacker checks the correctness by comparing it with known conditions. Assume that the exploited internal relationship f maps t-bit t<n state st to other n−t-bit state sn−t; say(5)fx0,x1,…,xt−1,xt,…,xn−1=c⇒xt,…,xn−1=f′x0,x1,…,xt−1,where c∈F2n. Then the internal state can be divided into two parts st and sn−t accordingly. Hereinafter, bits in st are called free variables as they should be enumerated, and those in sn−t are called controlled variables as they are deduced by the free variables. To recover an n-bit state, the original complexity is O2n. After such partition, the complexity could be reduced to O2t,t<n. In our search model, the internal relationship f is constructed by the fact that possible characteristics shall meet in the middle states. And the candidate state is determined by whether it is in accordance with the Differential Distribution Table (DDT) of the Sboxes.


## 2.3. Early-Abort Technique

The early-abort technique is noticed as early as in the differential attack against DES [22]; it has numerous successful applications in key recovery attacks against block ciphers and public-key encryption schemes designing [23, 24]. Instead of guessing all the required unknown bits at a time, it partially checks whether a candidate pair could produce the expected difference by guessing only a small fraction of keys. Since some useless pairs are discarded before the next guess, the computational workload could be decreased consequently. When this idea is applied to the search for impossible differential, according to (3) and (4), if one possible characteristic is detected, then this differential must be possible, and the check process for other characteristics could be terminated. In addition, when testing whether a single characteristic is possible or not, if one condition is found to be dissatisfied, this characteristic is impossible, and the cost of computing other variables would be saved.


## 3. Construction of Impossible Differentials

In this section, we will propose a generic framework to search for Sbox-related impossible differentials. Then the guess-and-determine and the early-abort techniques are introduced to improve the performance of the search algorithm. Our method puts no constraints on the structure of block ciphers, and it could be applied to SPN, Feistel, Lai-Massey, or other structures of block ciphers.In order to explain our techniques better, in the following, we will use the small-scale AES proposed by Cid et al. as an example. This variant inherits the design features of AES and provides a suitable instance for different cryptanalytic methods. The small-scale version [25] parameterized by (2, 2, 2, 8), also called miniAES for short in this section, has 2 rounds and a block size of 32 bits, where the data block is viewed as an array of 2×2 words of 8 bits.The encryption of miniAES is similar to AES. In the SP type round functions, an 8-bit Sbox is applied to each word first, which is the SB operation. Then the SR operation shifts the second row for 1 word. Finally, the MC operation multiplies a matrix overF28 and the state array. The matrix is specified as(6)3223∈F282×2.Note that the MC operation in the last round is omitted. Since the impossible differential properties are regarded as independent of round key addition, the AK operation is omitted here.In the following, we will study whether the 2-round differential(7)u0,0,0,u1⟶v0,0,0,v1is possible or not for miniAES, where ui,vi∈F28∗. The differential propagation is presented in Figure 1. Since the output difference of Sbox is hard to predict, new variables u2,u3,v2,v3 are introduced to show the propagation of Sboxes. When the details of Sboxes are taken into consideration, the impossible differential studied may not be in the truncated form. It is impossible for some specific instances, and its value is closely related to the choice of Sbox; this is what we called Sbox-related impossible differentials in our paper. It should also be pointed out that the input and output difference pattern is chosen empirically or by analyzing the structure of the target cipher.Figure 1
Differential propagation of miniAES.


### 3.1. A Straightforward Search Method for Impossible Differentials

To verify whether a differential is possible or not, according to the definition, that is, (8), all differential characteristics are impossible if the differential is impossible. Therefore, all characteristics should be checked. The conditions used in the check procedure could be divided into two parts. The first is that the differences in the middle state from both encryption and decryption should match where a linear equation system is built. For miniAES, this equation system is(8)v2=3u2⊕2u3,v3=2u2⊕3u3.The second is that new variables are introduced for active Sboxes; therefore, they should be in accordance with the propagation rules of Sboxes; that is to say, the corresponding entries in DDT are nonzero. Denote the entry of DDT as(9)DDTα,β=#x∈F28|Sx⊕Sx⊕α=β.For miniAES, it is required that(10)DDTu0,u2>0,DDTu1,u3>0,DDTv0,v2>0,DDTv1,v3>0.In the search for impossible differentials, all variables are enumerated first, where each set ofui,vi corresponds to a differential characteristic. If both (8) and (10) are satisfied, then this characteristic is possible. This definition-based method is shown in Algorithm 1.Algorithm 1: A straightforward way to find impossible differentials.
(1)
Initiate impossible differential setT and possible differential set T¯ to empty(2)
Derive differential propagation by introducing new variables(3)
for all the variablesdo(4)
if all conditions of middle state and Sboxes are satisfied then(5)
Add this differential toT¯(6)
end if(7)
end for(8)
ReturnT=F28∗×F28∗/T¯Remark 1.
Algorithm 1 provides an efficient way to take the DDT of Sbox into consideration. In our method, the information on Sbox is exploited by checking whether the differential propagation is in accordance with the DDT as in equation (10), while for the MILP-based search method, modeling a single 8-bit Sbox involves thousands of inequalities. And in our method, the DDT is accessed by table lookup, which is more effective. Moreover, when the size of Sboxes increases, the computation complexity of table lookup would still remain effective.Remark 2.
In the matrix-based method and its derivatives, the propagation rule ofn-bit Sbox is that a nonzero input difference δ∗∈F2n will propagate to a nonzero output difference Δ∗∈F2n, where Δ∗ could be any value over F2n∗. However, the exact value of the output difference usually is not considered. Therefore, the middle state conditions are built, and the attackers detect contradictions where the difference from one side is nonzero while it is zero from the other side of the equations. In fact, for an Sbox over a finite field with characteristic 2, the proportion of possible output difference Δ∗ for a given input difference is less than 50%, and treating Δ∗ as any nonzero value might cause inaccuracy consequently. In our method, only the output difference with DDTδ∗,Δ∗>0 is taken into consideration, resulting in a more accurate description of the differential propagation. Furthermore, for the middle state conditions, it is checked whether the exact value of the differences from both sides matches.
Though the definition-based search method could take more detailed differential properties into consideration, checking all characteristics will require excessive time and memory sources. Therefore, in the following, the guess-and-determine and the early-abort technique will be introduced to improve its performance in the enumerating process and the checking process.


### 3.2. Improvement with Guess-and-Determine Technique

The guess-and-determine technique exploits the relationship among internal values to reduce the complexity of enumerating all variables. For miniAES, there are eight 8-bit variablesu0,u1,u2,u3,v0,v1,v2,v3, that is, 8×8=64 bits in total. Therefore, 264 guesses would be needed to search for this type of impossible differentials. However, v2 and v3 could be expressed as functions of other variables as in (8). By exploring this relationship, instead of guessing all the 64 bits and then checking (8) and (10), the search could be performed by guessing u0,u1,u2,u3,v0,v1 first, then computing v2 and v3 by (8), and finally checking by (10). By exploiting the linear relationship among variables, the guesses of v2 and v3 could be saved. Furthermore, the resultant state will match the middle state since they are derived from it. Therefore, the checking process will also be reduced.The above process could be generalized as follows. Assume that the input difference is encrypted byr1 rounds, and the output difference is decrypted by r2 rounds. To precisely describe the differential propagation, a variable is introduced if its difference is not determined. Usually, new variables are introduced for the output of an active Sbox or the input of the inverse of an active Sbox. Assuming that there are l-bit variables in total introduced for the r1+r2-round differentials, to check whether there exist r1+r2-round impossible differentials, enumeration of all the 2l possible states is required. Using the guess-and-determine technique, when checking the possibility for every characteristic, the middle state computed from encryption and decryption direction shall match, resulting in a linear equation system. By Gaussian elimination, the controlled variables could be expressed by free variables. In the example of miniAES, the equation system is (3), and the controlled variables are v2 and v3, which are expressed by u2 and u3. If n-bit n<l controlled variables could be derived by the equation system, then only 2l−n states are required to try through instead of enumerating all 2l states. This decreases the complexity by a factor of 2n. Taking all those conditions into consideration, an algorithm is derived by combining the definition-based method and the guess-and-determine technique, which could reduce the complexity of enumerating and is shown in Algorithm 2.Algorithm 2: Find impossible differentials with the guess-and-determine technique.
(1)
Initiate impossible differential setT and possible differential set T¯ to empty(2)
Derive differential propagation by introducing new variables(3)
Build equations for the intermediate state(4)
Represent controlled variables by free variables from the equations(5)
for all the free variables do(6)
Compute the controlled variables(7)
if all conditions of Sboxes are satisfied then(8)
Add this differential toT¯(9)
end if(10)
end for(11)
ReturnT=F28∗×F28∗∖T¯The difference lies in that, in Algorithm 1, all variables are guessed as in Line 3, and the conditions are checked for Sbox and middle state in Line 4, while in Algorithm 2, the equation system is first derived in Line 2–4. Then only the free variables are enumerated in Line 5, and the controlled variables are computed accordingly in Line 6. Finally, only the conditions of the Sbox need to be checked in Line 7.The time-consuming step for the search process is the loop in Line 5. Taking CSA-BC as an example, to search forr-round (r=r1+r2 and r≥20) impossible differentials, r−12 8-bit variables will be introduced. Among them, there are 8 controlled 8-bit variables, and the remaining r−20 8-bit variables are free. Therefore, the complexity for searching r-round impossible differential is O28r−20. That is to say, the complexity of searching for 25-round and 26-round distinguishers is 240 and 248, respectively, where hours or days are needed for personal computers to cover the workload; thus, further improvement is needed.


### 3.3. Improvement with Early-Abort Technique

Back to the example of miniAES, according to (3) and (4), while all differential characteristics are required to be impossible for an impossible differential, it is enough to deny it if there exists one possible, meaning that the checking process could be terminated when a possible differential is detected. That is to say, when a set of u0,u1,u2,u3,v0,v1 is detected to satisfy the conditions of Sbox, meaning the corresponding differential characteristic in Figure 1 is possible, then the differential u0,0,0,u1⟶v0,0,0,v1 is possible, and there is no need to guess other u2 and u3 candidates. Moreover, there is no need to compute all controlled variables at a time. Instead, we compute one and check immediately. If the conditions are not satisfied, then this characteristic would be impossible, and we continue with another. For miniAES, the checking conditions for the middle state are guaranteed by the guess-and-determine technique, and the checking conditions for Sboxes are shown in (10). After guessing u0 and u2, whether DDTu0,u2>0 is checked immediately. If this is not satisfied, this characteristic is impossible, and there is no need to guess or compute other variables. Similarly, computing v2 is followed by checking whether DDTv0,v2>0 immediately. Performing the check procedure in advance would save much effort in guessing and computing those useless candidates. Based on those, an improved search algorithm combining the early-abort technique is proposed as shown in Algorithm 3, where the free variables are distinguished by whether they are involved in the first or last round.Algorithm 3: Improved search algorithm with early-abort technique.
(1)
Initiate impossible differential setT to empty(2)
Derive differential propagation by introducing new variables(3)
Represent controlled variables by free variables from the equations(4)
for all the free variables in the first and last round do(5)
for all remaining free variables do(6)
if the checking condition of Sbox for free variables is not satisfied then(7)
Turn to Line 5 ⊳ checking process early-aborted(8)
end if(9)
if all controlled variables are computed then(10)
Turn to Line 4 ⊳ possible characteristic found, differential early-aborted(11)
else(12)
Compute a controlled variable(13)
end if(14)
if check condition of Sbox for controlled variables is not satisfied then(15)
Turn to Line 5 ⊳ checking process early-aborted(16)
else(17)
Turn to Line 9 ⊳ continue checking Sbox conditions(18)
end if(19)
end for(20)
Add this differential intoT ⊳ Execute this line unless Line 10 is executed(21)
end for(22)
ReturnTThe improvement by the early-abort technique is that there is no need to compute all characteristic or controlled variables. In one trial, if some checking conditions are not satisfied (Line 7 and Line 15), indicating that this characteristic is impossible, then this loop is terminated. If one characteristic is found to be possible (Line 10), that is, all controlled variables are computed and passed the check procedure, then this differential is possible, and the loop for testing other characteristics is stopped. Thus, the computation and determination could be saved. The application of this algorithm will be presented in the next sections.To prove the validity of our algorithm, we performed comparative experiments on a personal computer. The device is equipped with an Intel Core i7-6500U processor, and the running time for finding an impossible differential for CSA-BC is shown in Table3. The results show that, for Algorithm 2, time consumed grows sharply with the increase of rounds, while the impossible differential for 22–26 rounds could be acquired in less than 5 seconds with Algorithm 3. Moreover, it is interesting to notice that the running time decreases when the length of differentials increases from 25 to 26. This is attributed to the effect of the early-abort technique. The proportion of possible characteristics grows exponentially with the increase of length; therefore, the search process would be terminated in advance, and much effort is saved thanks to the early-abort technique.Table 3
Time taken to search impossible differentials for CSA-BC.
Rounds22 (s)23 (s)24 (s)2526Time taken in Algorithm 2<1<1271.698 h>1 dTime taken in Algorithm 3<1<135 s3 s


## 3.1. A Straightforward Search Method for Impossible Differentials

To verify whether a differential is possible or not, according to the definition, that is, (8), all differential characteristics are impossible if the differential is impossible. Therefore, all characteristics should be checked. The conditions used in the check procedure could be divided into two parts. The first is that the differences in the middle state from both encryption and decryption should match where a linear equation system is built. For miniAES, this equation system is(8)v2=3u2⊕2u3,v3=2u2⊕3u3.The second is that new variables are introduced for active Sboxes; therefore, they should be in accordance with the propagation rules of Sboxes; that is to say, the corresponding entries in DDT are nonzero. Denote the entry of DDT as(9)DDTα,β=#x∈F28|Sx⊕Sx⊕α=β.For miniAES, it is required that(10)DDTu0,u2>0,DDTu1,u3>0,DDTv0,v2>0,DDTv1,v3>0.In the search for impossible differentials, all variables are enumerated first, where each set ofui,vi corresponds to a differential characteristic. If both (8) and (10) are satisfied, then this characteristic is possible. This definition-based method is shown in Algorithm 1.Algorithm 1: A straightforward way to find impossible differentials.
(1)
Initiate impossible differential setT and possible differential set T¯ to empty(2)
Derive differential propagation by introducing new variables(3)
for all the variablesdo(4)
if all conditions of middle state and Sboxes are satisfied then(5)
Add this differential toT¯(6)
end if(7)
end for(8)
ReturnT=F28∗×F28∗/T¯Remark 1.
Algorithm 1 provides an efficient way to take the DDT of Sbox into consideration. In our method, the information on Sbox is exploited by checking whether the differential propagation is in accordance with the DDT as in equation (10), while for the MILP-based search method, modeling a single 8-bit Sbox involves thousands of inequalities. And in our method, the DDT is accessed by table lookup, which is more effective. Moreover, when the size of Sboxes increases, the computation complexity of table lookup would still remain effective.Remark 2.
In the matrix-based method and its derivatives, the propagation rule ofn-bit Sbox is that a nonzero input difference δ∗∈F2n will propagate to a nonzero output difference Δ∗∈F2n, where Δ∗ could be any value over F2n∗. However, the exact value of the output difference usually is not considered. Therefore, the middle state conditions are built, and the attackers detect contradictions where the difference from one side is nonzero while it is zero from the other side of the equations. In fact, for an Sbox over a finite field with characteristic 2, the proportion of possible output difference Δ∗ for a given input difference is less than 50%, and treating Δ∗ as any nonzero value might cause inaccuracy consequently. In our method, only the output difference with DDTδ∗,Δ∗>0 is taken into consideration, resulting in a more accurate description of the differential propagation. Furthermore, for the middle state conditions, it is checked whether the exact value of the differences from both sides matches.
Though the definition-based search method could take more detailed differential properties into consideration, checking all characteristics will require excessive time and memory sources. Therefore, in the following, the guess-and-determine and the early-abort technique will be introduced to improve its performance in the enumerating process and the checking process.


## 3.2. Improvement with Guess-and-Determine Technique

The guess-and-determine technique exploits the relationship among internal values to reduce the complexity of enumerating all variables. For miniAES, there are eight 8-bit variablesu0,u1,u2,u3,v0,v1,v2,v3, that is, 8×8=64 bits in total. Therefore, 264 guesses would be needed to search for this type of impossible differentials. However, v2 and v3 could be expressed as functions of other variables as in (8). By exploring this relationship, instead of guessing all the 64 bits and then checking (8) and (10), the search could be performed by guessing u0,u1,u2,u3,v0,v1 first, then computing v2 and v3 by (8), and finally checking by (10). By exploiting the linear relationship among variables, the guesses of v2 and v3 could be saved. Furthermore, the resultant state will match the middle state since they are derived from it. Therefore, the checking process will also be reduced.The above process could be generalized as follows. Assume that the input difference is encrypted byr1 rounds, and the output difference is decrypted by r2 rounds. To precisely describe the differential propagation, a variable is introduced if its difference is not determined. Usually, new variables are introduced for the output of an active Sbox or the input of the inverse of an active Sbox. Assuming that there are l-bit variables in total introduced for the r1+r2-round differentials, to check whether there exist r1+r2-round impossible differentials, enumeration of all the 2l possible states is required. Using the guess-and-determine technique, when checking the possibility for every characteristic, the middle state computed from encryption and decryption direction shall match, resulting in a linear equation system. By Gaussian elimination, the controlled variables could be expressed by free variables. In the example of miniAES, the equation system is (3), and the controlled variables are v2 and v3, which are expressed by u2 and u3. If n-bit n<l controlled variables could be derived by the equation system, then only 2l−n states are required to try through instead of enumerating all 2l states. This decreases the complexity by a factor of 2n. Taking all those conditions into consideration, an algorithm is derived by combining the definition-based method and the guess-and-determine technique, which could reduce the complexity of enumerating and is shown in Algorithm 2.Algorithm 2: Find impossible differentials with the guess-and-determine technique.
(1)
Initiate impossible differential setT and possible differential set T¯ to empty(2)
Derive differential propagation by introducing new variables(3)
Build equations for the intermediate state(4)
Represent controlled variables by free variables from the equations(5)
for all the free variables do(6)
Compute the controlled variables(7)
if all conditions of Sboxes are satisfied then(8)
Add this differential toT¯(9)
end if(10)
end for(11)
ReturnT=F28∗×F28∗∖T¯The difference lies in that, in Algorithm 1, all variables are guessed as in Line 3, and the conditions are checked for Sbox and middle state in Line 4, while in Algorithm 2, the equation system is first derived in Line 2–4. Then only the free variables are enumerated in Line 5, and the controlled variables are computed accordingly in Line 6. Finally, only the conditions of the Sbox need to be checked in Line 7.The time-consuming step for the search process is the loop in Line 5. Taking CSA-BC as an example, to search forr-round (r=r1+r2 and r≥20) impossible differentials, r−12 8-bit variables will be introduced. Among them, there are 8 controlled 8-bit variables, and the remaining r−20 8-bit variables are free. Therefore, the complexity for searching r-round impossible differential is O28r−20. That is to say, the complexity of searching for 25-round and 26-round distinguishers is 240 and 248, respectively, where hours or days are needed for personal computers to cover the workload; thus, further improvement is needed.


## 3.3. Improvement with Early-Abort Technique

Back to the example of miniAES, according to (3) and (4), while all differential characteristics are required to be impossible for an impossible differential, it is enough to deny it if there exists one possible, meaning that the checking process could be terminated when a possible differential is detected. That is to say, when a set of u0,u1,u2,u3,v0,v1 is detected to satisfy the conditions of Sbox, meaning the corresponding differential characteristic in Figure 1 is possible, then the differential u0,0,0,u1⟶v0,0,0,v1 is possible, and there is no need to guess other u2 and u3 candidates. Moreover, there is no need to compute all controlled variables at a time. Instead, we compute one and check immediately. If the conditions are not satisfied, then this characteristic would be impossible, and we continue with another. For miniAES, the checking conditions for the middle state are guaranteed by the guess-and-determine technique, and the checking conditions for Sboxes are shown in (10). After guessing u0 and u2, whether DDTu0,u2>0 is checked immediately. If this is not satisfied, this characteristic is impossible, and there is no need to guess or compute other variables. Similarly, computing v2 is followed by checking whether DDTv0,v2>0 immediately. Performing the check procedure in advance would save much effort in guessing and computing those useless candidates. Based on those, an improved search algorithm combining the early-abort technique is proposed as shown in Algorithm 3, where the free variables are distinguished by whether they are involved in the first or last round.Algorithm 3: Improved search algorithm with early-abort technique.
(1)
Initiate impossible differential setT to empty(2)
Derive differential propagation by introducing new variables(3)
Represent controlled variables by free variables from the equations(4)
for all the free variables in the first and last round do(5)
for all remaining free variables do(6)
if the checking condition of Sbox for free variables is not satisfied then(7)
Turn to Line 5 ⊳ checking process early-aborted(8)
end if(9)
if all controlled variables are computed then(10)
Turn to Line 4 ⊳ possible characteristic found, differential early-aborted(11)
else(12)
Compute a controlled variable(13)
end if(14)
if check condition of Sbox for controlled variables is not satisfied then(15)
Turn to Line 5 ⊳ checking process early-aborted(16)
else(17)
Turn to Line 9 ⊳ continue checking Sbox conditions(18)
end if(19)
end for(20)
Add this differential intoT ⊳ Execute this line unless Line 10 is executed(21)
end for(22)
ReturnTThe improvement by the early-abort technique is that there is no need to compute all characteristic or controlled variables. In one trial, if some checking conditions are not satisfied (Line 7 and Line 15), indicating that this characteristic is impossible, then this loop is terminated. If one characteristic is found to be possible (Line 10), that is, all controlled variables are computed and passed the check procedure, then this differential is possible, and the loop for testing other characteristics is stopped. Thus, the computation and determination could be saved. The application of this algorithm will be presented in the next sections.To prove the validity of our algorithm, we performed comparative experiments on a personal computer. The device is equipped with an Intel Core i7-6500U processor, and the running time for finding an impossible differential for CSA-BC is shown in Table3. The results show that, for Algorithm 2, time consumed grows sharply with the increase of rounds, while the impossible differential for 22–26 rounds could be acquired in less than 5 seconds with Algorithm 3. Moreover, it is interesting to notice that the running time decreases when the length of differentials increases from 25 to 26. This is attributed to the effect of the early-abort technique. The proportion of possible characteristics grows exponentially with the increase of length; therefore, the search process would be terminated in advance, and much effort is saved thanks to the early-abort technique.Table 3
Time taken to search impossible differentials for CSA-BC.
Rounds22 (s)23 (s)24 (s)2526Time taken in Algorithm 2<1<1271.698 h>1 dTime taken in Algorithm 3<1<135 s3 s


## 4. Constructing Impossible Differentials for CSA-BC

In this section, we will first give a brief introduction of CSA-BC and then present the results of impossible differentials constructed by our method. The impact of Sbox on impossible differentials will also be discussed. Finally, key recovery attacks will be mounted using the impossible differentials found.


### 4.1. Description of CSA-BC

Digital Video Broadcast (DVB) is a series of standards for digital television. It is widely applied in most countries and regions in the world. The Digital Video Broadcast Common Scrambling Algorithm (DVB-CSA, or CSA for short) is mainly specified to guarantee the secure transmitting of MPEG-2 signal in Pay-TV and was adopted by the DVB consortium in 1994. The encryption process of CSA can be divided into two parts, the block cipher part (CSA-BC) and the stream cipher part (CSA-SC).CSA-BC is a 64-bit block cipher with a 64-bit key size. The state could be regarded as an 8-byte vector. And the plaintext is updated by the round functionF for 56 rounds.The round functionF is depicted in Figure 2 and works as follows. Denote its input and output as x0,x1,…,x7 and y0,y1,…,y7, respectively; then(11)y0=x1,y1=x2⊕x0,y2=x3⊕x0,y3=x4⊕x0,y4=x5,y5=x6⊕P°Sx7⊕k,y6=x7,y7=x0⊕Sx7⊕k,where k is the round key, S is the 8-bit to 8-bit Sbox (see [18, 26]), and P is a linear transformation that permutes the i-th bit in a byte into position Pi=1,7,5,4,2,6,0,3.Figure 2
Round function of CSA-BC.As our attack is independent of the key schedule and stream cipher, we omit that in this paper. Readers interested are referred to [18, 26] for more details.For CSA-BC, current works mainly focus on its security evaluation against impossible differential attacks. [17, 18] In 2016, Zhang et al. [17] proposed the first structural impossible differential attack. Then it is improved to 22 rounds by taking the DDT of the Sbox into consideration [18]. The analytical results of CSA-BC are listed in Table 1.


### 4.2. Impossible Differentials for CSA-BC

In [17, 18], impossible differentials with the pattern(12)0,0,0,0,0,0,u,0↛0,v,v,v,0,0,0,v,u,v≠0are considered. In this section, we will still study impossible differentials of this type as it diffuses relatively slower. Since more variables are involved in longer impossible differentials, we combined various search strategies as in Section 3, and better results were obtained.Table 4
Differential propagation from encryption direction.
Differential state0(0,0,0,0,0,0,u,0)1(0,0,0,0,0,u,0,0)2(0,0,0,0,u,0,0,0)3(0,0,0,u,0,0,0,0)4(0,0,u,0,0,0,0,0)5(0,u,0,0,0,0,0,0)6(u,0,0,0,0,0,0,0)7(0,u,u,u,0,0,0,u)8u,u,u,0,0,Pu1,u,u19u,0,u,u,Pu1,u⊕Pu2,u1,u⊕u210(0,0,0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2,u⊕u3)11(0,0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3,u4)12(0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3⊕Pu5,u4,u5)13(u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3⊕Pu5,u4⊕Pu6,u5,u6)14(u⊕Pu2,u⊕u1⊕Pu1⊕Pu3,Pu1⊕u2⊕Pu4, Pu1⊕u3⊕Pu5,u4⊕Pu6,u5⊕Pu7,u6, u⊕Pu1⊕u7)15(u⊕u1⊕Pu1⊕Pu3,u⊕u2⊕Pu1⊕Pu2⊕Pu4,u⊕u3⊕Pu1⊕Pu2⊕Pu5, u⊕u4⊕Pu2⊕Pu6,u5⊕Pu7,u6⊕Pu8,u⊕Pu1⊕u7,u⊕Pu2⊕u8)16(u⊕u2⊕Pu1⊕Pu2⊕Pu4,u1⊕u3⊕Pu2⊕Pu3⊕Pu5, u1⊕u4⊕Pu1⊕Pu2⊕Pu3⊕Pu6, u⊕u1⊕u5⊕Pu1⊕Pu3⊕Pu7,u6⊕Pu8,u⊕u7⊕Pu1⊕Pu9, u⊕Pu2⊕u8,u⊕u1⊕u9⊕Pu1⊕Pu3)According to Figure2, one byte is nonlinearly transformed after one round; therefore, only one new variable needs to be introduced to describe the differential propagation. From the encryption direction, the 16-round propagation is shown in Table 4, where u∈F28∗ and ui∈F28,1≤i≤9. The constraints are(13)DDTu,u1>0,DDTu1,u2>0,DDTu⊕u2,u3>0,DDTu⊕u3,u4>0,DDTu4,u5>0,DDTu5,u6>0,DDTu6,u7>0,DDTu⊕u7⊕Pu1,u8>0,DDTu⊕u8⊕Pu2,u9>0.Because one variable is introduced in the beginning and new variables are brought from the 8-th round, there arer1−6 variables in total for an r1-round r1>7 encryption.Using a similar strategy, the 10-round propagation from the decryption direction could be obtained, and it is shown in Table5, where v∈F28∗ and vi∈F28,1≤i≤3. The conditions for Sbox are DDTv,v1>0, DDTPv1,v2>0, and DDTPv2,v3>0. The number of variables needed to describe the differential propagation for an r2-round decryption is also r2−6 when r2>7.Table 5
Differential propagation from decryption direction.
Differential state0(0,v,v,v,0,0,0,v)1(v,0,0,0,0,0,0,0)2(0,v,0,0,0,0,0,0)3(0,0,v,0,0,0,0,0)4(0,0,0,v,0,0,0,0)5(0,0,0,0,v,0,0,0)6(0,0,0,0,0,v,0,0)7(0,0,0,0,0,0,v,0)8v1,0,v1,v1,v1,0,Pv1,v9(v⊕v2,v1,v⊕v2,v⊕v1⊕v2, v⊕v1⊕v2,v1,Pv2,Pv1)10(v3⊕Pv1,v⊕v2,v1⊕v3⊕Pv1,v⊕v2⊕v3⊕Pv1, v⊕v1⊕v2⊕v3⊕Pv1, v⊕v1⊕v2,v1⊕Pv3,Pv2)To search forr-round (r=r1+r2 and r≥20) impossible differentials, r−12 8-bit variables will be introduced. Given the differential state from both sides, 8 equations could be built by assuming they match in all positions, and 8 controlled variables will be deduced correspondingly. Therefore, only r−20 bytes need to be guessed instead of r−12. At the same time, those variables are input and output differences of the Sbox; hence, they are also required to satisfy the DDT of the Sbox. It should be pointed out that the work of both [17, 18] are special cases of our algorithm.The 23-round impossible differential is built by concatenating 15 rounds from the encryption direction and 8 rounds from the decryption direction. If they match in every byte, then the equation system for the middle state is built as(14)u⊕u1⊕Pu1⊕Pu3=v1,u⊕u2⊕Pu1⊕Pu2⊕Pu4=0,u⊕u3⊕Pu1⊕Pu2⊕Pu5=v1,u⊕u4⊕Pu2⊕Pu6=v1,u5⊕Pu7=v1,u6⊕Pu8=0,u⊕Pu1⊕u7=Pv1,u⊕Pu2⊕u8=v.Since the controlled variables could be expressed as linear functions of free variables, the equation system is transformed by the Gaussian elimination method to(15)u2=P236u⊕P2467v,v1=P−1P135u⊕Pu1⊕P01356v,u3=P−1P24u⊕Pu1⊕P02457v,u4=P−1P02467u⊕Pu1⊕P023456v,u5=P−1P127u⊕Pu1⊕P1267v,u6=P0145u⊕P046v,u7=P0135u⊕P01356v,u8=P0347u⊕P357v,where P−1 is the inverse of P and PN is the sum of power of P for short; that is,(16)PN=⊕i∈NPi.For example,P236u=P2⊕P3⊕P6u.It is deduced that there are 3 free variablesu,v,u1. Given a pair of candidates u,v, all u1 should be enumerated to check whether this correspondent characteristic is possible or not. If there exists a set of u,v,u1 such that all conditions are satisfied, then u,v is a possible differential, and we do not need to guess the remaining candidate u1. The results from Algorithm 3 show that there are 61814 23-round impossible differentials with input difference 0,0,0,0,0,0,u,0 and output difference 0,v,v,v,0,0,0,v.The 24-round impossible differential is constructed by concatenating 15 rounds forward and 9 rounds backward. The equation system is built and simplified as(17)u2=P236u⊕v1⊕P02457v,v2=P−1P135u⊕Pu1⊕P046v,u3=P−1P24u⊕Pu1⊕P0357v,u4=P−1P02467u⊕Pu1⊕Pv1⊕P123467v,u5=P−1P127u⊕Pu1⊕Pv1⊕P124v,u6=P0145u⊕v1⊕P12467v,u7=P0135u⊕P046v,u8=P0347u⊕P01356v.Here, the free variables areu,v,u1,v1, and 738 impossible differentials are acquired totally.The 25-round impossible differential combines 15 rounds from the top and 10 rounds from the bottom. The equation system after simplification is(18)u2=P236u⊕v2⊕P357v,v3=P−1P135u⊕Pu1⊕P12467v,u3=P−1P24u⊕Pu1⊕Pv1⊕P01356v,u4=P−1P02467u⊕Pu1⊕Pv2⊕P34567v,u5=P−1P127u⊕Pu1⊕Pv2⊕Pv1⊕P01237v,u6=P0145u⊕v2⊕v1⊕P0157v,u7=P0135u⊕v1⊕P12467v,u8=P0347u⊕P046v.The free variables are chosen to beu,v,u1,v1,v2. By running through all candidate pairs, only 1 impossible differential is found, which is 0,0,0,0,0,0,ea,0↛0,e8,e8,e8,0,0,0,e8, where the numbers are presented in hexadecimal, and the prefix 0x is omitted.Note that this method is also applied to 22-round and 26-round. For CSA-BC reduced to 22 rounds, the same results are obtained as in [18], which verified the correctness of our method. For 26-round CSA-BC consisting of 16-round encryption and 10-round decryption, the results confirmed the nonexistence of impossible difference of this considered type.


### 4.3. Effect of Sbox on Impossible Differentials

Since the information on Sbox is involved in our search algorithm for impossible differentials, to verify the dependency of impossible differentials and Sboxes, the Sbox of CSA-BC is replaced by the AES Sbox. AES Sbox [27] is constructed by the inversion function, and it possesses the optimal differential property among 8-bit permutations found so far. The experiment is carried out to the modified cipher, which adopts an identical structure but uses AES Sbox in round function F instead. Then, the same search procedure is repeated. The comparative results are listed in Table 6.Table 6
Number of impossible differentials for CSA-BC with different Sbox.
Distinguisher length232425CSA-BC618147381CSA-BC with AES Sbox515374780When the original Sbox of CSA-BC is replaced by the AES Sbox, the number of 23/24/25-round impossible differentials decreased significantly, which means that our search algorithm is indeed closely related to the detail of the Sbox. An example is that0,0,0,0,0,0,ea,0↛0,e8,e8,e8,0,0,0,e8 is a 25-round impossible differential for CSA. However, it is possible when the Sbox is replaced by the AES Sbox. Since there are few results on Sbox-related impossible differential, our method may be a possible tool to search for Sbox-related impossible differentials of similar block ciphers. In addition, as far as the number of impossible differentials is concerned, replacing the Sbox of CSA-BC with AES Sbox might improve its resistance against impossible differential attack for CSA-BC.


### 4.4. Key Recovery Attacks against 25-Round CSA-BC and CSA

Hereinbefore, impossible differential distinguishers have been constructed for CSA-BC reduced to 23/24/25 rounds. As there is only one impossible differential for 25 rounds, to achieve better attack performance, we will mount the key recovery attack against 25-round CSA-BC and CSA using the 24-round impossible differentials found above.As is presented in Figure3, 1 round is appended at the end of the 24-round impossible differentials. The detailed attack procedure is as follows:(1)
Define a plaintext structure whose 7-th byte takes all possible values and others constant(19)Λ=c0,c1,c2,c3,c4,c5,x,c6|x∈F28,whereci0≤i≤6 are constants over F28. For any two plaintexts in Λ, their difference will be of the form 0,0,0,0,0,0,∗,0.(2)
Choose2N structures, and then 2N+15 pairs will be generated with the desired input difference. Choose pairs whose difference of the ciphertext is(20)v,v,v,0,0,Pw,v,w,v,w∈F28∗.The probability that the difference of ciphertext pairs is of this expected form is2−48. As there are 738 24-round impossible differentials, that is, 738 u,v candidates, the proportion of pairs in accordance with the input and output difference of the attack scenario is 738/216≈2−6.47. Therefore, the probability that a plaintext pair from Step (1) results in the desired difference in ciphertext is 2−48×2−6.47=2−54.47, and the number of pairs satisfying the attack scenario is 2N+15×2−54.47=2N−39.47.(3)
Guess the round keys in the last round and decrypt for 1 round. If the difference after decryption is0,v,v,v,0,0,0,v, discard this key candidate and try another. Repeat this process until only the right key is left. The remaining key bits could be recovered by brute force attack.Figure 3
Key recovery attack of 25-round CSA-BC.The probability that a wrong key leads to the required difference in the key recovery process is1−2−8; then there would be 28−1⋅1−2−82N−39.47 wrong keys left. When we take N=50.5, the expected wrong key left after filtering is approximately 0.07. In this case, all wrong keys are thought to be removed. Hence, the data complexity is 250.5×28=258.5 chosen plaintexts. According to the quick-sort method, the time complexity of the data filtration phase is 250.5×28×log228=261.5 comparison. In the worst case, 2N−39.47×28=220.03 1-round decryption will be needed, which is neglectable compared with the date filtration phase. As a counter is used in data filtration and should be kept for the key candidate and the pairs after filtration, the memory complexity is 28+211.03+28≈211.35 memory units.As is pointed out in [17], a structural flaw could be exploited to extend the attack of block cipher CSA-BC to the whole algorithm CSA. Here, a similar method could be adopted where the first block is active and others are inactive. Choose the plaintext of the first block as in Step (1) and mount the same procedures of its ciphertext as in Steps (2) and (3); the keys could be recovered with data complexity 258.5 chosen plaintexts, time complexity 261.5 comparison, and memory complexity 211.35 memory units. The results are listed in Table 1.


## 4.1. Description of CSA-BC

Digital Video Broadcast (DVB) is a series of standards for digital television. It is widely applied in most countries and regions in the world. The Digital Video Broadcast Common Scrambling Algorithm (DVB-CSA, or CSA for short) is mainly specified to guarantee the secure transmitting of MPEG-2 signal in Pay-TV and was adopted by the DVB consortium in 1994. The encryption process of CSA can be divided into two parts, the block cipher part (CSA-BC) and the stream cipher part (CSA-SC).CSA-BC is a 64-bit block cipher with a 64-bit key size. The state could be regarded as an 8-byte vector. And the plaintext is updated by the round functionF for 56 rounds.The round functionF is depicted in Figure 2 and works as follows. Denote its input and output as x0,x1,…,x7 and y0,y1,…,y7, respectively; then(11)y0=x1,y1=x2⊕x0,y2=x3⊕x0,y3=x4⊕x0,y4=x5,y5=x6⊕P°Sx7⊕k,y6=x7,y7=x0⊕Sx7⊕k,where k is the round key, S is the 8-bit to 8-bit Sbox (see [18, 26]), and P is a linear transformation that permutes the i-th bit in a byte into position Pi=1,7,5,4,2,6,0,3.Figure 2
Round function of CSA-BC.As our attack is independent of the key schedule and stream cipher, we omit that in this paper. Readers interested are referred to [18, 26] for more details.For CSA-BC, current works mainly focus on its security evaluation against impossible differential attacks. [17, 18] In 2016, Zhang et al. [17] proposed the first structural impossible differential attack. Then it is improved to 22 rounds by taking the DDT of the Sbox into consideration [18]. The analytical results of CSA-BC are listed in Table 1.


## 4.2. Impossible Differentials for CSA-BC

In [17, 18], impossible differentials with the pattern(12)0,0,0,0,0,0,u,0↛0,v,v,v,0,0,0,v,u,v≠0are considered. In this section, we will still study impossible differentials of this type as it diffuses relatively slower. Since more variables are involved in longer impossible differentials, we combined various search strategies as in Section 3, and better results were obtained.Table 4
Differential propagation from encryption direction.
Differential state0(0,0,0,0,0,0,u,0)1(0,0,0,0,0,u,0,0)2(0,0,0,0,u,0,0,0)3(0,0,0,u,0,0,0,0)4(0,0,u,0,0,0,0,0)5(0,u,0,0,0,0,0,0)6(u,0,0,0,0,0,0,0)7(0,u,u,u,0,0,0,u)8u,u,u,0,0,Pu1,u,u19u,0,u,u,Pu1,u⊕Pu2,u1,u⊕u210(0,0,0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2,u⊕u3)11(0,0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3,u4)12(0,u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3⊕Pu5,u4,u5)13(u⊕Pu1,u⊕Pu2,u1⊕Pu3,u⊕u2⊕Pu4, u⊕u3⊕Pu5,u4⊕Pu6,u5,u6)14(u⊕Pu2,u⊕u1⊕Pu1⊕Pu3,Pu1⊕u2⊕Pu4, Pu1⊕u3⊕Pu5,u4⊕Pu6,u5⊕Pu7,u6, u⊕Pu1⊕u7)15(u⊕u1⊕Pu1⊕Pu3,u⊕u2⊕Pu1⊕Pu2⊕Pu4,u⊕u3⊕Pu1⊕Pu2⊕Pu5, u⊕u4⊕Pu2⊕Pu6,u5⊕Pu7,u6⊕Pu8,u⊕Pu1⊕u7,u⊕Pu2⊕u8)16(u⊕u2⊕Pu1⊕Pu2⊕Pu4,u1⊕u3⊕Pu2⊕Pu3⊕Pu5, u1⊕u4⊕Pu1⊕Pu2⊕Pu3⊕Pu6, u⊕u1⊕u5⊕Pu1⊕Pu3⊕Pu7,u6⊕Pu8,u⊕u7⊕Pu1⊕Pu9, u⊕Pu2⊕u8,u⊕u1⊕u9⊕Pu1⊕Pu3)According to Figure2, one byte is nonlinearly transformed after one round; therefore, only one new variable needs to be introduced to describe the differential propagation. From the encryption direction, the 16-round propagation is shown in Table 4, where u∈F28∗ and ui∈F28,1≤i≤9. The constraints are(13)DDTu,u1>0,DDTu1,u2>0,DDTu⊕u2,u3>0,DDTu⊕u3,u4>0,DDTu4,u5>0,DDTu5,u6>0,DDTu6,u7>0,DDTu⊕u7⊕Pu1,u8>0,DDTu⊕u8⊕Pu2,u9>0.Because one variable is introduced in the beginning and new variables are brought from the 8-th round, there arer1−6 variables in total for an r1-round r1>7 encryption.Using a similar strategy, the 10-round propagation from the decryption direction could be obtained, and it is shown in Table5, where v∈F28∗ and vi∈F28,1≤i≤3. The conditions for Sbox are DDTv,v1>0, DDTPv1,v2>0, and DDTPv2,v3>0. The number of variables needed to describe the differential propagation for an r2-round decryption is also r2−6 when r2>7.Table 5
Differential propagation from decryption direction.
Differential state0(0,v,v,v,0,0,0,v)1(v,0,0,0,0,0,0,0)2(0,v,0,0,0,0,0,0)3(0,0,v,0,0,0,0,0)4(0,0,0,v,0,0,0,0)5(0,0,0,0,v,0,0,0)6(0,0,0,0,0,v,0,0)7(0,0,0,0,0,0,v,0)8v1,0,v1,v1,v1,0,Pv1,v9(v⊕v2,v1,v⊕v2,v⊕v1⊕v2, v⊕v1⊕v2,v1,Pv2,Pv1)10(v3⊕Pv1,v⊕v2,v1⊕v3⊕Pv1,v⊕v2⊕v3⊕Pv1, v⊕v1⊕v2⊕v3⊕Pv1, v⊕v1⊕v2,v1⊕Pv3,Pv2)To search forr-round (r=r1+r2 and r≥20) impossible differentials, r−12 8-bit variables will be introduced. Given the differential state from both sides, 8 equations could be built by assuming they match in all positions, and 8 controlled variables will be deduced correspondingly. Therefore, only r−20 bytes need to be guessed instead of r−12. At the same time, those variables are input and output differences of the Sbox; hence, they are also required to satisfy the DDT of the Sbox. It should be pointed out that the work of both [17, 18] are special cases of our algorithm.The 23-round impossible differential is built by concatenating 15 rounds from the encryption direction and 8 rounds from the decryption direction. If they match in every byte, then the equation system for the middle state is built as(14)u⊕u1⊕Pu1⊕Pu3=v1,u⊕u2⊕Pu1⊕Pu2⊕Pu4=0,u⊕u3⊕Pu1⊕Pu2⊕Pu5=v1,u⊕u4⊕Pu2⊕Pu6=v1,u5⊕Pu7=v1,u6⊕Pu8=0,u⊕Pu1⊕u7=Pv1,u⊕Pu2⊕u8=v.Since the controlled variables could be expressed as linear functions of free variables, the equation system is transformed by the Gaussian elimination method to(15)u2=P236u⊕P2467v,v1=P−1P135u⊕Pu1⊕P01356v,u3=P−1P24u⊕Pu1⊕P02457v,u4=P−1P02467u⊕Pu1⊕P023456v,u5=P−1P127u⊕Pu1⊕P1267v,u6=P0145u⊕P046v,u7=P0135u⊕P01356v,u8=P0347u⊕P357v,where P−1 is the inverse of P and PN is the sum of power of P for short; that is,(16)PN=⊕i∈NPi.For example,P236u=P2⊕P3⊕P6u.It is deduced that there are 3 free variablesu,v,u1. Given a pair of candidates u,v, all u1 should be enumerated to check whether this correspondent characteristic is possible or not. If there exists a set of u,v,u1 such that all conditions are satisfied, then u,v is a possible differential, and we do not need to guess the remaining candidate u1. The results from Algorithm 3 show that there are 61814 23-round impossible differentials with input difference 0,0,0,0,0,0,u,0 and output difference 0,v,v,v,0,0,0,v.The 24-round impossible differential is constructed by concatenating 15 rounds forward and 9 rounds backward. The equation system is built and simplified as(17)u2=P236u⊕v1⊕P02457v,v2=P−1P135u⊕Pu1⊕P046v,u3=P−1P24u⊕Pu1⊕P0357v,u4=P−1P02467u⊕Pu1⊕Pv1⊕P123467v,u5=P−1P127u⊕Pu1⊕Pv1⊕P124v,u6=P0145u⊕v1⊕P12467v,u7=P0135u⊕P046v,u8=P0347u⊕P01356v.Here, the free variables areu,v,u1,v1, and 738 impossible differentials are acquired totally.The 25-round impossible differential combines 15 rounds from the top and 10 rounds from the bottom. The equation system after simplification is(18)u2=P236u⊕v2⊕P357v,v3=P−1P135u⊕Pu1⊕P12467v,u3=P−1P24u⊕Pu1⊕Pv1⊕P01356v,u4=P−1P02467u⊕Pu1⊕Pv2⊕P34567v,u5=P−1P127u⊕Pu1⊕Pv2⊕Pv1⊕P01237v,u6=P0145u⊕v2⊕v1⊕P0157v,u7=P0135u⊕v1⊕P12467v,u8=P0347u⊕P046v.The free variables are chosen to beu,v,u1,v1,v2. By running through all candidate pairs, only 1 impossible differential is found, which is 0,0,0,0,0,0,ea,0↛0,e8,e8,e8,0,0,0,e8, where the numbers are presented in hexadecimal, and the prefix 0x is omitted.Note that this method is also applied to 22-round and 26-round. For CSA-BC reduced to 22 rounds, the same results are obtained as in [18], which verified the correctness of our method. For 26-round CSA-BC consisting of 16-round encryption and 10-round decryption, the results confirmed the nonexistence of impossible difference of this considered type.


## 4.3. Effect of Sbox on Impossible Differentials

Since the information on Sbox is involved in our search algorithm for impossible differentials, to verify the dependency of impossible differentials and Sboxes, the Sbox of CSA-BC is replaced by the AES Sbox. AES Sbox [27] is constructed by the inversion function, and it possesses the optimal differential property among 8-bit permutations found so far. The experiment is carried out to the modified cipher, which adopts an identical structure but uses AES Sbox in round function F instead. Then, the same search procedure is repeated. The comparative results are listed in Table 6.Table 6
Number of impossible differentials for CSA-BC with different Sbox.
Distinguisher length232425CSA-BC618147381CSA-BC with AES Sbox515374780When the original Sbox of CSA-BC is replaced by the AES Sbox, the number of 23/24/25-round impossible differentials decreased significantly, which means that our search algorithm is indeed closely related to the detail of the Sbox. An example is that0,0,0,0,0,0,ea,0↛0,e8,e8,e8,0,0,0,e8 is a 25-round impossible differential for CSA. However, it is possible when the Sbox is replaced by the AES Sbox. Since there are few results on Sbox-related impossible differential, our method may be a possible tool to search for Sbox-related impossible differentials of similar block ciphers. In addition, as far as the number of impossible differentials is concerned, replacing the Sbox of CSA-BC with AES Sbox might improve its resistance against impossible differential attack for CSA-BC.


## 4.4. Key Recovery Attacks against 25-Round CSA-BC and CSA

Hereinbefore, impossible differential distinguishers have been constructed for CSA-BC reduced to 23/24/25 rounds. As there is only one impossible differential for 25 rounds, to achieve better attack performance, we will mount the key recovery attack against 25-round CSA-BC and CSA using the 24-round impossible differentials found above.As is presented in Figure3, 1 round is appended at the end of the 24-round impossible differentials. The detailed attack procedure is as follows:(1)
Define a plaintext structure whose 7-th byte takes all possible values and others constant(19)Λ=c0,c1,c2,c3,c4,c5,x,c6|x∈F28,whereci0≤i≤6 are constants over F28. For any two plaintexts in Λ, their difference will be of the form 0,0,0,0,0,0,∗,0.(2)
Choose2N structures, and then 2N+15 pairs will be generated with the desired input difference. Choose pairs whose difference of the ciphertext is(20)v,v,v,0,0,Pw,v,w,v,w∈F28∗.The probability that the difference of ciphertext pairs is of this expected form is2−48. As there are 738 24-round impossible differentials, that is, 738 u,v candidates, the proportion of pairs in accordance with the input and output difference of the attack scenario is 738/216≈2−6.47. Therefore, the probability that a plaintext pair from Step (1) results in the desired difference in ciphertext is 2−48×2−6.47=2−54.47, and the number of pairs satisfying the attack scenario is 2N+15×2−54.47=2N−39.47.(3)
Guess the round keys in the last round and decrypt for 1 round. If the difference after decryption is0,v,v,v,0,0,0,v, discard this key candidate and try another. Repeat this process until only the right key is left. The remaining key bits could be recovered by brute force attack.Figure 3
Key recovery attack of 25-round CSA-BC.The probability that a wrong key leads to the required difference in the key recovery process is1−2−8; then there would be 28−1⋅1−2−82N−39.47 wrong keys left. When we take N=50.5, the expected wrong key left after filtering is approximately 0.07. In this case, all wrong keys are thought to be removed. Hence, the data complexity is 250.5×28=258.5 chosen plaintexts. According to the quick-sort method, the time complexity of the data filtration phase is 250.5×28×log228=261.5 comparison. In the worst case, 2N−39.47×28=220.03 1-round decryption will be needed, which is neglectable compared with the date filtration phase. As a counter is used in data filtration and should be kept for the key candidate and the pairs after filtration, the memory complexity is 28+211.03+28≈211.35 memory units.As is pointed out in [17], a structural flaw could be exploited to extend the attack of block cipher CSA-BC to the whole algorithm CSA. Here, a similar method could be adopted where the first block is active and others are inactive. Choose the plaintext of the first block as in Step (1) and mount the same procedures of its ciphertext as in Steps (2) and (3); the keys could be recovered with data complexity 258.5 chosen plaintexts, time complexity 261.5 comparison, and memory complexity 211.35 memory units. The results are listed in Table 1.


## 5. Constructing Impossible Differentials for FOX64

In this section, we will first introduce the FOX64 block cipher, then our search method will be applied, and the improved results will be discussed.


### 5.1. FOX64 Block Cipher

The block cipher FOX, also known as IDEA-NXT, was proposed by Junod and Vaudenay in 2004 [28]. It was designed to have a high-security level, large implementation flexibility, and high performance on various platforms. FOX employs the Lai-Massey structure and an SPS-type round function, and it proved to be immune to differential and linear attacks. The 64-bit block length and 128-bit key length version of FOX is called FOX64, and it has 16 rounds in total.FOX64 employs the Lai-Massey structure, as is shown in Figure4. Denote the input and output of FOX64 as x1,x2,y1,y2, respectively; then(21)y1=orx1⊕Fx1⊕x2,rk,y2=x2⊕Fx1⊕x2,rk,where rk is the round key. The orthomorphism or uses a 1-round Feistel transformation. Denote the 32-bit input as l,r∈F2162; then(22)orl,r=r,l⊕r.Figure 4
Structure of FOX64.The round functionF employs an SPS-type design. It is composed of three parts: substitution part sigma4, diffusion part mu4, and round key addition part. The round function F takes a 32-bit input x and a 64-bit round key rk=rk1‖rk2; then(23)Fx,rk=sigma4mu4sigma4x⊕rk1⊕rk2⊕rk1.The substitution layer consists of 4 identical 8-bit Sboxes. The detailed permutation of the Sbox and its construction is discussed in [28]. The diffusion layer is a matrix multiplication over a finite field. The 32-bit input is regarded as a 4-dimensional vector over F28, and the 4×4 matrix is(24)mu4=1,1,1,α1,z,α,1z,α,1,1α,1,z,1,where F28=F2α, α is a root of polynomial x8⊕x7⊕x6⊕x5⊕x4⊕x3⊕1, and z=α−1⊕1.The security of FOX64 and its high-level structure are extensively studied [29–32]. For the impossible differential attack, Wu et al. [33] presented an impossible differential for 4-round FOX64 of the following form 0,u,0,u,0,u,0,u↛v1,v2,v1,v3,v1,v2,v1,v3. This distinguisher is further improved and generalized in [34]. In 2016, Li et al. used multiple impossible differentials and various techniques to mount an 8-round key recovery attack using similar 4-round impossible differentials [35]. The analytical results of FOX are listed in Table 2.


### 5.2. Impossible Differentials for FOX64

The impossible differentials are constructed using the method in Section3. Using Algorithm 3, the relationship between FOX64 and its round function F is first observed as the following theorem by exploiting the middle state conditions.Theorem 1.
Verifying a differential of the following form for 4-round FOX64(25)u1,u2,u3,u4,u1,u2,u3,u4⟶4−roundFOXv1,v2,v3,v4,v1,v2,v3,v4is equivalent to verifying a differential of its round function whereui,vi∈F28. Furthermore, an impossible differential for its round function will always imply an impossible differential for 4-round FOX64.Proof.
First, the differential propagation of FOX64 is presented in Figure 5.
For any input differenceu1,u2,u3,u4,u1,u2,u3,u4∈F288, the output difference after 2-round encryption is u1⊕u3⊕u11,u2⊕u4⊕u12,u1⊕u9⊕u11,u2⊕u10⊕u12,u1⊕u9,u2⊕u10,u3⊕u11,u4⊕u12, where u5−8 and u9−12 are the output difference after the first and second Sbox layer in the second round. Likewise, the output of 2-round decryption could also be derived as v1⊕v3⊕v9,v2⊕v4⊕v10,v1⊕v11,v2⊕v12,v1⊕v9,v2⊕v10,v3⊕v11,v4⊕v12. And v5−8 and v9−12 are the output difference after the first and second Sbox layers in the second round.
The 4-round impossible differentials are constructed by combining 2-round encryption and 2-round decryption. As possible differentials will match in all positions in the middle state, an equation system could be built reflecting this internal relationship(26)u1⊕u3⊕u11=v1⊕v3⊕v9,u2⊕u4⊕u12=v2⊕v4⊕v10,u1⊕u9⊕u11=v1⊕v11,u2⊕u10⊕u12=v2⊕v12,u1⊕u9=v1⊕v9,u2⊕u10=v2⊕v10,u3⊕u11=v3⊕v11,u4⊕u12=v4⊕v12.
This equation system could be simplified by the Gaussian elimination method as(27)u9=u1⊕u3⊕v1⊕v3,u10=u2⊕u4⊕v2⊕v4,u11=u1⊕v1,u12=u2⊕v2,v9=u3⊕v3,v10=u4⊕v4,v11=u1⊕u3⊕v1⊕v3,v12=u2⊕u4⊕v2⊕v4.
When verifying whether a 4-round differential of FOX64 is possible or not, this relationship among intermediate variables produces 8-byte controlled variables.
The determining process could be further separated into two independent parts. According to the structure of FOX64, thoseui’s are only involved in the second round function, and vi’s are only involved in the third. Therefore, the determining process could be divided into checking the validity of the following two differentials for the round function F(28)u1⊕u3,u2⊕u4,u1,u2⟶Fu9,u10,u11,u12,v3,v4,v1⊕v3,v2⊕v4⟶Fv9,v10,v11,v12.
That is, verifying a differential for 4-round FOX64 is equivalent to verifying one differential of its round function. If the differential is impossible forF, it implies one impossible differential for 4-round FOX64.Figure 5
Differential propagation of 4-round FOX64.Remark 3.
In Theorem1 and its proof, the relationship between 4-round FOX and its round functions is derived by exploiting the middle state conditions only. It indicates when an impossible differential for F is detected, it could be extended to FOX64 by equations (27) and (28). Then the search for impossible differential of 4-round FOX is transformed to checking the possibility of differentials of round function F, which corresponds to the Sbox conditions in Algorithm 3, and the early-abort technique will also work. According to equation (27), the controlled variables are ui,vi9≤i≤12, the free variables in the difference pattern are ui,vi1≤i≤4, and the remaining free variables are ui,vi5≤i≤8. To check the possibility of u1⊕u3,u2⊕u4,u1,u2⟶Fu9,u10,u11,u12 as in equation (28), all ui,vi5≤i≤8 are required to be enumerated. Assuming the difference after mu4 is x1,x2,x3,x4=mu4u5,u6,u7,u8, then the Sbox conditions are(29)DDTu1⊕u3,u5>0,DDTu2⊕u4,u6>0,DDTu1,u7>0,DDTu2,u8>0,DDTx1,u9>0,DDTx1,u10>0,DDTx3,u11>0,DDTx4,u12>0.
When all those Sbox conditions are satisfied, then this characteristic is possible, indicating the 4-round differential is also possible. And this differential is impossible only when at least one Sbox condition is not satisfied for each characteristic, that is, each set ofui,vi5≤i≤8.
This theorem indicates that the search of impossible differentials for FOX64 is equivalent to that of its round function. The complexity is reduced toO233, which is practical for current personal computers. The experimental results indicate that verifying one difference for FOX64 requires approximately 10−6 seconds on average. Moreover, previous works could also be obtained by our method.
Using the above method, we are capable of finding new impossible differentials for FOX64 with a more freedom degree. The results show that the number of impossible differentials of the following form for round functionF(30)01,00,00,00↛v1,v2,v3,v4,where vi∈F28∗, is 1197321873, accounting for 28.31% of the whole space approximately. And the time taken is 2133 seconds. When the input difference of F is 01,02,00,00, this proportion is reduced to 2−18.85, 8941 impossible differentials in total.
After acquiring the impossible differential for round functionF, the impossible differential for 4-round FOX64 could be constructed accordingly. For example, 01,02,00,00↛ff,fa,11,cc is an impossible differential for F; then(31)u1⊕u3,u2⊕u4,u1,u2=01,02,00,00,u9,u10,u11,u12=ff,fa,11,cc.
According to (27), v1−4 could be computed as(32)v1,v2,v3,v4=11,cc,ef,34.
That is,(33)00,00,01,02,00,00,01,02↛11,cc,ef,34,11,cc,ef,34is a 4-round impossible differential for FOX64.


## 5.1. FOX64 Block Cipher

The block cipher FOX, also known as IDEA-NXT, was proposed by Junod and Vaudenay in 2004 [28]. It was designed to have a high-security level, large implementation flexibility, and high performance on various platforms. FOX employs the Lai-Massey structure and an SPS-type round function, and it proved to be immune to differential and linear attacks. The 64-bit block length and 128-bit key length version of FOX is called FOX64, and it has 16 rounds in total.FOX64 employs the Lai-Massey structure, as is shown in Figure4. Denote the input and output of FOX64 as x1,x2,y1,y2, respectively; then(21)y1=orx1⊕Fx1⊕x2,rk,y2=x2⊕Fx1⊕x2,rk,where rk is the round key. The orthomorphism or uses a 1-round Feistel transformation. Denote the 32-bit input as l,r∈F2162; then(22)orl,r=r,l⊕r.Figure 4
Structure of FOX64.The round functionF employs an SPS-type design. It is composed of three parts: substitution part sigma4, diffusion part mu4, and round key addition part. The round function F takes a 32-bit input x and a 64-bit round key rk=rk1‖rk2; then(23)Fx,rk=sigma4mu4sigma4x⊕rk1⊕rk2⊕rk1.The substitution layer consists of 4 identical 8-bit Sboxes. The detailed permutation of the Sbox and its construction is discussed in [28]. The diffusion layer is a matrix multiplication over a finite field. The 32-bit input is regarded as a 4-dimensional vector over F28, and the 4×4 matrix is(24)mu4=1,1,1,α1,z,α,1z,α,1,1α,1,z,1,where F28=F2α, α is a root of polynomial x8⊕x7⊕x6⊕x5⊕x4⊕x3⊕1, and z=α−1⊕1.The security of FOX64 and its high-level structure are extensively studied [29–32]. For the impossible differential attack, Wu et al. [33] presented an impossible differential for 4-round FOX64 of the following form 0,u,0,u,0,u,0,u↛v1,v2,v1,v3,v1,v2,v1,v3. This distinguisher is further improved and generalized in [34]. In 2016, Li et al. used multiple impossible differentials and various techniques to mount an 8-round key recovery attack using similar 4-round impossible differentials [35]. The analytical results of FOX are listed in Table 2.


## 5.2. Impossible Differentials for FOX64

The impossible differentials are constructed using the method in Section3. Using Algorithm 3, the relationship between FOX64 and its round function F is first observed as the following theorem by exploiting the middle state conditions.Theorem 1.
Verifying a differential of the following form for 4-round FOX64(25)u1,u2,u3,u4,u1,u2,u3,u4⟶4−roundFOXv1,v2,v3,v4,v1,v2,v3,v4is equivalent to verifying a differential of its round function whereui,vi∈F28. Furthermore, an impossible differential for its round function will always imply an impossible differential for 4-round FOX64.Proof.
First, the differential propagation of FOX64 is presented in Figure 5.
For any input differenceu1,u2,u3,u4,u1,u2,u3,u4∈F288, the output difference after 2-round encryption is u1⊕u3⊕u11,u2⊕u4⊕u12,u1⊕u9⊕u11,u2⊕u10⊕u12,u1⊕u9,u2⊕u10,u3⊕u11,u4⊕u12, where u5−8 and u9−12 are the output difference after the first and second Sbox layer in the second round. Likewise, the output of 2-round decryption could also be derived as v1⊕v3⊕v9,v2⊕v4⊕v10,v1⊕v11,v2⊕v12,v1⊕v9,v2⊕v10,v3⊕v11,v4⊕v12. And v5−8 and v9−12 are the output difference after the first and second Sbox layers in the second round.
The 4-round impossible differentials are constructed by combining 2-round encryption and 2-round decryption. As possible differentials will match in all positions in the middle state, an equation system could be built reflecting this internal relationship(26)u1⊕u3⊕u11=v1⊕v3⊕v9,u2⊕u4⊕u12=v2⊕v4⊕v10,u1⊕u9⊕u11=v1⊕v11,u2⊕u10⊕u12=v2⊕v12,u1⊕u9=v1⊕v9,u2⊕u10=v2⊕v10,u3⊕u11=v3⊕v11,u4⊕u12=v4⊕v12.
This equation system could be simplified by the Gaussian elimination method as(27)u9=u1⊕u3⊕v1⊕v3,u10=u2⊕u4⊕v2⊕v4,u11=u1⊕v1,u12=u2⊕v2,v9=u3⊕v3,v10=u4⊕v4,v11=u1⊕u3⊕v1⊕v3,v12=u2⊕u4⊕v2⊕v4.
When verifying whether a 4-round differential of FOX64 is possible or not, this relationship among intermediate variables produces 8-byte controlled variables.
The determining process could be further separated into two independent parts. According to the structure of FOX64, thoseui’s are only involved in the second round function, and vi’s are only involved in the third. Therefore, the determining process could be divided into checking the validity of the following two differentials for the round function F(28)u1⊕u3,u2⊕u4,u1,u2⟶Fu9,u10,u11,u12,v3,v4,v1⊕v3,v2⊕v4⟶Fv9,v10,v11,v12.
That is, verifying a differential for 4-round FOX64 is equivalent to verifying one differential of its round function. If the differential is impossible forF, it implies one impossible differential for 4-round FOX64.Figure 5
Differential propagation of 4-round FOX64.Remark 3.
In Theorem1 and its proof, the relationship between 4-round FOX and its round functions is derived by exploiting the middle state conditions only. It indicates when an impossible differential for F is detected, it could be extended to FOX64 by equations (27) and (28). Then the search for impossible differential of 4-round FOX is transformed to checking the possibility of differentials of round function F, which corresponds to the Sbox conditions in Algorithm 3, and the early-abort technique will also work. According to equation (27), the controlled variables are ui,vi9≤i≤12, the free variables in the difference pattern are ui,vi1≤i≤4, and the remaining free variables are ui,vi5≤i≤8. To check the possibility of u1⊕u3,u2⊕u4,u1,u2⟶Fu9,u10,u11,u12 as in equation (28), all ui,vi5≤i≤8 are required to be enumerated. Assuming the difference after mu4 is x1,x2,x3,x4=mu4u5,u6,u7,u8, then the Sbox conditions are(29)DDTu1⊕u3,u5>0,DDTu2⊕u4,u6>0,DDTu1,u7>0,DDTu2,u8>0,DDTx1,u9>0,DDTx1,u10>0,DDTx3,u11>0,DDTx4,u12>0.
When all those Sbox conditions are satisfied, then this characteristic is possible, indicating the 4-round differential is also possible. And this differential is impossible only when at least one Sbox condition is not satisfied for each characteristic, that is, each set ofui,vi5≤i≤8.
This theorem indicates that the search of impossible differentials for FOX64 is equivalent to that of its round function. The complexity is reduced toO233, which is practical for current personal computers. The experimental results indicate that verifying one difference for FOX64 requires approximately 10−6 seconds on average. Moreover, previous works could also be obtained by our method.
Using the above method, we are capable of finding new impossible differentials for FOX64 with a more freedom degree. The results show that the number of impossible differentials of the following form for round functionF(30)01,00,00,00↛v1,v2,v3,v4,where vi∈F28∗, is 1197321873, accounting for 28.31% of the whole space approximately. And the time taken is 2133 seconds. When the input difference of F is 01,02,00,00, this proportion is reduced to 2−18.85, 8941 impossible differentials in total.
After acquiring the impossible differential for round functionF, the impossible differential for 4-round FOX64 could be constructed accordingly. For example, 01,02,00,00↛ff,fa,11,cc is an impossible differential for F; then(31)u1⊕u3,u2⊕u4,u1,u2=01,02,00,00,u9,u10,u11,u12=ff,fa,11,cc.
According to (27), v1−4 could be computed as(32)v1,v2,v3,v4=11,cc,ef,34.
That is,(33)00,00,01,02,00,00,01,02↛11,cc,ef,34,11,cc,ef,34is a 4-round impossible differential for FOX64.


## 6. Conclusion

In this paper, we proposed a new Sbox-related impossible differential search method combining the guess-and-determine and early-abort techniques. Our method is able to exploit more detailed information on Sboxes, and the impossible differentials found are closely related to the choice of Sboxes. Besides, our method is independent of a third-party solver and applicable to ciphers with Sboxes of large size (≥8 bits).Then this method is applied to CSA-BC and FOX64. With our method, 23/24/25-round impossible differentials for CSA-BC were found in less than 5 seconds. Those results are the longest impossible differentials for CSA-BC so far. And key recovery attacks were improved by 4 rounds using the impossible differentials found by our method. Those key recovery attacks are the longest impossible differential attack against CSA-BC and CSA by now. For FOX64, we first proved that an impossible differential for its round function will always imply one impossible differential for 4-round FOX64. Then new types of impossible differentials were able to be found with our method.Our results may help better understand the interaction between the structure and primitives of block ciphers. And the search method in this paper may provide a possible direction to take the large size of Sboxes into consideration and is applicable to other block ciphers with a similar structure.



---

*Source: 7196111-2022-09-05.xml*