Cryptanalysis Against Filtered FCSR Generators

Feedback with carry shift registers (FCSR) is a new pseudorandom generator presented by A. Klapper and M. Goresky. Its key idea is to realize the addition of 2-adic number by the carry registers, which enables the FCSR sequences possess high linear complexity inherently. The maximal periodic FCSR sequence (l-sequence) enjoys outstanding pseudorandom properties and is the most important FCSR sequence. Considering that the addition module 2 can destroy the 2-adic structure of FCSR sequences, the idea that filtering FCSR sequences by a linear filter is always be concerned and researched widely.It is obvious that the linear filter plays an important role in the generator based on filtering FCSR. In this paper, we focus on the choice of the linear filter and find out that, when the cells selected by the filter belong to the leftmost cells of the main register, the stream cipher is insecure. In particular, when the number of selected cells is odd, both the time complexity and the data complexity needed by the attacker are lower than the even case.The nonlinear property of FCSR sequences is guaranteed by the carry registers, thus the cryptanalyses against the generator based on filtering FCSR all put their focus on the carry registers. In this paper, we discuss the distribution of the carry register state. We find that the state that all the carry registers are 0 appears more frequently than any other carry register state in one period. In detail, for a large class of n-stage Galois FCSR whose connection number is prime q, if the number of active carry registers l satisfies l≥10 and l + log2 l + 4≤n, then the frequency of the state that all the carry registers are 0 in one period is larger than 2^-[1/2]-5, which is far larger than the average 2^-l. Hence the distribution of Galois FCSR' carry register state is not balanced.