Improved Practical BDD-based Cryptanalysis of Keystream Generators with application to Trivium

The Binary Decision Diagrams(BDD) have played important role in hardware verification, model checking, and logic synthesis, where they optimize the handling of complex Boolean expressions by reducing redundancy and ensuring canonical representation. Harish Sahu et. al. in 2017 gave a practical way to use ROBDDs to attack stream ciphers and compared different ways of operating AND operations between BDDs. We show that this method is not the universally fastest to perform a binary operation between any two objects. A successful attack requires the reduction of time and space complexity to the greatest extent possible. In this direction, we propose a new method that uses BDDs to attack any stream cipher with time complexity of $O(\frac{n}{4}\bar{M}^2)$, and demonstrate its application to a well known estream cipher, Trivium. We present Time and Space Analysis by means of several experiments and find that our method outperforms the earlier one in time and under certain conditions in space. Through comprehensive time and space analysis conducted via multiple experiments, we demonstrate that our method outperforms the previous approach in terms of time efficiency and, under specific conditions, in space efficiency as well.