International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Practical Key-Recovery Attack on 805-Round Trivium

Authors:
Chen-Dong Ye , PLA Strategic Support Force Information Engineering University
Tian Tian , PLA Strategic Support Force Information Engineering University
Download:
DOI: 10.1007/978-3-030-92062-3_7
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2021
Abstract: 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.
Video from ASIACRYPT 2021
BibTeX
@inproceedings{asiacrypt-2021-31410,
  title={A Practical Key-Recovery Attack on 805-Round Trivium},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-030-92062-3_7},
  author={Chen-Dong Ye and Tian Tian},
  year=2021
}