**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 $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.

**Category / Keywords: **secret-key cryptography / stream ciphers

**Publication Info: **still not published but submitted

**Date: **received 6 Nov 2001

**Contact author: **krause at th informatik uni-mannheim de

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20011106:175046 (All versions of this report)

**Short URL: **ia.cr/2001/092

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]