zbMATH — the first resource for mathematics

Advanced algebraic attack on Trivium. (English) Zbl 06585031
Kotsireas, Ilias S. (ed.) et al., Mathematical aspects of computer and information sciences. 6th international conference, MACIS 2015, Berlin, Germany, November 11–13, 2015. Revised selected papers. Cham: Springer (ISBN 978-3-319-32858-4/pbk; 978-3-319-32859-1/ebook). Lecture Notes in Computer Science 9582, 268-282 (2016).
Summary: 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.
For the entire collection see [Zbl 1334.68018].
94A60 Cryptography
M4RIE; PolyBoRi; Trivium
Full Text: DOI