# Multiple Impossible Differential Attacks for ForkAES

Authors: Zilong Jiang; Chenhui Jin
Journal: Security and Communication Networks
 (2022)

---

## Abstract

To yield a highly efficient authentication encryption design for very short messages, the tweakable forkcipher is proposed, which is a tweakable block cipher that uses forking construction to produce two output blocks. The designers also presented ForkAES, a forkcipher that is based on the round function of AES and the tweakable variant of KIASU. Therefore, the security of ForkAES is found on the block ciphers AES and KIASU. However, from the perspective of new forking construction, attackers may obtain some unique properties. Impossible differential attacks are widely used on block ciphers. This paper studies the security of ForkAES against multiple impossible differential cryptanalysis. Based on the property of the forking construction, two types of impossible differential distinguishers have been constructed. We first use the tweak with different truncated differences to build more attack trails. Then, we first propose the multiple impossible differential attack for ForkAES-∗ -5-4. Thus, only a single round would remain as a security margin. Utilizing multiple attack trails, our attack scenario obtains more subkey bytes and enhances the subkey’s sieving efficiency without increasing complexity. Furthermore, we carefully consider the process of recovering the master key, which can efficiently reject wrong candidate keys. In reconstruction queries, our attack reaches the longest number of rounds for ForkAES in impossible differential analysis, with 2100.8 lookups, 285.8 chosen ciphertexts, and 292.7 memory blocks to store AES states. In encryption queries, we improve the previous attacks on ForkAES by attacking one more round (i.e., ForkAES- ∗ -5-4), with 2118.2 lookups, 2111.4 plaintexts, and 292.7 memory blocks to store AES states.


---

## Body

## 1. Introduction

Many authenticated encryption (AE) schemes need to perform the initialization or finalization phase to optimize the cost of handling long messages. However, in these general schemes, initialization or finalization raises the cost of handling short messages. For example, the TLS needs to produce a message authentication code (MAC) in the initialization phase. An efficient AE scheme for very short messages is an actively discussed topic. To yield a highly efficient AE design for very short messages, Andreeva et al. [1] proposed a tweakable forkcipher [1], which utilizes the forking construction to produce two output blocks from the same input. Compared with the TLS, the expanded ciphertexts of the forkcipher can also serve as the MAC, so there is no need to perform initialization to produce the MAC. Furthermore, the forking construction shares some computations, so the forkcipher is a highly efficient AE design for very short messages. Andreeva et al. [1] also proposed a forkcipher named ForkAES. Balli and Banik [2] analysed the hardware performance of ForkAES. They achieve a hardware implementation of ForkAES without any additional storage cost if the AES circuit can also perform decryption, thereby further optimizing the storage cost.ForkAES is based on the round function AES [3] and the tweakable variant KIASU [4]. Andreeva et al. [1] briefly considered differential attacks, related-tweakey attacks, and meet-in-the-middle attacks. For other attacks, these authors stated that “the security of our forkcipher design can be reduced to the security of the AES and KIASU ciphers for further types of attacks.” However, from the perspective of the new forking construction, attackers may obtain some unique properties. Reconstruction queries mean that attackers can choose one block ciphertext and obtain the other block ciphertext by reconstruction querying. Encryption queries mean that attackers obtain the two block ciphertexts by encryption querying the plaintext. Banik et al. [5] introduced reflection differential trails and proposed some attacks of ForkAES- ∗ -4-4 (∗ is any nonnegative integer). Bariant et al. [6] first presented truncated differential attacks on ForkAES- ∗ -5-5 (full ten rounds) in reconstruction queries, but the security of ForkAES in encryption queries needs to be further studied.Impossible differential attack [7, 8] is a very powerful and important method of attacking block ciphers. For a long time, impossible differential attacks were among the most successful attacks for AES [9], KIASU [10] and Deoxys [11]. Tsunoo et al. [12] proposed the idea of multiple impossible differentials. Li et al. [13, 14] proposed the subkey early abort, and Boura et al. [15, 16] presented the state-test technique; using these techniques, these authors presented their successful attacks against classical block ciphers, such as Fox and AES.This paper studies the security of ForkAES against multiple impossible differential cryptanalysis. Based on the property of the forking construction, two types of impossible differential distinguishers have been constructed. We first use the tweak with different truncated differences to construct more attack trails. Then, we propose the multiple impossible differential attack for ForkAES-∗ -5-4. Utilizing multiple attack trails, our attack scenario obtains more subkey bytes and enhances the sieving efficiency of subkeys without increasing complexity. Furthermore, one of the impossible differential attacks needs to guess only five subkey bytes in paper [5], and the authors did not analyse the process of recovering the master key. Because the subkey bytes may not suffice, the cost of recovering the master key may be more than that of attacking subkey bytes. Compared with paper [5], we carefully consider the process of recovering the master key, which can reject wrong candidate keys efficiently. Compared with paper [6], we consider the attack scenario in encryption queries, which increases the understanding of ForkAES. To the best of our knowledge, we improve the previous attacks on ForkAES by attacking one more round in encryption queries. Table 1 summarizes some attacks of ForkAES.Table 1
The comparison of attacks on ForkAES.
Attack typeRoundsTimeDataMemoryReferenceEncs.MAsReconstruction queriesRectangle diff.ForkAES-∗ -4-4228235235233[5]Impossible diff.ForkAES-∗ -4-4247247239.4235[5]YoyoForkAES-∗ -3-3214.5229214.5229[5]Imp.-diff. YoyoForkAES-∗ -4-42128.83−2122.83O1[5]Impossible diffmkForkAES-∗ -5-427.22100.8285.8292.7This paperTruncated diff.ForkAES-∗ -5-52125−2119283[6]Encryption queriesRectangleForkAES-∗ -4-4288.5292.4285286.4[5]Impossible diff.ForkAES-∗ -4-4275.42110.2270.22110[5]Impossible diffmkForkAES-∗ -5-427.22118.22111.4292.7This papermk: recover the master key; MAs: memory accesses.This paper is organized as follows: in Section2, we describe the ForkAES structure and some basic concepts. In Section 3, we construct six impossible differential distinguishers of ForkAES. In Section 4, we propose multiple impossible differential attacks on ForkAES- ∗ -5-4 and analyse our attack. Finally, Section 5 concludes this paper.


## 2. Preliminaries

### 2.1. Notations

We will introduce some basic notations used throughout this paper:P/C/T: Plaintext/Ciphertext/Tweak;xi,p,…,rSB/SR/MCAK/AT: the intermediate state of the pth,…,rth bytes after SB/SR/MC/AK/AT in the i-th round;Δx: the difference between x and x′;ki,p,…,r: the pth,…,rth bytes of subkey ki;Ti: the ith byte of tweak T;a⟶i−roundb: the difference a cannot obtain the difference b through i round encryptions.


### 2.2. Brief Description of Impossible Differential Attack

To mount an impossible differential attack, the block cipherE is divided into three parts: E=E3°E2°E1 (as shown in Figure 1). First, an impossible differential distinguisher ΔIDin↛ΔIDout through E2 is constructed. Then, for the extra added rounds E1 and E3, the differential ΔIDin⟶ΔPin through E1−1 and ΔIDout⟶ΔCout through E3 occur with probability 1. The combination of the differential ΔIDin⟶ΔPin and ΔIDout⟶ΔCout is called an attack trail.Figure 1
General structure of an impossible differential attack.


### 2.3. Brief Description of ForkAES

ForkAES-rt-ra-rb means that the internal state is obtained after rt rounds from plaintext; then, ra and rb denote the number of rounds from internal state to ciphertext C0 and from internal state to ciphertext C1, respectively. As shown in Figure 2, the original ForkAES is ForkAES-5-5-5. ForkAES encrypts the plaintext over the first five rounds to produce the internal state, and then the internal state is forked to produce two ciphertexts C0 and C1. We denote the internal state as S5. The input state of the first branch is x5=S5, and the output of the first branch is x10=C0. Similarly, the input state of the second branch is y5=S5, and the output of the first branch is y10=C1.Figure 2
Illustration of ForkAES.The block size of ForkAES is 128 bits. As shown in Figure3, the round function of ForkAES is similar to that of KIASU, which applies five operations as follows:(1)
SubBytesSBThis operation applies an 8-bit invertible S-box of AES on 16 bytes of the state.(2)
ShiftRowsSRThe cyclic shift of each row is the same as AES.(3)
MixColumnsMCThe multiplication of each column by the 4- × -4-cell MDS matrix of AES.(4)
AddRoundTweakeyAKThis operation XORs with the round subkeys derived from the master key.(5)
AddRoundTweakeyATThis operation XORs with a tweak.Figure 3
The round function of ForkAES.In this paper,k0 represents the whitening key. SB−1, SR−1, MC−1, AK−1, and AT−1 represent the inverse operations of SB, SR, MC, AK, and AT, respectively. For more details on ForkAES, we can refer to the paper [1].


## 2.1. Notations

We will introduce some basic notations used throughout this paper:P/C/T: Plaintext/Ciphertext/Tweak;xi,p,…,rSB/SR/MCAK/AT: the intermediate state of the pth,…,rth bytes after SB/SR/MC/AK/AT in the i-th round;Δx: the difference between x and x′;ki,p,…,r: the pth,…,rth bytes of subkey ki;Ti: the ith byte of tweak T;a⟶i−roundb: the difference a cannot obtain the difference b through i round encryptions.


## 2.2. Brief Description of Impossible Differential Attack

To mount an impossible differential attack, the block cipherE is divided into three parts: E=E3°E2°E1 (as shown in Figure 1). First, an impossible differential distinguisher ΔIDin↛ΔIDout through E2 is constructed. Then, for the extra added rounds E1 and E3, the differential ΔIDin⟶ΔPin through E1−1 and ΔIDout⟶ΔCout through E3 occur with probability 1. The combination of the differential ΔIDin⟶ΔPin and ΔIDout⟶ΔCout is called an attack trail.Figure 1
General structure of an impossible differential attack.


## 2.3. Brief Description of ForkAES

ForkAES-rt-ra-rb means that the internal state is obtained after rt rounds from plaintext; then, ra and rb denote the number of rounds from internal state to ciphertext C0 and from internal state to ciphertext C1, respectively. As shown in Figure 2, the original ForkAES is ForkAES-5-5-5. ForkAES encrypts the plaintext over the first five rounds to produce the internal state, and then the internal state is forked to produce two ciphertexts C0 and C1. We denote the internal state as S5. The input state of the first branch is x5=S5, and the output of the first branch is x10=C0. Similarly, the input state of the second branch is y5=S5, and the output of the first branch is y10=C1.Figure 2
Illustration of ForkAES.The block size of ForkAES is 128 bits. As shown in Figure3, the round function of ForkAES is similar to that of KIASU, which applies five operations as follows:(1)
SubBytesSBThis operation applies an 8-bit invertible S-box of AES on 16 bytes of the state.(2)
ShiftRowsSRThe cyclic shift of each row is the same as AES.(3)
MixColumnsMCThe multiplication of each column by the 4- × -4-cell MDS matrix of AES.(4)
AddRoundTweakeyAKThis operation XORs with the round subkeys derived from the master key.(5)
AddRoundTweakeyATThis operation XORs with a tweak.Figure 3
The round function of ForkAES.In this paper,k0 represents the whitening key. SB−1, SR−1, MC−1, AK−1, and AT−1 represent the inverse operations of SB, SR, MC, AK, and AT, respectively. For more details on ForkAES, we can refer to the paper [1].


## 3. The Impossible Differential Distinguishers of ForkAES

The longest impossible differential key-independent distinguisher of AES is four rounds [17]. Utilizing the property of forking construction, we construct six 5-round impossible differential distinguishers of ForkAES.The input difference of distinguisherΔx8SR: in the round function after the subkey k8, the difference is after the SR operation.The output difference of distinguisherΔy5MC: in the round function after the subkey k11, the difference is after the MC operation.The input differenceΔx8SR (in the first branch) is mapped to the internal state difference and then obtains the output difference Δy5MC (in the second branch). The specific impossible differentials of six 5-round distinguishers are shown in Table 2. We construct two types of distinguishers by utilizing the tweak with a distinct truncated difference. The first type of distinguisher uses tweak pairs with only a 1-byte nonzero difference at position (0), and the second type of distinguisher uses tweak pairs with only a 1-byte nonzero difference at position (4). Figure 4 shows the sample of the first distinguisher. As shown in Figure 4, the impossible differential has been constructed in the first branch, and the output difference propagates to the internal state difference with probability 1, so the 5-round impossible differential distinguisher of ForkAES has been constructed.Table 2
Six 5-round truncated impossible differential distinguishers of ForkAES.
TypeNumberZero input differenceNonzero middle state differenceNonzero tweak and output differenceFirst1(3, 6, 9, 12)(0, 5, 10, 15)(0)2(2, 5, 8, 15)3(1, 4, 11, 14)Second4(3, 6, 9, 12)(3, 4, 9, 14)(4)5(2, 5, 8, 15)6(0, 5, 10, 15)Note: the input differenceΔx8SR propagates to the internal state with probability 0 and the output difference Δy5MC propagates to the internal state with probability 1.Figure 4
A sample of 5-round impossible differential distinguishers.Theorem 1.
As shown in Figure4, there is a 5-round truncated impossible differential distinguisher of ForkAES:(1)∗,∗,∗,0,∗,∗,0,∗,∗,0,∗,∗,0,∗,∗,∗⟶5−round∗,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,where ∗ is the nonzero difference. The input difference is Δx8SR, and the output difference is Δy5MC. This distinguisher uses the tweak pairs with only a 1-byte nonzero difference at position (0).Proof.
In the second branch, the output difference isΔy5MC. Through the MC−1, SR−1, and SB−1 operations, the internal state difference can be obtained with probability 1.
In the first branch, the difference of 4 bytesΔx5,0,1,2,3MC can be any value, and the difference of the other 12 bytes of Δx5MC must be zero. Then, through the SB, SR, and MC operations, each column of difference Δx6MC is either fully inactive or fully active (Property 1).
From the differenceΔx8SR, through the SR−1 and SB−1 operations, the rightmost column of Δx7AT is fully inactive, and the other three columns are fully active. Then, through the AT−1 operation, the difference of the byte at position (0) can be any value. Through the MC−1 operation, the rightmost column of Δx7SR is fully inactive, and the other three columns have at least one active byte. Through the SR−1, SB−1, and AT−1 operations, the difference Δx6MC exists in one column with at least one inactive byte and at least one active byte, thus contradicting Property 1.The other five impossible differential distinguishers of ForkAES could be proven similarly.


## 4. Multiple Impossible Differential Attacks on ForkAES-∗ -5-4

Based on the two types of distinguishers in Section3, we construct two attack trails with the same truncated difference of ciphertext C0 pairs. We first propose the multiple impossible differential attack on ForkAES- ∗ -5-4. In consideration of the clear expression, we have rt=5. Our attack scenario can be applied to chosen ciphertext (reconstruction queries) and known plaintext (encryption queries).As shown in Figure5, we append two rounds in the first branch and four rounds in the second branch. We swap the order of the SR, MC, and AK operations of the third and fourth rounds in the second branch, and k^ denotes the equivalent subkey. For the first attack trail, thirteen subkey bytes k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3 need to be guessed. For the second attack trail, thirteen subkey bytes k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 need to be guessed. These two attack trails have common subkey bytes k10,0,1,2,3,4,5,6,7, which can be repeatedly sieved to improve the result.Figure 5
The first attack trail of ForkAES-∗ -5-4.


### 4.1. The Attack with Reconstruction Queries

The attack procedure includes the data-collection phase, precomputation phase, and key-recovery phase. In this section, we use the sieve method based on rapid sorting [18] to choose ciphertext pairs.


#### 4.1.1. Data-Collection Phase

We choose the ciphertextC0 and then obtain the ciphertext C1 by reconstruction queries.For the first attack trail, select28 tweaks that take all possible values in T0 and fix the other 7 bytes to constant values. Select 264 ciphertexts C0 that take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7 and fix the other 8 bytes to constant values. We take 272C0,T0 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,0,1,2,3SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T0,y8,0,1,2,3SB in Table Ω1.For the second attack trail, select28 tweaks that take all possible values in T2 and fix the other 7 bytes to constant values. Select the same 264 ciphertexts C0 in the first trail. These ciphertexts take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7), and fix the other 8 bytes to constant values. We take 272C0,T2 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,4,5,6,7SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T2,y8,4,5,6,7SB in Table Ω2.


#### 4.1.2. Precomputation Phase

TableΛ: let S, Δin, and Δout denote the S-box of ForkAES, the input difference and the output difference of the S-box, respectively. The equation Sx⊕Sx⊕Δin=Δout has one solution on average when the values of the differences Δin and Δout are nonzero. We construct Table Λ to store the calculated value of x, indexed by all 216 values of Δin,Δout.TableH1: for the first branch of the first attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H1 to store 3×232 difference values of Δx8MC.TableH2: for the first branch of the second attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H2 to store 3×232 difference values of Δx8MC.TableH3: for the second branch of the first attack trail, there are 28 difference values by guessing all possible values of Δy7,0SR. Through the MC operation, there are 28 difference values of Δy7,0,1,2,3MC. We construct Table H3 to store these 28 difference values of Δy7,0,1,2,3MC.TableH4: for the second branch of the second attack trail, there are 28 difference values by guessing all possible values of Δy7,4SR. Through the MC operation, there are 28 difference values of Δy7,4,5,6,7MC. We construct Table H3 to store these 28 difference values of Δy7,4,5,6,7MC.


#### 4.1.3. Online Phase

In Steps 1 and 2, combining a series of techniques, use the first attack trail to reject some wrong subkeys. In Steps 3 and 4, use the second attack trail to reject some wrong subkeys for the remaining subkeys, thereby enhancing the efficiency of sieving subkeys. In Step 5, by comprehensively utilizing the subkeys information, use the master key recovering technique to reject wrong candidate keys until the right master key is obtained. We take2n structures, and the specific procedure is as follows:(1)
Use the first attack trail to calculate subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω1 to obtain 2n+47 pairs C0⊕T0,C0′⊕T0'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, access Table H1 to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,0,1,2,3SB,y′ in Table U1 indexed by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(2)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,0,k^14,0,1,2,3. Access Table H3 to obtain 28 input difference Δy7,0,1,2,3MC. Access Table U1 to obtain output difference.Construct TableV1, which has 240 addresses indexed by 5-byte subkeys k^13,0,k^14,0,1,2,3. For each address, set the initial value to 0. Then, set the counter that corresponds to F1 with an initial value of 0. For each pair in Table U1, 28 wrong subkeys k^13,0,k^14,0,1,2,3 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,0,k^14,0,1,2,3 is 0 in Table V1, update the value to 1 and increase the value of F1 by 1. If F1=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong, and discard it. Check all pairs in Table V1; then, if still F1<240, the value at the addresses of subkeys k^13,0,k^14,0,1,2,3 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3 are candidates; store these 240−F1 candidates in Table W1.(3)
Use the second attack trail to calculate the remaining subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω2 to obtain 2n+47 pairs C0⊕T2,C0′⊕T2'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, Table H2 is accessed to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,4,5,6,7SB,y′ in Table U2, and index the pairs by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(4)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,4,k^14,4,5,6,7. Access Table H4 to obtain 28 input difference Δy7,4,5,6,7MC. Access Table U2 to obtain the output difference.Construct TableV2, which has 240 addresses indexed by 5-byte subkeys k^13,4,k^14,4,5,6,7. For each address, set the initial value to 0. Then, set the counter that corresponds to F2 with an initial value of 0. For each pair in Table U2, 28 wrong subkeys k^13,4,k^14,4,5,6,7 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,4,k^14,4,5,6,7 is 0 in Table V2, update the value to 1 and increase the value of F2 by 1. If F2=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong and discard it. Check all pairs in Table V2. If still F2<240, the value at addresses of subkeys k^13,4,k^14,4,5,6,7 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 are candidates; store these 240−F2 candidates in Table W2.(5)
Fork10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, use the master key recovering technique to efficiently obtain the right master key. For each candidate, guess all 264 subkeys k^14,8,9,10,11,12,13,14,15. Through the SR and MC operations, the subkey k14 can be obtained. Calculate k^13,0,4 with the help of the key schedule, and if the calculated value of k^13,0,4 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Then, calculate k10,0,1,2,3,4,5,6,7 with the help of the key schedule, and if the calculated value of k10,0,1,2,3,4,5,6,7 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Attackers check the remaining candidates by brute force until the right master key is obtained.Then, we analyse the complexity of the attack with reconstruction queries.The data-collection phase requires2×2n×272log2272≈2n+79.2 comparisons and 2×2×2n+47×13≈2n+52.7 bytes of memory. The complexity of precomputation phase can be ignored compared with the data collecting phase.The complexities of the online phase are as follows:(1)
Step 1 requires2n+47×3×232≈2n+80.6 memory accesses (MAs) and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(2)
In Step 2, a wrong subkeyk^13,0,k^14,0,1,2,3 can pass the test of one pair with probability 1−2−24, and all 240 wrong subkeys k^13,0,k^14,0,1,2,3 cannot pass the test of 224 pairs with probability 1−1−2−24224240≈e−240−1.4425. Therefore, the probability that all 240 subkeys k^13,0,k^14,0,1,2,3 can pass the test of 224d pairs but cannot pass the test of 224d+1 pairs is pd≈e−240−1.4425d+1−e−240−1.4425d. Then, the mathematical expectation of d is(2)Ed=∑d=1∞de−240−1.4425d+1−e−240−1.4425d≈27.81≈24.8.Thus, Step 2 requires264×224×28×24.8≈2100.8 MAs. Wrong subkeys k10,0,1,2,3,4,5,6,7 can pass the test of 3×2n+15 pairs with the probability(3)pn=1−1−1−2−242n+16.6240≈1−e−240−1.4425×2n−7.4.Thus,264×pn subkeys k10,0,1,2,3,4,5,6,7 remain, and 264×pn×13 bytes of memory are required to store subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3.(3)
Similar to Step 1, Step 3 requires2n+47×3×232≈2n+80.6 MAs and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(4)
In Step 4, some wrong subkeysk10,0,1,2,3,4,5,6,7 have been discarded. As in Step 2, 264×pn×224×28×24.8≈2100.8×pn MAs are needed. Then, 264×pn2 subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 remain, so 264×pn2×18 bytes of memory are needed.(5)
In Step 5, for each candidatek10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, guessing all 264 subkeys k^14,8,9,10,11,12,13,14,15 to calculate subkey k^13,0,4 requires 2128×pn2 MAs. After sieving subkeys, 2112×pn2 candidates remain. Calculating k10,0,1,2,3,4,5,6,7 requires 2112×pn2×4 MAs. Then, 248×pn2 candidates remain. Then, the procedure by brute force requires 248×pn2 encryptions.For the attack procedure with reconstruction queries, taken=12.8, and then pn=2−20.9 can be obtained. The time complexity and the memory complexity are dominated by Step 2 and Steps 1 and 3, respectively. Overall, this attack scenario requires 285.8 chosen ciphertexts, 2100.8 lookups, 27.2 encryptions and 296.7/16=292.7 AES states.According to the above analysis, the advantages of our attack scenario are as follows:(1)
The second attack trail is only applied for sieving the remaining subkeys. Because the subkeysk10,0,1,2,3,4,5,6,7 are fewer, the time complexity of the attack scenario is not increased. Additionally, the second attack has high sieving efficiency. When n=12.8, the probability that a wrong subkey k10,0,1,2,3,4,5,6,7 can pass the test is Pn=2−20.9; that is, the second attack trail can discard 220.9 more wrong subkeys without increasing the time complexity.(2)
Our attack scenario calculates five more subkey bytes without increasing the time complexity. In Step 5, the efficiency of sieving candidates can be improved because attackers obtain more subkey bytes to discard wrong candidates efficiently. Thus, our attack scenario can obtain a better result.


### 4.2. The Attack with Encryption Queries

The procedure of an attack with encryption queries is similar to the procedure of an attack with reconstruction queries. We omit the precomputation and online phases for the sake of brevity. This section elaborates mainly on the data-collection phase.The idea of the data-collection phase is as follows: attackers obtain2m known plaintexts and guess a 1-byte tweak, and 2m+8 corresponding ciphertexts can be obtained by encryption queries. Then, the attackers select the pairs that meet the requirements of the attack trails. Thus, the attack scenario with encryption queries can be obtained.Data-collection phase: from2m known plaintexts, the ciphertext C0,C1 can be obtained by encryption queries.For the first attack trail, attackers obtain2m known plaintexts, select 28 tweaks that take all possible values in T0, and fix the other 7 bytes to constant values. Then, 2m+8 corresponding ciphertexts C0,C1 can be obtained by encryption queries. For C1, through the AT−1, MC−1, and SR−1 operations, C0,y8AK can be obtained. Using the sieve method based on rapid sorting, select 2m+8×2m+8−1÷2×2−160≈22m−145 pairs of C0,y8AK, where Δy8,0,1,2,3SB≠0 and ΔC0,0,1,2,3,4,5,6,7SB≠0, and the difference value of the other 20 bytes is zero; then, store the ordered texts C0,8,9,10,11,12,13,14,15,y8,0,1,2,3SB in Table Ω3.For the second attack trail, attackers use the same2m known plaintexts, select 28 tweaks that take all possible values in T2, and fix the other 7 bytes to constant values. Then, 2m+8 corresponding ciphertexts C0,C1 can be obtained by encryption queries. For C1, through the AT−1, MC−1, and SR−1 operations, C0,y8AK can be obtained. Using the sieve method based on rapid sorting, select 2m+8×2m+8−1÷2×2−160≈22m−145 pairs of C0,y8AK, where Δy8,4,5,6,7SB≠0 and ΔC0,0,1,2,3,4,5,6,7SB≠0 and the other 20 bytes difference value is zero; then, store the ordered texts C0,8,9,10,11,12,13,14,15,y8,4,5,6,7SB in Table Ω4.Then, we analyse the complexity of the above attack with encryption queries.The data-collection phase requires2×2m+8log22m+8≈m+8×2m+9 comparisons, 2×2×22m−145×13≈22m−149.3 bytes of memory and 2m+9 known plaintexts.For the attack with encryption queries, taken=12.8, and 2n+47=259.8 pairs meet the requirements of attack trails. For the attack with encryption queries, 22m−145 pairs meet the requirements of attack trails, so m=102.4. Thus, the time complexity is dominated by the data-collection phase, and the memory complexity is dominated by Steps 1 and 3. Overall, this attack scenario requires 2111.4 plaintexts, 2118.8 lookups, 27.2 encryptions and 296.7/16=292.7 AES states.


## 4.1. The Attack with Reconstruction Queries

The attack procedure includes the data-collection phase, precomputation phase, and key-recovery phase. In this section, we use the sieve method based on rapid sorting [18] to choose ciphertext pairs.


### 4.1.1. Data-Collection Phase

We choose the ciphertextC0 and then obtain the ciphertext C1 by reconstruction queries.For the first attack trail, select28 tweaks that take all possible values in T0 and fix the other 7 bytes to constant values. Select 264 ciphertexts C0 that take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7 and fix the other 8 bytes to constant values. We take 272C0,T0 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,0,1,2,3SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T0,y8,0,1,2,3SB in Table Ω1.For the second attack trail, select28 tweaks that take all possible values in T2 and fix the other 7 bytes to constant values. Select the same 264 ciphertexts C0 in the first trail. These ciphertexts take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7), and fix the other 8 bytes to constant values. We take 272C0,T2 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,4,5,6,7SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T2,y8,4,5,6,7SB in Table Ω2.


### 4.1.2. Precomputation Phase

TableΛ: let S, Δin, and Δout denote the S-box of ForkAES, the input difference and the output difference of the S-box, respectively. The equation Sx⊕Sx⊕Δin=Δout has one solution on average when the values of the differences Δin and Δout are nonzero. We construct Table Λ to store the calculated value of x, indexed by all 216 values of Δin,Δout.TableH1: for the first branch of the first attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H1 to store 3×232 difference values of Δx8MC.TableH2: for the first branch of the second attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H2 to store 3×232 difference values of Δx8MC.TableH3: for the second branch of the first attack trail, there are 28 difference values by guessing all possible values of Δy7,0SR. Through the MC operation, there are 28 difference values of Δy7,0,1,2,3MC. We construct Table H3 to store these 28 difference values of Δy7,0,1,2,3MC.TableH4: for the second branch of the second attack trail, there are 28 difference values by guessing all possible values of Δy7,4SR. Through the MC operation, there are 28 difference values of Δy7,4,5,6,7MC. We construct Table H3 to store these 28 difference values of Δy7,4,5,6,7MC.


### 4.1.3. Online Phase

In Steps 1 and 2, combining a series of techniques, use the first attack trail to reject some wrong subkeys. In Steps 3 and 4, use the second attack trail to reject some wrong subkeys for the remaining subkeys, thereby enhancing the efficiency of sieving subkeys. In Step 5, by comprehensively utilizing the subkeys information, use the master key recovering technique to reject wrong candidate keys until the right master key is obtained. We take2n structures, and the specific procedure is as follows:(1)
Use the first attack trail to calculate subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω1 to obtain 2n+47 pairs C0⊕T0,C0′⊕T0'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, access Table H1 to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,0,1,2,3SB,y′ in Table U1 indexed by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(2)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,0,k^14,0,1,2,3. Access Table H3 to obtain 28 input difference Δy7,0,1,2,3MC. Access Table U1 to obtain output difference.Construct TableV1, which has 240 addresses indexed by 5-byte subkeys k^13,0,k^14,0,1,2,3. For each address, set the initial value to 0. Then, set the counter that corresponds to F1 with an initial value of 0. For each pair in Table U1, 28 wrong subkeys k^13,0,k^14,0,1,2,3 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,0,k^14,0,1,2,3 is 0 in Table V1, update the value to 1 and increase the value of F1 by 1. If F1=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong, and discard it. Check all pairs in Table V1; then, if still F1<240, the value at the addresses of subkeys k^13,0,k^14,0,1,2,3 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3 are candidates; store these 240−F1 candidates in Table W1.(3)
Use the second attack trail to calculate the remaining subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω2 to obtain 2n+47 pairs C0⊕T2,C0′⊕T2'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, Table H2 is accessed to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,4,5,6,7SB,y′ in Table U2, and index the pairs by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(4)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,4,k^14,4,5,6,7. Access Table H4 to obtain 28 input difference Δy7,4,5,6,7MC. Access Table U2 to obtain the output difference.Construct TableV2, which has 240 addresses indexed by 5-byte subkeys k^13,4,k^14,4,5,6,7. For each address, set the initial value to 0. Then, set the counter that corresponds to F2 with an initial value of 0. For each pair in Table U2, 28 wrong subkeys k^13,4,k^14,4,5,6,7 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,4,k^14,4,5,6,7 is 0 in Table V2, update the value to 1 and increase the value of F2 by 1. If F2=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong and discard it. Check all pairs in Table V2. If still F2<240, the value at addresses of subkeys k^13,4,k^14,4,5,6,7 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 are candidates; store these 240−F2 candidates in Table W2.(5)
Fork10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, use the master key recovering technique to efficiently obtain the right master key. For each candidate, guess all 264 subkeys k^14,8,9,10,11,12,13,14,15. Through the SR and MC operations, the subkey k14 can be obtained. Calculate k^13,0,4 with the help of the key schedule, and if the calculated value of k^13,0,4 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Then, calculate k10,0,1,2,3,4,5,6,7 with the help of the key schedule, and if the calculated value of k10,0,1,2,3,4,5,6,7 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Attackers check the remaining candidates by brute force until the right master key is obtained.Then, we analyse the complexity of the attack with reconstruction queries.The data-collection phase requires2×2n×272log2272≈2n+79.2 comparisons and 2×2×2n+47×13≈2n+52.7 bytes of memory. The complexity of precomputation phase can be ignored compared with the data collecting phase.The complexities of the online phase are as follows:(1)
Step 1 requires2n+47×3×232≈2n+80.6 memory accesses (MAs) and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(2)
In Step 2, a wrong subkeyk^13,0,k^14,0,1,2,3 can pass the test of one pair with probability 1−2−24, and all 240 wrong subkeys k^13,0,k^14,0,1,2,3 cannot pass the test of 224 pairs with probability 1−1−2−24224240≈e−240−1.4425. Therefore, the probability that all 240 subkeys k^13,0,k^14,0,1,2,3 can pass the test of 224d pairs but cannot pass the test of 224d+1 pairs is pd≈e−240−1.4425d+1−e−240−1.4425d. Then, the mathematical expectation of d is(2)Ed=∑d=1∞de−240−1.4425d+1−e−240−1.4425d≈27.81≈24.8.Thus, Step 2 requires264×224×28×24.8≈2100.8 MAs. Wrong subkeys k10,0,1,2,3,4,5,6,7 can pass the test of 3×2n+15 pairs with the probability(3)pn=1−1−1−2−242n+16.6240≈1−e−240−1.4425×2n−7.4.Thus,264×pn subkeys k10,0,1,2,3,4,5,6,7 remain, and 264×pn×13 bytes of memory are required to store subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3.(3)
Similar to Step 1, Step 3 requires2n+47×3×232≈2n+80.6 MAs and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(4)
In Step 4, some wrong subkeysk10,0,1,2,3,4,5,6,7 have been discarded. As in Step 2, 264×pn×224×28×24.8≈2100.8×pn MAs are needed. Then, 264×pn2 subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 remain, so 264×pn2×18 bytes of memory are needed.(5)
In Step 5, for each candidatek10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, guessing all 264 subkeys k^14,8,9,10,11,12,13,14,15 to calculate subkey k^13,0,4 requires 2128×pn2 MAs. After sieving subkeys, 2112×pn2 candidates remain. Calculating k10,0,1,2,3,4,5,6,7 requires 2112×pn2×4 MAs. Then, 248×pn2 candidates remain. Then, the procedure by brute force requires 248×pn2 encryptions.For the attack procedure with reconstruction queries, taken=12.8, and then pn=2−20.9 can be obtained. The time complexity and the memory complexity are dominated by Step 2 and Steps 1 and 3, respectively. Overall, this attack scenario requires 285.8 chosen ciphertexts, 2100.8 lookups, 27.2 encryptions and 296.7/16=292.7 AES states.According to the above analysis, the advantages of our attack scenario are as follows:(1)
The second attack trail is only applied for sieving the remaining subkeys. Because the subkeysk10,0,1,2,3,4,5,6,7 are fewer, the time complexity of the attack scenario is not increased. Additionally, the second attack has high sieving efficiency. When n=12.8, the probability that a wrong subkey k10,0,1,2,3,4,5,6,7 can pass the test is Pn=2−20.9; that is, the second attack trail can discard 220.9 more wrong subkeys without increasing the time complexity.(2)
Our attack scenario calculates five more subkey bytes without increasing the time complexity. In Step 5, the efficiency of sieving candidates can be improved because attackers obtain more subkey bytes to discard wrong candidates efficiently. Thus, our attack scenario can obtain a better result.


## 4.1.1. Data-Collection Phase

We choose the ciphertextC0 and then obtain the ciphertext C1 by reconstruction queries.For the first attack trail, select28 tweaks that take all possible values in T0 and fix the other 7 bytes to constant values. Select 264 ciphertexts C0 that take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7 and fix the other 8 bytes to constant values. We take 272C0,T0 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,0,1,2,3SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T0,y8,0,1,2,3SB in Table Ω1.For the second attack trail, select28 tweaks that take all possible values in T2 and fix the other 7 bytes to constant values. Select the same 264 ciphertexts C0 in the first trail. These ciphertexts take all possible values in the 8 bytes at 0,1,2,3,4,5,6,7), and fix the other 8 bytes to constant values. We take 272C0,T2 as a structure. By reconstruction querying, through the AT−1, MC−1, and SR−1 operations, 272 texts y8AK can be obtained. Using the sieve method based on rapid sorting, select 272×28−19÷2×2−96≈247 pairs of y8SB,y′, where Δy8,4,5,6,7SB≠0 and the other 12-byte difference value is zero, and then store the ordered texts C0,T2,y8,4,5,6,7SB in Table Ω2.


## 4.1.2. Precomputation Phase

TableΛ: let S, Δin, and Δout denote the S-box of ForkAES, the input difference and the output difference of the S-box, respectively. The equation Sx⊕Sx⊕Δin=Δout has one solution on average when the values of the differences Δin and Δout are nonzero. We construct Table Λ to store the calculated value of x, indexed by all 216 values of Δin,Δout.TableH1: for the first branch of the first attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H1 to store 3×232 difference values of Δx8MC.TableH2: for the first branch of the second attack trail, there are 3×296 input difference values of three distinguishers. Through the MC operation, 3×296×2−64=3×232 input difference values satisfy the demand for the truncated difference Δx8AT. We construct Table H2 to store 3×232 difference values of Δx8MC.TableH3: for the second branch of the first attack trail, there are 28 difference values by guessing all possible values of Δy7,0SR. Through the MC operation, there are 28 difference values of Δy7,0,1,2,3MC. We construct Table H3 to store these 28 difference values of Δy7,0,1,2,3MC.TableH4: for the second branch of the second attack trail, there are 28 difference values by guessing all possible values of Δy7,4SR. Through the MC operation, there are 28 difference values of Δy7,4,5,6,7MC. We construct Table H3 to store these 28 difference values of Δy7,4,5,6,7MC.


## 4.1.3. Online Phase

In Steps 1 and 2, combining a series of techniques, use the first attack trail to reject some wrong subkeys. In Steps 3 and 4, use the second attack trail to reject some wrong subkeys for the remaining subkeys, thereby enhancing the efficiency of sieving subkeys. In Step 5, by comprehensively utilizing the subkeys information, use the master key recovering technique to reject wrong candidate keys until the right master key is obtained. We take2n structures, and the specific procedure is as follows:(1)
Use the first attack trail to calculate subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω1 to obtain 2n+47 pairs C0⊕T0,C0′⊕T0'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, access Table H1 to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,0,1,2,3SB,y′ in Table U1 indexed by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(2)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,0,k^14,0,1,2,3. Access Table H3 to obtain 28 input difference Δy7,0,1,2,3MC. Access Table U1 to obtain output difference.Construct TableV1, which has 240 addresses indexed by 5-byte subkeys k^13,0,k^14,0,1,2,3. For each address, set the initial value to 0. Then, set the counter that corresponds to F1 with an initial value of 0. For each pair in Table U1, 28 wrong subkeys k^13,0,k^14,0,1,2,3 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,0,k^14,0,1,2,3 is 0 in Table V1, update the value to 1 and increase the value of F1 by 1. If F1=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong, and discard it. Check all pairs in Table V1; then, if still F1<240, the value at the addresses of subkeys k^13,0,k^14,0,1,2,3 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3 are candidates; store these 240−F1 candidates in Table W1.(3)
Use the second attack trail to calculate the remaining subkeyk10,0,1,2,3,4,5,6,7. Access Table Ω2 to obtain 2n+47 pairs C0⊕T2,C0′⊕T2'. Through the AT−1, AK−1, MC−1, and SR−1 operations, the 2n+47 output difference Δout can be obtained. Then, Table H2 is accessed to obtain the 3×232 input difference Δin. Access Table Λ to obtain 3×2n+79 subkeys k10,0,1,2,3,4,5,6,7. Store the corresponding pairs y8,4,5,6,7SB,y′ in Table U2, and index the pairs by subkey k10,0,1,2,3,4,5,6,7, so 3×2n+15 pairs remain on average.(4)
For the current subkeyk10,0,1,2,3,4,5,6,7, calculate subkey k^13,4,k^14,4,5,6,7. Access Table H4 to obtain 28 input difference Δy7,4,5,6,7MC. Access Table U2 to obtain the output difference.Construct TableV2, which has 240 addresses indexed by 5-byte subkeys k^13,4,k^14,4,5,6,7. For each address, set the initial value to 0. Then, set the counter that corresponds to F2 with an initial value of 0. For each pair in Table U2, 28 wrong subkeys k^13,4,k^14,4,5,6,7 can be discarded by accessing Table Λ. If the value at the corresponding address of discarded subkey k^13,4,k^14,4,5,6,7 is 0 in Table V2, update the value to 1 and increase the value of F2 by 1. If F2=240, evaluate the current subkey k10,0,1,2,3,4,5,6,7 as wrong and discard it. Check all pairs in Table V2. If still F2<240, the value at addresses of subkeys k^13,4,k^14,4,5,6,7 is 0, and the corresponding subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 are candidates; store these 240−F2 candidates in Table W2.(5)
Fork10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, use the master key recovering technique to efficiently obtain the right master key. For each candidate, guess all 264 subkeys k^14,8,9,10,11,12,13,14,15. Through the SR and MC operations, the subkey k14 can be obtained. Calculate k^13,0,4 with the help of the key schedule, and if the calculated value of k^13,0,4 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Then, calculate k10,0,1,2,3,4,5,6,7 with the help of the key schedule, and if the calculated value of k10,0,1,2,3,4,5,6,7 differs from the value of the current subkey, evaluate the current candidate as wrong and discard it. Attackers check the remaining candidates by brute force until the right master key is obtained.Then, we analyse the complexity of the attack with reconstruction queries.The data-collection phase requires2×2n×272log2272≈2n+79.2 comparisons and 2×2×2n+47×13≈2n+52.7 bytes of memory. The complexity of precomputation phase can be ignored compared with the data collecting phase.The complexities of the online phase are as follows:(1)
Step 1 requires2n+47×3×232≈2n+80.6 memory accesses (MAs) and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(2)
In Step 2, a wrong subkeyk^13,0,k^14,0,1,2,3 can pass the test of one pair with probability 1−2−24, and all 240 wrong subkeys k^13,0,k^14,0,1,2,3 cannot pass the test of 224 pairs with probability 1−1−2−24224240≈e−240−1.4425. Therefore, the probability that all 240 subkeys k^13,0,k^14,0,1,2,3 can pass the test of 224d pairs but cannot pass the test of 224d+1 pairs is pd≈e−240−1.4425d+1−e−240−1.4425d. Then, the mathematical expectation of d is(2)Ed=∑d=1∞de−240−1.4425d+1−e−240−1.4425d≈27.81≈24.8.Thus, Step 2 requires264×224×28×24.8≈2100.8 MAs. Wrong subkeys k10,0,1,2,3,4,5,6,7 can pass the test of 3×2n+15 pairs with the probability(3)pn=1−1−1−2−242n+16.6240≈1−e−240−1.4425×2n−7.4.Thus,264×pn subkeys k10,0,1,2,3,4,5,6,7 remain, and 264×pn×13 bytes of memory are required to store subkeys k10,0,1,2,3,4,5,6,7,k^13,0,k^14,0,1,2,3.(3)
Similar to Step 1, Step 3 requires2n+47×3×232≈2n+80.6 MAs and 3×2n+15×264×2×5≈2n+83.9 bytes of memory.(4)
In Step 4, some wrong subkeysk10,0,1,2,3,4,5,6,7 have been discarded. As in Step 2, 264×pn×224×28×24.8≈2100.8×pn MAs are needed. Then, 264×pn2 subkeys k10,0,1,2,3,4,5,6,7,k^13,4,k^14,4,5,6,7 remain, so 264×pn2×18 bytes of memory are needed.(5)
In Step 5, for each candidatek10,0,1,2,3,4,5,6,7,k^13,0,4,k^14,0,1,2,3,4,5,6,7, guessing all 264 subkeys k^14,8,9,10,11,12,13,14,15 to calculate subkey k^13,0,4 requires 2128×pn2 MAs. After sieving subkeys, 2112×pn2 candidates remain. Calculating k10,0,1,2,3,4,5,6,7 requires 2112×pn2×4 MAs. Then, 248×pn2 candidates remain. Then, the procedure by brute force requires 248×pn2 encryptions.For the attack procedure with reconstruction queries, taken=12.8, and then pn=2−20.9 can be obtained. The time complexity and the memory complexity are dominated by Step 2 and Steps 1 and 3, respectively. Overall, this attack scenario requires 285.8 chosen ciphertexts, 2100.8 lookups, 27.2 encryptions and 296.7/16=292.7 AES states.According to the above analysis, the advantages of our attack scenario are as follows:(1)
The second attack trail is only applied for sieving the remaining subkeys. Because the subkeysk10,0,1,2,3,4,5,6,7 are fewer, the time complexity of the attack scenario is not increased. Additionally, the second attack has high sieving efficiency. When n=12.8, the probability that a wrong subkey k10,0,1,2,3,4,5,6,7 can pass the test is Pn=2−20.9; that is, the second attack trail can discard 220.9 more wrong subkeys without increasing the time complexity.(2)
Our attack scenario calculates five more subkey bytes without increasing the time complexity. In Step 5, the efficiency of sieving candidates can be improved because attackers obtain more subkey bytes to discard wrong candidates efficiently. Thus, our attack scenario can obtain a better result.


## 4.2. The Attack with Encryption Queries

The procedure of an attack with encryption queries is similar to the procedure of an attack with reconstruction queries. We omit the precomputation and online phases for the sake of brevity. This section elaborates mainly on the data-collection phase.The idea of the data-collection phase is as follows: attackers obtain2m known plaintexts and guess a 1-byte tweak, and 2m+8 corresponding ciphertexts can be obtained by encryption queries. Then, the attackers select the pairs that meet the requirements of the attack trails. Thus, the attack scenario with encryption queries can be obtained.Data-collection phase: from2m known plaintexts, the ciphertext C0,C1 can be obtained by encryption queries.For the first attack trail, attackers obtain2m known plaintexts, select 28 tweaks that take all possible values in T0, and fix the other 7 bytes to constant values. Then, 2m+8 corresponding ciphertexts C0,C1 can be obtained by encryption queries. For C1, through the AT−1, MC−1, and SR−1 operations, C0,y8AK can be obtained. Using the sieve method based on rapid sorting, select 2m+8×2m+8−1÷2×2−160≈22m−145 pairs of C0,y8AK, where Δy8,0,1,2,3SB≠0 and ΔC0,0,1,2,3,4,5,6,7SB≠0, and the difference value of the other 20 bytes is zero; then, store the ordered texts C0,8,9,10,11,12,13,14,15,y8,0,1,2,3SB in Table Ω3.For the second attack trail, attackers use the same2m known plaintexts, select 28 tweaks that take all possible values in T2, and fix the other 7 bytes to constant values. Then, 2m+8 corresponding ciphertexts C0,C1 can be obtained by encryption queries. For C1, through the AT−1, MC−1, and SR−1 operations, C0,y8AK can be obtained. Using the sieve method based on rapid sorting, select 2m+8×2m+8−1÷2×2−160≈22m−145 pairs of C0,y8AK, where Δy8,4,5,6,7SB≠0 and ΔC0,0,1,2,3,4,5,6,7SB≠0 and the other 20 bytes difference value is zero; then, store the ordered texts C0,8,9,10,11,12,13,14,15,y8,4,5,6,7SB in Table Ω4.Then, we analyse the complexity of the above attack with encryption queries.The data-collection phase requires2×2m+8log22m+8≈m+8×2m+9 comparisons, 2×2×22m−145×13≈22m−149.3 bytes of memory and 2m+9 known plaintexts.For the attack with encryption queries, taken=12.8, and 2n+47=259.8 pairs meet the requirements of attack trails. For the attack with encryption queries, 22m−145 pairs meet the requirements of attack trails, so m=102.4. Thus, the time complexity is dominated by the data-collection phase, and the memory complexity is dominated by Steps 1 and 3. Overall, this attack scenario requires 2111.4 plaintexts, 2118.8 lookups, 27.2 encryptions and 296.7/16=292.7 AES states.


## 5. Conclusion

In this paper, we first utilize the tweak with different truncated differences to construct two types of attack trails of ForkAES and then propose the multiple impossible differentials of ForkAES-∗ -5-4. Multiple attack trails obtain more subkey bytes and improve the efficiency of sieving keys without increasing the time complexity. Furthermore, we carefully consider the procedure of recovering the master key, which can efficiently reject wrong candidates. Combined with several technologies, the complexity of our attack scenarios can be optimized. In reconstruction queries, our attack reaches the longest number of rounds for ForkAES in impossible difference analysis, with 2100.8 lookups, 285.8 chosen ciphertexts, and 292.7 memory blocks to store AES states. In encryption queries, we improve the previous attacks on ForkAES by attacking one more round, with 2118.2 lookups, 2111.4 plaintexts, and 292.7 memory blocks to store AES states.



---

*Source: 5360032-2022-06-29.xml*