Paper 2001/092

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.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. still not published but submitted
Keywords
stream ciphers
Contact author(s)
krause @ th informatik uni-mannheim de
History
2001-11-06: received
Short URL
https://ia.cr/2001/092
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2001/092,
      author = {Matthias Krause},
      title = {BDD-based Cryptanalysis of Keystream Generators},
      howpublished = {Cryptology ePrint Archive, Paper 2001/092},
      year = {2001},
      note = {\url{https://eprint.iacr.org/2001/092}},
      url = {https://eprint.iacr.org/2001/092}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.