Algebraic Attack on the More Generalized Clock-Controlled Alternating Step Generator

摘要

The More Generalized Clock-Controlled Alternating Step Generator, MGCCASG, is a clock-controlled sequence generator proposed by Kanso in 2004. This generator consists of three feedback shift registers with lengths 1, m and n bits. The first register is clocked regularly and controls the clocking of the two others. At each time unit t, the two other shift registers are clocked r(t) times (or not clocked) (resp. s(t) times or not clocked) depending on the clock-control bits in the first register. The values of r(t) and s(t) are determined according to the values of W_B and W_C bits of the first register respectively. The special case when (r(t) = r; r > 1) and (s(t) = s; s > 1) is the Alternating Step(r, s) Generator proposed by Kanso, and the special case when r(t) = s(t) = 1 is the original and well known Alternating Step Generator. Kanso claims there is no efficient attack against the MGCCASG since the positions and the values of the W_B and W_C bits are kept secret and therefore, r(t) and s(t) are unknown. In this paper, we present an algebraic attack on this structure using 4M bits of the output sequence to find the secret key with a computational complexity of O(lM~2 2~(M+l+6) (W_B+ W_C)) and where M = max(m, n). In the case when m = n = l = 64 and W_B = W_C = 8, our attack can find the secret key using 256 output bits and a complexity of O(2~(156)) steps, while the author claims that the best attack needs O(2~(665.8)) steps and the exhaustive search needs O(2~(774.8)) steps.