Paper 2018/1082

An Algebraic Method to Recover Superpolies in Cube Attacks

Chen-Dong Ye and Tian Tian

Abstract

Cube attacks are an important type of key recovery attacks against NFSR-based cryptosystems. The key step in cube attacks closely related to key recovery is recovering superpolies. However, in the previous cube attacks including original, division property based, and correlation cube attacks, the algebraic normal form of superpolies could hardly be shown to be exact due to an unavoidable failure probability or a requirement of large time complexity. In this paper, we propose an algebraic method aiming at recovering the exact algebraic normal forms of superpolies practically. Our method is developed based on degree evaluation method proposed by Liu in Crypto-2017. As an illustration, we apply our method to Trivium. As a result, we recover the algebraic normal forms of some superpolies for the 818-, 835-, 837-, and 838-round Trivium. Based on these superpolies, on a large set of weak keys, we can recover at least five key bits equivalently for up to the 838-round Trivium with a complexity of about $2^{37}$. Besides, for the cube proposed by Liu in Crypto-2017 as a zero-sum distinguisher for the 838-round Trivium, it is proved that its superpoly is not zero-constant. Hopefully, our method would provide some new insights on cube attacks against NFSR-based ciphers.