Recovering decimation-based cryptographic sequences by means of linear CAs
This work addresses a security vulnerability in cryptographic systems using the shrinking generator, though it appears incremental as it builds on known linear modeling approaches.
The authors tackled the problem of cryptanalyzing the shrinking generator, a cryptographic sequence generator, by modeling its sequences as outputs of linear elementary cellular automata and exploiting their interleaved m-sequence structure, resulting in an algorithm that simplifies analysis despite the generator's intended non-linear design.
The sequences produced by the cryptographic sequence generator known as the shrinking generator can be modelled as the output sequences of linear elementary cellular automata. These sequences are composed of interleaved m-sequences produced by linear structures based on feedback shifts. This profitable characteristic can be used in the cryptanalysis of this generator. In this work we propose an algorithm that takes advantage of the inherent linearity of these cellular automata and the interleaved m-sequences. Although irregularly decimated generators have been conceived and designed as non-linear sequence generators, in practice they can be easily analysed in terms of simple linear structures.