Journal Article

Improvement of the Minimal‐Guess‐Basis MILP Model and Its Application to ESF

Li, Lingchen, Wei, Yongzhuang, Qiao, Zhi, Ye, Tao, Dai, Yiming

2026

Overview

The guess‐and‐determine technique find wide applications in the recovery of unknown variables within given system of relations. The fundamental concept behind this technique involves guessing certain unknown variables and deducing the remaining ones based on the relational system. In the context of symmetric cryptography analysis, the guess‐and‐determine technique is employed to deduce partial subkey information to recover the master key. The set of variables that need to be guessed is called the guess basis.The crux of the guess‐and‐determine technique lies in identifying the minimal guess basis. By introducing new equal relations and initial constraints, this paper enhances the minimal guess basis mixed integer linear programming (MILP) model. The new model offers a more comprehensive depiction of key schedule, thereby enabling a more accurate and efficient derivation of the minimal guess basis.The novel model is applied to the eight‐sided fortress (ESF) block cipher algorithm. By extending forward by three rounds and backward by three rounds based on a nine‐round impossible differential distinguisher, a 15‐round impossible differential attack is conducted. Utilizing the new model, the minimal guess basis required for key recovery is determined to be 54 bits. This represents a significant improvement compared to the existing result of 58 bits.The results indicate that for a 15‐round impossible differential attack on the ESF algorithm, the data complexity is 231.18 CP, the time complexity involves 261.67 iterations of 15‐round encryption, and the memory complexity is 266.18 bytes. Furthermore, this paper introduces, for the first time, a principle for designing key scheduling algorithms based on the guessing basis. This principle is applied to the ESF algorithm, where the minimal guess basis is employed to determine the positions of S‐boxes and the parameters for cyclic shifts within the key scheduling algorithm. Without altering the consumption of software or hardware resources, a global optimal search is conducted among various key scheduling candidate approaches. By employing an equivalence class partitioning approach derived from 2108 instances of nine‐round impossible differential distinguishers, the search space is reduced. Eventually, a selection process identifies a set of eight novel key schedule algorithms that achieve the maximum value of 77 bits for the minimal guess basis. These new key scheduling algorithms exhibit enhanced resistance against impossible differential attacks.

• Publisher: John Wiley & Sons, Inc
• Subject: Algorithms / Automation / Basis / Candidates / Complexity / Cryptography / Data encryption / Derivation / Efficiency / Linear programming / Recovery / Resistance / Scheduling / Variables