Paper 2001/092

BDD-based Cryptanalysis of Keystream Generators

Matthias Krause

Abstract

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 $$ time bounded attack, the FBDD-attack, against LFSR-based generators, which computes the secret initial state $$ from $$ consecutive keystream bits, where $$ denotes the rate of information, which $$ reveals about the internal bitstream, and $$ 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 $$ bound for the self-shrinking generator, a $$ bound for the A5/1 generator, used in the GSM standard, a $$ bound for the $$ encryption standard in the one level mode, and a $$ bound for the two-level $$ generator used in the Bluetooth wireless LAN system.