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 .