Improvement on the method for automatic differential analysis and its application to two lightweight block ciphers DESL and LBlock-s

With the development of the ubiquitous computing and large-scale information processing systems, the demand for lightweight block ciphers which is suitable for resource constrained computing devices is increasing. Hence, the methodology for design and analysis of block ciphers is becoming more important. In this paper, we use the Mixed-Integer Linear Programming (MILP) based tools for automatic differential cryptanalysis in a clever way to find improved single-key and related-key differential characteristics for DESL (a lightweight variant of the well known Data Encryption Standard), and obtain tighter security bound for LBlock-s (a core component of an lightweight authenticated encryption algorithm submitted to the international competition for authenticated encryption – CAESAR) against related-key differential attack. To be more specific, in searching for improved characteristics, we restrict the differential patterns allowed in the first and last rounds of the characteristics in the feasible region of an MILP problem by imposing different constraints than other rounds, and we partition the differential patterns of the DESL S-box into different sets with 2-bit more information associated with each pattern according to their probabilities. In addition, we show how to use the Gurobi optimizer combined with a known good characteristic to speed up the characteristic searching and bound proving process. Using these techniques, we managed to find the currently known best 9-round related-key differential characteristic for DESL, and the first published nontrivial related-key and single-key differential characteristics covering 10 rounds of DESL. Also, we obtain the currently known tightest security bound for LBlock-s against relatedkey differential attack. These techniques should be useful in analysis and design of other lightweight block ciphers.