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 language | English |
|---|---|
| Title of host publication | Cryptography and Coding : 12th IMA International Conference, Cryptography and Coding 2009 Cirencester, UK, DEcenber 2009 |
| Editors | Matthew G. Parker |
| Publisher | Springer |
| Publication date | 2009 |
| Pages | 133-152 |
| ISBN (Print) | 978-3-642-10867-9 |
| Publication status | Published - 2009 |
| Event | 12th IMA International Conference on Cryptography and Coding - Duration: 1 Jan 2009 → … |
Conference
| Conference | 12th IMA International Conference on Cryptography and Coding |
|---|---|
| Period | 01/01/2009 → … |
| Series | Lecture Notes of Computer Science |
|---|---|
| Number | 5921 |
| ISSN | 0302-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