Time and Space Complexity Reduction of a Cryptanalysis Algorithm

Abstract

Binary Decision Diagram (in short BDD) is an efficient data structure which has been used widely in computer science and engineering. BDD-based attack in key stream cryptanalysis is one of the best forms of attack in its category. In this paper, we propose a new key stream attack which is based on ZDD(Zero-suppressed BDD). We show how a ZDD-based key stream attack is more efficient in time and space complexity over its BDD-based variant against the E0 type of the Bluetooth security mechanism. We implemented it by using the CUDD - Colorado University Decision Diagram package. Experimental results show great improvements. We have also derived a mathematical proof, which shows that it is better than the BDDbased attack method even for the worst case analysis.