A New Correlation Attack on Nonlinear Combining Generators

In this paper, the correlation properties of a nonlinear combining function over its support or zero set are investigated. Based on this characterization, a new attack on nonlinear combining generators is proposed. Our attack does not utilize traditional (non)linear statistics between the input and the output over the entire variable space, as the distinguishing process is rather applied to the restricted input space. The attack appears to be very efficient against nonlinear combining generators whose combining LFSRs are of relatively small input size. In many cases, our attack is a more favorable alternative than the known correlation attacks (but also than algebraic attacks in certain cases). To study the maximum correlation of a nonlinear combining function over its support or zero set, the notion of maximum distinguishable correlation is introduced. The relationship between the maximum distinguishable correlation and the nonlinearity of a combining function is then derived by using the normalized Walsh transform. Finally, we extend the usual notion of resiliency and discuss its implications towards the resistance against our attack.