Cryptanalysis of Bivium using a Boolean all solution solver

Virendra Sule; Anmol Yadav

Paper 2017/1141

Cryptanalysis of Bivium using a Boolean all solution solver

Virendra Sule and Anmol Yadav

Abstract

Cryptanalysis of Bivium is presented with the help of a new Boolean system solver algorithm. This algorithm uses a Boolean equation model of Bivium for a known keystream. The Boolean solver uses implicant based computation of satisfying assignments and is distinct from well known CNF-satisfiability solvers or algebraic cryptanalysis methods. The solver is also inherently parallel and returns all satisfying assignments of the system of equations in terms of implicants. Cryptanalysis of Bivium is classified in four categories of increasing strength and it is shown that the solver algorithm is able to complete the key recovery in category 2 in 48 hours by a Python code. (This benchmark is improved to 3 hours by a C++ code). Computational algorithms for formation of equations and symbolic operations are also developed afresh for handling Boolean functions and presented. Limitations of these implementations are determined with respect to Bivium model and its cryptanalysis which shall be useful for cryptanalysis of general stream ciphers.

Note: Few corrections were necessary in the previous submission. Equations were not formatted properly. New benchmark with C++ code is reported in this submission.

Metadata

Available format(s): PDF
Publication info: Preprint. MINOR revision.
Keywords: boolean functions cryptanalysis stream ciphers
Contact author(s): vrs @ ee iitb ac in
History: 2018-03-05: revised; 2017-11-27: received; See all versions
Short URL: https://ia.cr/2017/1141
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1141,
      author = {Virendra Sule and Anmol Yadav},
      title = {Cryptanalysis of Bivium using a Boolean all solution solver},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1141},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1141}
}