Content area
Full Text
Theory Comput. Systems 40, 101121 (2007) Theory of
DOI: 10.1007/s00224-005-1282-8
OBDD-Based Cryptanalysis of Oblivious Keystream Generators
Matthias Krause
Lehrstuhl Theoretische Informatik, Universitat Mannheim, 68131 Mannheim, [email protected]
Abstract. Many keystream generators of practical use consist of a certain number of linear feedback shift registers (LFSRs) combined with a nonlinear output automaton. For this type of generator, we present an algorithm computing the secret initial state x {0, 1}n from a short piece of corresponding keystream by performing 2(1)/(1+)n polynomial-time operations, where denotes the rate of information which the output keystream reveals about the internal bitstream produced by the LFSRs. The algorithm uses Ordered Binary Decision Diagrams (OBDDs), a data structure for minimizing and manipulating Boolean functions. We demonstrate the potential of our method by applying it to the self-shrinking generator and to the E0-generator used in the Bluetooth wireless system and obtain the best known short-keystream attacks for these generators.
1. Introduction
A keystream generator is a nite automaton E, which, starting from a secret initial state x {0, 1}n, produces an output keystream y = E(x) = y0 y1 y2 . Keystream generators are designed for fast online encryption of bitstreams which have to pass an insecure channel. A standard application is to ensure the over-the-air privacy of communicating via mobile cellular telephones. A plaintext bitstream p0, p1, p2,... is
encrypted into the ciphertext bitstream e0, e1, e2,... via the rule ei = pi yi . The legal receiver knows x and can decrypt the bitstream using the same rule. The only secret information is the initial state x, which is exchanged before starting the transmission using a suitable key-exchange protocol. To estimate the security of keystream generators, it is common to make the realistic assumption that an attacker knows not only the encrypted bitstream, but even some short piece of the plaintext, and therefore can easily compute
Computing Systems
2005 Springer Science+Business Media, Inc.
102 M. Krause
some piece of the keystream. Consequently, one necessary criterion for the security of a keystream generator is that there is no feasible way to compute the secret initial state x from y = E(x). Observe that a trivial exhaustive search attack can be performed with 2n encryption operations.
Many keystream generators of practical use consist of a...