International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A New Practical Cube Attack via Recovering Numerous Superpolys

Authors:
Min Zhang
Yao Sun
Download:
DOI: 10.46586/tosc.v2024.i4.38-63
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11950
Search ePrint
Search Google
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 246 and 250, 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.
BibTeX
@article{tosc-2024-34888,
  title={A New Practical Cube Attack via Recovering Numerous Superpolys},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2024},
  pages={38-63},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11950},
  doi={10.46586/tosc.v2024.i4.38-63},
  author={Min Zhang and Yao Sun},
  year=2024
}