# The 7-Round Subspace Trail-Based Impossible Differential Distinguisher of Midori-64

Authors: Wenhao Liu; Yang Yang
Journal: Security and Communication Networks
 (2021)

---

## Abstract

This paper analyzes the subspace trail of Midori-64 and uses the propagation law and mutual relationship of the subspaces of Midori-64 to provide a 6-round Midori-64 subspace trail-based impossible differential key recovery attack. The data complexity of the attack is254.6 chosen plaintexts, and the computational complexity is 258.2 lookup operations. Its overall complexity is less than that of the known 6-round truncated impossible differential distinguisher. This distinguisher is also applicable to Midori-128 with a secret S-box. Additionally, utilizing the properties of subspaces, we prove that a subspace trail-based impossible differential distinguisher of Midori-64 contains at most 7 rounds. This is 1 more than the upper bound of Midori-64’s truncated impossible differential distinguisher which is 6. According to the Hamming weights of the starting and ending subspaces, we classify all 7-round Midori-64 subspace trail-based impossible differential distinguishers into two types and they need 259.6 and 251.4 chosen plaintexts, respectively.


---

## Body

## 1. Introduction

With the development of the Internet of Things, the security issues of the Internet of Things are becoming serious. Since most of the encryption devices on the Internet of Things have small storage space and weak computing power, the traditional cryptographic algorithms are not suitable for protecting information security on the Internet of Things. In this case, a large number of lightweight cryptographic algorithms have emerged. Typical algorithms are PRESENT [1], MIBS [2], GOST [3], KLEIN [4], LED [5], Piccolo [6], LBlock [7], PRINCE [8], etc. Most of these lightweight cryptographic algorithms focus on hardware implementation circuits. However, Banik et al. believe that the factor restricting the application of lightweight algorithms is the power consumption of the algorithm, and low-power cryptographic algorithms can be more widely used in a variety of devices. They proposed to focus on low-power Midori algorithm [9]. Midori is considered to be one of the first lightweight ciphers that optimizes energy consumption on bit-level circuits. Since Midori algorithm is limited to a lightweight environment, it is usually not analyzed for its security under the conditions of known keys, related keys, and chosen keys. We generally examine the security of the algorithm under the condition of a single key.At present, some security analysis results for the Midori algorithm are available. In 2015, Guo et al. analyzed the weak key set of the Midori-64 algorithm and used an invariant subspace attack [10] to provide full-round Midori-64 analysis results [11]. In 2015, Todo generalized the integral property to divisibility [12], which can be used to obtain Midori-64’s distinguisher. In 2016, Ling Sun et al. gave 6-round and 7-round Midori-64 integral distinguishers using the mixed-integer linear programming (MILP) technique and bit divisibility [13]. In 2017, Lin et al. used the meet-in-the-middle method [14] to construct 5-round and 6-round distinguishers [14] and provided security analysis results for the Midori-64 algorithm with 10 to 12 rounds [15], among which the 12-round Midori-64 key recovery attack required 255 chosen plaintexts, 2106 of storage, and 2125.5 calculations. In 2017, Chen et al. constructed the first 6-round Midori-64 truncated impossible differential distinguisher [16] and gave the first impossible differential attack for the 10-round Midori-64 algorithm without an entry whitening key. In 2018, Tim Beyne used a feature matrix to improve the nonlinear invariant Midori attack using 296 weak keys, 350 chosen plaintexts, and 256 encryptions. This method can recover all the keys of Midori in 10 rounds [17]. In 2019, Li et al. built on Chen’s work by demonstrating the existence of up to 6 rounds of truncated impossible differential distinguishers for Midori-64 [18]. Table 1 provides a comparison of our results with some previous results.Table 1
Comparison of our main results for Midori-64 with previous results.
log2(#Texts)Referr=6r=760—[12]4561[13]56.6/60.5—[18]54.6—Section4.3—59.6/51.4Section6.1/6.2This article first proves that, under the condition of a single key, Midori-64 has at most a 7-round space trail-based impossible differential distinguisher, which is 1 round more than the upper bound of the number of rounds contained in the impossible differential distinguisher for Midori-64. The 6-round Midori-64 subspace trail distinguisher has a greater distinguishing advantage than all known 6-round truncated impossible differential distinguishers. Thus, we classify all 7-round space trail-based impossible differential distinguishers of Midori-64.Section2 mainly introduces the Midori series of algorithms and the definition of subspace trails. Section 3 discusses the Midori-64 text subspace, the propagation law of the subspace, and the relationship between them. Section 4 uses the properties of the subspace to derive a special 6-round Midori-64 distinguisher. Section 5 proves that Midori-64 has at most a 7-round space trail-based impossible differential distinguisher. In Section 6, we use the Hamming weights of the starting and ending subspaces to classify all 7-round space trail-based impossible differential distinguishers of Midori-64.


## 2. Preliminary Preparation

### 2.1. Midori Series Cryptographic Algorithms

The Midori algorithm is divided into Midori-64 and Midori-128. The key size is 128 bits, and the block size is 64 bits and 128 bits, respectively. The corresponding iteration rounds are 16 rounds and 20 rounds. The text status is represented as 16 nibbles or bytes, as shown in the following:(1)s0s4s8s12s1s5s9s13s2s6s10s14s3s7s11s15.The Midori algorithm adopts the SPN structure, and its round function is composed of four transformations, namely, the nonlinear transformationSubCell, the shift transformation ShuffleCell, the column mixing transformation MixColumn, and the key XOR KeyAdd. The specific introduction of these four transformations and the key expansion algorithm is as follows.SubCell: in the Midori algorithm, there are two different involutive 4 bit S-boxes Sb0 and Sb1, namely, Sb0,Sb1:0,14⟶0,14. Midori-64 only uses Sb0, see Figure 1.Figure 1
The S-box of midori.ShuffleCell: rearrange the order of 16 blocks. The transformation and inverse transformation are shown in Figure 2.Figure 2
The shift transformation of midori.That is,SC0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15=0,10,5,15,14,4,11,1,9,3,12,6,7,13,2,8.MixColumn: use the involutive binary matrix M on F2416 to perform the following operations on each column in the state, namely, M·si,si+1,si+2,si+3′⟶si,si+1,si+2,si+3′, where i=0,4,8,12. M and its inverse matrix M−1 are as follows:(2)M=0111101111011110,M−1=0111101111011110.KeyAdd: XOR is the key byte to the corresponding position of the state byte.Key expansion algorithm: Midori algorithm uses a 128 bit master key, and its key expansion algorithm is relatively simple. Among them, the Midori-64 algorithm divides the 128 bit master key into two partsK=k0‖k1. The whitening keys of entry and exit are WK=k0⊕k1. The round key kei=ki+1mod2⊕ai, 1≤i≤15, where ai is the round constant. And, the whitening keys of entry and exit of the Midori-128 algorithm are all WK=K, the round key kei=K⊕bi, 1≤i≤19, where bi is the round constant. And, when 1≤i≤15, it satisfies ai=bi.Before the first round of encryption, the message needs to be XORed with the whitening key WK. To ensure the structural similarity of the encryption and decryption algorithms of the Midori algorithm, the cypher omits the shift transformation and column mixing transformation in the last round.


### 2.2. The Properties of Midori

Property 1 (see [18]).
The nibbles in the same column must be in the same row after the two shift transformations of the Midori algorithm:Property 2.
Suppose that the input matrix has only three identical nonzero bytes in theith column as x, and the remaining 13 bytes are all 0. After the column mixing operation, the original 0 byte in the ith column of the output matrix is x, and the remaining 15 bytes are all 0. Suppose that the input matrix has only two identical nonzero bytes in the ith column as x, and the remaining 14 bytes are all 0. After column mixing, the output matrix and the input matrix are the same.Proof.
When the input matrix has only three nonzero bytes in theith column, which are x and the remaining bytes are 0, let us set the ith column of the input matrix as xxx0. Then, there are Mxxx0=0111101111011110=000x. When the input matrix has two identical nonzero bytes in the ith column as x and the remaining bytes are 0, let us set the ith column of the input matrix as 00xx. Then, there are M00xx=00xx.


### 2.3. The Definition of Subspace Trail

In 2011, G. Leander et al. proposed the concept of an invariant subspace at the U.S. Conference and used it in the PRINT cipher [19] to conduct a full-round attack. The central idea is to construct a text subspace. If the subspace can still maintain the invariance of the subspace structure after one or more rounds of encryption, then this nonrandom phenomenon can be used to construct a distinguisher for the algorithm. On this basis, Grassi et al. proposed the concept of subspace trails [20]. A subspace trail does not emphasize the invariance of the associated subspace structure under the round function but shows the propagation law of the subspace structure under the round function and then uses the subspace trail with a certain law to establish a distinguisher. Since its proposal, subspace trail analysis has been mainly used in attacks on substitution-permutation network (SPN)-structured cryptographic algorithms such as the Advanced Security Standard (AES) [21]; this method is used to construct distinguishers or perform key recovery without possessing the information related to the S-box and the key.Definition 1 (see [20]).
FK=F⊕K is the round function of a block cipher, and V1,V2,…,Vr+1 are r + 1 subspaces with increasing dimensionality that are included in F2n. If, for any i=1,2,……,r+1 and for any ai belonging to Vi⊥, there exists ai+1 belonging to Vi+1⊥ such that(3)FKVi⊕ai⊆Vi+1⊕ai+1,then V1,V2,…,Vr+1 is the subspace trail of FK with length r.
Note thatai+1 depends on ai and the secret key. To simplify the notation, ai+1ai,k is replaced with ai+1. After defining the subspace trail, the following question is raised. If the plaintexts obey a certain subspace structure (for example, their sum is also in this fixed subspace), what is the probability that the ciphertexts or the sum of them fall in the particular subspace? If there are two texts, this method is similar to (truncated) differential cryptanalysis. If there are more than two texts, it is similar to integral cryptanalysis. In this case, small subspace trails can be connected together. According to the intersection property of the trail endpoints, the predictable subspace properties of the longer trail are obtained. However, in general, these are not necessarily constant-dimension trails. The subspace trail analysis and the distinguisher based on it are described below.


## 2.1. Midori Series Cryptographic Algorithms

The Midori algorithm is divided into Midori-64 and Midori-128. The key size is 128 bits, and the block size is 64 bits and 128 bits, respectively. The corresponding iteration rounds are 16 rounds and 20 rounds. The text status is represented as 16 nibbles or bytes, as shown in the following:(1)s0s4s8s12s1s5s9s13s2s6s10s14s3s7s11s15.The Midori algorithm adopts the SPN structure, and its round function is composed of four transformations, namely, the nonlinear transformationSubCell, the shift transformation ShuffleCell, the column mixing transformation MixColumn, and the key XOR KeyAdd. The specific introduction of these four transformations and the key expansion algorithm is as follows.SubCell: in the Midori algorithm, there are two different involutive 4 bit S-boxes Sb0 and Sb1, namely, Sb0,Sb1:0,14⟶0,14. Midori-64 only uses Sb0, see Figure 1.Figure 1
The S-box of midori.ShuffleCell: rearrange the order of 16 blocks. The transformation and inverse transformation are shown in Figure 2.Figure 2
The shift transformation of midori.That is,SC0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15=0,10,5,15,14,4,11,1,9,3,12,6,7,13,2,8.MixColumn: use the involutive binary matrix M on F2416 to perform the following operations on each column in the state, namely, M·si,si+1,si+2,si+3′⟶si,si+1,si+2,si+3′, where i=0,4,8,12. M and its inverse matrix M−1 are as follows:(2)M=0111101111011110,M−1=0111101111011110.KeyAdd: XOR is the key byte to the corresponding position of the state byte.Key expansion algorithm: Midori algorithm uses a 128 bit master key, and its key expansion algorithm is relatively simple. Among them, the Midori-64 algorithm divides the 128 bit master key into two partsK=k0‖k1. The whitening keys of entry and exit are WK=k0⊕k1. The round key kei=ki+1mod2⊕ai, 1≤i≤15, where ai is the round constant. And, the whitening keys of entry and exit of the Midori-128 algorithm are all WK=K, the round key kei=K⊕bi, 1≤i≤19, where bi is the round constant. And, when 1≤i≤15, it satisfies ai=bi.Before the first round of encryption, the message needs to be XORed with the whitening key WK. To ensure the structural similarity of the encryption and decryption algorithms of the Midori algorithm, the cypher omits the shift transformation and column mixing transformation in the last round.


## 2.2. The Properties of Midori

Property 1 (see [18]).
The nibbles in the same column must be in the same row after the two shift transformations of the Midori algorithm:Property 2.
Suppose that the input matrix has only three identical nonzero bytes in theith column as x, and the remaining 13 bytes are all 0. After the column mixing operation, the original 0 byte in the ith column of the output matrix is x, and the remaining 15 bytes are all 0. Suppose that the input matrix has only two identical nonzero bytes in the ith column as x, and the remaining 14 bytes are all 0. After column mixing, the output matrix and the input matrix are the same.Proof.
When the input matrix has only three nonzero bytes in theith column, which are x and the remaining bytes are 0, let us set the ith column of the input matrix as xxx0. Then, there are Mxxx0=0111101111011110=000x. When the input matrix has two identical nonzero bytes in the ith column as x and the remaining bytes are 0, let us set the ith column of the input matrix as 00xx. Then, there are M00xx=00xx.


## 2.3. The Definition of Subspace Trail

In 2011, G. Leander et al. proposed the concept of an invariant subspace at the U.S. Conference and used it in the PRINT cipher [19] to conduct a full-round attack. The central idea is to construct a text subspace. If the subspace can still maintain the invariance of the subspace structure after one or more rounds of encryption, then this nonrandom phenomenon can be used to construct a distinguisher for the algorithm. On this basis, Grassi et al. proposed the concept of subspace trails [20]. A subspace trail does not emphasize the invariance of the associated subspace structure under the round function but shows the propagation law of the subspace structure under the round function and then uses the subspace trail with a certain law to establish a distinguisher. Since its proposal, subspace trail analysis has been mainly used in attacks on substitution-permutation network (SPN)-structured cryptographic algorithms such as the Advanced Security Standard (AES) [21]; this method is used to construct distinguishers or perform key recovery without possessing the information related to the S-box and the key.Definition 1 (see [20]).
FK=F⊕K is the round function of a block cipher, and V1,V2,…,Vr+1 are r + 1 subspaces with increasing dimensionality that are included in F2n. If, for any i=1,2,……,r+1 and for any ai belonging to Vi⊥, there exists ai+1 belonging to Vi+1⊥ such that(3)FKVi⊕ai⊆Vi+1⊕ai+1,then V1,V2,…,Vr+1 is the subspace trail of FK with length r.
Note thatai+1 depends on ai and the secret key. To simplify the notation, ai+1ai,k is replaced with ai+1. After defining the subspace trail, the following question is raised. If the plaintexts obey a certain subspace structure (for example, their sum is also in this fixed subspace), what is the probability that the ciphertexts or the sum of them fall in the particular subspace? If there are two texts, this method is similar to (truncated) differential cryptanalysis. If there are more than two texts, it is similar to integral cryptanalysis. In this case, small subspace trails can be connected together. According to the intersection property of the trail endpoints, the predictable subspace properties of the longer trail are obtained. However, in general, these are not necessarily constant-dimension trails. The subspace trail analysis and the distinguisher based on it are described below.


## 3. The Subspace through One Round of Midori-64

### 3.1. The Subspace of Midori-64

For a vector spaceV and a function F on F244×4, let FV=Fv|v∈V. For a subset I⊆1,2,…,n and a subset of vector spaces G1,G2,…,Gn, we define GI=⊕i∈IGi.All the subspaces in this paper are defined on the spaceF244×4 over the field F24. Moreover, we denote E=e0,……,e15 as the unit vector space of F244×4. Otherwise, as specified below, the value range of a positive integer i in the subspace definition is 0≤i≤3. In the following, we define some families of subspaces that are essential to Midori-64: diagonal spaces DI, column spaces CI, mixed spaces MI, and so on.The column space:Ci=e4i,e4i+1,e4i+2,e4i+3. The diagonal space: Di=SC−1Ci. The CS space: CSi=SCCi. The mixed space: Mi=MCCSi. The inverse row space: R¯i=SCMi. The window space: Wi=MCR¯i. The diagonal mixes’ space: DMi=MCDi. The row space: Ri=SC−1Di.For example, if∀x1,x2,…,x11,x12∈F24, then(4)C0=x1000x2000x3000x4000,D0=x10000x20000x30000x4,CS0=x100000x30000x40x200,M0=0x2x3x4x1x20x4x1x2x30x10x3x4,R¯0=0000x1x4x7x10x2x5x8x11x3x6x9x12,W0=x1⊕x2⊕x3x4⊕x5⊕x6x7⊕x8⊕x9x10⊕x11⊕x12x2⊕x3x5⊕x6x8⊕x9x11⊕x12x1⊕x3x4⊕x6x7⊕x9x10⊕x12x1⊕x2x4⊕x5x7⊕x8x10⊕x11,DM0=0x2x3x4x10x3x4x1x20x4x1x2x30,R0=x1x2x3x4000000000000.Note that, due to the particularity of the shift transformation of the Midori algorithm, the first element (from left to right and top to bottom) of theith row (column) of Di is not necessarily nonzero. To mark which row’s (column) first element of Di is nonzero, we define a rotation η0123=0123. Then, the first element of the ηith row (column) of Di is nonzero.Moreover, it is not necessarily true that theith row of R¯i contains all 0s and that other rows have variables. To mark which row of R¯i contains all 0s, we define a rotation τ0123=0123. Then, the elements of the τith row of R¯i are all 0, and the remaining rows have variables.The four element expressions in rowτi of Wi are all sums of three variables, while the rest of the element expressions are all sums of two variables. Row τi of Ri has nonzero variables, while the rest of the rows contain all zeros.Definition 2.
GivenI⊆0,1,2,3, where 0<I≤3, we define(5)CI=⊕i∈ICi,DI=⊕i∈IDi,CSI=⊕i∈ICSi,MI=⊕i∈IMi,R¯I=⊕i∈IRi,WI=⊕i∈IWiDMi=⊕i∈IDMiRi=⊕i∈IRi.


### 3.2. The Propagation Law of Midori-64 Subspace and the Intersection Property of Each Subspace

The previous section defined a part of the text subspace of Midori-64. Next, we study the propagation law in the Midori-64 encryption function and the intersection property of each subspace.Lemma 1.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈DI⊥, there is a unique b∈CI⊥ such that RKDI⊕a=CI⊕b.Proof.
Since byte substitution is bijective and acts independently on each byte, it simply maps the cosetDI⊕a to DI⊕a0, where a=Sai, for all i=1,2,……,15. The byte shift operation simply moves the byte of DI⊕a0 to the column space CI⊕b0, where b0=SCa0. Column mixing keeps the column space unchanged, and it is a linear transformation, so MCI⊕b0=CI⊕Mb0=CI⊕b1. KeyAdd turns the coset into CI⊕b, where b=b1⊕k and k is the round key.
This means that a coset of a diagonal spaceDI goes through a round of encryption and becomes the coset of a column space CI. Two different cosets V⊕a and V⊕b are called equivalent [20] if and only if a⊕b∈V. This situation is recorded as V⊕a∼V⊕b. Therefore, in the previous lemma, b is unique in the equivalent sense.
Similar to before, we can obtain the propagation laws of other subspaces. Next, we provide Lemmas2 to 4 as follows.Lemma 2.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈CI⊥, there is a unique b∈MI⊥, such that RKCI⊕a=MI⊕b.Lemma 3.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈MI⊥, there is a unique b∈WI⊥, such that RKMI⊕a=WI⊕b.Lemma 4.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈DI⊥, there is a unique b∈R¯I⊥ such that RK−1DI⊕a=R¯I⊕b.Note that the conclusions from Lemmas1 to 4 are all reversible. For example, according to Lemma 3, we have RKDI⊕a=CI⊕b; then, RK−1CI⊕b=DI⊕a must also hold (in the sense of coset equivalence). The conclusion and proof process are not given here.The propagation law of the subspace after a round of Midori-64 is given above. Next, we study the property of the intersection of the Midori subspaces and explain that the column space has nonzero intersections with the diagonal space and theCS space. The window space WI and the diagonal space DJ have nonzero intersections.Lemma 5.
Di∩Cj=eSC−14i+t, where t satisfies ⌊SC−14i+t/4⌋=j and CSi∩Cj=eSC4i+t.Proof.
Di=SC−1Ci, Di=eSC4i+t, and CSi=SCCi. SC and SC−1 disperse the four elements of one column of Ci into 4 columns, so Di and Cj have one and only one intersection. Let t=0,1,2,3. When ⌊SC−14i+t/4⌋=j is satisfied, eSC−14i+t belongs to both Di and Cj, so Di∩Cj=eSC−14i+t. In the same way, when ⌊SC−14i+t/4⌋=j, CSi∩Cj=eSC4i+t.Lemma 6.
Wi∩Dj=eSC−14j+t, where t satisfies SC−14j+tmod4=τi, t=0,1,2,3.Lemma 7.
Di∩R¯j=Di∩Ca,b,c, where a,b,c satisfy a,b,c,⌊SC−14i+t/4⌋=0,1,2,3 and t satisfies SC−14i+tmod4=τj, t=0,1,2,3.The bijective function can maintain the property of the intersection of subspaces. In order to describe the form of the intersection of two subspaces more accurately, we give the following lemma.Lemma 8.
Mj∩Ci⟶S−boxCi∩Dk,l,m.
The proofs of Lemmas6 to 8 are shown in Appendix A.


## 3.1. The Subspace of Midori-64

For a vector spaceV and a function F on F244×4, let FV=Fv|v∈V. For a subset I⊆1,2,…,n and a subset of vector spaces G1,G2,…,Gn, we define GI=⊕i∈IGi.All the subspaces in this paper are defined on the spaceF244×4 over the field F24. Moreover, we denote E=e0,……,e15 as the unit vector space of F244×4. Otherwise, as specified below, the value range of a positive integer i in the subspace definition is 0≤i≤3. In the following, we define some families of subspaces that are essential to Midori-64: diagonal spaces DI, column spaces CI, mixed spaces MI, and so on.The column space:Ci=e4i,e4i+1,e4i+2,e4i+3. The diagonal space: Di=SC−1Ci. The CS space: CSi=SCCi. The mixed space: Mi=MCCSi. The inverse row space: R¯i=SCMi. The window space: Wi=MCR¯i. The diagonal mixes’ space: DMi=MCDi. The row space: Ri=SC−1Di.For example, if∀x1,x2,…,x11,x12∈F24, then(4)C0=x1000x2000x3000x4000,D0=x10000x20000x30000x4,CS0=x100000x30000x40x200,M0=0x2x3x4x1x20x4x1x2x30x10x3x4,R¯0=0000x1x4x7x10x2x5x8x11x3x6x9x12,W0=x1⊕x2⊕x3x4⊕x5⊕x6x7⊕x8⊕x9x10⊕x11⊕x12x2⊕x3x5⊕x6x8⊕x9x11⊕x12x1⊕x3x4⊕x6x7⊕x9x10⊕x12x1⊕x2x4⊕x5x7⊕x8x10⊕x11,DM0=0x2x3x4x10x3x4x1x20x4x1x2x30,R0=x1x2x3x4000000000000.Note that, due to the particularity of the shift transformation of the Midori algorithm, the first element (from left to right and top to bottom) of theith row (column) of Di is not necessarily nonzero. To mark which row’s (column) first element of Di is nonzero, we define a rotation η0123=0123. Then, the first element of the ηith row (column) of Di is nonzero.Moreover, it is not necessarily true that theith row of R¯i contains all 0s and that other rows have variables. To mark which row of R¯i contains all 0s, we define a rotation τ0123=0123. Then, the elements of the τith row of R¯i are all 0, and the remaining rows have variables.The four element expressions in rowτi of Wi are all sums of three variables, while the rest of the element expressions are all sums of two variables. Row τi of Ri has nonzero variables, while the rest of the rows contain all zeros.Definition 2.
GivenI⊆0,1,2,3, where 0<I≤3, we define(5)CI=⊕i∈ICi,DI=⊕i∈IDi,CSI=⊕i∈ICSi,MI=⊕i∈IMi,R¯I=⊕i∈IRi,WI=⊕i∈IWiDMi=⊕i∈IDMiRi=⊕i∈IRi.


## 3.2. The Propagation Law of Midori-64 Subspace and the Intersection Property of Each Subspace

The previous section defined a part of the text subspace of Midori-64. Next, we study the propagation law in the Midori-64 encryption function and the intersection property of each subspace.Lemma 1.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈DI⊥, there is a unique b∈CI⊥ such that RKDI⊕a=CI⊕b.Proof.
Since byte substitution is bijective and acts independently on each byte, it simply maps the cosetDI⊕a to DI⊕a0, where a=Sai, for all i=1,2,……,15. The byte shift operation simply moves the byte of DI⊕a0 to the column space CI⊕b0, where b0=SCa0. Column mixing keeps the column space unchanged, and it is a linear transformation, so MCI⊕b0=CI⊕Mb0=CI⊕b1. KeyAdd turns the coset into CI⊕b, where b=b1⊕k and k is the round key.
This means that a coset of a diagonal spaceDI goes through a round of encryption and becomes the coset of a column space CI. Two different cosets V⊕a and V⊕b are called equivalent [20] if and only if a⊕b∈V. This situation is recorded as V⊕a∼V⊕b. Therefore, in the previous lemma, b is unique in the equivalent sense.
Similar to before, we can obtain the propagation laws of other subspaces. Next, we provide Lemmas2 to 4 as follows.Lemma 2.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈CI⊥, there is a unique b∈MI⊥, such that RKCI⊕a=MI⊕b.Lemma 3.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈MI⊥, there is a unique b∈WI⊥, such that RKMI⊕a=WI⊕b.Lemma 4.
LettingI⊆0,1,2,3, where 0<I≤3 and a∈DI⊥, there is a unique b∈R¯I⊥ such that RK−1DI⊕a=R¯I⊕b.Note that the conclusions from Lemmas1 to 4 are all reversible. For example, according to Lemma 3, we have RKDI⊕a=CI⊕b; then, RK−1CI⊕b=DI⊕a must also hold (in the sense of coset equivalence). The conclusion and proof process are not given here.The propagation law of the subspace after a round of Midori-64 is given above. Next, we study the property of the intersection of the Midori subspaces and explain that the column space has nonzero intersections with the diagonal space and theCS space. The window space WI and the diagonal space DJ have nonzero intersections.Lemma 5.
Di∩Cj=eSC−14i+t, where t satisfies ⌊SC−14i+t/4⌋=j and CSi∩Cj=eSC4i+t.Proof.
Di=SC−1Ci, Di=eSC4i+t, and CSi=SCCi. SC and SC−1 disperse the four elements of one column of Ci into 4 columns, so Di and Cj have one and only one intersection. Let t=0,1,2,3. When ⌊SC−14i+t/4⌋=j is satisfied, eSC−14i+t belongs to both Di and Cj, so Di∩Cj=eSC−14i+t. In the same way, when ⌊SC−14i+t/4⌋=j, CSi∩Cj=eSC4i+t.Lemma 6.
Wi∩Dj=eSC−14j+t, where t satisfies SC−14j+tmod4=τi, t=0,1,2,3.Lemma 7.
Di∩R¯j=Di∩Ca,b,c, where a,b,c satisfy a,b,c,⌊SC−14i+t/4⌋=0,1,2,3 and t satisfies SC−14i+tmod4=τj, t=0,1,2,3.The bijective function can maintain the property of the intersection of subspaces. In order to describe the form of the intersection of two subspaces more accurately, we give the following lemma.Lemma 8.
Mj∩Ci⟶S−boxCi∩Dk,l,m.
The proofs of Lemmas6 to 8 are shown in Appendix A.


## 4. Subspace Trail-Based Impossible Differential Attack on 6-Round Midori-64 with a Single Secret S-Box

### 4.1. The Special Impossible Differential Attack on 6-Round Midori-64

In the previous section, we defined some subspaces of Midori-64 and studied the propagation laws of the subspaces and the intersection properties of each subspace. In the following, we extend the 5-round impossible difference concept to a subspace trail-based impossible differential key recovery method for 6-round Midori-64 using the above known information and a proposition that applies to column mixture matrices satisfying a special condition (three identical values are contained in one column). The attack is then transformed into a distinguisher according to the idea of excluding three bytes with incorrect keys. To facilitate the description, the definition of the Hamming weight is given first.Definition 3.
A subspaceV of the space F244×4 is defined on the domain F24, whose number of nonzero bytes n is the Hamming weight of V, where 0≤n≤16
The general truncated impossible difference uses the contradiction that the bytes at the corresponding positions of the two matrices are zero and nonzero, while the subspace trail-based impossible difference uses the intersection of the two subspaces as zero space. To find the longest truncated impossible difference, we usually encrypt texts from the head state, decrypt from the tail, and find the contradiction in the middle. This method inevitably leads to the Hamming weight of the ending subspace being very small, usually 1 or 2. Using the subspace trail, we can directly start from one subspace after encrypting the starting point for a few rounds and find the subspace that intersects with the set of 0 as the intermediate starting point and continue to encrypt several rounds (must be reversible). Finally, we obtain an impossible difference. Since the encryption process makes the Hamming weight of the subspace larger, the last round of the subspace of the distinguisher found by this method has a larger Hamming weight, and the advantage of distinguishing is also greater.
To find the 6-round subspace trail-based impossible differential distinguisher of Midori-64, we first need to give the ending encryption and decryption subspaces of Midori-64, and their intersection is 0, which is the crucial step of the subspace trail-based impossible differential attack. The following lemma is given, and the proof is given in Appendix A.Lemma 9.
Mj,k,l∩Wi∩Da=0.When selecting a subspaceCj∩Di as the initial space, according to the subspace propagation law in Section 3.2, a three-round subspace trail is obtained:(6)Cj∩Di⟶EkMj∩Ci⟶Lemma3.8S−boxCi∩Dk,l,m⟶AKMCSCMi∩Ck,l,m⟶EkWi∩Mk,l,m.To perform the key guessing attack, the following proposition is given.Proposition 1.
p1 and p2 are two plaintexts. When i≠5, 10, or 15, pi1=pi2. p51⊕p52=p101⊕p102=p151⊕p152=α. If p51⊕p101=k5⊕k10 and p51⊕p151=k5⊕k15 (k is the whitening key), then, after one round of encryption, they belong to the same coset of C0∩D0, namely, Rp1⊕Rp2∈C0∩D0.Proof.
The plaintext pairp1 and p2 after the whitening key addition, S-box, and byte shift is(7)0000Sp101⊕k10⊕Sp102⊕k10000Sp51⊕k5⊕Sp52⊕k5000Sp151⊕k15⊕Sp152⊕k15000.
Whenp51⊕p101=k5⊕k10 and p51⊕p151=k5⊕k15 (k is the whitening key), we have Sp51⊕k5⊕Sp52⊕k5=Sp101⊕k10⊕Sp101⊕k10⊕α=Sp101⊕k10⊕Sp102⊕k10 and Sp151⊕k15⊕Sp152⊕k15=Sp101⊕k10⊕Sp101⊕k10⊕α=Sp101⊕k10⊕Sp102⊕k10. After column mixing, by Property 2, the difference state matrix is(8)Sp101⊕k10⊕Sp102⊕k10000000000000000∈C0∩D0.
Note that the S-box information is not used in the proof of the proposition. This proposition can be easily extend to a general form.Proposition 2.
p1 and p2 are two plaintexts, p1,p2∈Dj: when i≠SR−14j+t, t=0,1,2,3/a (where a∈0,1,2,3), pi1=pi2. pSR−14j+11⊕pSR−14j+12=pSR−14j+21⊕pSR−14j+22=pSR−14j+31⊕pSR−14j+32=α. If pSR−14j+11⊕pSR−14j+21=kSR−14j+1⊕kSR−14j+2 and pSR−14j+21⊕pSR−14j+31=kSR−14j+2⊕kSR−14j+3 (k is the whitening key), then, after one round of encryption, they belong to the same coset of Cj∩Db, namely, Rp1⊕Rp2∈Cj∩Db. With Proposition 2, a general 6-round Midori-64 key recovery attack can be given. First, we define a plaintext set Vδ,μ. For convenience, we fix α=1. Vδ,μ=24:(9)Vδ,μ=pi,cifori=0,…,24−1|p5i⊕p10i=δ,p5i⊕p15i=μ,∀i,p51⊕p52=p101⊕p102=p151⊕p152=α=1,pki=pkj,∀k≠5,10,15andi≠j.That is, the plaintext has 13 constant bytes, and the other 3 bytes have fixed differences between each them which areδ, μ, and δ⊕μ.Consider Proposition9; if δ=k5⊕k10, μ=k5⊕k15, and p1,p2∈C0,1,2∩D0, then, after one round of encryption, they belong to the same coset of C0∩D0, that is, Rp1⊕Rp2∈C0∩D0⊆D0. From formula (6), the difference after four rounds falls into the same coset of W0∩M1,2,3 with probability 1. Then, from Lemma 9, W0∩M1,2,3∩Da=0, a=1,2,3. From the subspace propagation law of Section 3.2, Da⇌Ca⇌Ma, so the plaintext pair p1 and p2 will not produce the difference that falls into Ma, a=1,2,3, after 6 rounds of Midori-64 encryption. That is, for all p1,c1≠p2,c2,(10)p1,c1≠p2,c2andPrR6p1⊕R6p2∈Ma|p1,c1,p2,c2∈Vδ,μ=0.Ifδ=k5⊕k10 and μ=k5⊕k15 are not satisfied simultaneously, then they fall into a coset of C0 with probability 1 after one round of encryption and fall into C0∩D0 with probability 2−43=2−12. The probability that two plaintexts fall into the subspace Maa=1,2,3 after 6 rounds of encryption is 3×216/264≈2−46.4.From the above discussion, we obtain a 6-round SUBspace trail-based impossible difference for Midori-64 as follows:(11)Ca,b,c∩Dj⟶EkCj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m,⟶EkWi∩Mk,l,m=impossibleDr⟶EkCr⟶EkMr.TakingC0,1,2∩D0 as an example,(12)00000x′0000y′0000z′⟶Ekx′′000000000000000⟶Ek0000x′′′000y′′′000z′′′000⟶Ek0xzy0x0y0xz000zy⟶Ekx1⊕x2⊕x3x4⊕x5x6⊕x7x8⊕x9x2⊕x3x5x6⊕x7x9x1⊕x3x4x7x8⊕x9x1⊕x2x4⊕x5x6x8=impossibleLemma4.10y˙00x˙000000w˙00z˙0,⟶Ek0x¨000y¨000z¨000w¨00⟶Ekdfg0d0ge0fgedf0e.Sincer has three values, we can detect whether the difference between the plaintext pair after encryption is in these three mixed spaces. If the difference falls into these three mixed spaces, it must not be obtained by 6 rounds of Midori-64 encryption, and 3 bytes with wrong keys can be excluded.


### 4.2. Key Recovery Attacks on Midori with a Secret S-Box

Now, we focus on Midori-64 with a secret bijective S-box and then use the subspace trail to derive a general method for recovering all keys without any information or an equivalent representation of the S-box.The core idea of an attack on Midori with a secret S-box is as follows. We selectDi as the starting subspace. It is known that a coset of Di is mapped to a coset of Ci after a round of encryption. Using the special properties of the Midori column mix matrix, we can choose a subset of Di that relies on the secret key and let it fall into Ci∩Dj with probability 1 after one round of encryption. That is, we guess some bytes of the key to select a subset of Di’s coset; if the guessed key is wrong, then it is mapped to a coset of Ci after encryption. In contrast, if the guessed key is correct, it is mapped to a coset of Ci∩Dj after encryption, that is, a coset of Dj. Note that even if the key is guessed incorrectly, it may also cause the subspace to be mapped to Dj, but the probability of this event is much less than 1. Using this property and other conclusions, the adversary can recover the correct key.In particular, when there is at least one collision, a set of candidate keysδ and μ are judged as wrong keys. That is, two different plaintext pairs p1,c1 and p2,c2 are formed, where p1⊕p2∈Vδ,μ, c1⊕c2∈Ma, and a=1,2,3. Therefore, for each group δ=k5⊕k10 with μ=k5⊕k15, it is necessary to find the minimum number of texts with a high probability of causing at least one collision.The attack is divided into two steps. First, attention is paid to the three-byte difference of the secret key. Then, all the keys are found.Algorithm 1: The key recovery attack of 6-round Midori-64.
Input:254.6 chosen plaintexts (each pair of δ, μ has 246.6 texts, i.e., 242.6 different sets Vδ,μ)Output:k5⊕k10, k5⊕k15, k10⊕k15(1)
fora=0,b=0;a<24,b<24 do(2)
flag = 0;(3)
divide the246.6 to the corresponding different 242.6 sets Vδ,μ;(4)
for each one of the242.6 different sets Va,b do(5)
letpi,ci for i=0,…,24−1 be the 24−1 (plaintexts, ciphertexts) of a single set Va,b;(6)
reorder this set of elements as described in [18];(7)
fori = 0; i<24−−1 do(8)
ifci⊕ci+1∈Ma,a=1,2,3, then(9)
flag = 1;(10)
next collection (i.e., next pair ofδ, μ);(11)
if flag = 0, then(12)
identifyδ, μ, δ⊕μ as candidates of k5⊕k10, k5⊕k15, k10⊕k15, respectively;(13)
return candidates ofk5⊕k10,k5⊕k15,k10⊕k15.Next, we calculate the amount of data and computational complexity required for the attack.The purpose is to find the minimum numberm of plaintexts required to ensure collisions with high probability in random situations. For this reason, we introduce the “birthday paradox.” For a given d value and n variables, the probability that at least two variables have the same value can be calculated by(13)p=1−n!n−d!nd=1−d!ndCnd≅1−e−dd−12n.The last step is a useful approximation. If we choose two plaintexts ofDi+a, they can only belong to Mi+c after two rounds of Midori-64; then, the probability of obtaining a collision is p=1−e−mm−1/2·24. However, if we choose Di with i=0,1,2,3/b as the target space, all three spaces produce independent experiments. Therefore, given m plaintext subspaces, the probability of at least one collision occurring is(14)p=1−24!24−m!24d3≅1−e−mm−12·243≅1−e−mm−123.4.Ifm=6, the probability of at least one collision occurring in one of the three different spaces is 94% (in fact, when m=4 is selected, at least one collision is obtained with a probability of 67.6%).To distinguish these two types of sets (i.e., random sets and “subspace” sets), the verifier must construct all possible plaintext pairs and count the number of collisions between each plaintext pair.Finding a Secret Byte for the Secret Key-Data Complexity. Only one collision can eliminate an error group of δ and μ. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Ma after 6 rounds of encryption is 216/264=2−48. Therefore, given n pairs and a fixed δ=k5⊕k10 and μ=k5⊕k15, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Ma is p=1−e−nn−1/46.4. If n=224 (approximately 247 pairs), the probability p is greater than 95 % (taking n = 223.5, there is a 75 % chance of obtaining a collision). Given a set Vδ,μ, 23·24−1=120≈27 different pairs can be constructed. Therefore, for the adversary, approximately 247·2−7=240 different sets Vδ,μ are needed. Since each set contains 24 texts, the data complexity is 240·24=244 texts. With this method, the adversary can recover a 3 byte key k5,k10,k15.Finding the Secret Key-Data Complexity. To recover all the keys, we need to repeat the attack 4 times. First, we select 4 different diagonal spaces Di as the initial space to attack and restore different positions with a total of 4×3×4=48 bit keys. The remaining 16 bit key can be obtained through an exhaustive search. Since there are 28 different combinations of δ and μ and the attack must be repeated 4 times, the total number of texts required for the attack is 28·4·240=250.Computational Complexity. The adversary needs to construct all text pairs to calculate the number of collisions in the same coset of Maa=1,2,3. The best way to reduce the computational complexity is to “reorder” the elements in all sets. The algorithm for doing so is described in [20]. Then, we only need to count the number of collisions among texts that are sorted. In this case, each set has 24 elements, and the “reordering” algorithm requires 3·24⋅log24+1≈27.6 table lookup operations. Since this operation is the most time-consuming step, we can estimate the cost of this attack as 4·240·27.6=249.6.


### 4.3. Subspace Trail-Based Impossible Differential Distinguisher of 6-Round Midori-64

After key recovery attacks on 6-round Midori-64 based on subspace trails, we give the corresponding 6 rounds of the distinguisher.The core idea is to detect whether there is a pair of plaintexts such that the impossible difference satisfies. Note that compared to key recovery attacks, the advantage of the distinguisher is that it does not need to recover all the keys to distinguish two functions, since it only needs a limited number of bytes to judge. In addition, the constructed distinguisher is independent of the S-box, but the column mix is required to meet the assumption (there are three same values in a column in the column mix matrix).Theorem 1.
The data complexity of a 6-round Midori-64 subspace trail impossible differential distinguisher is254.6 chosen plaintexts, and the computational complexity is 258.2 table lookup operation.Proof.
The idea is to consider242.6 different sets Vδ,μ with a total of 24·242.6·28=254.6 chosen plaintexts. From Proposition 1, there is a set δ and μ such that the set does not collide after 6-round Midori-64 encryption; that is, for Midori-64 and δ=k5⊕k10 with μ=k5⊕k15, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ and c1,c2∈Ma. In this way, 6-round Midori-64 can be distinguished from the random function, that is, there are 28 collections (each group δ and μ constitute a collection), and each collection has 242.6 different sets Vδ,μ. In random permutation, there is a 95 % probability of getting at least one collision in each of the 256 collections. Note that the average number of collisions for each collection should be 2−46.4·249.6=23.2≃9. For the Midori-64 cypher, it is expected that there is a group δ and μ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The data complexity is 254.6 choice plaintexts, and the computational complexity is 28·242.6·27.6=258.2.
The truncated impossible differential distinguisher of 6-round Midori-64 ranges from the ending state to the middle round and then conflicts with the state obtained by encrypting the starting state, so the following situation is generally encountered:(15)Ca,b,c∩Dj⟶EkCj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m=impossibleSR−1Ws∩DMu,v,w←Ek−1R¯s∩Du,v,w←Ek−1Ds∩Cu,v,w←Ek−1Cs∩Dt.
The difference matrix at the ending state has only one variable, so the distinguishing advantage is24/264≈2−60. In contrast, the subspace trail-based impossible differential distinguisher has a larger distinguishing advantage which is 216/264=2−48.
Note that the above attack and distinguisher have nothing to do with the size of the cipher and the specific information of the S-box, that is, they are also effective for Midori-128 with a secret S-box.


## 4.1. The Special Impossible Differential Attack on 6-Round Midori-64

In the previous section, we defined some subspaces of Midori-64 and studied the propagation laws of the subspaces and the intersection properties of each subspace. In the following, we extend the 5-round impossible difference concept to a subspace trail-based impossible differential key recovery method for 6-round Midori-64 using the above known information and a proposition that applies to column mixture matrices satisfying a special condition (three identical values are contained in one column). The attack is then transformed into a distinguisher according to the idea of excluding three bytes with incorrect keys. To facilitate the description, the definition of the Hamming weight is given first.Definition 3.
A subspaceV of the space F244×4 is defined on the domain F24, whose number of nonzero bytes n is the Hamming weight of V, where 0≤n≤16
The general truncated impossible difference uses the contradiction that the bytes at the corresponding positions of the two matrices are zero and nonzero, while the subspace trail-based impossible difference uses the intersection of the two subspaces as zero space. To find the longest truncated impossible difference, we usually encrypt texts from the head state, decrypt from the tail, and find the contradiction in the middle. This method inevitably leads to the Hamming weight of the ending subspace being very small, usually 1 or 2. Using the subspace trail, we can directly start from one subspace after encrypting the starting point for a few rounds and find the subspace that intersects with the set of 0 as the intermediate starting point and continue to encrypt several rounds (must be reversible). Finally, we obtain an impossible difference. Since the encryption process makes the Hamming weight of the subspace larger, the last round of the subspace of the distinguisher found by this method has a larger Hamming weight, and the advantage of distinguishing is also greater.
To find the 6-round subspace trail-based impossible differential distinguisher of Midori-64, we first need to give the ending encryption and decryption subspaces of Midori-64, and their intersection is 0, which is the crucial step of the subspace trail-based impossible differential attack. The following lemma is given, and the proof is given in Appendix A.Lemma 9.
Mj,k,l∩Wi∩Da=0.When selecting a subspaceCj∩Di as the initial space, according to the subspace propagation law in Section 3.2, a three-round subspace trail is obtained:(6)Cj∩Di⟶EkMj∩Ci⟶Lemma3.8S−boxCi∩Dk,l,m⟶AKMCSCMi∩Ck,l,m⟶EkWi∩Mk,l,m.To perform the key guessing attack, the following proposition is given.Proposition 1.
p1 and p2 are two plaintexts. When i≠5, 10, or 15, pi1=pi2. p51⊕p52=p101⊕p102=p151⊕p152=α. If p51⊕p101=k5⊕k10 and p51⊕p151=k5⊕k15 (k is the whitening key), then, after one round of encryption, they belong to the same coset of C0∩D0, namely, Rp1⊕Rp2∈C0∩D0.Proof.
The plaintext pairp1 and p2 after the whitening key addition, S-box, and byte shift is(7)0000Sp101⊕k10⊕Sp102⊕k10000Sp51⊕k5⊕Sp52⊕k5000Sp151⊕k15⊕Sp152⊕k15000.
Whenp51⊕p101=k5⊕k10 and p51⊕p151=k5⊕k15 (k is the whitening key), we have Sp51⊕k5⊕Sp52⊕k5=Sp101⊕k10⊕Sp101⊕k10⊕α=Sp101⊕k10⊕Sp102⊕k10 and Sp151⊕k15⊕Sp152⊕k15=Sp101⊕k10⊕Sp101⊕k10⊕α=Sp101⊕k10⊕Sp102⊕k10. After column mixing, by Property 2, the difference state matrix is(8)Sp101⊕k10⊕Sp102⊕k10000000000000000∈C0∩D0.
Note that the S-box information is not used in the proof of the proposition. This proposition can be easily extend to a general form.Proposition 2.
p1 and p2 are two plaintexts, p1,p2∈Dj: when i≠SR−14j+t, t=0,1,2,3/a (where a∈0,1,2,3), pi1=pi2. pSR−14j+11⊕pSR−14j+12=pSR−14j+21⊕pSR−14j+22=pSR−14j+31⊕pSR−14j+32=α. If pSR−14j+11⊕pSR−14j+21=kSR−14j+1⊕kSR−14j+2 and pSR−14j+21⊕pSR−14j+31=kSR−14j+2⊕kSR−14j+3 (k is the whitening key), then, after one round of encryption, they belong to the same coset of Cj∩Db, namely, Rp1⊕Rp2∈Cj∩Db. With Proposition 2, a general 6-round Midori-64 key recovery attack can be given. First, we define a plaintext set Vδ,μ. For convenience, we fix α=1. Vδ,μ=24:(9)Vδ,μ=pi,cifori=0,…,24−1|p5i⊕p10i=δ,p5i⊕p15i=μ,∀i,p51⊕p52=p101⊕p102=p151⊕p152=α=1,pki=pkj,∀k≠5,10,15andi≠j.That is, the plaintext has 13 constant bytes, and the other 3 bytes have fixed differences between each them which areδ, μ, and δ⊕μ.Consider Proposition9; if δ=k5⊕k10, μ=k5⊕k15, and p1,p2∈C0,1,2∩D0, then, after one round of encryption, they belong to the same coset of C0∩D0, that is, Rp1⊕Rp2∈C0∩D0⊆D0. From formula (6), the difference after four rounds falls into the same coset of W0∩M1,2,3 with probability 1. Then, from Lemma 9, W0∩M1,2,3∩Da=0, a=1,2,3. From the subspace propagation law of Section 3.2, Da⇌Ca⇌Ma, so the plaintext pair p1 and p2 will not produce the difference that falls into Ma, a=1,2,3, after 6 rounds of Midori-64 encryption. That is, for all p1,c1≠p2,c2,(10)p1,c1≠p2,c2andPrR6p1⊕R6p2∈Ma|p1,c1,p2,c2∈Vδ,μ=0.Ifδ=k5⊕k10 and μ=k5⊕k15 are not satisfied simultaneously, then they fall into a coset of C0 with probability 1 after one round of encryption and fall into C0∩D0 with probability 2−43=2−12. The probability that two plaintexts fall into the subspace Maa=1,2,3 after 6 rounds of encryption is 3×216/264≈2−46.4.From the above discussion, we obtain a 6-round SUBspace trail-based impossible difference for Midori-64 as follows:(11)Ca,b,c∩Dj⟶EkCj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m,⟶EkWi∩Mk,l,m=impossibleDr⟶EkCr⟶EkMr.TakingC0,1,2∩D0 as an example,(12)00000x′0000y′0000z′⟶Ekx′′000000000000000⟶Ek0000x′′′000y′′′000z′′′000⟶Ek0xzy0x0y0xz000zy⟶Ekx1⊕x2⊕x3x4⊕x5x6⊕x7x8⊕x9x2⊕x3x5x6⊕x7x9x1⊕x3x4x7x8⊕x9x1⊕x2x4⊕x5x6x8=impossibleLemma4.10y˙00x˙000000w˙00z˙0,⟶Ek0x¨000y¨000z¨000w¨00⟶Ekdfg0d0ge0fgedf0e.Sincer has three values, we can detect whether the difference between the plaintext pair after encryption is in these three mixed spaces. If the difference falls into these three mixed spaces, it must not be obtained by 6 rounds of Midori-64 encryption, and 3 bytes with wrong keys can be excluded.


## 4.2. Key Recovery Attacks on Midori with a Secret S-Box

Now, we focus on Midori-64 with a secret bijective S-box and then use the subspace trail to derive a general method for recovering all keys without any information or an equivalent representation of the S-box.The core idea of an attack on Midori with a secret S-box is as follows. We selectDi as the starting subspace. It is known that a coset of Di is mapped to a coset of Ci after a round of encryption. Using the special properties of the Midori column mix matrix, we can choose a subset of Di that relies on the secret key and let it fall into Ci∩Dj with probability 1 after one round of encryption. That is, we guess some bytes of the key to select a subset of Di’s coset; if the guessed key is wrong, then it is mapped to a coset of Ci after encryption. In contrast, if the guessed key is correct, it is mapped to a coset of Ci∩Dj after encryption, that is, a coset of Dj. Note that even if the key is guessed incorrectly, it may also cause the subspace to be mapped to Dj, but the probability of this event is much less than 1. Using this property and other conclusions, the adversary can recover the correct key.In particular, when there is at least one collision, a set of candidate keysδ and μ are judged as wrong keys. That is, two different plaintext pairs p1,c1 and p2,c2 are formed, where p1⊕p2∈Vδ,μ, c1⊕c2∈Ma, and a=1,2,3. Therefore, for each group δ=k5⊕k10 with μ=k5⊕k15, it is necessary to find the minimum number of texts with a high probability of causing at least one collision.The attack is divided into two steps. First, attention is paid to the three-byte difference of the secret key. Then, all the keys are found.Algorithm 1: The key recovery attack of 6-round Midori-64.
Input:254.6 chosen plaintexts (each pair of δ, μ has 246.6 texts, i.e., 242.6 different sets Vδ,μ)Output:k5⊕k10, k5⊕k15, k10⊕k15(1)
fora=0,b=0;a<24,b<24 do(2)
flag = 0;(3)
divide the246.6 to the corresponding different 242.6 sets Vδ,μ;(4)
for each one of the242.6 different sets Va,b do(5)
letpi,ci for i=0,…,24−1 be the 24−1 (plaintexts, ciphertexts) of a single set Va,b;(6)
reorder this set of elements as described in [18];(7)
fori = 0; i<24−−1 do(8)
ifci⊕ci+1∈Ma,a=1,2,3, then(9)
flag = 1;(10)
next collection (i.e., next pair ofδ, μ);(11)
if flag = 0, then(12)
identifyδ, μ, δ⊕μ as candidates of k5⊕k10, k5⊕k15, k10⊕k15, respectively;(13)
return candidates ofk5⊕k10,k5⊕k15,k10⊕k15.Next, we calculate the amount of data and computational complexity required for the attack.The purpose is to find the minimum numberm of plaintexts required to ensure collisions with high probability in random situations. For this reason, we introduce the “birthday paradox.” For a given d value and n variables, the probability that at least two variables have the same value can be calculated by(13)p=1−n!n−d!nd=1−d!ndCnd≅1−e−dd−12n.The last step is a useful approximation. If we choose two plaintexts ofDi+a, they can only belong to Mi+c after two rounds of Midori-64; then, the probability of obtaining a collision is p=1−e−mm−1/2·24. However, if we choose Di with i=0,1,2,3/b as the target space, all three spaces produce independent experiments. Therefore, given m plaintext subspaces, the probability of at least one collision occurring is(14)p=1−24!24−m!24d3≅1−e−mm−12·243≅1−e−mm−123.4.Ifm=6, the probability of at least one collision occurring in one of the three different spaces is 94% (in fact, when m=4 is selected, at least one collision is obtained with a probability of 67.6%).To distinguish these two types of sets (i.e., random sets and “subspace” sets), the verifier must construct all possible plaintext pairs and count the number of collisions between each plaintext pair.Finding a Secret Byte for the Secret Key-Data Complexity. Only one collision can eliminate an error group of δ and μ. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Ma after 6 rounds of encryption is 216/264=2−48. Therefore, given n pairs and a fixed δ=k5⊕k10 and μ=k5⊕k15, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Ma is p=1−e−nn−1/46.4. If n=224 (approximately 247 pairs), the probability p is greater than 95 % (taking n = 223.5, there is a 75 % chance of obtaining a collision). Given a set Vδ,μ, 23·24−1=120≈27 different pairs can be constructed. Therefore, for the adversary, approximately 247·2−7=240 different sets Vδ,μ are needed. Since each set contains 24 texts, the data complexity is 240·24=244 texts. With this method, the adversary can recover a 3 byte key k5,k10,k15.Finding the Secret Key-Data Complexity. To recover all the keys, we need to repeat the attack 4 times. First, we select 4 different diagonal spaces Di as the initial space to attack and restore different positions with a total of 4×3×4=48 bit keys. The remaining 16 bit key can be obtained through an exhaustive search. Since there are 28 different combinations of δ and μ and the attack must be repeated 4 times, the total number of texts required for the attack is 28·4·240=250.Computational Complexity. The adversary needs to construct all text pairs to calculate the number of collisions in the same coset of Maa=1,2,3. The best way to reduce the computational complexity is to “reorder” the elements in all sets. The algorithm for doing so is described in [20]. Then, we only need to count the number of collisions among texts that are sorted. In this case, each set has 24 elements, and the “reordering” algorithm requires 3·24⋅log24+1≈27.6 table lookup operations. Since this operation is the most time-consuming step, we can estimate the cost of this attack as 4·240·27.6=249.6.


## 4.3. Subspace Trail-Based Impossible Differential Distinguisher of 6-Round Midori-64

After key recovery attacks on 6-round Midori-64 based on subspace trails, we give the corresponding 6 rounds of the distinguisher.The core idea is to detect whether there is a pair of plaintexts such that the impossible difference satisfies. Note that compared to key recovery attacks, the advantage of the distinguisher is that it does not need to recover all the keys to distinguish two functions, since it only needs a limited number of bytes to judge. In addition, the constructed distinguisher is independent of the S-box, but the column mix is required to meet the assumption (there are three same values in a column in the column mix matrix).Theorem 1.
The data complexity of a 6-round Midori-64 subspace trail impossible differential distinguisher is254.6 chosen plaintexts, and the computational complexity is 258.2 table lookup operation.Proof.
The idea is to consider242.6 different sets Vδ,μ with a total of 24·242.6·28=254.6 chosen plaintexts. From Proposition 1, there is a set δ and μ such that the set does not collide after 6-round Midori-64 encryption; that is, for Midori-64 and δ=k5⊕k10 with μ=k5⊕k15, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ and c1,c2∈Ma. In this way, 6-round Midori-64 can be distinguished from the random function, that is, there are 28 collections (each group δ and μ constitute a collection), and each collection has 242.6 different sets Vδ,μ. In random permutation, there is a 95 % probability of getting at least one collision in each of the 256 collections. Note that the average number of collisions for each collection should be 2−46.4·249.6=23.2≃9. For the Midori-64 cypher, it is expected that there is a group δ and μ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The data complexity is 254.6 choice plaintexts, and the computational complexity is 28·242.6·27.6=258.2.
The truncated impossible differential distinguisher of 6-round Midori-64 ranges from the ending state to the middle round and then conflicts with the state obtained by encrypting the starting state, so the following situation is generally encountered:(15)Ca,b,c∩Dj⟶EkCj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m=impossibleSR−1Ws∩DMu,v,w←Ek−1R¯s∩Du,v,w←Ek−1Ds∩Cu,v,w←Ek−1Cs∩Dt.
The difference matrix at the ending state has only one variable, so the distinguishing advantage is24/264≈2−60. In contrast, the subspace trail-based impossible differential distinguisher has a larger distinguishing advantage which is 216/264=2−48.
Note that the above attack and distinguisher have nothing to do with the size of the cipher and the specific information of the S-box, that is, they are also effective for Midori-128 with a secret S-box.


## 5. Subspace Trail of the Midori-64 Encryption and Decryption Algorithm

In 2016, Chen et al. constructed the first 6-round truncated impossible difference path for Midori-64 [16]. Since a truncated impossible difference exploits the contradiction between 0 bytes and nonzero bytes, while the subspace trace-based impossible difference exploits the contradiction by which the intersection between two subspaces is a zero subspace, it is meaningful to study the subspace trail-based impossible difference of Midori. If the impossible difference of Midori-64 over 6 rounds is obtained using a subspace trace, this shows that the subspace trail-based impossible difference is better than the truncated impossible difference in some ways. The existence of a space trail-based impossible distinguisher for 7-round (or more rounds) Midori-64 is one of the main focuses of this paper.The basic idea of the proof that Midori-64 has at most a 7-round subspace trail-based impossible differential distinguisher is to prove that every bit block of the output state of any (nonzero) initial differential state after 4 rounds of the Midori-64 encryption algorithm or 4 rounds of Midori-64 algorithm decryption is a possible differential activity, so the contradiction between nonzero bytes and 0 bytes in two states cannot be found; thus, it is impossible to construct 8 rounds or more of the Midori-64 subspace trail-based impossible differential distinguisher.Section4 introduces the idea of converting a subspace trail-based key recovery attack into a distinguisher that can be extended by one round, i.e., we consider the case, where the plaintext difference satisfies Property 2 after whitening the key and S-box.To find the longest subspace trace in both the encryption and decryption directions, first, we need to choose a starting space such that the subspace trail is as long as possible. Second, note that the intersection property of two subspaces is maintained when they pass through the cryptographic function, and the intersection can reduce the dimensionality of the subspace. We can find a longer subspace trail by precisely characterizing which subspaces are the intersections of other subspaces and passing them in the forms of intersections.


### 5.1. The Longest Subspace Trail of the Midori-64 Encryption Algorithm

Note that the subspace trail in the encryption direction of Midori-64,Di has no predecessor, and no subspace becomes Di with probability 1 after one round of encryption, that is, when Di is selected as the starting subspace, the subspace trail formed is the longest. Therefore, to prove this lemma, we discuss the four cases with 1 active byte, 2 active bytes, 3 active bytes, and 4 active bytes in the initial input differential space Di.Property 3.
When the input difference falls intoDi and there is only one active byte, after 3 rounds of Midori-64 encryption, every byte of the output difference is active.Proof.
Since there is only one active byte, we may also assume that the difference falls intoCj∩Di; then, the subspace propagation law obtained in Section 3.2 yields(16)Cj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m⟶EkWi∩Mk,l,m,where j,k,l,m=1,2,3,4.
For example,(17)x000000000000000⟶Ek0000x000y000z000⟶Ek0xzy0x0y0xz000zy⟶Ekx1⊕x2⊕x3x4⊕x5x6⊕x7x8⊕x9x2⊕x3x5x6⊕x7x9x1⊕x3x4x7x8⊕x9x1⊕x2x4⊕x5x6x8.
Note thatxi,i=1,…,9, must be nonzero, so the resulting subspace can be written as follows:(18)?????1?1?11???11.
Among the above symbols, “?” means that the difference byte could be 0 or nonzero and “1″ means that the byte must not be 0.Property 4.
When the input difference falls intoDi and there are two active bytes, after 4 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
When the input difference is passed through the whitening key S-box andSC, there may be a column with only two identical nonzero bytes. According to the propagation law of subspaces obtained in Section 3.2, we have(19)Ca,b∩Df⟶EkCi∩Dj,k⟶EkMi∩Cj,k⟶EkWi∩Mj,k⟶EkWj,k.
For example,(20)x000000000y00000⟶Ekx000y00000000000⟶Ek0y0yxy00xy00x000,⟶Ekx1x2⊕x3x4⊕x5x6x1x2x4x60x2⊕x3x4⊕x50x1x3x5x6⟶EkW0,2.Property 5.
When the input difference falls intoDi and there are three active bytes, after 4 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
After the input difference is passed through the whitening key S-box andSC, there may be a column with three identical nonzero bytes and another byte is 0. Ca,b,c∩Di⟶EkCi∩Dj is obtained by Property 2. By Property 3, after 3 more rounds of encryption, each byte of the output difference matrix is active.Property 6.
When the input difference falls intoDi and there are four active bytes, after 3 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
According to the subspace propagation law in Section3.2, it is easy to obtain(21)Di⟶EkCi⟶EkMi⟶EkWi.
From the above four properties, the following conclusions can be drawn.Lemma 10.
When the initial input difference only has active bytes onDi, after 4 rounds of the Midori-64 encryption algorithm, each byte of the output difference is active.Lemma 11.
Suppose that the initial input stateA is only differentially active in Di. If after n rounds of the Midori-64 algorithm, every byte of the output state B is differentially active, then state A′ is obtained by arbitrarily increasing the active difference in A, and every byte difference in the output state B′ after n rounds of the Midori algorithm must be active.Proof.
By the properties ofSB, SC, KeyAdd, and MC, these four transformations between the four diagonal spaces of any state are independent of each other. Therefore, after the transformation of A′, the set of bit blocks with active differences in the output state must contain the set of bit blocks with active differences in the output state of A. Therefore, the conclusion is obvious.
Combining Lemmas10 and 11, the following theorem can be obtained.Theorem 2.
After 4 rounds of the Midori-64 encryption algorithm, each bit block of the output differential matrix of any input differential matrix may be active.


### 5.2. The Longest Subspace Trail of the Midori-64 Decryption Algorithm

Note that the subspace trail in the decryption direction of Midori-64Ci has no predecessor, and no subspace becomes Ci with probability 1 after one round of decryption; that is, when Ci is selected as the starting subspace, the subspace trail formed is the longest. Therefore, to prove this lemma, we discuss the four cases with 1 active byte, 2 active bytes, 3 active bytes, and 4 active bytes in the initial input differential space Ci.Property 7.
When the input difference falls intoCi and there is only one active byte, after 3 rounds of Midori-64 decryption, every byte of the output difference is active.Proof.
Since there is only one active byte, we may also assume that the difference falls intoCj∩Di; then, the subspace propagation law obtained in Section 3.2 yields(22)Ci∩Dj⟶Ek−1Di∩R¯j=Lemma3.5Di∩Ca,b,c⟶Ek−1R¯i∩Da,b,c⟶Ek−1SR−1Wi∩R¯a,b,c,where SC−14i+tmod4=τj, a,b,c,⌊SC−14i+t/4⌋=0,1,2,3.
For example,(23)x′′′000000000000000⟶Ek−100000x′′0000y′′0000z′′⟶Ek−10000x10x6x8x2x40x9x3x5x70⟶Ek−1????1??111??1?1?.Property 8.
When the input difference falls intoCi and there are two active bytes, after 4 rounds of Midori-64 decryption, each byte of the output difference is active.Proof.
When the input difference is passed through the whitening key S-box andSC, there may be a column with only two identical nonzero bytes. According to the propagation law of subspaces obtained in Section 3.2, we have(24)Ca,b∩Df⟶Ek−1Di∩Cj,k⟶Ek−1R¯i∩Dj,k⟶Ek−1SR−1Wi∩Mj,k⟶Ek−1Full.
For example,(25)x′′000y′′00000000000⟶Ek−1x′00000y′000000000⟶Ek−100000xq00py0w00z⟶AK−1MC−1wx⊕py⊕qzwxyzwpqz0x⊕py⊕q0⟶S−1SR−1??0????????????0⟶Ek−1Full.Property 9.
When the input difference falls intoCi and there are three active bytes, after 4 rounds of Midori-64 decryption, each byte of the output difference is active.Proof.
After the input difference is passed through the whitening key S-box andSC, there may be a column with three identical nonzero bytes, and another byte is 0. Da,b,c∩Ci⟶Ek−1Cj∩Di is obtained by Property 2. By property 8, after 3 rounds of decryption, each byte of the output difference matrix is active.Property 10.
When the input difference falls intoCi and there are four active bytes, after 3 rounds of Midori-64 decryption, each byte of the output difference is active.
Proof. According to the subspace propagation law in Section3.2, it is easy to obtain(26)Ci⟶Ek−1Di⟶Ek−1R¯i⟶Ek−1SR−1Wi.
From the above four properties, the following conclusions can be drawn.Lemma 12.
When the initial input difference only has active bytes onCi, after 4 rounds of the Midori-64 decryption algorithm, each byte of the output difference is active.Combining Lemmas11 and 12, the following theorem can be obtained.Theorem 3.
After 4 rounds of Midori decryption, each bit block of any difference matrix may be active.From the above discussion, after 4 rounds of Midori-64 decryption, any subspace becomes a matrix with active bytes in all positions. Therefore, there is no 8-round subspace trail-based impossible differential distinguisher of Midori-64, and it is at most 7 rounds.Of course, an 8-round subspace trail-based impossible differential distinguisher can consist of not only 4 rounds of encryption and 4 rounds of decryption but also 4.5 rounds of encryption (decryption) and 3.5 rounds of decryption (encryption). However, since a state may have differential activity in each byte, the state can be encrypted or decrypted by the Midori-64 algorithm in one round. This output state must not have any definite differentially active or differentially inactive bytes so that it cannot constitute a subspace trail-based impossible differential path. Therefore, it is sufficient to prove that every byte of the output state of any initial differential state after 4 rounds of Midori encryption or Midori decryption is likely to be active.Theorem 4.
The subspace trail-based impossible differential distinguisher of Midori-64 is at most 7 rounds.Thus, by giving that the longest subspace trail of Midori-64 encryption and decryption are 4 rounds, we prove that the subspace trail-based impossible differential distinguisher of Midori-64 is at most 7 rounds. According to Properties4 to 10, it is easy to find that the 7-round subspace trail-based impossible differential distinguisher of Midori-64 can be constructed by using the contradiction between the corresponding bytes 0 and nonzero in the two state matrices.


## 5.1. The Longest Subspace Trail of the Midori-64 Encryption Algorithm

Note that the subspace trail in the encryption direction of Midori-64,Di has no predecessor, and no subspace becomes Di with probability 1 after one round of encryption, that is, when Di is selected as the starting subspace, the subspace trail formed is the longest. Therefore, to prove this lemma, we discuss the four cases with 1 active byte, 2 active bytes, 3 active bytes, and 4 active bytes in the initial input differential space Di.Property 3.
When the input difference falls intoDi and there is only one active byte, after 3 rounds of Midori-64 encryption, every byte of the output difference is active.Proof.
Since there is only one active byte, we may also assume that the difference falls intoCj∩Di; then, the subspace propagation law obtained in Section 3.2 yields(16)Cj∩Di⟶EkCi∩Dk,l,m⟶EkMi∩Ck,l,m⟶EkWi∩Mk,l,m,where j,k,l,m=1,2,3,4.
For example,(17)x000000000000000⟶Ek0000x000y000z000⟶Ek0xzy0x0y0xz000zy⟶Ekx1⊕x2⊕x3x4⊕x5x6⊕x7x8⊕x9x2⊕x3x5x6⊕x7x9x1⊕x3x4x7x8⊕x9x1⊕x2x4⊕x5x6x8.
Note thatxi,i=1,…,9, must be nonzero, so the resulting subspace can be written as follows:(18)?????1?1?11???11.
Among the above symbols, “?” means that the difference byte could be 0 or nonzero and “1″ means that the byte must not be 0.Property 4.
When the input difference falls intoDi and there are two active bytes, after 4 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
When the input difference is passed through the whitening key S-box andSC, there may be a column with only two identical nonzero bytes. According to the propagation law of subspaces obtained in Section 3.2, we have(19)Ca,b∩Df⟶EkCi∩Dj,k⟶EkMi∩Cj,k⟶EkWi∩Mj,k⟶EkWj,k.
For example,(20)x000000000y00000⟶Ekx000y00000000000⟶Ek0y0yxy00xy00x000,⟶Ekx1x2⊕x3x4⊕x5x6x1x2x4x60x2⊕x3x4⊕x50x1x3x5x6⟶EkW0,2.Property 5.
When the input difference falls intoDi and there are three active bytes, after 4 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
After the input difference is passed through the whitening key S-box andSC, there may be a column with three identical nonzero bytes and another byte is 0. Ca,b,c∩Di⟶EkCi∩Dj is obtained by Property 2. By Property 3, after 3 more rounds of encryption, each byte of the output difference matrix is active.Property 6.
When the input difference falls intoDi and there are four active bytes, after 3 rounds of Midori-64 encryption, each byte of the output difference is active.Proof.
According to the subspace propagation law in Section3.2, it is easy to obtain(21)Di⟶EkCi⟶EkMi⟶EkWi.
From the above four properties, the following conclusions can be drawn.Lemma 10.
When the initial input difference only has active bytes onDi, after 4 rounds of the Midori-64 encryption algorithm, each byte of the output difference is active.Lemma 11.
Suppose that the initial input stateA is only differentially active in Di. If after n rounds of the Midori-64 algorithm, every byte of the output state B is differentially active, then state A′ is obtained by arbitrarily increasing the active difference in A, and every byte difference in the output state B′ after n rounds of the Midori algorithm must be active.Proof.
By the properties ofSB, SC, KeyAdd, and MC, these four transformations between the four diagonal spaces of any state are independent of each other. Therefore, after the transformation of A′, the set of bit blocks with active differences in the output state must contain the set of bit blocks with active differences in the output state of A. Therefore, the conclusion is obvious.
Combining Lemmas10 and 11, the following theorem can be obtained.Theorem 2.
After 4 rounds of the Midori-64 encryption algorithm, each bit block of the output differential matrix of any input differential matrix may be active.


## 5.2. The Longest Subspace Trail of the Midori-64 Decryption Algorithm

Note that the subspace trail in the decryption direction of Midori-64Ci has no predecessor, and no subspace becomes Ci with probability 1 after one round of decryption; that is, when Ci is selected as the starting subspace, the subspace trail formed is the longest. Therefore, to prove this lemma, we discuss the four cases with 1 active byte, 2 active bytes, 3 active bytes, and 4 active bytes in the initial input differential space Ci.Property 7.
When the input difference falls intoCi and there is only one active byte, after 3 rounds of Midori-64 decryption, every byte of the output difference is active.Proof.
Since there is only one active byte, we may also assume that the difference falls intoCj∩Di; then, the subspace propagation law obtained in Section 3.2 yields(22)Ci∩Dj⟶Ek−1Di∩R¯j=Lemma3.5Di∩Ca,b,c⟶Ek−1R¯i∩Da,b,c⟶Ek−1SR−1Wi∩R¯a,b,c,where SC−14i+tmod4=τj, a,b,c,⌊SC−14i+t/4⌋=0,1,2,3.
For example,(23)x′′′000000000000000⟶Ek−100000x′′0000y′′0000z′′⟶Ek−10000x10x6x8x2x40x9x3x5x70⟶Ek−1????1??111??1?1?.Property 8.
When the input difference falls intoCi and there are two active bytes, after 4 rounds of Midori-64 decryption, each byte of the output difference is active.Proof.
When the input difference is passed through the whitening key S-box andSC, there may be a column with only two identical nonzero bytes. According to the propagation law of subspaces obtained in Section 3.2, we have(24)Ca,b∩Df⟶Ek−1Di∩Cj,k⟶Ek−1R¯i∩Dj,k⟶Ek−1SR−1Wi∩Mj,k⟶Ek−1Full.
For example,(25)x′′000y′′00000000000⟶Ek−1x′00000y′000000000⟶Ek−100000xq00py0w00z⟶AK−1MC−1wx⊕py⊕qzwxyzwpqz0x⊕py⊕q0⟶S−1SR−1??0????????????0⟶Ek−1Full.Property 9.
When the input difference falls intoCi and there are three active bytes, after 4 rounds of Midori-64 decryption, each byte of the output difference is active.Proof.
After the input difference is passed through the whitening key S-box andSC, there may be a column with three identical nonzero bytes, and another byte is 0. Da,b,c∩Ci⟶Ek−1Cj∩Di is obtained by Property 2. By property 8, after 3 rounds of decryption, each byte of the output difference matrix is active.Property 10.
When the input difference falls intoCi and there are four active bytes, after 3 rounds of Midori-64 decryption, each byte of the output difference is active.
Proof. According to the subspace propagation law in Section3.2, it is easy to obtain(26)Ci⟶Ek−1Di⟶Ek−1R¯i⟶Ek−1SR−1Wi.
From the above four properties, the following conclusions can be drawn.Lemma 12.
When the initial input difference only has active bytes onCi, after 4 rounds of the Midori-64 decryption algorithm, each byte of the output difference is active.Combining Lemmas11 and 12, the following theorem can be obtained.Theorem 3.
After 4 rounds of Midori decryption, each bit block of any difference matrix may be active.From the above discussion, after 4 rounds of Midori-64 decryption, any subspace becomes a matrix with active bytes in all positions. Therefore, there is no 8-round subspace trail-based impossible differential distinguisher of Midori-64, and it is at most 7 rounds.Of course, an 8-round subspace trail-based impossible differential distinguisher can consist of not only 4 rounds of encryption and 4 rounds of decryption but also 4.5 rounds of encryption (decryption) and 3.5 rounds of decryption (encryption). However, since a state may have differential activity in each byte, the state can be encrypted or decrypted by the Midori-64 algorithm in one round. This output state must not have any definite differentially active or differentially inactive bytes so that it cannot constitute a subspace trail-based impossible differential path. Therefore, it is sufficient to prove that every byte of the output state of any initial differential state after 4 rounds of Midori encryption or Midori decryption is likely to be active.Theorem 4.
The subspace trail-based impossible differential distinguisher of Midori-64 is at most 7 rounds.Thus, by giving that the longest subspace trail of Midori-64 encryption and decryption are 4 rounds, we prove that the subspace trail-based impossible differential distinguisher of Midori-64 is at most 7 rounds. According to Properties4 to 10, it is easy to find that the 7-round subspace trail-based impossible differential distinguisher of Midori-64 can be constructed by using the contradiction between the corresponding bytes 0 and nonzero in the two state matrices.


## 6. The Classification of Space Trail-Based Impossible Differential Distinguisher of 7-Round Midori-64

In this section, based on the properties and theorems obtained above and based on the Hamming weights of the starting and ending states, we classify all seven-round space trail-based impossibility differential distinguishers.According to Properties3 to 10 proved in Section 5, when the number of active bytes in the subspace is 1 or 4, the bytes determined to be 0 cannot be obtained within 3 or 4 rounds of encryption (deencryption), and the contradiction between the zero and nonzero bytes at the same position cannot be used to construct an impossible differential distinguisher. Therefore, the Hamming weights of the starting and ending subspaces can only be 2 and 3, respectively.Two types of 7-round subspace trail-based impossible differential distinguishers can be constructed, which are classified based on the Hamming weights of the starting and ending difference matrices, and the two impossible differences are encrypted in 4 rounds/decrypted in 3 rounds and encrypted 3 rounds/decrypted 4 rounds.First, from Properties5 and 8, the first class of subspace trail-based impossible distinguishers can be constructed; the starting subspace’s Hamming weight is 3 and the ending subspace’s Hamming weight is 2:(27)Ca,b,c∩Dj⟶Ek−1Cj∩Di⟶Ek−1Ci∩Dk,l,m⟶Ek−1Mi∩Ck,l,m⟶Ek−1Wi∩Mk,l,m=impossibleSCDMt,u∩Ws←Ek−1Dt,u∩R¯s←Ek−1Ct,u∩Ds←Ek−1Cs∩Dd,e.According to Properties4 and 9, we construct the second type of subspace trail-based impossible differential distinguisher; the starting subspace’s Hamming weight is 2 and the ending subspace’s Hamming weight is 3:(28)Ca,b∩Df⟶Ek−1Ci∩Dj,k⟶Ek−1Mi∩Cj,k⟶Ek−1Wi∩Mj,k=impossibleSCDMd,e,f∩Ws←Ek−1R¯s∩Dd,e,f←Ek−1Ds∩R¯g←Ek−1Cs∩Dg←Ek−1Cs∩Dd,e,f.The data and computational complexities of the two types of distinguishers are given below.


### 6.1. The First Type of 7-Round Midori-64 Subspace Trail-Based Impossible Differential Distinguisher

We take the following seven-round impossible difference as an example:(29)C0,1,2∩D0⟶EkC0∩D0⟶EkC0∩D1,2,3⟶EkM0∩C1,2,3⟶EkW0∩M1,2,3=impossibleSCDM0,2∩W0←Ek−1D0,2∩R¯0←Ek−1C0,2∩D0←Ek−1C0∩D0,1.The construction of the distinguisher is the same as that in the previous 6 rounds of key recovery attacks. The definition of the setVδ,μ is the same as before. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Cs∩Dd,e,f after 7 rounds of encryption is 4×A42×28/264=2−51.4. Therefore, given n pairs, a pair fixed δ=k5⊕k10 and μ=k5⊕k15, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Cs∩Dd,e is p=1−e−n/251.4. If n=254.6 (approximately 256.6 pairs), the probability p is greater than 99.98 % (actually, 0.9998256≈0.95). Therefore, for the adversary, approximately, 254.6·2−7=247.6 different sets Vδ,μ are needed.The idea is to consider247.6 different sets Vδ,μ with a total of 24·247.6·28=259.6 chosen plaintexts. From Proposition 1, there is a set δ, μ such that the set does not collide after 7 rounds of Midori-64 encryption; that is, for Midori-64 and δ=k5⊕k10 and μ=k5⊕k15, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ and c1,c2∈Cs∩Dd,e. In this way, 7 rounds’ Midori-64 can be distinguished from the random function, that is, there are 28 collections (each group of δ and μ constitute a collection), and each collection has 247.6 different sets Vδ. In random permutation, there is a 95 % probability that at least one collision is obtained in each of the 256 collections. Note that the average number of collisions for each collection should be 2−51.4·254.6=23.2≃9. For the Midori-64 cypher, it is expected that there is one pair of δ, μ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The amount of data is 259.6 choice plaintexts, and the computational complexity is 251.6·27.6=259.2.


### 6.2. The Second Type of 7-Round Midori-64 Subspace Trail-Based Impossible Differential Distinguisher

To construct the second type of seven-round subspace trail-based impossible differential distinguisher, we give the following proposition.Proposition 3.
p1 and p2 are two plaintexts. When i≠0,10, pi1=pi2 and p01⊕p101=p02⊕p102. If p01⊕p101=p02⊕p102=k0⊕k10 (k is the whitening key), then, after one round of encryption, they belong to the same coset of C0∩D0,1, namely, Rp1⊕Rp2∈C0∩D0,1.Note that the information of the S-box is not used in the proof process; only the mixture matrix is required (each column has two identical elements), so the general form of Proposition3 can be given.Proposition 4.
p1 and p2 are two plaintexts, p1,p2∈Dj. When i≠SR−14j+t,t=a,b, and pi1=pi2. pSR−14j+a1⊕pSR−14j+b1=pSR−14j+a2⊕pSR−14j+b2. If pSR−14j+a1⊕pSR−14j+b1=pSR−14j+a2⊕pSR−14j+b2=kSR−14j+a⊕kSR−14j+b (k is the whitening key), after one round of encryption, they belong to the same coset of Cj∩Dc,d, that is, Rp1⊕Rp2∈Cj∩Dc,d, a,b,c,d=0,1,2,3.Similar to Section4.2, after having Proposition 4, we can give the second type of seven-round Midori-64 subspace trail-based impossible differential distinguisher. First, we define a plaintext-ciphertext set Vδ, Vδ=24:(30)Vδ=pi,cifori=0,…,24−1|p0i⊕p10i=δ,∀ipki=pkj,∀k≠0,10,i≠j.That is, the plaintext has 14 constants, and the other two fixed bytes have differences.The definition of setVδ is the same as before, a total of 24 pairs δ. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Cs∩Dd,e after 7 rounds of encryption is 4×A43×212/264=2−48. Therefore, given n pairs, a fixed δ=k0⊕k10, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Cs∩Dd,e,f is p=1−e−n/248. If n=250.4, the probability p is greater than 99.55% 0.99516≈0.923. Therefore, for the adversary, approximately, 250.4·2−7=243.4 different sets Vδ are needed.The idea is to consider243.4 different sets Vδ with a total of 24·243.4·24=251.4 chosen plaintexts. From Proposition 1, there is a set δ and μ such that the set does not collide after 7 rounds of Midori-64 encryption; that is, for Midori-64 and δ=k0⊕k10, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ. In this way, 7 rounds Midori-64 can be distinguished from the random function; that is, there are 28 collections (each δ constitutes a collection), and each collection has 247.4 different sets Vδ. In random permutation, there is a 92.3 % probability that at least one collision is obtained in each collection. Note that the average number of collisions for each collection should be 2−48·250.4=22.4≃5.3. For the Midori-64 cypher, it is expected that there is a δ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The amount of data is 251.4 choice plaintexts, and the computational complexity is 243.4·27.6=251.Li MM et al. proved that Midori-64’s truncated impossible differential distinguisher contains at most 6 rounds in the article “Truncation Impossible Difference Analysis of Midori-64 Algorithm” [18]. We construct a subspace trail-based impossible differential distinguisher for 7-round Midori-64, indicating that the subspace trail has advantages in combination with other analysis methods and can increase the number of rounds of the distinguisher.


## 6.1. The First Type of 7-Round Midori-64 Subspace Trail-Based Impossible Differential Distinguisher

We take the following seven-round impossible difference as an example:(29)C0,1,2∩D0⟶EkC0∩D0⟶EkC0∩D1,2,3⟶EkM0∩C1,2,3⟶EkW0∩M1,2,3=impossibleSCDM0,2∩W0←Ek−1D0,2∩R¯0←Ek−1C0,2∩D0←Ek−1C0∩D0,1.The construction of the distinguisher is the same as that in the previous 6 rounds of key recovery attacks. The definition of the setVδ,μ is the same as before. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Cs∩Dd,e,f after 7 rounds of encryption is 4×A42×28/264=2−51.4. Therefore, given n pairs, a pair fixed δ=k5⊕k10 and μ=k5⊕k15, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Cs∩Dd,e is p=1−e−n/251.4. If n=254.6 (approximately 256.6 pairs), the probability p is greater than 99.98 % (actually, 0.9998256≈0.95). Therefore, for the adversary, approximately, 254.6·2−7=247.6 different sets Vδ,μ are needed.The idea is to consider247.6 different sets Vδ,μ with a total of 24·247.6·28=259.6 chosen plaintexts. From Proposition 1, there is a set δ, μ such that the set does not collide after 7 rounds of Midori-64 encryption; that is, for Midori-64 and δ=k5⊕k10 and μ=k5⊕k15, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ and c1,c2∈Cs∩Dd,e. In this way, 7 rounds’ Midori-64 can be distinguished from the random function, that is, there are 28 collections (each group of δ and μ constitute a collection), and each collection has 247.6 different sets Vδ. In random permutation, there is a 95 % probability that at least one collision is obtained in each of the 256 collections. Note that the average number of collisions for each collection should be 2−51.4·254.6=23.2≃9. For the Midori-64 cypher, it is expected that there is one pair of δ, μ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The amount of data is 259.6 choice plaintexts, and the computational complexity is 251.6·27.6=259.2.


## 6.2. The Second Type of 7-Round Midori-64 Subspace Trail-Based Impossible Differential Distinguisher

To construct the second type of seven-round subspace trail-based impossible differential distinguisher, we give the following proposition.Proposition 3.
p1 and p2 are two plaintexts. When i≠0,10, pi1=pi2 and p01⊕p101=p02⊕p102. If p01⊕p101=p02⊕p102=k0⊕k10 (k is the whitening key), then, after one round of encryption, they belong to the same coset of C0∩D0,1, namely, Rp1⊕Rp2∈C0∩D0,1.Note that the information of the S-box is not used in the proof process; only the mixture matrix is required (each column has two identical elements), so the general form of Proposition3 can be given.Proposition 4.
p1 and p2 are two plaintexts, p1,p2∈Dj. When i≠SR−14j+t,t=a,b, and pi1=pi2. pSR−14j+a1⊕pSR−14j+b1=pSR−14j+a2⊕pSR−14j+b2. If pSR−14j+a1⊕pSR−14j+b1=pSR−14j+a2⊕pSR−14j+b2=kSR−14j+a⊕kSR−14j+b (k is the whitening key), after one round of encryption, they belong to the same coset of Cj∩Dc,d, that is, Rp1⊕Rp2∈Cj∩Dc,d, a,b,c,d=0,1,2,3.Similar to Section4.2, after having Proposition 4, we can give the second type of seven-round Midori-64 subspace trail-based impossible differential distinguisher. First, we define a plaintext-ciphertext set Vδ, Vδ=24:(30)Vδ=pi,cifori=0,…,24−1|p0i⊕p10i=δ,∀ipki=pkj,∀k≠0,10,i≠j.That is, the plaintext has 14 constants, and the other two fixed bytes have differences.The definition of setVδ is the same as before, a total of 24 pairs δ. When the guessed key is wrong, the probability of two plaintexts falling into the subspace Cs∩Dd,e after 7 rounds of encryption is 4×A43×212/264=2−48. Therefore, given n pairs, a fixed δ=k0⊕k10, according to the birthday paradox (formula (13)), the probability of obtaining at least one collision in the same coset of Cs∩Dd,e,f is p=1−e−n/248. If n=250.4, the probability p is greater than 99.55% 0.99516≈0.923. Therefore, for the adversary, approximately, 250.4·2−7=243.4 different sets Vδ are needed.The idea is to consider243.4 different sets Vδ with a total of 24·243.4·24=251.4 chosen plaintexts. From Proposition 1, there is a set δ and μ such that the set does not collide after 7 rounds of Midori-64 encryption; that is, for Midori-64 and δ=k0⊕k10, no p1,c1 or p2,c2 satisfies p1,p2∈Vδ,μ. In this way, 7 rounds Midori-64 can be distinguished from the random function; that is, there are 28 collections (each δ constitutes a collection), and each collection has 247.4 different sets Vδ. In random permutation, there is a 92.3 % probability that at least one collision is obtained in each collection. Note that the average number of collisions for each collection should be 2−48·250.4=22.4≃5.3. For the Midori-64 cypher, it is expected that there is a δ, and there is no such collision in the corresponding collection with probability 1, so the result is distinguished from the random function. The amount of data is 251.4 choice plaintexts, and the computational complexity is 243.4·27.6=251.Li MM et al. proved that Midori-64’s truncated impossible differential distinguisher contains at most 6 rounds in the article “Truncation Impossible Difference Analysis of Midori-64 Algorithm” [18]. We construct a subspace trail-based impossible differential distinguisher for 7-round Midori-64, indicating that the subspace trail has advantages in combination with other analysis methods and can increase the number of rounds of the distinguisher.


## 7. Summary

In this paper, we present a special 6-round subspace trail-based impossible differential key recovery attack on Midori-64 by using the subspace trail analysis method, and the corresponding distinguisher, which has a greater distinguishing ability than the truncated impossible differential distinguisher, is given. After that, the longest subspace trails of Midori-64 encryption and decryption are given, and it is shown that there is no subspace trail-based impossible differential distinguisher with 8 rounds or more. Finally, the classification of all 7-round subspace trail-based impossible differential distinguishers of Midori-64 is given based on the Hamming weight of the starting and ending subspaces and the data complexity and computational complexity of the two types of distinguishers.Three open questions: is it possible to construct a new distinguisher for Midori-128 based on the impossible differential distinguisher of 6- and 7-round space trails of Midori-64? How can we find distinguishers with 6 or more rounds for cryptographic algorithms whose number of linear layer branches is four (e.g., the Midori series) and perform mixture differential cryptanalysis? Can we find a theoretical relationship between the number of linear layer branches and the length of the corresponding subspace trail? These are the goals of our next study.



---

*Source: 6269604-2021-11-09.xml*