Abstract: Automatic analysis is one of the important methods to evaluate the security of cryptographic algorithms. It is characterized by high efficiency and easily implement. In ASIACRYPT 2014, Sun et al. presented a MILP-based automatic search differential and linear trails method for bit-oriented block ciphers, which has attracted the attention of many cryptographers. At present, there are still a lack of research about solving the MILP model, such as how to reduce the number of variables and constraint inequalities. According to the differential propagation model of the XOR operation, in EUROCRYPT 2017, Sasaki et al. gave a set of new constraints without dummy variables. The new constraint inequalities can not only preserve the differential propagation for XOR operation, but also reduce the number of variables. At the same time, Sun et al. uses four constraints to describe the property when the input differential variable (the linear mask variable) of an S-box is non-zero and the S-box must be an active, but in this paper, we just use one constraint. Based on these refined constraints and the automatic method for finding high probability trails of block cipher, we establish the refined differential and linear MILP model under the single key assumption for the lightweight block cipher ESF. We have found that the minimum number of active S-boxes in 15-round differential trail of ESF is 19 and the number is 15 in 16-round linear trail. Moreover, we find so far the longest impossible differential and zero-correlation linear approximation distinguishers of ESF.

Key words: differential cryptanalysis, linear cryptanalysis, impossible differential, zero-correlation linear approximation, ESF, MILP