[Resource Topic] 2023/1237: More Balanced Polynomials: Cube Attacks on 810- and 825-Round Trivium with Practical Complexities

Resource Secret-key cryptography
#1

Welcome to the resource topic for 2023/1237

Title:
More Balanced Polynomials: Cube Attacks on 810- and 825-Round Trivium with Practical Complexities

Authors: haolei, Jiahui He, Kai Hu, Meiqin Wang

Abstract:

The key step of the cube attack is to recover the special polynomial, the superpoly, of the target cipher. In particular, the balanced superpoly, in which there exists at least one secret variable as a single monomial and none of the other monomials contain this variable, can be exploited to reveal one-bit information about the key bits. However, as the number of rounds grows, it becomes increasingly difficult to find such balanced superpolies. Consequently, traditional methods of searching for balanced superpolies soon hit a bottleneck. Aiming at performing a cube attack on more rounds of Trivium with a practical complexity, in this paper, we present three techniques to obtain sufficient balanced polynomials.

  1. Based on the structure of Trivium, we propose a variable substitution technique to simplify the superpoly.
  2. Obtaining the additional balanced polynomial by combining two superpolies to cancel the two-degree terms.
  3. We propose an experimental approach to construct high-quality large cubes which may contain more subcubes with balanced superpolies and a heuristic search strategy for their subcubes whose superpolies are balanced.
    To illustrate the power of our techniques, we search for balanced polynomials for 810- and 825-round Trivium. As a result, we can mount cube attacks against 810- and 825-round Trivium with the time complexity of 2^{44.17} and 2^{53.17} round-reduced Trivium initializations, respectively, which can be verified in 48 minutes and 18 days on a PC with one A100 GPU. For the same level of time complexity, this improves the previous best results by 2 and 5 rounds, respectively.

ePrint: https://eprint.iacr.org/2023/1237

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .