期刊名称:Electronic Colloquium on Computational Complexity
印刷版ISSN:1433-8092
出版年度:2001
卷号:2001
出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要:Many of the keystream generators which are used in practice are LFSR-based in the sense that they produce the keystream according to a rule y = C ( L ( x )) , where L ( x ) denotes an internal linear bitstream, produced by a small number of parallel linear feedback shift registers (LFSRs), and C denotes some nonlinear compression function. We present an n O (1) 2 (1 − ) (1+ ) n time bounded attack, the FBDD-attack, against LFSR-based generators, which computes the secret initial state x \booln from cn consecutive keystream bits, where denotes the rate of information, which C reveals about the internal bitstream, and c denotes some small constant. The algorithm uses Free Binary Decision Diagrams (FBDDs), a data structure for minimizing and manipulating Boolean functions. The FBDD-attack yields better bounds on the effective key length for several keystream generators of practical use, so a 0 656 n bound for the self-shrinking generator, a 0 6403 n bound for the A5/1 generator, used in the GSM standard, a 0 6 n bound for the E 0 encryption standard in the one level mode, and a 0 8823 n bound for the two-level E 0 generator used in the Bluetooth wireless LAN system.