Paper 2021/1225

Massive Superpoly Recovery with Nested Monomial Predictions

Kai Hu, Siwei Sun, Yosuke Todo, Meiqin Wang, and Qingju Wang

Abstract

Determining the exact algebraic structure or some partial information of the superpoly for a given cube is a necessary step in the cube attack -- a generic cryptanalytic technique for symmetric-key primitives with some secret and public tweakable inputs. Currently, the division property based approach is the most powerful tool for exact superpoly recovery. However, as the algebraic normal form (ANF) of the targeted output bit gets increasingly complicated as the number of rounds grows, existing methods for superpoly recovery quickly hit their bottlenecks. For example, previous method stuck at round 842, 190, and 892 for Trivium, Grain-128AEAD, and Kreyvium, respectively. In this paper, we propose a new framework for recovering the exact ANFs of massive superpolies based on the monomial prediction technique (ASIACRYPT 2020, an alternative language for the division property). In this framework, the targeted output bit is first expressed as a polynomial of the bits of some intermediate states. For each term appearing in the polynomial, the monomial prediction technique is applied to determine its superpoly if the corresponding MILP model can be solved within a preset time limit. Terms unresolved within the time limit are further expanded as polynomials of the bits of some deeper intermediate states with symbolic computation, whose terms are again processed with monomial predictions. The above procedure is iterated until all terms are resolved. Finally, all the sub-superpolies are collected and assembled into the superpoly of the targeted bit. We apply the new framework to Trivium, Grain-128AEAD, and Kreyvium. As a result, the exact ANFs of the superpolies for 843-, 844- and 845-round Trivium, 191-round Grain-128AEAD and 894-round Kreyvium are recovered. Moreover, with help of the Möbius transform, we present a novel key-recovery technique based on superpolies involving all key bits by exploiting the sparse structures, which leads to the best key-recovery attacks on the targets considered.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in Asiacrypt 2021
Keywords
Cube AttackSuperpolyTriviumGrain-128AEADKreyviumDivision PropertyMonomial Prediction
Contact author(s)
hukai @ mail sdu edu cn
History
2021-11-19: last of 3 revisions
2021-09-20: received
See all versions
Short URL
https://ia.cr/2021/1225
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1225,
      author = {Kai Hu and Siwei Sun and Yosuke Todo and Meiqin Wang and Qingju Wang},
      title = {Massive Superpoly Recovery with Nested Monomial Predictions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1225},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1225}},
      url = {https://eprint.iacr.org/2021/1225}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.