Bivium as a Mixed-Integer Linear Programming Problem

摘要

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 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.