Improved method of searching for boomerang distinguishers on Feistel structures–applications to WARP, TWINE, LBlock, LBlock-s, and ALLPC
摘要
In recent years, automatic methods of searching for boomerang distinguishers have received widespread attention. Most previous works mainly focused on searching for boomerang distinguishers with the minimum weighted sum of active S-boxes. However, the boomerang distinguisher with the minimum weighted sum of active S-boxes may not be the optimal distinguisher. Thus, several good boomerang distinguishers are likely to be missed. In order to tackle this problem, we propose an improved method of searching for boomerang distinguishers based on Mixed-Integer Linear Programming (MILP). In our method, the search space for boomerang distinguishers is expanded by considering a larger range of the number of active S-boxes rather than being limited to the minimum weighted sum of active S-boxes. Therefore, some potential truncated boomerang distinguishers are obtained. In order to further improve truncated boomerang distinguishers, we optimize the number of active S-boxes in boomerang switches (the middle part) of truncated boomerang distinguishers. Then, under a specific truncated boomerang distinguisher, we instantiate the middle part of it and select the boomerang distinguisher with the highest probability in the middle part. Finally, we instantiate the entire truncated boomerang distinguisher. To demonstrate the advantages of our method, we apply it to multiple block ciphers with Generalized Feistel Structure (GFS), such as WARP, TWINE, LBlock, LBlock-s, and ALLPC. As a result, the previous best results on boomerang distinguishers for WARP, TWINE, LBlock, LBlock-s and ALLPC are improved.