Bivium as a Mixed Integer Programming Problem

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Trivium is a stream cipher proposed for the eSTREAM project. Raddum introduced some reduced versions of Trivium, named Bivium A and Bivium B. In this article we present a numerical attack on the Biviums. The main idea is to transform the problem of solving a sparse system of quadratic equations over $GF(2)$ into a combinatorial optimization problem. We convert the Boolean equation system into an equation system over $\mathbb{R}$ and formulate the problem of finding a $0$-$1$-valued solution for the system as a mixed-integer programming problem. This enables us to make use of several algorithms in the field of combinatorial optimization in order to find a solution for the problem and recover the initial state of Bivium. In particular this gives us an attack on Bivium B in estimated time complexity of $2^{63.7}$ seconds. But this kind of attack is also applicable to other cryptographic algorithms.
Original languageEnglish
Title of host publicationCryptography and Coding : 12th IMA International Conference, Cryptography and Coding 2009 Cirencester, UK, DEcenber 2009
EditorsMatthew G. Parker
PublisherSpringer
Publication date2009
Pages133-152
ISBN (Print)978-3-642-10867-9
Publication statusPublished - 2009
Event12th IMA International Conference on Cryptography and Coding -
Duration: 1 Jan 2009 → …

Conference

Conference12th IMA International Conference on Cryptography and Coding
Period01/01/2009 → …
SeriesLecture Notes of Computer Science
Number5921
ISSN0302-9743

Cite this

Borghoff, J., Knudsen, L. R., & Stolpe, M. (2009). Bivium as a Mixed Integer Programming Problem. In M. G. Parker (Ed.), Cryptography and Coding: 12th IMA International Conference, Cryptography and Coding 2009 Cirencester, UK, DEcenber 2009 (pp. 133-152). Springer. Lecture Notes of Computer Science, No. 5921