Advanced Algebraic Attack on Trivium

Frank Quedenfeld; Christopher Wolf

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 bits of output in an overall time complexity of Trivium computations. While other attacks can do better in terms of rounds (), this is a practical attack with a very low data usage (down from output bits) and low computation time (down from ). 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: Trivium algebraic modelling similar variables ElimLin sparse multivariate algebra equation solving over
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: 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},
      url = {https://eprint.iacr.org/2014/893}
}