| |
| | ECCC Report TR01-078 and related Papers (Site not responding. Last check: 2007-10-20) |
 | | 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 $xinbooln$ 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. |
| www.eccc.uni-trier.de /eccc-reports/2001/TR01-078 (157 words) |
|