Paper 2013/676

Automatic Security Evaluation for Bit-oriented Block Ciphers in Related-key Model: Application to PRESENT-80, LBlock and Others

Siwei Sun, Lei Hu, Peng Wang

Abstract

Since AES and PRESENT are two international standard block ciphers representing the most elegant design strategies for byte-oriented and bit-oriented designs respectively, we regard AES and PRES\-ENT the two most significant candidates to scrutinize with respect to related-key differential attack. In EUROCRYPT 2010 and CRYPTO 2013, the security of AES with respect to related-key differential attack has been completely analyzed by Alex Biryukov et al and Pierre-Alain Fouque et al with automatic related-key differential characteristic searching tools. In this paper, we propose two methods to describe the differential behaviour of an S-box with linear inequalities based on logical condition modelling and computational geometry. In one method, inequalities are generated according to some conditional differential properties of the S-box; in the other method, inequalities are extracted from the H-representation of the convex hull of all possible differential patterns of the S-box. For the second method, we develop a greedy algorithm for selecting a given number of inequalities from the convex hull. Using these inequalities combined with Mixed-Integer Linear Programming (MILP) technique, we successfully prove that the full-round PRESENT-80 is secure against standard related-key differential attack, which solves an open problem of the symmetric-key cryptography community. This proof is accomplished automatically on a workstation with 8 CPU cores in a time within 16 days. In a similar way, we also prove that the probability of the best related-key differential characteristic of full LBlock is upper bounded by $2^{-56}$, which is the first result concerning the security of full LBlock with respect to related-key differential attack. The methodology presented in this paper is generic, automatic and applicable to lightweight constructions with small block size, small S-boxes, and bit-oriented operations, including but not limited to PRESENT, EPCBC, LBlock, etc, which opens a new interesting direction of research for bit-oriented ciphers and for the application of MILP technique in cryptography.