Welcome to the resource topic for
**2001/092**

**Title:**

BDD-based Cryptanalysis of Keystream Generators

**Authors:**
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 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.

**ePrint:**
https://eprint.iacr.org/2001/092

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .