International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Key-Recovery Attack on 855-round Trivium

Authors:
Ximing Fu
Xiaoyun Wang
Xiaoyang Dong
Willi Meier
Download:
DOI: 10.1007/978-3-319-96881-0_6 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: In this paper, we propose a key-recovery attack on Trivium reduced to 855 rounds. As the output is a complex Boolean polynomial over secret key and IV bits and it is hard to find the solution of the secret keys, we propose a novel nullification technique of the Boolean polynomial to reduce the output Boolean polynomial of 855-round Trivium. Then we determine the degree upper bound of the reduced nonlinear boolean polynomial and detect the right keys. These techniques can be applicable to most stream ciphers based on nonlinear feedback shift registers (NFSR). Our attack on 855-round Trivium costs time complexity $$2^{77}$$. As far as we know, this is the best key-recovery attack on round-reduced Trivium. To verify our attack, we also give some experimental data on 721-round reduced Trivium.
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28837,
  title={A Key-Recovery Attack on 855-round Trivium},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10992},
  pages={160-184},
  doi={10.1007/978-3-319-96881-0_6},
  author={Ximing Fu and Xiaoyun Wang and Xiaoyang Dong and Willi Meier},
  year=2018
}