Embedding Attacks on Simple Clock-controlled Sequence Generators

William Chambers
Department of Electronic and Electrical Engineering, Kings College London

I shall describe a number of attacks proposed recently on simple binary clock-controlled sequence generators, where one linear feedback shift-register determines the clocking of another shift-register which produces the output. (The connection polynomials are assumed known.) In particular I shall consider the step[1..D] generator, the shrinking generator, and the closely related alternating-step generator. The basic idea is to find out where and with what frequency or probability the output binary sequence can be embedded in the sequence produced by the clock-controlled shift-register. After describing methods for finding the most likely places for the embedding, I then examine ways of finding 'a postiori' probabilities for the bits in the clocking sequence, and hence make possible fast correlation attacks on the control shift register.