Keywords

1 Introduction

Cryptography plays a central role in protecting today’s information system, and block cipher is one of the most important types of cryptographic algorithms. Moreover, with the development of the ubiquitous computing and large-scale information processing systems, the demand for lightweight block ciphers which are suitable for resource constrained computing devices such as sensor nodes, and RFID tags is increasing. Therefore, design and analysis of lightweight block ciphers draw much attention from the researchers in applied cryptography.

Differential cryptanalysis [20], introduced by Eli Biham and Adi Shamir in the late 1980s, is one of the most effective attacks on modern block ciphers. Moreover, many cryptanalytic techniques, such as the related-key differential attack [2, 6, 19], truncated differential attack [24], statistical saturation attack [11, 16], impossible differential attack [1, 23], (probabilistic) higher order differential attack [24, 43], boomerang attack [18], multiple differential attack [8, 9, 15, 17], differential-linear cryptanalysis [42], multiple linear attack [5, 14, 28–30] and so on so forth, are essentially based on differential attack.

Typically, the first step in differential attack is to find a differential characteristic with high (or the highest possible) probability. Hence, a method used for searching for good (or the best) differential characteristic is of great importance. For a designer, such method can be used to obtain a proven security bound against differential attack, which is a necessary part of the design of a block cipher. In fact, a large part of the design document of a modern block cipher is devoted to the security evaluation of differential attack. For an attacker, such method can be used to find high probability differential characteristics of a cipher which lead to distinguishers or key recovery attacks.

Matusi’s branch-and-bound depth-first search algorithm [31] is a classic method for finding the best differential characteristic of a cipher. Several works were devoted to improving the efficiency of Matsui’s approach. The concept of search pattern was introduced in [34] to reduce the search complexity of Matusi’s algorithm by detecting unnecessary search candidates. Further improvements were obtained by Aoki et al. [10] and Bao et al. [48]. Remarkably, significant efficiency improvement on Matsui’s approach was observed for specific ciphers in [48].

Despite its guarantee for finding the best single-key differential characteristic for a cipher (given unlimited computational power), Matsui’s algorithm and its variants has some important limitations making it not practically applicable in many situations. Firstly, for most ciphers, the original algorithm of Matsui is not practically applicable in the related-key model. Even though there exits Matsui’s variant (see Biryukov et al.’s work [3]) for finding related-key differential characteristics, this method is not very useful for ciphers with nonlinear key schedule algorithms, whereas ciphers with nonlinear key schedule algorithms are plentiful. Moreover, with the developement of new techniques for cryptanalysis (e.g., the differential fault attack [13, 21, 47] and biclique attack [7]), the related-key model is becoming more important and highly relevant to the design and analysis of symmetric-key cryptographic algorithms. Secondly, Matsui’s approach is inefficient in finding the best characteristics for many ciphers, and some speeding-up techniques for Matusi’s approach were intimately related to the special properties of the specific ciphers under consideration, making it difficult to implement and far from being a generic and convenient tool for cryptanalysis.

For ciphers that cannot be analyzed by Matsui’s approach, the cryptanalysts turn to other methods which can be employed to find reasonably good characteristics. Although the characteristics found by these methods are not guaranteed to be the best, they do produce currently the best known results for many ciphers.

In [4], Biryukov et al.extend Matsui’s algorithm by using the partial (rather than the full) difference distribution table (pDDT) to prevent the number of explored candidates from exploding and at the same time keep the total probability of the resulting characteristic high. In [35], truncated differentials with the minimum number of active S-boxes are found by a breadth-first search based on the Dijkstra’s algorithm, and then these truncated differentials are instantiated with actual differences.

Another line of research is to model the differential behavior of a cipher as an SAT or Mixed-Integer Linear Programming (MILP) problem which can be solved automatically by SAT or MILP solvers. Compared with other methods, these methods are easier to implement and more flexible. In [32, 40, 41], SMT/SAT solvers are employed to find differential characteristics of Salsa and other ciphers. Mouha et al. [33], Wu et al. [36], and Sun et al. [37] translated the problem of counting the minimum number of differentially active S-boxes into an MILP problem which can be solved automatically with open source or commercially available optimizers. This method has been applied in evaluating the security against (related-key) differential attacks of many symmetric-key schemes. However, this tool cannot be used to find the actual differential characteristics directly. In Asiacrypt 2014, two systematic methods for generating linear inequalities describing the differential properties of an arbitrary S-box were given in [39]. With these inequalities, the authors of [39] were able to construct an MILP model whose feasible region is a more accurate description of the differential behavior of a given cipher. Based on such MILP models, the authors of [39] proposed a heuristic algorithm for finding actual (related-key) differential characteristics, which is applicable to a wide range of block ciphers. In [38], Sun et al. get rid of the heuristic argument in [39] by constructing MILP models whose feasible regions are exactly the sets of all (related-key) differential characteristics.

These MILP based methods [37, 39] mainly focus on finding characteristics with the minimum (or reasonably small) number of active S-boxes. However, it is well possible that a characteristic with more active S-boxes is better than a characteristic with a smaller number of active S-boxes. Even though a method for finding the best characteristic of a cipher by encoding the probability information into the differential patterns is proposed in [38], this method is only applicable to ciphers with \(4 \times 4\) S-boxes and infeasible when the number of rounds is large. Therefore, by using these methods, we may miss some better characteristics. In this paper, we mainly focus on how to use the MILP based methods in a clever way such that better characteristics can be found.

Our Contribution. Based on Sun et al.’s MILP framework for automatic differential analysis presented in [37–39], we propose several techniques which are useful for finding improved characteristics. To be more specific, we restrict the differential patterns allowed in the first and last rounds to be those with relatively high probability in the differential distribution table, which makes sure that the active S-boxes in the first and last rounds assume relatively high probabilities. We also partition the differential patterns into different sets. For each of these sets, we associate 2-bit more information into its differential patterns, and try to find a characteristic maximizing a special objective function rather than maximizing the number of differentially active S-boxes. Moreover, after we find a good characteristic with \(N_A\) active S-boxes, we use the tool presented in [38] to enumerate all characteristics with \(N_A\), \(N_A + 1\) and \(N_A + 2\) active S-boxes, from which we may find better characteristics than the original one. We also present some tricks in using the Gurobi [22] optimizer which may speed up the solving process.

With these techniques, we find a related-key characteristic covering 9 rounds of DESL whose probability is \(2^{-41.89}\), while the best previously published 9-round related-key differential characteristic with probability \(2^{-44.06}\) is given in [38]. Note that in [3], only the upper bound of the probability of the related-key differential characteristics covering 9 rounds of DESL is given. We also present a 10-round single-key and related-key differential characteristics of DESL with probabilities \(2^{-52.25}\) and \(2^{-51.85}\) respectively. Moreover, we give so far the tightest security bound of the full LBlock-s with respect to related-key differential attack.

Organization of the Paper. In Sect. 2, we introduce the MILP framework for automatic differential cryptanalysis. In Sect. 3, we present several techniques for finding improved (related-key) differential characteristics. Then we apply these techniques to DESL and LBlock-s in Sect. 4. Section 5 is the conclusion and discussion.

2 MILP Based Framework for Automatic Differential Cryptanalysis

A brief introduction of Sun et al.’s method is given below. Sun et al.’s method [37–39] is an extension of Mouha et al.’s technique [33] based on Mixed-Integer Linear Programming, which can be used to search for (related-key) differential characteristics and obtain security bounds of a cipher with respect to the (related-key) differential attack automatically.

Sun et al.’s method is applicable to ciphers involving the following three operations:

  • bitwise XOR;

  • bitwise permutation L which permutes the bit positions of an n dimensional vector in \(\mathbb {F}_2^n\);

  • S-box, \(\mathcal {S}: \mathbb {F}_2^{\omega }\rightarrow \mathbb {F}_2^{\nu }\).

Note that a general linear transformation \(T: \mathbb {F}_2^n \rightarrow \mathbb {F}_2^m\) can be treated as some XOR summations and bitwise permutations of the input bits. In Sun et al.’s methods, a new variable \(x_i\) is introduced for every input and output bit-level differences, where \(x_i = 1\) means the XOR difference at this position is 1 and \(x_i = 0\) if there is no difference.

Also, for every S-box involved in the cipher, introduce a new 0–1 variable \(A_j\) such that

$$\begin{aligned} A_j = \left\{ \begin{array}{l} 1,~ \mathrm {if ~the~ input ~ word ~of~ the~ Sbox~ is~ nonzero,} \\ 0,~ \mathrm {otherwise.} \end{array} \right. \end{aligned}$$

Now, we are ready to describe Sun et al.’s method by clarifying the objective function and constraints in the MILP model. Note that we assume that all variables involved are 0–1 variables.

Objective Function. The objective function is to minimize the sum of all variables \(A_j\) indicating the activities of the S-boxes:   \(\sum _j A_j\).

Constraints. Firstly, for every XOR operation \(a \oplus b = c \in \{0,1\}\), include the following constraints

$$\begin{aligned} \left\{ \begin{array}{l} a + b + c \ge 2d_{\oplus }\\ a + b + c \le 2\\ d_{\oplus } \ge a,~d_{\oplus } \ge b,~d_{\oplus } \ge c \end{array} \right. \end{aligned}$$
(1)

where \(d_{\oplus }\) is a dummy variable.

Assuming \((x_{i_0}, \dots ,x_{i_{\omega -1}})\) and \((y_{i_0}, \dots ,y_{i_{\nu -1}})\) are the input and output differences of an \(\omega \times \nu \) S-box marked by \(A_t\), we have

$$\begin{aligned} \left\{ \begin{array}{l} A_t - x_{i_k} \ge 0,~k \in \{0,\dots ,\omega -1\}\\ - A_t + \sum \limits _{j=0}^{\omega -1}x_{i_j} \ge 0 \end{array} \right. \end{aligned}$$
(2)

and

$$\begin{aligned} \left\{ \begin{array}{l} \sum \limits _{k = 0}^{\omega -1} x_{i_k} + \sum \limits _{k = 0}^{\nu - 1}y_{j_k} \ge \mathcal {B}_\mathcal {S} d_{\mathcal {S}} \\ d_{\mathcal {S}} \ge x_{i_k},~~ 0\le k \le \omega -1\\ d_{\mathcal {S}} \ge y_{j_k},~~0\le k \le \nu -1\\ \end{array} \right. \end{aligned}$$
(3)

where \(d_{\mathcal {S}}\) is a dummy variable, and the branch number \(\mathcal {B}_\mathcal {S}\) of an S-box \(\mathcal {S}\), is defined as \(\min _{a \ne b} \{\text {wt}((a\oplus b)||(\mathcal {S}(a)\oplus \mathcal {S}(b)): a, b \in \mathbb {F}_2^{\omega } \}\). For an bijective S-box we have

$$\begin{aligned} \left\{ \begin{array}{l} \omega \sum \limits _{k=0}^{\nu -1}y_{j_k} - \sum \limits _{k=0}^{\omega -1}x_{i_k} \ge 0\\ \nu \sum \limits _{k=0}^{\omega -1}x_{i_k} - \sum \limits _{k=0}^{\nu -1}y_{j_k} \ge 0 \end{array} \right. \end{aligned}$$
(4)

Then, treat every possible input-output differential pattern \((x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\nu -1})\) of an \(\omega \times \nu \) S-box as an \((\omega +\nu )\)-dimensional vector \((x_0, \dots , x_{\omega -1},\) \( y_0, \dots , y_{\nu -1}) \in \{0,1\}^{\omega +\nu }\subseteq \mathbb {R}^{\omega +\nu }\), and compute the H-representation of the convex hull of all possible input-output differential patterns of the S-box. From the H-representation select a small number of linear inequalities using the greedy algorithm presented in [38] which can be used to exactly describe the differential behavior of the S-box. Finally, relate the input and output variables of the S-box using these inequalities. Now, if we require that all the variables involved are 0–1 variables, then the feasible region of the resulting MILP model is exactly the set of all differential characteristics. We mention here that all the constraints in (3) and (4) can be omitted if we have already use the constraints from the critical set, since these constraints remove all impossible patterns.

3 Techniques for Obtaining Better Characteristics

In [37–39], MILP models are constructed and solved to search for characteristics with a small or the minimal number of active S-boxes. The main reason preventing the solution of such MILP models from leading to better characteristics is that the objective function in the MILP model is to minimize the number of differentially or linearly active S-boxes. Under this setting, an MILP optimizer, say Gurobi, is constantly trying to find a characteristic with a smaller number of active S-boxes. In this process, some characteristics with higher probability but larger numbers of active S-boxes are lost. Therefore, the method presented in [37–39] may fail to find some better characteristics. In this section, we show how to mitigate this situation such that improved characteristics can be obtained automatically.

Technique 1. Finding Characteristics with More Active S-Boxes. For an iterative r-round block cipher E, Sun et al.’s methods can be used to find a characteristic with the minimal or a reasonably small number of active S-boxes. Assuming that such an r-round characteristic with \(N_A\) active S-boxes has been found, then we add the constraint \(N_A \le \sum _j S_j \le N_A + m\) to the MILP model, where \(S_j\)’s are the variables marking the activities of the involved S-boxes. Then we try to enumerate all related-key differential characteristics satisfying all the constraints in the model, where m is a small positive integer typically chosen to be 1 or 2. From these characteristics we may find better ones. This is in fact the same heuristic employed by Biham et al. in [12], where they try to find differential characteristics with higher probabilities for the amplified boomerang attack. They try to accomplish this by adding an active S-box in the first round. This might seem a bad thing (as this increase the number of active S-boxes), but they find out that in exchange they get 3 more differentials of the active S-boxes with probability \(2^{-2}\) instead of \(2^{-3}\).

Technique 2. Imposing Different Constraints for Different Rounds. Another technique for getting better characteristic is to allow only those differential patterns in the first and last rounds of a characteristic to take relatively high probabilities. This is because the input of the first round and the output of the last round is relatively free when compared to other rounds. In fact, for every characteristic we get, we can always manually modify its input and output differences (such that high probability differential patterns are used in the first and last rounds) to get a characteristic which is at least not worse than the original one. This manual process can be done automatically in the MILP framework by, in the first and last rounds, using the constraints generated from the critical set of the convex hull of all differential patterns with probability higher than a threshold value \(p_T\) we choose, rather than the convex hull of all possible differential patterns. Note that it is important to do this automatically since the enumeration process may return thousands of characteristics.

Technique 3. Encoding More Information into the Differential Patterns of an S-Box. In Sect. 5 of [38], an MILP based method for constructing an MILP model which can be used to search for the best (related-key) differential characteristic of a block cipher with \(4 \times 4\) S-box is proposed by encoding the probability information of the differentials of a \(4 \times 4\) S-box into the differential patterns.

Take the PRESENT S-box S for example. For every possible differential pattern \((x_0, x_1, x_2, x_3) \rightarrow (y_0, y_1, y_2, y_3)\), a corresponding differential pattern with probability information can be constructed as follows

$$(x_0, x_1, x_2, x_3, y_0, y_1, y_2, y_3; p_0, p_1)\in \{0,1\}^{8+2}$$

where the two extra bits \((p_0, p_1)\) are used to encode the differential probability \(\mathrm{Pr}_S[(x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\nu -1})]\) as follows

$$\begin{aligned} \left\{ \begin{array}{l} (p_0, p_1) = (0, 0),~\mathrm{if~} \mathrm{Pr}_S[(x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\nu -1})] = 1; \\ (p_0, p_1) = (0, 1),~\mathrm{if~} \mathrm{Pr}_S[(x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\nu -1})] = 2^{-2}; \\ (p_0, p_1) = (1, 1),~\mathrm{if~} \mathrm{Pr}_S[(x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\nu -1})] = 2^{-3}.\\ \end{array} \right. \end{aligned}$$
(5)

Hence, the probability of the differential pattern \((x_0, x_1, x_2, x_3) \rightarrow (y_0, y_1, y_2, y_3)\) is \(2^{-(p_0 + 2p_1)}\). We refer the reader to [38] for more information of the technique.

This technique is only feasible for ciphers for \(4 \times 4\) S-boxes because there are only 3 different probabilities for all differential patterns of a typical \(4 \times 4\) S-boxes and hence we need only \(\lceil \log _2 3 \rceil = 2\) extra bits to encode the probability information for each differential pattern. For an \(\omega \times \mu \) S-box, if d extra bits are needed to encode the differential probability information, then we need to compute the H-representation of the convex hull of a subset in \(\mathbb {R}^{\omega + \mu + d}\). For the PRESENT S-box, we need to compute the H-representation of a convex hull of a subset in \(\mathbb {R}^{4 + 4 + 2} = \mathbb {R}^{10}\). For the S-box of DESL, this technique is infeasible since there are 9 different probabilities for the differentials of the DESL S-box and we need at least \(\lceil \log _2 9 \rceil = 4\) extra bits to encode the probability information. This will force us to compute the H-representation of a convex hull of a set in \(\mathbb {R}^{6+4+4}=\mathbb {R}^{14}\) which leads to MILP models with too many constraints to be solved in practical time. In the following, we propose a technique which partitions the differential patterns into several sets according to their probabilities and encodes their probability information with less extra bits.

Definition 1

Define \(\mathcal {D}_S^{[p]}\) to be the set of all differential patterns of an \(\omega \times \mu \) S-box with probability p, that is

$$\mathcal {D}_S^{[p]} = \{ (x_0, \cdots , x_{\omega -1}, y_0, \cdots , y_{\mu -1}): \mathrm{Pr}_S[(x_0, \dots , x_{\omega -1})\rightarrow (y_0, \dots , y_{\mu -1})] = p\},$$

and we use \(\mathcal {D}_S^{[p_1, \cdots , p_t]}\) to denote the set \(\mathcal {D}_S^{[p_1]} \cup \cdots \cup \mathcal {D}_S^{[p_t]} \).

Take the DESL S-box for example. For every possible differential pattern \((x_0, \cdots , x_{5}) \rightarrow (y_0, \cdots , y_{3})\), we can construct a corresponding pattern

$$(x_0, \cdots , x_{5},y_0, \cdots , y_{3}; \theta _0, \theta _1) \in \mathbb {R}^{6+4+2}$$

such that

$$\begin{aligned} \left\{ \begin{array}{l} (\theta _0, \theta _1) = (0, 0),~\mathrm{if~} (x_0, \cdots , x_{5},y_0, \cdots , y_{3}) \in \mathcal {D}_S^{[\frac{64}{64}]}; \\ (\theta _0, \theta _1) = (1, 0),~\mathrm{if~} (x_0, \cdots , x_{5},y_0, \cdots , y_{3}) \in \mathcal {D}_S^{[\frac{16}{64}, \frac{14}{64},\frac{12}{64}]};\\ (\theta _0, \theta _1) = (0, 1),~\mathrm{if~} (x_0, \cdots , x_{5},y_0, \cdots , y_{3}) \in \mathcal {D}_S^{[\frac{10}{64}, \frac{8}{64},\frac{6}{64}]};\\ (\theta _0, \theta _1) = (1, 1),~\mathrm{if~} (x_0, \cdots , x_{5},y_0, \cdots , y_{3}) \in \mathcal {D}_S^{[\frac{4}{64}, \frac{2}{64}]}. \end{array} \right. \end{aligned}$$
(6)

In this technique, the constraints for S-boxes are the critical sets of all patterns with the above encoding scheme, and the objective function is chosen to be minimizing \(\sum (\theta _0 + \lambda \theta _1)\), where \(\lambda \) is a positive constant. Note that the differential patterns in \(D^{[p_1, \cdots , p_t]}\) with larger \(p_i\) will lead to a smaller \(\theta _0 + \lambda \theta _1\), and therefore tend to make the objective function \(\sum (\theta _0 + \lambda \theta _1)\) smaller.

Note that this method is heuristic in nature. Firstly, unlike the case of PRESENT S-box, the encoding scheme does not represent the exact probability of a differential. Secondly, the solution which minimizes the objective function is not necessarily corresponding to the best characteristic. Finally, the partition of the differential patterns and the selection of \(\lambda \) are rather ad-hoc (we choose \(\lambda = 3\) when applied this technique to DESL). All these problems deserve further investigation. In the next section, we will show that although this technique is heuristic and rather ad-hoc, it does produce the currently known best results for DESL.

Finally, we would also like to point out a feature provided by the MILP optimizer Gurobi [22] which may be useful in speeding up the searching process of better characteristics. In Gurobi, an MILP start (MST) file is used to specify an initial solution for a mixed integer programming model. The file lists values to assign to the variables in the model. If an MILP start file has been imported into an MILP model before optimization begins, the Gurobi optimizer will attempt to build a feasible solution from the specified start values. A good initial solution often speeds up the solution of the MILP model, since it provides an early bound on the optimal value, and also since the specified solution can be used to seed the local search heuristics employed by the MILP solver. An MILP start file consists of variable-value pairs, each on its own line. Any line that begins with the hash sign (#) is a comment line and is ignored. The following is a simple example:

figure a

Therefore, by converting known good characteristics into an MST file, and importing it into our MILP model before optimization begins, we may speed up the searching process.

4 Application to DESL and LBlock-s

The techniques presented in Sect. 3 are implemented in a Python [44] framework, and we show its applications in the following.

4.1 Improved Single-Key and Related-Key Differential Characteristics for DESL

DESL [25] is a lightweight variant of the well known block cipher DES (the Data Encryption Standard), which is almost the same as DES except that it uses a single S-box instead of eight different S-boxes as in DES. This S-box has a special design criteria to discard high probability (single-key) differential characteristics. This simple modification makes DESL much stronger than DES with respect to differential attack. In [3], Alex Biryukov et al. observed that Matsui’s tool is infeasible for finding the best differential characteristics for DESL. However, Matsui’s tool can find the best characteristic of the full DES in no more than several hours on a PC. To the best of our knowledge, there is no published single-key or related-key differential characteristics covering 10 rounds of DESL, and in fact, even in the design document of DESL, there is no concrete security bounds provided for DESL.

We first generate an MILP model for 9-round DESL in the related-key model according to the technique 2 and technique 3 presented in Sect. 3. By solving this model using the Gurobi optimizer [22], we find a 9-round related-key differential characteristic for DESL with probability \(2^{-41.89}\), which is the best published 9-round related-key differential characteristic so far. The concrete results are given in Tables 1 and 2.

Subsequently, we construct an MILP model for 10-round DESL in the related-key model. Before we start to solve this model, we import the 9-round related-key differential characteristic found previously as an MILP start file. Finally, we find a 10-round related-key differential characteristic of DESL with probability \(2^{-51.85}\) and 14 active S-boxes (see Tables 3 and  4). Then by employing the technique 1 of Sect. 3, we search for characteristics with 14, 15 or 16 active S-boxes. Finally, we find a single-key (a special case of the related-key model where there is no key difference) differential characteristic with probability \(2^{-52.25}\) and 15 active S-boxes, which is given in Table 5. Note that this is the first published nontrivial single-key differential characteristic covering 10 rounds of DESL.

Table 1. A 9-round related-key differential characteristic for DESL with probability \(2^{-41.89}\) (characteristic in the encryption process)
Full size table
Table 2. A 9-round related-key differential characteristic for DESL with probability \(2^{-41.89}\)(characteristic in the key schedule algorithm)
Full size table
Table 3. A 10-round related-key differential characteristic for DESL with probability \(2^{-51.85}\) (characteristic in the key schedule algorithm)
Full size table
Table 4. A 10-round related-key differential characteristic for DESL with probability \(2^{-51.85}\)(characteristic in the encryption process)
Full size table
Table 5. A 10-round single-key differential characteristic for DESL with probability \(2^{-52.25}\)
Full size table

4.2 Tighter Security Bound for LBlock-s

LBlock is a lightweight block cipher proposed by Wu et al. in ACNS 2011 [46]. It is a Feistel Network with a 64-bit block size and a 80-bit key size. Since its publication, LBlock received extensive cryptanalysis, such as [27] and [45]. According to [45], the security of LBlock against biclique attack is not strong enough due to its relatively weak diffusion of the key schedule algorithm. So a new key schedule algorithm is proposed in [45]. The LBlock with this improved key schedule is called LBlock-s, which is a core component of the authenticated encryption LAC [26] submitted to the CAESAR competition (Competition for Authenticated Encryption: Security, Applicability, and Robustness). Also, instead of using 10 different S-boxes in LBlock, LBlock-s uses only one S-box to reduce the cost of hardware implementation. For a detailed description of the cipher LBlock-s we refer the reader to [45] and [26] for more information. In this section, we apply the technique presented in this paper and the method presented in [38, 39] to LBlock-s, and we obtain so far the tightest security bound for the full LBlock-s.

To obtain the security bound for LBlock-s against related-key differential attack, we generate two MILP instances for 10-round and 11-round LBlock-s using the method presented in [38, 39]. Then we use the Gurobi optimizer to solve these models. The results indicate that there are at least 10 active S-boxes for 10-round LBlock-s, and 11 active S-boxes for 11-round LBlock-s. However, when we solve the 11-round model, we use the 10-round related-key differential characteristic found by the Gurobi model by solving the 10-round model as an MILP start file (see Sect. 3), and import it into the 11-round model. Finally, we observe a roughly 7 % speed up compared with the case without using the MILP start file. Then, we employ the technique 2 presented in Sect. 4.1 of [39] to generate an MILP model for 11-round LBlock-s such that only the differential patterns of the S-box with probability greater than or equal to \(2^{-2}\) are allowed. By solving this model, we prove that there are at least 12 active S-boxes for 11-round LBlock-s in the related-key model if only those S-box differential patterns with probability greater than or equal to \(2^{-2}\) are allowed. These results indicate that the probability of any related-key differential characteristic for the 11-round LBlock-s is at most \((2^{-2})^{10}\times 2^{-3} = 2^{-23}\). Consequently, the probability of the full round LBlock-s (32 rounds in total) is upper bounded by \(2^{-23} \times 2^{-23} \times (2^{-2})^{10} = 2^{-66}\). Note that this is so far the tightest security bound for full LBlock-s against related-key differential attack.

5 Conclusion and Discussion

In this paper, we use the MILP based methods in a clever way to find better (related-key) differential characteristics of DESL and obtain tighter security bound for LBlock-s. The key idea is to force the active S-boxes in the first and last rounds of a characteristic to take the differentials with relatively high probabilities, encode more information into the differential patterns, and to find better characteristics by enumerating all characteristics with their objective value (number of active S-boxes) close to the minimum number of active S-boxes. Moreover, we show how to use Gurobi and a known good characteristic to speed up the searching process. Finally, we would like to propose some problems deserving further investigation. Firstly, how to find the related-key differential characteristic of DESL with the maximal probability automatically by using MILP technique? Secondly, how to exploit the special features and tune the available parameters of the Gurobi optimizer to speed up the solving process further?