Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleOptimising Gr\"obner bases on Bivium.
Author(s) Tobias Eibach, Enrico Pilz, Gunnar Völkel
TypeArticle in Journal
AbstractBivium is a reduced version of the stream cipher Trivium. In this paper we investigate how fast a key recovery attack on Bivium using Gröbner bases is. First we explain the attack scenario and the cryptographic background. Then we identify the factors that have impact on the computation time and show how to optimise them. As a side effect these experiments benchmark several Gröbner basis implementations. The optimised version of the Gröbner attack has an expected running time of 239.12 s, beating the attack time of our previous SAT solver attack by a factor of more than 330. Furthermore this approach is faster than an attack based on BDDs, an exhaustive key search, a generic time-memory trade-off attack and a guess-and-determine strategy.
KeywordsBivium, Trivium, Gröbner basis, Stream cipher, Algebraic attack, Benchmark
ISSN1661-8270; 1661-8289/e
URL http://link.springer.com/article/10.1007%2Fs11786-009-0016-7
JournalMath. Comput. Sci.
PublisherSpringer (Birkh\"auser), Basel
Translation No
Refereed No