Improving OBDD attacks against stream ciphers

OBDD-attacks against stream ciphers compute the secret initial state by generating a sequence of $\mathcal{O}(n)$ ordered binary decision diagrams (OBDDs) of maximal width $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$, where $n$ denotes the inner state length and $\alpha\in (0,1)$ is the compression rate of the cipher. We propose and experimentally verify the following strategy of avoiding the huge storage demand of $\mathcal{O}(2^{\frac{1-\alpha}{1+\alpha}n})$. (1) Generate in parallel two OBDDs $P$ and $Q$ such that $P \wedge Q$ has only a few satisfying assignments. (2) Compute the set $(P \wedge Q)^{-1}(1)$, containing the secret inner state, by a new breadth-first-search based algorithm. We show that this approach improves standard OBDD-attacks drastically.