[Resource Topic] 2023/202: SAT-aided Automatic Search of Boomerang Distinguishers for ARX Ciphers (Long Paper)

Welcome to the resource topic for 2023/202

SAT-aided Automatic Search of Boomerang Distinguishers for ARX Ciphers (Long Paper)

Authors: Dachao Wang, Baocang Wang, Siwei Sun


In Addition-Rotation-Xor (ARX) ciphers, the large domain size obstructs the application of the boomerang connectivity table. In this paper, we explore the problem of computing this table for a modular addition and the automatic search of boomerang characteristics for ARX ciphers. We provide dynamic programming algorithms to efficiently compute this table and its variants. These algorithms are the most efficient up to now. For the boomerang connectivity table, the execution time is 4^2(n − 1) simple operations while the previous algorithm costs 8^2(n − 1) simple operations, which generates a smaller model in the searching phase. After rewriting these algorithms with boolean expressions, we construct the corresponding Boolean Satisfiability Problem models. Two automatic search frameworks are also proposed based on these models. This is the first time bringing the SAT-aided automatic search techniques into finding boomerang attacks on ARX ciphers. Finally, under these frameworks, we find out the first verifiable 10-round boomerang trail for SPECK32/64 with probability 2^{-29.15} and a 12-round trail for SPECK48/72 with probability 2^{-44.15}. These are the best distinguishers for them so far. We also perceive that the previous boomerang attacks on LEA are constructed with an incorrect computation of the boomerang connection probability. The result is then fixed by our frameworks.

ePrint: https://eprint.iacr.org/2023/202

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .