International Association
for Cryptologic Research

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 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.