Improved Graph-Based Model for Recovering Superpoly on Trivium

Recovering superpoly for a given cube is the key step in cube attacks - an algebraic cryptanalysis method for symmetric ciphers. Since 2015, division property, monomial prediction, and enhanced techniques have been proposed to recover the exact superpoly by converting the problem into Mixed Integer Linear Programming (MILP) model, whose feasible solutions should be enumerated exactly. To penetrate more rounds, cryptanalysts try their best to reduce the scale of deduced MILP model to alleviate the bottleneck of computational cost for solving the model. In this paper, we investigate the graph-based modeling approach proposed in SAC 2021 to further reduce the number of feasible solutions for the model to handle and reduce the model’s scale in cube attacks on Trivium. Specifically, we develop an algorithm to search for pruning patterns and reveal a budget way to add the constraints concerning pruning patterns, thus eliminating a large number of solutions by adding fewer additional constraints. Under our measurement method, the pruning efficiency of added constraints is improved by 7 to 10 times more effective than in previous work. We also embed this modified graph-based model to the nested superpoly recovery framework proposed in ASIACRYPT 2021 and improve graph-based cube attack on Trivium by one round. The improved graph-based model performs better than monomial prediction with nested framework on 842- and 843-round cube attack of Trivium.