Optimized Linear Attack against Stream Ciphers of Pseudo Random Number Generators Using Non-linear Combiner

摘要

The generator that is the target of this attack consists of LFSRs (Linear Feedback Shift Registers) and a non linear function f(•). The attack equation (AEQ) is derived from the linear approximate function f(•) of f(•) and the generator polynomials of the LFSRs. AEQ focuses on the output sequence of one LFSR, by eliminating the initial values of the other LFSRs in a function f(•). The performance of AEQ depends on the number of terms and the degree of the elimination polynomial. We derive an efficient algorithm for determining an optimal elimination polynomial. With this attack, we can determine the initial value of the LFSR from the tapped bits whose number is much smaller than the period of the random generator.