Abstract:

To attack nonlinear combined sequences, we propose a new method that only requires the stage of the linear feedback shift register's (LFSR) and enough sample bits to recover the initial states and the feedback polynomial. Complexity of the algorithm is studied. We show that security cannot be improved essentially by just increasing the number of LFSRs. We propose a new metric to evaluate the cryptographic ability of Boolean functions in order to resist this kind of attack, and study some properties of the metric. We show that this metric should be small in designing a nonlinear combined sequence. We gave all the functions that the new metric is 0 when the variable number is 2 and 3. An up-bound of the metric is given when the number of variable is equal to or greater than 4.

Key words:

Boolean function, nonlinear combined, Walsh spectra, correlation attack