A New Framework for Finding Nonlinear Superpolies in Cube Attacks Against Trivium-Like Ciphers

摘要

In this paper, we focus on traditional cube attacks against Trivium-like ciphers in which linear and nonlinear superpolies are experimentally tested. We provide a new framework on nonlinear superpoly recoveries by exploiting a kind of linearization technique. It worth noting that, in this new framework, the complexities of testing and recovering nonlinear superpolies are almost the same as those of testing and recovering linear superpolies. Moreover, extensive experiments show that by making use of the new framework, the probability to find a quadratic superpoly is almost twice as large as that to find a linear superpoly for Kreyvium and they are almost the same for Trivium. Hopefully, this new framework would provide some new insights on cube attacks against NFSR-based ciphers, and in particular make nonlinear superpolies potentially useful in the future cube attacks.