Paper 2018/198

A Key-recovery Attack on 855-round Trivium

Ximing Fu, Xiaoyun Wang, Xiaoyang Dong, and Willi Meier

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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in CRYPTO 2018
Keywords
TriviumNullification TechniquePolynomial ReductionIV RepresentationKey-recovery Attack
Contact author(s)
fxm15 @ mails tsinghua edu cn
History
2018-06-03: revised
2018-02-22: received
See all versions
Short URL
https://ia.cr/2018/198
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/198,
      author = {Ximing Fu and Xiaoyun Wang and Xiaoyang Dong and Willi Meier},
      title = {A Key-recovery Attack on 855-round Trivium},
      howpublished = {Cryptology ePrint Archive, Paper 2018/198},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/198}},
      url = {https://eprint.iacr.org/2018/198}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.