Modeling Large S-box in MILP and a (Related-key) Differential Attack on Full Round PIPO-64/128

Tarun Yadav; Manoj Kumar

Paper 2021/1388

Modeling Large S-box in MILP and a (Related-key) Differential Attack on Full Round PIPO-64/128

Tarun Yadav and Manoj Kumar

Abstract

Mixed integer linear programming (MILP) based tools are used to estimate the strength of block ciphers against the cryptanalytic attacks. The existing tools use partial difference distribution table (p-DDT) approach to optimize the probability of differential characteristics for large (≥8-bit) S-box based ciphers. We propose to use the full difference distribution table (DDT) with the probability of each possible propagation for MILP modeling of large S-boxes. This requires more than 16 variables to represent the linear inequalities of each propagation and corresponding probabilities. The existing tools (viz. Logic Friday) cannot handle the linear inequalities in more than 16 variables. In this paper, we present a new tool (namely MILES) to minimize the linear inequalities in more than 16 variables. This tool reduces the number of inequalities by minimizing the truth table corresponding to the DDT of S-box. We use our tool to minimize the linear inequalities for 8-bit S-boxes (AES and SKINNY) and get better results than existing tools. We show the application of MILES on 8-bit S-box based lightweight block cipher PIPO. There are 20621 inequalities in 23 variables corresponding to the possible propagations in DDT and these are minimized to 6035 inequalities using MILES. MILP model based on these linear inequalities is used to optimizethe probability of differential characteristics for round-reduced PIPO. MILP model based on these inequalities is used to optimize the probability of differential and impossible differential characteristics for PIPO-64/128 reduced to 9 and 4 rounds respectively. We present an iterative 2-round related-key differential characteristic with the probability of 2^{-4} and that is used to construct a full round related-key differential distinguisher with the probability of 2^{-24}. We present a major collision in PIPO-64/128 which produces the same ciphertext (C) by encrypting the plaintext (P) under two different keys.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Block Cipher Differential Cryptanalysis Lightweight Cryptography MILP S-box
Contact author(s): tarunyadav @ sag drdo in
manojkumar @ sag drdo in
History: 2022-02-28: revised; 2021-10-15: received; See all versions
Short URL: https://ia.cr/2021/1388
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1388,
      author = {Tarun Yadav and Manoj Kumar},
      title = {Modeling Large S-box in {MILP} and a (Related-key) Differential Attack on Full Round {PIPO}-64/128},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1388},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1388}
}