  In this paper, we improve the cube attack by exploiting low-degree factors of
the superpoly w.r.t. certain "special" index set of cube (ISoC). This can be
viewed as a special case of the correlation cube attack proposed at Eurocrypt
2018, but under our framework more beneficial equations on the key variables
can be obtained in the key-recovery phase. To mount our attack, one has two
challenging problems: effectively recover algebraic normal form of the
superpoly and extract out its low-degree factors; and efficiently search a
large quantity of good ISoCs. We bring in new techniques to solve both of them.
First, we propose the variable substitution technique for middle rounds of a
cipher, in which polynomials on the key variables in the algebraic expressions
of internal states are substituted by new variables. This will improve
computational complexity of the superpoly recovery and promise more compact
superpolys that can be easily decomposed with respect to the new variables.
Second, we propose the vector numeric mapping technique, which seeks out a
tradeoff between efficiency of the numeric mapping technique and accuracy of
the monomial prediction technique in degree evaluation of superpolys. Combining
with this technique, a fast pruning method is given and modeled by MILP to
filter good ISoCs of which the algebraic degree satisfies some fixed threshold.
Thanks to automated MILP solvers, it becomes practical to comprehensively
search for good cubes across the entire search space. To illustrate the power
of our techniques, we apply all of them to Trivium stream cipher. The previous
best practical key recovery attack was on 820-round Trivium with complexity
$2^{53.17}$. We put forward 820-, 825- and 830-round practical key-recovery
attacks, in which there are 2^{80}\times 87.8%, 2^{80}\times 83% and
2^{80}\times 65.7% keys that could be practically recovered, respectively.
