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. 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: secret-key cryptography / cryptanalysis

Date: received 25 Nov 2017

Contact author: vrs at ee iitb ac in

Available format(s): PDF | BibTeX Citation

Note: The paper presents computation of algebraic models of Bivium cipher using a Boolean solver.

Version: 20171127:133125 (All versions of this report)

Short URL: ia.cr/2017/1141

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]