Improved search models of boomerang distinguishers and application to LILLIPUT

Abstract Boomerang attack serves as a potent cryptanalytic tool for assessing the security of block ciphers. Over the past few years, various automatic search models for boomerang distinguishers have been proposed for block ciphers with different structures. This paper presents improved Mixed-Integer Linear Programming (MILP)-based search models for both single-key and related-key boomerang distinguishers. In the single-key scenario, we propose a method for dynamic allocation of active S-boxes. Our search model for single-key boomerang distinguishers characterizes the distinguisher probability more accurately, addressing the suboptimality issue caused by non-fixed weight assignments in prior models. In the related-key scenario, a search model for related-key boomerang distinguisher is proposed for block ciphers with bit-level key schedule algorithms, where the probability of the boomerang switch is ensured to be 1. To validate the effectiveness of our models, we apply them to the lightweight block cipher LILLIPUT based on Extended Generalized Feistel Networks (EGFN), conducting a comprehensive security analysis against boomerang attacks. Using our models, we successfully derive single-key boomerang distinguishers for 8 to 13 rounds and a 15-round related-key boomerang distinguisher. Notably, the data complexity required for 13-round single-key distinguishing attack is reduced by $${2^{ 3.172}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mn>3.172</mml:mn> </mml:mrow> </mml:msup> </mml:math> , and the 15-round related-key boomerang distinguisher with a probability of $${2^{ - 58}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow> <mml:mo>-</mml:mo> <mml:mn>58</mml:mn> </mml:mrow> </mml:msup> </mml:math> is currently the longest-round distinguisher among all known distinguishers for LILLIPUT. The application results fully demonstrate the capability of our models in evaluating the security of block ciphers. This research not only provides new insights and methods for the design and analysis of lightweight block ciphers, but also deepens the understanding of the security characteristics for LILLIPUT.