Cryptanalytic Attack on CryptographicSequence Generators: The Class of Clock-Controlled Shrinking Generators

摘要

The shrinking generator is a very popular sequence generator with cryptographic applications. Nowadays, it is still considered as a secure keystream generator. In this work, it is shown that the knowledge of only a low number of generated bits is sufficient to break it. Indeed, whereas the linear complexity of the generated sequence (the shrunken sequence) is bounded by A·2~(S-2) < LC ≤ A · 2~(S-1) (A and S being the lengths of the two component registers), we claim that the generator can be cryptanalyzed with the knowledge of A · S intercepted bits and simple computations. Such a result is proven thanks to the definition of the shrunken sequences as a particular kind of interleaved sequences. A similar attack can be extended to any other generator of the class of clock-controlled shrinking generators. Furthermore, this paper confirms that certain bits of the interleaved sequences have a greater strategic importance than others, which must be considered as a proof of weakness of interleaved sequence generators regarding their use in cryptography.