Pseudonoise sequences generated by linear feedback shift registers [1] with some nonlinear combining function have been proposed [2]–[5] for cryptographic applications as running key generators in stream ciphers. In this correspondence it will be shown that the number of trials to break these ciphers can be significantly reduced by using correlation methods. By comparison of computer simulations and theoretical results based on a statistical model, the validity of this analysis is demonstrated. Rubin [6] has shown that it is computationally feasible to solve a cipher proposed by Pless [2] in a known plaintext attack, using as few as 15 characters. Here, the number of ciphertext symbols is determined to perform a ciphertext-only attack on the Pless cipher using the correlation attack. Our conclusion from the analysis is that the pseudonoise generator's output sequence and the sequences generated by the linear feedback shift registers should be uncorrelated. This leads to constraints for the nonlinear combining function to be used.

Pseudonoise generators for cryptographic applications consisting of several linear feedback shift registers with a nonlinear combining function have been proposed as running key generators in stream ciphers. These running key generators eau sometimes be broken by (ciphertext-only) correlation attacks on individual subsequences. A new class of combining functions is presented, which provides better security against such attacks. The security is quantified by the smallest numberm + 1of subsequences that must be simultaneously considered in a correlation attack. A necessary condition for suchmth-order correlation-immunity is proved. A recursive construction is given that permits the construction of anmth-order immune combining function fornsubsequences for anymandnwith1 \leq m < n. Finally, the trade-off between the length of the linear equivalent of the nonlinear generator and the ordermof its immunity against correlation attacks is considered.