Paper 2025/2209

A New Practical Cube Attack via Recovering Numerous Superpolys

Abstract

Cube attack is one of the most powerful approaches for recovering keys of stream ciphers. Practical cube attacks generate several superpolys first and solve the system constructed by these superpolys afterward. Unlike previous practical attacks, we propose a new cube attack that transfers the difficulty of generating easy-solving superpolys to solving the system built by numerous nonlinear ones. In the offline phase, we recovered lots of nonlinear superpolys by improving the approach proposed by Delaune et al. at SAC 2022 in theory. In the online phase, taking advantage of the sparsity and asymmetry of these numerous superpolys, we present a new testing method to solve the constructed system efficiently. As applications, the latest attack could practically recover the keys for 820- and 832-round Trivium with the time complexity no more extensive than $2^{46}$ and $2^{50}$, while the previous highest number of rounds of Trivium that can be attacked practically is 830. We believe the proposed approach can be used to attack more rounds of Trivium and other stream ciphers.

Note: This paper is an extended version of our ToSC paper: Min Zhang and Yao Sun, “A New Practical Cube Attack via Recovering Numerous Superpolys,” IACR Transactions on Symmetric Cryptology, 2024. DOI: https://tosc.iacr.org/index.php/ToSC/article/view/11950. Compared with the ToSC version, this extended version includes the following main improvements: 1. Graph-Based Representation with a New Algebraic Interpretation. Sections 2.3 and 2.4 are revised with clear definitions , and Section 2.4 introduces a new algebraic structural view that provides a intuitive understanding of monomial propagation. Related examples and figures are also provided. 2. Constraint Generation Based on Rep Conditions. Proposition 2 is revised by deriving constraints directly from the conditions for a trail to be excluded from Rep. This provides a essential and reliable way to remove useless trails, and the example below Proposition 2 is also updated. 3. Clarification of the Proofs of Lemma 1 and Lemma 3. The proofs of Lemma 1 and Lemma 3 are revised to make the reasoning more rigorous and transparent. Additional clarifications are also added to other proofs to improve readability. 4. Experiments and Improved Results. A new subsection (Sec. 5.1) is added to test how many pair trails can be rejected by introducing additional pattern instances into the model. The experimental results (Sec. 5.1-5.3) are also improved and presented with clear comparisons, and a toy example (Example 2) is added to show how Algorithm 4 works in practice. 5. Evaluation and Open Problems. Section 6 is extended to provide an overall evaluation of our work, and list several open problems that merit further investigation.