Portal de Periódicos da CAPES

An Experimentally Verified Attack on 820-Round Trivium

2023; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-031-26553-2_19

1611-3349

Cheng Che, Tian Tian,

Coding theory and cryptography

The cube attack is one of the most important cryptanalytic techniques against Trivium. As the method of recovering superpolies becomes more and more effective, another problem of cube attacks, i.e., how to select cubes that can effectively attack, is attracting more and more attention. In this paper, we present a novel framework to search for valuable cubes whose superpolies have an independent secret variable each, i.e., a linear variable not appearing in any nonlinear term. To control online complexity, valuable cubes are selected from very few large cubes. New ideas are given on the large cube construction and the subcube sieve. As illustrations, we apply the new algorithm to the stream cipher Trivium. For 815-round Trivium, the complexity of full key-recovery attack is $$2^{47.32}$$ . For 820-round Trivium, the complexity of full key-recovery attack is $$2^{53.17}$$ . Strong experimental evidence shows that the full key-recovery attacks on 815- and 820-round Trivium could be completed within six hours and two weeks on a PC with two RTX3090 GPUs, respectively.