A Novel Approach to Algebraic and Fast Correlation Attacks for Cryptanalysis of Certain Keystream Generators

摘要

This paper proposes a novel approach for cryptanalysis of keystream generators based on the composition of a linear finite state machine (LFSM) and nonlinear mapping. The proposed approach includes a dedicated decimation of the sample for cryptanalysis. Oppositely to the previously reported methods, the proposed one also identifies and uses certain characteristics of the LFSM state-transition matrix in order to reduce the nonlinearity of the system of overdefined equations employed in an algebraic attack scenario or to reduce the noise introduced due to the linearization of the nonlinear function which corrupts the linear equations employed in a correlation attack scenario. The developed method is employed for efficient cryptanalysis of the nonlinear combination keystream generator recently reported at INDOCRYPT 2004.