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

Authors

  • Ling Sun Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; State Key Laboratory of Cryptology, P.O.Box 5159, Beijing, China; School of Cyber Science and Technology, Shandong University, Qingdao, China; Quan Cheng Shandong Laboratory, Jinan, China
  • 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:

https://doi.org/10.46586/tosc.v2023.i1.111-151

Keywords:

Automatic cryptanalysis, differential characteristic, SKINNY-128, PIPO, AES-based construction

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.

Downloads

Published

2023-03-10

Issue

Section

Articles

How to Cite

SoK: Modeling for Large S-boxes Oriented to Differential Probabilities and Linear Correlations. (2023). IACR Transactions on Symmetric Cryptology, 2023(1), 111-151. https://doi.org/10.46586/tosc.v2023.i1.111-151