Cryptanalysis Techniques for Stream Cipher: A Survey
---
paper_title: Understanding Cryptography: A Textbook for Students and Practitioners

paper_content:

Cryptography is now ubiquitous moving beyond the traditional environments, such as government communications and banking systems, we see cryptographic techniques realized in Web browsers, e-mail programs, cell phones, manufacturing systems, embedded software, smart buildings, cars, and even medical implants. Today's designers need a comprehensive understanding of applied cryptography. After an introduction to cryptography and data security, the authors explain the main techniques in modern cryptography, with chapters addressing stream ciphers, the Data Encryption Standard (DES) and 3DES, the Advanced Encryption Standard (AES), block ciphers, the RSA cryptosystem, public-key cryptosystems based on the discrete logarithm problem, elliptic-curve cryptography (ECC), digital signatures, hash functions, Message Authentication Codes (MACs), and methods for key establishment, including certificates and public-key infrastructure (PKI). Throughout the book, the authors focus on communicating the essentials and keeping the mathematics to a minimum, and they move quickly from explaining the foundations to describing practical implementations, including recent topics such as lightweight ciphers for RFIDs and mobile devices, and current key-length recommendations. The authors have considerable experience teaching applied cryptography to engineering and computer science students and to professionals, and they make extensive use of examples, problems, and chapter reviews, while the books website offers slides, projects and links to further resources. This is a suitable textbook for graduate and advanced undergraduate courses and also for self-study by engineers.
---
paper_title: Differential Power Analysis of Stream Ciphers

paper_content:

Side-channel attacks on block ciphers and public key algorithms have been discussed extensively. However, there is only sparse literature about side-cannel attacks on stream ciphers. The few existing references mainly treat timing [8] and template attacks [10], or provide a theoretical analysis [6], [7] of weaknesses of stream cipher constructions. In this paper we present attacks on two focus candidates, Trivium and Grain, of the eSTREAM stream cipher project. The attacks exploit the resynchronization phase of ciphers. A novel concept for choosing initial value vectors is introduced, which totally eliminates the algorithmic noise of the device, leaving only the pure side-channel signal. This attack allows to recover the secret key with a small number of samples and without building templates. To prove the concept we apply the attack to hardware implementations of the ciphers. For both stream ciphers we are able to reveal the complete key.
---
paper_title: Side-Channel Attacks: Ten Years After Its Publication and the Impacts on Cryptographic Module Security Testing

paper_content:

Side-channel attacks are easy-to-implement whilst powerful attacks against cryptographic implementations, and their targets range from primitives, protocols, modules, and devices to even systems. These attacks pose a serious threat to the security of cryptographic modules. In consequence, cryptographic implementations have to be evaluated for their resistivity against such attacks and the incorporation of different countermeasures has to be considered. This paper surveys the methods and techniques employed in these attacks, the destructive effects of such attacks, the countermeasures against such attacks and evaluation of their feasibility and applicability. Finally, the necessity and feasibility of adopting this kind of physical security testing and evaluation in the development of FIPS 140-3 standard are explored. This paper is not only a survey paper, but also more a position paper.
---
paper_title: A Practical Implementation of the Timing Attack

paper_content:

When the running time of a cryptographic algorithm is non-constant, timing measurements can leak information about the secret key. This idea, first publicly introduced by Kocher, is developed here to attack an earlier version of the CASCADE smart card. We propose several improvements on Kocher’s ideas, leading to a practical implementation that is able to break a 512-bit key in few hours, provided we are able to collect 300000 timing measurements (128-bit keys can be recovered in few seconds using a personal computer and less than 10000 samples). We therefore show that the timing attack represents an important threat against cryptosystems, which must be very seriously taken into account.
---
paper_title: Differential power analysis

paper_content:

Cryptosystem designers frequently assume that secrets will be manipulated in closed, reliable computing environments. Unfortunately, actual computers and microchips leak information about the operations they process. This paper examines specific methods for analyzing power consumption measurements to find secret keys from tamper resistant devices. We also discuss approaches for building cryptosystems that can operate securely in existing hardware that leaks information.
---
paper_title: Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers

paper_content:

In 1980 Hellman introduced a general technique for breaking arbitrary block ciphers with N possible keys in time T and memory M related by the tradeoff curve TM2 = N2 for 1 ≤ T ≤ N. Recently, Babbage and Golic pointed out that a different TM = N tradeoff attack for 1 ≤ T ≤ D is applicable to stream ciphers, where D is the amount of output data available to the attacker. In this paper we show that a combination of the two approaches has an improved time/memory/data tradeoff for stream ciphers of the form TM2D2 = N2 for any D2 ≤ T ≤ N. In addition, we show that stream ciphers with low sampling resistance have tradeoff attacks with fewer table lookups and a wider choice of parameters.
---
paper_title: Real Time Cryptanalysis of A5/1 on a PC

paper_content:

A5/1 is the strong version of the encryption algorithm used by about 130 million GSM customers in Europe to protect the over-the-air privacy of their cellular voice and data communication. The best published attacks against it require between 240 and 245 steps. This level of security makes it vulnerable to hardware-based attacks by large organizations, but not to software-based attacks on multiple targets by hackers. ::: ::: In this paper we describe new attacks on A5/1, which are based on subtle flaws in the tap structure of the registers, their noninvertible clocking mechanism, and their frequent resets. After a 248 parallelizable data preparation stage (which has to be carried out only once), the actual attacks can be carried out in real time on a single PC. ::: ::: The first attack requires the output of the A5/1 algorithm during the first two minutes of the conversation, and computes the key in about one second. The second attack requires the output of the A5/1 algorithm during about two seconds of the conversation, and computes the key in several minutes. The two attacks are related, but use different types of time-memory tradeoffs. The attacks were verified with actual implementations, except for the preprocessing stage which was extensively sampled rather than completely executed. ::: ::: REMARK: We based our attack on the version of the algorithm which was derived by reverse engineering an actual GSM telephone and published at http://www.scard.org. We would like to thank the GSM organization for graciously confirming to us the correctness of this unofficial description. In addition, we would like to stress that this paper considers the narrow issue of the cryptographic strength of A5/1, and not the broader issue of the practical security of fielded GSM systems, about which we make no claims.
---
paper_title: Improved “exhaustive search” attacks on stream ciphers

paper_content:

Given a certain amount of known keystream from a keystream generator (KG), the most obvious way to determine the state of the generator is to search through all possible states, checking for a match between the resulting and observed keystream. In this paper, we draw attention to two attacks on stream cipher systems which, although their complexity grows exponentially with the size of the KG state, are more efficient than a simple-minded search through all possible KG states. Indeed, given sufficient storage and sufficient known keystream, each attack can almost halve the effective entropy of the state to be searched.
---
paper_title: Cryptanalysis of alleged A5 stream cipher

paper_content:

A binary stream cipher, known as A5, consisting of three short LFSRs of total length 64 that are mutually clocked in the stop/go manner is cryptanalyzed. It is allegedly used in the GSM standard for digital cellular mobile telephones. Very short keystream sequences are generated from different initial states obtained by combining a 64-bit secret session key and a known 22-bit public key. A basic divide-and-conquer attack recovering the unknown initial state from a known keystream sequence is first introduced. It exploits the specific clocking rule used and has average computational complexity around 240. A time-memory trade-off attack based on the birthday paradox which yields the unknown internal state at a known time for a known keystream sequence is then pointed out. The attack is successful if T ċ M ≥ 2633.32, where T and M are the required computational time and memory (in 128-bit words), respectively. The precomputation time is O(M) and the required number of known keystream sequences generated from different public keys is about T/102. For example, one can choose T ≅ 227.67 and M ≅ 235.65. To obtain the secret session key from the determined internal state, a so-called internal state reversion attack is proposed and analyzed by the theory of critical and subcritical branching processes.
---
paper_title: A New Distinguisher for Clock Controlled Stream Ciphers

paper_content:

In this paper we present a distinguisher targeting towards irregularly clocked filter generators. The attack is applied on the irregularly clocked stream cipher called LILI-II. LILI-II is the successor of the cipher LILI-128 and its design was published in [1]. There have been no known attacks better than exhaustive key search on LILI-II. Our attack is the first of this kind that distinguishes the cipher output from a random source using 2103 bits of keystream using computational complexity of approximately 2103 operations.
---
paper_title: Distinguishing Attacks on the Stream Cipher Py

paper_content:

The stream cipher Py designed by Biham and Seberry is a submission to the ECRYPT stream cipher competition. The cipher is based on two large arrays (one is 256 bytes and the other is 1040 bytes) and it is designed for high speed software applications (Py is more than 2.5 times faster than the RC4 on Pentium III). The paper shows a statistical bias in the distribution of its output-words at the 1st and 3rd rounds. Exploiting this weakness, a distinguisher with advantage greater than 50% is constructed that requires 2 84.7 randomly chosen key/IV's and the first. 24 output bytes for each key. The running time and the data required by the distinguisher are t ini 2 84,7 and 2 89.2 respectively (t ini denotes the running time of the key/IV setup). We further show that the data requirement can be reduced by a factor of about 3 with a distinguisher that considers outputs of later rounds. In such case the running time is reduced to t r .2 84.7 (t, denotes the time for a single round of Py). The Py specification allows a 256-bit key and a keystream of 2 64 bytes per key/IV. As an ideally secure stream cipher with the above specifications should be able to resist the attacks described before, our results constitute an academic break of Py. In addition we have identified several biases among pairs of bits; it seems possible to combine all the biases to build more efficient distinguishers.
---
paper_title: On the Applicability of Distinguishing Attacks Against Stream Ciphers

paper_content:

We demonstrate that the existence of distinguishing attacks against stream ciphers is unrelated to their security in practical use, and in particular that the amount of data required to perform a distinguishing attack is unrelated to the key length of the cipher. The implication for the NESSIE Project is that no submitted symmetric cipher would be accepted under the unpublished rules for distinguishing attacks, not even the block ciphers in Counter Mode or Out-
---
paper_title: On the Optimality of Linear, Differential, and Sequential Distinguishers

paper_content:

In this paper, we consider the statistical decision processes behind a linear and a differential cryptanalysis. By applying techniques and concepts of statistical hypothesis testing, we describe precisely the shape of optimal linear and differential distinguishers and we improve known results of Vaudenay concerning their asymptotic behaviour. Furthermore, we formalize the concept of sequential distinguisher and we illustrate potential applications of such tools in various statistical attacks.
---
paper_title: On the (In)security of Stream Ciphers Based on Arrays and Modular Addition

paper_content:

Stream ciphers play an important role in symmetric cryptology because of their suitability in high speed applications where block ciphers fall short. A large number of fast stream ciphers or pseudorandom bit generators (PRBG's) can be found in the literature that are based on arrays and simple operations such as modular additions, rotations and memory accesses (e.g. RC4, RC4A, Py, Py6. ISAAC etc.). This paper investigates the security of array-based stream ciphers (or PRBG's) against certain types of distinguishing attacks in a unified way. We argue, counter-intuitively, that the most useful characteristic of an array, namely, the association of array-elements with unique indices, may turn out to be the origins of distinguishing attacks if adequate caution is not maintained. In short, an adversary may attack a cipher simply exploiting the dependence of array-elements on the corresponding indices. Most importantly, the weaknesses are not eliminated even if the indices and the array-elements are made to follow uniform distributions separately. Exploiting these weaknesses we build distinguishing attacks with reasonable advantage on five recent stream ciphers (or PRBG's), namely, Py6 (2005, Biham et al.), IA, ISAAC (1996, Jenkins Jr.), NGG, GGHN (2005, Gong et al.) with data complexities 2 68.61 , 2 32.59 , 2 16.89 , 2 32.89 and 2 32.89 respectively. In all the cases we worked under the assumption that the key-setup algorithms of the ciphers produced uniformly distributed internal states. We only investigated the mixing of bits in the keystream generation algorithms. In hindsight, we also observe that the previous attacks on the other array-based stream ciphers (e.g. Py, etc.), can also be explained in the general framework developed in this paper. We hope that our analyses will be useful in the evaluation of the security of stream ciphers based on arrays and modular addition.
---
paper_title: Statistical Analysis of the Alleged RC4 Keystream Generator

paper_content:

The alleged RC4 keystream generator is examined, and a method of explicitly computing digraph probabilities is given. Using this method, we demonstrate a method for distinguishing 8-bit RC4 from randomness. Our method requires less keystream output than currently published attacks, requiring only 230:6 bytes of output. In addition, we observe that an attacker can, on occasion, determine portions of the internal state with nontrivial probability. However, we are currently unable to extend this observation to a full attack.
---
paper_title: A Distinguishing Attack of SNOW 2.0 with Linear Masking Method

paper_content:

SNOW 2.0 was developed by Johansson and Ekdahl in 2002, as a modified version of SNOW 1.0. In this paper we present the application of linear (masking) attack to SNOW 2.0 stream cipher. Our attack requires 2225 output words (2230 bits) and 2225 steps of analysis to distinguish the output of SNOW 2.0 from a truly random bit sequence.
---
paper_title: Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt

paper_content:

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.
---
paper_title: An Analysis of Linear Feedback Shift Registers in Stream Ciphers

paper_content:

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
---
paper_title: Algebraic attacks on stream ciphers with linear feedback

paper_content:

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.
---
paper_title: Algebraic attacks on combiners with memory

paper_content:

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.
---
paper_title: Improving Fast Algebraic Attacks

paper_content:

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.
---
paper_title: An Improved Fast Correlation Attack on Stream Ciphers

paper_content:

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.
---
paper_title: A fast correlation attack for LFSR-based stream ciphers

paper_content:

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.
---
paper_title: Decrypting a Class of Stream Ciphers Using Ciphertext Only

paper_content:

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.
---
paper_title: Fast correlation attacks on stream ciphers

paper_content:

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.
---
paper_title: Fast Correlation Attacks based on Turbo Code Techniques

paper_content:

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.
---
paper_title: Improved Fast Correlation Attacks Using Parity-Check Equations of Weight 4 and 5

paper_content:

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.
---
paper_title: A Low-Complexity and High-Performance Algorithm for the Fast Correlation Attack

paper_content:

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.
---
paper_title: Exploiting Multiples of the Connection Polynomial in Word-Oriented Stream Ciphers

paper_content:

This paper describes some attacks on word-oriented stream ciphers that use a linear feedback shift register (LFSR) and a non-linear filter. These attacks rely on exploiting linear relationships corresponding to multiples of the connection polynomial that define the LFSR.
---
paper_title: Cryptanalysis of stream ciphers with linear masking

paper_content:

We describe a cryptanalytical technique for distinguishing some stream ciphers from a truly random process. Roughly, the ciphers to which this method applies consist of a non-linear process (say, akin to a round function in block ciphers), and a linear process such as an LFSR (or even fixed tables). The output of the cipher can be the linear sum of both processes. To attack such ciphers, we look for any property of the non-linear process that can be distinguished from random. In addition, we look for a linear combination of the linear process that vanishes. We then consider the same linear combination applied to the cipher's output, and try to find traces of the distinguishing property. In this report we analyze two specific distinguishing properties. One is a linear approximation of the non-linear process, which we demonstrate on the stream cipher SNOW. This attack needs roughly 2 95 words of output, with work-load of about 2 100 . The other is a low-diffusion attack, that we apply to the cipher Scream-0. The latter attack needs only about 2 43 bytes of output, using roughly 2 50 space and 2 80 time.
---
paper_title: A Distinguishing Attack of SNOW 2.0 with Linear Masking Method

paper_content:

SNOW 2.0 was developed by Johansson and Ekdahl in 2002, as a modified version of SNOW 1.0. In this paper we present the application of linear (masking) attack to SNOW 2.0 stream cipher. Our attack requires 2225 output words (2230 bits) and 2225 steps of analysis to distinguish the output of SNOW 2.0 from a truly random bit sequence.
---
paper_title: Decrypting a Class of Stream Ciphers Using Ciphertext Only

paper_content:

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.
---
paper_title: A Complete Divide and Conquer Attack on the Alpha1 Stream Cipher

paper_content:

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.
---
paper_title: Design of Combiners to Prevent Divide and Conquer Attacks

paper_content:

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.
---

Title: Cryptanalysis Techniques for Stream Cipher: A Survey

Section 1: INTRODUCTION
Description 1: This section introduces the basic concepts of cryptography and cryptanalysis, explains the importance of cryptanalysis, and briefly discusses the categorization of cryptographic algorithms with a focus on stream ciphers.

Section 2: CRYPTANALYSIS TECHNIQUES
Description 2: This section outlines various cryptanalysis techniques used against stream ciphers and provides a brief description of each technique.

Section 3: Exhaustive Key Search Attack
Description 3: This section describes the exhaustive key search attack, also known as brute force attack, and details the computational complexity involved in this type of attack.

Section 4: Side Channel Analysis Attack
Description 4: This section discusses side channel analysis attacks based on physically observable characteristics during the execution of cryptographic algorithms.

Section 5: Time Memory Tradeoff Attacks
Description 5: This section covers time memory tradeoff attacks, explaining the two phases (offline and online) and discussing historical implementations and refinements of the technique.

Section 6: Distinguishing Attack
Description 6: This section explains distinguishing attacks, their methodology, and how they identify relationships between internal state variables and output keystream.

Section 7: Algebraic Attack
Description 7: This section outlines algebraic attacks, detailing their focus on modeling cryptographic systems as algebraic equations and their effectiveness against LFSR based ciphers.

Section 8: Correlation Attacks
Description 8: This section describes correlation attacks, their application to stream ciphers with feedback shift register designs, and improvements made over time.

Section 9: Guess-and-Determine Attacks
Description 9: This section details guess-and-determine attacks, explaining the process of guessing parts of the internal state to recover full values of internal states.

Section 10: Linear Masking Attacks
Description 10: This section discusses linear masking attacks, which are applicable to ciphers with non-linear processing disguised by linear masking.

Section 11: Related Key Attack
Description 11: This section describes related key attacks, which exploit relationships between keys generated in cryptographic protocols.

Section 12: Divide and Conquer Attack
Description 12: This section explains the divide and conquer strategy, its application to cryptanalysis, and the conditions under which this attack is successful.

Section 13: CONCLUSION
Description 13: This section summarizes the existing cryptanalytic attacks on stream ciphers and emphasizes the importance of considering these attacks during the development of new cryptographic primitives.