Cryptanalysis Techniques for Stream Cipher: A Survey <s> Divide and Conquer Attack <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> Divide and Conquer Attack <s> A finite state machine driven by n independent sources each generating a q-ary sequence is investigated. The q-ary output sequence of that device is considered as the running-key sequence in a stream cipher. Possible definitions for Correlation-Immunity are discussed and a simple condition is given which ensures that divide-and-conquer attacks on such generators are prevented. <s> BIB002 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Divide and Conquer Attack <s> Alphal is a stream cipher with a key size of 128 bits. It was proposed as a replacement algorithm for the stream cipher A5 to supply confidentiality over mobile communication systems. Alphal consists of four binary linear feedback shift registers. Previous attacks on Alphal only recover the initial state of the shortest register. In this paper we present a complete divide and conquer attack, starting with an improved attack on the shortest register, and continuing the attack to recover the remaining three registers. Although Alphal is a 128-bit stream cipher, the key can be recovered through this divide and conquer attack with complexity 2 61 , using 35,000 bits of known plaintext. <s> BIB003
Divide and conquer is a common technique to divide the problem into small problems and try to solve the problem step by step. The same strategy is applied in case of divide and conquer attack where a cipher is partitioned into components and only a few key bits are determined in each stage. First the most vulnerable components are attacked. Siegenthaler BIB001 originally pointed out this concept. The attack can be termed as successful only if complexities of all the stages are smaller than the exhaustive key search. Some examples of attack are BIB003  . High correlation immunity decreases the vulnerability to divide and conquer attack BIB002 .