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 functionscryptanalysisstream 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/1141}},
      url = {https://eprint.iacr.org/2017/1141}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.