Improved Search of Boomerang Distinguishers for Generalized Feistel and Application to WARP

Abstract

Boomerang and rectangle cryptanalysis are powerful cryptanalytic techniques for security evaluation of block ciphers. Automated search for boomerang distinguishers is an important area of research. In FSE 2023, Hadipour et al. proposed a MILP model of searching boomerang distinguishers for Feistel structure, and applied their model to obtain the best known boomerang distinguishers to date for many generalized Feistel ciphers including WARP. In this paper, we focus on improving Hadipour et al.’s model for generalized Feistel structure and boomerang distinguishers on WARP. We show that a boomerang distinguisher with more active S-boxes may have a higher probability. It is caused by the semi-active S-boxes active only in one of the upper and lower differential trails, which are not considered in Hadipour et al.’s model. We classify the active S-boxes in the middle part E_m in more detail, according to the associated tables of DDT, DDT², FBCT and its variants in the computation formula of boomerang probability for E_m. Then, we propose an improved MILP model to search boomerang distinguishers for generalized Feistel structure. Applying our model to WARP, we find better boomerang distinguishers for all rounds than those found by Hadipour et al.’s model. For 15-round boomerang distinguisher on WARP, the probability is improved by a factor of 2^5.78. For the longest 23-round boomerang distinguisher, the probability is improved by a factor of 2^4.23, resulting in the best result presented on WARP so far. Exploiting the properties of two local structures and the probabilistic extension technique, we improve the 26-round rectangle attack and give the first 27-round rectangle attack on WARP, which extends the best previous rectangle attack by one round. Note that our findings do not threaten the security of WARP which iterates 41 rounds.