Paper 2022/643

Accelerating the Best Trail Search on AES-Like Ciphers

Seonggyeom Kim, Korea University
Deukjo Hong, Jeonbuk National University
Jaechul Sung, University of Seoul
Seokhie Hong, Korea University

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 full-round 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 BOGI-based 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.

Note: Our codes and more detailed results can be found in The codes could be easily adapted to other ciphers or modified for clustering. Moreover, the obtained best trails of BOGI-based ciphers will be helpful for future design considerations.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in TOSC 2022
Substitution–Permutation Network (SPN) Matsui's Search Algorithm Bad Output must go to Good Input (BOGI)
Contact author(s)
jeffgyeom @ korea ac kr
deukjo hong @ jbnu ac kr
jcsung @ uos ac kr
shhong @ korea ac kr
2022-05-25: approved
2022-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Seonggyeom Kim and Deukjo Hong and Jaechul Sung and Seokhie Hong},
      title = {Accelerating the Best Trail Search on {AES}-Like Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2022/643},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.