Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Cube attack, Division property, MILP, TRIVIUM, KREYVIUM

Date: received 25 Oct 2017, last revised 31 Oct 2017

Contact author: quwg at dtu dk,haoyonglin@yeah net,todo yosuke@lab ntt co jp,chaoyun li@esat kuleuven be,takanori isobe1@gmail com,willi meier@fhnw ch

Available format(s): PDF | BibTeX Citation

Version: 20171109:163204 (All versions of this report)

Short URL: ia.cr/2017/1063

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]