# Related-Key Multiple Impossible Differential Cryptanalysis on Full-Round LiCi-2 Designed for IoT

Authors: Kai Zhang; Xuejia Lai; Lei Wang; Jie Guan; Bin Hu; Senpeng Wang; Tairong Shi
Journal: Security and Communication Networks
 (2022)

---

## Abstract

LiCi-2 is an ultralightweight block cipher designed for constrained IoT devices. It is a successor of LiCi and has even better performance in both software and hardware implementation. In this paper, based on the idea of related-key multiple impossible differential cryptanalysis, a key recovery attack on full-round LiCi-2 is proposed. First, an interesting property is revealed that, with a single bit difference in the related key, a 10-round differential character with probability of 1 exists on LiCi-2. With an automatic approach, the boundaries of impossible differential distinguishers in terms of single-key setting and related-key setting are explored. Under our construction method, the longest length is 8 rounds for single-key setting and 18 rounds for related-key setting. Finally, based on these 18-round distinguishers, a 25-round key recovery attack is proposed with adding 3 rounds before and 4 rounds after the distinguisher. Our attack needs one related key. The time complexity for our attack isO(2123.44), the memory complexity is O(294), and the data complexity is O(260.68). As far as we know, no full-round attack has previously been reported on LiCi-2.


---

## Body

## 1. Introduction

As a representative for the new information age, the Internet of things (IoT) has shown its strong vitality in many fields. It can be viewed as an expanded network based on the Internet and it combines various sensing devices to form a huge network, which enables a wider interconnection of people, machines, and things. However, the sensing devices in IoT usually have very limited resources such as computing resource, power resource, and hardware implementation resource. So, it is very essential to propose lightweight primitives and ensure the information security in IoT devices. In recent years, many good lightweight block ciphers are proposed such as PRESENT [1], GIFT [2], Midori [3], LBlock [4], RECTANGLE [5], SIMON, and SPECK [6]. In 2019, NIST (National Institute of Standards and Technology) proposed a standardization project LWC (LightWeight Cryptography) to enhance the development for lightweight ciphers. Among these lightweight block ciphers, LiCi (denoted as LiCi-1 in this paper to avoid confusion) is a lightweight block cipher proposed in 2017 [7]. The block size for LiCi-1 is 64-bit and the key size is 128-bit. It totally has 31 rounds. Up to now, the security margin on LiCi-1 is enough. To reach better performance, as a successor, LiCi-2 was proposed in 2018 [8]. For LiCi-2, it reduces the total rounds from 31 to 25, and half of the subkeys and a circular shift are omitted for better performance. LiCi-2 is designed for extremely constrained devices, such as 6LoWPAN. It shows good performance in memory requirement, power consumption, and hardware implementation.Impossible differential cryptanalysis was originally proposed by Knudsen [9] and Biham et al. [10], respectively. It is one of the most effective cryptanalytic methods so far. The basic idea of impossible differential cryptanalysis is establishing an impossible differential distinguisher and filtering the wrong key candidates with this distinguisher until the correct key is recovered. Related-key impossible differential cryptanalysis is a variant of impossible differential cryptanalysis. This attack is based on the assumption that the attacker has access to the encryption oracle and can use related keys as input. This kind of attack has been applied to many block ciphers successfully, such as AES and LBlock [11–15].Our Contributions: The main purpose of this paper is to evaluate the security level on LiCi-2 against related-key multiple impossible differential cryptanalysis. There are three main contributions which are listed as follows:(i)
A 10-round differential distinguisher with probability of 1 is constructed. With this property, many differential-type distinguishers can be extended for better attack.(ii)
The length and number of impossible differential distinguishers on LiCi-2 in single-key setting and related-key setting are explored in an automatic approach. In the single-key setting, the longest length of the distinguisher under our construction method is 9-round and there are altogether 240 such distinguishers discovered. In the related-key setting, the longest length of the distinguishers discovered is 18-round and 65 such distinguishers are presented.(iii)
Based on twenty of these 18-round related-key distinguishers, a key recovery attack on full-round LiCi-2 is proposed with adding 3 rounds before and 4 rounds after the distinguisher. The summary of our result and prior results on LiCi-1 and LiCi-2 is presented in Table1.This paper is organized as follows. Section2 introduces the notations used throughout this paper. Section 3 gives a brief description on LiCi-2. Section 4 presents some observations and properties on LiCi-2. In Section 5, a key recovery attack on LiCi-2 is proposed, and Section 6 concludes the paper.Table 1
Summary of previous results on LiCi-1 and LiCi-2.
CipherType of attackAttacked/total roundsLength of the distinguisherTime complexityMemory complexityData complexityReferenceLiCi-1Linear16/32———2106[7]Differential16/32———296Integral13/3212283241263[16]16/321021732119263.6Impossible differential16/3210283.08276.76259.76[17]LiCi-2Linear20/25———2106[8]Differential20/25———280Impossible differential25/25182123.44294260.68This paper


## 2. Notations

Suppose thatE is an n-bit block cipher of R rounds; the following notations are used throughout this paper:(i)
K: 128-bit master key, Kt represents the value of the 128-bit key register at the t-th round and Ki−j represents the i-th bit to the jth bit of K(ii)
RKi: 32-bit round key at the i-th round(iii)
Li,Ri: input for the i-th round, Li represents the left branch, Ri represents the right branch, and Lt1−t2i (Rt1−t2i) represents the t1-th bit to the t2-th bit of Li (Ri)(iv)
Si: output of the Sbox layer for the i-th round(v)
“<<<i”: left rotation with i bits(vi)
“⊕”: XOR operation


## 3. Brief Description on LiCi-2

LiCi-2 is a lightweight block cipher that was proposed in 2018 [8]. It adopts a Feistel-type structure. The block size for LiCi-2 is 64-bit and the key size is 128-bit. It totally has 25 rounds. Each round consists of Sbox constitution, key addition, and circular shift. The round function is depicted in Figure 1 and the 4-bit Sbox used in LiCi-2 is depicted in Table 2.Figure 1
Round function of LiCi-2.Table 2
Sbox in LiCi-2.
x0123456789ABCDEFS(x)3FE10A58C4B2976DKey Schedule: The scale of master keyK is 128-bit. It can be denoted as K = k127, k126, k125, …, k2, k1, k0. First, the 128-bit key register is initialized with the master key. The register is rotated by 13 bits on the left. Every four of the eight least significant bits of the key register are substituted with the Sbox. XOR the binary form of the round number to the bits [k63k62k61k60k59]. The 32 least significant bits are extracted as the round key RKi. The mathematical form of this updating progress can be illustrated as follows:(1)
[k127k126 ⋅⋅⋅ k1k0] <<< 13(2)
[k3k2k1k0] = S[k3k2k1k0](3)
[k7k6k5k4] = S[k7k6k5k4](4)
[k63k62k61k60k59] = [k63k62k61k60k59] ⊕ RCi(5)
RKi = [k31k30 ⋅⋅⋅ k1k0]


## 4. Observations on LiCi-2

In this section, some new observations and properties on LiCi-2 are introduced. First, a 10-round differential character with probability one is constructed in Property 1. The boundaries of impossible differential distinguishers on LiCi-2 in single-key setting and related-key setting are discussed in Observation 1 and Observation 2. These distinguishers will be a foundation for our later attack.Property 1 (a 10-Round Differential Character). Given two plaintext pairs whose difference is ΔL0,ΔR0 and a related key whose difference is ΔK, if ΔR210=1, ΔK21=1, and other differences are all zeros, the difference of the internal state at the beginning of the 11th round ΔL10,ΔR10 will have only two-bit difference ΔL1010=1,ΔR1010=1 with probability of 1.Proof.
The difference of the first subkeyΔRK0 can be derived from ΔK, where ΔRK210=1 and other bits are all zeros. According to the round function, the difference for the input of the second round can be calculated as follows:(1)ΔL1=ΔR0⊕ΔRK0⊕ΔSΔL0<<<11,ΔR1=ΔSΔL0<<<11⊕ΔL1.
AsΔL0 = 0 and ΔR0=ΔRK0, we can derive ΔL1,ΔR1=0,0. So, after several consecutive rounds, the difference of the internal state will remain zero until some ΔRKi bring in a new nonzero difference.
Let us consider the differential transfer property of the key schedule. According to the key schedule, the single-bit difference of the master key will go through the following positions of the key register (Table3) at the first 10 rounds.
After analyzing these positions, the nonzero difference will not appear in the subkeys until the 10th round, that is,ΔRK109. So the differences of ΔL1,ΔR1, ΔL2,ΔR2… ΔL9,ΔR9 will all be zeros and, for ΔL10,ΔR10, ΔL1010=1,ΔR1010=1 due to the difference of ΔRK109.
Former Observation 1 [17]. For the Sbox of LiCi-2, there are some differential characters for the input and output difference as indicated in Table 4.
This observation was proposed on LiCi-1. As the Sboxes for these two ciphers are identical, it can also be used on LiCi-2. It reveals the details of the differential transmission property for the Sbox. With this property, we can construct longer impossible differential distinguishers.
Observation 1 (Boundary of Single-Key Impossible Differential Distinguishers). For LiCi-2, in single-key setting, considering the details of the Sbox in Table 4, the maximum length of impossible differential distinguisher is 8 rounds and there are 544 such distinguishers in terms of one active bit input and output difference. If the numbers of active bits for the input and output difference are both limited to 2, the maximum length of single-key impossible differential distinguisher is 9 rounds and there are 240 such 9-round distinguishers. Summary of the statistics for these distinguishers is illustrated in Table 5.
As expected by the designers, this new version of LiCi has better diffusion property. The result in Observation 1 validates this improvement. For the original LiCi-1, for single-bit difference, the maximum length can reach 10 rounds and, for 1-bit input and 2-bit output difference, the maximum length can reach 11 rounds.
Observation 2 (Boundary of Related-Key Impossible Differential Distinguishers). For LiCi-2, in related-key setting, considering the details of the Sbox in Table 4, the maximum length of impossible differential distinguisher is 17 rounds and there are 64 such distinguishers in terms of one active bit in input, output, and key difference. If the number of active bits is 1 for input and key and 2 for output, the maximum length of related-key impossible differential distinguisher can reach 18 rounds and there are 65 such distinguishers (all these 65 distinguishers are presented in the Appendix). The summary of all these distinguishers is illustrated in Table 6.
According to Property 1, there are some long related-key differential characters. Thus, we added the condition of related key to our automatic searching algorithm and the result coincides with Property 1. The distinguishers are stretched for about 10 rounds as expected. Through Observation 2, it is found that, due to the existence of Property 1, many long related-key impossible differential distinguishers exist for LiCi-2 and the longest length under our searching strategy can cover about 72% of the total rounds.
For LiCi-1, a single 10-round impossible differential distinguisher is reported in [11], the hamming weight for the input difference is one, and output difference is two. According to our research on LiCi-2, there are two interesting contrary observations:(1)
The security level for single-key impossible differential cryptanalysis on LiCi-2 is higher than that on LiCi-1(2)
In related-key setting, the security level on LiCi-2 is much worse than that on LiCi-1
Property 2 (an 18-Round Distinguisher). For LiCi-2 reduced to 18 rounds, the differences for the plaintexts, ciphertexts, and related keys are denoted as ΔL0,ΔR0,ΔL18,ΔR18, and ΔK respectively. If ΔR00=1, ΔK45=1, ΔR1018=1, and other differences are all zeros, it is an 18-round impossible differential distinguisher.Table 3
Related position of key registers withΔRK190 at rounds 0 to 9.
Round0123456789Position2134476073869911212510Table 4
Differential transmission property for the Sbox of LiCi-2.
Input difference00010100100011001101∗∗11∗∗1∗∗∗0∗∗∗∗1∗∗∗0Output difference1∗∗∗∗∗∗1∗∗∗11∗∗00∗∗∗00010010001101000101Table 5
Length and number of the best distinguishers in single-key setting.
Strategy (difference)Maximum lengthNumberSingle-bit85441-bit input, 2-bit output92242-bit input, 1-bit output85602-bit input, 2-bit output916Table 6
Length and number of the best distinguishers in related-key setting.
Strategy (difference)Maximum lengthNumberSingle-bit17641-bit input, 2-bit output, 1-bit key1865Proof.
The difference of the master keyΔK45=1 will lead to the following differences for the 18-round key registers: ΔK450=1,ΔK581=1,ΔK712=1,ΔK843=1,ΔK974=1,ΔK1105=1,ΔK1236=1,ΔK87=1,ΔK218=1,ΔK349=1,ΔK4710=1,ΔK6011=1,ΔK7312=1,ΔK8613=1,ΔK9914=1,ΔK11215=1,ΔK12516=1,ΔK1017=1. According to the key schedule, the differences for the round keys are ΔRK87=1,ΔRK218=1,ΔRK1017=1, and other differences are all zeros.
AsΔL0=0,ΔR0=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1, according to the round function, the difference of the output of the first round can be calculated as follows:(2)ΔL1=ΔR0⊕ΔRK0⊕ΔSΔL0≪<11,ΔR1=ΔSΔL0≪<11⊕ΔL1.
SoΔL1=ΔR1=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1.
ForS3−01, as the difference of the input is (0,0,0,1), according to Table 4, the difference of the output is of the form (1,∗,∗,∗). After calculation according to the round function, the form of the difference for ΔL2,ΔR2 is as follows:(3)ΔL2=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,∗,∗,∗,0,0,0,0,0,0,0,0,0,0,1,ΔR2=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,∗,∗,∗,0,0,0,0,0,0,0,0,0,0,1.
Similarly, the input differences for the 4th round and 5th round are as follows:(4)ΔL3=0,0,0,0,0,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,1,∗,∗,∗,0,0,0,0,0,0,0,0,0,0,1,ΔR3=0,0,0,0,0,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,0,∗,∗,∗,0,0,0,0,0,0,0,0,0,0,1,ΔL4=∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,1,∗,∗,∗,0,0,0,0,∗,∗,∗,∗,∗,∗,∗,ΔR4=∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,0,∗,∗,∗,0,0,0,0,∗,∗,∗,∗,∗,∗,∗.
In the direction of decryption, the output differenceΔL18,ΔR18 is expressed as follows:(5)ΔL18=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,ΔR18=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0.
According to the key schedule, the round keyRK17 has a single-bit difference in RK1017. After one-round decryption, the difference for the input of the 17th round is ΔL17=0,ΔR17=0. As the differences for subkey RK16 to RK9 are all zeros, the difference for the input of the 9th round ΔL9=0,ΔR9=0.
The subkeyRK8 will bring in a new difference in RK218; thus the difference for the input of the 8th round is ΔL8=0,ΔR8=0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0.
Similarly, the input differences for the 7th to 4th rounds calculated in the decryption direction are as follows:(6)ΔL7=0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,∗,∗,∗,1,0,0,0,0,0,0,0,0,ΔR7=0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,ΔL6=∗,∗,∗,∗,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,∗,∗,∗,1,0,0,0,0,∗,∗,∗,∗,ΔR6=0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,∗,∗,∗,1,0,0,0,0,0,0,0,0,ΔL5=∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,∗,∗,∗,1,0,0,0,0,∗,∗,∗,∗,ΔR5=∗,∗,∗,∗,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,∗,∗,∗,1,0,0,0,0,∗,∗,∗,∗,ΔL4=∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,ΔR4=∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,∗,0,0,0,0,∗,∗,∗,1,0,0,0,0,∗,∗,∗,∗.
After comparing the two differences ofΔL4,ΔR4 derived in the encryption and decryption direction, there exists a contradiction in the position of ΔR84 (in the encryption direction, the difference ΔR84 is zero, while in the decryption direction, the difference ΔR84 is one, and the contradiction bit is marked in red in Figure 2). Thus, the constructed distinguisher is an 18-round impossible differential distinguisher. All the details for the construction of this 18-round distinguisher are depicted in Figure 2.Figure 2
A concrete 18-round related-key impossible differential distinguisher on LiCi-2.


## 5. Key Recovery Attack on Full-Round LiCi-2

With the 18-round related-key impossible differential proposed in Property 2, we add three rounds before and four rounds after the distinguisher to launch a key recovery attack. There are two stages for the key recovery attack: data collection stage and key recovery stage.Also, we use two approaches to reduce the data complexity. The first one is that more than one key is left in the candidate keys set and it will need to proceed to an exhaustive search among the remaining candidates; this strategy can be viewed as a tradeoff between the time complexity and data complexity. The second one is using multiple impossible differential distinguishers to reduce the data complexity. These two methods have been used and validated in ASIACRYPT 2014 [18] and Journal of Cryptology [19]. For simplicity, we will follow the framework proposed in [18].


### 5.1. Main Conclusions in [18]

#### 5.1.1. Notations

(i)
ΔXΔY: input (output) difference of the impossible differential distinguisher(ii)
ΔinΔout: set of all the possible input (output) differences of the cipher(iii)
rin: number of rounds of the differential path ΔX,Δin(iv)
rout: number of rounds of the differential path ΔY,Δout(v)
cincout: number of bit conditions that have to be verified to obtain ΔX from ΔinΔYfromΔout(vi)
kinkout: subset of subkey bits involved in the attack during the first rin rounds lastroutrounds(vii)
ΔinΔout: the dimension of the input space (output space)(viii)
N: amount of input (or output) pairs needed for the attack(ix)
P: the probability that a guessed wrong key is kept in the candidate key set(x)
nin: the number of equivalent impossible differential distinguishers with different input differences and same output differences(xi)
nout: the number of equivalent impossible differential distinguishers with same input difference and different output differencesSuppose that the block cipher we are dealing with is of block sizen and a key K of size K.


#### 5.1.2. Main Conclusions

The main conclusions are as follows.(1)
The relationship betweenN and P is as follows:(7)P=1−2−cin+coutN<12.The minimum value ofN, denoted by Nmin, is about 2cin+cout.(2)
The time complexity of the attack is approximated byT:(8)T=CN+N+2kin∪kout⋅N2cin+cout⋅CE′+2K⋅P⋅CE,whereCN=maxminΔ∈Δin,ΔoutN⋅2n+1−Δ|,N⋅2n+1−Δin−Δout,CN represents the data complexity needed to construct N plaintext-ciphertext pairs, with N and P satisfying condition (2) above, CE represents the cost for one full-round encryption, and CE′ represents the ratio of the cost for the partial encryption to the full encryption.The memory complexity of the attack is determined byN.(3)
To apply multiple impossible differential cryptanalysis, suppose thatnin⋅nout impossible differential distinguishers are derived from a single distinguisher. With more distinguishers, the time complexity of the attack can also be calculated with equation (8); however, previous Δin and Δout are replaced with Δin′ and Δout′, where Δin′=Δin+log2nin and Δout′=Δout+log2nout.


### 5.2. Procedures of the Attack

#### 5.2.1. Data Collection Stage

On one hand, construct 2m data sets. For each data set, to make the difference of a plaintext pair satisfy ΔL0,ΔR0 in Figure 3, there are 34 bits that can be arbitrary value and other 30 bits are fixed to a constant for a data set. On the other hand, suppose that the difference for the output of the 25th round is ΔL25,ΔR25, ΔL27,325=1,ΔR27,325=0 (4 bits).Figure 3
Key recovery attack on 25-round LiCi-2.


#### 5.2.2. Key Recovery Stage

In the key recovery stage, we guess the subkey bits in its smallest unit to reduce the complexity. This process is depicted in Figure3 to make it more intuitive. The details for the key recovery stage are illustrated in the following steps:(i)
Step 1. Sieve plaintext-ciphertext pairs according to the difference of the first round and last round. This process can be launched without the key.(i)
Step 1.1. For each plaintext-ciphertext pair, sieve those pairs whose difference for the input and output ofΔS7−40 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise. There are 3 bit conditions for this step.(ii)
Step 1.2. Sieve those pairs whose difference for the input and output ofΔS11−80 satisfies [∗,∗,∗,∗ – ∗,1,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (2 bit conditions).(iii)
Step 1.3. Sieve those pairs whose difference for the input and output ofΔS15−120 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 1.4. Sieve those pairs whose difference for the input and output ofΔS23−200 satisfies [∗, ∗, 1, ∗ – 0, 0, 1, 0]. If the pairs can satisfy the condition, save the pair or discard it otherwise. (3 bit conditions).(v)
Step 1.5 Sieve those pairs whose difference for the input and output ofΔS31−280 satisfies [∗,∗,∗,∗ – ∗,∗,∗,0]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(vi)
Step 1.6. Sieve the remaining pairs withΔL1,ΔR1. If ΔR15−81=0, keep the pair (8 bit conditions).(vii)
Step 1.7. Sieve those pairs whose difference for the input and output ofΔS3−024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(viii)
Step 1.8. Sieve those pairs whose difference for the input and output ofΔS15−1224 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ix)
Step 1.9. Sieve those pairs whose difference for the input and output ofΔS19−1624 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(x)
Step 1.10. Sieve those pairs whose difference for the input and output ofΔS23−2024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(xi)
Step 1.11. Sieve those pairs whose difference for the input and output ofΔS27−2424 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(xii)
Step 1.12. Sieve the remaining pairs withΔR24. If ΔR26−24,19−1524=0,ΔR2324=1, keep the pair (9 bit conditions).(ii)
Step 2. Sieve the plaintext-ciphertext pairs according to the difference of the second round.(i)
Step 2.1. GuessRK11−80 and test whether the difference of ΔS11−81 satisfies the form [∗,∗,∗,∗ – ∗,1,∗,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (2 bit conditions).(ii)
Step 2.2. GuessRK15−120 and test whether the difference of ΔS15−121 satisfies the form [∗,∗,∗,∗ – 0,0,0,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 2.3. GuessRK23−200 and test whether the difference of ΔS23−201 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ivi)
Step 2.4. Sieve the remaining pairs withΔR2. If ΔR23,22,202=0, keep the pair (3 bit conditions).(iii)
Step 3. Sieve the plaintext-ciphertext pairs according to the difference of the 23th round.(i)
Step 3.1. GuessRK14−1124 and test whether the difference for the input and output of ΔS3−023 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ii)
Step 3.2. GuessRK22−1924 and test whether the difference for the input and output of ΔS11−823 satisfies [0,1,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iii)
Step 3.3. GuessRK30−2724 and test whether the difference for the input and output of ΔS19−1623 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 3.4. GuessRK31,2−024 and test whether the difference for the input and output of ΔS23−2023 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(v)
Step 3.5. GuessRK6−324 and test whether the difference for the input and output of ΔS27−2423 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(vi)
Step 3.6. Sieve the remaining pairs withΔR23. If ΔR14−11,9−41=0,ΔR101=1, keep the pair. There are 2 m + 3 plaintext-ciphertext pairs left (11 bit conditions).(iv)
Step 4. Sieve the plaintext-ciphertext pairs according to the difference of the 22th round.(i)
Step 4.1. GuessRK22−1923 and test whether the input and output differences of ΔS11−822 satisfy the form [0,1,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ii)
Step 4.2. GuessRK30−2723 and RK10−724 and test whether the input and output differences of ΔS19−1622 satisfy the form [1,0,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 4.3 GuessRK31,223 and test whether the input and output differences of ΔS23−2022 satisfy the form [1,∗,∗,∗ – ∗,∗,∗,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (1 bit condition). It is noted that RK1,023=RK14,1324 have already been guessed in Step 3.1 and these redundant related keys will not be listed in the rest of the steps for simplicity.(iv)
Step 4.4. Sieve the remaining pairs withΔR22. If ΔR31−28,2−022=0, keep the pair (7 bit conditions).(v)
Step 5. Sieve the plaintext-ciphertext pairs according to the difference of the 3rd round. Guess extra 4 subkey bitsRK23−201 and calculate ΔS23−202. If ΔS23−202 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs and if the pairs can satisfy the condition, save the pair (3 bit conditions).(vi)
Step 6. Sieve the incorrect subkey candidates according to the difference of the 21th round. Guess extra 4 subkey bitsRK22−1922 and test whether the input and output differences of ΔS11−821 satisfy the form [0,1,0,0 – ∗,∗,∗,1] and if ΔR22−2021=0 (6 bit conditions) and if the pairs can satisfy the condition, it will lead to an impossible differential distinguisher; thus the guessed subkey candidate is false. Discard this key candidate and test another one, and iterate this process to reduce the space of key candidates.


### 5.3. Complexities of the Attack

According to our attack, the values areΔin = 34, Δout = 60, cin = 34, and cout = 60. As the data complexity for this attack always exceeds the full code book, it is infeasible to propose a valid impossible differential cryptanalysis with a single distinguisher. So, we will use multiple distinguishers to reduce this data complexity. Concretely speaking, twenty 18-round distinguishers with the following form are used (all the 65 18-round distinguishers can be found at the Appendix).Input difference:ΔR213=1. Key difference: ΔK110=1Output difference:ΔLi21,ΔRi21=1,i∈0−10,15−18,27−31Sonout = 20 and Δout′=Δout+log2nout=60+4.32=64.32.As there are altogether 23 active Sboxes (50 independent subkey bits) involved in the calculation,CE′=23/8⋅24=2−3.12. According to the equations in Section 5.1, the data complexity, memory complexity, and time complexity for our attack are calculated as follows:Data complexity:CN=maxmin294⋅264+1−34,294⋅264+1−64.32,294⋅264+1−34−64.32=260.68.Memory complexity:N=294 plaintext pairs and corresponding ciphertext pairs.Time complexity:T=260.68+294+250⋅294/294⋅2−3.12+2128⋅0.3679⋅2−3.12≈2123.44 LiCi-2 encryption.


## 5.1. Main Conclusions in [18]

### 5.1.1. Notations

(i)
ΔXΔY: input (output) difference of the impossible differential distinguisher(ii)
ΔinΔout: set of all the possible input (output) differences of the cipher(iii)
rin: number of rounds of the differential path ΔX,Δin(iv)
rout: number of rounds of the differential path ΔY,Δout(v)
cincout: number of bit conditions that have to be verified to obtain ΔX from ΔinΔYfromΔout(vi)
kinkout: subset of subkey bits involved in the attack during the first rin rounds lastroutrounds(vii)
ΔinΔout: the dimension of the input space (output space)(viii)
N: amount of input (or output) pairs needed for the attack(ix)
P: the probability that a guessed wrong key is kept in the candidate key set(x)
nin: the number of equivalent impossible differential distinguishers with different input differences and same output differences(xi)
nout: the number of equivalent impossible differential distinguishers with same input difference and different output differencesSuppose that the block cipher we are dealing with is of block sizen and a key K of size K.


### 5.1.2. Main Conclusions

The main conclusions are as follows.(1)
The relationship betweenN and P is as follows:(7)P=1−2−cin+coutN<12.The minimum value ofN, denoted by Nmin, is about 2cin+cout.(2)
The time complexity of the attack is approximated byT:(8)T=CN+N+2kin∪kout⋅N2cin+cout⋅CE′+2K⋅P⋅CE,whereCN=maxminΔ∈Δin,ΔoutN⋅2n+1−Δ|,N⋅2n+1−Δin−Δout,CN represents the data complexity needed to construct N plaintext-ciphertext pairs, with N and P satisfying condition (2) above, CE represents the cost for one full-round encryption, and CE′ represents the ratio of the cost for the partial encryption to the full encryption.The memory complexity of the attack is determined byN.(3)
To apply multiple impossible differential cryptanalysis, suppose thatnin⋅nout impossible differential distinguishers are derived from a single distinguisher. With more distinguishers, the time complexity of the attack can also be calculated with equation (8); however, previous Δin and Δout are replaced with Δin′ and Δout′, where Δin′=Δin+log2nin and Δout′=Δout+log2nout.


## 5.1.1. Notations

(i)
ΔXΔY: input (output) difference of the impossible differential distinguisher(ii)
ΔinΔout: set of all the possible input (output) differences of the cipher(iii)
rin: number of rounds of the differential path ΔX,Δin(iv)
rout: number of rounds of the differential path ΔY,Δout(v)
cincout: number of bit conditions that have to be verified to obtain ΔX from ΔinΔYfromΔout(vi)
kinkout: subset of subkey bits involved in the attack during the first rin rounds lastroutrounds(vii)
ΔinΔout: the dimension of the input space (output space)(viii)
N: amount of input (or output) pairs needed for the attack(ix)
P: the probability that a guessed wrong key is kept in the candidate key set(x)
nin: the number of equivalent impossible differential distinguishers with different input differences and same output differences(xi)
nout: the number of equivalent impossible differential distinguishers with same input difference and different output differencesSuppose that the block cipher we are dealing with is of block sizen and a key K of size K.


## 5.1.2. Main Conclusions

The main conclusions are as follows.(1)
The relationship betweenN and P is as follows:(7)P=1−2−cin+coutN<12.The minimum value ofN, denoted by Nmin, is about 2cin+cout.(2)
The time complexity of the attack is approximated byT:(8)T=CN+N+2kin∪kout⋅N2cin+cout⋅CE′+2K⋅P⋅CE,whereCN=maxminΔ∈Δin,ΔoutN⋅2n+1−Δ|,N⋅2n+1−Δin−Δout,CN represents the data complexity needed to construct N plaintext-ciphertext pairs, with N and P satisfying condition (2) above, CE represents the cost for one full-round encryption, and CE′ represents the ratio of the cost for the partial encryption to the full encryption.The memory complexity of the attack is determined byN.(3)
To apply multiple impossible differential cryptanalysis, suppose thatnin⋅nout impossible differential distinguishers are derived from a single distinguisher. With more distinguishers, the time complexity of the attack can also be calculated with equation (8); however, previous Δin and Δout are replaced with Δin′ and Δout′, where Δin′=Δin+log2nin and Δout′=Δout+log2nout.


## 5.2. Procedures of the Attack

### 5.2.1. Data Collection Stage

On one hand, construct 2m data sets. For each data set, to make the difference of a plaintext pair satisfy ΔL0,ΔR0 in Figure 3, there are 34 bits that can be arbitrary value and other 30 bits are fixed to a constant for a data set. On the other hand, suppose that the difference for the output of the 25th round is ΔL25,ΔR25, ΔL27,325=1,ΔR27,325=0 (4 bits).Figure 3
Key recovery attack on 25-round LiCi-2.


### 5.2.2. Key Recovery Stage

In the key recovery stage, we guess the subkey bits in its smallest unit to reduce the complexity. This process is depicted in Figure3 to make it more intuitive. The details for the key recovery stage are illustrated in the following steps:(i)
Step 1. Sieve plaintext-ciphertext pairs according to the difference of the first round and last round. This process can be launched without the key.(i)
Step 1.1. For each plaintext-ciphertext pair, sieve those pairs whose difference for the input and output ofΔS7−40 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise. There are 3 bit conditions for this step.(ii)
Step 1.2. Sieve those pairs whose difference for the input and output ofΔS11−80 satisfies [∗,∗,∗,∗ – ∗,1,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (2 bit conditions).(iii)
Step 1.3. Sieve those pairs whose difference for the input and output ofΔS15−120 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 1.4. Sieve those pairs whose difference for the input and output ofΔS23−200 satisfies [∗, ∗, 1, ∗ – 0, 0, 1, 0]. If the pairs can satisfy the condition, save the pair or discard it otherwise. (3 bit conditions).(v)
Step 1.5 Sieve those pairs whose difference for the input and output ofΔS31−280 satisfies [∗,∗,∗,∗ – ∗,∗,∗,0]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(vi)
Step 1.6. Sieve the remaining pairs withΔL1,ΔR1. If ΔR15−81=0, keep the pair (8 bit conditions).(vii)
Step 1.7. Sieve those pairs whose difference for the input and output ofΔS3−024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(viii)
Step 1.8. Sieve those pairs whose difference for the input and output ofΔS15−1224 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ix)
Step 1.9. Sieve those pairs whose difference for the input and output ofΔS19−1624 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(x)
Step 1.10. Sieve those pairs whose difference for the input and output ofΔS23−2024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(xi)
Step 1.11. Sieve those pairs whose difference for the input and output ofΔS27−2424 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(xii)
Step 1.12. Sieve the remaining pairs withΔR24. If ΔR26−24,19−1524=0,ΔR2324=1, keep the pair (9 bit conditions).(ii)
Step 2. Sieve the plaintext-ciphertext pairs according to the difference of the second round.(i)
Step 2.1. GuessRK11−80 and test whether the difference of ΔS11−81 satisfies the form [∗,∗,∗,∗ – ∗,1,∗,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (2 bit conditions).(ii)
Step 2.2. GuessRK15−120 and test whether the difference of ΔS15−121 satisfies the form [∗,∗,∗,∗ – 0,0,0,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 2.3. GuessRK23−200 and test whether the difference of ΔS23−201 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ivi)
Step 2.4. Sieve the remaining pairs withΔR2. If ΔR23,22,202=0, keep the pair (3 bit conditions).(iii)
Step 3. Sieve the plaintext-ciphertext pairs according to the difference of the 23th round.(i)
Step 3.1. GuessRK14−1124 and test whether the difference for the input and output of ΔS3−023 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ii)
Step 3.2. GuessRK22−1924 and test whether the difference for the input and output of ΔS11−823 satisfies [0,1,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iii)
Step 3.3. GuessRK30−2724 and test whether the difference for the input and output of ΔS19−1623 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 3.4. GuessRK31,2−024 and test whether the difference for the input and output of ΔS23−2023 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(v)
Step 3.5. GuessRK6−324 and test whether the difference for the input and output of ΔS27−2423 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(vi)
Step 3.6. Sieve the remaining pairs withΔR23. If ΔR14−11,9−41=0,ΔR101=1, keep the pair. There are 2 m + 3 plaintext-ciphertext pairs left (11 bit conditions).(iv)
Step 4. Sieve the plaintext-ciphertext pairs according to the difference of the 22th round.(i)
Step 4.1. GuessRK22−1923 and test whether the input and output differences of ΔS11−822 satisfy the form [0,1,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ii)
Step 4.2. GuessRK30−2723 and RK10−724 and test whether the input and output differences of ΔS19−1622 satisfy the form [1,0,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 4.3 GuessRK31,223 and test whether the input and output differences of ΔS23−2022 satisfy the form [1,∗,∗,∗ – ∗,∗,∗,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (1 bit condition). It is noted that RK1,023=RK14,1324 have already been guessed in Step 3.1 and these redundant related keys will not be listed in the rest of the steps for simplicity.(iv)
Step 4.4. Sieve the remaining pairs withΔR22. If ΔR31−28,2−022=0, keep the pair (7 bit conditions).(v)
Step 5. Sieve the plaintext-ciphertext pairs according to the difference of the 3rd round. Guess extra 4 subkey bitsRK23−201 and calculate ΔS23−202. If ΔS23−202 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs and if the pairs can satisfy the condition, save the pair (3 bit conditions).(vi)
Step 6. Sieve the incorrect subkey candidates according to the difference of the 21th round. Guess extra 4 subkey bitsRK22−1922 and test whether the input and output differences of ΔS11−821 satisfy the form [0,1,0,0 – ∗,∗,∗,1] and if ΔR22−2021=0 (6 bit conditions) and if the pairs can satisfy the condition, it will lead to an impossible differential distinguisher; thus the guessed subkey candidate is false. Discard this key candidate and test another one, and iterate this process to reduce the space of key candidates.


## 5.2.1. Data Collection Stage

On one hand, construct 2m data sets. For each data set, to make the difference of a plaintext pair satisfy ΔL0,ΔR0 in Figure 3, there are 34 bits that can be arbitrary value and other 30 bits are fixed to a constant for a data set. On the other hand, suppose that the difference for the output of the 25th round is ΔL25,ΔR25, ΔL27,325=1,ΔR27,325=0 (4 bits).Figure 3
Key recovery attack on 25-round LiCi-2.


## 5.2.2. Key Recovery Stage

In the key recovery stage, we guess the subkey bits in its smallest unit to reduce the complexity. This process is depicted in Figure3 to make it more intuitive. The details for the key recovery stage are illustrated in the following steps:(i)
Step 1. Sieve plaintext-ciphertext pairs according to the difference of the first round and last round. This process can be launched without the key.(i)
Step 1.1. For each plaintext-ciphertext pair, sieve those pairs whose difference for the input and output ofΔS7−40 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise. There are 3 bit conditions for this step.(ii)
Step 1.2. Sieve those pairs whose difference for the input and output ofΔS11−80 satisfies [∗,∗,∗,∗ – ∗,1,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (2 bit conditions).(iii)
Step 1.3. Sieve those pairs whose difference for the input and output ofΔS15−120 satisfies [∗,∗,∗,∗ – 0,0,0,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 1.4. Sieve those pairs whose difference for the input and output ofΔS23−200 satisfies [∗, ∗, 1, ∗ – 0, 0, 1, 0]. If the pairs can satisfy the condition, save the pair or discard it otherwise. (3 bit conditions).(v)
Step 1.5 Sieve those pairs whose difference for the input and output ofΔS31−280 satisfies [∗,∗,∗,∗ – ∗,∗,∗,0]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(vi)
Step 1.6. Sieve the remaining pairs withΔL1,ΔR1. If ΔR15−81=0, keep the pair (8 bit conditions).(vii)
Step 1.7. Sieve those pairs whose difference for the input and output ofΔS3−024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(viii)
Step 1.8. Sieve those pairs whose difference for the input and output ofΔS15−1224 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ix)
Step 1.9. Sieve those pairs whose difference for the input and output ofΔS19−1624 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(x)
Step 1.10. Sieve those pairs whose difference for the input and output ofΔS23−2024 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(xi)
Step 1.11. Sieve those pairs whose difference for the input and output ofΔS27−2424 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(xii)
Step 1.12. Sieve the remaining pairs withΔR24. If ΔR26−24,19−1524=0,ΔR2324=1, keep the pair (9 bit conditions).(ii)
Step 2. Sieve the plaintext-ciphertext pairs according to the difference of the second round.(i)
Step 2.1. GuessRK11−80 and test whether the difference of ΔS11−81 satisfies the form [∗,∗,∗,∗ – ∗,1,∗,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (2 bit conditions).(ii)
Step 2.2. GuessRK15−120 and test whether the difference of ΔS15−121 satisfies the form [∗,∗,∗,∗ – 0,0,0,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 2.3. GuessRK23−200 and test whether the difference of ΔS23−201 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ivi)
Step 2.4. Sieve the remaining pairs withΔR2. If ΔR23,22,202=0, keep the pair (3 bit conditions).(iii)
Step 3. Sieve the plaintext-ciphertext pairs according to the difference of the 23th round.(i)
Step 3.1. GuessRK14−1124 and test whether the difference for the input and output of ΔS3−023 satisfies [0,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(ii)
Step 3.2. GuessRK22−1924 and test whether the difference for the input and output of ΔS11−823 satisfies [0,1,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iii)
Step 3.3. GuessRK30−2724 and test whether the difference for the input and output of ΔS19−1623 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(iv)
Step 3.4. GuessRK31,2−024 and test whether the difference for the input and output of ΔS23−2023 satisfies [1,∗,∗,∗ – ∗,∗,∗,∗]. If the pairs can satisfy the condition, save the pair or discard it otherwise (1 bit condition).(v)
Step 3.5. GuessRK6−324 and test whether the difference for the input and output of ΔS27−2423 satisfies [1,0,0,0 – ∗,∗,∗,1]. If the pairs can satisfy the condition, save the pair or discard it otherwise (3 bit conditions).(vi)
Step 3.6. Sieve the remaining pairs withΔR23. If ΔR14−11,9−41=0,ΔR101=1, keep the pair. There are 2 m + 3 plaintext-ciphertext pairs left (11 bit conditions).(iv)
Step 4. Sieve the plaintext-ciphertext pairs according to the difference of the 22th round.(i)
Step 4.1. GuessRK22−1923 and test whether the input and output differences of ΔS11−822 satisfy the form [0,1,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(ii)
Step 4.2. GuessRK30−2723 and RK10−724 and test whether the input and output differences of ΔS19−1622 satisfy the form [1,0,0,0 – ∗,∗,∗,1] for the remaining pairs. If the pairs can satisfy the condition, save the pair (3 bit conditions).(iii)
Step 4.3 GuessRK31,223 and test whether the input and output differences of ΔS23−2022 satisfy the form [1,∗,∗,∗ – ∗,∗,∗,∗] for the remaining pairs. If the pairs can satisfy the condition, save the pair (1 bit condition). It is noted that RK1,023=RK14,1324 have already been guessed in Step 3.1 and these redundant related keys will not be listed in the rest of the steps for simplicity.(iv)
Step 4.4. Sieve the remaining pairs withΔR22. If ΔR31−28,2−022=0, keep the pair (7 bit conditions).(v)
Step 5. Sieve the plaintext-ciphertext pairs according to the difference of the 3rd round. Guess extra 4 subkey bitsRK23−201 and calculate ΔS23−202. If ΔS23−202 satisfies the form [∗,∗,1,∗ – 0,0,1,0] for the remaining pairs and if the pairs can satisfy the condition, save the pair (3 bit conditions).(vi)
Step 6. Sieve the incorrect subkey candidates according to the difference of the 21th round. Guess extra 4 subkey bitsRK22−1922 and test whether the input and output differences of ΔS11−821 satisfy the form [0,1,0,0 – ∗,∗,∗,1] and if ΔR22−2021=0 (6 bit conditions) and if the pairs can satisfy the condition, it will lead to an impossible differential distinguisher; thus the guessed subkey candidate is false. Discard this key candidate and test another one, and iterate this process to reduce the space of key candidates.


## 5.3. Complexities of the Attack

According to our attack, the values areΔin = 34, Δout = 60, cin = 34, and cout = 60. As the data complexity for this attack always exceeds the full code book, it is infeasible to propose a valid impossible differential cryptanalysis with a single distinguisher. So, we will use multiple distinguishers to reduce this data complexity. Concretely speaking, twenty 18-round distinguishers with the following form are used (all the 65 18-round distinguishers can be found at the Appendix).Input difference:ΔR213=1. Key difference: ΔK110=1Output difference:ΔLi21,ΔRi21=1,i∈0−10,15−18,27−31Sonout = 20 and Δout′=Δout+log2nout=60+4.32=64.32.As there are altogether 23 active Sboxes (50 independent subkey bits) involved in the calculation,CE′=23/8⋅24=2−3.12. According to the equations in Section 5.1, the data complexity, memory complexity, and time complexity for our attack are calculated as follows:Data complexity:CN=maxmin294⋅264+1−34,294⋅264+1−64.32,294⋅264+1−34−64.32=260.68.Memory complexity:N=294 plaintext pairs and corresponding ciphertext pairs.Time complexity:T=260.68+294+250⋅294/294⋅2−3.12+2128⋅0.3679⋅2−3.12≈2123.44 LiCi-2 encryption.


## 6. Conclusion

In this paper, based on the idea of related-key multiple impossible differential cryptanalysis, a full-round attack on LiCi-2 is proposed. As a first step, several properties and observations on LiCi-2 are proposed to give an overall estimation on LiCi-2 against single-key and related-key impossible differential cryptanalysis. Some 18-round related-key impossible differential distinguishers are proposed alongside. As a second step, based on the newly constructed 18-round impossible differential distinguishers, a full-round key recovery attack is presented with adding three rounds before and four rounds after the distinguisher. In the future, some modifications on LiCi-2 are needed to avoid the reported attack.



---

*Source: 3611840-2022-05-25.xml*