Paper 2021/1285

Convexity of division property transitions: theory, algorithms and compact models

Aleksei Udovenko

Abstract

Integral cryptanalysis is a powerful tool for attacking symmetric primitives, and division property is a state-of-the-art framework for finding integral distinguishers. This work describes new theoretical and practical insights into traditional bit-based division property. We focus on analyzing and exploiting monotonicity/convexity of division property and its relation to the graph indicator. In particular, our investigation leads to a new compact representation of propagation, which allows CNF/MILP modeling for larger S-Boxes, such as 16-bit Super-Sboxes of lightweight block ciphers or even 32-bit random S-boxes. This solves the challenge posed by Derbez and Fouque (ToSC 2020), who questioned the possibility of SAT/SMT/MILP modeling of 16-bit Super-Sboxes. As a proof-of-concept, we model the Super-Sboxes of the 8-round LED by CNF formulas, which was not feasible by any previous approach. Our analysis is further supported by an elegant algorithmic framework. We describe simple algorithms for computing division property of a set of $n$-bit vectors in time $O(n2^n)$, reducing such sets to minimal/maximal elements in time $O(n2^n)$, computing division property propagation table of an $n\times m$-bit S-box and its compact representation in time $O((n+m)2^{n+m})$. In addition, we develop an advanced algorithm tailored to "heavy" bijections, allowing to model, for example, a randomly generated 32-bit S-box.

Note: Full version (minor changes)

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2021
DOI
10.1007/978-3-030-92062-3_12
Keywords
Division PropertyS-boxesSATCNFMILPLED
Contact author(s)
aleksei @ affine group
History
2021-11-30: last of 2 revisions
2021-09-24: received
See all versions
Short URL
https://ia.cr/2021/1285
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1285,
      author = {Aleksei Udovenko},
      title = {Convexity of division property transitions: theory, algorithms and compact models},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1285},
      year = {2021},
      doi = {10.1007/978-3-030-92062-3_12},
      note = {\url{https://eprint.iacr.org/2021/1285}},
      url = {https://eprint.iacr.org/2021/1285}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.