Consider a keystream generator (KSG) with M bits of memory. For dimensional reasons, there exists at least one linear function L of any M + 1 consecutive output bits that is not balanced. Under reasonable hypotheses, L is independent of time, so L (essentially an ( M + 1 ) × 1 matrix) is a function of the initial state vector S0 of the KSG. The author’s linear sequential circuit approximation is used to find candidates for L. In order to exploit this weakness, a portion of the output proportional to the square of the sum, over all linear models of a given length, of the correlation with the zero function becomes a cryptographic design criterion.
The feasibility of this computation depends on the assumption that the “functions effectively depend on small subsets of the state variables.” I cannot decide whether this assumption is reasonable in all cases. However, the author is able to derive the required length of the keystream sequence to exploit the weakness for many KSGs. This seems to be the main improvement over the author’s earlier proceedings paper [1].
