# On the Complexity of Impossible Differential Cryptanalysis

Authors: Qianqian Yang; Lei Hu; Danping Shi; Yosuke Todo; Siwei Sun
Journal: Security and Communication Networks
 (2018)

---

## Abstract

While impossible differential attack is one of the most well-known and familiar techniques for symmetric-key cryptanalysts, its subtlety and complicacy make the construction and verification of such attacks difficult and error-prone. We introduce a new set of notations for impossible differential analysis. These notations lead to unified formulas for estimation of data complexities of ordinary impossible differential attacks and attacks employing multiple impossible differentials. We also identify an interesting point from the new formulas: in most cases, the data complexity is only related to the form of the underlying distinguisher and has nothing to do with how the differences at the beginning and the end of the distinguisher propagate in the outer rounds. We check the formulas with some examples, and the results are all matching. Since the estimation of the time complexity is flawed in some situations, in this work, we show under which condition the formula is valid and give a simple time complexity estimation for impossible differential attack which is always achievable.


---

## Body

## 1. Introduction

Impossible differential attack, introduced by Knudsen [1] and Biham et al. [2] independently, is one of the most well-known cryptanalytic techniques for symmetric-key cryptanalysts [3–9]. Generally, in impossible differential cryptanalysis, we guess some key bits involved in the outer rounds of the target cipher. Then the guess is rejected if it leads to impossible differentials at the inner rounds. Despite its extensive application in symmetric-key cryptanalysis, errors in the analysis are often discovered and many papers in the literature presented subtle flaws. Note that the flaws typically arise in the estimation of the time and data complexities rather than in the distinguisher, similar to searching differential and linear characteristic [10–13], the methodology of searching for impossible differential is fairly mature, and automatic tools are available [14–17]. To relieve the difficulty of the complexity analysis, Boura et al. presented generic complexity analysis formulas along with the development of new ideas for optimizing impossible differential cryptanalysis [18]. However, at FSE 2016, Derbez identified some flaws in the formulas for the time complexity estimation given in [18], and concrete examples were presented such that the time complexities estimated with the formulas given in [19] are not achievable.Our contribution follows Boura, Naya-Plasencia, Suder, and Derbez’s work at ASIACRYPT 2014, FSE 2016, and ESC 2017; we investigate further some aspects of the estimation of the impossible differential attack which have not been explored or stated explicitly in previous work.Firstly, we introduce a new set of notations for impossible differential analysis. With these notations, there is no difference between ordinary impossible differentials and multiple impossible differentials. Under some reasonable assumptions (the same assumptions were made implicitly in [18, 19]), we modify the formula in [18] for calculating the data complexity into a form getting rid of the parameters of the number of bit-conditions (the cin and cout notations in [18]) that have to be verified to follow some specified behavior in the outer rounds of a target cipher. Moreover, in the formulas derived with the new notations, we identify a very interesting and somehow strange point: in most cases, the data complexity is only related to the form of the underlying distinguisher and has nothing to do with how the differences at the beginning and the end of the distinguisher propagate in the outer rounds. That is, in most cases, the data complexity can be completely determined by the underlying impossible differential distinguisher employed in the attack. Hence, estimating the data complexity with the new formulas is much more easier and straightforward than that of [18].Secondly, since Derbez showed concrete examples where Boura et al.’s formula of the time complexity of impossible differential attack is invalid, we are interested in the condition under which the estimation of Boura et al. is correct, and we prove that the time complexity of the key-sieving process given by Boura et al. is not only achievable but also optimal if the key bits involved in the outer rounds are independent. Using the early abort technique presented by Lu et al. in [20, 21], we give the optimal result with detailed process.Finally, we give a formula to estimate the time complexity of the key-sieving process in the case where the key bits involved in the outer rounds are not independent. The estimation is not guaranteed to be equal to the complexity of the optimal attack as discussed by Derbez in [19], but it is always achievable. Therefore, the formula serves to give a rough estimation of an impossible differential attack without diving into complicated calculations and time-consuming search algorithms, which should be very useful in fast prototyping in cryptanalysis.We present a new set of notations for impossible differential analysis in Section2. Section 3 briefly shows impossible differential attacks. In Section 4, we modify the data formula, which is related to a few parameters and unifies multiple impossible differential attacks with ordinary impossible differential attacks. In Section 5 we prove that the formula of the time complexity is achievable and optimal with the key bits independent and give a rough estimation formula for the key bits without independence. At last we conclude the paper in Section 6.


## 2. Notations

LetF2={0,1} be the finite field of two elements. For a set A, its number of elements is denoted by A, and let A=log2(A). Also, for an integer n, let n=log2(n).In addition, we use some notations like regular expression to represent a set of bit strings. For example,1 is equivalent to the set {1}, 0 is equivalent to {0}, and 000**1 is equivalent to {000001,000011,000101,000111}, which is alternatively denoted by 03∗21, where the subscript tells the number of occurrences of the symbol concerned.Definition 1.
LetEK(·) be a block cipher and α, β∈F2n; if ∀K, EK(x⊕α)⊕EK(x)≠β for all x∈F2n, we call (α,β) an impossible differential of E, which is denoted by α↛β. More generally, let A, B⊆F2n; we call (A,B) an impossible differential, denoted by A↛B, if for any α∈A, ∃β∈B, such that α↛β, and for any β∈B, ∃α∈A, such that α↛β.Note that this notation is different from the notation of impossible differential we typically see in the literature, since in our notation, it is possible that ∃ α ∈ A and ∃ β ∈ B , such that α → β is not an impossible differential.LetIDEK(A,B)={(α,β):α↛β,α∈A,β∈B}, where IDEK is simply written as ID if EK is clear from the context. Then we have ID(A,B)≤A+B, and ID(A,B)=A+B in the special case for any α∈A and β∈B, α↛β. It is worth mentioning, with the new notation, that we can unify ordinary impossible differentials and multiple impossible differentials in impossible differential cryptanalysis.For example, if0011↛0001, 0011↛0010, and 0011→0011, with the new notation, we call (0011,00∗∗) an impossible differential, and ID(0011,00∗∗)=log2(2)=1.Definition 2.
LetA¯⊆F2n, and the structure δ(A¯) derived from A¯ is defined to be the set of all n-bit strings y=y0⋯yn-1 such that yi≡0 for all i∈{j:∀x∈A¯,xj=0}. Given a bit string x∈F2n, δx(A¯) is defined to be the set x+δ(A¯)={x⊕y:y∈δ(A¯)}.For example, ifA¯={0010,0011,1010,1011} and x=0100, then (1)δA¯=0000,0001,0010,0011,1000,1001,1010,1011and δ0100(A¯)={0100,0101,0110,0111,1100,1101,1110, 1111}. Recall that, in differential type of cryptanalysis, if we want to get many pairs of data whose differences are in a set A¯, we typically first prepare a structure δ(A¯) from which the needed pairs will be generated. From Figure 1, we can see the relationship in A, A¯, and δ(A¯).Figure 1
The relationship inA, A-, and δ(A).


## 3. Impossible Differential Attack

In contrast to ordinary differential attack which relies on differentials with high probability, impossible differential attack reduces the key space by identifying wrong key guesses with the aid of differentials which never occur.We show how to convert an impossible differential distinguisher into a key-recovery attack in Figure2. Firstly, we need to append some outer rounds (E1 with rin rounds and E3 with rout rounds) around the distinguisher (A,B) with rΔ rounds covering E2. Then we propagate the differences in A and B to both directions in the outer rounds to get A¯ and B_, where A¯ is the set of all differences having the possibility of creating an intermediate difference in A at the beginning of E2, and B_ is defined similarly. For fixed outer rounds, A¯ and B_ are not dependent on the involved secret key bits in the outer rounds. Actually they can be computed by propagating the difference patterns upwards and downwards according to the differential distribution table of the components of the cipher. Now we can identify the involved secret key bits in the outer rounds. These key bits are the secret information we are going to recover in the attack, which we call thetargeted key bits. Finally, we prepare some structures δx(A¯) and encrypt the plaintexts in δx(A¯) to get the corresponding ciphertexts. For each pair (P,P′) of plaintexts in δx(A¯) satisfying P⊕P′∈A¯, guess the secret key information kin∪kout involved in the outer rounds. If the partial encryption/decryption of (P,P′) and (E(P),E(P′)) leads to impossible differentials, the guess is certainly incorrect. With this strategy, hopefully we can reject lots of wrong guesses of kin∪kout, and the key space is therefore reduced. To calculate complexity of the attack, we define cin which is the number of bit-conditions that have to be verified to obtain A from A¯. In other words, the differences A¯ are propagated from A with probability 1 while the differential A←A¯ is verified with probability 1/2cin. Similarly, we can get the definition of cout.Figure 2
Generic vision of impossible differential attack.


## 4. On the Data Complexity of Impossible Differential Attack

Assuming that we have identified an impossible differentialA↛B, we propagate A and B differentials to both directions to get A¯ and B_. Then we prepare many structures δx(A¯) by varying x∈F2n. For each structure δx(A¯), there are 22δ(A¯)-1 pairs of plaintexts (P,P′) satisfying P⊕P′∈δ(A¯). Filtering the pairs by the condition that the differences of ciphertexts pairs are in δ(B_), we can get approximately (2)22δA¯-12n-δB_=22δA¯+δB_-n-1plaintext pairs (P,P′) such that (3)P⊕P′∈δA¯,EP⊕EP′∈δB_.Moreover, there are approximately(4)22δA¯+δB_-n-1·2A¯·2B_2δA¯·2δB_=2δA¯+A¯+B_-n-1pairs satisfying P⊕P′∈A¯ and E(P)⊕E(P′)∈B_.Definition 3.
A pair of plaintexts(P,P′) is (A,B)-effective if and only if P⊕P′∈A¯ and E(P)⊕E(P′)∈B_.According to the definitions ofA¯ and B_, only (A,B)-effective pairs have the potential to suggest wrong key guesses, since it is only possible for such pairs to lead to the impossible differential A↛B under wrong key guesses. From the above discussion, we have the following fact.Fact 4.
From one structureδx(A¯), approximately 2δ(A¯)+A¯+B_-n-1(A,B)-effective pairs can be generated.For an(A,B)-effective pair (P,P′), the probability that E1(P)⊕E1(P′)∈A under some random guess of the key information involved in E1 can be estimated as A/A¯=2A-A¯. Similarly, let (C,C′) be the ciphertexts of the (A,B)-effective pair (P,P′). Then the probability that E3-1(C)⊕E3-1(C′)∈B under some random guess of the key information involved in E3 can be estimated as B/B_=2B-B_.Fact 5.
The probability that an(A,B)-effective pair (P,P′) leads to an impossible differential (α,β)∈ID(A,B) after partial encryption/decryption with a random key guess is (5)2A2A¯·2B2B_·2IDA,B2A+B=2IDA,B-A¯-B_;that is, there are cID=A¯+B_-ID(A,B) bit-conditions that need to be verified for an (A,B)-effective pair to satisfy an impossible differential in ID(A,B).Note thatcID=A¯-A+B_-B is coincidence to the notation of cin+cout presented in [18] for any α∈A and β∈B, α↛β. Hence, the notion of cin+cout is actually a special case of our notion cID. This is demonstrated by the following two concrete examples.Example 6 (on the bit-conditions).
Take the impossible differential attacks on SIMON [22] presented in Appendix A.3 in [18] as an example. The impossible differential used in the attack and the outer rounds are redrawn in Figure 3, from which we have A={00000000000000000000000000000001}, B={00000000100000000000000000000000}, (6)A¯=000∗∗∗0∗01∗∗∗∗∗00∗∗∗∗∗∗1∗∗∗∗∗∗0∗B_=1∗∗∗∗∗∗0∗0∗∗∗∗∗∗∗01∗∗∗∗∗0000∗∗∗0Therefore, cID=A¯-A+B_-B=22-0+22-0=44, which is the same as [18] where cID is calculated as cin+cout=(8+7+5+2)+(2+5+7+8)=44. As can be seen in Figure 3,  cin+cout=c0+⋯+c3+c15+⋯+c18, where ci is the number of bit-conditions in ith round.Figure 3
The initial rounds (a) and the final rounds (b) of the attack on SIMON32/64.
(a) (b)Example 7 (on the bit-conditions).
Take the impossible differential attacks on 13-round CLEFIA-128 [23] presented in Section 3.2 of [18], for example. The impossible differentials used in the attack and the outer rounds are redrawn in Figure 4, from which we have A=096∗8024, B=072∗8048, A¯=032∗8024M0(∗8024)∗32, and B_=040∗8016M1(08∗8016)∗32. Therefore, cID=A¯-A+B_-B=48-8+48-8=80, which is the same as [18], where cID is calculated as cin+cout=40+40=80 which are depicted in Figure 4.Figure 4
The attack on CLEFIA-128.For an(A,B)-effective pair (P,P′), we can guess the key bits involved in E1 and E3 and get E1(P)⊕E1(P′) and E3-1(C)⊕E3-1(C′). If (E1(P)⊕E1(P′),E3-1(C)⊕E3-1(C′))∈ID(A,B), the key guess must be incorrect and therefore can be removed from the candidate key space safely. In this case, we say that a key guess is rejected by a set P of plaintext pairs if and only if the guess is rejected by at least one pair in P. Let kin∪kout be the target key space, and let P be the set of (A,B)-effective pairs generated from the chosen plaintexts. The goal of an impossible differential attack is to reject as many as possible keys in kin∪kout such that the target key space can be reduced significantly.According to Fact5, the probability that a key guess for kin∪kout is rejected by a given (A,B)-effective pair (P,P′)∈P is 2-cID. Therefore, the probability that a guess is not rejected by P is (1-2-cID)P.Therefore, the number of candidates keys in the target key space after performing the impossible differential analysis is(1-2-cID)Pkin∪kout. In the literature, we typically regard (1-2-cID)2cID approximately as e-1. Consequently, we need approximately (7)ζ-1=2cID=2A¯+B_-IDA,B(A,B)-effective pairs to reduce the target key space by log2e bit.Theorem 8.
With the probabilityPr=e-1=2-log2e, in other words, to reduce log2e-bit information of the space of key candidates, the data complexity is CNζ-1, where(8)CNζ-1=2n+1+δA¯-IDA,B/2,δA¯≥n+1-IDA,B;2n+1-IDA,B,δA¯≤n+1-IDA,B.Proof.
We are now ready to have a careful look at the data complexity needed to reduce at leastlog2e bit of information of the space of key candidates by considering two cases.
In the first case, 1 structureδ(A¯) is enough to generate ζ-1(A,B)-effective pairs. That is, (9)2δA¯+A¯+B_-n-1≥2A¯+B_-IDA,B,namely, δ(A¯)≥n+1-ID(A,B). Assuming that we need Nζ-1 plaintexts from δ(A¯), then (10)Nζ-1·Nζ-12·2δB_2n·2A¯·2B_2δA¯·2δB_=2A¯+B_-IDA,B,from which we can get Nζ-1=2(n+1+δ(A¯)-ID(A,B))/2.
In the second case, 1 structure is not enough to produceζ-1(A,B)-effective pairs, and we need 2s structures. In this case, we have (11)2s·2δA¯+A¯+B_-n-1=ζ-1=2A¯+B_-IDA,B.Therefore, we need 2s·2δ(A¯)=2n+1-ID(A,B) plaintexts.
From the above two cases, we can obtain formula (8).Corollary 9.
With the probabilityPr=e-2α=2-2α·log2e, in other words, to reduce 2α·log2e-bit information of the space of key candidates, the data complexity is CNζ-α, where(12)CNζ-α=2n+1+δA¯-IDA,B/2·2α/2,δA¯≥n+1-IDA,B+α;2n+1-IDA,B·2α,δA¯≤n+1-IDA,B+α.From Theorem8, we can get Corollary 9 easily with the same method. According to Theorem 8, while A=B=0, namely, for one bit-level impossible differential, the minimum data complexity is 2n+1. Obviously, the amount of all data is 2n, which is less than the minimum data complexity needed for a feasible impossible differential attack.Corollary 10.
If only using one bit-level impossible differential, which isA=B=0, then there does not exist a successful impossible differential attack.In our formulas, the computation of the data complexity for standard impossible differential analysis and attacks based on multiple impossible differentials are unified. Moreover, our formulas reveal some interesting facts which have not been spotted previously. Taking formula (8), for example, in almost all papers [9, 20, 24–28], it is the case that (13)δA¯≤n+1-IDA,B.This is very reasonable, since the cryptanalysts cannot propagate A upwards too much; otherwise δ(A¯) would contain almost all strings in F2n, which is obviously an unpleasant situation. Therefore, in most cases, the data complexity can be computed from the distinguisher (A,B) directly and has nothing to do with how A/B propagate upwards/downwards. This formula offers an extremely simple procedure for computing the data complexity of impossible differential attack. Let us show some examples.Example 11 (multiple impossible differential attack on SIMON32/64 and SIMON96/96).
In [18], Boura et al. used multiple impossible differentials to attack SIMON32/64. There are 8 independent input patterns by one original 11-round impossible differential (14)00000000000000000000000000000001↛00000000100000000000000000000000;we can see the detail in Table 1. It is obvious that ID(A,B)=log2(4×2)=3. Thus the data complexity is approximately 2n+1-ID(A,B)·2α=232+1-3·21=231 to reduce 2·log2e≈2.88-bit information of the key candidates space from formula (12). Similarly, using 8 16-round impossible differentials, to reduce the target key space by approximately log2e bit, the data complexity is approximately 296+1-3=294. These data complexities are in accordance with the results proposed in [18].Table 1
Impossible differential characteristics for SIMON32/64.
Number ID (1) 0000000000000000 0000000000000001↛ 0000000010000000 0000000000000000 (2) 0000000000000000 0000000010000000↛ 0000000010000000 0000000000000000 (3) 0000000000000000 0000000100000000↛ 0000000010000000 0000000000000000 (4) 1000000000000000 0000000000000000↛ 0000000010000000 0000000000000000 (5) 0000000000000000 0000000000000001↛ 0000001000000000 0000000000000000 (6) 0000000000000000 0000000010000000↛ 0000001000000000 0000000000000000 (7) 0000000000000000 0000000100000000↛ 0000001000000000 0000000000000000 (8) 1000000000000000 0000000000000000↛ 0000001000000000 0000000000000000Example 12 (multiple impossible differential attack on CLEFIA-128).
In [24], Tsunoo et al. mounted an impossible differential attack on CLEFIA [23] by using multiple impossible differentials discovered in [29]. There are the following two 9-round impossible differentials in CLEFIA (15)032,032,032,αin↛032,032,032,αout,032,αin,032,032↛032,αout,032,032.Only considering that there is one active byte in αin and αout presented in Table 2, we will show how to use our formula to determine the data complexity of an impossible differential attack based on these differentials.Table 2
Differential values forαin and αout.
0 αin α o u t (1) [ 0 8 , 0 8 , 0 8 , x 8 ] [08,08,y8,08],[08,y8,08,08],[y8,08,08,08] (2) [ 0 8 , 0 8 , x 8 , 0 8 ] [08,08,08,y8],[08,y8,08,08],[y8,08,08,08] (3) [ 0 8 , x 8 , 0 8 , 0 8 ] [08,08,08,y8],[08,08,y8,08],[y8,08,08,08] (4) [ x 8 , 0 8 , 0 8 , 0 8 ] [08,08,08,y8],[08,y8,08,08],[08,08,y8,08]From Table3, we can see that (16)IDA,B=log228×28×24≈20.58.Therefore, to reduce the target key space by approximately log2e bit, the minimal number of data complexity is approximately 2128+1-20.58=2108.42, which matches the results presented in [18, 24] perfectly.Table 3
Impossible differential characteristics for CLEFIA-128.
Number ID (1) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] ] (2) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , y 8 , 0 8 , 0 8 ] ] (3) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] ]  (4) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] ] (5) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , y 8 , 0 8 , 0 8 ] ] (6) [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] ]  (7) [ 0 32 , 0 32 , 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] ] (8) [ 0 32 , 0 32 , 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] ] (9) [ 0 32 , 0 32 , 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] ]  (10) [ 0 32 , 0 32 , 0 32 , [ x 8 , 0 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] ] (11) [ 0 32 , 0 32 , 0 32 , [ x 8 , 0 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] ] (12) [ 0 32 , 0 32 , 0 32 , [ x 8 , 0 8 , 0 8 , 0 8 ] ] ↛ [ 0 32 , 0 32 , 0 32 , [ 0 8 , y 8 , 0 8 , 0 8 ] ]  (13) [ 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] , 0 32 , 0 32 ] (14) [ 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , y 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] (15) [ 0 32 , [ 0 8 , 0 8 , 0 8 , x 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ]  (16) [ 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] , 0 32 , 0 32 ] (17) [ 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , y 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] (18) [ 0 32 , [ 0 8 , 0 8 , x 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ]  (19) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] , 0 32 , 0 32 ] (20) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] , 0 32 , 0 32 ] (21) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ]  (22) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , 0 8 , y 8 ] , 0 32 , 0 32 ] (23) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ 0 8 , 0 8 , y 8 , 0 8 ] , 0 32 , 0 32 ] (24) [ 0 32 , [ 0 8 , x 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ] ↛ [ 0 32 , [ y 8 , 0 8 , 0 8 , 0 8 ] , 0 32 , 0 32 ]


## 5. On the Time Complexity of Impossible Differential Attack

The time complexity of the impossible differential attack is estimated by Boura et al. with the formula(17)Tcomp=CNCE+N+2kin∪koutN2cin+coutCE′CE+2KPCE,where CN is the amount of needed data for obtaining the N pairs, 2kin∪kout is the number of candidate keys, CE′ is the ratio of the partial encryption to the full encryption, 2KP is the key candidates needed to exhaustive search, and CE is the full encryption. The first term is the cost of generating N(A,B)-effective pairs. The second term corresponds to the cost of the key-sieving procedure. Finally, the third term is the cost of exhaustive search for the key candidates which are not removed by the key-sieving procedure. Among these three terms, the second one is the most obscure part. Next, we focus attention on the second part. So before we go further, we would like to give some comments on it. Note that the comments are never meant to be precise, but try to get some intuitive understanding.LetQ0,…,QN-1 be N(A,B)-effective plaintext pairs. We create 2kin∪koutN tuples of the form Wi,j=(Qi,j), where 0≤i≤N-1 and 0≤j≤2kin∪kout-1. We arrange these tuples into N rows as follows: (18)Wi,0,Wi,1,…,Wi,2kin∪kout-1.No matter how we perform the impossible differential attack, the partial encryption and decryption of the plaintext pairs Qi with guessed key kin∪kout=j will be performed inevitably for those (i,j) such that j is rejected by Qi. Let (19)W∗=Wi,j:jis  rejected  byQi,0≤i≤N-1,0≤j≤2kin∪kout-1.Then W∗ is approximately 2kin∪koutN/2cin+cout. Therefore, the time complexity of the key-sieving process is at least 2kin∪koutN/2cin+coutCE′CE, which is optimal. That is, the second term of Boura et al.’s formula is in some sense a minimum estimation of the complexity of the key-sieving process.In [19], Derbez presented some concrete examples where there is no attack whose complexity is as low as Boura et al.’s estimation. Consequently, we want to ask the question: under which condition is Boura et al.’s estimation valid? The following shows that when the key bits are independent Boura et al.’s formula is valid and achievable. For the other case when the key bits are not independent we give a simple discussion.


### 5.1. When the Key Bits Are Independent

Assumption 13.
In order to give a technique to achieve the optimal time complexity, there are some assumptions in the target cipher. We focus our attention on these ciphers which consist of subkey XOR, nonlinear, and linear operations. For nonlinear layer, it should be composed by S-boxes or bitwise AND. In other words, the difference values of nonlinear operation should be shown in a table with less storage and we can ignore the time complexity of creating table. Therefore, most block ciphers satisfy this assumption.Let us assume thatΔi+1 is the (i+1)th round input set and Δi is the set propagated by Δi+1 with probability 1. During the key filtering phase of impossible differential attack, ki includes two parts: one involved the value of difference Δi and the other part involved no difference but need to get these values. Therefore, for target ciphers satisfying our assumption(20)ci=Δi-Δi+1,ki=kiΔ≠0+kiΔ=0=Δi+kiΔ=0.An example is depicted in Figure 5, where k0=k0[0,1,2]+k0[3]=kiΔ≠0+kiΔ=0.Figure 5
Example: grey color stands for nibbles with nonzero difference.In the following, we presentthe early abort technique in which the time complexity will achieve the optimal result if the involved key bits are independent. Assuming that there are l outer rounds, let ki denote the involved key bits and let ci denote the number of bit-conditions. Given N(A,B)-effective plaintext pairs Q0,…,QN-1, for each Q∈{Q0,…,QN-1}, completes the following steps:(i)
Step 0: deriveW(0)={(Q,kσ(i)′):thecσ(0)bitsofconditionsareverified} by table look-up. W0≈2kσ(0)-cσ(0). In detail, at first guess the value of Δσ(0) and decrypt the corresponding plaintext pairs partially to calculate the output difference after nonlinear operation, then get the value of kΔ≠0 by table look-up technique and finally guess the value of kiΔ=0 to get W(0).(ii)
Step 1: deriveW(1)={(Q,kσ(0)′∪kσ(1)′):thecσ(1)bitsofconditionsareverified} by table look-up. W1≈2kσ(0)∪kσ(1)′-cσ(0)-cσ(1).(iii)
⋯(iv)
Stepl-1: derive W(l-1)={(Q,⋃i=0l-1kσ(i)′):thecσ(l-1)bitsofconditionsareverified} by table look-up. Wl-1≈2⋃i=0l-1kσ(i)′-∑i=0l-1cσ(i).For Step 0, the time complexity is(21)N2Δi+1×CE0×2kΔ=0CE=N2kσ0-cσ0CE0CE.Therefore, the complexity of the whole procedure with a given permutation σ is(22)N∑j=0l-12⋃i=0jkσi′-∑i=0jcσiCEjCE≈N2dσCE′CE,where dσ=max0≤j≤l-1{⋃i=0jkσ(i)′-∑i=0jcσ(i)} and CE′=∑j=0l-1CEj. Obviously, CE′ is the ratio of the cost of partial encryption to the full encryption.Combining (20) withthe early abort technique, ∀i, kσ(i)-cσ(i)≥0. Hence dσ=max0≤j≤l-1{⋃i=0jkσ(i)′-∑i=0jcσ(i)}=∑i=0l-1(kσ(i)-cσ(i))=∑i=0l-1(ki-ci)=kin∪kout-cin-cout.Fact 14.
If the involved key bits are independent, thendσ=kin∪kout-cin-cout.From Fact14, we know that there is a permutation σ such that the time complexity of the key-sieving process is approximately(23)2kin∪koutN2cin+coutCE′CEwhich is the same as Boura’s formula. Without considering the time complexity of the key schedule, if the target ciphers are under our assumption and the involved key bits are independent, we can conclude that Boura et al.’s formula is correct.Example 15 (impossible differential attack on a toy cipher).
Let us consider the toy block cipherE used by Derbez in [19] as an example which is defined as follows: (24)E=E′∘MC∘SR∘SB∘AK,where E′ is a 128-bit block cipher and where AK, SB, SR, and MC, respectively, are the AddRoundKey, SubBytes, ShriftRows, and MixColumns operations from the AES: (i)
AddRoundKey (AK): XORing the state with round key;(ii)
SubBytes (SB): nonlinearity transformation using 8-bit to 8-bit invertible S-Box;(iii)
ShiftRows (SR): permutation with cyclic shift of each row to the left;(iv)
MixColumns (MC): linearity transformation to mix all the column by4×4 invertible matrix.Assume that there is an impossible differential(A,B) over E′ where A has one active byte. As shown in Figure 6, appending one round on the top of the distinguisher we give an impossible differential cryptanalysis. The bit-condition cin is 24 and there are 32 key bits. In the case that the key bits are independent, we give the time complexity of the attack as follows:(i)
Step 1: guessA; there are 28 values. For each value of A, decrypt pairs to calculate the difference value after SB operation. Thus the input difference and output difference of S-Box are both known in nibbles 0, 5, 10, and 15 for each pair.(ii)
Step 2: by table look-up four times, get the values ofk0, k5, k10, and k15 in turn.Figure 6
Impossible differential attack against the toy cipherE.Step 1 and Step 2 are the detailed explanation aboutStep 0. For N(A,B)-effective pairs, the time complexity in above steps is (25)N×28×1+1+1+1×116×1rCE=N×28×CE′CEwhich is in conformity with formula (23).


### 5.2. When the Key Bits Are Not Independent

The previous section shows in some sense that the estimation of Boura is not only achievable but also optimal when the key bits involved are independent.In the following, we give a formula to estimate the complexity of the key-sieving process which is always valid regardless whether the involved key bits are independent or not(26)2β×2kin∪koutN2cin+coutCE′CE.We show how to determine β by example.Example 16 (multiple impossible differential attack on CLEFIA-128).
From Figure4 showing the attack on CLEFIA-128 by using multiple impossible differentials, there are 4 outer rounds. For kin there are 32 bits of RK1, 32 bits of RK0, and 8 bits of RK2⊕WK0 to be guessed. Similarly, for kout we also need to guess 8 bits of RK23⊕WK2, 32 bits of RK24, and 32 bits of RK25. Therefore, kin=72 and kout=72. Considering the relationship between the subkeys, the subkeys RK1 and RK24 share 22 bits in common. Thus the number of information key bits is kin∪kout=72+72-22=122 and for each round the bit-conditions are c1=32, c2=8, c12=8, and c13=32. Because the key bits are not independent, we should calculate 2dσ by steps, which could not calculate by the formula 2kin∪kout-cin-cout.The process to calculate2dσ is as follows:(i)
Step 0: guess the subkeys of the first round,kσ(0)=k1=64 and cσ(0)=c1=32; thus W0≈2kσ(0)-cσ(0)=264-32=232.(ii)
Step 1: guess the subkeys of the second round,kσ(1)=k2=8 and cσ(1)=c2=8; thus W1≈2kσ(0)∪kσ(1)′-cσ(0)-cσ(1)=264+8-32-8=232.(iii)
Step 2: guess the subkeys of the 13th round,kσ(2)=k13=64-22=42 and cσ(2)=c13=32; thus W2≈2⋃i=02kσ(i)′-∑i=02cσ(i)=264+8+42-32-8-32=242.(iv)
Step 3: guess the subkeys of the 12th round,kσ(3)=k12=8 and cσ(3)=c12=8; thus W3≈2⋃i=03kσ(i)′-∑i=03cσ(i)=264+8+42+8-32-8-32-8=242.The above steps show2dσ=max0≤j≤3Wj=242 which is equal to 2kin∪kout-cin-cout; thus 2β=1. The key point is that in Step 2 kσ(2)=k13=42≥c13=32, it does not generate greater value than 2kin∪kout-cin-cout, and the time complexity of the key-sieving process is 1×2kin∪kout(N/2cin+cout)CE′CE. To trade-off the data complexity and the time complexity, choosing α=2.6, the time complexity is (27)CNCE+N+2kin∪koutN2cin+coutCE′CE+2KPCE≈2122.07CEwith CN=2108.42×22.6=2111.06, N=280×22.6=282.6, CE′=18/104, and P=2-2αlog2e≈2-8.75, which is as a result presented in [18].


## 5.1. When the Key Bits Are Independent

Assumption 13.
In order to give a technique to achieve the optimal time complexity, there are some assumptions in the target cipher. We focus our attention on these ciphers which consist of subkey XOR, nonlinear, and linear operations. For nonlinear layer, it should be composed by S-boxes or bitwise AND. In other words, the difference values of nonlinear operation should be shown in a table with less storage and we can ignore the time complexity of creating table. Therefore, most block ciphers satisfy this assumption.Let us assume thatΔi+1 is the (i+1)th round input set and Δi is the set propagated by Δi+1 with probability 1. During the key filtering phase of impossible differential attack, ki includes two parts: one involved the value of difference Δi and the other part involved no difference but need to get these values. Therefore, for target ciphers satisfying our assumption(20)ci=Δi-Δi+1,ki=kiΔ≠0+kiΔ=0=Δi+kiΔ=0.An example is depicted in Figure 5, where k0=k0[0,1,2]+k0[3]=kiΔ≠0+kiΔ=0.Figure 5
Example: grey color stands for nibbles with nonzero difference.In the following, we presentthe early abort technique in which the time complexity will achieve the optimal result if the involved key bits are independent. Assuming that there are l outer rounds, let ki denote the involved key bits and let ci denote the number of bit-conditions. Given N(A,B)-effective plaintext pairs Q0,…,QN-1, for each Q∈{Q0,…,QN-1}, completes the following steps:(i)
Step 0: deriveW(0)={(Q,kσ(i)′):thecσ(0)bitsofconditionsareverified} by table look-up. W0≈2kσ(0)-cσ(0). In detail, at first guess the value of Δσ(0) and decrypt the corresponding plaintext pairs partially to calculate the output difference after nonlinear operation, then get the value of kΔ≠0 by table look-up technique and finally guess the value of kiΔ=0 to get W(0).(ii)
Step 1: deriveW(1)={(Q,kσ(0)′∪kσ(1)′):thecσ(1)bitsofconditionsareverified} by table look-up. W1≈2kσ(0)∪kσ(1)′-cσ(0)-cσ(1).(iii)
⋯(iv)
Stepl-1: derive W(l-1)={(Q,⋃i=0l-1kσ(i)′):thecσ(l-1)bitsofconditionsareverified} by table look-up. Wl-1≈2⋃i=0l-1kσ(i)′-∑i=0l-1cσ(i).For Step 0, the time complexity is(21)N2Δi+1×CE0×2kΔ=0CE=N2kσ0-cσ0CE0CE.Therefore, the complexity of the whole procedure with a given permutation σ is(22)N∑j=0l-12⋃i=0jkσi′-∑i=0jcσiCEjCE≈N2dσCE′CE,where dσ=max0≤j≤l-1{⋃i=0jkσ(i)′-∑i=0jcσ(i)} and CE′=∑j=0l-1CEj. Obviously, CE′ is the ratio of the cost of partial encryption to the full encryption.Combining (20) withthe early abort technique, ∀i, kσ(i)-cσ(i)≥0. Hence dσ=max0≤j≤l-1{⋃i=0jkσ(i)′-∑i=0jcσ(i)}=∑i=0l-1(kσ(i)-cσ(i))=∑i=0l-1(ki-ci)=kin∪kout-cin-cout.Fact 14.
If the involved key bits are independent, thendσ=kin∪kout-cin-cout.From Fact14, we know that there is a permutation σ such that the time complexity of the key-sieving process is approximately(23)2kin∪koutN2cin+coutCE′CEwhich is the same as Boura’s formula. Without considering the time complexity of the key schedule, if the target ciphers are under our assumption and the involved key bits are independent, we can conclude that Boura et al.’s formula is correct.Example 15 (impossible differential attack on a toy cipher).
Let us consider the toy block cipherE used by Derbez in [19] as an example which is defined as follows: (24)E=E′∘MC∘SR∘SB∘AK,where E′ is a 128-bit block cipher and where AK, SB, SR, and MC, respectively, are the AddRoundKey, SubBytes, ShriftRows, and MixColumns operations from the AES: (i)
AddRoundKey (AK): XORing the state with round key;(ii)
SubBytes (SB): nonlinearity transformation using 8-bit to 8-bit invertible S-Box;(iii)
ShiftRows (SR): permutation with cyclic shift of each row to the left;(iv)
MixColumns (MC): linearity transformation to mix all the column by4×4 invertible matrix.Assume that there is an impossible differential(A,B) over E′ where A has one active byte. As shown in Figure 6, appending one round on the top of the distinguisher we give an impossible differential cryptanalysis. The bit-condition cin is 24 and there are 32 key bits. In the case that the key bits are independent, we give the time complexity of the attack as follows:(i)
Step 1: guessA; there are 28 values. For each value of A, decrypt pairs to calculate the difference value after SB operation. Thus the input difference and output difference of S-Box are both known in nibbles 0, 5, 10, and 15 for each pair.(ii)
Step 2: by table look-up four times, get the values ofk0, k5, k10, and k15 in turn.Figure 6
Impossible differential attack against the toy cipherE.Step 1 and Step 2 are the detailed explanation aboutStep 0. For N(A,B)-effective pairs, the time complexity in above steps is (25)N×28×1+1+1+1×116×1rCE=N×28×CE′CEwhich is in conformity with formula (23).


## 5.2. When the Key Bits Are Not Independent

The previous section shows in some sense that the estimation of Boura is not only achievable but also optimal when the key bits involved are independent.In the following, we give a formula to estimate the complexity of the key-sieving process which is always valid regardless whether the involved key bits are independent or not(26)2β×2kin∪koutN2cin+coutCE′CE.We show how to determine β by example.Example 16 (multiple impossible differential attack on CLEFIA-128).
From Figure4 showing the attack on CLEFIA-128 by using multiple impossible differentials, there are 4 outer rounds. For kin there are 32 bits of RK1, 32 bits of RK0, and 8 bits of RK2⊕WK0 to be guessed. Similarly, for kout we also need to guess 8 bits of RK23⊕WK2, 32 bits of RK24, and 32 bits of RK25. Therefore, kin=72 and kout=72. Considering the relationship between the subkeys, the subkeys RK1 and RK24 share 22 bits in common. Thus the number of information key bits is kin∪kout=72+72-22=122 and for each round the bit-conditions are c1=32, c2=8, c12=8, and c13=32. Because the key bits are not independent, we should calculate 2dσ by steps, which could not calculate by the formula 2kin∪kout-cin-cout.The process to calculate2dσ is as follows:(i)
Step 0: guess the subkeys of the first round,kσ(0)=k1=64 and cσ(0)=c1=32; thus W0≈2kσ(0)-cσ(0)=264-32=232.(ii)
Step 1: guess the subkeys of the second round,kσ(1)=k2=8 and cσ(1)=c2=8; thus W1≈2kσ(0)∪kσ(1)′-cσ(0)-cσ(1)=264+8-32-8=232.(iii)
Step 2: guess the subkeys of the 13th round,kσ(2)=k13=64-22=42 and cσ(2)=c13=32; thus W2≈2⋃i=02kσ(i)′-∑i=02cσ(i)=264+8+42-32-8-32=242.(iv)
Step 3: guess the subkeys of the 12th round,kσ(3)=k12=8 and cσ(3)=c12=8; thus W3≈2⋃i=03kσ(i)′-∑i=03cσ(i)=264+8+42+8-32-8-32-8=242.The above steps show2dσ=max0≤j≤3Wj=242 which is equal to 2kin∪kout-cin-cout; thus 2β=1. The key point is that in Step 2 kσ(2)=k13=42≥c13=32, it does not generate greater value than 2kin∪kout-cin-cout, and the time complexity of the key-sieving process is 1×2kin∪kout(N/2cin+cout)CE′CE. To trade-off the data complexity and the time complexity, choosing α=2.6, the time complexity is (27)CNCE+N+2kin∪koutN2cin+coutCE′CE+2KPCE≈2122.07CEwith CN=2108.42×22.6=2111.06, N=280×22.6=282.6, CE′=18/104, and P=2-2αlog2e≈2-8.75, which is as a result presented in [18].


## 6. Conclusion

Thanks to the new notations, we give a unified data complexity formula for both the ordinary impossible differential attacks and attacks based on multiple impossible differentials. This formula not only is more convenient to use, but also reveals an interesting fact that the data complexity of an impossible differential attack can be derived by the mere knowledge of the underlying impossible differential distinguisher in most cases. Moreover, we show under which condition Boura et al.’s formula is valid and give a simple time complexity estimation for impossible differential attack which is always achievable. We believe that these results make the evaluation of the impossible differential attack more straightforward and reliable.



---

*Source: 7393401-2018-04-17.xml*