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.