International Association for Cryptologic Research

International Association
for Cryptologic Research


SoK: Modeling for Large S-boxes Oriented to Differential Probabilities and Linear Correlations

Ling Sun
Meiqin Wang , Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China; Quan Cheng Shandong Laboratory, Jinan, China
DOI: 10.46586/tosc.v2023.i1.111-151
Search ePrint
Search Google
Abstract: Automatic methods for differential and linear characteristic search are well-established at the moment. Typically, the designers of novel ciphers also give preliminary analytical findings for analysing the differential and linear properties using automatic techniques. However, neither MILP-based nor SAT/SMT-based approaches have fully resolved the problem of searching for actual differential and linear characteristics of ciphers with large S-boxes. To tackle the issue, we present three strategies for developing SAT models for 8-bit S-boxes that are geared toward differential probabilities and linear correlations. While these approaches cannot guarantee a minimum model size, the time needed to obtain models is drastically reduced. The newly proposed SAT model for large S-boxes enables us to establish that the upper bound on the differential probability for 14 rounds of SKINNY-128 is 2−131, thereby completing the unsuccessful work of Abdelkhalek et al. We also analyse the seven AES-based constructions C1 - C7 designed by Jean and Nikolić and compute the minimum number of active S-boxes necessary to cause an internal collision using the SAT method. For two constructions C3 and C5, the current lower bound on the number of active S-boxes is increased, resulting in a more precise security analysis for these two structures.
  title={SoK: Modeling for Large S-boxes Oriented to Differential Probabilities and Linear Correlations},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2023, Issue 1},
  author={Ling Sun and Meiqin Wang},