Paper 2020/1404

A Practical Key-Recovery Attack on 805-Round Trivium

Chen-Dong Ye and Tian Tian

Abstract

The cube attack is one of the most important cryptanalytic techniques against Trivium. Many improvements have been proposed and lots of key-recovery attacks based on cube attacks have been established. However, among these key-recovery attacks, few attacks can recover the 80-bit full key practically. In particular, the previous best practical key-recovery attack was on 784-round Trivium proposed by Fouque and Vannet at FSE 2013 with on-line complexity about $2^{39}$. To mount a practical key-recovery attack against Trivium on a PC, a sufficient number of low-degree superpolies should be recovered, which is around 40. This is a difficult task both for experimental cube attacks and division property based cube attacks with randomly selected cubes due to lack of efficiency. In this paper, we give a new algorithm to construct candidate cubes targeting at linear superpolies in cube attacks. It is shown by our experiments that the new algorithm is very effective. In our experiments, the success probability is $ 100\% $ for finding linear superpolies using the constructed cubes. As a result, we mount a practical key-recovery attack on 805-round Trivium, which increases the number of attacked initialisation rounds by 21. We obtain over 1000 cubes with linear superpolies for 805-round Trivium, where 42 linearly independent ones could be selected. With these superpolies, for 805-round Trivium, the 80-bit key could be recovered within on-line complexity $ 2^{41.40} $, which could be carried out on a single PC equipped with a GTX-1080 GPU in several hours. Furthermore, the new algorithm is applied to 810-round Trivium, a cube of size 43 is constructed and two subcubes of size 42 with linear superpolies for 810-round Trivium are found.