Portal de Periódicos da CAPES

A Practical Key-Recovery Attack on 805-Round Trivium

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

10.1007/978-3-030-92062-3_7

1611-3349

Chen-Dong Ye, Tian Tian,

Physical Unclonable Functions (PUFs) and Hardware Security

The cube attack is one of the most important cryptanalytic techniques against Trivium. Many key-recovery attacks based on cube attacks have been established. However, few attacks can recover the 80-bit full key information practically. In particular, the previous best practical key-recovery attack was on 784-round Trivium proposed by Fouque and Vannet at FSE 2013. To mount practical key-recovery attacks, it requires a sufficient number of low-degree superpolies. It is difficult 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 linear superpolies. Our experiments show that the success probability is \( 100\% \) for finding linear superpolies using the constructed cubes. We obtain over 1000 linear superpolies for 805-round Trivium. With 42 independent linear superpolies, we mount a practical key-recovery attack on 805-round Trivium, which increases the number of attacked rounds by 21. The complexity of our attack is \( 2^{41.40} \), which could be carried out on a PC with a GTX-1080 GPU in several hours.