Cryptology ePrint Archive: Report 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.

Category / Keywords: secret-key cryptography / Trivium, algebraic modelling, similar variables, ElimLin, sparse multivariate algebra, equation solving over $\F_2$

Original Publication (with minor differences): MACIS 2015

Date: received 29 Oct 2014, last revised 28 Nov 2015

Contact author: frank quedenfeld at googlemail com

Available format(s): PDF | BibTeX Citation

Note: Publication in MACIS proceedings. Full version here,

Version: 20151128:173920 (All versions of this report)

Short URL: ia.cr/2014/893

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]