Researches On Decimation Attack Of Stream Ciphers

Eric Filiol presents a new attack method of stream ciphers named decimation attack in the India-INDOCRYPT 2000. The main idea is as follows. Firstly, we select a decimation distance d such that the linear complexity L_d of the decimated sequence of the Lth linear feedback shiftregister (LFSR) less than L. Secondly, we use the decimated sequence of similar sequence of the original sequence to attack the decimated sequence of the original sequence. By this way we can obtain the initial state of the decimated sequence and L_d bits key. Finally, we can finish thedecimation attack and obtain the initial state of the original sequence with the L_d bits key.Because we reduce the series of original LFSR, so the practical performance of the attack is increased.We study the decimation attack from the point of view how we perform the decimation attack in practice. The main results of the paper are listed below:(1) The relationship between the linear complexity of the original sequence and the decimated sequence is presented. It is proved that: the linear complexity of the dth decimated sequence of Lth m sequence is equal to the L for all integers d(0