Skip to Main content Skip to Navigation
Journal articles

Efficient MILP Modelings for Sboxes and Linear Layers of SPN ciphers

Abstract : Mixed Integer Linear Programming (MILP) solvers are regularly used by designers for providing security arguments and by cryptanalysts for searching for new distinguishers. For both applications, bitwise models are more refined and permit to analyze properties of primitives more accurately than word-oriented models. Yet, they are much heavier than these last ones. In this work, we first propose many new algorithms for efficiently modeling any subset of F n 2 with MILP inequalities. This permits, among others, to model differential or linear propagation through Sboxes. We manage notably to represent the differential behaviour of the AES Sbox with three times less inequalities than before. Then, we present two new algorithms inspired from coding theory to model complex linear layers without dummy variables. This permits us to represent many diffusion matrices, notably the ones of Skinny-128 and AES in a much more compact way. To demonstrate the impact of our new models on the solving time we ran experiments for both Skinny-128 and AES. Finally, our new models allowed us to computationally prove that there are no impossible differentials for 5-round AES and 13-round Skinny-128 with exactly one input and one output active byte, even if the details of both the Sbox and the linear layer are taken into account.
Document type :
Journal articles
Complete list of metadatas
Contributor : Daniel Coggia <>
Submitted on : Tuesday, December 8, 2020 - 12:27:42 PM
Last modification on : Wednesday, December 9, 2020 - 3:40:31 AM


8705-Article Text-5396-1-10-20...
Files produced by the author(s)




Christina Boura, Daniel Coggia. Efficient MILP Modelings for Sboxes and Linear Layers of SPN ciphers. IACR Transactions on Symmetric Cryptology, Ruhr Universität Bochum, 2020, ⟨10.13154/tosc.v2020.i3.327-361⟩. ⟨hal-03046211⟩



Record views


Files downloads