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 ∈ {0, 1}~n from a short piece of corresponding keystream by performing 2~((1-α)/(1+α)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 E_0-generator used in the Bluetooth wireless system and obtain the best known short-keystream attacks for these generators.