CryptoDB
A Practical Key-Recovery Attack on 805-Round Trivium
| Authors: |
|
|---|---|
| Download: | |
| 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
}