Study On Fast Correlation Attacks On Nonlinear Combination Stream Ciphers

This paper researches on fast correlation attacks on nonlinear combination stream ciphers. In chapter one, nonlinear combination generators, and development and model of fast correlation attacks on nonlinear combination generators are introduced. In chapter two, the fast correlation attacks based on low-density parity-check codes are systemic introduced. In chapter three, the fast correlation attacks based on convolutional codes and Turbo codes are introduced. In chapter four, we describe briefly a kind of fast correlation attacks presented by [22], then based on our generalization of the procomputation phase in [22], we presented two new algorithms Cl and C2 based on hypothesis testing and ML-decoding. Theoretical analysis of the new algorithms indicates that both of them have high probability of attacks success, but the computational complexity of decoding phase of algorithm Cl is linear increased, and the computational complexity of decoding phase of algorithm C2 increased not so much as algorithm Cl's by linear increase the computational complexity of precomputation phase and the decoding phase compute in parallel. Finally, we present a precomputation algorithm based on dump order in case of t 0, w = 0. In chapter five, fast correlation attacks based on reconstruction of linear polynomials in [23 us introduced and some error in [23] when analyses algorithm is pointed out.