Paper 2023/1408

Correlation Cube Attack Revisited: Improved Cube Search and Superpoly Recovery Techniques

Jianhua Wang, Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
Lu Qin, China UnionPay Co., Ltd., Shanghai, China, School of electronic information and electrical engineering, Shanghai Jiao Tong University, Shanghai, China
Baofeng Wu, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

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: (1) effectively recover algebraic normal form of the superpoly and extract out its low-degree factors; and (2) 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 (Crypto 2019) and accuracy of the monomial prediction technique (Asiacrypt 2020) 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. As a result, we have recovered the superpolys of three cubes given by Kesarwani et al. in 2020, only to find they do not have zero-sum property up to 842 rounds as claimed in their paper. To our knowledge, 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 $\mathbf{2^{80}\times 87.8\%}$, $\mathbf{2^{80}\times 83\%}$ and $\mathbf{2^{80}\times 65.7\%}$ keys that could be practically recovered, respectively, if we consider $\mathbf{2^{60}}$ as the upper bound for practical computational complexity. Besides, even for computers with computational power not exceeding $\mathbf{2^{52}}$ (resp. $\mathbf{2^{55}}$), we can still recover $\mathbf{58\%}$ (resp. $\mathbf{46.6\%}$) of the keys in the key space for 820 rounds (resp. 830 rounds). Our attacks have led 10 rounds more than the previous best practical attack.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in ASIACRYPT 2023
Correlation cube attackVariable substitutionVector numeric mappingMILPTrivium.
Contact author(s)
wangjianhua @ amss ac cn
qinlu @ unionpay com
wubaofeng @ iie ac cn
2023-09-24: approved
2023-09-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jianhua Wang and Lu Qin and Baofeng Wu},
      title = {Correlation Cube Attack Revisited: Improved Cube Search and Superpoly Recovery Techniques},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1408},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.