Paper 2026/735

CLAASP-MP: An Automated MILP Framework for Monomial Prediction

Abstract

As AI increasingly automates cryptanalytic programming, transparent and reproducible frameworks are essential for making generated results human-verifiable. We present CLAASP-MP, a monomial-prediction tool integrated into CLAASP and based on the three-subset division property without unknown subset (3SDP-woU). CLAASP-MP generates a Mixed Integer Linear Programming (MILP) model directly from the CLAASP component graph, supporting S-boxes, linear layers, Boolean operations, modular addition and multiplication, and linear and nonlinear feedback shift registers. For selected output bits, CLAASP-MP computes the algebraic normal form (ANF) for small numbers of rounds, derives superpolies for a chosen cube, and bounds the algebraic degree with respect to plaintext, key, or IV variables. It detects absent monomials through vanishing ANF coefficients, zero superpolies, or degree bounds, thereby identifying balanced outputs and integral distinguishers. We evaluate CLAASP-MP on block ciphers, permutations, and stream-cipher update functions. For block ciphers, we reproduce known distinguishers, find new cubes, and report the first integral distinguishers for SAECHAM. For Splight, we reach rounds 10 and 11, despite a previous two-subset division-property search reporting no 10-round distinguisher. On MSX-128, a $96$-dimensional cube leaves $64$ of $128$ output bits balanced after 7 rounds. For permutations, we extend the best-known division-property distinguishers for ChaCha and Salsa from 6 and 5 rounds, respectively, to 6.75 rounds; give the first such distinguishers for Forr\'o; and reduce the data complexity for Chaskey-Pi from $2^{64}$ to $2^{23}$ at round 3 and from $2^{127}$ to $2^{122}$ at round 4. For stream ciphers, we find new 36-dimensional cubes for Bivium, extend the tight degree bounds for Trivium to later initialization clocks, and reproduce published superpolies. These results establish CLAASP-MP as a unified, practical, and human-verifiable framework for monomial prediction across symmetric primitives.

Note: Revised version. Added results on SAECHAM, Splight, Forró, Chaskey-Pi, and uKNIT-BC.