__
TR01-078 | 6th November 2001 00:00
__

#### BDD-based Cryptanalysis of Keystream Generators

**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 $n^{O(1)} 2^{(1-\alpha)/(1+\alpha)n}$ time bounded attack, the FBDD-attack,

against LFSR-based generators, which computes the secret initial state

$x\in\booln$ from $cn$ consecutive keystream bits, where $\alpha$ 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.656n$ bound for the self-shrinking generator, a $0.6403 n$ bound for the A5/1 generator,

used in the GSM standard, a $0.6n$

bound for the $E_0$ encryption standard in the one level mode,

and a $0.8823n$ bound for the two-level $E_0$ generator used in the Bluetooth wireless LAN system.