Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Division Property, S-boxes, SAT, CNF, MILP, LED

Original Publication (with minor differences): IACR-ASIACRYPT-2021

Date: received 24 Sep 2021, last revised 12 Oct 2021

Contact author: aleksei at affine group

Available format(s): PDF | BibTeX Citation

Note: Full version (minor changes)

Version: 20211012:115939 (All versions of this report)

Short URL: ia.cr/2021/1285


[ Cryptology ePrint archive ]