Paper 2017/1063

Improved Division Property Based Cube Attacks Exploiting Low Degree Property of Superpoly

Qingju Wang and Yonglin Hao and Yosuke Todo and Chaoyun Li and Takanori Isobe and Willi Meier

Abstract

In this paper we investigate the sparse structure of the superpoly in cube attack, and further reduce the complexity of superpoly recovery. We apply our technique to stream cipher TRIVIUM and KREYVIUM. For TRIVIUM, benefited from our techniques, we, for the first time, can recover the superpoly of 833-rounds with cube dimension 73, and complexity $2^{76.91}$. Furthermore, for 833-rounds, we can find a new cube of dimension 74, with only one secret key bit involved, thus the complexity is $2^{75}$. For 839-rounds, we find a cube of dimension 78, with only one secret key bit involved in the superpoly. For KREYVIUM, the lower complexity evaluation enables us to recover the superpoly of 849-rounds with time complexity of $2^{81.7}$. Moreover, we find a new cube of dimension 102, which can achieve 888-rounds with complexity $2^{111.38}$. So far as we know, all of our results are the best.