A linear attack on the random generator by a nonlinear combiner

We propose a linear attack on random generators by a nonlinear combiner. Th is attack assumes that the attacker knows the nonlinear function f(.) and g enerator polynomials of the LFSR in the random generator. It estimates the initial value of the LFSR from the tapped bits. The linear attack is as fol lows. (1) For each linear approximate function of f(.), make a candidate attackin g equation. It is composed of the initial state of one LFSR by eliminating the variables of the other LFSRs by using their generator polynomials. (2) Evaluate the probabilities with which the candidate equations hold and select the maximum one as the attacking equation. By mutual information analysis of the attacking equation, it is estimated t hat the number of tapped bits for the successful attack is much smaller tha n the period of the random generator. Computer simulations show that the es timated number is enough for successful attack. (C) 1999 Scripta Technica.