International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Accelerating the Best Trail Search on AES-Like Ciphers

Authors:
Seonggyeom Kim , Korea University, Seoul, South Korea
Deukjo Hong , Jeonbuk National University, Jeonju, South Korea
Jaechul Sung , University of Seoul, Seoul, South Korea
Seokhie Hong , Korea University, Seoul, South Korea
Download:
DOI: 10.46586/tosc.v2022.i2.201-252
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9719
Search ePrint
Search Google
Abstract: In this study, we accelerate Matsui’s search algorithm to search for the best differential and linear trails of AES-like ciphers. Our acceleration points are twofold. The first exploits the structure and branch number of an AES-like round function to apply strict pruning conditions to Matsui’s search algorithm. The second employs permutation characteristics in trail search to reduce the inputs that need to be analyzed. We demonstrate the optimization of the search algorithm by obtaining the best differential and linear trails of existing block ciphers: AES, LED, MIDORI-64, CRAFT, SKINNY, PRESENT, and GIFT. In particular, our search program finds the fullround best differential and linear trails of GIFT-64 (in approx. 1 s and 10 s) and GIFT-128 (in approx. 89 h and 452 h), respectively.For a more in-depth application, we leverage the acceleration to investigate the optimal DC/LC resistance that GIFT-variants, called BOGI-based ciphers, can achieve. To this end, we identify all the BOGI-based ciphers and reduce them into 41,472 representatives. Deriving 16-, 32-, 64-, and 128-bit BOGI-based ciphers from the representatives, we obtain their best trails until 15, 15, 13, and 11 rounds, respectively. The investigation shows that 12 rounds are the minimum threshold for a 64-bit BOGIbased cipher to prevent efficient trails for DC/LC, whereas GIFT-64 requires 14 rounds. Moreover, it is shown that GIFT can provide better resistance by only replacing the existing bit permutation. Specifically, the bit permutation variants of GIFT-64 and GIFT-128 require fewer rounds, one and two, respectively, to prevent efficient differential and linear trails.
BibTeX
@article{tosc-2022-32085,
  title={Accelerating the Best Trail Search on AES-Like Ciphers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={201-252},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9719},
  doi={10.46586/tosc.v2022.i2.201-252},
  author={Seonggyeom Kim and Deukjo Hong and Jaechul Sung and Seokhie Hong},
  year=2022
}