International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

SAT-aided Automatic Search of Boomerang Distinguishers for ARX Ciphers

Authors:
Dachao Wang , State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an, China
Baocang Wang , State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an, China
Siwei Sun , School of Cryptology, University of Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing, China
Download:
DOI: 10.46586/tosc.v2023.i1.152-191
URL: https://tosc.iacr.org/index.php/ToSC/article/view/10311
Search ePrint
Search Google
Abstract: 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 42(n − 1) simple operations while the previous algorithm costs 82(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.
BibTeX
@article{tosc-2023-33057,
  title={SAT-aided Automatic Search of Boomerang Distinguishers for ARX Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 1},
  pages={152-191},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/10311},
  doi={10.46586/tosc.v2023.i1.152-191},
  author={Dachao Wang and Baocang Wang and Siwei Sun},
  year=2023
}