OBDD-based cryptanalysis of oblivious keystream generators

Many keystream generators of practical use consist of a certain number of linear feedback shift registers (LFSRs) combined with a nonlinear output automaton. For this type of generator, we present an algorithm computing the secret initial state x is an element of{0, 1}(n) from a short piece of corresponding keystream by performing 2((1-alpha)/(1+alpha)n) polynomial-time operations, where a denotes the rate of information which the output keystream reveals about the internal bitstream produced by the LFSRs. The algorithm uses Ordered Binary Decision Diagrams (OBDDs), a data structure for minimizing and manipulating Boolean functions. We demonstrate the potential of our method by applying it to the self-shrinking generator and to the Eo-generator used in the Bluetooth wireless system and obtain the best known short-keystream attacks for these generators.