Paper 2014/893

Advanced Algebraic Attack on Trivium

Frank Quedenfeld and Christopher Wolf

Abstract

This paper presents an algebraic attack against Trivium that breaks 625 rounds using only $4096$ bits of output in an overall time complexity of $2^{42.2}$ Trivium computations. While other attacks can do better in terms of rounds ($799$), this is a practical attack with a very low data usage (down from $2^{40}$ output bits) and low computation time (down from $2^{62}$). From another angle, our attack can be seen as a proof of concept: how far can algebraic attacks can be pushed when several known techniques are combined into one implementation? All attacks have been fully implemented and tested; our figures are therefore not the result of any potentially error-prone extrapolation, but results of practical experiments.

Note: Publication in MACIS proceedings. Full version here,

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Minor revision. MACIS 2015
Keywords
Triviumalgebraic modellingsimilar variablesElimLinsparse multivariate algebraequation solving over $\F_2$
Contact author(s)
frank quedenfeld @ googlemail com
History
2015-11-28: revised
2014-10-30: received
See all versions
Short URL
https://ia.cr/2014/893
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/893,
      author = {Frank Quedenfeld and Christopher Wolf},
      title = {Advanced Algebraic Attack on Trivium},
      howpublished = {Cryptology ePrint Archive, Paper 2014/893},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/893}},
      url = {https://eprint.iacr.org/2014/893}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.