A linear attack on the random generator by a nonlinear combiner

✍ Scribed by Hidema Tanaka; Toshinobu Kaneko

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 777 KB
• Volume: 82
• Category: Article
• ISSN: 1042-0967
• DOI: 10.1002/(sici)1520-6440(199905)82:5<72::aid-ecjc9>3.0.co;2-i

✦ Synopsis

We propose a linear attack on random generators by a nonlinear combiner. This attack assumes that the attacker knows the nonlinear function f(×) and generator 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 follows.

(1) For each linear approximate function of f(×), make a candidate attacking 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 that the number of tapped bits for the successful attack is much smaller than the period of the random generator. Computer simulations show that the estimated number is enough for successful attack.