# Related-Key Differential Attacks on Reduced-Round LBlock

Authors: Tianling Weng; Tingting Cui; Ting Yang; Yinghua Guo
Journal: Security and Communication Networks
 (2022)

---

## Abstract

LBlock, as one of the typical lightweight encryption schemes, is a 32-round block cipher with 64 bit block and 80 bit master key. It can be widely applied in the IoT environment because of its friendly software and hardware implementations. Since it came out, it has encountered many attacks. In this paper, we evaluate LBlock’s ability against related-key differential attack more accurately based on SMT method. On the one hand, we propose tighter lower bounds on the minimal number of active S-boxes for up to 19 rounds of LBlock, which are 8 more rounds than previous ones. Then, we propose the upper bounds of total probabilities for up to 19 rounds of LBlock for the first time. On the other hand, with a suitable 17-round related-key differential distinguisher, we propose attacks on 22- and 23-round LBlock. Each of these attacks has lower time complexity and data complexity than previous ones for the same rounds of LBlock.


---

## Body

## 1. Introduction

In recent years, the Internet of Things (IoT), as the emerging product of Internet, has been widely applied in industry, agriculture, environment and so on, such as smart transportation and smart medical. In IoT, Radio Frequency Identification (RFID), Sensor Network[1], Machine-to-Machine (M2M) and Cloud Computing are key techniques. However, within them, lots of devices have limited resources, which results in the useless of traditional encryption ciphers to guarantee the security of data. To solve this problem, lightweight encryption schemes are more and more popular, such as PRESENT [2], LED [3], HIGHT [4], LBlock [5], SIMON [6], SPECK [6] and SKINNY [7].As one of the typical lightweight encryption schemes, LBlock is a 32-round block cipher proposed by Wu et al. at ACNS [5]. It adopts a variant Feistel construction with 80 bit master key and 64 bit block. Thanks to its simple round function, it has friendly software and hardware implementations. Its slightly modified version LBlock-s [8] has been used in authenticated encryption scheme LAC in CAESAR competition.Since LBlock was raised, it has encountered differential attacks [9, 10], integral attacks [11], impossible differential attacks [12] and boomerang attacks [13] in both single-key settings and related-key settings. In single-key settings, the designers of LBlock proposed the first impossible differential attack and integral attack on 20-round LBlock in the design document. Then, the impossible differential attack was further improved in [14, 15], and it could attack 22-round LBlock now.In related-key settings, the designers first gave valid related-key differential characteristics for up to 13-round LBlock in the design document [5]. At ASIACRYPT’14, Sun et al. [16] used MILP method to evaluate the lower bounds on the minimal active S-boxes of related-key differential characteristics for reduced rounds of LBlock. In the end, they gave security bounds for reduced 1- to 11-round LBlock, although the bounds were a little relax. Later, Sun et al. [17] improved these results and proposed more accurate bounds for the same reduced rounds of LBlock. Besides that, they found a valid characteristic for 15-round LBlock with 23 active S-boxes. Please note that all bounds in these previous works are measured by the number of active S-boxes instead of the total probability due to high time complexity in the search process, although measuring by probability is more accurate. To recover the key for as many rounds of a cipher as possible, the distinguisher used in the attack usually is expected for as long as possible. How to overcome the shortage in MILP method so as to evaluate more accurate bounds of related-key differential attack on LBlock? This is our first motivation to do this work.Once a good distinguisher is found, we can go on recovering the secret key out. In [14], Liu et al. proposed the first related-key differential attack on 22-round LBlock based on a 16-round truncated differential. Then, Minier and Naya-Plasencia [18] used related-key impossible differential cryptanalysis to attack 22-round LBlock. Then this work was improved by Wen et al. [19]. They built a new searching algorithm to find out a 16-round related-key impossible differential instead of the 15-round one in [18], so they attacked one more round, i.e. 23 rounds. Please note that although the 23-round attack is suitable for all master keys, it needs 4 different related keys totally. This is a more strict requirement than 2 related keys in traditional related-key (impossible) differential attacks. If we can find longer related-key differential characteristics (more than 16 rounds), when we evaluate more accurate security bounds of LBlock, is there any better related-key differential attack on LBlock? This is our second motivation to do this work.In this paper, we evaluate the resistance of LBlock against related-key differential attacks by security bounds based on SMT technique [20] and propose better related-key differential attacks on LBlock. Our contributions are as follows:


### 1.1. Propose More Accurate Bounds of Security against Related-Key Differential Attack on LBlock

In this work, we first propose tighter lower bounds on the minimal number of active S-boxes for up to 19 rounds of LBlock based on the SMT method. Then, we take the total probability of related-key differential characteristic as an objective function to evaluate the ability of LBlock against related-key differential attack and propose the upper bounds of probabilities for up to 19 rounds of LBlock for the first time. All results are summarized in Tables1–3.Table 1
Summary of lower bounds on the minimal number of active S-boxes or upper bound on probability in related-key differential characteristics for reduced-round LBlock (bounds are measured by the number of active S-boxes or total probability).
Objective function# RoundsBoundsReference# Active S-boxes1110[16]# Active S-boxes1326[5]# Active S-boxes1523[17]# Active S-boxes19≤31Section 3Total probability19≥2−75Section 3Table 2
Summary of results about the lower bounds on the number of active S-boxes in related-key differential characteristics under different rounds of LBlock.
RoundsLower boundsThis paper[16][17]100—200—300—400—51116222743486569768109810111110121213——1316——1418——1520—231623——1726——1828——19≤31——Table 3
The upper bounds of probabilities for related-key differential characteristics under different rounds of LBlock.
#RoundsMaximal probability12−022−032−042−052−262−472−882−1292−16102−21112−26122−32132−3914≥2−4515≥2−5116≥2−5517≥2−6318≥2−7019≥2−75


### 1.2. Propose 22- and 23-Round Related-Key Differential Attacks on LBlock

In this work, we first find out a suitable related-key differential distinguisher for 17-round LBlock with SMT method by a special observation and some constraints on input and output differences. This strategy is similar to that in [21] to some extent, aiming to reduce the search space so as to speed up the search according to some suitable observations. With this distinguisher, we propose attacks on 22- and 23-round LBlock. Each of these attacks has lower time complexity and data complexity than previous ones. All results are summarized in Table 4.Table 4
Summary of attacks on LBlock.
Attack type#RoundsTimeData#Keys per attack#Weak keysReferenceBoomerang18270.84263.271280[22]ID20272.72631280[5]Integral20263.7263.71280[5]ID21273.7262.51280[14]ID21269.52631280[15]ID22279.282581280[15]ID23271.82591280[23]RKD22267263.12278[24]RKID222702474278[18]RKD22245.542612270Section 4RKID23278.3261.44280[19]RKD23265.482612270Section 4Remark: ID denotes impossible differential; RKD denotes related-key differential; RKID denotes Related-key impossible differential.


#### 1.2.1. Outline

In Section2, we briefly recall the specification of LBlock and the description of the SMT method. Then, we propose new security bounds against related-key differential attack on LBlock in Section 3. In Section 4, we find out a suitable 17-round related-key differential distinguisher and use it to attack 22- and 23-round LBlock. In the end, we conclude the paper in Section 5.


## 1.1. Propose More Accurate Bounds of Security against Related-Key Differential Attack on LBlock

In this work, we first propose tighter lower bounds on the minimal number of active S-boxes for up to 19 rounds of LBlock based on the SMT method. Then, we take the total probability of related-key differential characteristic as an objective function to evaluate the ability of LBlock against related-key differential attack and propose the upper bounds of probabilities for up to 19 rounds of LBlock for the first time. All results are summarized in Tables1–3.Table 1
Summary of lower bounds on the minimal number of active S-boxes or upper bound on probability in related-key differential characteristics for reduced-round LBlock (bounds are measured by the number of active S-boxes or total probability).
Objective function# RoundsBoundsReference# Active S-boxes1110[16]# Active S-boxes1326[5]# Active S-boxes1523[17]# Active S-boxes19≤31Section 3Total probability19≥2−75Section 3Table 2
Summary of results about the lower bounds on the number of active S-boxes in related-key differential characteristics under different rounds of LBlock.
RoundsLower boundsThis paper[16][17]100—200—300—400—51116222743486569768109810111110121213——1316——1418——1520—231623——1726——1828——19≤31——Table 3
The upper bounds of probabilities for related-key differential characteristics under different rounds of LBlock.
#RoundsMaximal probability12−022−032−042−052−262−472−882−1292−16102−21112−26122−32132−3914≥2−4515≥2−5116≥2−5517≥2−6318≥2−7019≥2−75


## 1.2. Propose 22- and 23-Round Related-Key Differential Attacks on LBlock

In this work, we first find out a suitable related-key differential distinguisher for 17-round LBlock with SMT method by a special observation and some constraints on input and output differences. This strategy is similar to that in [21] to some extent, aiming to reduce the search space so as to speed up the search according to some suitable observations. With this distinguisher, we propose attacks on 22- and 23-round LBlock. Each of these attacks has lower time complexity and data complexity than previous ones. All results are summarized in Table 4.Table 4
Summary of attacks on LBlock.
Attack type#RoundsTimeData#Keys per attack#Weak keysReferenceBoomerang18270.84263.271280[22]ID20272.72631280[5]Integral20263.7263.71280[5]ID21273.7262.51280[14]ID21269.52631280[15]ID22279.282581280[15]ID23271.82591280[23]RKD22267263.12278[24]RKID222702474278[18]RKD22245.542612270Section 4RKID23278.3261.44280[19]RKD23265.482612270Section 4Remark: ID denotes impossible differential; RKD denotes related-key differential; RKID denotes Related-key impossible differential.


### 1.2.1. Outline

In Section2, we briefly recall the specification of LBlock and the description of the SMT method. Then, we propose new security bounds against related-key differential attack on LBlock in Section 3. In Section 4, we find out a suitable 17-round related-key differential distinguisher and use it to attack 22- and 23-round LBlock. In the end, we conclude the paper in Section 5.


## 1.2.1. Outline

In Section2, we briefly recall the specification of LBlock and the description of the SMT method. Then, we propose new security bounds against related-key differential attack on LBlock in Section 3. In Section 4, we find out a suitable 17-round related-key differential distinguisher and use it to attack 22- and 23-round LBlock. In the end, we conclude the paper in Section 5.


## 2. Preliminaries

In this part, we first introduce some notations used in this paper, then briefly recall the specification of LBlock and the description of Simple theorem Prover (STP) Solver.


### 2.1. Notations

In this paper, some notations are defined as follows:NotationDefinitionΔXi32 bits of 64 bit input differenceXi‖Xi−164 bit input of roundiYi32 bit input of S-box layer in roundiZi32 bit output of S-box layer in roundiK80 bit master keyKi32 bit subkey used in roundiki∼jThei-th to j-th bits of master key, 0≤i,j≤79kijThej-th nibble of subkey Ki, j=0,1,…,7FRound function of LBlock⊕Exclusive-OR⋘iLeft rotatei bitsa‖bConcatenation of two binary stringsa,bi2Binary form of an integeri


### 2.2. Specification of LBlock

LBlock [5] is a 32-round lightweight block cipher proposed by Wu et al. at ACNS 2011. It adopts a variant Feistel construction with 80 bit master key and 64 bit block. LBlock’s round function is shown in Figure 1.Figure 1
Round function of LBlock.As we can see from Figure1, the 64 bit input of the i-th round function is divided into two branches named as Xi and Xi−1, then is updated with the following equation to generate 64 bit output Xi+1‖Xi, i=1,2,…,32:(1)Xi+1=FXi⊕Xi−1⋘8.Here symbolF function consists of three parts: AddRoundKey AK, nonlinear S-box layer S and nibble permutation layer P, which are listed as follows:(i)
AddRoundKeyAK: The secret subkey Ki is mixed with input Xi by XOR operation.(ii)
S-box layerS: This layer includes 8 different parallel 4×4 S-boxes S0∼S7 whose specifications are shown in Table 5.(iii)
Nibble Permutation layerP: This layer is a linear symmetric nibble-wise permutation.Table 5
S-boxes used in LBlock.
S014, 9, 15, 0, 13, 4, 10, 11, 1, 2, 8, 3, 7, 6, 12, 5S14, 11, 14, 9, 15, 13, 0, 10, 7, 12, 5, 6, 2, 8, 1, 3S21, 14, 7, 12, 15, 13, 0, 6, 11, 5, 9, 3, 2, 4, 8, 10S37, 6, 8, 11, 0, 15, 3, 14, 9, 10, 12, 13, 5, 2, 4, 1S414, 5, 15, 0, 7, 2, 12, 13, 1, 8, 4, 9, 11, 10, 6, 3S52, 13, 11, 12, 15, 14, 0, 9, 7, 10, 6, 3, 1, 8, 4, 5S611, 9, 4, 14, 0, 15, 10, 13, 6, 12, 5, 7, 3, 8, 1, 2S713, 10, 15, 0, 14, 4, 9, 11, 2, 1, 8, 3, 7, 5, 12, 6S88, 7, 14, 5, 15, 13, 0, 6, 11, 12, 9, 10, 2, 4, 1, 3S911, 5, 15, 0, 7, 2, 9, 13, 4, 8, 1, 12, 14, 10, 3, 6Please note that there is no branch-wise permutation in the last round function and LBlock has totally 32 rounds, so we can denote plaintext asX1‖X0 and ciphertext as X32‖X33.


#### 2.2.1. Key Schedule Algorithm

The master keyK of LBlock has 80 bits, which is stored in a register at very beginning. Without loss of generality, we also denote the master key as K=k79k78…k1k0. The leftmost 32 bits of master key are used as the first subkey K0, then the current register is updated with the following operations in Algorithm 1.Algorithm 1: Key schedule algorithm.
(1)
K0=k79…k48(2)
foriin1,2,…,31doK⋘29k79k78k77k76←S9k79k78k77k76k75k74k73k72←S8k75k74k73k72k50k49k48k47k46←k50k49k48k47k46⊕iKi←k79k78…k48endHereS8 and S9 are two 4 bit S-boxes, which are shown in Table 5. For more details about LBlock, please refer to [5].


### 2.3. Simple theorem Prover

During the last few years, automatic search tools are more and more widely used to search for differential characteristics or linear approximations. One of the tools is Simple theorem Prover (STP) which bases on Satisfiability Modulo Theories (SMT) method. STP [20] is an effective SMT solver originally designed to solve the constraints of bit-vectors and arrays. When searching for differential characteristics with the STP solver, users usually transform such problems into a series of constraints. This solver has been used for cryptanalysis, such as [25–28]. CVC language [20] is STP’s default language. Here, we use Table 6 to list some orders in the CVC language. For more details, please refer to https://stp.readthedocs.io/en/latest/cvc-input-language.html.Table 6
Description of some common orders in CVC language.
NameSymbolExampleConcatenation@t1@t2…@tmExtractioni:jx31:26Left shift≪0bin0011≪3=0bin0011000Bitwise AND&t1&t2&…&tmBitwise XORBVXORBVXORt1,t2Bitvector addBVPLUSBVPLUSn,t1,t2,…,tmGreater than or equal toBVGEBVGEt1,t2In order to describe the STP model clearly, we also give two simple examples as follows.Example 1.
Describea=b⊕c:a:BITVECTOR4;b:BITVECTOR4;c:BITVECTOR4;ASSERTa=BVXORb,c;
The first three statements are to claim thata,b,c are 4 bit variables.Example 2.
S0 is an S-box used in LBlock, the Differential Distribution Table (DDT) of S0 can be described in CVC language as:S0:ARRAY BITVECTOR8OF BITVECTOR1;ASSERTS00bin00000000=0bin1;ASSERTS00bin00000000=0bin0;⋮ASSERTS00bin11111111=0bin0;
In this Example2, BTVECTORi denotes that the variable has i bits. ARRAY BITVECTORiOF BITVECTORj denotes that the input of the array is i bits, and the output is j bits. In the statement of ASSERTS00binx1x2…x8=0biny, the 8 bit x1x2…x8 includes 4 bit input difference x1x2x3x4 and 4 bit output difference x5x6x7x8. If this differential pattern x1x2x3x4⟶x5x6x7x8 is possible in DDT. Then y=1, otherwise y=0.


## 2.1. Notations

In this paper, some notations are defined as follows:NotationDefinitionΔXi32 bits of 64 bit input differenceXi‖Xi−164 bit input of roundiYi32 bit input of S-box layer in roundiZi32 bit output of S-box layer in roundiK80 bit master keyKi32 bit subkey used in roundiki∼jThei-th to j-th bits of master key, 0≤i,j≤79kijThej-th nibble of subkey Ki, j=0,1,…,7FRound function of LBlock⊕Exclusive-OR⋘iLeft rotatei bitsa‖bConcatenation of two binary stringsa,bi2Binary form of an integeri


## 2.2. Specification of LBlock

LBlock [5] is a 32-round lightweight block cipher proposed by Wu et al. at ACNS 2011. It adopts a variant Feistel construction with 80 bit master key and 64 bit block. LBlock’s round function is shown in Figure 1.Figure 1
Round function of LBlock.As we can see from Figure1, the 64 bit input of the i-th round function is divided into two branches named as Xi and Xi−1, then is updated with the following equation to generate 64 bit output Xi+1‖Xi, i=1,2,…,32:(1)Xi+1=FXi⊕Xi−1⋘8.Here symbolF function consists of three parts: AddRoundKey AK, nonlinear S-box layer S and nibble permutation layer P, which are listed as follows:(i)
AddRoundKeyAK: The secret subkey Ki is mixed with input Xi by XOR operation.(ii)
S-box layerS: This layer includes 8 different parallel 4×4 S-boxes S0∼S7 whose specifications are shown in Table 5.(iii)
Nibble Permutation layerP: This layer is a linear symmetric nibble-wise permutation.Table 5
S-boxes used in LBlock.
S014, 9, 15, 0, 13, 4, 10, 11, 1, 2, 8, 3, 7, 6, 12, 5S14, 11, 14, 9, 15, 13, 0, 10, 7, 12, 5, 6, 2, 8, 1, 3S21, 14, 7, 12, 15, 13, 0, 6, 11, 5, 9, 3, 2, 4, 8, 10S37, 6, 8, 11, 0, 15, 3, 14, 9, 10, 12, 13, 5, 2, 4, 1S414, 5, 15, 0, 7, 2, 12, 13, 1, 8, 4, 9, 11, 10, 6, 3S52, 13, 11, 12, 15, 14, 0, 9, 7, 10, 6, 3, 1, 8, 4, 5S611, 9, 4, 14, 0, 15, 10, 13, 6, 12, 5, 7, 3, 8, 1, 2S713, 10, 15, 0, 14, 4, 9, 11, 2, 1, 8, 3, 7, 5, 12, 6S88, 7, 14, 5, 15, 13, 0, 6, 11, 12, 9, 10, 2, 4, 1, 3S911, 5, 15, 0, 7, 2, 9, 13, 4, 8, 1, 12, 14, 10, 3, 6Please note that there is no branch-wise permutation in the last round function and LBlock has totally 32 rounds, so we can denote plaintext asX1‖X0 and ciphertext as X32‖X33.


### 2.2.1. Key Schedule Algorithm

The master keyK of LBlock has 80 bits, which is stored in a register at very beginning. Without loss of generality, we also denote the master key as K=k79k78…k1k0. The leftmost 32 bits of master key are used as the first subkey K0, then the current register is updated with the following operations in Algorithm 1.Algorithm 1: Key schedule algorithm.
(1)
K0=k79…k48(2)
foriin1,2,…,31doK⋘29k79k78k77k76←S9k79k78k77k76k75k74k73k72←S8k75k74k73k72k50k49k48k47k46←k50k49k48k47k46⊕iKi←k79k78…k48endHereS8 and S9 are two 4 bit S-boxes, which are shown in Table 5. For more details about LBlock, please refer to [5].


## 2.2.1. Key Schedule Algorithm

The master keyK of LBlock has 80 bits, which is stored in a register at very beginning. Without loss of generality, we also denote the master key as K=k79k78…k1k0. The leftmost 32 bits of master key are used as the first subkey K0, then the current register is updated with the following operations in Algorithm 1.Algorithm 1: Key schedule algorithm.
(1)
K0=k79…k48(2)
foriin1,2,…,31doK⋘29k79k78k77k76←S9k79k78k77k76k75k74k73k72←S8k75k74k73k72k50k49k48k47k46←k50k49k48k47k46⊕iKi←k79k78…k48endHereS8 and S9 are two 4 bit S-boxes, which are shown in Table 5. For more details about LBlock, please refer to [5].


## 2.3. Simple theorem Prover

During the last few years, automatic search tools are more and more widely used to search for differential characteristics or linear approximations. One of the tools is Simple theorem Prover (STP) which bases on Satisfiability Modulo Theories (SMT) method. STP [20] is an effective SMT solver originally designed to solve the constraints of bit-vectors and arrays. When searching for differential characteristics with the STP solver, users usually transform such problems into a series of constraints. This solver has been used for cryptanalysis, such as [25–28]. CVC language [20] is STP’s default language. Here, we use Table 6 to list some orders in the CVC language. For more details, please refer to https://stp.readthedocs.io/en/latest/cvc-input-language.html.Table 6
Description of some common orders in CVC language.
NameSymbolExampleConcatenation@t1@t2…@tmExtractioni:jx31:26Left shift≪0bin0011≪3=0bin0011000Bitwise AND&t1&t2&…&tmBitwise XORBVXORBVXORt1,t2Bitvector addBVPLUSBVPLUSn,t1,t2,…,tmGreater than or equal toBVGEBVGEt1,t2In order to describe the STP model clearly, we also give two simple examples as follows.Example 1.
Describea=b⊕c:a:BITVECTOR4;b:BITVECTOR4;c:BITVECTOR4;ASSERTa=BVXORb,c;
The first three statements are to claim thata,b,c are 4 bit variables.Example 2.
S0 is an S-box used in LBlock, the Differential Distribution Table (DDT) of S0 can be described in CVC language as:S0:ARRAY BITVECTOR8OF BITVECTOR1;ASSERTS00bin00000000=0bin1;ASSERTS00bin00000000=0bin0;⋮ASSERTS00bin11111111=0bin0;
In this Example2, BTVECTORi denotes that the variable has i bits. ARRAY BITVECTORiOF BITVECTORj denotes that the input of the array is i bits, and the output is j bits. In the statement of ASSERTS00binx1x2…x8=0biny, the 8 bit x1x2…x8 includes 4 bit input difference x1x2x3x4 and 4 bit output difference x5x6x7x8. If this differential pattern x1x2x3x4⟶x5x6x7x8 is possible in DDT. Then y=1, otherwise y=0.


## 3. Evaluate the Resistance of LBlock against Related-Key Differential Attack by Bounds

Taking the total number of active S-boxes as the objective function is a very traditional method to evaluate the resistance of such cipher against related-key differential attack by designers because it is more easier and less time-consuming, especially for byte-wise ciphers. However, taking the maximal probability as the objective function directly results in more precise evaluation. Unluckily, it is more complex and time-consuming, especially for high rounds of a cipher. Attackers usually would like this method to find the best related-key differential characteristic so as to carry out a good attack. In this work, we evaluate the security of LBlock with both ideas.In this section, we use the SMT method to automatically evaluate the resistance of LBlock against related-key differential attack by computing the exact lower bounds on the minimal number of active S-boxes and the upper bounds of the maximal probabilities. As a result, we find out the minimal number of active S-boxes for1∼18 rounds and a lower bound on the number of active S-boxes for 19-round related-key differential characteristics in Subsection 3.1, as well as the maximal probabilities for 1∼13 rounds and upper bounds of probabilities for 14∼19 rounds of related-key differential characteristics in Subsection 3.2.


### 3.1. Lower Bounds on the Minimal Number of Active S-Boxes

Computing the lower bounds on the minimal number of active S-boxes in related-key differential characteristics under different rounds of target cipher, is a common and traditional method to evaluate the ability of a cipher against related-key differential attack. In [16], Sun et al. first proposed bounds on the number of active S-boxes in related-key differential characteristics under different rounds of LBlock. However, because of the time complexity, they could only evaluate under at most 11 rounds of LBlock. Besides that, they found the differential characteristics with the lower bounds on the number of active S-boxes instead of maximal probability for block cipher with 4 × 4 S-boxes. Later, these results were improved in [17] based on MILP method. They gave the exact lower bounds on the number of active S-boxes for 5 ∼ 11 rounds of LBlock. Similarly, because of high time complexity, they only could try to find the bound for high rounds and gave a bound for 15 rounds of LBlock (the program did not run over). Since the MILP-based method which they used could not find the differential characteristic with the maximal probability in practical time, the bounds they proposed still were not the exact lower bounds. All these results are summarized in Table 2.In this work, we use the SMT method to automatically search for the exact lower bounds on the number of active S-boxes in related-key differential characteristics for 1∼19 rounds of LBlock. Firstly, we describe the differential propagations on encryption scheme and key schedule algorithm of LBlock by an STP model in CVC language and add the objective function as a constraint to limit the number of active S-boxes in the model. The whole process is summarized in Algorithm 2. By solving the STP model, the exact lower bounds on the number of active S-boxes for 1∼19 rounds of LBlock can be solved out, which are shown in Table 2.As we can see from Table2, our results are more accurate and strong to show the actual ability of LBlock against related-key differential attack compared with previous related works. Firstly, our work shows there is valid related-key differential characteristic for 19-round LBlock for the first time. As an example, we list one related-key differential characteristic for 19-round LBlock in Table 7. Secondly, we find that the exact lower bound of n-round related-key differential characteristic has 2 or 3 active S-boxes more than the exact lower bound of n−1-round related-key differential characteristic, where 7≤n≤18. In other words, there may be at least 40 active S-boxes for 23-round LBlock, which means there is no valid related-key differential characteristic for 23-round LBlock.Table 7
19-round related-key differential characteristic with 31 active S-boxes (#AS means the number of active S-boxes.).
RdiΔXiΔXi−1ΔKi#AS130000004400010E300003000320000E800300000040000380013000004000000E800000004000400E80000000004000018000015000A000000E80000001C000026E0090000000A000000020000370C800000E00900000C00000028090E00E00C800000060000004906000000090E00E0060000301100E00E0080600000000000018311500000A40E00E008000000183120000000C500000A40000180031300000C000000000C00000C0001400000C0000000C0000000C00015000C000000000C00000C0000016000C0000000C00000006000011700000000000C0000000600002180F000000000000000F000000119000000000F000000090000001203000000F00000000——


### 3.2. Upper Bounds of the Maximal Probabilities

In Subsection3.1, we give the exact lower bounds on the minimal number of active S-boxes for 1∼19 rounds of LBlock by the SMT method to evaluate the ability of LBlock against the related-key differential attack. However, although we have obtained the minimal number of active S-boxes under different rounds of LBlock, we can not directly determine the maximal probability under different rounds. For example, the minimal number of active S-boxes of 12-round related-key differential characteristic is 13. Among such characteristics, their probabilities are in range from 2−26 to 2−39, but actually, the maximal probability for 12-round LBlock is 2−32 (totally 13 active S-boxes). In other words, evaluating the ability against related-key differential attack with the maximal probability can get tighter security bounds, compared with evaluating with the minimal number of active S-boxes. Unfortunately, there is no previous work on searching the upper bound of probabilities for related-key differential characteristics under different rounds of LBlock. In this work, we evaluate the upper bounds of probabilities under different rounds of LBlock by the SMT method.In fact, taking the upper bound of probability as the objective function instead of the number of active S-boxes will slow down the searching speed, especially for high rounds of LBlock.Luckily, by observing the best related-key differential characteristics for short rounds of LBlock, we find an observation as follows.Transforming this observation as a constraint into the STP model can speed up the STP solver and get tighter results for14∼19 rounds.Observation 1 AssumeR1⟶R2⟶⋯⟶Rr7≤r≤13 is an r-round related-key differential characteristic with the maximal probability and Pi1≤i≤r−1 is the probability on the i-th round, there are at least two consecutive rounds with probability of 1. i.e. Pi=1andPi+1=1.For example, we list one of the best related-key differential characteristic for 13-round LBlock in Table8. From this Table, we can see that the probability is 1 on both round 6 and 7.Table 8
Related-key differential characteristic for 13-round LBlock (total probability is2−39).
RdiΔXiΔXi−1ΔKiproi10000020000000020000000002−220000000000000200000000002−030002000000000000001200002−340007000000020000000000002−250000000000070000000000002−360700000000000000070000002−070000000007000000000000002−0800000007000000000000001C2−890000010F00000007D00000002−81000A060000000010F000000002−41100000F4000A0600000000F402−012A060000000000F40000000002−51300204000A0600000000000002−4146001006000204000——We transform the above observation in CVC language as a constraint and add it to the STP model. After that, we can apply Algorithm 3 (similar to Algorithm 2) to search the upper bounds of probabilities for related-key differential characteristics under different rounds of LBlock. The results are shown in Table3.Please note that the probability in Table3 denotes the total probability including both probabilities on cipher itself and on the key schedule. From Table 3, we can see that the best probability of related-key differential charateristic for 19-round LBlock is no less than 2−75.As an example, we give one related-key differential characteristic with high probablity for 19-round LBlock in Table9.Table 9
Related-key differential characteristic for 19-round LBlock (total probability is2−75).
RdiΔXiΔXi−1ΔKiproi1B0000004C000209E000030002−6200009800B0000004000038002−230000040000009800000004002−040098000000000400001800002−35000A000000980000001C00002−4690090000000A0000000200002−770C800000900900000C0000002−68090E00900C800000060000002−10906000000090E0090060000302−2100E00900806000000000000182−711500000A40E009008000000182−7120000000C500000A4000018002−91300000C000000000C00000C002−01400000C0000000C0000000C002−015000C000000000C00000C00002−016000C0000000C0000000600002−31700000000000C0000000600002−5180E000000000000000E0000002−219000000000E000000050000002−2204000000E00000000——Algorithm 2: Get the exact lower bound on the number of active S-boxes by STP model.
(1)
FunctionEncryption Algorithm:(2)
r: the number of rounds(3)
eqn = [ ] //list(4)
fori ← 0 to r − 1 do(5)
Add “ASSERTΔYi=BVXORΔXi,ΔKi;” in eqn(6)
Add “ASSERTS7ΔYi31:28@ΔZi23:20=0bin1;” in eqn(7)
⋮(8)
Add “ASSERTS0ΔYi3:0@ΔZi11:8=0bin1;” in eqn(9)
Add “ASSERTΔXi−123:0@ΔXi−131:24=BVXORΔZi,ΔXi+1;” in eqn//Note: These variables are from Figure 1(10)
end(11)
return eqn(12)(13)
FunctionKey Schedule Algorithm:(14)
r: the number of rounds(15)
eqn = [ ] //list(16)
fori ← 0 to r − 1 do(17)
Add “ASSERTS8ΔKi50:0@ΔKi79:5175:72@ΔKi+175:72=0bin1;” in eqn(18)
Add “ASSERTS9ΔKi50:0@ΔKi79:5179:76@ΔKi+179:76=0bin1;” in eqn(19)
Add “ASSERTΔKi50:0@ΔKi79:5171:70=ΔKi+171:0; ” in eqn(20)
end(21)
return eqn(22)(23)
FunctionMain:(24)
Create a file LBlock.cvc(25)
eqn = [ ] //list(26)
Add “S0:ARRAY BITVECTOR8OF BITVECTOR1;(27)
⋮(28)
S9:ARRAY BITVECTOR8OF BITVECTOR1;(29)
ASSERTS00bin00000000=0bin1;(30)
ASSERTS00bin00000001=0bin0;(31)
⋮(32)
ASSERTS90bin11111110=0bin1;(33)
ASSERTS90bin11111111=0bin0;” in eqn//Describe the differential distribution table ofS0∼S9(34)
eqn + = Encryption Algorithm();(35)
eqn + = Key Schedule Algorithm();(36)(37)
Add “ASSERTBVGTK1,0bin0…0; ” in eqn(38)
Add “ASSERTBVGTBVPLUS8,0bin0000000@k150:0@k179:5175:723:3k150:0@k179:5175:722:2k150:0@k179:5175:721:1|k150:@k179:5175:720:0,…,0bin0000000@Xr−13:03:3|Xr−13:02:2|Xr−13:01:1|Xr−13:00:0,0bin00000000;” in eqn(39)
write eqn in LBlock.cvc(40)(41)
stp LBlock.cvcAlgorithm 3: Get the upper bounds of probability by STP model.
(1)
FunctionEncryption Algorithm:(2)
r: the number of rounds(3)
eqn = [ ] //list(4)
fori ← 0 to r − 1 do(5)
Add “ASSERTΔYi=BVXORΔXi,ΔKi;” in eqn(6)
Add “ASSERTNOTS7ΔYi31:28@ΔZi23:20=0bin01;” in eqn(7)
⋮(8)
Add “ASSERTNOTS0ΔYi3:0@ΔZi11:8=0bin01;” in eqn(9)
Add “ASSERTΔXi−123:0@ΔXi−131:24=BVXORΔZi,ΔXi+1; ” in eqn(10)
end(11)
return eqn(12)(13)
FunctionKey Schedule Algorithm:(14)
r: the number of rounds(15)
eqn = [ ] //list(16)
fori ← 0 to r − 1 do(17)
Add “ASSERTNOTS8ΔKi50:0@ΔKi79:5175:72@ΔKi+175:72=0bin01;” in eqn(18)
Add “ASSERTNOTS9ΔKi50:0@ΔKi79:5179:76@ΔKi+179:76=0bin01;” in eqn(19)
Add “ASSERTΔKi50:0@ΔKi79:5171:0=ΔKi+171:0;” in eqn(20)
end(21)
return eqn(22)(23)
FunctionMain:(24)
Create a file LBlock.cvc(25)
eqn = [ ] //list(26)
Add “S0:ARRAY BITVECTOR8OF BITVECTOR2;(27)
⋮(28)
S9:ARRAY BITVECTOR8OF BITVECTOR2;(29)
ASSERTS00bin00000000=0bin00;(30)
ASSERTS00bin00000000=0bin01;(31)
⋮(32)
ASSERTS90bin00000000=0bin11;(33)
ASSERTS90bin11111111=0bin01;” in eqn(34)
eqn + = Encryption Algorithm();(35)
eqn + = Key Schedule Algorithm();(36)(37)
Add “ASSERTY0=0x00000000ANDY1=0x00000000OR…ORYr−1=0x00000000ANDYr=0x00000000;” in eqn(38)
Add “ASSERTBVGTK1,0bin0⋯0;” in eqn(39)
Add “ASSERTBVGTBVPLUS10,0bin00000000@S8k150:0@k179:5175:72@k275:72,0bin00000000@S9k150:0@k179:5179:76@k279:76,…,0bin00000000@S1Yr7:4@Zr3:0,0bin00000000@S0Yr3:0@Zr11:8,0bin00000000;” in eqn(40)
write eqn in LBlock.cvc 19(41)(42)
stp LBlock.cvc


## 3.1. Lower Bounds on the Minimal Number of Active S-Boxes

Computing the lower bounds on the minimal number of active S-boxes in related-key differential characteristics under different rounds of target cipher, is a common and traditional method to evaluate the ability of a cipher against related-key differential attack. In [16], Sun et al. first proposed bounds on the number of active S-boxes in related-key differential characteristics under different rounds of LBlock. However, because of the time complexity, they could only evaluate under at most 11 rounds of LBlock. Besides that, they found the differential characteristics with the lower bounds on the number of active S-boxes instead of maximal probability for block cipher with 4 × 4 S-boxes. Later, these results were improved in [17] based on MILP method. They gave the exact lower bounds on the number of active S-boxes for 5 ∼ 11 rounds of LBlock. Similarly, because of high time complexity, they only could try to find the bound for high rounds and gave a bound for 15 rounds of LBlock (the program did not run over). Since the MILP-based method which they used could not find the differential characteristic with the maximal probability in practical time, the bounds they proposed still were not the exact lower bounds. All these results are summarized in Table 2.In this work, we use the SMT method to automatically search for the exact lower bounds on the number of active S-boxes in related-key differential characteristics for 1∼19 rounds of LBlock. Firstly, we describe the differential propagations on encryption scheme and key schedule algorithm of LBlock by an STP model in CVC language and add the objective function as a constraint to limit the number of active S-boxes in the model. The whole process is summarized in Algorithm 2. By solving the STP model, the exact lower bounds on the number of active S-boxes for 1∼19 rounds of LBlock can be solved out, which are shown in Table 2.As we can see from Table2, our results are more accurate and strong to show the actual ability of LBlock against related-key differential attack compared with previous related works. Firstly, our work shows there is valid related-key differential characteristic for 19-round LBlock for the first time. As an example, we list one related-key differential characteristic for 19-round LBlock in Table 7. Secondly, we find that the exact lower bound of n-round related-key differential characteristic has 2 or 3 active S-boxes more than the exact lower bound of n−1-round related-key differential characteristic, where 7≤n≤18. In other words, there may be at least 40 active S-boxes for 23-round LBlock, which means there is no valid related-key differential characteristic for 23-round LBlock.Table 7
19-round related-key differential characteristic with 31 active S-boxes (#AS means the number of active S-boxes.).
RdiΔXiΔXi−1ΔKi#AS130000004400010E300003000320000E800300000040000380013000004000000E800000004000400E80000000004000018000015000A000000E80000001C000026E0090000000A000000020000370C800000E00900000C00000028090E00E00C800000060000004906000000090E00E0060000301100E00E0080600000000000018311500000A40E00E008000000183120000000C500000A40000180031300000C000000000C00000C0001400000C0000000C0000000C00015000C000000000C00000C0000016000C0000000C00000006000011700000000000C0000000600002180F000000000000000F000000119000000000F000000090000001203000000F00000000——


## 3.2. Upper Bounds of the Maximal Probabilities

In Subsection3.1, we give the exact lower bounds on the minimal number of active S-boxes for 1∼19 rounds of LBlock by the SMT method to evaluate the ability of LBlock against the related-key differential attack. However, although we have obtained the minimal number of active S-boxes under different rounds of LBlock, we can not directly determine the maximal probability under different rounds. For example, the minimal number of active S-boxes of 12-round related-key differential characteristic is 13. Among such characteristics, their probabilities are in range from 2−26 to 2−39, but actually, the maximal probability for 12-round LBlock is 2−32 (totally 13 active S-boxes). In other words, evaluating the ability against related-key differential attack with the maximal probability can get tighter security bounds, compared with evaluating with the minimal number of active S-boxes. Unfortunately, there is no previous work on searching the upper bound of probabilities for related-key differential characteristics under different rounds of LBlock. In this work, we evaluate the upper bounds of probabilities under different rounds of LBlock by the SMT method.In fact, taking the upper bound of probability as the objective function instead of the number of active S-boxes will slow down the searching speed, especially for high rounds of LBlock.Luckily, by observing the best related-key differential characteristics for short rounds of LBlock, we find an observation as follows.Transforming this observation as a constraint into the STP model can speed up the STP solver and get tighter results for14∼19 rounds.Observation 1 AssumeR1⟶R2⟶⋯⟶Rr7≤r≤13 is an r-round related-key differential characteristic with the maximal probability and Pi1≤i≤r−1 is the probability on the i-th round, there are at least two consecutive rounds with probability of 1. i.e. Pi=1andPi+1=1.For example, we list one of the best related-key differential characteristic for 13-round LBlock in Table8. From this Table, we can see that the probability is 1 on both round 6 and 7.Table 8
Related-key differential characteristic for 13-round LBlock (total probability is2−39).
RdiΔXiΔXi−1ΔKiproi10000020000000020000000002−220000000000000200000000002−030002000000000000001200002−340007000000020000000000002−250000000000070000000000002−360700000000000000070000002−070000000007000000000000002−0800000007000000000000001C2−890000010F00000007D00000002−81000A060000000010F000000002−41100000F4000A0600000000F402−012A060000000000F40000000002−51300204000A0600000000000002−4146001006000204000——We transform the above observation in CVC language as a constraint and add it to the STP model. After that, we can apply Algorithm 3 (similar to Algorithm 2) to search the upper bounds of probabilities for related-key differential characteristics under different rounds of LBlock. The results are shown in Table3.Please note that the probability in Table3 denotes the total probability including both probabilities on cipher itself and on the key schedule. From Table 3, we can see that the best probability of related-key differential charateristic for 19-round LBlock is no less than 2−75.As an example, we give one related-key differential characteristic with high probablity for 19-round LBlock in Table9.Table 9
Related-key differential characteristic for 19-round LBlock (total probability is2−75).
RdiΔXiΔXi−1ΔKiproi1B0000004C000209E000030002−6200009800B0000004000038002−230000040000009800000004002−040098000000000400001800002−35000A000000980000001C00002−4690090000000A0000000200002−770C800000900900000C0000002−68090E00900C800000060000002−10906000000090E0090060000302−2100E00900806000000000000182−711500000A40E009008000000182−7120000000C500000A4000018002−91300000C000000000C00000C002−01400000C0000000C0000000C002−015000C000000000C00000C00002−016000C0000000C0000000600002−31700000000000C0000000600002−5180E000000000000000E0000002−219000000000E000000050000002−2204000000E00000000——Algorithm 2: Get the exact lower bound on the number of active S-boxes by STP model.
(1)
FunctionEncryption Algorithm:(2)
r: the number of rounds(3)
eqn = [ ] //list(4)
fori ← 0 to r − 1 do(5)
Add “ASSERTΔYi=BVXORΔXi,ΔKi;” in eqn(6)
Add “ASSERTS7ΔYi31:28@ΔZi23:20=0bin1;” in eqn(7)
⋮(8)
Add “ASSERTS0ΔYi3:0@ΔZi11:8=0bin1;” in eqn(9)
Add “ASSERTΔXi−123:0@ΔXi−131:24=BVXORΔZi,ΔXi+1;” in eqn//Note: These variables are from Figure 1(10)
end(11)
return eqn(12)(13)
FunctionKey Schedule Algorithm:(14)
r: the number of rounds(15)
eqn = [ ] //list(16)
fori ← 0 to r − 1 do(17)
Add “ASSERTS8ΔKi50:0@ΔKi79:5175:72@ΔKi+175:72=0bin1;” in eqn(18)
Add “ASSERTS9ΔKi50:0@ΔKi79:5179:76@ΔKi+179:76=0bin1;” in eqn(19)
Add “ASSERTΔKi50:0@ΔKi79:5171:70=ΔKi+171:0; ” in eqn(20)
end(21)
return eqn(22)(23)
FunctionMain:(24)
Create a file LBlock.cvc(25)
eqn = [ ] //list(26)
Add “S0:ARRAY BITVECTOR8OF BITVECTOR1;(27)
⋮(28)
S9:ARRAY BITVECTOR8OF BITVECTOR1;(29)
ASSERTS00bin00000000=0bin1;(30)
ASSERTS00bin00000001=0bin0;(31)
⋮(32)
ASSERTS90bin11111110=0bin1;(33)
ASSERTS90bin11111111=0bin0;” in eqn//Describe the differential distribution table ofS0∼S9(34)
eqn + = Encryption Algorithm();(35)
eqn + = Key Schedule Algorithm();(36)(37)
Add “ASSERTBVGTK1,0bin0…0; ” in eqn(38)
Add “ASSERTBVGTBVPLUS8,0bin0000000@k150:0@k179:5175:723:3k150:0@k179:5175:722:2k150:0@k179:5175:721:1|k150:@k179:5175:720:0,…,0bin0000000@Xr−13:03:3|Xr−13:02:2|Xr−13:01:1|Xr−13:00:0,0bin00000000;” in eqn(39)
write eqn in LBlock.cvc(40)(41)
stp LBlock.cvcAlgorithm 3: Get the upper bounds of probability by STP model.
(1)
FunctionEncryption Algorithm:(2)
r: the number of rounds(3)
eqn = [ ] //list(4)
fori ← 0 to r − 1 do(5)
Add “ASSERTΔYi=BVXORΔXi,ΔKi;” in eqn(6)
Add “ASSERTNOTS7ΔYi31:28@ΔZi23:20=0bin01;” in eqn(7)
⋮(8)
Add “ASSERTNOTS0ΔYi3:0@ΔZi11:8=0bin01;” in eqn(9)
Add “ASSERTΔXi−123:0@ΔXi−131:24=BVXORΔZi,ΔXi+1; ” in eqn(10)
end(11)
return eqn(12)(13)
FunctionKey Schedule Algorithm:(14)
r: the number of rounds(15)
eqn = [ ] //list(16)
fori ← 0 to r − 1 do(17)
Add “ASSERTNOTS8ΔKi50:0@ΔKi79:5175:72@ΔKi+175:72=0bin01;” in eqn(18)
Add “ASSERTNOTS9ΔKi50:0@ΔKi79:5179:76@ΔKi+179:76=0bin01;” in eqn(19)
Add “ASSERTΔKi50:0@ΔKi79:5171:0=ΔKi+171:0;” in eqn(20)
end(21)
return eqn(22)(23)
FunctionMain:(24)
Create a file LBlock.cvc(25)
eqn = [ ] //list(26)
Add “S0:ARRAY BITVECTOR8OF BITVECTOR2;(27)
⋮(28)
S9:ARRAY BITVECTOR8OF BITVECTOR2;(29)
ASSERTS00bin00000000=0bin00;(30)
ASSERTS00bin00000000=0bin01;(31)
⋮(32)
ASSERTS90bin00000000=0bin11;(33)
ASSERTS90bin11111111=0bin01;” in eqn(34)
eqn + = Encryption Algorithm();(35)
eqn + = Key Schedule Algorithm();(36)(37)
Add “ASSERTY0=0x00000000ANDY1=0x00000000OR…ORYr−1=0x00000000ANDYr=0x00000000;” in eqn(38)
Add “ASSERTBVGTK1,0bin0⋯0;” in eqn(39)
Add “ASSERTBVGTBVPLUS10,0bin00000000@S8k150:0@k179:5175:72@k275:72,0bin00000000@S9k150:0@k179:5179:76@k279:76,…,0bin00000000@S1Yr7:4@Zr3:0,0bin00000000@S0Yr3:0@Zr11:8,0bin00000000;” in eqn(40)
write eqn in LBlock.cvc 19(41)(42)
stp LBlock.cvc


## 4. Related-Key Differential Attacks on LBlock

In this section, we propose the best related-key differential attacks on LBlock as far as we know. Firstly, we search out a suitable 17-round related-key differential distinguisher on LBlock by combining the techniques used in Section3.2 and some extra constraints, which are described in Subsection 4.1. Then, based on this distinguisher, we propose the best related-key differential attacks on 22-round and 23-round LBlock in Subsections 4.2 and 4.3 respectively.


### 4.1. Automatic Search for Suitable Related-Key Differential Distinguishers on LBlock

A related-key differential attack consists of a suitable related-key differential characteristic and a key-recovery phase. In most cases, the longer rounds an attack achieves on a cipher, the better such attack is. Thus, the related-key differential distinguisher is expected as long as possible, while the corresponding key-recovery phase is expected to involve more rounds. However, there is a tradeoff between the related-key differential distinguisher and key-recovery phase. The longest related-key differential characteristic with the largest probability may not result in the best attack because it may lead to fast diffusion and confusion in the key-recovery phase, further leading to attack fewer rounds. Generally, In order to enhance the effect in the key-recovery phase, few active nibbles are expected on input and output differences of related-key differential distinguisher.In this part, we combine the automatic search method used in section3.2 and extra constraints on input and output differences of distinguisher to search out a good related-key differential distinguisher which is very suitable to implement the best attack on LBlock. In detail, some requirements and constraints in the automatic search method of suitable r-round related-key differential distinguisher are listed as follows:(i)
Assume the input and output differences of targetr-round related-key differential characteristic are ΔX1,ΔX0 and ΔXr+1,ΔXr respectively, we require that HwnibbleΔXi≤2,i=0,1,r,r+1, where HwnibbleX denotes the number of active nibbles in state X;(ii)
There exist consecutive two rounds with probability 1 in the related-key differential characteristic, which is exactly the requirement in Observation 1;(iii)
In order to adapt key-recovery attack on most cases of masterkey, we limit the probability on the key schedule isprokey≥2−10;(iv)
General requirement: the number of active nibbles on masterkeyΔK satisfies HwnibbleΔK≥1;(v)
Objective function: maximize the probability on cipher itselfprocipher.As a result, we finally find a suitable 17-round related-key differential characteristic, whose total probability is2−70 including 2−60 on cipher itself and 2−10 on the key schedule. This characteristic is listed in Table 10.Table 10
17-round related-key differential characteristic with total probabilitypro=2−70 including procipher=2−60 on cipher itself and prokey=2−10 on the key schedule.
RdiΔXiΔXi−1ΔKiproi10000080000100003000008002−021000030000000800000008002−530078200010000300001800002−440007000000782000000400002−257020000000070000000400002−960D410000702000000C0000002−87010600700D410000060000002−980600000001060070060000302−290600700806000000000000182−610100000E406007008000000182−9110000000C100000E4000018002−81200000C000000000C00000C002−01300000C0000000C0000000C002−014000C000000000C00000C00002−015000C0000000C0000000600002−31600000000000C0000000600002−5170E000000000000000E0000002−018000000000E000000--In this 17-round related-key differential characteristic, there are 4 active S-boxes within the key schedule that are distributed on theS8 of rounds 6, 7, 8 and 17. In round 6, the differential pattern passing S8 is 1100⟶S81100 with probability 2−3. According to the difference distribution table of S8, there are two cases for k61,k6′1 that is 0111,1011 and 1011,0111, where kij means the j-th nibble of subkey in round i. Similarly, we can analyze the differential patterns on S8 in rounds 7, 8 and 17, which are summarized in Table 11.Table 11
Differential patterns on active S-boxes in the key schedule of 17-round related-key differential characteristic.
RdiΔinΔoutproInput pairski1,ki′16110011002−30111,1011, 1011,01117001001102−20000,0010, 0010,0000, 1100,1010, 1010,11008001001102−20000,0010, 0010,0000, 1100,1010, 1010,110017011011102−31011,1101, 1101,1011


### 4.2. Related-Key Differential Attack on 22-Round LBlock

In subsection4.1, we search out an expected 17-round related-key differential distinguisher on LBlock, whose total probability is 2−70 including 2−60 on cipher itself and 2−10 on the key schedule. In this subsection, we extend three rounds before this distinguisher and two rounds behind this distinguisher to attack 22-round LBlock. It is shown in Figure 2.Figure 2
Related-key differential attack on 22-round LBlock.


#### 4.2.1. Data Collection

From Figure2, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗000000E,∗0∗00∗0∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts.Since each structure composes264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


#### 4.2.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−44=2x+20 pairs remained after the filtering on ciphertext.


#### 4.2.3. Filtering on Rounds1∼3

In this part, we guess the subkey nibblesk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 one by one to filter pairs. Which are summarized within steps 1∼11 in Table 12. Taking step 1 as an example, we explain how we filter pairs in detail.Table 12
Related-key differential attack process on 22-round LBlock.
StepSubkeyMasterkey#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+202x+162k10k51∼483k50∼482×25×2x+162x+123k16k75∼7242×29×2x+122x+84k27k50∼471k472×210×2x+82x+45k13k63∼6042×214×2x+42x6k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x2x−47k20k22∼193k21∼192×220×2x−42x−88k22k30∼2742×224×2x−82x−129k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x−122x−1610k30k73∼702k71∼702×229×2x−162x−2011k35k13∼1042×233×2x−202x−2412k226k32∼222k32∼312×235×2x−242x−2813k221k17∼04k2212×239×2x−282x−3214k216k61∼514k59∼562×243×2x−322x−3615k220k77∼104k2202×247×2x−362x−4016k227k39∼264k2272×251×2x−402x−44In this step, we need to guess 4 bits subkeyk11 corresponding to the master key k55∼52. Note that we know k11=k55∼52 according to the key schedule algorithm of LBlock. Since k54, k53 and k52 are already known, it is only necessary to guess k55 so as to obtain the value of k11.Please note thatk54∼52 has 2 possible cases, which is equivalent to guessing one more bit. Under each out of 22 possible values of k11, we can calculate the output difference of S7 in round 1 for each plaintext pair, and check whether it equals the third nibble of ΔX0. If not, we filter out the current plaintext pair. Otherwise, we remain it and go next step. Totally, it needs 2×22×2x+20 operations on Sbox in step 1, while 2x+16 plaintext pairs are remained on average after step 1 because the probability is 2−4. The similar idea is applied on steps 2∼11.Sometimes, instead of considering the subkey nibbles independently, we would like to focus on their related masterkey bits according to the key schedule. Thanks to the slow diffusion of LBlock’s key schedule, the corresponding masterkey bits ofk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 are k55∼52, k51∼48, k75∼72, k50∼47, k63∼60, k26∼23, k22∼19, k30∼27, k78∼1, k73∼70 and k13∼10, respectively. However, please note that there are only 2 cases for k3∼0, 4 cases for k54∼51 and 4 cases for k25∼22 because of the 17-round related-key differential distinguisher. Thus, in step 1, we only need to guess k55 and 2 cases of k54∼51 (We all know that there are two encryption machines with different masterkeys in related-key setting. Here, we don’t fix k79∼0 to a certain machine, so there are only two cases for k54∼51. Once we recover all masterkey bits, we finally check which machine such masterkey belongs to.). The time complexity of this step is 2×22×2x+20=2x+23, and the number of pairs remained is 2x+20×2−4=2x+16. Similarly, we can handle other subkey nibbles on rounds 1∼3 within steps 2∼11. Finally, 33 bits of masterkey are guessed in this part, and 2x−24 pairs are left.


#### 4.2.4. Filtering on Rounds21∼22

In this part, we guess the subkey nibblesk226, k221, k216, k220, k227 one by one to further filter pairs, which are summarized within steps 12∼16 in Table 12. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, while k216 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 51 bits of key information (including 39 masterkey bits and 12 subkey bits) guessed.


#### 4.2.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


#### 4.2.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under tthe right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼16 when filtering on rounds 1∼3 and 21∼22, which are listed in Table 12 one by one step. By summing the time complexities of all steps, the total time is about 245.54 22-round encryptions, which is(2)252+2×251+2×248+247+2×246+245+2×243+5×241×18×122=245.54.According to [29], the signal-to-noise ratio is(3)SN=2κ−1pλγ−p,where p denotes the probability of the related-key differential distinguisher, κ denotes number of key bits to recover, λ denotes the probability that a pair survives the filtering, γ denotes keys suggested by each pair surviving the filtering.Based on signal-to-noise ratioSN, the success probability of attack is(4)Ps=ϕμSN−ϕ−11−2−aSN+1,where μ denotes that the number of the right pairs, a denotes that a-bit advantage.We can calculate that signal-to-noise ratio isSN=251−12−60/2−44−2−60=235, when μ=2,a=51. Thus, Ps=92.1% according to equation (4).


### 4.3. Related-Key Differential Attack on 23-Round LBlock

In Subsection4.1, we search out an expected 17-round related-key differential distinguisher on LBlock, whose total probability is 2−70 including 2−60 on cipher itself and 2−10 on the key schedule. In this subsection, we extend three rounds before this distinguisher and three rounds behind this distinguisher to attack 23-round LBlock. It is shown in Figure 3.Figure 3
Related-key differential attack on 23-round LBlock.


#### 4.3.1. Data Collection

From Figure3, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗0∗00∗0∗,00∗∗∗∗∗∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts. Since each structure composes 264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


#### 4.3.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−24=2x+40 pairs remained after the filtering on ciphertext.


#### 4.3.3. Filtering on Rounds1∼3

In this part, because we are using the same distinguisher as that in 22-round attack, the details are the same as the Filtering on rounds1∼3 in Subsection 4.2.


#### 4.3.4. Filtering on Rounds21∼23

In this part, we guess the subkey nibblesk231, k226, k235, k237, k232, k230, k221, k216, k220, k233, k227 one by one to further filter pairs, which are summarized within steps 12∼21 in Table 13. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, k235 can be calculated by the masterkey bits k76∼69 in which there are only 2 unknown bits k76 and k69, k216 can be calculated by the masterkey bits k61∼51 in which there are not unknown bits, while k230 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 65 bits of key information (including 37 masterkey bits and 28 subkey bits) guessed.Table 13
Related-key differential attack process on 23-round LBlock.
StepSubkeyMaster Key#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+402x+362k10k51∼483k50∼482×25×2x+362x+323k16k75∼7242×29×2x+322x+284k27k50∼471k472×210×2x+282x+245k13k63∼6042×214×2x+242x+206k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x+202x+167k20k22∼193k21∼192×220×2x+162x+128k22k30∼2742×224×2x+122x+89k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x+82x+410k30k73∼702k71∼702×229×2x+42x11k35k13∼1042×233×2x2x−412k231k68∼514k2312×237×2x−42x−813k226k32∼222k32∼312×239×2x−82x−1214k235k76∼692k76,k692×241×2x−122x−1615k237k77∼104k2372×245×2x−162x−2016k232k68∼554k2322×249×2x−202x−2417k230k61∼474k59∼562×253×2x−242x−2818k221k17∼04k2212×257×2x−282x−3219k216k61∼5102×257×2x−322x−3620k220k77∼104k2202×261×2x−362x−4021k233k227k72∼58k39∼268 (k233k227)2×269×2x−402x−44


#### 4.3.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


#### 4.3.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼21 when filtering on rounds 1∼3 and 21∼23, which are listed in Table 13 one by one step. By summing the time complexities of all steps, the total time is about 265.48 23-round encryptions, which is(5)272+2×271+2×268+267+2×266+265+2×263+7×261+2×256×18×123=265.48.According to equations (3) and (4), the signal-to-noise ratio is SN=265−12−60/2−24−2−60=229, when μ=2,a=65, so the final success rate is Ps=92.1%.


## 4.1. Automatic Search for Suitable Related-Key Differential Distinguishers on LBlock

A related-key differential attack consists of a suitable related-key differential characteristic and a key-recovery phase. In most cases, the longer rounds an attack achieves on a cipher, the better such attack is. Thus, the related-key differential distinguisher is expected as long as possible, while the corresponding key-recovery phase is expected to involve more rounds. However, there is a tradeoff between the related-key differential distinguisher and key-recovery phase. The longest related-key differential characteristic with the largest probability may not result in the best attack because it may lead to fast diffusion and confusion in the key-recovery phase, further leading to attack fewer rounds. Generally, In order to enhance the effect in the key-recovery phase, few active nibbles are expected on input and output differences of related-key differential distinguisher.In this part, we combine the automatic search method used in section3.2 and extra constraints on input and output differences of distinguisher to search out a good related-key differential distinguisher which is very suitable to implement the best attack on LBlock. In detail, some requirements and constraints in the automatic search method of suitable r-round related-key differential distinguisher are listed as follows:(i)
Assume the input and output differences of targetr-round related-key differential characteristic are ΔX1,ΔX0 and ΔXr+1,ΔXr respectively, we require that HwnibbleΔXi≤2,i=0,1,r,r+1, where HwnibbleX denotes the number of active nibbles in state X;(ii)
There exist consecutive two rounds with probability 1 in the related-key differential characteristic, which is exactly the requirement in Observation 1;(iii)
In order to adapt key-recovery attack on most cases of masterkey, we limit the probability on the key schedule isprokey≥2−10;(iv)
General requirement: the number of active nibbles on masterkeyΔK satisfies HwnibbleΔK≥1;(v)
Objective function: maximize the probability on cipher itselfprocipher.As a result, we finally find a suitable 17-round related-key differential characteristic, whose total probability is2−70 including 2−60 on cipher itself and 2−10 on the key schedule. This characteristic is listed in Table 10.Table 10
17-round related-key differential characteristic with total probabilitypro=2−70 including procipher=2−60 on cipher itself and prokey=2−10 on the key schedule.
RdiΔXiΔXi−1ΔKiproi10000080000100003000008002−021000030000000800000008002−530078200010000300001800002−440007000000782000000400002−257020000000070000000400002−960D410000702000000C0000002−87010600700D410000060000002−980600000001060070060000302−290600700806000000000000182−610100000E406007008000000182−9110000000C100000E4000018002−81200000C000000000C00000C002−01300000C0000000C0000000C002−014000C000000000C00000C00002−015000C0000000C0000000600002−31600000000000C0000000600002−5170E000000000000000E0000002−018000000000E000000--In this 17-round related-key differential characteristic, there are 4 active S-boxes within the key schedule that are distributed on theS8 of rounds 6, 7, 8 and 17. In round 6, the differential pattern passing S8 is 1100⟶S81100 with probability 2−3. According to the difference distribution table of S8, there are two cases for k61,k6′1 that is 0111,1011 and 1011,0111, where kij means the j-th nibble of subkey in round i. Similarly, we can analyze the differential patterns on S8 in rounds 7, 8 and 17, which are summarized in Table 11.Table 11
Differential patterns on active S-boxes in the key schedule of 17-round related-key differential characteristic.
RdiΔinΔoutproInput pairski1,ki′16110011002−30111,1011, 1011,01117001001102−20000,0010, 0010,0000, 1100,1010, 1010,11008001001102−20000,0010, 0010,0000, 1100,1010, 1010,110017011011102−31011,1101, 1101,1011


## 4.2. Related-Key Differential Attack on 22-Round LBlock

In subsection4.1, we search out an expected 17-round related-key differential distinguisher on LBlock, whose total probability is 2−70 including 2−60 on cipher itself and 2−10 on the key schedule. In this subsection, we extend three rounds before this distinguisher and two rounds behind this distinguisher to attack 22-round LBlock. It is shown in Figure 2.Figure 2
Related-key differential attack on 22-round LBlock.


### 4.2.1. Data Collection

From Figure2, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗000000E,∗0∗00∗0∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts.Since each structure composes264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


### 4.2.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−44=2x+20 pairs remained after the filtering on ciphertext.


### 4.2.3. Filtering on Rounds1∼3

In this part, we guess the subkey nibblesk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 one by one to filter pairs. Which are summarized within steps 1∼11 in Table 12. Taking step 1 as an example, we explain how we filter pairs in detail.Table 12
Related-key differential attack process on 22-round LBlock.
StepSubkeyMasterkey#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+202x+162k10k51∼483k50∼482×25×2x+162x+123k16k75∼7242×29×2x+122x+84k27k50∼471k472×210×2x+82x+45k13k63∼6042×214×2x+42x6k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x2x−47k20k22∼193k21∼192×220×2x−42x−88k22k30∼2742×224×2x−82x−129k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x−122x−1610k30k73∼702k71∼702×229×2x−162x−2011k35k13∼1042×233×2x−202x−2412k226k32∼222k32∼312×235×2x−242x−2813k221k17∼04k2212×239×2x−282x−3214k216k61∼514k59∼562×243×2x−322x−3615k220k77∼104k2202×247×2x−362x−4016k227k39∼264k2272×251×2x−402x−44In this step, we need to guess 4 bits subkeyk11 corresponding to the master key k55∼52. Note that we know k11=k55∼52 according to the key schedule algorithm of LBlock. Since k54, k53 and k52 are already known, it is only necessary to guess k55 so as to obtain the value of k11.Please note thatk54∼52 has 2 possible cases, which is equivalent to guessing one more bit. Under each out of 22 possible values of k11, we can calculate the output difference of S7 in round 1 for each plaintext pair, and check whether it equals the third nibble of ΔX0. If not, we filter out the current plaintext pair. Otherwise, we remain it and go next step. Totally, it needs 2×22×2x+20 operations on Sbox in step 1, while 2x+16 plaintext pairs are remained on average after step 1 because the probability is 2−4. The similar idea is applied on steps 2∼11.Sometimes, instead of considering the subkey nibbles independently, we would like to focus on their related masterkey bits according to the key schedule. Thanks to the slow diffusion of LBlock’s key schedule, the corresponding masterkey bits ofk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 are k55∼52, k51∼48, k75∼72, k50∼47, k63∼60, k26∼23, k22∼19, k30∼27, k78∼1, k73∼70 and k13∼10, respectively. However, please note that there are only 2 cases for k3∼0, 4 cases for k54∼51 and 4 cases for k25∼22 because of the 17-round related-key differential distinguisher. Thus, in step 1, we only need to guess k55 and 2 cases of k54∼51 (We all know that there are two encryption machines with different masterkeys in related-key setting. Here, we don’t fix k79∼0 to a certain machine, so there are only two cases for k54∼51. Once we recover all masterkey bits, we finally check which machine such masterkey belongs to.). The time complexity of this step is 2×22×2x+20=2x+23, and the number of pairs remained is 2x+20×2−4=2x+16. Similarly, we can handle other subkey nibbles on rounds 1∼3 within steps 2∼11. Finally, 33 bits of masterkey are guessed in this part, and 2x−24 pairs are left.


### 4.2.4. Filtering on Rounds21∼22

In this part, we guess the subkey nibblesk226, k221, k216, k220, k227 one by one to further filter pairs, which are summarized within steps 12∼16 in Table 12. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, while k216 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 51 bits of key information (including 39 masterkey bits and 12 subkey bits) guessed.


### 4.2.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


### 4.2.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under tthe right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼16 when filtering on rounds 1∼3 and 21∼22, which are listed in Table 12 one by one step. By summing the time complexities of all steps, the total time is about 245.54 22-round encryptions, which is(2)252+2×251+2×248+247+2×246+245+2×243+5×241×18×122=245.54.According to [29], the signal-to-noise ratio is(3)SN=2κ−1pλγ−p,where p denotes the probability of the related-key differential distinguisher, κ denotes number of key bits to recover, λ denotes the probability that a pair survives the filtering, γ denotes keys suggested by each pair surviving the filtering.Based on signal-to-noise ratioSN, the success probability of attack is(4)Ps=ϕμSN−ϕ−11−2−aSN+1,where μ denotes that the number of the right pairs, a denotes that a-bit advantage.We can calculate that signal-to-noise ratio isSN=251−12−60/2−44−2−60=235, when μ=2,a=51. Thus, Ps=92.1% according to equation (4).


## 4.2.1. Data Collection

From Figure2, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗000000E,∗0∗00∗0∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts.Since each structure composes264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


## 4.2.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−44=2x+20 pairs remained after the filtering on ciphertext.


## 4.2.3. Filtering on Rounds1∼3

In this part, we guess the subkey nibblesk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 one by one to filter pairs. Which are summarized within steps 1∼11 in Table 12. Taking step 1 as an example, we explain how we filter pairs in detail.Table 12
Related-key differential attack process on 22-round LBlock.
StepSubkeyMasterkey#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+202x+162k10k51∼483k50∼482×25×2x+162x+123k16k75∼7242×29×2x+122x+84k27k50∼471k472×210×2x+82x+45k13k63∼6042×214×2x+42x6k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x2x−47k20k22∼193k21∼192×220×2x−42x−88k22k30∼2742×224×2x−82x−129k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x−122x−1610k30k73∼702k71∼702×229×2x−162x−2011k35k13∼1042×233×2x−202x−2412k226k32∼222k32∼312×235×2x−242x−2813k221k17∼04k2212×239×2x−282x−3214k216k61∼514k59∼562×243×2x−322x−3615k220k77∼104k2202×247×2x−362x−4016k227k39∼264k2272×251×2x−402x−44In this step, we need to guess 4 bits subkeyk11 corresponding to the master key k55∼52. Note that we know k11=k55∼52 according to the key schedule algorithm of LBlock. Since k54, k53 and k52 are already known, it is only necessary to guess k55 so as to obtain the value of k11.Please note thatk54∼52 has 2 possible cases, which is equivalent to guessing one more bit. Under each out of 22 possible values of k11, we can calculate the output difference of S7 in round 1 for each plaintext pair, and check whether it equals the third nibble of ΔX0. If not, we filter out the current plaintext pair. Otherwise, we remain it and go next step. Totally, it needs 2×22×2x+20 operations on Sbox in step 1, while 2x+16 plaintext pairs are remained on average after step 1 because the probability is 2−4. The similar idea is applied on steps 2∼11.Sometimes, instead of considering the subkey nibbles independently, we would like to focus on their related masterkey bits according to the key schedule. Thanks to the slow diffusion of LBlock’s key schedule, the corresponding masterkey bits ofk11, k10, k16, k27, k13, k21, k20, k22, k33, k30 and k35 are k55∼52, k51∼48, k75∼72, k50∼47, k63∼60, k26∼23, k22∼19, k30∼27, k78∼1, k73∼70 and k13∼10, respectively. However, please note that there are only 2 cases for k3∼0, 4 cases for k54∼51 and 4 cases for k25∼22 because of the 17-round related-key differential distinguisher. Thus, in step 1, we only need to guess k55 and 2 cases of k54∼51 (We all know that there are two encryption machines with different masterkeys in related-key setting. Here, we don’t fix k79∼0 to a certain machine, so there are only two cases for k54∼51. Once we recover all masterkey bits, we finally check which machine such masterkey belongs to.). The time complexity of this step is 2×22×2x+20=2x+23, and the number of pairs remained is 2x+20×2−4=2x+16. Similarly, we can handle other subkey nibbles on rounds 1∼3 within steps 2∼11. Finally, 33 bits of masterkey are guessed in this part, and 2x−24 pairs are left.


## 4.2.4. Filtering on Rounds21∼22

In this part, we guess the subkey nibblesk226, k221, k216, k220, k227 one by one to further filter pairs, which are summarized within steps 12∼16 in Table 12. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, while k216 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 51 bits of key information (including 39 masterkey bits and 12 subkey bits) guessed.


## 4.2.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


## 4.2.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under tthe right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼16 when filtering on rounds 1∼3 and 21∼22, which are listed in Table 12 one by one step. By summing the time complexities of all steps, the total time is about 245.54 22-round encryptions, which is(2)252+2×251+2×248+247+2×246+245+2×243+5×241×18×122=245.54.According to [29], the signal-to-noise ratio is(3)SN=2κ−1pλγ−p,where p denotes the probability of the related-key differential distinguisher, κ denotes number of key bits to recover, λ denotes the probability that a pair survives the filtering, γ denotes keys suggested by each pair surviving the filtering.Based on signal-to-noise ratioSN, the success probability of attack is(4)Ps=ϕμSN−ϕ−11−2−aSN+1,where μ denotes that the number of the right pairs, a denotes that a-bit advantage.We can calculate that signal-to-noise ratio isSN=251−12−60/2−44−2−60=235, when μ=2,a=51. Thus, Ps=92.1% according to equation (4).


## 4.3. Related-Key Differential Attack on 23-Round LBlock

In Subsection4.1, we search out an expected 17-round related-key differential distinguisher on LBlock, whose total probability is 2−70 including 2−60 on cipher itself and 2−10 on the key schedule. In this subsection, we extend three rounds before this distinguisher and three rounds behind this distinguisher to attack 23-round LBlock. It is shown in Figure 3.Figure 3
Related-key differential attack on 23-round LBlock.


### 4.3.1. Data Collection

From Figure3, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗0∗00∗0∗,00∗∗∗∗∗∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts. Since each structure composes 264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


### 4.3.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−24=2x+40 pairs remained after the filtering on ciphertext.


### 4.3.3. Filtering on Rounds1∼3

In this part, because we are using the same distinguisher as that in 22-round attack, the details are the same as the Filtering on rounds1∼3 in Subsection 4.2.


### 4.3.4. Filtering on Rounds21∼23

In this part, we guess the subkey nibblesk231, k226, k235, k237, k232, k230, k221, k216, k220, k233, k227 one by one to further filter pairs, which are summarized within steps 12∼21 in Table 13. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, k235 can be calculated by the masterkey bits k76∼69 in which there are only 2 unknown bits k76 and k69, k216 can be calculated by the masterkey bits k61∼51 in which there are not unknown bits, while k230 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 65 bits of key information (including 37 masterkey bits and 28 subkey bits) guessed.Table 13
Related-key differential attack process on 23-round LBlock.
StepSubkeyMaster Key#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+402x+362k10k51∼483k50∼482×25×2x+362x+323k16k75∼7242×29×2x+322x+284k27k50∼471k472×210×2x+282x+245k13k63∼6042×214×2x+242x+206k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x+202x+167k20k22∼193k21∼192×220×2x+162x+128k22k30∼2742×224×2x+122x+89k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x+82x+410k30k73∼702k71∼702×229×2x+42x11k35k13∼1042×233×2x2x−412k231k68∼514k2312×237×2x−42x−813k226k32∼222k32∼312×239×2x−82x−1214k235k76∼692k76,k692×241×2x−122x−1615k237k77∼104k2372×245×2x−162x−2016k232k68∼554k2322×249×2x−202x−2417k230k61∼474k59∼562×253×2x−242x−2818k221k17∼04k2212×257×2x−282x−3219k216k61∼5102×257×2x−322x−3620k220k77∼104k2202×261×2x−362x−4021k233k227k72∼58k39∼268 (k233k227)2×269×2x−402x−44


### 4.3.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


### 4.3.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼21 when filtering on rounds 1∼3 and 21∼23, which are listed in Table 13 one by one step. By summing the time complexities of all steps, the total time is about 265.48 23-round encryptions, which is(5)272+2×271+2×268+267+2×266+265+2×263+7×261+2×256×18×123=265.48.According to equations (3) and (4), the signal-to-noise ratio is SN=265−12−60/2−24−2−60=229, when μ=2,a=65, so the final success rate is Ps=92.1%.


## 4.3.1. Data Collection

From Figure3, we can see that the forms of differences on plaintext and ciphertext are △P=0∗00∗0∗∗,∗∗∗0000∗ and △C=∗0∗00∗0∗,00∗∗∗∗∗∗ respectively, where ∗ denotes any 4 bit value. According to the form of difference on plaintext, we can build 2x structures and each structure involves 232 plaintexts. Totally, the data complexity is 2x+32 chosen plaintexts. Since each structure composes 264 plaintext pairs, there are expected 2x+64−32−60=2x−28 plaintext pairs to satisfy the 17-round distinguisher on both input and output differences.


## 4.3.2. Filtering on Ciphertext

According to the form of ciphertext difference△C, there are on average 2x+64−24=2x+40 pairs remained after the filtering on ciphertext.


## 4.3.3. Filtering on Rounds1∼3

In this part, because we are using the same distinguisher as that in 22-round attack, the details are the same as the Filtering on rounds1∼3 in Subsection 4.2.


## 4.3.4. Filtering on Rounds21∼23

In this part, we guess the subkey nibblesk231, k226, k235, k237, k232, k230, k221, k216, k220, k233, k227 one by one to further filter pairs, which are summarized within steps 12∼21 in Table 13. Luckily, k226 can be calculated by the masterkey bits k32∼22 in which there are only 2 unknown bits k32∼31, k235 can be calculated by the masterkey bits k76∼69 in which there are only 2 unknown bits k76 and k69, k216 can be calculated by the masterkey bits k61∼51 in which there are not unknown bits, while k230 is exactly the 4 bit masterkey k59∼56. By guessing such subkey nibbles one by one, ciphertext pairs can be decrypted to the end of distinguisher. In the end, about 2x−44 pairs are filtered to satisfy the output difference of distinguisher 00000000,0E000000. Until now, there are 65 bits of key information (including 37 masterkey bits and 28 subkey bits) guessed.Table 13
Related-key differential attack process on 23-round LBlock.
StepSubkeyMaster Key#BitsTime#Pairs left1k11k55∼522 (k55, 2 cases for k54∼51)2×22×2x+402x+362k10k51∼483k50∼482×25×2x+362x+323k16k75∼7242×29×2x+322x+284k27k50∼471k472×210×2x+282x+245k13k63∼6042×214×2x+242x+206k21k26∼233 (k26, 4 cases for k25∼22)2×217×2x+202x+167k20k22∼193k21∼192×220×2x+162x+128k22k30∼2742×224×2x+122x+89k33k5∼23 (k5∼4, 2 cases for k3∼0)2×227×2x+82x+410k30k73∼702k71∼702×229×2x+42x11k35k13∼1042×233×2x2x−412k231k68∼514k2312×237×2x−42x−813k226k32∼222k32∼312×239×2x−82x−1214k235k76∼692k76,k692×241×2x−122x−1615k237k77∼104k2372×245×2x−162x−2016k232k68∼554k2322×249×2x−202x−2417k230k61∼474k59∼562×253×2x−242x−2818k221k17∼04k2212×257×2x−282x−3219k216k61∼5102×257×2x−322x−3620k220k77∼104k2202×261×2x−362x−4021k233k227k72∼58k39∼268 (k233k227)2×269×2x−402x−44


## 4.3.5. Exhaustive Search of Remained Key Bits

In order to recover the right key with a high probability, we expect there are 2 pairs left under right key, which meansx=29 in the data collection phase. Once 2 pairs or larger than 2 pairs are left under certain guessed key, we regard such key as a candidate key. Then we search exhaustively remaining key bits and check if it is right with another plaintext/ciphertext pairs.


## 4.3.6. Complexity Analysis

According to the data collection phase, we can see that the data complexity is261 chosen plaintexts when we take x=29. In this case, there are expected 2 pairs left under right key, which is enough to recover the right key with a high probability. The time complexity mainly happens in steps 1∼21 when filtering on rounds 1∼3 and 21∼23, which are listed in Table 13 one by one step. By summing the time complexities of all steps, the total time is about 265.48 23-round encryptions, which is(5)272+2×271+2×268+267+2×266+265+2×263+7×261+2×256×18×123=265.48.According to equations (3) and (4), the signal-to-noise ratio is SN=265−12−60/2−24−2−60=229, when μ=2,a=65, so the final success rate is Ps=92.1%.


## 5. Conclusion

In this paper, we use SMT-based approaches to evaluate the security bounds of LBlock against related-key differential cryptanalysis. Firstly, we propose tighter security bounds, including both the minimal number of active S-boxes and the upper bounds of probabilities for up to 19 rounds of LBlock. As far as we know, these are the best security bounds so far. Secondly, we find a 17-round related-key differential characteristic, whose total probability is2−70 including probability 2−60 on the encryption algorithm itself. With this characteristic, we mount key-recovery attacks on 22-round and 23-round LBlock. These are the best related-key differential attacks on LBlock so far. However, there are still some problems that remained in this work that we need to further study. For example, We will focus on how to find as many useful related-key differentials with high probability as possible so as to increase the total probability of the related-key differential distinguisher. With such distinguisher, we can further improve the related-key differential attack on LBlock.



---

*Source: 8464960-2022-09-16.xml*