Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> 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. <s> BIB001 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> A common type of running key generator employed in stream cipher systems consists of n (mostly maximum-length) binary linear feedback shift registers (LFSR's) whose output sequences are combined by a nonlinear Boolean function f. The output of several combining functions previously proposed in the literature is known to be correlated to some input variables with probabilities p up to 0.75 (this holds, e.g. for the generators of Geffe, Pless, or Bruer). These generators have been broken in [2] for LFSR-lengths k < 50 (roughly), according to the computational complexity of the attack (based on an exhaustive search over all phases of the LFSR). But also other generators, e.g. certain types of multiplexed sequence generators, are known to be correlated to LFSR-components. In fact any generator having such correlations may be vulnerable to a correlation attack. <s> BIB002 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> This paper describes new techniques for fast correlation attacks, based on Gallager iterative decoding algorithm using parity-check equations of weight greater than 3. These attacks can be applied to any key-stream generator based on LFSRs and it does not require that the involved feedback polynomial have a low weight. We give a theoretical analysis of all fast correlation attacks, which shows that our algorithm with parity-check equations of weight 4 or 5 is usually much more efficient than correlation attacks based on convolutional codes or on turbo codes. Simulation results confirm the validity of this comparison. In this context, we also point out the major role played by the nonlinearity of the Boolean function used in a combination generator. <s> BIB003 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> This paper describes new methods for fast correlation attacks on stream ciphers, based on techniques used for constructing and decoding the by now famous turbo codes. The proposed algorithm consists of two parts, a preprocessing part and a decoding part. The preprocessing part identifies several parallel convolutional codes, embedded in the code generated by the LFSR, all sharing the same information bits. The decoding part then finds the correct information bits through an iterative decoding procedure. This provides the initial state of the LFSR. <s> BIB004 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> An algorithm for cryptanalysis of certain keystream generators is proposed. The developed algorithm has the following two advantages over other reported ones: (i) it is more powerful and (ii) it provides a high-speed software implementation, as well as a simple hard-ware one, suitable for high parallel architectures. The novel algorithm is a method for the fast correlation attack with significantly better performance than other reported methods, assuming a lower complexity and the same inputs. The algorithm is based on decoding procedures of the corresponding binary block code with novel constructions of the parity-checks, and the following two decoding approaches are employed: the a posterior probability based threshold decoding and the belief propagation based bit-flipping iterative decoding. These decoding procedures offer good trade-offs between the required sample length, overall complexity and performance. The novel algorithm is compared with recently proposed improved fast correlation attacks based on convolutional codes and turbo decoding. The underlying principles, performance and complexity are compared, and the gain obtained with the novel approach is pointed out. <s> BIB005 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> This paper describes a novel fast correlation attack of stream ciphers. The salient feature of the algorithm is the absence of any pre-processing or iterative phase, an usual feature of existing fast correlation attacks. The algorithm attempts to identify a number of bits of the original linear feedback shift register (LFSR) output from the received bits of the ciphertext. These are then used to construct a system of linear equations which are subsequently solved to obtain the initial conditions. The algorithm is found to perform well for LFSRs of large sizes but having sparse polynomials. It may be noted that such polynomials have low Hamming weight which is one more than the number of feedback connections or taps of the corresponding LFSR. Its performance is good in situations even where limited cipherlength is available. Another important contribution of the paper is a modification of the approach when the LFSR outputs are combined by a function which is correlation immune and perhaps, unknown to the decrypter. <s> BIB006 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Correlation Attacks <s> At Crypto'2000, Johansson and Jonsson proposed a fast correlation attack on stream ciphers based on the Goldreich-Rubinfeld-Sudan algorithm. In this paper we show that a combination of their approach with techniques for substituting keystream and evaluating parity-checks gives us the most efficient fast correlation attack known so far. An application of the new algorithm results in the first-known near-practical key recovery attack on the shrinking generator with the parameters suggested by Krawczyk in 1994, which was verified in the 40-bit data LFSR case for which the only previously known efficient attacks were distinguishing attacks. <s> BIB007
Correlation attack is a class of known plaintext attack. These attacks are widely applicable to stream ciphers; especially to design based on feedback shift registers. A correlation attack tries to extract some information about the initial state from the output keystream by exploiting the weaknesses in the combining function of the design. Siegenthaler first introduced the Correlation attack against combination generator BIB001 in 1985 but Meier and Staffelbach further improved this attack in 1988 as Fast Correlation Attack BIB002 . Zhang and Feng proposed an improved fast correlation attack on stream ciphers in BIB007 . This attack was further discussed and applied in BIB005 BIB003 BIB004 BIB006 . Correlationimmune functions need to be implemented for avoiding such attacks. In the case of LFSRs, the irregular clocking is one of the concepts to avoid linearity that will help countering this attack.