Cryptanalysis Techniques for Stream Cipher: A Survey <s> Algebraic Attack <s> Many stream ciphers are built of a linear sequence generator and a non-linear output function f. There is an abundant literature on (fast) correlation attacks, that use linear approximations of f to attack the cipher. In this paper we explore higher degree approximations, much less studied. We reduce the cryptanalysis of a stream cipher to solving a system of multivariate equations that is overdefined (much more equations than unknowns). We adapt the XL method, introduced at Eurocrypt 2000 for overdefined quadratic systems, to solving equations of higher degree. Though the exact complexity of XL remains an open problem, there is no doubt that it works perfectly well for such largely overdefined systems as ours, and we confirm this by computer simulations. We show that using XL, it is possible to break stream ciphers that were known to be immune to all previously known attacks. For example, we cryptanalyse the stream cipher Toyocrypt accepted to the second phase of the Japanese government Cryptrec program. Our best attack on Toyocrypt takes 2 92 CPU clocks for a 128-bit cipher. The interesting feature of our XL-based higher order correlation attacks is, their very loose requirements on the known keystream needed. For example they may work knowing ONLY that the ciphertext is in English. <s> BIB001 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Algebraic Attack <s> A classical construction of stream ciphers is to combine several LFSRs and a highly non-linear Boolean function f. Their security is usually analysed in terms of correlation attacks, that can be seen as solving a system of multivariate linear equations, true with some probability. At ICISC'02 this approach is extended to systems of higher-degree multivariate equations, and gives an attack in 292 for Toyocrypt, a Cryptrec submission. In this attack the key is found by solving an overdefined system of algebraic equations. In this paper we show how to substantially lower the degree of these equations by multiplying them by well-chosen multivariate polynomials. Thus we are able to break Toyocrypt in 249 CPU clocks, with only 20 Kbytes of keystream, the fastest attack proposed so far. We also successfully attack the Nessie submission LILI-128, within 257 CPU clocks (not the fastest attack known). In general, we show that if the Boolean function uses only a small subset (e.g. 10) of state/LFSR bits, the cipher can be broken, whatever is the Boolean function used (worst case). Our new general algebraic attack breaks stream ciphers satisfying all the previously known design criteria in at most the square root of the complexity of the previously known generic attack. <s> BIB002 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Algebraic Attack <s> Recently, algebraic attacks were proposed to attack several cryptosystems, e.g. AES, LILI-128 and Toyocrypt. This paper extends the use of algebraic attacks to combiners with memory. A (k,l)-combiner consists of k parallel linear feedback shift registers (LFSRs), and the nonlinear filtering is done via a finite automaton with k input bits and l memory bits. It is shown that for (k, l)-combiners, nontrivial canceling relations of degree at most [k(l+1)/2] exist. This makes algebraic attacks possible. Also, a general method is presented to check for such relations with an even lower degree. This allows to show the invulnerability of certain (k,l)-combiners against this kind of algebraic attacks. On the other hand, this can also be used as a tool to find improved algebraic attacks. Inspired by this method, the E 0 keystream generator from the Bluetooth standard is analyzed. As it turns out, a secret key can be recovered by solving a system of linear equations with 2 23.07 unknowns. To our knowledge, this is the best published attack on the E 0 keystream generator yet. <s> BIB003 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Algebraic Attack <s> An algebraic attack is a method for cryptanalysis which is based on finding and solving a system of nonlinear equations. Recently, algebraic attacks where found helpful in cryptanalysing LFSR-based stream ciphers. The efficiency of these attacks greatly depends on the degree of the nonlinear equations. At Crypto 2003, Courtois [8] proposed Fast Algebraic Attacks. His main idea is to decrease the degree of the equations using a precomputation algorithm. Unfortunately, the correctness of the precomputation step was neither proven, nor was it obvious. The three main results of this paper are the following: First, we prove that Courtois' precomputation step is applicable for cryptographically reasonable LFSR-based stream ciphers. Second, we present an improved precomputation algorithm. Our new precomputation algorithm is parallelisable, in contrast to Courtois' algorithm, and it is more efficient even when running sequentially. Third, we demonstrate the improved efficiency of our new algorithm by applying it to the key stream generator E 0 from the Bluetooth standard. In this case, we get a theoretical speed-up by a factor of about 8, even without any parallelism. This improves the fastest attack known. Practical tests confirm the advantage of our new precomputation algorithm for the test cases considered. <s> BIB004 </s> Cryptanalysis Techniques for Stream Cipher: A Survey <s> Algebraic Attack <s> Linear Feedback Shift Registers (LFSRs) have always received considerable attention in cryptography. Owing to the good statistical properties, large period and low implementation costs, LFSR have achieved wide acceptance in developing stream ciphers. This paper intends to present a self-contained and comprehensive analysis of linear feedback shift registers and their application in stream ciphers. This research focuses on analyzing the mechanism of an LFSR, the two implementation variations and various properties of LFSR, which play a vital role in stream cipher design. In the last section of this paper, we address the security aspect of LFSR based stream ciphers and different techniques to enhance it. General Terms Design, Security, Cryptography, Algorithms <s> BIB005
Algebraic attacks are relatively new attacks for stream ciphers and progress is rapidly taking place in this field. Algebraic attacks are very much effective against LFSR based ciphers BIB005 . The basic principle of algebraic attacks is to model a cryptographic system in terms of algebraic equations. The first step of this attack is to find the set of algebraic equations that relate the initial state with the output keystream, then keystream bits are observed and these values are substituted into the equations. Attackers try to collect maximum possible keystream bits. Finally, this system of equations is solved to determine the initial state and then derive the secret key from it. Courtois in BIB001 against Toycrypt first proposed algebraic Attack on stream cipher and later it was used on LILI-128 BIB002 . This attack was also successfully applied to the stream ciphers with memory that were assumed to be more secure against this attack BIB003  . Later on Courtois further enhanced this attack and proposed Fast Algebraic attack  that was further strengthened by Armknecht BIB004 . The idea behind fast algebraic attack was to get equations of lower degree by linearly combining the equations before solving the system of equation that drastically increases the speed of the attack.