Cryptology ePrint Archive: Report 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.

Category / Keywords: boolean functions, cryptanalysis, stream ciphers

Date: received 25 Nov 2017, last revised 5 Mar 2018

Contact author: vrs at ee iitb ac in

Available format(s): PDF | BibTeX Citation

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

Version: 20180305:165459 (All versions of this report)

Short URL: ia.cr/2017/1141


[ Cryptology ePrint archive ]