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 - Cirencester, United Kingdom Duration: 15 Dec 2009 → 17 Dec 2009 Conference number: 12 |
Conference
| Conference | 12th IMA International Conference on Cryptography and Coding |
|---|---|
| Number | 12 |
| Country/Territory | United Kingdom |
| City | Cirencester |
| Period | 15/12/2009 → 17/12/2009 |
| Series | Lecture Notes of Computer Science |
|---|---|
| Number | 5921 |
| ISSN | 0302-9743 |