Accelerating the Best Trail Search on AES-Like Ciphers

Seonggyeom Kim, Deukjo Hong, Jaechul Sung, Seokhie Hong

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish
Pages (from-to)201-252
Number of pages52
JournalIACR Transactions on Symmetric Cryptology
Issue number2
StatePublished - 10 Jun 2022


  • Bad Output must go to Good Input (BOGI)
  • Best Differential Trail
  • Best Linear Trail
  • Matsui’s Search Algorithm
  • Substitution-Permutation Network (SPN)


Dive into the research topics of 'Accelerating the Best Trail Search on AES-Like Ciphers'. Together they form a unique fingerprint.

Cite this