Improving the generalized correlation attack against stream ciphers by using bit parallelism

  • Slobodan Petrovic


It is well known that a pseudorandom generator scheme employing irregularly clocked
Linear Feedback Shift Registers (LFSRs) can be broken using the generalized correlation
attack, in which the constrained edit distance between the intercepted noised output se-
quence of the generator and the output sequence of a particular independent LFSR inside
the generator is computed. The most time-consuming part of the attack is the very con-
strained edit distance computation, whose time complexity is quadratic in the length of the
intercepted sequence. In this paper, we apply constrained bit-parallel approximate search
in the attack instead of the edit distance computation. We discuss the advantages and the
challenges of using this technique in cryptanalysis.