Content area
Abstract
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 [?] {0,1}n from a short piece of corresponding keystream by performing 2(1 - a)/(1 + a)n polynomial-time operations, where ? 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 E0-generator used in the Bluetooth wireless system and obtain the best known short-keystream attacks for these generators. [PUBLICATION ABSTRACT]